RANSAC

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

RANSAC — (аббр. RANdom SAmple Consensus) стабильный метод оценки параметров модели на основе случайных выборок. Схема RANSAC устойчива к зашумлённости исходных данных. Метод был предложен в 1981 году Фишлером и Боллесом.

Часто возникает задача обработки данных, в которой необходимо определить параметры модели, которая должна удовлетворять исходным данным. Все исходные данные можно разделить на два типа: хорошие точки, удовлетворяющие модели, «не-выбросы» или «инлаеры» (англ. inlier) и ложные точки, шумы — случайные включения в исходные данные, «выбросы» или «аутлаеры» (англ. outlier).

Пример[править | править вики-текст]

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

Описание алгоритма[править | править вики-текст]

На вход алгоритма поступает:

  1. набор исходных данных X
  2. функция M, позволяющая вычислить параметры \theta модели P по набору данных из n точек
  3. функция оценки E соответствия точек полученной модели
  4. порог t для функции оценки
  5. количество итераций метода k

Весь алгоритм состоит из одного цикла, каждую итерацию которого можно логически разделить на два этапа.

  • Первый этап — выбор точек и подсчёт модели.
    • Из множества исходных точек X случайным образом выбираются n различных точек.
    • На основе выбранных точек вычисляются параметры \theta модели P с помощью функции M, построенную модель принято называть гипотезой.
  • Второй этап — проверка гипотезы.
    • Для каждой точки проверяется её соответствие данной гипотезе с помощью функции оценки E и порога t
    • Каждая точка помечается инлаером или выбросом
    • После проверки всех точек, проверяется, является ли гипотеза лучшей на данный момент, и если является, то она замещает предыдущую лучшую гипотезу.

В конце работы цикла оставляется последняя лучшая гипотеза.

Результатом работы метода являются:

  1. Параметры \theta модели P
  2. Точки исходных данных, помеченные инлаерами или выбросами.

Оценка исходных данныx[править | править вики-текст]

Значение параметра t должно быть определено в зависимости от конкретных требований, зависящих от данных, в большинстве случаев, только после экспериментальных оценок. Количество итераций k может быть определено до выполнения алгоритма методом теоретической оценки. Пусть p — вероятность того, что алгоритм RANSAC на некоторой итерации, выбирая n точек, на основе которых строится модель, возьмёт для расчётов из исходного набора данных только инлаеры. В такой ситуации построенная по данным точкам модель, с большой вероятностью будет достаточно точной. Исходя из этого, мы можем использовать вероятность p для оценки точности работы алгоритма. Пусть w — вероятность выбора одного инлаера из общего числа точек, то есть w= (количество инлаеров)/(общее число точек) В большинстве случаев доля инлаеров w неизвестна до начала выполнения алгоритма, но практически всегда можно дать некоторую грубую оценку. Вероятность независимого выбора n инлаеров из исходных данных, в таком случае равна w^{n}, а вероятность того, что хотя бы одна точка из набора выброс, то есть что будет построена некорректная модель — (1 - w^{n}). Вероятность того, что за k итераций алгоритм ни разу не выберет n инлаеров — (1 - w^{n})^k, такая ситуация означает, что точная модель не будет построена, а вероятноть этого события равна (1-p). Таким образом


1 - p = (1 - w^n)^k

Выразим необходимое нам количество итераций k


k = \frac{\log(1 - p)}{\log(1 - w^n)}


У этой оценки есть один очевидный недостаток: все точки n выбираются независимо, что недопустимо для реальной работы алгоритма. Например, в случае вписывания линии в исходный набор данных (показано на рисунке выше) алгоритм RANSAC выбирает две точки на каждой итерации и вычисляет модель как линию между точками, в этом случае крайне важно, чтобы две точки различны. Исходя из этого, k можно использовать как верхнюю оценку количества итераций метода.

Преимущества и недостатки алгоритма RANSAC[править | править вики-текст]

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

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

Применение[править | править вики-текст]

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

Ссылки[править | править вики-текст]