Scale-Invariant Feature Transform

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

История

Алгоритм SIFT был впервые представлен Дэвидом Лоу в 1999 году на Международной конференции по компьютерному зрению (ICCV). В 2004 году Лоу опубликовал расширенную версию статьи, в которой подробно описал математическую основу и результаты экспериментов. Алгоритм быстро стал одним из самых популярных методов в компьютерном зрении благодаря своей надёжности и устойчивости к различным трансформациям изображений.

В 2004 году Лоу получил патент на SIFT (US 6,711,293 B1), который принадлежал Университету Британской Колумбии. В 2020 году срок действия патента истёк, и алгоритм перешёл в общественное достояние. Это привело к его широкому внедрению в коммерческие и открытые проекты, включая библиотеки OpenCV и VLFeat.

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

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

Обнаружение масштабно-инвариантных ключевых точек

Для обнаружения точек, инвариантных к масштабу, используется разность гауссианов (Difference of Gaussians, DoG). Сначала изображение свёртывается с гауссовыми фильтрами с различными значениями параметра масштаба (σ), создавая набор масштабных пространств. Затем вычисляется разность между соседними масштабными уровнями. Ключевые точки выявляются как локальные экстремумы (максимумы или минимумы) в трёхмерном пространстве (x, y, σ). Для повышения точности используется квадратичная интерполяция, чтобы уточнить положение и масштаб каждой точки.

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

На этом этапе отбрасываются точки с низким контрастом (шумовые) и точки, расположенные вдоль рёбер (нестабильные). Для этого применяется анализ главных кривизн (Hessian matrix). Если отношение главных кривизн превышает пороговое значение, точка удаляется. Это позволяет оставить только устойчивые и информативные ключевые точки.

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

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

Формирование дескриптора

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

Свойства

SIFT обладает рядом ключевых свойств, которые делают его эффективным для практических задач:

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

Применение

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

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

Сравнение с другими методами

SIFT является одним из первых и наиболее известных алгоритмов для обнаружения и описания локальных особенностей. Сравнение с другими методами:

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

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

Несмотря на широкое распространение, SIFT имеет ряд недостатков:

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

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

• Алгоритм SIFT был вдохновлён работой нейронов зрительной коры головного мозга, которые реагируют на определённые ориентации и масштабы стимулов.
• В 2012 году Дэвид Лоу получил премию ACM Prize in Computing за вклад в компьютерное зрение, в том числе за разработку SIFT.
• SIFT используется в системах автоматического распознавания лиц, хотя для этой задачи существуют более специализированные методы (например, DeepFace).

Источники

• Lowe, D. G. (1999). "Object recognition from local scale-invariant features". Proceedings of the International Conference on Computer Vision.
• Lowe, D. G. (2004). "Distinctive image features from scale-invariant keypoints". International Journal of Computer Vision, 60(2), 91–110.
• Mikolajczyk, K., & Schmid, C. (2005). "A performance evaluation of local descriptors". IEEE Transactions on Pattern Analysis and Machine Intelligence, 27(10), 1615–1630.
• OpenCV documentation: "Introduction to SIFT (Scale-Invariant Feature Transform)".
• VLFeat library: "SIFT detector and descriptor".