RANSAC Robust Estimation

RANSAC fits models to noisy matches by voting: sample few points, count supporters, and keep the model with the largest consensus.

RANSAC samples minimal point sets, counts inliers for each candidate, and keeps the model with the largest consensus.

Why Does This Exist?

Least squares trusts every match, so one bad pair bends the answer. Real match sets carry 30 to 70 percent outliers from repetition, occlusion, and motion, which makes direct fitting useless. RANSAC (Fischler and Bolles, 1981) instead hunts the largest self-consistent subset: fit candidates from tiny random samples, let every point vote, and refit the winner on its supporters. It fits lines, homographies, and poses the same way. This page covers the sample-count-vote loop, the iteration math, and the two setup traps. It turns ratio-filtered matches into trustworthy geometry for homographies and structure from motion.

Think of It Like This

Finding the real meeting spot

Ten friends text you meeting spots, but four phones autocorrected wrongly. You test small groups: pick two texts, walk to that corner, and count who else named it. The corner with six supporters beats scattered wrong pins, and you never average all ten pins into a wall.

Minimal samples are those small groups and inlier counts are the supporters. It stops at measurement noise: friends stand on exact corners, while pixels carry detection error, so votes need a distance threshold around each candidate.

How It Actually Works

Pick a minimal sample of size $s$ : 2 points for a line, 4 for a homography, 5 to 8 for camera pose, where $s$ is the smallest count that determines the model. Fit the candidate, count points within reprojection threshold $t$ as inliers, and repeat $N$ times, where $t$ is the pixel tolerance and $N$ is the round count. Keep the largest inlier set, then refit the model on all its inliers with least squares. Adaptive variants update the inlier ratio from the best set so far and stop early once $N$ drops.

Worked example: how many rounds?

With inlier ratio $w = 0.5$ , sample size $s = 4$ , and target success probability $p = 0.99$ , where $w$ is the fraction of true matches and $p$ is your confidence of hitting one clean sample:

N = \frac{\log(1 - p)}{\log(1 - w^s)} = \frac{\log(0.01)}{\log(1 - 0.0625)} \approx \frac{-4.6052}{-0.0645} \approx 71.4

Round up to $N = 72$ : seventy-two rounds give 99 percent odds of one all-inlier sample. With 200 pairs and $t = 3$ pixels, a true homography might claim 110 inliers while bad samples claim 20 to 40, so the winner stands out. Drop to $w = 0.3$ and the same formula gives $N = 567$ , which is why dirty match sets cost real time.

Code

1import math2
3
4def ransac_rounds(w: float, s: int, p: float = 0.99) -> int:5    """Rounds N so an all-inlier sample appears with probability p."""6    return math.ceil(math.log(1 - p) / math.log(1 - w ** s))7
8
9print(ransac_rounds(0.5, 4))10# -> 7211print(ransac_rounds(0.3, 4))12# -> 567

Seventy-two rounds cover a half-clean homography problem at 99 percent confidence, while a 30 percent inlier ratio needs 567, replaying the worked example.

Watch Out For

Threshold copied across resolutions

Three pixels means little on a 4K frame and a lot on a thumbnail. The symptom is inlier sets that swing wildly between runs or resolutions with the same $t$ . Don't reuse a tutorial constant: scale the threshold with image size and expected detection noise.

Degenerate samples accepted blindly

Four near-collinear points define no stable homography yet can still collect accidental inliers. The symptom is a confident transform from a line of points that warps everything else. Check each sample's geometry for spread and non-collinearity before counting its votes.

The Quick Version

RANSAC fits candidates from minimal random samples, not from all points at once.
The inlier threshold defines who counts as a consensus supporter.
Round count follows the outlier ratio and sample size: 72 rounds at half inliers, 567 at 30 percent.
The winner is refit on all its inliers with least squares.
It is the standard gate before any homography or pose estimate is trusted.