SIFT

SIFT (аббревиатура от англ. Scale-Invariant Feature Transform — масштабно-инвариантное преобразование признаков) — это алгоритм компьютерного зрения, предназначенный для обнаружения и описания локальных особенностей (ключевых точек) на изображениях. Разработанный Дэвидом Лоу в 1999 году и запатентованный в 2004 году, SIFT стал одним из наиболее влиятельных и широко используемых методов для решения задач сопоставления изображений, распознавания объектов, построения панорам и трёхмерной реконструкции. Ключевой особенностью алгоритма является его устойчивость (инвариантность) к изменениям масштаба, повороту, частичным изменениям освещения и небольшим деформациям объекта.

История

Алгоритм SIFT был впервые представлен Дэвидом Лоу в 1999 году в статье «Object Recognition from Local Scale-Invariant Features», опубликованной в трудах Международной конференции по компьютерному зрению (ICCV). В 2004 году Лоу опубликовал расширенную версию работы в журнале International Journal of Computer Vision, где подробно описал математическую основу и экспериментальные результаты. Алгоритм был запатентован Университетом Британской Колумбии в США (патент US6711293B1). В течение длительного времени патентные ограничения сдерживали использование SIFT в коммерческом программном обеспечении с открытым исходным кодом, однако в 2020 году срок действия патента истёк, что привело к более широкому внедрению алгоритма в открытые библиотеки, такие как OpenCV.

Общая схема работы

Алгоритм SIFT состоит из четырёх основных этапов, выполняемых последовательно:

1. Обнаружение экстремумов в масштабном пространстве (Scale-space extrema detection). На этом этапе строится пирамида разностей гауссианов (Difference of Gaussians, DoG) для исходного изображения. Путём последовательного размытия и субдискретизации изображения создаются октавы, представляющие разные масштабы. Ключевые точки (кандидаты) определяются как локальные максимумы или минимумы в трёхмерном пространстве (координаты x, y и масштаб σ) функции DoG. Для отбора стабильных точек используется сравнение с 26 соседями (8 в текущем масштабе и по 9 в соседних).

1. Локализация ключевых точек (Keypoint localization). Кандидаты, полученные на первом этапе, уточняются путём интерполяции для получения субпиксельной точности положения и масштаба. Точки с низкой контрастностью (недостаточно выраженные) и точки, расположенные вдоль краёв (чувствительные к шуму), отбрасываются. Для устранения краевых точек используется анализ кривизны поверхности через матрицу Гессе.

1. Назначение ориентации (Orientation assignment). Для каждой оставшейся ключевой точки вычисляется доминирующее направление на основе градиентов яркости пикселей в её окрестности. Строится гистограмма градиентов (обычно 36 бинов), и пик максимального значения принимается за основную ориентацию. Если существуют другие пики с высотой не менее 80% от максимального, создаются дополнительные ключевые точки с той же позицией и масштабом, но разными ориентациями. Это обеспечивает инвариантность к повороту изображения.

1. Построение дескриптора (Keypoint descriptor). Вокруг ключевой точки с учётом её масштаба и ориентации выделяется область размером 16×16 пикселей. Эта область разбивается на 4×4 субрегиона. Для каждого субрегиона строится гистограмма градиентов по 8 направлениям. В результате получается вектор признаков размерностью 128 (4×4×8). Этот вектор нормализуется для обеспечения инвариантности к изменениям освещения.

Характеристики и свойства

Основные свойства, обеспечивающие популярность SIFT:

• Инвариантность к масштабу: Алгоритм надёжно находит одни и те же точки на изображениях одного объекта, снятых с разного расстояния.
• Инвариантность к повороту: Дескриптор строится относительно доминирующей ориентации, что позволяет сопоставлять точки при произвольном вращении изображения.
• Устойчивость к изменениям освещения: Нормализация дескриптора и использование градиентов, а не абсолютных значений яркости, снижает чувствительность к перепадам освещённости.
• Устойчивость к аффинным искажениям и шуму: Алгоритм сохраняет работоспособность при небольших изменениях точки съёмки и наличии аддитивного шума.
• Высокая различительная способность: 128-мерный дескриптор позволяет однозначно идентифицировать большое количество ключевых точек даже на сложных сценах.

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

Применение

SIFT нашёл применение в широком спектре задач компьютерного зрения:

• Распознавание объектов (Object recognition): Поиск заданного объекта на изображении или в видеопотоке путём сопоставления его ключевых точек с точками на сцене.
• Построение панорамных изображений (Image stitching): Сопоставление перекрывающихся областей нескольких фотографий для их бесшовного объединения.
• Трёхмерная реконструкция (3D reconstruction): Определение соответствий между точками на изображениях с разных ракурсов для вычисления трёхмерных координат объектов (стереозрение, структура из движения).
• Робототехника и навигация: Визуальная одометрия и одновременная локализация и построение карты (SLAM) для мобильных роботов и беспилотных автомобилей.
• Поиск изображений по содержанию (Content-based image retrieval): Поиск в базе данных изображений, содержащих определённые объекты или сцены.
• Слежение за объектами (Object tracking): Отслеживание движения объекта в видеопоследовательности на основе его ключевых точек.

Варианты и развитие

На основе SIFT были разработаны модификации и альтернативные алгоритмы, направленные на повышение скорости или адаптацию к специфическим условиям:

• PCA-SIFT: Использует метод главных компонент (PCA) для уменьшения размерности дескриптора со 128 до 36, что ускоряет сопоставление.
• GLOH (Gradient Location and Orientation Histogram): Альтернативный дескриптор, использующий логарифмически-полярную сетку вместо прямоугольной, показавший более высокую различительную способность.
• SURF (Speeded Up Robust Features): Ускоренная версия, использующая интегральные изображения и приближения фильтров Гессе. SURF быстрее SIFT, но несколько менее устойчив к изменениям масштаба и поворота.
• A-SIFT (Affine-SIFT): Модификация, обеспечивающая полную инвариантность к аффинным преобразованиям (изменение ракурса до 60 градусов).
• RootSIFT: Вариант, в котором дескриптор SIFT подвергается дополнительной обработке (извлечение квадратного корня из нормализованных значений), что улучшает результаты при использовании евклидова расстояния.

Критика

Основной критике подвергается высокая вычислительная сложность SIFT, делающая его непригодным для задач, требующих обработки в реальном времени на маломощных устройствах. Также отмечается, что алгоритм генерирует большое количество ключевых точек, многие из которых могут быть нестабильными или неинформативными. В условиях сильных аффинных искажений (например, при съёмке под очень острым углом) эффективность SIFT снижается. Патентная защита алгоритма на протяжении многих лет ограничивала его использование в открытых проектах, что стимулировало развитие альтернатив, таких как SURF и ORB (Oriented FAST and Rotated BRIEF).

Источники

1. Lowe, D. G. (1999). Object recognition from local scale-invariant features. Proceedings of the Seventh IEEE International Conference on Computer Vision, 2, 1150-1157.
2. Lowe, D. G. (2004). Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision, 60(2), 91-110.
3. Szeliski, R. (2010). Computer Vision: Algorithms and Applications. Springer.
4. Bay, H., Tuytelaars, T., & Van Gool, L. (2006). SURF: Speeded Up Robust Features. Computer Vision – ECCV 2006, 404-417.
5. Mikolajczyk, K., & Schmid, C. (2005). A performance evaluation of local descriptors. IEEE Transactions on Pattern Analysis and Machine Intelligence, 27(10), 1615-1630.