Estimators

A non-robust estimator solves a well-posed algebraic or least-squares problem: given exactly the minimal number of correspondences an entity needs (2 points for a line, 3 for a circle, 5 for a conic, 4 for a 2D homography, 6 for a camera, …​), or more than that minimum, it produces the entity that fits them exactly, or in an LMSE (Least Mean Squared Error) sense if over-determined. This is exactly what a class like PlaneEstimator-if it existed as a public class-or the inlined closed-form constructors inside RANSACPlaneRobustEstimator do: for 3 points, no iteration, no notion of "this correspondence might be wrong".

The problem is that real correspondences — 2D/3D point matches from a feature detector, line matches from an edge detector — are never 100% correct. A single badly-matched point dragged into an LMSE fit can move the whole result arbitrarily far from the truth, because a least-squares cost grows quadratically with a point’s residual: one far-away outlier can dominate the sum of squared errors contributed by every other, correct, point. `irurueta-geometry’s own family portrait of this problem is exactly Transformations / Conics and Quadrics / Pinhole Camera's entities: none of their non-robust fits have any built-in outlier rejection.

Robust estimation solves a different, harder problem: simultaneously find the entity and the subset of correspondences that agree with it (the inliers), while implicitly discounting the rest (the outliers) — without knowing in advance which is which. com.irurueta.geometry.estimators solves this the same way for every one of its twelve hierarchies:

That is why every hierarchy in this library has the same shape: one small, exact/LMSE algorithm, wrapped by five classes that differ only in step 2’s scoring rule. The next section works through each rule with the real equations behind it.

RANSAC (RANdom SAmple Consensus) is Fischler and Bolles' original 1981 algorithm (Fischler & Bolles, 1981), and the one all the others are variations of. Quoting the algorithm as stated in Hartley & Zisserman (chapter 4, Algorithm 4.4, p.119):

Two constants make this concrete, and the library exposes both as configurable properties on every XxxRobustEstimator:

Instead of counting inliers under a fixed threshold, LMedS scores a candidate by the median of its squared residuals over the whole data set, and keeps the candidate with the smallest median (HZ §4.7.3, p.120: "Least Median of Squares (LMS) estimation…​ requires no setting of thresholds or a priori knowledge of the variance of the error"):

The number of samples is still drawn from the same eq. 4.18. The trade-off is symmetric to RANSAC’s: no threshold to tune, but the median is only a meaningful "typical" residual while inliers are the majority — LMedS breaks down once outliers exceed 50% of the data, exactly where thresholded RANSAC keeps working provided is chosen well. Numerical Recipes §15.7 "Robust Estimation" (p.818) frames the same median-based idea for the simpler 1D case (Fitmed, a least-median/least-absolute-deviation line fit, p.823) as a general antidote to the sensitivity of ordinary least squares to a "long tail of outliers" — the 1D special case of exactly the geometric problem LMedSLine2DRobustEstimator and its eleven siblings solve.

RANSAC’s step-function score (an inlier contributes 0 cost, an outlier contributes a fixed cost, nothing in between) throws away information: two inliers at different distances from the model score identically. HZ proposes, without naming it, exactly the cost function that Torr and Zisserman later formalized as MSAC (M-estimator SAmple Consensus, Torr & Zisserman, 2000) and the library implements as its MSACXxxRobustEstimator classes:

(HZ eq. 4.19, p.120). Inliers still contribute their true squared residual (the maximum-likelihood cost under a Gaussian error model, HZ §4.3), but outliers are capped at rather than contributing 0 — so MSAC’s winning hypothesis is the one minimizing total cost, not maximizing inlier count, letting a model with slightly fewer, tighter inliers beat one with more, looser ones. Threshold and sample count are computed exactly as in RANSAC.

PROSAC (PROgressive SAmple Consensus, Chum & Matas, 2005) and this library’s PROMedS keep RANSAC’s/LMedS’s scoring rules unchanged, but change which samples are drawn first: if each correspondence carries a quality score (e.g. a feature descriptor’s match confidence), samples are drawn in decreasing quality order instead of uniformly at random, so a sample entirely made of high-quality matches — and thus likely outlier-free — is tried early rather than waiting for it to come up by chance. Every PROSACXxxRobustEstimator/PROMedSXxxRobustEstimator constructor accordingly takes an extra double[] qualityScores argument, one entry per correspondence (e.g. PROSACDLTPointCorrespondencePinholeCameraRobustEstimator(double[] qualityScores)); RANSAC, LMedS and MSAC take none. PROSAC postdates HZ's 2nd edition (2004) and neither it nor an equally-named PROMedS reference was found in any of the three source PDFs used for this documentation pass; the description above reflects the library’s own javadoc and constructor signatures rather than a page citation.

None of the five robust algorithms above is reimplemented per entity. com.irurueta.geometry.estimators delegates to a single, generic, entity-agnostic implementation in the sibling module com.irurueta.numerical.robust: abstract RobustEstimator<T> plus concrete, type-parameterized RANSACRobustEstimator<T>, LMedSRobustEstimator<T>, MSACRobustEstimator<T>, PROSACRobustEstimator<T>, PROMedSRobustEstimator<T>. Every RANSACXxxRobustEstimator in com.irurueta.geometry.estimators is a thin adapter: its estimate() builds an anonymous RobustEstimatorListener<T> whose estimatePreliminarSolutions(int[] sampleIndices, List<T> solutions) plugs in that entity’s minimal-sample closed-form construction, and whose computeResidual(T, int) plugs in that entity’s geometric distance formula — then hands both to new RANSACRobustEstimator<>(listener).estimate() (see e.g. RANSACConicRobustEstimator.java:165-249). This is why adding a thirteenth entity to the library would not require reimplementing RANSAC: only the two entity-specific hooks change.

Every entity below follows exactly the pattern described above; the pages linked here work through each one’s specific minimal-sample algorithm, distance/residual formula, and any book equations that match it.

Full citations are in the bibliography. In summary: Fischler & Bolles for RANSAC itself; Hartley & Zisserman chapter 4 (§4.1-4.2 DLT algorithms and cost functions, §4.7 robust estimation, Algorithms 4.1-4.6) for the RANSAC/MSAC equations and thresholds used above; Irurueta’s PhD thesis §2.5 for an independently-derived RANSAC camera-estimation algorithm using the same sample-count formula; Numerical Recipes §15.7 for the 1D robust/median-fit analogue of LMedS; Torr & Zisserman for the formal MSAC/MLESAC name; and Chum & Matas for PROSAC.