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

в 18:19, , рубрики: open source, Raspberry Pi, Алгоритмы, Видео регистрация, обработка изображений, Разработка робототехники

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

Я довольно давно (около 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

Быстрая регистрация особых точек изображений с помощью голосования биграфа - 1
Предлагаемая схема регистрации следующая.
Для каждой картинки (detect):

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

  1. Найти особые точки
  2. Разделить особые точки на 2 группы по признаку знака разницы (DoG) между значением в точке и среднего в малой окрестности.
  3. Для каждой точки из первой группы найти примерно десяток соседей.
    На данном этапе мы имеем биграф из ~N/2*10 ориентированных ребер
  4. Для каждого ребра семплируем в точках паттерна масштабированного и повернутого вместе с ребром
  5. Строим битовый (~26 бит) hash c помощью сравнения отсчетов

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

Для регистрации (bind):

  1. Строим LUT из ребер правой картинки по hash значению
  2. Для каждого ребра из левой картинки ищем О(1) ребро(ребра) с тем же hash в LUT
  3. Дописываем 2 индекса точек из левого ребра в 2 индекса точек из правого
  4. Проходим по всем точкам правой картинки и подсчитываем число голосов

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

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

Для примерно 10000 точек на каждое изображение
detect 29.0556 ms /per image
bind 10.46563 ms /per pair

Достоинства: быстрый, надежный при малых перспективных искажениях (малое количество неверно связанных точек), простой код, не закрыт патентами(насколько мне известно).
Быстрая регистрация особых точек изображений с помощью голосования биграфа - 5
Быстрая регистрация особых точек изображений с помощью голосования биграфа - 6
Собственно исходный код
На базе этой схемы сейчас пишу заготовку для Raspberry Pi SLAM, в свободное от работы время.

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

Источник

Поделиться

* - обязательные к заполнению поля