Scale-Invariant Feature Transform (SIFT)

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

История и основная идея#

Дэвид Лоу из Университета Британской Колумбии представил SIFT в статье «Распознавание объектов по локальным инвариантным к масштабу признакам», опубликованной на ICCV в 1999 году, а полное описание метода дал в статье «Характерные признаки изображений по ключевым точкам, инвариантным к масштабу» в International Journal of Computer Vision в 2004 году. Признаки SIFT инвариантны к масштабу и повороту, а также надежно сопоставляются при значительных аффинных искажениях, изменениях ракурса в 3D, шумах и освещении. Метод был запатентован, срок действия патента истек в 2020 году. В версии 4.4.0 OpenCV перенесла SIFT из репозитория contrib в основную библиотеку.

Размер объекта на фотографии не фиксирован, поэтому детектор должен искать структуры разных размеров. SIFT строит пространство масштабов, многократно применяя размытие по Гауссу с нарастающей силой и уменьшая разрешение изображений в группах, называемых октавами.

Как работает SIFT#

Алгоритм состоит из четырех этапов:

1. Поиск экстремумов в пространстве масштабов: Разности между соседними уровнями размытия (разность гауссиан) приближенно работают как детектор областей. Пиксель становится кандидатом, если он является максимумом или минимумом среди 26 соседей в пространстве и масштабе.
2. Локализация ключевых точек: Координаты кандидатов уточняются до субпиксельной точности. Точки с низким контрастом и точки на границах отбрасываются как нестабильные.
3. Назначение ориентации: Гистограмма локальных направлений градиента вокруг каждой ключевой точки определяет преобладающую ориентацию, относительно которой измеряются все последующие параметры. Это обеспечивает инвариантность к повороту.
4. Построение дескриптора: Окрестность разбивается на сетку 4 x 4, и в каждой ячейке строится гистограмма градиентов с 8 интервалами. В итоге получается 4 x 4 x 8 = 128 значений, которые нормализуются, чтобы уменьшить чувствительность к освещению.

Дескрипторы сопоставляются по евклидову расстоянию. Тест отношения Лоу оставляет совпадение, только если ближайший сосед заметно ближе второго по расстоянию. Поиск k ближайших соседей при k = 2 возвращает оба расстояния.

import cv2
from ultralytics.utils import ASSETS

# Load a sample image in grayscale and a half-size copy
img = cv2.imread(str(ASSETS / "bus.jpg"), cv2.IMREAD_GRAYSCALE)
small = cv2.resize(img, None, fx=0.5, fy=0.5)

# Detect keypoints and compute 128-dimensional descriptors
sift = cv2.SIFT_create()
kp1, des1 = sift.detectAndCompute(img, None)
kp2, des2 = sift.detectAndCompute(small, None)

# Match half-size descriptors to full-size ones, then apply Lowe's ratio test
pairs = cv2.BFMatcher().knnMatch(des2, des1, k=2)
good = [m for m, n in pairs if m.distance < 0.8 * n.distance]
print(f"{len(good)} of {len(kp2)} half-size keypoints matched at full size")

Выведенное число показывает, сколько ключевых точек, найденных на изображении половинного размера, удалось снова обнаружить на изображении полного размера: это и есть инвариантность к масштабу.

Применение#

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

• Сшивание панорам: В методе автоматического сшивания панорам Брауна и Лоу (IJCV, 2007) признаки SIFT сопоставляются между перекрывающимися фотографиями, а для их совмещения вычисляется гомография. Этот этап совмещения называется регистрацией изображений.
• Восстановление 3D-сцены: В проекте Photo Tourism (Снавели, Зейтц и Сзелиски, 2006) признаки SIFT сопоставляются на фотографиях туристических мест, а эпиполярная геометрия используется для восстановления положений камер и разреженной 3D-структуры.
• Локализация робота: В 2001 году Се, Лоу и Литтл использовали ориентиры SIFT для локализации и построения карты мобильным роботом. Этот метод стал предшественником современной визуальной SLAM.
• Распознавание экземпляров: В статье Лоу 2004 года игрушечный поезд и лягушка распознаются в загроможденной, частично перекрытой сцене всего по 3 совпавшим признакам.

В Ultralytics YOLO отслеживании объектов BoT-SORT компенсирует движение камеры между кадрами, а параметр gmc_method: sift в конфигурации трекера включает сопоставление признаков SIFT для этой оценки вместо разреженного оптического потока, используемого по умолчанию.

Сравнение SIFT с родственными методами#

SIFT сопоставляет одни и те же физические точки на разных ракурсах, что подходит для установления соответствий и геометрических задач. Обнаружение объектов, напротив, предсказывает категории и расположение объектов. Сопоставление с шаблоном перемещает фиксированный фрагмент изображения и не работает при изменении масштаба или поворота.

SIFT медленнее ORB — бинарного дескриптора, представленного Рубли и коллегами в 2011 году в качестве альтернативы SIFT и SURF. Кроме того, метод плохо работает на поверхностях без текстуры и при очень сильном изменении ракурса; для распознавания на уровне категорий его в основном заменили обучаемые модели.

В тестах Лоу 2004 года отбрасывание совпадений с отношением расстояний выше 0.8 устранило 90% ложных совпадений, отбросив менее 5% правильных; использовались изображения со случайными изменениями масштаба и поворота, поворотом по глубине на 30 градусов и шумом 2%, сопоставленные с 40,000 ключевыми точками.