RANSAC

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

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

ПримерПравить

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

•  

  Набор данных, в который надо вписать прямую. выбросы присутствуют в большом количестве.

•  

  Предложенная алгоритмом RANSAC прямая. выбросы не влияют на результат.

Описание алгоритмаПравить

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

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

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

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

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

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

1. Параметры $\mathrm{\theta <!--\; \theta \; -->}$$\theta$  модели $P$$P$ 
2. Точки исходных данных, помеченные инлаерами или выбросами.

Оценка исходных данныxПравить

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

$1-<!--\; -\; -->p=(1-<!--\; -\; -->q{)}^k$$1-p=(1-q)^{k}$ 

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

$k=\frac{\log <!--\; \; -->(1-<!--\; -\; -->p)}{\log <!--\; \; -->(1-<!--\; -\; -->q)}$$k={\frac {\log(1-p)}{\log(1-q)}}$ 

Преимущества и недостатки алгоритма RANSACПравить

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

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

ПрименениеПравить

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

СсылкиПравить

• Martin A. Fischler and Robert C. Bolles. Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography (англ.) // Comm. Of the ACM : journal. — 1981. — June (vol. 24). — P. 381—395. — doi:10.1145/358669.358692.
• David A. Forsyth and Jean Ponce. Computer Vision, a modern approach (неопр.). — Prentice Hall, 2003. — ISBN ISBN 0-13-085198-1.
• Richard Hartley and Andrew Zisserman  (англ.) (рус.. Multiple View Geometry in Computer Vision (англ.). — 2nd. — Cambridge University Press, 2003.
• P.H.S. Torr, and D.W. Murray. The Development and Comparison of Robust Methods for Estimating the Fundamental Matrix (англ.) // International Journal of Computer Vision  (англ.) (рус. : journal. — 1997. — Vol. 24. — P. 271—300. — doi:10.1023/A:1007927408552.
• Ondrej Chum (2005), Two-View Geometry Estimation by Random Sample and Consensus, PhD Thesis, <http://cmp.felk.cvut.cz/~chum/Teze/Chum-PhD.pdf>. Проверено 30 мая 2010.  Архивная копия от 16 августа 2009 на Wayback Machine
• Антон Конушин, Устойчивые алгоритмы оценки параметров модели на основе случайных выборок, Компьютерная графика и мультимедиа, <http://cgm.computergraphics.ru/content/view/47>  Архивная копия от 30 января 2009 на Wayback Machine