narrativeForty Years Against Outliers

Robust two-view geometry did not advance by finding one better algorithm; it advanced by relocating distrust. Longuet-Higgins's 1981 linear solution trusted every calibrated coordinate and every input point equally, so the sequence of fixes that follows strips that trust away one layer at a time — first from the algebra's numerical conditioning, then from the individual correspondence, then from the fixed boundary between inlier and outlier — until the hard threshold itself becomes the thing under suspicion.

The Algebra of Two Views

Epipolar Geometry supplies the constraint every method below tests residuals against: a point visible in one image must lie on a specific line in the other, reducing stereo correspondence search from 2-D to 1-D. Longuet-Higgins Linear Eight-Point Algorithm turns that constraint into arithmetic. Writing $Q = R \cdot \mathrm{skew}(\mathbf{T})$ for the unknown relative pose, the epipolar relation collapses to a bilinear equation $x'^T Q x = 0$, linear in $Q$'s nine entries, and eight calibrated correspondences determine the ratios of the nine $Q$ entries by a single linear solve — replacing Thompson's 1959 five-point method, which required iterating the solution of five simultaneous third-order equations. The unknowns fall out through SVD Null-Space Estimation: $x^\star = v_n$, the smallest right-singular vector of the stacked correspondence system, the same computational core every later linear estimator in this story reuses.

The scale of $Q$ that the linear system alone leaves undetermined is fixed afterward by the trace constraint $\operatorname{tr}(Q^T Q) = 2$, and rotation and translation are peeled apart from the normalised $Q^T Q$ in closed form — no iteration anywhere in the pipeline. The 1981 paper also names its own degenerate configurations — any four points collinear, any seven points coplanar, six points at the vertices of a regular hexagon, eight points at the vertices of a cube — where the linear system loses rank. It does not, however, need to worry about numerical scale: its inputs are calibrated projective coordinates, so the conditioning problem that defines the next chapter simply does not arise inside its own setting.

Numerics Catch Up

Normalised Eight-Point Algorithm generalises Longuet-Higgins's linear DLT from the calibrated essential matrix to the uncalibrated fundamental matrix — the same bilinear constraint, now applied to raw pixel coordinates. That change alone breaks the algebra: on typical images the design matrix's condition number runs 10^11–10^13, and the unnormalised linear solution is dominated by floating-point error. Hartley's fix is not a new formulation but two lines of preconditioning, DLT Normalisation: translate so the centroid of the points is at the origin, then isotropically scale so the average distance from the origin is $\sqrt{2}$. Applied before the identical DLT solve, this drops the condition number of $A^T A$ to roughly $10^3$–$10^5$ — a preconditioning gain of roughly eight orders of magnitude.

The payoff is empirical, not just algebraic: at ten or more correspondences the normalised linear estimate becomes "almost indistinguishable" from the iterative gold-standard estimator, while running ~20× faster. Longuet-Higgins's method is preserved as a historical entry for citation lineage, since Hartley's method recovers everything it recovers — plus the strictly larger uncalibrated problem class — for the cost of the normalisation step alone. What both methods still share, though, is the assumption that every correspondence fed into the design matrix is trustworthy. That assumption is the next one to go.

Gross Outliers Enter

Fischler–Bolles RANSAC discards it outright. Instead of fitting a model to every correspondence and pruning the worst residuals afterward — fitting all data and pruning residuals iteratively — it draws a minimal random sample, instantiates a candidate model, and counts how many of the remaining points are consistent with it within a threshold, keeping whichever hypothesis wins the largest consensus; only after the winner is chosen does an optional least-squares re-fit on that consensus set improve the final parameters. The founding paper has no identified parent technique; it is the paradigm the rest of this story extends.

The trade is exponential sensitivity to the inlier fraction $w$: the expected number of trials scales as $E[k] = w^{-s}$ for minimal sample size $s$, so for $s=4$, halving $w$ from 0.5 to 0.25 drives $E[k]$ from 16 to 256. RANSAC organises everything that follows along four independent design axes — sampling, verification, local optimisation, threshold treatment — that the founding paper and its three major extensions each specialise differently. The founding paper's own consensus re-fit, though, rests on a hidden assumption: that the model a minimal sample produces already fits every true inlier.

Correcting the Minimal Sample

Locally Optimized RANSAC (LO-RANSAC) names that assumption directly and shows it false: the standard termination criterion assumes a model fit from one uncontaminated minimal sample already matches all inliers, an assumption that "rarely holds in practice" because minimal-sample estimates are themselves noisy. The fix inserts a local-optimization step whenever a new best inlier count is found, refitting on a non-minimal sample drawn from the current consensus set instead of trusting the minimal-sample fit outright.

The correction is cheap because it is rare: the $k$-th sample has probability $1/k$ of setting a new record, so the expected number of local-optimization invocations across a run is bounded by $O(\log k)$ — asymptotically negligible against the total sample count. Across five two-view-geometry experiments, standard RANSAC's actual-to-expected sample ratio ranged 2.63–3.35; the best local-optimization variant brought that ratio close to 1.0. The paper states plainly that the modification "makes no new assumptions about the data" and is compatible with, not competing against, other extensions such as MLESAC and NAPSAC — a compatibility that lets the next chapter fold local optimization into a larger machine rather than replace it.

One Engine, Many Parts

USAC: Universal RANSAC Framework does exactly that folding. It is not a new estimator but an engineering decomposition of practical RANSAC into four independently swappable stages: PROSAC quality-ordered sampling, SPRT sequential verification, LO-RANSAC's local optimisation reused directly as its stage-4 module, and DEGENSAC degeneracy handling. SPRT's early-rejection test cuts the mean number of point evaluations per hypothesis by a factor of 2–9 over full consensus counting, corrected by an SPRT-adjusted stopping criterion so the confidence guarantee survives the stochastic early rejections.

DEGENSAC's contribution is narrow but pointed: it detects when $\geq 5$ of the 7 minimal-sample correspondences in a fundamental-matrix draw are secretly related by a homography — a planar degeneracy that silently corrupts every earlier method in this story — and runs a model-completion step to recover the off-plane inliers. The LO-RANSAC stage carries its own separate payoff, reducing the number of required outer iterations by a factor of 2–3 over vanilla RANSAC, and the whole assembly is tested across an inlier-ratio range of 10–92% on homography, fundamental, and essential-matrix benchmarks. What USAC does not touch is the inlier threshold itself: every module in its four-stage decomposition still tests residuals against the same fixed scalar $\varepsilon$ that Fischler and Bolles introduced in 1981. That fixed number is the last untouched assumption.

Marginalising the Threshold

MAGSAC: Marginalising Sample Consensus removes it. Instead of testing each residual against one hard-coded $\varepsilon$, it treats the noise scale $\sigma$ itself as a random variable, uniformly distributed on $[0, \sigma_\mathrm{max}]$, and marginalises the RANSAC quality function over that whole range rather than committing to a single value. The integral is discretised into $d = 10$ uniform partitions of $\sigma$, reducing the fitting cost from $O(K)$ to $O(d)$ model re-fits per hypothesis. The final model is not a re-fit on a hard inlier set at all: it is a weighted least-squares fit using the marginalised inlier likelihoods as IRLS weights. The paper frames this as an empirical refutation of fixed-threshold RANSAC, demonstrated across 545 image pairs where the right noise scale is unknown or varies scene to scene.

The method does not discard everything that came before it — MAGSAC reuses the SPRT pre-screen from USAC and PROSAC ordering for sampling, replacing only the threshold-and-refit step at the center of the loop. That selective reuse is itself the tell. Forty years of this story moved the site of distrust from the algebra, to the conditioning, to the individual correspondence, to the threshold — and each move left the previous machinery mostly intact, aimed at a narrower target. MAGSAC's own sampling and verification stages still draw a minimal sample and still fit it as a single hypothesis. When the inlier threshold is marginalised away, what is left to tune, and is the minimal sample still the right unit of hypothesis?