RANSAC

RANSAC (от англ. Random Sample Consensus — «согласие на основе случайной выборки») — это итеративный недетерминированный алгоритм, предназначенный для оценки параметров математической модели по набору данных, содержащему значительную долю выбросов (аномальных значений). В отличие от классических методов, таких как метод наименьших квадратов, которые чувствительны к каждому наблюдению, RANSAC способен игнорировать выбросы и строить модель, опираясь только на «внутренние» (согласующиеся с моделью) точки данных. Алгоритм был предложен в 1981 году Фишлером и Боллесом (Fischler & Bolles) и с тех пор является одним из стандартных инструментов в компьютерном зрении, робототехнике и обработке данных.

История и происхождение

Алгоритм RANSAC был впервые опубликован в 1981 году в статье Мартина Фишлера (Martin A. Fischler) и Роберта Боллеса (Robert C. Bolles) в журнале Communications of the ACM. Работа была выполнена в рамках исследований в SRI International (Стэнфордский исследовательский институт). Основной проблемой, которую решал алгоритм, была задача автоматического определения соответствий между двумя изображениями (например, для стереозрения или построения карт местности). Существовавшие на тот момент методы, основанные на наименьших квадратах, давали сбой при наличии даже небольшого числа ошибочных соответствий (выбросов). RANSAC предложил принципиально иной подход: вместо того чтобы пытаться учесть все данные, он многократно строит гипотезы на минимально возможных случайных подвыборках и проверяет, сколько точек поддерживают каждую гипотезу.

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

Работа RANSAC основана на вероятностном подходе. Алгоритм выполняет следующие шаги итеративно:

1. Выборка. Из всего набора данных случайным образом выбирается минимальное количество точек, необходимое для однозначного определения параметров модели. Например, для построения прямой линии достаточно двух точек, для плоскости — трёх, для гомографии (матрицы преобразования между двумя плоскостями) — четырёх точек.

1. Построение гипотезы. На основе выбранных точек вычисляется кандидатная модель (гипотеза).

1. Проверка. Для каждой точки из исходного набора данных вычисляется расстояние до построенной модели. Точка считается «внутренней» (inlier), если это расстояние меньше заранее заданного порога (порога согласия). Все точки, расстояние до которых превышает порог, считаются «выбросами» (outliers).

1. Оценка. Фиксируется количество «внутренних» точек, поддерживающих данную гипотезу. Если это количество превышает текущий максимум, гипотеза запоминается как лучшая.

1. Повторение. Шаги 1–4 повторяются заданное число раз (или до достижения определённого уровня уверенности). После завершения всех итераций алгоритм возвращает модель, набравшую наибольшее количество «внутренних» точек.

1. Финальная оптимизация (опционально). На заключительном этапе модель может быть пересчитана заново, но уже с использованием всех найденных «внутренних» точек (например, методом наименьших квадратов), что повышает точность.

Ключевые параметры

Эффективность RANSAC критически зависит от нескольких параметров, которые задаются пользователем:

• Порог согласия (t) — максимальное расстояние, при котором точка считается «внутренней». Слишком маленькое значение приведёт к потере большого числа правильных точек, слишком большое — к включению в модель выбросов.
• Число итераций (k) — количество случайных выборок. Чем выше доля выбросов в данных, тем больше итераций требуется для нахождения корректной модели. Теоретически число итераций можно рассчитать, исходя из требуемой вероятности успеха (обычно 0,99) и доли «внутренних» точек.
• Минимальное количество точек (n) — определяется типом модели.

Виды и модификации

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

M-оценщик RANSAC (MSAC)

Модификация, в которой вместо простого подсчёта числа «внутренних» точек используется взвешенная сумма. Точки, попадающие в порог, получают вес, пропорциональный их расстоянию до модели, а выбросы — фиксированный штраф. Это позволяет более точно выбирать модель, особенно когда порог задан неидеально.

MLESAC (Maximum Likelihood Estimation SAC)

Вероятностная модификация, где оценка модели производится на основе максимума правдоподобия. MLESAC моделирует распределение ошибок как смесь распределения «внутренних» точек (обычно нормального) и равномерного распределения выбросов. Это делает алгоритм более устойчивым к выбору порога.

PROSAC (Progressive SAC)

Алгоритм, который использует априорную информацию о качестве точек. Если точки можно отсортировать по степени «надёжности» (например, по качеству совпадения дескрипторов), PROSAC начинает выборку с наиболее надёжных точек, что значительно ускоряет сходимость по сравнению с полностью случайной выборкой.

R-RANSAC (Randomized RANSAC)

Ускоренная версия, в которой проверка гипотезы проводится не по всем точкам, а сначала по случайной подвыборке. Если эта подвыборка не подтверждает модель, гипотеза отбрасывается без полной проверки. Это позволяет экономить вычислительные ресурсы.

Применение

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

Компьютерное зрение

• Стереозрение и построение карт глубины. Алгоритм используется для отбраковки ошибочных соответствий между пикселями на двух изображениях (disparity map) и оценки фундаментальной или существенной матрицы, описывающей геометрию двух камер.
• Сшивка панорам (Image Stitching). При поиске совпадающих точек на соседних снимках (например, с помощью SIFT или ORB) RANSAC применяется для вычисления гомографии — матрицы преобразования, которая «склеивает» изображения, игнорируя ложные совпадения.
• Отслеживание объектов (Object Tracking). Используется для оценки движения камеры или объекта на основе набора характерных точек.
• 3D-реконструкция. В структуре из движения (Structure from Motion, SfM) RANSAC необходим для оценки положения камер и построения трёхмерной модели сцены.

Робототехника

• Локализация и картографирование (SLAM). Алгоритм применяется для сопоставления данных с лидара или камеры с существующей картой, отбрасывая выбросы, вызванные движущимися объектами или шумом сенсора.

Обработка данных и статистика

• Анализ регрессии. В задачах, где данные содержат грубые ошибки (например, в финансовых рядах или данных с датчиков), RANSAC позволяет построить устойчивую регрессионную модель, нечувствительную к выбросам.
• Обработка сигналов. Используется для обнаружения и оценки параметров сигналов на фоне сильных помех.

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

Несмотря на свою популярность, RANSAC имеет ряд ограничений:

• Неопределённость результата. Алгоритм не гарантирует нахождения оптимального решения за конечное число итераций. Результат может быть субоптимальным, особенно при малом числе итераций или высокой доле выбросов.
• Чувствительность к порогу. Выбор порога согласия (t) является критическим и часто требует эвристического подбора. Неправильный порог может привести к полной неработоспособности алгоритма.
• Вычислительная сложность. При очень высокой доле выбросов (более 80–90%) число необходимых итераций резко возрастает, что делает алгоритм медленным.
• Неспособность обрабатывать множественные модели. Классический RANSAC предполагает, что в данных присутствует только одна модель. Для обнаружения нескольких моделей (например, нескольких линий на одном графике) требуются расширения, такие как последовательное применение RANSAC или алгоритмы на основе кластеризации.

Источники

1. Fischler, M. A., & Bolles, R. C. (1981). Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography. Communications of the ACM, 24(6), 381–395.
2. Hartley, R., & Zisserman, A. (2003). Multiple View Geometry in Computer Vision (2nd ed.). Cambridge University Press.
3. Torr, P. H. S., & Zisserman, A. (2000). MLESAC: A new robust estimator with application to estimating image geometry. Computer Vision and Image Understanding, 78(1), 138–156.
4. Chum, O., & Matas, J. (2005). Matching with PROSAC – progressive sample consensus. Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05), 1, 220–226.