Transformation Estimators

Kabsch’s own closed-form solution — not itself in any of the three source PDFs, since it is a 1976 crystallography paper the library only cites via Wikipedia, but built entirely from the SVD machinery this library already relies on elsewhere (Numerical Recipes §2.6) — proceeds in four steps that a reader of EuclideanTransformation2D/3DEstimator.java will recognize directly:

MetricTransformation2D/3DEstimator solve the identical rotation problem, then recover a single extra unknown — a uniform scale — directly from the same SVD, with no further decomposition (MetricTransformation2DEstimator.java:432-436):

where are 's singular values and carries the same reflection sign-fix as the rotation step (the denominator, inCov in the source, is the input point set’s own variance around its centroid). EuclideanTransformation2D/3DEstimator is the special case, consistent with Transformations's statement that Euclidean is metric with scale fixed at 1 — which is why every transformation on that page’s Euclidean/metric rows (rotation plus translation, optionally plus scale) reduces to the same handful of linear-algebra primitives regardless of dimension.

Because this non-robust estimator is a real, independently useful class, the robust wrapper does not reimplement anything: it forwards the minimal-sample-size constants from the non-robust class — 

 — and every concrete {RANSAC|LMedS|MSAC|PROSAC|PROMedS}EuclideanTransformation2DRobustEstimator literally constructs a private EuclideanTransformation2DEstimator and delegates the minimal-sample hypothesis to it:

MetricTransformation2D/3DRobustEstimator follow the identical delegation pattern. This is the only place in com.irurueta.geometry.estimators where "compose, don’t duplicate" holds across the non-robust/robust boundary — contrast with affine and projective transformations below, and with the inlined constructions in Point, Line and Plane Estimators and Conic and Quadric Estimators. Only the point-correspondence variant exists for Euclidean/metric transformations (no line/plane correspondence flavor). 20 concrete robust subclasses total (5 algorithms × {Euclidean2D, Euclidean3D, Metric2D, Metric3D}).

A 2D affine map has 6 unknowns (a 2×2 matrix plus a 2-vector), and each point correspondence contributes 2 equations (its and ) — hence 3 points exactly pin down the 6 unknowns, with no scale ambiguity to divide out (unlike the homogeneous projective case below, affine parameters are already inhomogeneous). The 3D case is the same argument with a 3×3 matrix plus a 3-vector (12 unknowns, 3 equations per point) — 4 points. A line correspondence in 2D contributes exactly the same 2 independent constraints as a point correspondence (a Line2D has 2 degrees of freedom, dual to a Point2D’s), which is exactly why the code needs no separate, larger `MINIMUM_SIZE for the line-correspondence variant — LineCorrespondenceAffineTransformation2DRobustEstimator inherits MINIMUM_SIZE = 3 unchanged from AffineTransformation2DRobustEstimator (verified: it does not redeclare the constant), and likewise PlaneCorrespondenceAffineTransformation3DRobustEstimator inherits MINIMUM_SIZE = 4.

Unlike Euclidean/metric, there is no shared AffineTransformation2DEstimator class to delegate to — each of the 5 concrete {RANSAC|LMedS|MSAC|PROSAC|PROMedS}PointCorrespondenceAffineTransformation2DRobustEstimator classes independently calls the same 3-point constructor:

The residual here is a genuine Euclidean distance between the transformed input point and the measured output point — not an algebraic proxy like the conic/quadric residuals in Conic and Quadric Estimators — because an affine transformation’s output is already an ordinary inhomogeneous point, with no matrix normalization or scale ambiguity to complicate the comparison. The line-correspondence variant’s residual combines the transformed line’s angular and positional agreement with the target line rather than a single point distance (see getResidual in RANSACLineCorrespondenceAffineTransformation2DRobustEstimator.java).

After a robust affine estimate is found, an optional LMSE polish over all detected inliers is available through a separate package: attemptRefine builds a com.irurueta.geometry.refiners.PointCorrespondenceAffineTransformation2DRefiner when the refineResult flag is set (PointCorrespondenceAffineTransformation2DRobustEstimator.java:568-584) — exactly the generic "LMSE re-estimation" step estimators.adoc#shared-architecture describes, concretely instantiated for this hierarchy.

20 concrete robust subclasses total (5 algorithms × {Point2D, Line2D, Point3D, Plane3D}).

A 2D projective transformation (homography) has 9 homogeneous entries, hence 8 degrees of freedom once scale is divided out. Each point correspondence contributes only 2 independent equations, not 3, even though naively looks like 3 equations — Hartley & Zisserman show that only 2 of the 3 rows are linearly independent (§4.1, eq. 4.1-4.3, p.89): "each point correspondence gives two equations in the entries of H". So 8 DOF over 2 equations per point gives exactly 4 points — HZ’s own words: "it is necessary to specify four point correspondences in order to constrain H fully" (p.88), and this is precisely ProjectiveTransformation2DRobustEstimator.MINIMUM_SIZE = 4. One dimension up, a 3D projective transformation has 15 DOF and each point correspondence still contributes only 3 independent equations (of the naive 4), giving points — matching ProjectiveTransformation3DRobustEstimator.MINIMUM_SIZE = 5. As with the affine case, a line correspondence in 2D (or a plane correspondence in 3D) contributes the same equation count as a point, so the minimal sample size is unchanged across correspondence types.

HZ’s Algorithm 4.1 (p.109) is the textbook version of exactly what `RANSACPointCorrespondenceProjectiveTransformation2DRobustEstimator’s minimal-sample hook computes: stack the constraint row from each of the 4 correspondences into an matrix , and take as the right singular vector of with the smallest singular value (the null-space of when the 4 points are in general position):

HZ’s own justification (Appendix A5.3-A5.4, pp.592-593) for "take the last column of " is a short, self-contained proof worth restating, since every homogeneous minimal-sample solve on this site (Point, Line and Plane Estimators, Conic and Quadric Estimators, and this page) ultimately reduces to it. The problem is: find minimizing subject to . Writing and substituting (an orthogonal change of variables, so ):

Because is diagonal with entries in descending order, is minimized by putting all of 's unit "budget" on the coordinate multiplied by the smallest diagonal entry — i.e.  — so is simply the last column of (HZ Algorithm A5.4, p.593). Equivalently, that last column is the eigenvector of with the smallest eigenvalue. This is the exact justification for every new ProjectiveTransformation2D(p1..p4, q1..q4)-style constructor’s use of SingularValueDecomposer across this hierarchy, and for the identical pattern in Conic/Quadric/DualConic/DualQuadric (Conic and Quadric Estimators).

HZ’s Algorithm 4.2 (p.109, motivated in §4.4 "Transformation invariance and normalization", pp.104-108) does not hand the raw pixel coordinates to the SVD solve above — it first applies a similarity transformation to the points so that their centroid sits at the origin and their average distance from it is (so the "average" normalized point is ):

solves for from the normalized points, then denormalizes to recover the homography in the original coordinates ( for the input points, for the output points). HZ’s own motivation (p.107-108) for this step: without normalization, raw image coordinates like make the design matrix’s entries span several orders of magnitude (products like land around while stays at ), which inflates the equation system’s condition number and, in the presence of noise, measurably worsens the SVD solution — HZ states this in so many words: "Data normalization is an essential step in the DLT algorithm. It must not be considered optional."

This is worth stating precisely rather than glossing over, because the library’s own affine/projective robust estimators do not actually implement HZ’s centroid-plus-average-distance scheme above. Two normalization mechanisms exist in this codebase, and neither is that one:

3D projective (plane/point correspondence) and the line-correspondence 2D variant follow the identical SVD-null-space pattern one dimension up or with lines/planes substituted for points. 20 concrete robust subclasses total (5 algorithms × {Point2D, Line2D, Point3D, Plane3D}).