Быстрая Регистрация Особых Точек Изображений С Помощью Биграфового Голосования.

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

Она либо быстрая, либо аккуратная.

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

Общая идея существующих относительно быстрых алгоритмов такова:

(Обнаружение особенностей) Найдите любые особые точки на каждом изображении, желательно с точностью до субпикселя.
(Описание признака) Постройте для каждой точки массив признаков, полностью или частично удовлетворяющий следующим требованиям:
- Инвариантность к:
  - (Физический) шум, изменения выдержки (яркость и контрастность), артефакты сжатия
  - (2D-геометрия) вращения, перемещения, масштабирование
  - (3D-геометрия) искажение проекции
- Компактный (меньше памяти, более быстрое сравнение)
- Разновидности (около выбранной точки в определенном заранее заданном шаблоне):
- Гистограмма градиентов, яркости, цветов.
  (просеивание, серфинг.
  )
Чтение значений и нормализация уровня.
(ORB,BRIFF.)
Для пары изображений найдите точки соответствия, используя минимальное расстояние (сумму абсолютных разностей (L1) или сумму квадратов разностей (L2)) между массивами признаков, асимптотическая сложность этого шага равна O(N^2), где N — количество особых точек.
(Необязательно): Проверьте геометрическую совместимость пар, например, с помощью РАНСАК и повторите шаг 3

Предлагаемая схема регистрации следующая.

Для каждого изображения (обнаружить):

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

Найдите особые точки
Особые точки разделим на 2 группы по знаку разности ( Собака ) между значением в точке и средним значением в небольшой окрестности.
Для каждой точки из первой группы найдите около десятка соседей.
На этом этапе у нас есть биграф из ~N/2*10 ориентированных ребер.
Для каждого края мы отбираем точки шаблона, масштабированные и поворачиваемые вместе с краем.
Мы строим битовый (~26 бит) хэш, используя сравнение образцов.

Для регистрации (привязки):

Мы строим ЛУТ от краев правой картинки по хеш-значению
Для каждого ребра на левом рисунке мы ищем O(1) ребер с одинаковым хешем в LUT.
Добавляем 2 индекса точек с левого края к 2 индексам точек с правого края
Проходим по всем пунктам правой картинки и подсчитываем количество голосов

Результат: для FullHD на i7-6900K с использованием одного ядра Примерно 10 000 точек на изображение обнаружить 29,0556 мс/на изображение связывание 10,46563 мс/на пару Достоинства: быстрый, надежный с небольшими искажениями перспективы (маленькое количество неправильно соединенных точек), простой код, не запатентованный (насколько мне известно).

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

Фактический исходный код Сейчас я пишу шаблон для Raspberry Pi на основе этой схемы.