reestimate-eps-converted-to

Due to its random nature, standard RANSAC is not always able to find the optimal set (all inliers)  even for moderately contaminated sets and it is known to perform badly when the number of inliers is less than 50%. But this algorithm is capable of finding the optimal set (hence it is “almost” deterministic) even when the inlier ratio is under 5%. The proposed algorithm is based on several known methods, which was modified in a unique way and together they produce a result that is quite different from what each method can produce on its own.

The algorithm proves to find the optimal set if there is one model at hand. For outdoor scenarios it might find one of many possible models. Hence it has this limitation, which ordinary RANSAC also has.

The image above shows one of the main contributions which repeats the reestimation to get an even better result. This is usually only done as a last step in RANSAC, but we showed that it can be repeated, but needs to be resampled.

I personally only use this whenever I would otherwise normally have used “normal” RANSAC. It can be slow for very large datasets. But it will find the optimal set, even if it is heavily contaminated with outliers. Most versions of RANSAC cannot handle this.

The paper shows how it can be applied, not only for images but also for computation of finding an optimal plane that cuts through a dataset in a medical application.

  • Optimal RANSAC – Towards a Repeatable Algorithm for Finding the Optimal Set.
    A. Hast, J. Nysjö, A. Marchetti.
    Journal of WSCG, Vol.21, no.1, Journal. pp. 21-30. 2013. pdf
@article{Hast624363,
   author = {Hast, Anders and Nysj{\"o}, Johan},
   institution = {Uppsala University, Division of Visual Information and Interaction},
   institution = {Uppsala University, Computerized Image Analysis and Human-Computer Interaction},
   journal = {Journal of WSCG},
   number = {1},
   pages = {21--30},
   title = {Optimal RANSAC - Towards a Repeatable Algorithm for Finding the Optimal Set},
   volume = {21},
   year = {2013}

 

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s