RANSAC for robust fitting
RANSAC fits a model when a quarter of your data is nonsense, by guessing from tiny random samples and keeping the guess that the most points agree with.
- 17 min read
- 3 reading levels
- Updated
Read these first
On this page 10
One lesson, three depths. Pick the one that fits you today — you can switch any time.
Beginner — No maths. Plain English.
The short answer
RANSAC finds the right answer when much of your data is wrong, by trusting whatever the most points agree with.
The analogy you have already lived
Imagine asking a class of forty where the canteen is. Thirty point the same way. Ten point in random directions, because they are new or joking.
You do not average all forty directions — that would send you into a wall. You notice that thirty agree, and you go that way.
RANSAC does exactly this. It looks for the largest group that agrees, and ignores everyone else.
Why averaging fails
The usual way to fit a line is least squares. It picks the line that minimises the total of the squared distances to every point.
Squaring is the problem. A point ten units away contributes a hundred. A point far off in the wrong place contributes enormously, and drags the whole line toward itself.
In the run below, one quarter of the points are nonsense. Least squares gets the slope wrong by 27% and the intercept wrong by more than double. It is not slightly off. It is useless.
How RANSAC works
The idea is almost cheeky.
repeat many times:
1. pick the SMALLEST number of points that define a model
(two points define a line)
2. build the model from just those
3. count how many of ALL the points sit close to it
4. remember it if it is the best count so far
at the end: refit properly, using only the points that agreedStep one is the clever bit. Picking only two points means there is a decent chance both are good. Picking twenty would almost guarantee at least one is bad.
Why so few points
Suppose 70% of your points are good. The chance both of two random points are good is 0.7 times 0.7, about half. So one try in two gives a clean model, and a few dozen tries make failure very unlikely.
Now pick eight points instead. The chance all eight are good is 0.7 to the eighth power, about 6%. You would need roughly 70,000 tries.
The table in the code output shows this exactly. Fewer points per guess is the whole trick.
The one number you must choose
How close does a point have to be to count as agreeing? That is the threshold, and it is the setting that decides everything.
Too tight, and you throw away good data along with the bad. Too loose, and outliers slip in and pull the answer back toward the broken average.
The output below sweeps it. At a threshold of 8 the slope error grows sevenfold, because sixteen outliers were let in.
The honest part
RANSAC is random. Run it twice and you can get two different answers.
With enough tries the difference disappears. With too few, the spread is dramatic. The run below gets slopes of 2.03 and -4.73 from the same data.
So if a pipeline gives different results each run, check the RANSAC iteration count before blaming anything else.
Where you have already seen it
- Panorama stitching, which throws away the wrong feature matches.
- GPS software rejecting a reflected satellite signal.
- A robot fitting a floor plane while people walk through the scan.
- Any step in this section that starts from matched points.
Remember this
- RANSAC keeps the model that the most points agree with.
- It guesses from the smallest possible sample, which is why it works.
- Its threshold and its iteration count are the two things you must set.
What to learn next
- Structure from motion — where RANSAC runs on every image pair.
- Homographies and perspective warp — the model most often fitted this way.
- Linear regression — the estimator RANSAC is protecting.
Developer — Code and libraries.
Setup
pip install numpy==1.26.4RANSAC is about twenty lines. Writing it once makes every library call afterwards legible, including the cv2.RANSAC flag in findHomography.
RANSAC written out, and its two knobs measured
import numpy as np
rng = np.random.default_rng(7)
TRUE_M, TRUE_C = 2.0, 5.0
x = np.linspace(0, 20, 60)
y = TRUE_M * x + TRUE_C + rng.normal(0, 0.6, 60) # 60 honest points
n_bad = 20
bad_x = rng.uniform(0, 20, n_bad)
bad_y = rng.uniform(0, 60, n_bad) # 20 points from nowhere
X = np.concatenate([x, bad_x])
Y = np.concatenate([y, bad_y])
is_good = np.array([True] * 60 + [False] * n_bad)
print(f"{len(X)} points: {is_good.sum()} on the line, {n_bad} outliers "
f"({100 * n_bad / len(X):.0f}%)")
print(f"true line: y = {TRUE_M} x + {TRUE_C}\n")
A = np.vstack([X, np.ones_like(X)]).T
m_ls, c_ls = np.linalg.lstsq(A, Y, rcond=None)[0]
print(f"least squares on everything: y = {m_ls:.3f} x + {c_ls:.3f}")
print(f" slope error {abs(m_ls - TRUE_M):.3f}, intercept error {abs(c_ls - TRUE_C):.3f}")
print(" every outlier pulls on the fit, and squaring makes the far ones pull hardest\n")
def ransac_line(X, Y, threshold=1.5, iterations=200, seed=0):
rs = np.random.default_rng(seed)
best_inliers, best_model = None, None
for _ in range(iterations):
i, j = rs.choice(len(X), 2, replace=False) # 2 points define a line
if X[i] == X[j]:
continue
m = (Y[j] - Y[i]) / (X[j] - X[i])
c = Y[i] - m * X[i]
residual = np.abs(Y - (m * X + c)) / np.sqrt(1 + m * m) # perpendicular distance
inliers = residual < threshold
if best_inliers is None or inliers.sum() > best_inliers.sum():
best_inliers, best_model = inliers, (m, c)
# Refit on the agreed inliers: the 2-point model was only a hypothesis.
Ai = np.vstack([X[best_inliers], np.ones(best_inliers.sum())]).T
m, c = np.linalg.lstsq(Ai, Y[best_inliers], rcond=None)[0]
return m, c, best_inliers
m_r, c_r, inliers = ransac_line(X, Y)
print(f"RANSAC, then least squares on its inliers: y = {m_r:.3f} x + {c_r:.3f}")
print(f" slope error {abs(m_r - TRUE_M):.3f}, intercept error {abs(c_r - TRUE_C):.3f}")
tp = int((inliers & is_good).sum())
fp = int((inliers & ~is_good).sum())
print(f" kept {inliers.sum()} points: {tp} genuine, {fp} outliers wrongly kept")
print(f" missed {int((~inliers & is_good).sum())} genuine points\n")
print("how many tries do you need? the standard formula:")
print(" iterations = log(1 - p) / log(1 - w^s)")
print(" p = chance of success you want, w = fraction of good points,")
print(" s = points needed per hypothesis\n")
print(" s w=0.9 w=0.7 w=0.5 w=0.3")
for s in [2, 4, 8]:
row = f" {s:<4}"
for w in [0.9, 0.7, 0.5, 0.3]:
n = np.log(1 - 0.99) / np.log(1 - w ** s)
row += f"{int(np.ceil(n)):>8}"
print(row)
print("\n read the last column: a model needing 8 points, with 70% outliers,")
print(" needs about 70,000 tries. Small sample sizes are what make RANSAC work.\n")
print("the threshold is the one knob that really matters:")
for t in [0.05, 0.3, 0.8, 1.5, 3.0, 8.0]:
m, c, inl = ransac_line(X, Y, threshold=t)
kept_bad = int((inl & ~is_good).sum())
print(f" threshold {t:>5.2f}: kept {inl.sum():>3} points "
f"({kept_bad} of them outliers), slope {m:.3f}, error {abs(m - TRUE_M):.3f}")
print("\n too small: most genuine points get thrown out with the outliers")
print(" too large: outliers get in and drag the answer back toward least squares")
print("\nRANSAC is random, so it is not the same answer every run:")
for seed in range(6):
m, c, inl = ransac_line(X, Y, iterations=2, seed=seed)
print(f" seed {seed}, only 2 iterations: slope {m:7.3f} inliers {inl.sum():>3}")
print(" with enough iterations the spread collapses; with too few it does not")80 points: 60 on the line, 20 outliers (25%) true line: y = 2.0 x + 5.0 least squares on everything: y = 1.452 x + 11.084 slope error 0.548, intercept error 6.084 every outlier pulls on the fit, and squaring makes the far ones pull hardest RANSAC, then least squares on its inliers: y = 2.032 x + 4.564 slope error 0.032, intercept error 0.436 kept 65 points: 60 genuine, 5 outliers wrongly kept missed 0 genuine points how many tries do you need? the standard formula: iterations = log(1 - p) / log(1 - w^s) p = chance of success you want, w = fraction of good points, s = points needed per hypothesis s w=0.9 w=0.7 w=0.5 w=0.3 2 3 7 17 49 4 5 17 72 567 8 9 78 1177 70188 read the last column: a model needing 8 points, with 70% outliers, needs about 70,000 tries. Small sample sizes are what make RANSAC work. the threshold is the one knob that really matters: threshold 0.05: kept 16 points (0 of them outliers), slope 1.988, error 0.012 threshold 0.30: kept 51 points (1 of them outliers), slope 2.028, error 0.028 threshold 0.80: kept 64 points (4 of them outliers), slope 2.022, error 0.022 threshold 1.50: kept 65 points (5 of them outliers), slope 2.032, error 0.032 threshold 3.00: kept 66 points (6 of them outliers), slope 2.051, error 0.051 threshold 8.00: kept 74 points (16 of them outliers), slope 1.779, error 0.221 too small: most genuine points get thrown out with the outliers too large: outliers get in and drag the answer back toward least squares RANSAC is random, so it is not the same answer every run: seed 0, only 2 iterations: slope 2.032 inliers 65 seed 1, only 2 iterations: slope 2.020 inliers 36 seed 2, only 2 iterations: slope 2.022 inliers 64 seed 3, only 2 iterations: slope 1.291 inliers 21 seed 4, only 2 iterations: slope -4.727 inliers 11 seed 5, only 2 iterations: slope -4.474 inliers 11 with enough iterations the spread collapses; with too few it does not
Reading the output carefully
Least squares: slope 1.452 where the truth is 2.0. Twenty-five per cent bad data, and the answer is 27% wrong. Least squares has a breakdown point of zero — a single sufficiently distant outlier can move the fit arbitrarily far. It is the right estimator only when you already know the noise is well behaved.
RANSAC: slope 2.032, from the same data. Error down from 0.548 to 0.032, a factor of seventeen.
missed 0 genuine points, 5 outliers wrongly kept. Not perfect classification, and it does not need to be. Five random points that happen to fall within 1.5 units of the line are, by construction, nearly harmless — they sit close to the answer. RANSAC does not need to identify outliers correctly; it needs to exclude the ones that would matter.
The refit step is easy to miss and important. The two-point model is a hypothesis, and it is fitted to exactly two noisy points. Once the inlier set is agreed, refitting by least squares on all 65 of them recovers the precision that two points cannot provide. Skipping this is a common bug and costs real accuracy.
The iteration table is the argument for minimal samples. Look along the s = 8 row: 9, 78, 1177, 70188. Doubling the sample size does not double the cost, it raises it exponentially. This is why estimators are formulated with the fewest points possible — 4 for a homography, 5 for an essential matrix, 3 for a plane.
The threshold sweep is honest about both directions. At 0.05 the fit is accurate but built from 16 of 80 points, and on noisier data that few points would be unstable. At 8.00 sixteen outliers are inside the tent and the slope error grows to 0.221. The useful range here is wide, roughly 0.3 to 3.0, because the inlier noise is 0.6.
The seed table is the honesty section. With two iterations the same code returns 2.032 and -4.727 from the same data. RANSAC gives a probabilistic guarantee, not a deterministic one, and the guarantee is only as good as the iteration count.
Choosing the threshold in practice
Set it from your measurement noise, not by trial and error. If inlier residuals are Gaussian with standard deviation $\sigma$, a threshold of $2\sigma$ to $3\sigma$ keeps 95% to 99% of inliers.
For feature matching, $\sigma$ is roughly the keypoint localisation error — about 1 pixel for SIFT and about 2 for ORB, matching what we measured. So a reprojection threshold of 2 to 4 pixels is the usual setting, and it is why cv2.findHomography(..., cv2.RANSAC, 3.0) looks the way it does.
Using OpenCV's version
H, mask = cv2.findHomography(src, dst, cv2.USAC_MAGSAC, 3.0,
maxIters=10000, confidence=0.9999)
E, mask = cv2.findEssentialMat(p1, p2, K, method=cv2.USAC_MAGSAC, threshold=1.0)
_, rvec, tvec, inliers = cv2.solvePnPRansac(obj_pts, img_pts, K, dist)Prefer USAC_MAGSAC over plain cv2.RANSAC in current OpenCV. It marginalises over the threshold rather than fixing it, which makes it far less sensitive to the one setting you are least sure about. The mask output is the inlier set, and you should always look at how many survived — a low inlier count is the earliest warning that a pipeline is about to produce confident nonsense.
Common mistakes
Forgetting to refit on the inliers. Discussed above. Some library calls do it for you; check.
Using a fixed iteration count on hard data. Adaptive RANSAC updates the required iteration count from the best inlier ratio seen so far, and stops early when the guarantee is met. It is a few lines and it is what OpenCV does internally.
Setting the threshold from the model's units instead of the measurement's. A homography threshold is in pixels, a plane-fitting threshold is in metres. Mixing them up produces either everything or nothing as inliers.
Assuming the largest consensus is the right one. If more than half the data comes from a second structure — two planes in view, say — RANSAC can lock onto the wrong one. Sequential RANSAC or multi-model methods are needed then.
Reporting results without the inlier count. A homography from 8 inliers and one from 200 are different levels of evidence, and the matrix looks identical.
Try it yourself
Raise n_bad from 20 to 200, so 77% of the points are outliers, and keep iterations=200. RANSAC will start failing. Then raise iterations to 2000 and it recovers. Compare against the formula's prediction for w = 0.23, s = 2 and see how close it lands.
What to learn next
- Structure from motion — where RANSAC runs on every image pair.
- Homographies and perspective warp — the model most often fitted this way.
- Linear regression — the estimator RANSAC is protecting.
Researcher — Mathematics and papers.
The algorithm
Fischler and Bolles (1981), Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography, CACM 24(6). One of the most-cited papers in computer vision, and the algorithm is a page long.
Given data $\mathcal{D}$ with an unknown fraction $w$ of inliers, a model requiring $s$ points, and an inlier threshold $t$:
- Sample $s$ points uniformly at random.
- Fit the model exactly to those $s$ points.
- Score by $|{d \in \mathcal{D} : \operatorname{err}(d, \text{model}) < t}|$.
- Keep the best-scoring model; repeat $N$ times.
- Refit on the best consensus set.
The iteration count
The probability that a single sample is all-inlier is $w^s$. The probability that $N$ samples all contain at least one outlier is $(1 - w^s)^N$. Setting this to $1 - p$ for a desired success probability $p$:
$$ N = \frac{\log(1 - p)}{\log(1 - w^{s})} $$
Three things this formula does not say, and all three matter.
- It assumes an all-inlier sample yields a good model. Degenerate configurations — three collinear points for a homography, a pure-rotation pair for an essential matrix — break this, and the sample is clean but useless.
- It assumes $w$ is known. It is not. Adaptive RANSAC substitutes the running estimate $\hat{w} = |\text{best consensus}| / |\mathcal{D}|$ and recomputes $N$ each iteration, which is what production implementations do.
- It gives a probability of sampling a clean set, not of selecting it. A degenerate or lucky outlier-contaminated model can outscore the clean one under noise.
Sampling $s$ points without replacement from a finite set makes the true probability hypergeometric; the $w^s$ form is the large-$N$ limit and is accurate enough in practice.
The cost function
Plain RANSAC maximises the inlier count, which is equivalent to minimising a top-hat loss:
$$ \mathcal{L}_{\text{RANSAC}} = \sum_i \rho(e_i), \qquad \rho(e) = \begin{cases} 0 & |e| < t \ 1 & \text{otherwise} \end{cases} $$
This is a 0-1 loss, so it is insensitive to how well inliers fit — a model with all residuals at $0.99t$ scores identically to one with all residuals at zero. Two well-known refinements:
MSAC (Torr and Zisserman, 2000) replaces the top-hat with a truncated quadratic, $\rho(e) = \min(e^2, t^2)$. It costs nothing extra and is strictly better; it is what OpenCV's RANSAC flag actually implements.
MLESAC models the residuals as a mixture of an inlier Gaussian and a uniform outlier distribution, and maximises the likelihood, estimating the mixing parameter by expectation-maximisation.
Modern variants worth knowing
- LO-RANSAC (Chum et al., 2003) runs a local optimisation — an inner refit-and-rescore loop — whenever a new best model is found. It reaches the theoretical accuracy in far fewer outer iterations, and it is the reason a well-implemented RANSAC beats a naive one by a wide margin.
- PROSAC (Chum and Matas, 2005) samples in order of match quality rather than uniformly, exploiting the fact that a low descriptor-distance ratio predicts a correct match. It converges dramatically faster on feature-matching problems and degrades to plain RANSAC in the worst case.
- MAGSAC and MAGSAC++ (Barath et al., CVPR 2019 and 2020) marginalise over the noise scale $\sigma$ rather than fixing $t$, using a $\chi^2$ model of the residuals. This removes the threshold as a hyperparameter, and it is why
cv2.USAC_MAGSACis the right default in current OpenCV. - GC-RANSAC adds a graph-cut local optimisation exploiting spatial coherence of inliers.
The USAC framework (Raguram et al., TPAMI 2013) unifies these into a single configurable pipeline, and OpenCV's USAC_* flags expose it.
Degeneracy
The most dangerous failure mode is a sample that is clean but uninformative.
For two-view geometry, the classic case is a scene that is planar, or a camera that only rotates. Both make the essential matrix under-determined, and RANSAC then returns a model with a high inlier count that is wrong. DEGENSAC (Chum et al., CVPR 2005) detects this by testing whether the inliers are explained by a homography, and is important for any real SfM pipeline — planar scenes are common.
Where it does not apply
RANSAC needs a model fittable from a small sample and a residual you can compute for every datum. That covers geometry and covers very little else.
For a neural network there is no minimal sample and no cheap residual, so robustness comes from robust losses instead — Huber, or the general adaptive family of Barron (CVPR 2019), A general and adaptive robust loss function, which interpolates between L2, Cauchy and Welsch with a learnable shape parameter. That is the right mental model: RANSAC is a robust estimator for problems with exact minimal solvers, and robust losses are its counterpart everywhere else.
What to learn next
- Structure from motion — where RANSAC runs on every image pair.
- Homographies and perspective warp — the model most often fitted this way.
- Linear regression — the estimator RANSAC is protecting.