RANSAC

Definition

Least squares is very unstable with outliers (squared norm). RANSAC counts for a given model how many samples agree with it (inliers) and selects the model with which the most samples agree.

Algorithm

1. Randomly choose $s$ samples ($s$ = minimal sample size: line 2, $E$ 5, $F$ 8)
2. Fit a model to them
3. Count the inliers
4. Update the best solution so far
5. Repeat

Number of iterations for outlier ratio $e$ and success probability $p$:

$$N\ge \frac{\log (1-p)}{\log \left(1-(1-e{)}^s\right)}$$

Intuition

A model estimated only from inliers is supported by most inliers. A model estimated with outliers is supported by few. Smaller $s$ means fewer iterations: with $e=0.5$, $p=0.99$, the 8-point algorithm needs about 1177 iterations, the 5-point algorithm about 146.

Appears in

• Lecture 3, RANSAC
• Lecture 3, Data association: geometric verification
• Lecture 3, Worked example

Related concepts

• Eight-Point Algorithm
• Structure from Motion