Быстрая регистрация особых точек изображений с помощью голосования биграфа

Детектирование и регистрация особенностей изображений имеет много приложений в робототехнике, видео компрессии и т.д. Быстрая и аккуратная регистрация — пока недостижимая мечта многих программистов и пользователей. Она или быстрая, или аккуратная…

Я довольно давно (около 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, в свободное от работы время.

Автор: Дмитрий Самсонов

Источник