Выделение и сопоставление особых точек в обработке изображений Александр Мордвинцев, СПбГУ ИТМО, НИИ НКТ

Мотивация

План Выделение особых точек (feature point detection) – Harris, LoG, DoG, MSER, FAST … Построение дескрипторов (feature description) – SIFT, SURF, BRIEF, DAISY … Feature matching Applications

Поиск особых точек Повторяемость – Детектор находит одни и те же точки на разных кадрах Эффективность – Особых точек значительно меньше, чем пикселей

Поиск особых точек традиционный подход Функция «особенности» Saliency function Порог Локальные максимумы

Локальная особенность: угол Ищем точки, окрестность которых сильно изменяется при смещении в любом направлении Монотонный регион (-) Край (-)Угол (+)

Детектор углов Харриса Harris Corner Detector Окно (напр. Гауссиан) Окно (напр. Гауссиан) Яркость точки окрестности Яркость точки окрестности Яркость смещенной точки Яркость смещенной точки Матрица произведений производных в точке (x, y) Матрица произведений производных в точке (x, y) Аппроксимация E квадратичной формой Матрица моментов, структурный тензор…

Детектор углов Харриса функции особенности λ 1 и λ 2 – собственные числа матрицы M Инвариантны к повороту Частично инвариантны к перемене освещенности

Структурный тензор Второй собственный вектор матрицы M указывает направление текстуры Обобщается на трехмерное пространство

Выбор масштаба Проблема: детектор Харриса не инвариантен к масштабу изображения Необходим выбор масштаба Локальная особенность: капля (blob) – Более яркое (или темное), чем фон, пятно на изображении «Край» Угол!

Лапласиан Гауссиана Положение локальных максимумов LoG определяет положение и масштаб особой точки Комбинируется с детектором Харриса для вычисления масштаба углов Аппроксимации используются в детекторах SIFT, SURF и многих других

Детектор областей MSER MSER - Maximally Stable Extremal Region Устойчивые к бинаризации с различным порогом участки изображения Эффективно реализуется при помощи системы непересекающихся множеств Инвариантен к аффинным преобразованиям

Точка особенная, если в на кольце радиуса r есть дуга из N последовательных пикселей, все из которых – Значительно темнее p – Значительно светлее p Детектор FAST: идея

Классифицируем пиксели кольца по порогу t на светлые, темные и серые. Окрестность точки описывается тренарным вектором Строим решающее дерево для классификации векторов на особые/не особые Результат - >4000 строк вложенных if-else Но в среднем всего 2.26 сравнений на пиксель для r = 3, N=9. Работает очень быстро Детектор FAST: реализация

Дескрипторы особенностей Описывают окрестность каждой особой точки набором параметров Должны быть: – специфичны – локальны – устойчивы – просты в вычислении – иметь адекватную метрику

Дескрипторы особенностей Простейшие (не)ориентированные окна

Гистограммы градиентов (SIFT) Ориентация точки (поиск доминирующего градиента) Бьем ориентированную окрестность регулярной сеткой (обычно 4x4) Строим гистограмму градиентов, попавших в каждую ячейку (обычно 8 бинов) Получаем вектор из 4*4*8=128. Нормализуем. Это и есть дескриптор SIFT

Дескриптор BRIEF При разработке дескриптора генерируем случайный набор пар двухмерных векторов смещений (x i, x i) Дескриптор точки p b(p) - вектор из N= булевых значений Метрика Хемминга для сравнения дескрипторов

Сравнение дескрипторов Имеем два набора дескрипторов, хотим найти соответствия – Критерий 1-NN distance – 1-NN / 2-NN distance Используем вероятностный индекс для поиска ближайших соседей в многомерном пространстве (FLANN)

Модель трансформации между изображениями RANSAC Регистрация изображений

Приложения, демонстрации.

Ссылки Richard Szeliski Computer Vision: Algorithms and Applications ( Feature detectors – – – Space-time interest points Space-time interest points Descriptors – – – (BRIEF) – – Applications – – –