ИСПОЛЬЗОВАНИЕ МЕТОДА SIFT В ЦИФРОВОЙ ОБРАБОТКЕ ИЗОБРАЖЕНИЯ

Введение. Технология SIFT (масштабно-инвариантное преобразование признаков или масштабно-инвариантное преобразование объектов) представляет собой алгоритм обнаружения признаков компьютерного изображения, используемый для идентификации и описания локальных признаков изображения. Алгоритм был запатентован в Канаде Университетом Британской Колумбии и опубликован Дэвидом Лоу в 1999 году [1].

Описание и отслеживание локальных особенностей изображения может помочь идентифицировать объекты. Функции SIFT основаны на некоторой локальной точке появления объекта и не зависят от размера и поворота изображения. Толерантность к свету, шуму и небольшим изменениям угла обзора также достаточно высока. Исходя из этих характеристик, они очень важны, и их относительно легко найти. В большой базе данных объектов легко идентифицировать объекты с помощью нескольких ошибочных идентификаций. Частота обнаружения частичного затемнения объекта с помощью описаний признаков SIFT также достаточно высока: для расчета местоположения и ориентации достаточно даже более 3 описаний признаков SIFT [1]. В зависимости от текущей скорости аппаратного обеспечения компьютера и состояния базы данных с небольшими функциями скорость распознавания может быть близка к работе в режиме реального времени. SIFT содержит большое количество информации, подходящей для быстрого и точного сопоставления в больших базах данных.

В начале, ключевые точки объектов в SIFT извлекаются из набора эталонных изображений и сохраняются в базе данных [2]. Объект распознается на новом изображении путем сравнения каждого признака из нового изображения с признаками из базы данных и поиска признаков-кандидатов на основе евклидова расстояния между векторами признаков. Из полного набора совпадений на новом изображении выбираются подмножества ключевых точек, которые лучше всего соответствуют объекту с точки зрения положения, масштаба и ориентации. Благодаря эффективной реализации обобщенного преобразования Хафа в виде хэш-таблицы можно быстро определить подходящие блоки признаков. Каждый блок из 3 или более признаков, который соответствует объекту и его расположению, подвергается дальнейшей детальной проверке соответствия модели, а выбросы отбрасываются. Наконец, вычисляется вероятность того, что заданный набор признаков указывает на присутствие объекта, что дает представление о точности совпадения и количестве возможных промахов. Объекты, прошедшие все эти тесты, могут считаться правильными с высокой степенью уверенности [3].

В целом алгоритм можно разделить на 6 основных этапов:

1. Построение пирамиды разностей гауссиан выполняется следующим образом:

• Выбираются числа  такие что  
• Из исходного изображения  формируются s изображений  ,такие, что размер   в два раза меньше размера  
• К исходному изображению применяется функция Гауссова размытия (фильтр Гаусса) с разными радиусами :

Где   – изображение,  .

• Рассчитываются пиксельные разности изображений, размытых Гауссовым фильтром

• Формируется h пирамид разностей гауссианов:

2. Определение особых точек. Для этого сравним точку с 26 соседями: по 8 точек на ее уровне в пирамиде Гаусса и по 9 точек на предыдущем и следующем уровнях пирамиды. Если точка является минимальной или максимальной, она включается в список возможных точек.
3. Фильтрация особых точек.  На этом этапе алгоритма из списка особых точек удаляются те точки, которые либо имеют низкий контраст относительно соседних точек, либо сосредоточены на границах объектов. Для каждой точки рассматривается несколько специальных функций, по значениям которых принимается решение об отбрасывании точки.
4. Ориентация особых точек. Для каждой ключевой точки вычисляется особое значение: направление ключевой точки. Это необходимо для обеспечения инвариантности алгоритма по отношению к вращению объекта. Направление ключевой точки - это угол от интервала. Точка может иметь несколько направлений. Для расчета направления берется несколько ближайших точек, и вычисляются их наклоны.
5. Построение дескрипторов. В методе SIFT дескриптор представляет собой вектор. Как и направление ключевой точки, дескриптор рассчитывается по шкале Гаусса, ближайшей к ключевой точке, и по градиентам в окне ключевой точки. Перед вычислением дескриптора это окно поворачивается на угол направления ключевой точки для достижения инвариантности поворота.
6. Хранение и обработка дескриптора. Поскольку дескриптор представляет собой большой массив и для изображения формируется несколько сотен или тысяч дескрипторов, для хранения и обработки дескрипторов необходимы специальные алгоритмы и структуры данных. Часто используются такие структуры данных, как K-дерево, R*-дерево, SR-дерево.

В данном методе есть как свои плюсы, так и недостатки. К достоинствам данного метода можно отнести инвариантность относительно следующих аффинных преобразований: масштабирование, перемещение изображения объекта на сцене, вращение объекта или камеры. А к недостаткам можно отнести то, что метод обладает большой вычислительной сложностью (обработка изображений размером 1440х900 не может быть выполнена в реальном времени на обычном ПК); часть ключевых точек и их дескрипторы будет удалена в результате фильтрации, что может сказаться на дальнейшем решении задачи сопоставления изображений; метод работает некорректно при кардинально различных условиях освещения (день и ночь), а также когда изображение имеет фрактальную или себе подобную структуру (кирпичная стена).