RANSAC правильно: как оценивать качество моделей без пользовательских параметров
RANSAC, один из самых распространённых алгоритмов удаления выбросов в компьютерном зрении. Его суть: предложить много вариантов моделей и выбрать лучший. Но как выбрать лучший? Традиционные варианты RANSAC (а также MSAC, GaU и MAGSAC) подсчитывают количество «хороших» точек или суммируют оценки для каждой точки. Проблема: у всех этих методов есть параметр, который зависит от шума в данных (так называемая inlier scale), и его надо угадать. Если угадал неверно, оценка портится.
Авторы работы нашли элегантное решение: вместо угадывания масштаба шума, они его вычисляют математически. Они переделали порядок вычислений, сначала маргинализируют масштаб аналитически в замкнутом виде (используя сопряжённое апостериорное распределение Inverse-Gamma), а затем оптимизируют по разбиениям точек на инлаеры и аутлаеры. В одной формуле объединили как непараметрический (Jeffreys), так и параметрический подходы, так что алгоритм автоматически подстраивается под количество доступных данных.
Тестирование на бенчмарке из почти 70 тысяч пар изображений показало, что новый RANSAC-скор превосходит всё, что было до этого. Он не чувствителен к неправильной калибровке порога (где другие методы падают), достигает почти оптимальной точности уже на двух пробных парах (в то время как другим нужно порядка 100 раз больше), и хорошо регуляризуется по мере роста объёма валидационных данных.
Ключевые факты
- Новая формула RANSAC-скора не требует пользовательского параметра масштаба шума, вычисляет его аналитически в закрытом виде
- Один алгоритм работает и на богатых данных (Jeffreys prior), и на скудных (empirical-Bayes), без изменения кода
- На бенчмарке 70 000 пар фото новый скор обошёл MSAC, GaU, MAGSAC по всем метрикам
- Метод устойчив к неправильной калибровке пороговых значений, где классический RANSAC падает
- Вычислительная сложность O(N log N) за счёт алгоритма сортировки и прохода
Почему это важно
RANSAC, это базовый алгоритм в компьютерном зрении, используется везде, где нужно оценить геометрическую модель при наличии выбросов: калибровка камер, сопоставление изображений, 3D-реконструкция. До сих пор главный недостаток, нужно вручную выбирать параметр, который зависит от шума. Новый подход убирает эту боль: алгоритм становится более автономным и надёжным.
Кому это важно
Разработчикам систем компьютерного зрения (мобильные приложения, робототехника, дроны, автономные автомобили), исследователям в области SLAM и 3D-реконструкции, компаниям, которые используют геометрические методы для обработки видео и фото.
Как это применить
Авторы предложили замкнутую формулу, которую можно встроить вместо стандартного RANSAC-скора в существующие системы. Алгоритм работает за O(N log N), что позволяет использовать его в real-time приложениях. Мотивация: если у вас есть задача двухракурсной геометрии (two-view estimation), новый скор может просто заменить старый без переделки всей системы.
Можно ли доверять
Статья основана на строгой математике (сопряжённые распределения, байесовский вывод). Тестирование проведено на большом бенчмарке (70 000 пар изображений) с разными pipelines, как инженерных признаков (engineered features), так и тех, что выучены нейросетями (learned features). Результаты показывают преимущество на всех типах данных.
Риски и подводные камни
Новая формула мощнее, но исследование, это статья на arXiv, не production code. Нужна реализация в популярных библиотеках (OpenCV, COLMAP и т. п.) и верификация на реальных задачах. Также важно понять, как метод работает с экстремальными случаями (очень мало данных, очень высокий шум).
«Предложенный RANSAC-скор, первый, в котором масштаб инлаеров действительно отсутствует из формулы.»
— Авторы исследования, arXiv:2606.27385