Перейти к содержанию
Публикация AiManual

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

RANSAC выбирает 4 пары точек, строит матрицу гомографии H, считает инлайеры по порогу ε и отбрасывает выбросы SIFT. Разбираем алгоритм по шагам, настройку парам

Коротко

Что будет в материале

  1. 01

    Зачем фильтровать совпадения SIFT перед построением гомографии

  2. 02

    Как работает RANSAC: пошаговый разбор алгоритма

  3. 03

    Условие эффективности RANSAC: доля выбросов и число итераций

  4. 04

    Параметры RANSAC: число итераций и порог ошибки ε

SIFT находит пары ключевых точек, но часть этих пар ложная, а гомография строится всего по четырём соответствиям, поэтому одна ошибка в выборке способна увести матрицу в сторону. RANSAC решает именно эту задачу: многократно берёт по 4 случайные пары, строит по ним матрицу H, проецирует первое изображение на второе и считает инлайерами те пары, чья ошибка укладывается в порог ε. После заданного числа итераций остаётся модель с наибольшим числом инлайеров, и при необходимости её переобучают на всех найденных инлайерах.

SIFT устойчив к масштабу и повороту, но инвариантность дескриптора не гарантирует корректного сопоставления признаков между снимками (RANSAC, Explained: Consensus Fitting for Image Feature Matching). При заметном числе неверных пар алгоритм просто не выведет корректное преобразование, и нужен отдельный шаг фильтрации уже готового набора соответствий.

RANSAC не ищет признаки и не матчит их. Детектор и дескриптор дают пары, матчер их сопоставляет, а RANSAC оценивает, какая геометрическая модель объясняет максимум пар. Путаница этих ролей приводит к бессмысленным ожиданиям: сколько итераций ни ставь, новые признаки из воздуха не появятся.

Зачем фильтровать совпадения SIFT перед построением гомографии

Гомография описывает проективное преобразование одной плоскости в другую и требует как минимум четырёх пар соответствующих точек. Четыре пары дают восемь уравнений на восемь степеней свободы матрицы 3×3: масштаб фиксируют, например, делением всех элементов на H[2][2]. Минимум достигается на четырёх парах, и это число определяет всю дальнейшую статистику RANSAC.

Почему SIFT ошибается на похожих областях

Дескриптор SIFT кодирует распределение направлений и величин градиентов в окрестности ключевой точки. Такое описание устойчиво к масштабу и повороту, но два разных места сцены могут дать похожие дескрипторы. Повторяющаяся текстура: кафель в санузле, одинаковые окна фасада, надписи на упаковке, листва, сетка рабица. Визуально области выглядят почти идентично, а соответствуют разным 3D-точкам, и матчер по расстоянию между дескрипторами выбирает такую пару как лучшую.

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

Что происходит с гомографией при наличии выбросов

Если хотя бы одна пара из выбранной четвёрки ложная, система уравнений решается, но решение описывает не ту деформацию. Дальше всё зависит от того, как оценивается финальная матрица. Метод наименьших квадратов по всем парам минимизирует сумму квадратов ошибок и не различает инлайер и выброс: одна пара с ошибкой в десятки пикселей перетягивает результат сильнее, чем десять аккуратных пар с ошибкой в один пиксель.

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

Как работает RANSAC: пошаговый разбор алгоритма

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

  1. Случайно выбрать k точек из n. Для гомографии k = 4.
  2. Построить модель по этой выборке, то есть матрицу H.
  3. Пропустить через модель все n пар и спроецировать первое изображение на второе.
  4. Отметить инлайерами пары с ошибкой в пределах ε, зафиксировать их количество, остальные считать выбросами.
  5. Повторить шаги 1-4 заданное число итераций.
  6. Выбрать модель с наибольшим числом инлайеров.
  7. При необходимости переобучить выбранную модель на всех её инлайерах.

Случайная выборка минимального набора и построение матрицы H

Брать именно четыре пары, а не двадцать, нужно по одной причине: чем меньше выборка, тем выше вероятность, что в неё не попадёт ни один выброс. При доле инлайеров w вероятность чистой четвёрки равна w⁴, и каждые лишние два соответствия в выборке эту вероятность заметно снижают. Выбор случаен на каждой итерации, поэтому один и тот же вызов с другим seed даёт другой набор кандидатов.

Вырожденные выборки возможны и их надо отбрасывать: три точки на одной прямой, четыре точки, лежащие почти на одной прямой, совпадающие точки. Система для H в таких случаях становится плохо обусловленной, и библиотека обычно возвращает пустой результат на итерации или пропускает её. Проверка на вырожденность стоит копейки по сравнению с дальнейшим подсчётом ошибок по всем парам.

Подсчёт инлайеров по порогу ε

Ошибка считается после проекции: насколько точка, перенесённая через H, расходится с фактическим положением парной точки. Пара с ошибкой внутри ε становится инлайером, пара с ошибкой снаружи становится выбросом. Считать нужно по всем n парам, а не только по выбранной четвёрке, иначе модель никогда не получит оценки на данных, которые не участвовали в её построении.

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

Выбор лучшей модели и переобучение на инлайерах

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

У переобучения есть обратная сторона. Если ε слишком велик, в инлайеры попали выбросы, и финальная подгонка закрепит их влияние, сделав результат хуже, чем «сырая» модель по четырём парам. Переобучение помогает только тогда, когда маска инлайеров действительно чистая.

Схема на псевдокоде выглядит так:

best_H, best_mask, best_count = None, None, 0
for i in range(max_iters):
    sample = random_sample(pairs, 4)
    H = fit_homography(sample)
    if H is None:              # вырожденная выборка
        continue
    errors = reprojection_errors(H, pairs)
    mask = errors < eps
    if mask.sum() > best_count:
        best_H, best_mask, best_count = H, mask, mask.sum()
# финальная подгонка по всем инлайерам
H_final = fit_homography(pairs[best_mask])

В OpenCV тот же шаг закрывает одна функция: она возвращает матрицу и маску инлайеров.

import cv2

# pts1, pts2: массивы Nx2 с координатами сопоставленных точек
H, mask = cv2.findHomography(
    pts1, pts2,
    method=cv2.RANSAC,
    ransacReprojThreshold=3.0,
    maxIters=2000,
    confidence=0.995,
)
inliers = int(mask.sum())

Значения в примере выше взяты как рабочий старт, а не как рекомендация: и порог, и число итераций зависят от разрешения снимков и качества матчинга.

Условие эффективности RANSAC: доля выбросов и число итераций

RANSAC работает тем лучше, чем меньше доля выбросов, а с ростом доли выбросов число необходимых итераций резко увеличивается. Это прямое следствие вероятностной схемы: нужна всего одна чистая выборка из четырёх пар, но вероятность её получить падает как w⁴, где w — доля инлайеров. Платой становится вычислительная цена, и она растёт резко.

Почему при большом числе выбросов нужно больше итераций

Вероятность, что все k выбранных пар окажутся инлайерами, равна w^k, где w это доля инлайеров среди всех пар. Для гомографии k = 4, поэтому доля инлайеров входит в четвёртой степени. При w = 0,5 чистая четвёрка выпадает примерно в 6% попыток, при w = 0,3 уже меньше чем в 1%. Классическая оценка числа итераций:

N = log(1 - p) / log(1 - w^k)

Здесь p это желаемая вероятность получить хотя бы одну чистую выборку за N итераций, w доля инлайеров, k размер минимальной выборки. Число необходимых итераций растёт с увеличением размера выборки и с ростом доли выбросов. Арифметика по этой формуле даёт наглядный масштаб: при p = 0,99 и w = 0,5 для выборки из двух точек формула даёт 16 итераций, а для выборки из восьми точек — уже 1177. Для гомографии с k = 4 порядок величины лежит между этими значениями и быстро растёт при снижении доли инлайеров.

Практический смысл: доля инлайеров измеряется по первой же маске, после чего число необходимых итераций можно оценить, а не назначать наугад. Если оценка выходит за разумные пределы по времени, проблема не в RANSAC, а в матчинге.

Когда RANSAC не спасает

Границы применимости стоит знать заранее.

  • Почти все пары ложные. Если доля инлайеров близка к нулю, число необходимых итераций уходит в бесконечность, и любая модель с максимумом «инлайеров» окажется случайной.
  • Вырожденные конфигурации выбранных точек. Три коллинеарные точки или четыре точки на одной прямой дают неустойчивую матрицу, и итерация тратится впустую.
  • Сцена не описывается гомографией. Сильный параллакс, несколько плоскостей на разной глубине, движение объектов в кадре: одна матрица 3×3 физически не может объяснить такие соответствия, и RANSAC честно выберет модель, которая описывает лишь доминирующую часть пар.
  • Неверный порядок величины ε. Слишком маленький порог оставляет модель без инлайеров, слишком большой превращает выбросы в согласные точки.

RANSAC это фильтр, а не замена качественному матчингу. Когда выбросов слишком много, дешевле сначала улучшить сопоставление: ratio test по отношению расстояний к первому и второму соседу, кросс-проверка в обе стороны, ограничение по абсолютной дистанции дескрипторов, отбраковка пар на границах кадра.

Параметры RANSAC: число итераций и порог ошибки ε

Два параметра определяют поведение алгоритма, и настраивать их нужно вместе, а не по отдельности. Порог задаёт, что считается согласием с моделью, число итераций задаёт, сколько попыток есть на поиск чистой модели.

Как выбрать порог ошибки ε

Отталкиваться стоит от геометрии задачи: порог должен соответствовать ожидаемой ошибке локализации ключевой точки в пикселях на конкретном разрешении. Пирамида SIFT сама по себе даёт неточность положения ключа, к ней добавляется ошибка субпиксельной интерполяции и погрешность самого преобразования. На снимке 4000 px по ширине порог в 3 px и порог в 10 px описывают разные множества пар.

Универсального правильного числа нет, зато есть рабочая процедура: прогнать несколько значений ε и посмотреть, как меняются число инлайеров, доля инлайеров и визуальное качество наложения. Хороший порог даёт стабильную долю инлайеров и заметно улучшает перенос после варпа. Если доля инлайеров почти не растёт при увеличении ε, значит, часть пар неверна геометрически, а не «чуть-чуть неточна».

Сколько итераций ставить и что делают maxIters и confidence

Компромисс простой: больше итераций повышают шанс найти хорошую модель, но линейно увеличивают время работы. Ориентир для старта даёт формула выше, посчитанная по фактической доле инлайеров из первой маски. Если оценка требует десятков тысяч итераций, разумнее вернуться к матчингу, чем ждать.

В OpenCV у cv2.findHomography есть параметры maxIters и confidence, которые применяются только с робастными методами, включая RANSAC. maxIters задаёт верхнюю границу числа итераций, а confidence — желаемый уровень доверия к оценённому преобразованию. Оба параметра работают вместе с порогом ransacReprojThreshold: он задаёт максимально допустимую ошибку репроекции, при которой пара считается инлайером, и чем меньше значение, тем строже критерий. Конкретное поведение остановки зависит от реализации, поэтому при нестабильном результате надёжнее оценить нужное число итераций по доле инлайеров и задать его явно, чем полагаться на значения по умолчанию.

Как читать результат: инлайеры, маска и качество наложения

cv2.findHomography возвращает два объекта: матрицу H и маску инлайеров, где каждая пара помечена как согласная или нет. Смотреть нужно на несколько признаков сразу.

  • Абсолютное число и доля инлайеров от общего количества пар. Маска из 15 точек из 2000 говорит о проблемах с матчингом или порогом.
  • Пространственное распределение. Если все инлайеры собрались в одном углу, матрица описывает локальный участок и на остальном кадре даст мусор.
  • Визуальный перенос углов кадра через H: рамка после переноса должна лежать правдоподобно относительно содержимого второго снимка.
  • Стабильность H при повторных запусках с разным seed. Сильные расхождения между запусками означают, что модель держится на небольшом числе точек.

Высокая доля инлайеров при плохом пространственном распределении это повод насторожиться, а не повод радоваться метрике.

Где RANSAC стоит в пайплайнах: панорамы и 3D-реконструкция

Преобразования изображений лежат в основе сборки панорам, реконструкции 3D-сцен и измерений длины объектов или расстояний между ними (источник). RANSAC в этих сценариях занимает скромное, но критичное место: он поставляет чистые соответствия для следующих шагов.

Сборка панорам: от пар к общему преобразованию

Пайплайн панорамы выглядит линейно: детектор и дескриптор (SIFT или ORB), матчинг между перекрывающимися кадрами, оценка H с фильтрацией RANSAC, варп и сшивка. Для каждой пары соседних кадров оценивается своя матрица, затем преобразования согласуются между всеми кадрами, чтобы накопить общую картину.

Слабое место здесь очевидно: ошибка на одном стыке переносится на все последующие кадры и накапливается по цепочке. Плохая матрица на первом стыке проявляется как «поехавшая» линия горизонта в конце панорамы, и лечится это не подбором параметров сшивки, а качеством инлайеров на каждом стыке отдельно.

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

3D-реконструкция по фотографиям и место RANSAC

В реконструкции по фотографиям RANSAC фильтрует соответствия при оценке геометрии между кадрами. В COLMAP пайплайн состоит из двух стадий. Первая — поиск соответствий: извлечение признаков, матчинг и геометрическая верификация, по результатам которой строится граф сцены. Вторая — инкрементальная реконструкция: инициализация, регистрация изображений через PnP, триангуляция, bundle adjustment и фильтрация выбросов. Триангуляция в COLMAP формулируется как рекурсивный RANSAC по элементам треков: выбираются два измерения, триангуляция выполняется через DLT, и модель принимается только при достаточном угле триангуляции.

Роль RANSAC скромная, но без неё пайплайн не поедет: грязные соответствия дают неверную геометрию, а неверная геометрия ломает триангуляцию. При этом сам RANSAC не строит 3D-сцену и не восстанавливает позы камер: он только отбирает пары, согласующиеся с моделью. В реальных пайплайнах рядом с ним работают другие фильтры, включая геометрическую верификацию и проверку по нескольким видам, и в одиночку RANSAC не решает задачу реконструкции.

Типичные ошибки и как их избежать

  • Слишком большой ε. Признак: доля инлайеров подозрительно высокая (near 100%) при явно плохом наложении. Действие: уменьшать порог до момента, когда маска начнёт отражать реальное согласие.
  • Слишком мало итераций. Признак: результат меняется от запуска к запуску при том же входном наборе пар. Действие: оценить нужное число итераций по доле инлайеров или поднять maxIters.
  • RANSAC вместо матчинг-фильтра. Признак: тысячи пар на входе, десятки инлайеров на выходе. Действие: добавить ratio test, кросс-проверку и ограничение по дистанции дескрипторов до вызова RANSAC.
  • Ожидание гомографии на сцене с сильным параллаксом. Признак: инлайеры распределены по кадру, но наложение расходится на объектах переднего плана. Действие: признать ограничение модели и переходить к оценке фундаментальной матрицы или к разбиению сцены на плоскости.
  • Игнорирование вырожденных выборок. Признак: заметные скачки результата при повторных запусках. Действие: явно проверять конфигурацию точек перед подгонкой.
  • Отсутствие визуальной проверки. Признак: метрики в норме, а сшивка разъехалась. Действие: смотреть на карту переноса и на несколько контрольных сцен, а не на одну.

Проверка результата без визуального контроля

Автоматизировать контроль можно тремя метриками: доля инлайеров, средняя ошибка инлайеров и разброс параметров H при повторных запусках с разным seed. Все три легко считаются в скрипте и хорошо ловят деградацию. Граница применимости простая: на новом типе сцен метрики нужно один раз откалибровать глазами, иначе они закрепят неверное представление о норме. Доля инлайеров в 40% на текстурированной сцене и в 40% на симметричном фасаде означают разное качество матчинга, и порог отбраковки для этих случаев должен различаться.

Короткий итог: что запомнить о RANSAC

  • RANSAC фильтрует выбросы SIFT итеративной консенсус-подгонкой: случайная минимальная выборка, модель, подсчёт согласных пар.
  • Для гомографии k = 4, потому что матрица 3×3 имеет восемь степеней свободы, а каждая пара даёт два уравнения.
  • Инлайнеры определяются порогом ε в пикселях ошибки переноса; считается ошибка по всем парам, а не по выбранной четвёрке.
  • Побеждает модель с максимальным числом инлайеров, а переобучение на инлайерах повышает точность только при чистой маске.
  • Число необходимых итераций растёт с размером выборки и с долей выбросов; при малой доле инлайеров оно уходит в десятки тысяч, и тогда правильнее улучшать матчинг.
  • Параметры ε и число итераций подбираются под разрешение и качество матчинга, а результат проверяется по доле инлайеров, их распределению и визуальному наложению.

Если гомография сходится плохо, начните с одного конкретного действия: посчитайте долю инлайеров на текущих параметрах и сравните с результатом после ratio test по матчам. Разница покажет, где лежит проблема, в матчинге или в пороге.

Подписаться на канал