Швидка реєстрація особливих точок зображень за допомогою голосування біграфа

Детектування та реєстрація особливостей зображень має багато додатків у робототехніці, відео компресії тощо. Швидка і акуратна реєстрація - поки недосяжна мрія багатьох програмістів і користувачів. Вона або швидка, або акуратна...

Я досить давно (близько 17 років), працюю над обробкою зображень, в тому числі реконструювання 3D mesh з відео і навіть є своя компанія продає такий продукт. Однак вирішив частину розробки і ключову ідею викласти у відкритий доступ без патентного блокування

Загальна ідея існуючих відносно швидких алгоритмів наступна:

1. (Feature detection) Знайти якісь особливі точки на кожній картинці, бажано з субпіксельною точністю.
2. (Feature description) Побудувати якийсь масив ознак для кожної точки, який повністю або частково задовольняє наступним вимогам:
   • Інваріантність до:
     • (Фізика) шуми, зміни витримки (яскравість і контраст), артефакти стиснення
     • (Геометрія 2D) поворотів, зсувів, масштабування
     • (Геометрія 3D) проекційних спотворень
   • Компактність (менше пам'яті, швидше порівняння)
   • Різновиди (Біля виділеної точки в певному визначеному патерні):
   • Гістограма градієнтів, яскравості, кольорів. (SIFT,SURF ...)
3. Видирання значень і нормалізація рівня (ORB, BRIFF...)
4. Для пари картинок знайти відповідності точок за допомогою мінімальної відстані (сума абсолютних різниць (L1) або сума квадратів різниць (L2)) між масивами ознак, асимптотична складність даного кроку О (N ^ 2), де N - число особливих точок.
5. (Необов'язково): Перевірити геометричну сумісність пар за допомогою RANSAC і повторити крок 3

Пропонована схема реєстрації наступна.

Для кожної картинки (detect):

1. Знайти особливі точки
2. Розділити особливі точки на 2 групи за ознакою знака різниці (DoG) між значенням в точці і середнього в малій околиці.
3. Для кожної точки з першої групи знайти приблизно десяток сусідів.

На даному етапі ми маємо біграф з ауд N/2 * 10 орієнтованих ребер

4. Для кожного ребра семплюємо в точках патерну масштабованого і повернутого разом з руба
5. Будуємо бітовий (ауд 26 біт) hash c допомогою порівняння відліків

Для реєстрації (bind):

1. Будуємо LUT з ребер правої картинки за hash значенням
2. Для кожного ребра з лівої картинки шукаємо О (1) ребро (ребра) з тим же hash в LUT
3. Дописуємо 2 індекси точок з лівого ребра в 2 індексу точок з правого
4. Проходимо по всіх точках правої картинки і підраховуємо число голосів

Результат:

для ФуллГД на i7-6900K using single core

Приблизно 10000 точок на кожне зображення

detect 29.0556 ms /per image

bind 10.46563 ms /per pair

Переваги: швидкий, надійний при малих перспективних спотвореннях (мала кількість неправильно пов'язаних точок), простий код, не закритий патентами (наскільки мені відомо).

Власне початковий код

На базі цієї схеми зараз пишу заготовку для Raspberry Pi SLAM, у вільний від роботи час.