Robust Estimation

Division of labor

VisualGeometryToolkitCore owns the contracts every robust estimator composes through — the problem protocol, the scoring contract, the local-optimization contract — together with the robust-statistics toolkit, the loss family and the baseline scorers. The one generic RANSAC loop, the problems and the core local optimizations live in VisualGeometryToolkitEstimation.jl; the paper scorers in RANSACScoringDoneRight and the paper local optimizers in LocalOptimizationDoneRight implement the contracts. See The composable RANSAC below.

Which function for which task

An estimator's name states its kind: a one-step algorithm is called by its algorithm's name; a minimal solver runs through the solve(solver, cs, idx) protocol; iterative fits (fit_*), robust searches (find_*) and refinements from a guess (refine_*) live in VisualGeometryToolkitEstimation. Data go in as correspondences (a => b pairs, a Correspondences preferred), with per-correspondence weights as its weights column.

TaskFunctionKindPackage
Homography from ≥ 4 point correspondenceshomography_dlt(cs)one-stepVGC
Fundamental matrix from ≥ 8 correspondencesfundamental_dlt(cs)one-stepVGC
Essential matrix from ≥ 8 bearing pairsessential_dlt(cs) (PoseLib backend)one-stepVGC
Rotation from vector pairs (R·a ≈ b)kabsch(cs)one-stepVGC
Mean of a set of rotationschordal_mean(Rs)one-stepVGC
Focal lengths from plane homographieszhang_intrinsics(Hs[, pitch])one-stepVGC
Line through 2D points, with its covariancetls_line(points)one-stepVGC
The point nearest to N lines (origin => direction pairs)nearest_point(lines)one-stepVGC
Ellipse through 2D points (algebraic, always an ellipse)direct_ellipse(points)one-stepVGC
A pure-bending height field through scattered heights (point => height pairs, the plane dropped)HeightField(nodes, points .=> heights; smoothing)one-stepVGC
Normalize points for a solve (centroid, or a known centre)AffineMap(HartleyNormalization(; center), points)normalizationVGC
Normalize a correspondence set for a model classCorrespondenceNormalization(M, cs; center)normalizationVGC
Store image points resolution-independently (pools)AffineMap(DiagonalNormalization(size))normalizationVGC
Homography from a 4-point samplesolve(Homography4pt(), cs, idx)minimalVGC
Radially distorted homography from 5 pointssolve(Homography5ptRadial(), cs, idx)minimalVGC
Fundamental matrix from a 7-point samplesolve(Fundamental7pt(), cs, idx)minimalVGC
Essential matrix from 5 bearing pairssolve(Essential5pt(), cs, idx)minimalVGC
Absolute pose from 3 point–bearing pairssolve(P3P(), cs, idx)minimalVGC
Circle through 3 pointssolve(Circle3pt(), points, idx)minimalVGC
Ellipse through 5 pointssolve(Ellipse5pt(), points, idx)minimalVGC
Radial camera from 5 plane–pixel pairssolve(RadialCamera5pt(; center), cs, idx)minimalVGC
A model from contaminated correspondencesfind_homography, find_absolute_pose, find_radial_camera, find_circle, find_ellipse, …find (RANSAC)RVG
Radial camera of one board, whitened iterationsfit_radial_camerafitRVG
Division camera (focal and distortion) from boardsfit_division_camera (over division_camera_step)fitRVG
A camera model re-expressed in another family (a lens family, a SplineLens and its forward spline) over a regionfit_camerafitRVG
Line through points carrying covariancesfit_linefitRVG
A model refined from a given one (no scorer: the caller's scale or width)refine_homography, refine_absolute_pose, refine_circle, refine_ellipse, …refineRVG
Robot–world / hand–eye from a guessrefine_robot_world_hand_eyerefineRVG

The kind fixes how a call can fail: an algorithm is one deterministic computation and can only be degenerate; a fit can fail to converge; a find is randomized; a refine can end in a local minimum.

find_* and refine_*

Every RVG find_* is RANSAC's sampling around one local-optimization step: it scores hypotheses and ORIGINATES a scale (its result's noise_scale). Its refine_* starts from a given model (guess first, then the data as the find_* takes them) and estimates no scale: it runs no scorer, and its robust loss — optimization_strategy = Triggs{Shape} (the default, Welsch: one robustified LM, no reweighting cycles; an Irls{Shape} is refused) or nothing for least squares — runs at the caller's scale (a number, or an upstream result such as the find_*'s) times the loss's efficiency_constant, or at a given width. It returns the refined model with per-datum loss weights and the scale it ran with. The two take one family of AbstractOptimizationStrategy types under two keywords (local_optimization_strategy on a find_*); the RANSAC-family seeded step, with a scorer and its consensus set, is VisualGeometryToolkitEstimation's locally_optimize.

The robust-loss family

One unified family of loss SHAPES (AbstractLossShape) replaces per-package loss-function copies. A loss shape is a normalized scale family ρ_w(r) = w²·ρ₁(r/w): every member shares the quadratic regime at the origin, and its scale parameter w, the loss_width, is the residual scale at which it leaves that regime (LOSSES.md at the repository root states the normalization). The shapes: GaussianShape, WelschShape, GemanMcclureShape, CauchyShape, SmoothTLSShape, TLSShape, HuberShape, and the Barron α-family dial (BarronShape). Traits classify them (liftable, bounded). A shape is paired with the width it runs at by deploy — loss_width = efficiency_constant · ŝ, the width as a multiple of the noise scale — and the resulting DeployedLoss answers the one-argument verbs that read that width: lift_weight, lift_rho, lift_conjugate, lift_cost, lift_zblock. decision_width converts a decision threshold (the residual where a method's inlier/outlier decision flips) into each shape's native width, and is_map_inlier is the MAP decision on a posterior membership weight.

The GNC surrogate facet supplies the annealed closed form (gnc_tls_weight) and the engine vocabulary (gnc_weight, gnc_target, gnc_mu0), all dispatched on the gnc_surrogate trait.

The composable RANSAC

A robust search is a composition of three parts, each behind a contract this package owns: a problem (data, residuals, minimal solver, weighted refit), a scoring (which hypothesis wins, and its consensus set), and a local optimization (how the winner is refined). VisualGeometryToolkitEstimation's loop calls only the contract verbs, so a scorer or an optimizer from any package plugs in as a keyword:

using VisualGeometryToolkitEstimation, LocalOptimizationDoneRight
using VisualGeometryToolkitCore: StudentTUniformScoring, JeffreysPrior, FlatLabelPrior
find_homography(cs)       # core default: the class's scorer (MSAC) + Irls{TLSShape} at its decision point
find_homography(cs; scoring = StudentTUniformScoring(HomographyProblem, 20.0;   # outlier half-width, pixels
                        scale_prior = JeffreysPrior(), label_prior = FlatLabelPrior()),
                    local_optimization_strategy = HQ{WelschShape}())                     # an optimizer (LODR)

Every dispatch is static: the composed workspace is typed on the scorer's and the optimizer's workspaces, so one RANSAC call compiles per (problem, scoring, local optimization).

The problem protocol (AbstractConstraintProblem): data_size, codimension, minimal_sample_size and constraint_with_jacobians, from which the signed whitened_residual and the distances mahalanobis_distances! are derived (a problem may supply a faster residual_context / mahalanobis_distance path); optionally solver_covariance for predictive scoring; and the weighted refit refine!(R, problem, θ, w) on refine_workspace(P, n) that local optimizations call.

The scoring contract (AbstractScoring). A scorer implements four verbs:

verbmeaning
scoring_workspace(scoring, n, d_g)its scratch, built once per composed workspace
score!(W, scoring, scores, residuals, n; sample, bound)the score of one model (higher is better)
inlier_count(scoring, W)the size k* of the consensus set of the last score!
consensus_order(scoring, W)an order whose first k* entries are the consensus set

Optional verbs have defaults: is_predictive and scored_model (a scorer that scores a model with its covariance), scale_prior (Jeffreys), outlier_halfwidth (a uniform outlier model, nothing by default), decision_boundary with its static trait has_decision_boundary (the decision point a width-free optimizer follows), score_bound (a bounded-sum scorer may stop a score early) and check_workspace. The derived verbs are stated once and never overridden: consensus_s2, consensus_set (the ConsensusSet, the inlier set and its Student-t scale that local optimization starts from), inlier_probabilities! and score_model!, the one scoring path over a ScoreBuffers. with_width(scoring, w) and width_axis(scoring) rebuild a scorer at another width on its native axis.

The baseline scorers live here: RansacScoring (inlier count) and MsacScoring (truncated quadratic). MsacScoring(problem; threshold = τ) is a loop scorer at a threshold in the problem's residual unit; the width-free MsacScoring() is the grid family that pool selection sweeps over a width grid. Both are AbstractThresholdScorings: a family at a threshold supplies only its per-point residual_quality (and, where it is proven, its score_bound) and inherits the one threshold score! with its consensus set, so a downstream loss-width family shares the loop.

The local-optimization contract (AbstractOptimizationStrategy):

lo_workspace(::Type{P}, ::Type{T}, lo, n) -> L     # built once; default nothing
locally_optimize!(L, lo, problem, θ, cs::ConsensusSet, buf::ScoreBuffers, scoring)
    -> lo_estimate(θ′, code, rule; iterations, residuals_current)

On entry residuals(buf) holds θ's residuals and cs is the consensus set of the score that just ran; the optimizer may overwrite the buffers and call score_model!, but never scores for acceptance (the loop re-scores and keeps the incumbent). A width-carrying optimizer has a width mode, read by lo_width and set by with_width(lo, w): nothing follows the scorer's decision_boundary, EfficiencyConstant(m) anchors the width at m times the consensus scale, and LossWidth(w) is an absolute width. loss_at is the one resolution of a mode into a DeployedLoss, and check_composition refuses, once at entry, an optimizer that follows a scorer with no threshold. The label trait scale_interface is derived from the mode (FollowsScorer, ConsensusAnchored, FixedScale).

External refiners. A strategy that runs outside the loop (a third-party solver) declares RefitFamily(lo) = ExternalRefit() and implements external_workspace(lo, problem, frame, scoring), optionally prepare_external!, and refine_external!(ws, lo, problem, θ, width, scoring) -> θ′ | nothing, a pure model-to-model refine at an absolute LossWidth (a FixedS2(s2) noise scale is the width √s2 unless the refiner reads it itself). In-loop strategies are NativeRefit(), the default.

The chart-rows contract (rows_provider, lift_init, lift_refresh!, lift_jacobian!, lift_retract, lift_model, lift_valid, lift_rows) — what a lifted local optimizer reads of a chart problem: its whitened rows, their Jacobian and per-point norms in a RowsWorkspace. Problems provide it (VisualGeometryToolkitEstimation); the half-quadratic lifts and their continuation schedules that consume it are LocalOptimizationDoneRight's.

Pool selection over a benchmark pool record (Pools.PoolPair): best_pool_model(scoring, pair, R) is the per-pair argmax of score! over the stored models; select_on_grid!(idxs, P, scoring, grid, staged) the selections at every width of a grid, after selection_staging(scoring) and stage_selection(key, pairs, residuals; backend). The generic method is a CPU fallback (per column with_width, then best_pool_model); a grid family with device kernels (RANSACScoringDoneRight) implements its own staging and selection.

Width axes. One name per width quantity, each a value carrier and, bare, an axis tag: EfficiencyConstant, LossWidth and OutlierHalfwidth (a scorer's width, never an optimizer's). width_axis(name) / width_axis_name(axis) map the persisted names, and to_native / native_map convert an efficiency constant into an axis's native width at the same decision point.

Configuration tags and quality gates. A TOML tag that selects a type goes through a TagRegistry, whose tags are snake_case of the type name with the family's suffix removed (TLSShape → "tls", StudentTUniform → "student_t_uniform"); a renamed tag fails with its successor's name. The quality gates (test_quality_gates) check every registry, every config tag, the stack dependency allow-list, and that a package adds methods to another stack package's functions only through that owner's CONTRACT_GENERICS. The conformance helpers test_scoring_contract, test_local_optimization_contract and test_constraint_problem (loaded with Test) check an implementation.

Interfaces and loops

  • Scoring/LO interface hierarchy (AbstractScoring, AbstractOptimizationStrategy, RefitFamily, AbstractWeightPolicy) — the type hierarchy of the contracts above.
  • Generic block-coordinate-descent loop (block_coordinate_descent!, AbstractBlockCoordinateMethod and its extension verbs) — the model/nuisance/weights loop (EM, IRLS, GNC, Barron-adaptive) stated once, extended by downstream methods.
  • Chart-rows contract (rows_provider, lift_rows, RowsWorkspace) — what a lifted local optimizer reads of a chart problem: its whitened rows, their Jacobian and per-point norms. The lifts and their continuation schedules are LocalOptimizationDoneRight's.
  • The one LM (lmsolve_chart!, LmStops; static_lm, StaticLmStops) — the stack's Levenberg–Marquardt: NLLSsolver (Marquardt's DᵀD damping by default, LevenbergDamping opt-in) through ONE adapter, lmsolve_chart!, on a linearization state's residual_rows! / residual_jacobian_rows! (a ManifoldLmWorkspace keeps the problem and the solver's internal data), the same robustified per datum, or a multi-block LmProblem (the bundles: heterogeneous variables and residual blocks, each with its own robustifier). Its stop settings have ONE owner, LmStops (configs/default.toml [lm]); an LmProblem's damping is the problem's own (its kept cache is built for it: the default stops take it, explicit stops of another damping are refused). Every solve has ONE success rule (Core 0.11.0): a tolerance stop (ftol, xtol, xtol_rel) is converged, and the consecutive-rejection cap is judged by the stationarity postcondition at the returned point (is_stationary), a cost below the final point's rounding ((16ε)²·Σᵢ sᵢ² over the residuals' operand scales, floored by the data's residual_resolution²) an exact fit. A kernel's fixed-N solve is the one device LM, static_lm, under StaticLmStops and its own rule (stationary and accepted). No package calls NLLSsolver's solver API directly: check_duplication fails it. The Schur complement (NLLSsolver pull request #60, still open) is used when the loaded NLLSsolver has it (nlls_features); see "The Schur complement of the LM driver" in Getting Started.

Model manifolds and covariance

Model manifolds (Manifold: EssentialManifold5, FundMatManifold7, HomographyManifold8, RigidManifold6, …) provide local parameterizations of the model manifolds with first-order covariance transport between charts and the ambient space (transform_covariance, the ambient chart EuclideanManifold(ch)); implicit_covariance derives the solver covariance by the implicit function theorem — of a minimal solve, and of the whitened least-squares estimator on an overdetermined sample. Image-domain confidence regions (confidence_ellipse, epipolar_band, LineConfidenceBand) turn those covariances into point-transfer ellipses and Hartley–Zisserman epipolar-line bands (Hartley and Zisserman, 2003).

API reference

See the Robust Estimation API for the complete reference.