Алгоритм SIFT

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

История создания

До появления SIFT методы поиска и сопоставления точек на изображениях (например, детектор углов Харриса) были чувствительны к изменениям масштаба и поворота. Дэвид Лоу, работавший в Университете Британской Колумбии, поставил задачу создать дескриптор, который оставался бы инвариантным к аффинным преобразованиям и частично — к изменениям освещения. Первая версия алгоритма была представлена в 1999 году на Международной конференции по компьютерному зрению (ICCV). В 2004 году вышла расширенная статья в журнале International Journal of Computer Vision, где были детализированы этапы построения дескриптора и приведены результаты экспериментов, показавшие высокую надёжность SIFT по сравнению с аналогами.

Изначально алгоритм был запатентован Университетом Британской Колумбии, что ограничивало его использование в коммерческих продуктах. В 2020 году срок действия патента истёк, и SIFT стал общедоступным для любых целей.

Принцип работы

Алгоритм SIFT состоит из четырёх основных этапов: обнаружение экстремумов в масштабном пространстве, локализация ключевых точек, назначение ориентации и построение дескриптора.

Обнаружение экстремумов в масштабном пространстве

На первом этапе строится пирамида разностей гауссианов (DoG — Difference of Gaussians). Для этого исходное изображение последовательно размывается гауссовым фильтром с увеличивающимся коэффициентом σ, образуя октавы. Разность между соседними размытыми изображениями даёт карту DoG, которая аппроксимирует лапласиан гауссиана. Точки, в которых значение DoG является локальным максимумом или минимумом по сравнению с 26 соседями (8 в текущем масштабе и 9 в соседних масштабах), считаются кандидатами в ключевые точки. Этот подход обеспечивает инвариантность к масштабу.

Локализация ключевых точек

Для каждого кандидата уточняется его положение и масштаб с помощью интерполяции по трёхмерной квадратичной функции. Отбрасываются точки с низким контрастом (значение DoG меньше порога) и точки, расположенные вдоль рёбер (высокая кривизна в одном направлении и низкая в перпендикулярном), так как они неустойчивы к шуму. Для отбраковки рёберных точек используется отношение собственных значений матрицы Гессе — если оно превышает порог (обычно 10), точка удаляется.

Назначение ориентации

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

Построение дескриптора

Дескриптор SIFT представляет собой вектор из 128 чисел. Для его построения вокруг ключевой точки выделяется область размером 16×16 пикселей, ориентированная по доминирующему направлению. Эта область делится на 4×4 подобласти. В каждой подобласти строится гистограмма направлений градиентов из 8 бинов. Таким образом, 4×4×8 = 128 значений. Дескриптор нормализуется для достижения инвариантности к изменениям освещения (линейным изменениям контраста и яркости).

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

• Инвариантность: SIFT устойчив к масштабированию, повороту, частично к аффинным искажениям, изменению яркости и контраста, а также к шуму.
• Уникальность: 128-мерный дескриптор обеспечивает высокую различимость ключевых точек, что позволяет надёжно сопоставлять их даже на изображениях с большим количеством повторяющихся текстур.
• Количество точек: на типичном изображении размером 640×480 пикселей алгоритм находит от нескольких сотен до нескольких тысяч ключевых точек.
• Вычислительная сложность: SIFT является ресурсоёмким алгоритмом, требующим значительных вычислительных мощностей, особенно на этапе построения пирамиды DoG и дескрипторов. Время обработки одного кадра на процессоре общего назначения может составлять от 0,1 до 1 секунды в зависимости от размера изображения и настроек.

Применение

Алгоритм SIFT широко используется в различных областях компьютерного зрения:

• Построение панорам: сопоставление ключевых точек на перекрывающихся снимках позволяет автоматически сшивать их в единое изображение.
• Распознавание объектов: SIFT применяется для поиска заданных объектов на изображениях, например, в системах дополненной реальности или для идентификации продуктов.
• Трёхмерная реконструкция: по парам изображений, снятых с разных ракурсов, SIFT находит соответствия, которые затем используются для вычисления трёхмерных координат точек.
• Отслеживание движения: в видеопотоке ключевые точки позволяют отслеживать перемещение объектов.
• Робототехника: навигация и локализация роботов на основе визуальных данных, в том числе в задачах SLAM (одновременная локализация и построение карты).
• Биометрия: распознавание отпечатков пальцев, радужной оболочки глаза и других биометрических признаков.

Модификации и альтернативы

Из-за высокой вычислительной стоимости SIFT были разработаны более быстрые и компактные алгоритмы, основанные на схожих принципах:

• SURF (Speeded Up Robust Features) — использует интегральные изображения и фильтры Хаара для ускорения обнаружения и описания точек. SURF работает в несколько раз быстрее SIFT, но несколько уступает в устойчивости к аффинным искажениям.
• ORB (Oriented FAST and Rotated BRIEF) — комбинация детектора FAST и дескриптора BRIEF, дополненная ориентацией. ORB значительно быстрее SIFT и SURF, но менее устойчив к масштабу и повороту.
• BRISK (Binary Robust Invariant Scalable Keypoints) — бинарный дескриптор, инвариантный к масштабу и повороту, работающий быстрее SIFT.
• AKAZE (Accelerated KAZE) — использует нелинейное масштабное пространство, что позволяет лучше сохранять границы объектов и обеспечивает высокую скорость.

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

Критика и ограничения

• Вычислительная нагрузка: SIFT не подходит для систем реального времени на мобильных устройствах или встраиваемых системах без аппаратного ускорения.
• Чувствительность к аффинным искажениям: при сильных перспективных искажениях (например, при съёмке под большим углом) надёжность сопоставления снижается.
• Патентные ограничения: до 2020 года использование SIFT в коммерческих продуктах было затруднено из-за патента. После истечения срока действия патента эта проблема исчезла.
• Необходимость настройки: для разных типов изображений (например, медицинских или спутниковых) может потребоваться подбор пороговых значений, что усложняет автоматическое применение.

Интересные факты

• Алгоритм SIFT был вдохновлён работой нейронов зрительной коры мозга, которые реагируют на определённые ориентации и масштабы.
• Дэвид Лоу получил за разработку SIFT премию ACM Prize in Computing в 2015 году.
• В 2012 году алгоритм был использован в системе распознавания изображений Google Goggles, которая позволяла искать объекты по фотографии.
• SIFT остаётся одним из наиболее цитируемых алгоритмов в области компьютерного зрения — его основная статья 2004 года имеет более 60 000 цитирований.

Источники

• Lowe, D. G. (2004). Distinctive Image Features from Scale-Invariant Keypoints. International Journal of Computer Vision, 60(2), 91–110.
• Lowe, D. G. (1999). Object recognition from local scale-invariant features. Proceedings of the International Conference on Computer Vision, 1150–1157.
• Szeliski, R. (2010). Computer Vision: Algorithms and Applications. Springer.
• Tuytelaars, T., & Mikolajczyk, K. (2008). Local Invariant Feature Detectors: A Survey. Foundations and Trends in Computer Graphics and Vision, 3(3), 177–280.