RANSAC

Prévia do material em texto

RANdom SAmple Consensus 
RANSAC 
 
 
 
Raul Queiroz Feitosa 
19/03/2013 RANSAC 2 
Motivation 
Problems with parameter estimation: 
 Parameters of a given model y=M(x) are estima-
ted upon a set of correspondences (yi↔xi). 
 In practical situations there is an unknown 
number of mismatched correspondences 
(outliers) . 
 Outliers can severely disturb parameter 
estimation. 
19/03/2013 RANSAC 3 
What is RANSAC ? 
RANSAC is 
 robust, (it works in the presence of outliers), 
 iterative, 
 non-deterministic (it produces a reasonable result only 
with a certain probability, with this probability 
increasing as more iterations are allowed ) 
 method for parameter model estimation. 
 
 
19/03/2013 RANSAC 4 
General Description 
1. First choose a small subset of points. 
2. Fit that subset. 
3. See how many other points fit to the resulting 
function. 
4. Repeat the previous steps till you find enough 
additional points. 
5. Refit the function using all these points. 
 
19/03/2013 RANSAC 5 
RANSAC Algorithm 
Determine: 
 n – the smallest number of points required 
 k – the number of iterations required 
 t – the threshold used to identify a point that fits well 
 d – the number of nearby points required 
Until k iterations have occurred: 
 Draw a sample of n points from the data uniformly and at random. 
 Fit to that set of n point., 
 For each data point outside the sample, 
 Test the “distance” of the point to the function against t 
 end 
 If there are d or more points close to the function then there is a good fit. 
 Refit the function using these points. 
end 
Use the best fit from this collection, using the fitting error as criterion 
19/03/2013 RANSAC 6 
RANSAC Parameters 
n – the smallest number of points required - Problem specific 
 
k – the number of iterations required 
 if w is the fraction of good points, the probability z of seeing 
only bad samples in k draws is equal to 
(1 – wn)k =z 
 If we want to keep z below a limit zmax we have to work with 
 
 
 
 w is usually unknown. We refine the estimate using a previous 
sequence of successful /unsuccessful attempts (it is like 
estimating the probability that a coin comes up heads or tails 
given the sequence of fits). 
 
 ) 1 ( log
) ( log
max
n
w
z
k


19/03/2013 RANSAC 7 
RANSAC Parameters 
 t – the threshold used to identify a point that fits well 
 Specifying this parameter is part of the modeling 
process. 
 Often empirically. 
 
 d – the number of nearby points required 
 if w is the fraction of good points and the sample 
contains a total of N points 
 d < w N.