IRLS & Posterior Weighting
Generic Block-Coordinate-Descent Loop
The generic loop is VisualGeometryToolkitCore's block_coordinate_descent!, dispatching on AbstractBlockCoordinateMethod. Concrete methods plug in by extending a small set of interface methods (all declared public): init_state!, update_model!, update_residuals!, update_nuisance!, update_weights!, post_iteration!, stopping_criterion (a VGC StoppingCriterion value, composed with |; a new criterion implements stop_reason), and block_coordinate_result. Every local-optimization strategy in this package plugs into the block_coordinate_descent! loop through this interface, and a new one does the same.
The RANSAC LO refinement uses the loop via PosteriorIrlsMethod (the iteration of Irls, posterior_irls!; downstream, LocalOptimizationDoneRight's Student-t + uniform IRLS). Its model block is a bound, named update — WeightedRefine (the problem's weighted refine!, the default) or KeepModel (the model held: EM of the noise model on fixed residuals, stopping on the mixture NLL) — its stop rule a value too — NoImprovementStop (the incumbent's cost, returning the incumbent: the RANSAC local optimization's) or ParameterChangeStop (the relative change of the problem's change_parameters, returning the last iterate: fit_division_camera's) — and its state a PosteriorIrlsState built from a seeded posterior and its residual buffers.
VisualGeometryToolkitEstimation.PosteriorIrlsMethod — Type
PosteriorIrlsMethod(refine_ws, model_update = WeightedRefine(), stop = NoImprovementStop())The block-coordinate method of the posterior-weight iteration (VGC block_coordinate_descent!): the model block is model_update(refine_ws, problem, θ, robust_weight(state.rws)) (WeightedRefine or KeepModel); the residuals, nuisance and weight blocks are the likelihood's; stop the stop rule and the result (NoImprovementStop: the incumbent, the RANSAC local optimization's; ParameterChangeStop: the last iterate). refine_ws is the workspace the model update hands refine! (nothing when the model is held). The state is a PosteriorIrlsState built from a seeded posterior and its residual buffers — by the consensus seed (posterior_irls!) or by the caller. A MixtureEmConfig states model_update and stop in its table.
VisualGeometryToolkitEstimation.PosteriorIrlsState — Type
PosteriorIrlsState(rws, residuals, best_residuals, θ₀, cost)The state of a PosteriorIrlsMethod run: the seeded posterior rws, the residual buffer residuals (the model's residuals at θ₀, refilled by update_residuals!) and the incumbent's best_residuals, with θ₀ the incumbent at cost. The buffers are the caller's — the local optimizer's workspace (posterior_irls!) or any caller's own.
VisualGeometryToolkitEstimation.WeightedRefine — Type
WeightedRefine()The model update of a PosteriorIrlsMethod that REFITS the model under the current weights: refine!(refine_ws, problem, θ, weights) — the problem's own weighted solve (its chart LM). The RANSAC local optimization's, and the default.
VisualGeometryToolkitEstimation.KeepModel — Type
KeepModel(tol)The model update of a PosteriorIrlsMethod that HOLDS the model: it returns θ unchanged, so an iteration moves only the noise model (the nuisance, then the E-step) — EM of the Student-t + uniform mixture on the model's fixed residuals. The iteration's cost is then the mixture negative log-likelihood (mixture_nll), which that EM never raises, and the loop converges once an iteration lowers it by no more than tol relative.
VisualGeometryToolkitEstimation.LossPlainWeights — Type
LossPlainWeights(rws::PosteriorWeightState, n::Int, loss::DeployedLoss)
LossPlainWeights(rws::PosteriorWeightState, n::Int, loss::DeployedLoss, consensus)Frozen-scale plain-IRLS likelihood adapter for Irls{K}: ONE weight policy generic over the loss, replacing the former per-loss Welsch/Geman–McClure/Huber/L2 quadruplet whose bodies differed only in the weight formula — which is exactly VisualGeometryToolkitCore.weight on the shape. Reuses the PosteriorWeightState buffers (sq_distances, w). The loss carries its OWN squared width (sq_loss_width, Huber: elbow²), committed at construction from the seed partition's Student-t scale and frozen — update_nuisance! is a no-op.
Two rules hold for every weight it writes:
- a datum whose squared residual is not finite (an out-of-reach point, an infinite Sampson distance, a NaN) weighs 0 under every shape — the shape's own weight there is 1 (the Gaussian) or NaN, either of which would make the cost Σwᵢrᵢ² non-finite and stop the iteration at its seed;
consensus, when given (aBitVectorover the data), restricts the weights to its members: a datum outside it weighs 0 and is no inlier.locally_optimize!(L, ::Irls{GaussianShape}, …)supplies the scorer's consensus set (consensus_mask!): least squares is not robust, so the Gaussian refit sees the inliers only (LO-RANSAC's least squares on the inliers). The 3-argument form has none: every datum weighs its shape's weight.
VisualGeometryToolkitEstimation.StopWhenNoImprovement — Type
StopWhenNoImprovement(patience, first_iteration):converged once patience consecutive iterations have failed to improve the incumbent (iterations_without_improvement), from iteration first_iteration on.
VisualGeometryToolkitEstimation.iterations_without_improvement — Function
iterations_without_improvement(state) -> IntThe consecutive iterations that have failed to improve the incumbent, as StopWhenNoImprovement reads it. The default: a state that keeps only whether the LAST iteration improved (its improved field) counts 0 or 1; a state that counts further adds its method.
VisualGeometryToolkitEstimation.NoImprovementStop — Type
NoImprovementStop()The stop rule of a PosteriorIrlsMethod that ends the iteration once an iteration fails to lower the INCUMBENT's cost (StopWhenNoImprovement: from the second iteration under WeightedRefine, the cost Σ wᵢrᵢ²; from the first under KeepModel, the mixture NLL at its tol), and returns the incumbent. The RANSAC local optimization's rule, and [mixture_em]'s. TOML tag "no_improvement".
VisualGeometryToolkitEstimation.ParameterChangeStop — Type
ParameterChangeStop(rtol)The stop rule of a PosteriorIrlsMethod that ends the iteration once an iteration moves the parameters by less than rtol RELATIVE, ‖p − p_old‖ / ‖p_old‖ < rtol with p the problem's change_parameters of the iterate, and returns the LAST iterate. For a fixed-point iteration with no fixed objective to track — one that re-linearizes its residuals at every iterate (fit_division_camera), where the cost of one iteration is not comparable to the next. TOML tag "parameter_change".
VisualGeometryToolkitEstimation.StopWhenParameterChangeLess — Type
StopWhenParameterChangeLess(rtol):converged once the last iteration moved the problem's change_parameters by less than rtol relative to their previous value. The criterion of ParameterChangeStop.
VisualGeometryToolkitEstimation.change_parameters — Function
change_parameters(problem, θ) -> AbstractVectorThe parameters of the model θ that ParameterChangeStop compares between iterations — a problem's own measure of how far an iteration moved its model (fit_division_camera's: the focal length and the division coefficients, pixels). The default is the model's parameter_vector.
Classifying a held model's residuals
Regression and classification apart: whatever fitted the model, its residuals are FIXED here. The fit's weighting — its Student-t + uniform E-step, any scorer with a uniform outlier model (outlier_halfwidth), e.g. VisualGeometryToolkitCore's StudentTUniformScoring; a fit takes no scoring — seeds the mixture from its consensus set, EM fits it with the model held, and each residual's MAP label is VisualGeometryToolkitCore's is_map_inlier of its posterior. The result records the posteriors as its weights (PosteriorWeights, so inlier_mask(result) is the MAP labels) and the E-step's ŝ as its noise_scale (ScaleEstimated).
VisualGeometryToolkitEstimation.fit_residual_mixture — Function
fit_residual_mixture(distances; weighting, model_dof, config = MixtureEmConfig())
-> Union{FitResult{PosteriorWeightState, ResidualMixtureMetadata}, Nothing}Fit the Student-t + uniform mixture to a held model's distances (≥ 0, unsquared: the Mahalanobis distances, the residual NORMS of a codimension-2 observation — what mahalanobis_distances! fills) and classify each one. A negative entry is a signed residual, not a distance, and is an ArgumentError (supply abs.(r)).
weighting is the EM's weighting, the Student-t + uniform E-step: a scorer with a uniform outlier model (outlier_halfwidth) whose per-point scores are the squared residuals, as a sort-and-sweep scorer's are (VisualGeometryToolkitCore's StudentTUniformScoring). A fit takes no scoring: the former positional scoring argument and a scoring keyword are an ArgumentError naming weighting (the robust-estimation contract, since 0.9).
- The weighting takes their consensus set —
score!at its codimension and scale prior — and the set's Student-t (ŝ² at the residual dof(k* − model_dof)·d_g) seeds the posterior (PosteriorWeightStateon the weighting'sconsensus_order). - EM with the model held —
config.model_updatemust beKeepModelandconfig.stopNoImprovementStop(a held model's parameters never move) — under VisualGeometryToolkitCore'sblock_coordinate_descent!: each iteration the nuisance parts (config.nuisance) then the E-step, untilconfig.stoporconfig.max_iter. - Each residual's MAP label: inlier iff
is_map_inlierof its posterior.
model_dof counts the parameters the held model spent per correspondence (a bundle's free parameters over the codimension, rounded up). Returns nothing when the partition is too thin to carry a scale.
The result: estimate the fitted mixture, a PosteriorWeightState — its s_hat_sq, student_t_dof and inlier_prior, and per residual its posterior inlier_weight(estimate)[i], whose MAP label is VisualGeometryToolkitCore's is_inlier(estimate, i). The contract's record (metadata, a ResidualMixtureMetadata): weights(result) the posteriors (PosteriorWeights, so inlier_mask(result) is the MAP labels) and noise_scale(result) = ŝ, estimated (ScaleEstimated). n is the support, the distances of positive weight, and rms the weight-weighted root mean square √(Σwᵢrᵢ² / Σwᵢ) (the MAP inliers' count is count(inlier_mask(result))); retcode and iterations the EM's.
VisualGeometryToolkitEstimation.ResidualMixtureMetadata — Type
ResidualMixtureMetadataThe metadata of a fit_residual_mixture result: the mixture's negative log-likelihood nll of the distances at the fitted noise model (the quantity the EM lowered), each distance's posterior inlier probability weights (PosteriorWeights: inlier_mask(result) is the MAP rule, posterior > ½; a posterior below eps() is an exact 0) and the E-step's scale scale = ŝ (the distances' unit, a LINEAR scale; scale_sourceScaleEstimated), read by weights(result) and noise_scale(result).
VisualGeometryToolkitEstimation.MixtureEmConfig — Type
MixtureEmConfig(; model_update, nuisance, stop, max_iter)The EM of the Student-t + uniform mixture: the model update (WeightedRefine or KeepModel(tol), whose tol is the relative mixture-NLL decrease below which the EM has converged), the nuisance parts' update policies nuisance = (; scale, inlier_prior, nu) (each Estimated(), or held: VisualGeometryToolkitCore's FixedS2(s2), FixedPrior(π) and FixedNu(ν), and for ν also ConsensusDof() — held at the consensus seed's posterior-predictive dof), the stop rule stop (NoImprovementStop: the incumbent's cost, returning the incumbent; ParameterChangeStop(rtol): the relative change of the parameters, returning the last iterate) and the iteration cap. Every default reads the [mixture_em] table of configs/default.toml (every key is required there: none is defaulted in code); mixture_em_from_toml loads a caller's table and config_dict writes one back.
VisualGeometryToolkitEstimation.mixture_em_from_toml — Function
mixture_em_from_toml(table; section = "mixture_em") -> MixtureEmConfigBuild a MixtureEmConfig from its TOML table: present keys override, absent keys inherit configs/default.toml's [mixture_em], and an unknown key, tag or tag field is an ArgumentError.
Student-t + Uniform Mixture
The inlier likelihood of the posterior-weight iteration and of direct posterior weighting calls: the predictive Student-t density obtained by marginalising the inlier scale σ² under the scorer's prior (scale_prior, Jeffreys by default), against a uniform outlier density of half-width outlier_halfwidth(scoring).
A VisualGeometryToolkitCore PosteriorWeightState is seeded from a consensus set:
- In the RANSAC loop:
consensus_posteriorsquares the seed model's residuals (already in the score buffers) and seeds(ν₀, ŝ²₀)from the scorer'sconsensus_orderandinlier_count— no re-score, no sort. - Residuals only:
fit_residual_mixturescores the residuals once with the scorer and seeds from its consensus set. The outlier half-width is the scorer's; a scorer without one is refused (required_outlier_halfwidth).
consensus_s2! gives the consensus set's scale alone — the scale a consensus-anchored loss runs at — for a refiner outside the loop.
PosteriorLikelihood updates the three nuisance parts — the scale, the inlier prior and the Student-t dof — each under its policy: Estimated(), or held at a value (VisualGeometryToolkitCore's FixedS2(s2), FixedPrior(π), FixedNu(ν) and ConsensusDof()).
VisualGeometryToolkitEstimation.PosteriorLikelihood — Type
PosteriorLikelihood(rws::PosteriorWeightState, n::Int;
scale_update = Estimated(), prior_update = FixedPrior(inlier_prior(rws)),
nu_update = Estimated()) <: NormalizedWeightPolicyLikelihood adapter for block_coordinate_descent!. Wraps a VisualGeometryToolkitCore PosteriorWeightState with its data size n so the generic block_coordinate_descent! loop can call update_nuisance! / update_weights! without problem-specific detail.
The nuisance is a composite block of three parts, each with its own update policy (VisualGeometryToolkitCore's): the scale ŝ² (Estimated() or FixedS2(s2)), the inlier prior π (Estimated() or FixedPrior(π)) and the Student-t dof ν (Estimated(), FixedNu(ν) or ConsensusDof()). The defaults are the Student-t + uniform posterior of the RANSAC local optimization: ŝ² and ν estimated, π held at the seeded state's own value (1/2). A held part takes its value at the first nuisance update.
VisualGeometryToolkitEstimation.consensus_posterior — Function
consensus_posterior(L::LoBuffers, problem, cs::ConsensusSet, buf::ScoreBuffers, scoring, a::Float64)
-> PosteriorWeightStateThe Student-t + uniform posterior of the consensus set cs, on the local optimizer's buffers L (its posterior state, re-seeded in place), at the uniform outlier half-width a — the ONE seeding of every local optimization that starts from the posterior (the posterior-weight iteration, posterior_irls!; LocalOptimizationDoneRight's mixture lifts). Freshness contract: cs must come from the most recent score on buf; its consensus order is read from the scorer's workspace. The seed model's residuals are already in buf, so squaring them into the posterior buffer avoids a redundant mahalanobisdistances!() sweep. The Student-t scale contributes one extra DOF on top of the minimal sample size (ν = (k − m)·dg). A datum whose squared residual is not finite weighs 0 (robust weight and inlier posterior: Core's E-step, `seedposterior!`).
VisualGeometryToolkitEstimation.posterior_irls! — Function
posterior_irls!(likelihood, L::LoBuffers, problem, model, cs::ConsensusSet, buf::ScoreBuffers, scoring,
a::Float64; max_iter) -> FitResultTHE posterior-weight iteration of every posterior-IRLS local optimization: seeded from the consensus set cs of the score that just ran on buf (its order reused, no fresh sort) at the uniform outlier half-width a, then VisualGeometryToolkitCore's block_coordinate_descent! with a PosteriorIrlsMethod on the problem's weighted refit. A strategy contributes only its weight policy, likelihood(rws, n) on the seeded posterior state rws:
PosteriorLikelihood: the Student-t + uniform posterior, self-scaling — its seed weights are the posterior's own;- any other policy (a frozen-width loss,
LossPlainWeights) REPLACES the seed weights before the first solve: itsupdate_nuisance!thenupdate_weights!, and the cost re-seeded under those weights.
Under every policy a datum whose squared residual is not finite at the seed weighs 0, and each weight refresh (update_weights!) gives 0 to a datum whose residual has become non-finite, so one out-of-reach point cannot make the seed's cost Σwᵢrᵢ² infinite and stop the iteration there. A refit that puts a datum still weighed out of reach costs Inf and is not accepted.
The best iterate's residuals are handed back to buf (residuals_current = true), so the loop skips a redundant mahalanobis_distances!() sweep.
VisualGeometryToolkitEstimation.required_outlier_halfwidth — Function
required_outlier_halfwidth(scoring) -> Float64The uniform outlier model a posterior-weight fit needs: the scorer's outlier_halfwidth, refused (ArgumentError) when the scorer has none.
VisualGeometryToolkitEstimation.consensus_s2! — Function
consensus_s2!(ws::RansacWorkspace, problem, scoring, model) -> Union{Float64, Nothing}The consensus scale ŝ² of model under scoring: its residuals and score on the workspace's buffers, then the consensus set's Student-t scale at a local optimizer's dof (minimal_sample_size + 1) — the scale a consensus-anchored loss runs at in the native loop (scale_s2(consensus_set(…))), floored at eps.
THE one scale source for engines that cannot run in the native loop (an external refiner's adaptive-width arm): never a loss-width-window plug-in. Returns nothing on a consensus set too thin to carry a scale (k* ≤ m + 1) — the caller bails with no refit call.
The reweighted fits' termination record
Every reweighted fit (fit_linear, fit_rotation, fit_rigid_alignment, fit_rotation_averaging, fit_robot_world_hand_eye) records its stop through one function, as an LM does through VisualGeometryToolkitCore's one LM, lmsolve_chart!; a downstream reweighted loop calls it too.
VisualGeometryToolkitEstimation.irls_termination — Function
irls_termination(converged, closed_form; solve_failed = false) -> (ReturnCode.T, StopRule)THE termination record of the reweighted fits' loop (fit_linear, fit_rotation, fit_rigid_alignment, fit_rotation_averaging, fit_robot_world_hand_eye): its increment tolerance met, (Success, IncrementSize); otherwise a least-squares run (closed_form) is a closed form, (Success, ClosedForm), and a robust one reached its cap, (MaxIters, IterationCap); a weighted solve that could not be solved inside the loop (too few rows of positive weight left) is SciMLBase's (InternalLinearSolveFailed, NoRule).
Public (as Core's lmsolve_chart! records an LM's) so that a downstream reweighted loop records its stops in the same words: BlobBoards' per-blob IRLS (its relative parameter step below rtol is IncrementSize; a singular LU is solve_failed). A stop the loop adds of its own (BlobBoards' shape gate, ShapeGate) stays its own.
Posterior Weighting
Lower-level posterior weighting utilities used by both the RANSAC inner loop and stand-alone EM-style refinement. They are VisualGeometryToolkitCore's toolkit (import them from there): spec arguments (log_two_outlier_halfwidth, model_dof, codimension) are supplied explicitly, and the partition is a consensus order and its size k, as a scorer's consensus_order and inlier_count give them: posterior_weights!, posterior_inlier_probs!, soft_posterior_weights!, update_nu!, next_nu and median_seeded_posterior.
Scale and Mixture Estimation
The scale fit, the Student-t + uniform mixture and its ECM cycle, and the degrees-of-freedom policies the posterior weighting above draws on. They are VisualGeometryToolkitCore's (import them from there): fit_scale, update_scale!, partition_student_t, StudentTMixture, inlier_posterior, posterior_weight, mixture_nll, mixture_ecm!, update_inlier_prior!, sq_distances, and the policies Estimated, FixedS2, FixedPrior, FixedNu and ConsensusDof.
Robust Losses
The loss SHAPES are VisualGeometryToolkitCore's (robust/losses.jl; import them from there); they parameterize the loss-parametric LO strategies (the core Irls{K}; downstream, LocalOptimizationDoneRight's HQ{K} and Gnc{S}), so the loss is what carries the objective. A shape is the ρ profile alone — it gains a width only when deploy(shape, ŝ²; efficiency_constant) composes the scale and the efficiency constant onto it, and it is that deployed loss every function below takes. See the VisualGeometryToolkitCore documentation for the full API.
AbstractLossShape— abstract supertypeGaussianShape— no redescending (plain least squares)HuberShape— linear beyond the elbowCauchyShape— logarithmic penalty (heavy-tailed)WelschShape— exponential penalty; the paper's recipe deploys it as LocalOptimizationDoneRight'sHQ{WelschShape}at its cross-validated scale multiplesGemanMcclureShape— smooth redescenderTLSShape/SmoothTLSShape— truncated least squares, hard and smoothed;Irls{TLSShape}()following the scorer's threshold is everyfind_*pipeline's default (least squares on the inliers)BarronShape— the α-parameterized family
Irls{K} refuses at construction a shape its mechanism cannot run: BarronShape carries its α — the Barron family runs as LocalOptimizationDoneRight's BarronHQ and BarronAdaptive.
Key functions: weight(shape, s, sq_loss_width) (equivalently lift_weight(loss, s) on a deployed loss) and, for the half-quadratic lift, lift_rho / lift_weight / lift_zblock / lift_cost — each on a DEPLOYED loss, which carries the width, so no scale argument is supplied at the call site. An efficiency constant is always the plain multiple, loss_width = efficiency_constant·ŝ, for every shape. decision_width(shape, decision_boundary) converts the residual at which a decision flips (a scorer's decision boundary, which a strategy with no width of its own follows) into the shape's loss width, and takes the bare shape because that is the conversion that produces a width in the first place.
The AbstractLoss family (HuberLoss, CauchyLoss, TukeyLoss, WelschLoss, L2Loss, GemanMcClureLoss, FairLoss) and the AbstractScaleEstimator family (MadScale, WeightedScale, SpatialMadScale) were deleted from VisualGeometryToolkitCore along with the file that held them. The loss shapes above replace the first; scale is estimated from the scorer's consensus set (consensus_s2) rather than by a standalone estimator object. (FixedScale is not retired: it is VisualGeometryToolkitCore's ScaleInterface label of a strategy deployed at an absolute width, LossWidth.)