Зіставлення зображень на основі пошуку найближчих сусідів в просторі параметрів

Abstract

В задачах комп'ютерного зору та обробки зображень часто виникає необхідність проведення процесу зіставлення точок двох зображень, наприклад, для пошуку об'єктів на зображеннях або для відновлення тривимірних геометричних моделей сцени. В той же час, не існує загального методу визначення чітких точкових відповідностей на зображеннях. В роботі запропоновано підхід до визначення пар ключових точок на зображеннях на основі розбиття простору параметрів на регулярну сітку і представлення такої сітки в вигляді просторової хеш-таблиці для прискорення пошуку. Підхід дозволяє визначати стійкі пари ключових точок на двох зображеннях, що дозволяє його використання в задачах стереозору для відновлення тривимірних моделей поверхонь і для пошуку об’єктів на зображеннях. Представлений підхід складається з наступних кроків: визначення ключових точок з використанням дескрипторів; зіставлення ключових точок на основі побудови двовимірного простору параметрів, який формується з розміру і кута орієнтації дескриптора; розбиття простору параметрів на регулярну сітку; побудова хеш-таблиці на основі сітки, в якості значень в комірках хеш-таблиці містяться кількість пар ключових точок з близькими значеннями розміру і орієнтації дескриптора, що відповідають даній комірці; пошук в хеш-таблиці комірки, що міститиме найбільшу кількість точок, така комірка відповідатиме найбільш стійким відповідностям ключових точок на зображеннях. Представлений алгоритм може бути розширений для роботи з довільною кількістю параметрів. Запропонований алгоритм дозволяє проводити зіставлення ключових точок на зображеннях за час O(n).