RANSAC

Least squares lets every point vote, so a few wild outliers can drag the answer far off. RANSAC instead guesses a model from the smallest possible random sample, counts how many points agree with it, and keeps the guess with the most agreement.

Outlier fraction Inlier distance threshold Iterations per second

The loop

Repeat: pick 2 random points, draw the line through them, count the points within distance $t$ of it. Keep the line with the most inliers, then refit it to those inliers with least squares. To succeed with probability $p$ when a fraction $w$ of points are inliers, you need about

$$N = \frac{\log(1 - p)}{\log(1 - w^2)}$$

iterations, since each try needs both sampled points to be inliers.

What to notice

The navy least squares line is pulled toward the outliers. RANSAC's red line ignores them and lands on the true line, with its inliers highlighted. With more outliers it takes more tries to stumble on a good pair, which the formula predicts. RANSAC is used everywhere in robot perception: fitting floor planes to point clouds, matching features between images, and estimating camera motion.