Интернет магазин китайских планшетных компьютеров



Компьютеры - RANSAC - Оценка исходных данныx

16 июня 2011


Оглавление:
1. RANSAC
2. Описание алгоритма
3. Оценка исходных данныx
4. Преимущества и недостатки алгоритма RANSAC
5. Применение



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

1 − p =

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


k = \frac{\log}{\log}


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



Просмотров: 3736


<<< LucasKanade