A probabilistic analysis of a common RANSAC heuristic

Random Sample Consensus (RANSAC) is an iterative algorithm for robust model parameter estimation from observed data in the presence of outliers. First proposed by Fischler and Bolles back in 1981, it still is a very popular algorithm in the computer vision community. The primary objective of their p...

Full description

Saved in:
Bibliographic Details
Published in:Machine vision and applications 2019-02, Vol.30 (1), p.71-89
Main Authors: Sangappa, Hemanth Kumar, Ramakrishnan, K. R.
Format: Article
Language:English
Subjects:
Algorithms
Communications Engineering
Computer Science
Computer vision
Data points
Heuristic
Image Processing and Computer Vision
Inliers (landforms)
Iterative algorithms
Iterative methods
Lower bounds
Mathematical models
Monte Carlo simulation
Networks
Original Paper
Outliers (statistics)
Parameter estimation
Parameter robustness
Pattern Recognition
Probabilistic analysis
Vision systems
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Random Sample Consensus (RANSAC) is an iterative algorithm for robust model parameter estimation from observed data in the presence of outliers. First proposed by Fischler and Bolles back in 1981, it still is a very popular algorithm in the computer vision community. The primary objective of their paper was to find an effective strategy for excluding outliers from estimation process, but it did not consider the presence of noise among the inliers. A common practice among implementations of RANSAC is to take a few samples extra than the minimum required for estimation problem, but implications of this heuristic are lacking in the literature. In this paper, we present a probabilistic analysis of this common heuristic and explore the possibility of finding an optimal size for the randomly sampled data points per iteration of RANSAC. We also improve upon the lower bound for the number of iterations of RANSAC required to recover the model parameters. On the basis of this analysis, we propose an improvement in the hypothesis step of RANSAC algorithm. Since this step is shared (unchanged) by many of the variants of RANSAC, their performance can also be improved upon. The paper also presents the improvements achieved by incorporating the findings of our analysis in two of the popular variants of RANSAC.
ISSN:0932-8092
1432-1769
DOI:10.1007/s00138-018-0973-4