Признаки: SIFT, SURF, ORB

2010 год. Microsoft запускает Kinect - первый массовый depth-сенсор. За 60 дней продаётся 8 миллионов устройств. Внутри - ORB-features, работающие в real-time: 30 кадров в секунду, без GPU, распознавая скелет человека за 200 миллисекунд. Классический алгоритм 2011 года сделал motion capture доступным каждому.

• **Google Photos / Apple Photos** - автоматическая группировка фотографий одних и тех же мест и объектов через feature matching
• **Visual SLAM (роботы, AR)** - ORB features позволяют роботу строить карту помещения и одновременно определять своё положение, 30+ fps без GPU
• **Панорамы** - каждый раз, когда делается панорама на телефоне, алгоритм находит features на перекрывающихся кадрах, вычисляет гомографию и склеивает их в единое изображение

David Lowe и рождение SIFT

В 1999 году Дэвид Лоу из University of British Columbia опубликовал черновик SIFT, а в 2004 - финальную версию с ratio test. Алгоритм решал проблему, которую считали нерешаемой: как найти одну и ту же точку на фотографиях, сделанных с разных расстояний и под разными углами? SIFT стал самой цитируемой работой по computer vision на десятилетие вперёд. В 2020 году патент истёк - алгоритм стал свободным. Сегодня производные SIFT работают в каждом смартфоне при съёмке панорам.

Предварительные знания

• Filtering and Convolution

Что такое feature? Harris и FAST

**Feature (признак)** - это точка на изображении, которую можно надёжно найти повторно. Гладкая стена - плохой feature (все участки одинаковые). Прямая линия - лучше (можно определить позицию перпендикулярно ей). **Угол** - идеальный feature (можно точно определить позицию в обоих направлениях).

**Harris Corner Detector** (1988) формализует эту интуицию. Для каждого пикселя вычисляется матрица автокорреляции M (2x2) по градиентам Sobel. Собственные значения M говорят: оба маленькие - гладкость, одно большое - край, оба больших - **угол**.

**FAST (Features from Accelerated Segment Test)** - альтернатива Harris, оптимизированная для скорости. Вместо матрицы градиентов проверяются 16 пикселей на окружности вокруг кандидата: если 12+ из них ярче или темнее центра на заданный порог - это угол. FAST в 10-20 раз быстрее Harris, поэтому используется в real-time системах.

Проблема Harris и FAST: они находят углы **только в текущем масштабе**. Здание издалека - угол окна занимает 3x3 пикселя. Вблизи - 30x30 пикселей. Harris/FAST на разных масштабах найдут разные точки. Решение - **scale-space**: анализ на нескольких уровнях масштаба (пирамида Гаусса). Именно это делают SIFT и SURF.

На практике: Harris - для учебных задач и калибровки камер (шахматная доска). FAST - для real-time tracking (дроны, AR). SIFT/ORB - для matching между изображениями (панорамы, поиск объектов).

Дескрипторы: SIFT, SURF, ORB

Feature detector находит **где** интересные точки. Но для сопоставления двух изображений нужно ответить: «Эта точка на фото A - та же самая, что эта на фото B?» Для этого каждой точке присваивается **дескриптор** - числовой вектор, описывающий окрестность точки. Похожие окрестности - близкие дескрипторы.

**SIFT (Scale-Invariant Feature Transform)**, 2004, David Lowe - первый полноценный алгоритм с инвариантностью к масштабу и вращению. Для каждого keypoint строится гистограмма ориентированных градиентов (HOG) в окрестности 16x16, разделённой на 4x4 ячейки по 8 направлений. Результат - вектор из **128 чисел** (float32).

**SURF (Speeded-Up Robust Features)**, 2006 - ускоренная версия SIFT. Вместо гистограмм градиентов использует Haar wavelets и integral images. Дескриптор - **64 числа** (вдвое компактнее). В 3-5 раз быстрее SIFT при сопоставимом качестве.

**SIFT и SURF были запатентованы.** Патент SIFT истёк в 2020 году - теперь свободен. SURF всё ещё под патентом в некоторых юрисдикциях. В OpenCV: SIFT доступен в основном модуле (`cv2.SIFT_create()`), SURF - только в `opencv-contrib-python`.

**ORB (Oriented FAST and Rotated BRIEF)**, 2011, OpenCV Labs - бесплатная альтернатива. Использует FAST для детекции + BRIEF для дескрипторов, добавляя ориентацию. Дескриптор - **бинарный вектор 256 бит** (32 байта). Сравнение - через Hamming distance (подсчёт отличающихся бит), что на порядок быстрее евклидова расстояния.

Matching: BFMatcher, FLANN, ratio test

Есть два набора дескрипторов (от двух изображений). Задача **matching** - для каждого дескриптора из набора A найти ближайший из набора B. «Ближайший» - по евклидову расстоянию (для float-дескрипторов SIFT/SURF) или Hamming distance (для бинарных ORB).

**BFMatcher (Brute-Force)** - сравнивает каждый дескриптор A с каждым дескриптором B. Сложность O(N×M). Надёжно, но медленно при тысячах keypoints. **FLANN (Fast Library for Approximate Nearest Neighbors)** - использует KD-деревья или LSH для приблизительного поиска. В 5-10 раз быстрее BF, но может пропустить лучший match.

Проблема: многие matches - ошибочные. Дескриптор может быть одинаково похож на несколько точек (повторяющиеся текстуры, шум). **Ratio test Лоу** (David Lowe, 2004) - лаконичное решение: для каждого дескриптора берём два ближайших соседа. Если лучший match **значительно** ближе второго - хороший match. Если оба примерно на одном расстоянии - ненадёжно, отбрасываем.

Ratio test с порогом **0.75** отсеивает ~90% ложных matches, теряя лишь ~5% правильных. Можно ужесточить до 0.6 (меньше matches, но почти все правильные) или ослабить до 0.8 (больше matches, но больше ошибок). Выбор зависит от задачи: для RANSAC лучше больше matches, для визуализации - точнее.

Гомография и RANSAC

После matching известно: точка (x1, y1) на фото A соответствует точке (x2, y2) на фото B. Набор таких пар позволяет вычислить **геометрическое преобразование** между изображениями. Если оба фото - плоской сцены (или снятые с одной точки), это преобразование - **гомография**.

**Гомография** - матрица 3x3 (H), которая переводит точки из одного изображения в другое через проективное преобразование. Описывает повороты, масштабирование, перспективные искажения. Нужно минимум **4 пары точек** для вычисления (8 степеней свободы, 9-й элемент фиксируется).

Проблема: среди matches всегда есть **outliers** (ложные соответствия). Даже после ratio test ~10-30% matches могут быть неправильными. Один outlier может катастрофически исказить гомографию. Решение - **RANSAC (RANdom SAmple Consensus)**.

**RANSAC** - итеративный алгоритм: 1) Случайно выбрать 4 пары. 2) Вычислить гомографию по ним. 3) Проверить, сколько остальных пар ей соответствуют (inliers). 4) Повторить 100-1000 раз. 5) Взять гомографию с наибольшим числом inliers. Гениальность: outliers **не влияют** на результат, если inliers составляют хотя бы ~30% пар.

Главное применение гомографии - **image stitching** (склейка панорам). Алгоритм: 1) Найти features на обоих фото. 2) Сопоставить (match). 3) Вычислить H через RANSAC. 4) Применить `warpPerspective` - трансформировать одно фото в систему координат другого. 5) Склеить (blending).

OpenCV имеет готовый `cv2.Stitcher`: `stitcher = cv2.Stitcher_create(); status, panorama = stitcher.stitch([img1, img2, img3])`. Он автоматически делает feature detection, matching, homography, blending и exposure compensation. Но понимание каждого шага критически важно для отладки, когда `Stitcher` не справляется.

Ключевые идеи

• **Feature** = точка, которую можно надёжно найти повторно. Углы - лучшие features. Harris находит углы по матрице градиентов, FAST - по окружности пикселей (быстрее)
• **Дескриптор** - числовой «отпечаток» окрестности keypoint. SIFT (128 float, точный, медленный) -> ORB (256 bit, быстрый, бесплатный). Миллион фото Эйфелевой башни? Для каждого угла на каждом фото строится дескриптор - и похожие дескрипторы находят друг друга
• **Ratio test Лоу** отсеивает ~90% ложных matches, оставляя надёжные. Порог 0.75 - золотой стандарт
• **Гомография + RANSAC** - из matches вычисляется геометрическое преобразование, устойчивое к outliers. Применение: панорамы, AR, стабилизация видео

Связанные темы

Feature detection - мост между низкоуровневой обработкой и высокоуровневым пониманием:

• Фильтрация и свёртка — SIFT использует Gaussian blur для scale-space, Sobel для градиентов. Harris corner detector - это свёртка ядрами Sobel + анализ собственных значений
• Цифровое изображение: пиксели и цвет — Feature detection работает на grayscale-канале. Понимание shape (H, W), координат (y, x) и конвертации cv2.cvtColor - необходимые предпосылки

Вопросы для размышления

• Ratio test работает, потому что «правильная» точка-match должна быть значительно ближе любой другой. В каких ситуациях это предположение нарушается? Подсказка: повторяющиеся паттерны (окна здания, клавиатура).
• RANSAC случайно выбирает 4 точки на каждой итерации. Если 50% matches - outliers, какова вероятность, что все 4 случайные точки - inliers? Сколько итераций нужно для 99% уверенности?
• Гомография предполагает плоскую сцену (или вращение камеры). Что произойдёт при склейке панорамы улицы с близкими объектами (машины, деревья) и далёкими (здания)?

Связанные уроки

• cv-02 — SIFT использует Gaussian blur и градиенты Sobel из свёрток
• cv-01 — Feature detection работает на grayscale-канале, нужно знать shape и cvtColor
• cv-04 — Object detection и трекинг строятся на feature matching
• ml-01 — Дескрипторы как feature vectors для классификаторов
• alg-01 — RANSAC итеративен: понимание big-O помогает выбрать число итераций
• geo-01 — Гомография - это проективное преобразование плоскости в плоскость
• la-15-svd