RANSAC

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

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

Пример

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

• Line with outliers.svg

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

• Fitted line.svg

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

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

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

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

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

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

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

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

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

Оценка исходных данныx

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

<math>

1 - p = (1 - q)^k </math>

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

<math> k = \frac{\log(1 - p)}{\log(1 - q)} </math>

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

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

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

Применение

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

Ссылки

• Martin A. Fischler and Robert C. Bolles (June 1981). «Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography». Comm. Of the ACM 24: 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 (1997). «The Development and Comparison of Robust Methods for Estimating the Fundamental Matrix». International Journal of Computer Vision 24: 271–300. DOI:10.1023/A:1007927408552.
• Ondrej Chum (2005), "[cmp.felk.cvut.cz/~chum/Teze/Chum-PhD.pdf Two-View Geometry Estimation by Random Sample and Consensus]", PhD Thesis, <cmp.felk.cvut.cz/~chum/Teze/Chum-PhD.pdf> 
• Антон Конушин, "[cgm.computergraphics.ru/content/view/47 Устойчивые алгоритмы оценки параметров модели на основе случайных выборок]", Компьютерная графика и мультимедиа, <cgm.computergraphics.ru/content/view/47> 

К:Википедия:Изолированные статьи (тип: не указан)

Отрывок, характеризующий RANSAC

– И если бы заехали ко мне – чистое дело марш! – сказал дядюшка, еще бы того лучше; видите, погода мокрая, говорил дядюшка, отдохнули бы, графинечку бы отвезли в дрожках. – Предложение дядюшки было принято, за дрожками послали охотника в Отрадное; а Николай с Наташей и Петей поехали к дядюшке.
Человек пять, больших и малых, дворовых мужчин выбежало на парадное крыльцо встречать барина. Десятки женщин, старых, больших и малых, высунулись с заднего крыльца смотреть на подъезжавших охотников. Присутствие Наташи, женщины, барыни верхом, довело любопытство дворовых дядюшки до тех пределов, что многие, не стесняясь ее присутствием, подходили к ней, заглядывали ей в глаза и при ней делали о ней свои замечания, как о показываемом чуде, которое не человек, и не может слышать и понимать, что говорят о нем.
– Аринка, глянь ка, на бочькю сидит! Сама сидит, а подол болтается… Вишь рожок!
– Батюшки светы, ножик то…
– Вишь татарка!
– Как же ты не перекувыркнулась то? – говорила самая смелая, прямо уж обращаясь к Наташе.
Дядюшка слез с лошади у крыльца своего деревянного заросшего садом домика и оглянув своих домочадцев, крикнул повелительно, чтобы лишние отошли и чтобы было сделано всё нужное для приема гостей и охоты.
Всё разбежалось. Дядюшка снял Наташу с лошади и за руку провел ее по шатким досчатым ступеням крыльца. В доме, не отштукатуренном, с бревенчатыми стенами, было не очень чисто, – не видно было, чтобы цель живших людей состояла в том, чтобы не было пятен, но не было заметно запущенности.
В сенях пахло свежими яблоками, и висели волчьи и лисьи шкуры. Через переднюю дядюшка провел своих гостей в маленькую залу с складным столом и красными стульями, потом в гостиную с березовым круглым столом и диваном, потом в кабинет с оборванным диваном, истасканным ковром и с портретами Суворова, отца и матери хозяина и его самого в военном мундире. В кабинете слышался сильный запах табаку и собак. В кабинете дядюшка попросил гостей сесть и расположиться как дома, а сам вышел. Ругай с невычистившейся спиной вошел в кабинет и лег на диван, обчищая себя языком и зубами. Из кабинета шел коридор, в котором виднелись ширмы с прорванными занавесками. Из за ширм слышался женский смех и шопот. Наташа, Николай и Петя разделись и сели на диван. Петя облокотился на руку и тотчас же заснул; Наташа и Николай сидели молча. Лица их горели, они были очень голодны и очень веселы. Они поглядели друг на друга (после охоты, в комнате, Николай уже не считал нужным выказывать свое мужское превосходство перед своей сестрой); Наташа подмигнула брату и оба удерживались недолго и звонко расхохотались, не успев еще придумать предлога для своего смеха.
Немного погодя, дядюшка вошел в казакине, синих панталонах и маленьких сапогах. И Наташа почувствовала, что этот самый костюм, в котором она с удивлением и насмешкой видала дядюшку в Отрадном – был настоящий костюм, который был ничем не хуже сюртуков и фраков. Дядюшка был тоже весел; он не только не обиделся смеху брата и сестры (ему в голову не могло притти, чтобы могли смеяться над его жизнию), а сам присоединился к их беспричинному смеху.
– Вот так графиня молодая – чистое дело марш – другой такой не видывал! – сказал он, подавая одну трубку с длинным чубуком Ростову, а другой короткий, обрезанный чубук закладывая привычным жестом между трех пальцев.
– День отъездила, хоть мужчине в пору и как ни в чем не бывало!
Скоро после дядюшки отворила дверь, по звуку ног очевидно босая девка, и в дверь с большим уставленным подносом в руках вошла толстая, румяная, красивая женщина лет 40, с двойным подбородком, и полными, румяными губами. Она, с гостеприимной представительностью и привлекательностью в глазах и каждом движеньи, оглянула гостей и с ласковой улыбкой почтительно поклонилась им. Несмотря на толщину больше чем обыкновенную, заставлявшую ее выставлять вперед грудь и живот и назад держать голову, женщина эта (экономка дядюшки) ступала чрезвычайно легко. Она подошла к столу, поставила поднос и ловко своими белыми, пухлыми руками сняла и расставила по столу бутылки, закуски и угощенья. Окончив это она отошла и с улыбкой на лице стала у двери. – «Вот она и я! Теперь понимаешь дядюшку?» сказало Ростову ее появление. Как не понимать: не только Ростов, но и Наташа поняла дядюшку и значение нахмуренных бровей, и счастливой, самодовольной улыбки, которая чуть морщила его губы в то время, как входила Анисья Федоровна. На подносе были травник, наливки, грибки, лепешечки черной муки на юраге, сотовой мед, мед вареный и шипучий, яблоки, орехи сырые и каленые и орехи в меду. Потом принесено было Анисьей Федоровной и варенье на меду и на сахаре, и ветчина, и курица, только что зажаренная.
Всё это было хозяйства, сбора и варенья Анисьи Федоровны. Всё это и пахло и отзывалось и имело вкус Анисьи Федоровны. Всё отзывалось сочностью, чистотой, белизной и приятной улыбкой.
– Покушайте, барышня графинюшка, – приговаривала она, подавая Наташе то то, то другое. Наташа ела все, и ей показалось, что подобных лепешек на юраге, с таким букетом варений, на меду орехов и такой курицы никогда она нигде не видала и не едала. Анисья Федоровна вышла. Ростов с дядюшкой, запивая ужин вишневой наливкой, разговаривали о прошедшей и о будущей охоте, о Ругае и Илагинских собаках. Наташа с блестящими глазами прямо сидела на диване, слушая их. Несколько раз она пыталась разбудить Петю, чтобы дать ему поесть чего нибудь, но он говорил что то непонятное, очевидно не просыпаясь. Наташе так весело было на душе, так хорошо в этой новой для нее обстановке, что она только боялась, что слишком скоро за ней приедут дрожки. После наступившего случайно молчания, как это почти всегда бывает у людей в первый раз принимающих в своем доме своих знакомых, дядюшка сказал, отвечая на мысль, которая была у его гостей:
– Так то вот и доживаю свой век… Умрешь, – чистое дело марш – ничего не останется. Что ж и грешить то!
Лицо дядюшки было очень значительно и даже красиво, когда он говорил это. Ростов невольно вспомнил при этом всё, что он хорошего слыхал от отца и соседей о дядюшке. Дядюшка во всем околотке губернии имел репутацию благороднейшего и бескорыстнейшего чудака. Его призывали судить семейные дела, его делали душеприказчиком, ему поверяли тайны, его выбирали в судьи и другие должности, но от общественной службы он упорно отказывался, осень и весну проводя в полях на своем кауром мерине, зиму сидя дома, летом лежа в своем заросшем саду.