Transcription of Overview of the RANSAC Algorithm - York University
1 Overview of the RANSAC AlgorithmKonstantinos G. 13, SAmple Consensus( RANSAC ) Algorithm proposed by Fischler andBolles [1] is a general parameter estimation approach designed to cope with a largeproportion of outliers in the input data. Unlike many of the common robust esti-mation techniques such as M-estimators and least-median squares that have beenadopted by the computer vision community from the statistics literature, RANSACwas developed from within the computer vision is a resampling technique that generates candidate solutions by usingthe minimum number observations (data points) required to estimate the underlyingmodel parameters. As pointed out by Fischler and Bolles [1], unlike conventionalsampling techniques that use as much of the data as possible to obtain an initialsolution and then proceed to prune outliers, RANSAC uses the smallest set possibleand proceeds to enlarge this set with consistent data points [1].
2 The basic Algorithm is summarized as follows: Algorithm 1 RANSAC1:Select randomly the minimum number of points required to determine the :Solve for the parameters of the :Determine how many points from the set of all points fit with a predefined toler-ance .4:If the fraction of the number of inliers over the total number points in the setexceeds a predefined threshold , re-estimate the model parameters using all theidentified inliers and :Otherwise, repeat steps 1 through 4 (maximum ofNtimes).The number of iterations,N, is chosen high enough to ensure that the probabilityp(usually set to ) that at least one of the sets of random samples does not includean outlier. Leturepresent the probability that any selected data point is an inlier1andv= 1 uthe probability of observing an of the minimumnumber of points denotedmare required, where1 p= (1 um)N(1)and thus with some manipulation,N=log(1 p)log(1 (1 v)m)(2)For more details on the basic RANSAC formulation, see [1, 2].
3 Extensions ofRANSAC include using aMaximum Likelihoodframework [4] andimportance sam-pling[3].References[1] Fischler and Bolles. Random sample consensus: A paradigm for modelfitting with applications to image analysis and automated of the ACM, 24(6):381 395, 1981.[2] R. Hartley and A. View Geometry in Computer Vision. Uni- versity Press, Cambridge, 2001.[3] P. Torr and C. Davidson. IMPSAC: A synthesis of importance sampling andrandom sample consensus to effect multi-scale image matching for small and widebaselines. InEuropean Conference on Computer Vision, pages 819 833, 2000.[4] P. Torr and A. Zisserman. MLESAC: A new robust estimator with applica-tion to estimating image Vision and Image Understanding,78(1):138 156.
