Image matching based on nearest neighbor search in parameter space

В задачах комп'ютерного зору та обробки зображень часто виникає необхідність проведення процесу зіставлення точок двох зображень, наприклад, для пошуку об'єктів на зображеннях або для відновлення тривимірних геометричних моделей сцени. В той же час, не існує загального методу визначення чітких точкових відповідностей на зображеннях. В роботі запропоновано підхід до визначення пар ключових точок на зображеннях на основі розбиття простору параметрів на регулярну сітку і представлення такої сітки в вигляді просторової хеш-таблиці для прискорення пошуку. Підхід дозволяє визначати стійкі пари ключових точок на двох зображеннях, що дозволяє його використання в задачах стереозору для відновлення тривимірних моделей поверхонь і для пошуку об’єктів на зображеннях. Представлений підхід складається з наступних кроків: визначення ключових точок з використанням дескрипторів; зіставлення ключових точок на основі побудови двовимірного простору параметрів, який формується з розміру і кута орієнтації дескриптора; розбиття простору параметрів на регулярну сітку; побудова хеш-таблиці на основі сітки, в якості значень в комірках хеш-таблиці містяться кількість пар ключових точок з близькими значеннями розміру і орієнтації дескриптора, що відповідають даній комірці; пошук в хеш-таблиці комірки, що міститиме найбільшу кількість точок, така комірка відповідатиме найбільш стійким відповідностям ключових точок на зображеннях. Представлений алгоритм може бути розширений для роботи з довільною кількістю параметрів. Запропонований алгоритм дозволяє проводити зіставлення ключових точок на зображеннях за час O(n).In tasks of computer vision and image processing, it is often necessary to carry out the process of comparing points of two images, for example, to search for objects in images or to restore three-dimensional geometric models of the scene. At the same time, there is no common method for determining stable point correspondences in images. An approach to determine of key point pairs in the images based on a subdivision of parameter space into regular grid and building a spatial hash table over the grid is proposed. Approach, that is developed, provides to determine strong key point pairs in two images, which makes possible to use it in the stereovision problems to surface reconstruction and for object search in the images. The presented approach consists of a sequence of steps: defining key points using descriptors; matching key points based on the construction of a two-dimensional parameter space, which is formed from the size and orientation angle of the descriptor; partitioning the parameter space into a regular grid; constructing a hash table based on the grid; the values in the cells of the hash table contain the number of pairs of key points with similar values of the size and orientation of the descriptors that correspond to this cell; searching in the hash table of the cell with the greatest number of points, such a cell will correspond to the most stable combinations of key points in the images. The presented algorithm can be extended to work with an arbitrary number of parameters and allows for the mapping of key points on images with a time complexitiy of O(n)