[pullquote align=”left|top” textalign=”center” width=”30%”]Лучше один раз увидеть…[/pullquote]

Local features – локальные особенности

Изображение, бесспорно, представляет собой самое емкое и лаконичное представление большего объема “нефильтрованной” информации. Нефильтрованной, потому как в большинстве случаев, в рамках определенной задачи, нам вполне достаточно некоей “выжимки” данных: есть на изображении объект интереса или нет, где он расположен, каковы его характеристики. Эпическое описание сцены со всеми подробностями, как правило, не является предметом первой необходимости. Да и второй тоже.

features – особые точки

Особые точки (в разных источниках – features/characteristic points/local feature points/interest point/локальные особенности) – говоря неформально – “хорошо различимые” фрагменты изображения. Это точки (пиксели) с характерной (особой) окрестностью – т.е. отличающиеся своей окрестностью от всех соседних точек. Классический пример локальной особенности – вершина угла (а не какая-то произвольная точка на прямой или на однородном фоне). Описываются вектором признаков вычисляемых на основе интенсивности/градиентов или других характеристик точек окрестности. Используя особые точки можно  анализировать как изображения целиком так и объекты на них. Хорошие характерные точки позволяют справиться с изменением масштаба, ракурса и перекрытиями сцены или объекта.

Локальные особенности – краеугольный камень во многих высокоуровневых алгоритмах компьютерного зрения: отслеживание (tracking) и распознавание (recognition) объектов, 3d-реконструкция и навигация (SLAM и loop-closure). Используя характерные точки можно вычислить сдвиг (disparity) между двумя изображениями, произвести сегментацию на основе сдвига элементов сцены, рассчитать фундаментальную матрицу для калибровки стерео-пары или проиндексировать изображения для поиска.

Какими должны быть локальные особенности?

• повторяемыми – должны находиться в одном и том же месте сцены независимо от ракурса и освещения
• локальными – (как родинки у человека) – должны быть расположены в малой области и не страдать от перекрытий
• компактными – по сравнению с общим числом пикселей изображения их должно быть в разы меньше
• значимыми – уникальными – каждая особенность должна иметь свое собственное описание (чтобы сложно было перепутать их между собой)

Основные методы поиска локальных особенностей:

• детектор Harris (Forstner)
• детектор Harris-Laplace
• детектор на основе LoG (Laplacian of Gaussian)
• детектор на основе DoG (Difference of Gaussian)

Виды преобразований.

Перед тем как переходить к описанию методов поиска характерных точек имеет смысл освежить в памяти виды геометрических преобразований. Если мы сделаем несколько фотографий одной и той же сцены с разных точек и рассмотрим полученные изображения, можно сказать что имеет место некоторое преобразование точек изображения А в В.

Простейшим видом преобразования является параллельный перенос (сдвиг):

пример преобразования параллельный перенос

Подобие (перенос, масштаб, поворот):.

пример преобразования подобия

Афинное (дает хорошее приближение искажений претерпеваемых небольшим плоским фрагментом объекта при изменении радиуса):

пример аффинного преобразования

Гомография – одна из простых разновидностей проективного преобразования. Это перспективное преобразование плоскости – преобразование между двумя видами одной и той же плоскости или преобразование между видами полученными с повернутой камеры (при общем центре проекций) – съемка со штатива. По сути – преобразование в однородных координатах.

пример преобразования гомография

Если распределить модели преобразований по возрастанию сложности то получится:

поворот -> масштаб -> афинное.

Особняком стоит афинное изменение яркости (съемка сцены в разных условиях освещения) которое хоть и не геометрическое, но также часто встречается на практике.

Как найти локальные особенности?

Локальные особенности бывают простыми – навроде углов и сложными – состоящими из целых регионов изображения – блобов. Как это водится, универсального средства найти все особенности нет. Потому, для каждого типа особенностей существует свой детектор – грубо говоря, фильтр, просевая через который все пиксели изображения можно получить особые точки.

Первым детектором особенностей был детектор углов Харриса (Harris corner detector), построенном на основе того нехитрого факта, что в области вокруг угла у градиента изображения 2 основных направления. Обладает частичной инвариантностью к преобразованиям поворота и к изменению освещения, но не к масштабу.

Масштаб вообще штука коварная – при одном приближении, все точки выглядят одинаково, а чуть отдалишься – начинают просматриваться очертания угла. Характерный масштаб – такой размер окрестности, при которой данная точка является особой.

В качестве детектора, не чувствительного к масштабу была предложена концепция блобов (Blobe) – каплевидных окрестностей, в центре которых расположена особая точка. Внимание – ужас. Для определения таких окрестностей использовались лапласианы гауссианов (LoG – ЛОГ-фильтром) или разница гауссианов (DoG – DOG-фильтром). Несмотря на зловещее название тут тоже все просто. Изображение, как все помнят, мы представляем в виде функции. Лапласиан – сумма вторых частных производных функции в точке. Гауссиан – это просто гауссова функция – которой обрабатывают изображение. Соответственно лапласиан гауссиана – представление функции-изображения после применения оператора Гаусса, через сумму частных производных (его трехмерный график, при некоторой доле воображения, напоминает мексиканскую шляпку или сомбреро).

Характеристический размер блоба, теоретически, можно найти так: провести свертку размытого Гауссом изображения с помощью оператора Лапласа в нескольких масштабах и выбрать тот масштаб, на котором достигается максимальный отклик лапласиана. Для того чтобы это все работало на больших масштабах – необходима нормализация. Именно так и работали первые многомасштабные детекторы блобов. Одно но – лапласианы дорого считать. Лапласиан гауссиана можно приближенно представить в виде разницы двух гауссиан (с различным масштабом) – по русски это значит что мы “размазываем” исходное изображение с помощью оператора Гаусса (с разными значениями сигмы) и вычитаем одно из другого.

Детекторы углов и блобов можно использовать параллельно. На этой нехитрой идее выросли алгоритма Харис-Лапласа (Harris–Laplace) и Хессиан (Hessian affine region detector).
Общая идея – мы также выделяем углы на изображении, но уже с учетом характеристического размера: ищем точки максимизирующие отклик угла Харриса по изображению и отклик Лаплассиана по масштабу. Отклик – это просто значения функции после применения фильтра.

И все бы в этих детекторах было замечательно если бы не суровая правда – мир далеко не так прост. В большинстве алгоритмов для анализа отбираются особые точки, обеспечившие самый высокий отклик. В львиной доле изображений самые сильные точки группируются в сильно текстурированных областях (какие-нибудь кусты на фото). И если мы рассматриваем только их – мы, зачастую, рассматриваем лишь какую-то часть изображения с высокой концентрацией этих точек. Чтобы найти точки равномерно по картинке используются адаптивный радиус. Принцип адаптивного радиуса прост – для каждой найденной особой точки отбрасываем всех соседей в некоторой окрестности и смотрим – хватит нам результирующего набора или нет. Точки рассматриваем в порядке убывания качества.

Развитием идеи блобов явились детекторы областей: EBR (edge-based regions), IBR (Intensity-Extrema-Based Region), MSER (Maximally stable external regions). Характерных областей на изображении будет значительно меньше чем блобов, но, с точки зрения семантического описания сцены, они более информативны. К сожалению, на информацию о применении в практических задачах такого подхода я не натыкался.

Как описать локальные особенности? Дескрипторы особых точек (feature descriptor)

После того как особые точки найдены их надо друг с дружкой сравнивать. Для этого необходимо некоторое компактное представление характерных особенностей. Они должны быть:

• Простыми – представление должно быть быстро вычислимым.
• Уникальными – разные точки должны иметь разное представление.
• Локальными – как и сама особая точка ее представление должно зависеть лишь от небольшой окрестности.
• Инвариантными к максимально большему числу преобразований.

Обычно используется вектор-признаков. И вопрос только в одном – по каким характеристикам вычислять этот дескриптор.

Интуитивно простой способ – отталкиваться от интенсивности пикселей в окрестности точки. Однако, такой подход обеспечивает инвариантность только к сдвигу. Впрочем, для видео, вариант с нормализованной интенсивностью может и подойти (для сравнения можно использовать банальные SAD/SSD). Есть некоторые подходы для создания классификатора не так сильно реагирующего на изменение яркости (нормирование яркости, локальная нормализация гистограмма).

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

Тем не менее, в практических задачах уже давно эталоном стал дескриптор SIFT – Scale-invariant feature transform и его производные – SURF, GLOH и PCA-SIFT. Самый его жирный минус – для использования необходим патент.

Состоит из трех основных компонентов:

• Детектор на основе разницы гауссиан – DoG – служит для определения положения и характерного масштаба особой точки на изображении.
• Гистограмма градиентов, используется для определения ориентации особой точки (берется самый сильный градиент).
• Дескриптор конструируется на основе направлений всех градиентов орестности.

Инвариантен к малому сдвигу и изменениям освещения.

Более компактное представление дескриптора практиковалось в методы PCA-SIFT. Использование цветовой информации нашло свое отражении в дескрипторе RGB-SIFT (3 SIFT для каждого канала) а также C-SIFT, rgSIFT.

С перспективными искажениями (множество всяких разных эллипсов упрямо проецируются в один и тот же круг) используется метод аффинной адаптации.

Для усиления дескриптора, можно учитывать контекст (формы или глобальный) – рассматривая взаиморасположение других особых точек, находящихся в некоторой окрестности вокруг первой точки.

Готовое приложение для сравнения всех детекторов в OpenCV (SIFT, SURF, ORB, FREAK и тд) с гуи и исходниками доступно здесь – https://code.google.com/p/find-object/

Для сравнительно недавнего (2011) сравнения дескрипторов и детекторов особых точек гуглить:
Steffen Gauglitz Tobias Höllerer Matthew Turk
Evaluation of Interest Point Detectors and Feature Descriptors for Visual Tracking

Сравнение дескрипторов:
http://computer-vision-talks.com/2011/08/feature-descriptor-comparison-report/
http://computer-vision-talks.com/2012/08/a-battle-of-three-descriptors-surf-freak-and-brisk/