12.5 Robustness: the ratio test and RANSAC⧉
A candidate correspondence can select the wrong repeated window, miss an occlusion, or match unrelated texture. These outliers can dominate a least-squares geometric fit. Descriptor ambiguity tests and geometric consensus address different parts of the problem.
Two classic filters make matching usable, and they attack the problem from opposite ends. One prunes matches before any geometry is fit, by spotting which matches are ambiguous. The other fits a transform despite the outliers that survive pruning, by replacing the fragile least-squares average with a robust consensus vote. Neither alone is enough; together they turn a 50%-garbage match set into a clean geometric model.
12.5.1 The ratio test: reject ambiguous matches before fitting⧉
The instinct, when you have a keypoint in image A and a set of candidates in image B, is to keep the match if the nearest descriptor is close. Lowe's ratio test (Lowe 2004 Lowe 2004) says that is the wrong question. Closeness in absolute terms is unreliable because a descriptor on a high-contrast corner is close to its true partner, a descriptor on flat texture is far from everything, and a single threshold on distance cannot serve both. The right question is about ambiguity: is the nearest match decisively better than the second-nearest one?
So for each keypoint, find its two nearest neighbors in descriptor space, at distances $d_1\le d_2$, and accept the match only if
The logic is clean. A distinctive point (a unique corner of a window frame) has one obviously-best partner and everything else far away, so $d_1\ll d_2$ and the ratio is small: keep it. A point on repeated texture (one brick among a hundred) has a best match that is barely better than the next brick over, so $d_1\approx d_2$, the ratio is near $1$, and the match is thrown out (Figure 12.5.1). The test measures exactly the failure mode that breaks matching: it does not ask "is this match good?" but "is there a competitor that makes this match untrustworthy?" That is why it works where an absolute-distance threshold does not, because repeated structure produces near-ties, and near-ties are precisely what the ratio catches.
The ratio threshold is empirical and descriptor-dependent. Handle fewer than two candidates and zero second-neighbor distance explicitly. If a search returns squared distances, compare their ratio with the square of the distance-ratio threshold. Mutual nearest-neighbor checks impose another useful consistency condition but do not replace geometry.
Rejecting ambiguity costs some correct matches too. A real window corner may have a nearly identical neighbor on the same façade, so its descriptor does not identify a unique partner even when the best candidate happens to be right. Lowering the ratio threshold generally rejects more such cases. This is a precision/recall choice before geometric fitting, not proof that the remaining pairs are correct.
12.5.2 RANSAC: fit from a minimal random sample, score by consensus⧉
After the ratio test, outliers remain, so we must fit the transform in a way that tolerates them, without letting every bad match directly influence every fitted hypothesis. RANSAC, RANdom SAmple Consensus, from Fischler & Bolles (1981) Fischler & Bolles 1981, does this with an idea that is simple and exactly right. Rather than fit one model to all the data and hope, fit many models to tiny random subsets and let the data vote.
The loop, for fitting a transform $T$ (Figure 12.5.4 shows it on a homography):
- Draw a minimal random sample, the fewest matches that determine the model. Two points for a line, four point-pairs for a homography $H$, and so on. Minimal is deliberate: the smaller the sample, the higher the chance it lands entirely on inliers.
- Fit $T$ from just that sample (reject repeated or collinear configurations before solving; numerical conditioning still matters).
- Score by consensus. Count how many of all the other matches agree with this $T$, the inliers, using the test $\lVert \mathbf{x}'_i - T(\mathbf{x}_i)\rVert < \epsilon$: a match is an inlier if mapping $\mathbf{x}_i$ through $T$ lands within $\epsilon$ pixels of its claimed partner $\mathbf{x}'_i$.
- Repeat, keeping the $T$ with the largest inlier set.
- Refit that winning model by least squares on all its inliers. Recompute residuals and the inlier set after refinement; the consensus may still contain outliers or reflect the wrong motion model.
Here is why this beats least squares. A least-squares fit averages in every match, so a handful of gross outliers drag the answer off (Figure 12.5.2, the canonical picture: the least-squares line tilts toward the outliers, while RANSAC's best minimal-sample line threads the inlier majority). RANSAC instead ignores outliers rather than averaging them: a minimal sample that happens to be all-inlier defines a model the inlier majority votes for, and inconsistent outliers contribute little support to that hypothesis. Structured outliers can form a competing consensus. The method is robust even when most of the matches are wrong, which is exactly the regime keypoint matching lives in.
Suppose an independent trial yields an all-inlier, nondegenerate minimal sample with probability approximated by $w^s$. To make the probability of at least one such trial at least $p$, choose the ceiling of
Read the three dependencies off this formula, because they are the design knobs. The sample size $s$ sits in an exponent, so larger minimal samples raise the cost quickly; you want the minimal solver and not one match more (this is why "minimal sample" is load-bearing, not a stylistic choice). The inlier fraction $w$ sets the base of the exponential, so a cleaner match set converges much faster. And $N$ itself is the good exponential: more iterations drive failure down geometrically, and iterations are cheap (a four-point solve plus a residual count). A concrete case from the slides: with a homography ($s=4$) and a 50% inlier fraction ($w=0.5$), a single draw succeeds only 6% of the time, but $N=100$ iterations cuts the failure probability to about $1$ in $600$, and $N=1000$ to astronomically small. Even at a punishing $w=0.1$, raising $N$ buys success; you simply pay more iterations. RANSAC trades one fit to all samples for a search over hypotheses. The trial probability quantifies one part of that search under stated assumptions; it does not make the result immune to outliers or model error.
Consensus is more robust than averaging. A least-squares fit is an average: it minimizes a sum of squared residuals, so it is perfectly behaved when every data point is a slightly-noisy inlier, and catastrophically fragile the instant one point is a gross outlier, because that one term dominates the sum. RANSAC's move is to stop averaging the raw data and instead let the data vote: fit from a minimal sample (small enough to occasionally be outlier-free), score by how many others agree, and keep the model with the most votes, and average only at the very end, after the outliers have been excluded. The pattern recurs far beyond matching: whenever your data is contaminated by points that don't merely add noise but actively lie, replace the global average with a consensus-of-a-clean-subset. Robustness is not a better fit to all the data; it is knowing which data to fit. Consensus has its own failure: when the data are degenerate, or when the outliers are themselves consistent (a repeated pattern, a second moving object), the largest agreeing set can support the wrong model.
The usual bound approximates sampling without replacement and assumes the estimated inlier rate is meaningful. Degenerate samples and structured outliers reduce effective success. Handle rates near zero or one explicitly, use a finite trial cap, and report failure when the support is inadequate. A homography’s inliers should cover the image region being warped, not occupy one small corner.
The sample-size exponent has a large practical effect. With an inlier fraction of one half and a four-match minimal sample, only about one draw in sixteen is all-inlier under the independent-draw approximation. Reaching a 99 percent chance of at least one all-inlier sample takes about 72 draws. With an inlier fraction of one fifth, the same calculation gives about 2,876 draws. A modest improvement in match quality can therefore save much more work than the inlier percentages suggest. These counts concern drawing an all-inlier sample, not guaranteed recovery: degenerate configurations, localization error, and a wrong geometric model can still defeat the fit.
12.5.3 Variants and degeneracy⧉
The sample-and-score skeleton is so useful that a family of variants has grown around it, each improving one piece while keeping the loop intact:
- MLESAC (Torr & Zisserman 2000) replaces the hard inlier count with a likelihood score. Instead of asking whether a point is in or out at threshold $\epsilon$, it models inliers and outliers as a mixture and scores a model by how probable the data is under it. This makes the choice between near-tied models less brittle than a binary count.
- PROSAC (Chum & Matas 2005) attacks the iteration budget directly: rather than sample uniformly, draw from the most confident matches first (ranked by descriptor-match quality). Good matches are more likely to be inliers, so a clean minimal sample is found in far fewer iterations, often an order of magnitude fewer, while degrading gracefully to plain RANSAC if the confident matches mislead.
- LO-RANSAC Chum, Matas & Kittler 2003 (LO-RANSAC) adds a local optimization: each time the best model improves, run a quick inner refit (least squares on the current inliers, possibly with a looser-then-tighter threshold) before continuing. This closes the gap between RANSAC's coarse minimal-sample estimate and the true optimum, with little extra cost.
- MAGSAC++ (Barath et al., 2020) reduces sensitivity to a single inlier threshold by marginalizing over noise scales and using the resulting weights in iterative fitting. It still needs a maximum noise scale; it does not remove every threshold or guarantee a fit when the model or matches are wrong.
All four keep the draw-a-sample, score-by-agreement, keep-the-best loop; they change how you sample, how you score, or how you refine, never the core idea.
There is one caveat that no amount of iteration fixes: RANSAC finds consensus, not truth. The algorithm trusts whatever model the most points agree on, but a degenerate configuration can make a wrong model win with overwhelming consensus. The textbook case lives in two-view geometry (Chapter 36.1, Multiple view geometry): if you are estimating the fundamental matrix $F$ to recover 3-D structure, but all the matched points happen to lie on a single plane (a building façade, a tabletop), then the data is consistent with infinitely many $F$'s, and RANSAC will confidently return one of them. It is geometrically valid by its inlier count, but useless for reconstruction. Consensus and correctness diverge exactly when the data is degenerate. The standard guards are a planar-versus-3-D check (test whether the inliers are explained by a homography alone, which flags the planar degeneracy) and choosing minimal solvers matched to the geometry you actually want. The lesson sits one level above the algorithm: a method that rewards agreement will be fooled by data that agrees for the wrong reason.
These three pieces, the ratio test, RANSAC, and a degeneracy guard, are what make sparse matching usable. The automatic-panorama chapter in the Multiple-Exposure-Imaging part, Chapter 20.2, Automatic panorama stitching from multiple views and feature matching, runs the full pipeline in anger: Harris corners Harris & Stephens 1988 → descriptors → ratio test → RANSAC homography → blend; and the same robust-fitting machinery underwrites every two-view estimator in Chapter 36.1, Multiple view geometry. Prune ambiguous matches, fit by consensus, and check for degeneracy.
Recap: big lessons of this chapter
Consensus is more robust than averaging. A least-squares fit is an average: it minimizes a sum of squared residuals, so it is perfectly behaved when every data point is a slightly-noisy inlier, and catastrophically fragile the instant one point is a gross outlier, because that one term dominates the sum. RANSAC's move is to stop averaging the raw data and instead let the data vote: fit from a minimal sample (small enough to occasionally be outlier-free), score by how many others agree, and keep the model with the most votes, and average only at the very end, after the outliers have been excluded. The pattern recurs far beyond matching: whenever your data is contaminated by points that don't merely add noise but actively lie, replace the global average with a consensus-of-a-clean-subset. Robustness is not a better fit to all the data; it is knowing which data to fit. Consensus has its own failure: when the data are degenerate, or when the outliers are themselves consistent (a repeated pattern, a second moving object), the largest agreeing set can support the wrong model.