Я думал, что RANSAC должен случайным образом выбирать подмножество точек для подгонки, так почему же он каждый раз возвращает одну и ту же матрицу преобразования?
RANSAC неоднократно выбирает подмножество точек, затем подбирает модель на их основе, а затем проверяет, сколько точек данных в наборе данных являются посторонними для этой подобранной модели. После того, как это будет сделано много раз, он выбирает подогнанную модель с наибольшим количеством вставок и подгоняет модель под эти вставки.
Для любого заданного набора данных, набора переменных параметров модели и правила для того, что составляет вставку, будет существовать один или несколько (но часто ровно один) максимально возможный набор «вставок». Например, с учетом этого набора данных (изображение из Википедии):
![График, показывающий прямую линию точек с кучей случайных выбросов, разбросанных вокруг](https://i.stack.imgur.com/NAgDj.png)
... тогда с каким-то разумным определением выброса максимально возможный набор выбросов, который может иметь любая линейная модель, выделен синим цветом ниже:
![То же изображение, что и раньше, но с синими вкраплениями, красными выбросами и синей линией, которая лучше всего проходит через них](https://i.stack.imgur.com/MHuhz.png)
Назовем набор синих точек выше - максимально возможный набор вкраплений - I.
Если вы случайно выберете небольшое количество точек (например, две или три) и проведете через них линию наилучшего соответствия, надеюсь, интуитивно очевидно, что вам потребуется всего несколько попыток, пока вы не нажмете итерацию, где:
- все случайно выбранные вами точки взяты из I, и поэтому
- линия наилучшего соответствия через эти точки примерно равна линии наилучшего соответствия на графике выше, и поэтому
- набор вставок, найденный на этой итерации, точно равен I
Начиная с этой итерации, все дальнейшие итерации — это пустая трата времени, которая не может улучшить модель дальше (хотя RANSAC не может узнать об этом, поскольку он волшебным образом не знает, когда находит максимальный набор вставок).
Если у вас есть достаточно большое количество итераций по отношению к размеру вашего набора данных, и достаточно большая часть набора данных является вкладышами, то вы в конечном итоге найдете максимальный набор вкладышей с вероятностью, близкой к 100%, каждый раз, когда вы запустить РАНСАК. Как следствие, RANSAC будет (почти) всегда выводить одну и ту же модель.
И это хорошо! Часто вы требуете, чтобы RANSAC находил абсолютный максимальный набор вставок, и не хотите соглашаться ни на что меньшее. Если вы получаете разные результаты каждый раз при запуске RANSAC в таком сценарии, это признак того, что вы хотите увеличить количество итераций.
(Конечно, в приведенном выше случае мы говорим о попытке провести линию через точки на 2D-плоскости, что не является тем, что делает findHomography
, но принцип тот же; обычно по-прежнему будет один максимальный набор inliers, и в конце концов RANSAC найдет его.)
Как я могу сделать это поведение действительно случайным?
Уменьшите количество итераций (maxIters
), чтобы RANSAC иногда не мог найти максимальный набор вставок.
Но, как правило, для этого нет иной причины, кроме чисто интеллектуального любопытства; в основном вы намеренно говорите RANSAC выводить неполноценную модель.
person
Mark Amery
schedule
31.03.2019