Line Fitting

RANSAC Problems

Two RANSAC problem types for 2D line fitting, distinguished by their noise model:

VisualGeometryToolkitEstimation.LineFittingProblem — Type
LineFittingProblem{T} <: AbstractRansacProblem

Plain RANSAC problem for estimating a 2D line from points with per-point covariances.

Residuals are standardized: r_std[i] = (n⊤pᵢ + d) / √(n⊤Σᵢn), so all points contribute on a comparable scale regardless of their covariance shape.

Supports LO-RANSAC via refine!(ws, problem, θ, weights) (θ unread: a linear problem's step): the covariance-weighted line of fit_line with each point's weight wᵢ/σᵢ² — the local optimizer's robust weight times its inverse variance along the normal — seeded by the w-weighted total-least-squares normal. A zero weight drops the point.

Constructors

LineFittingProblem(pts::AbstractVector{<:Uncertain{<:Point2}})
LineFittingProblem(pts::AbstractVector{<:Point2})  # identity covariances

Solver Details

  • Minimal sample: 2 points (returns FixedModels{1, Line2D{T}})
  • Model type: Line2D{T} (Hesse normal form)
  • Residual: Standardized orthogonal distance
  • LO-RANSAC: refine!(ws, p, θ, weights) — the weights-weighted fit_line step, θ unread
source
VisualGeometryToolkitEstimation.InhomLineFittingProblem — Type
InhomLineFittingProblem{T} <: AbstractRansacProblem

Inhomogeneous line fitting: y = a + b·x, 2 parameters, scalar residual.

The simplest possible RANSAC problem for debugging and testing the covariance-aware pipeline. No standardization, no per-point covariances.

Model

  • SVector{2,T}: (a, b) where y = a + b·x
  • Residual: r_i = y_i - a - b·x_i (scalar, raw)
  • Residual DOF: 1
  • Model DOF: 2
source

LineFittingProblem uses Hesse normal form (Line2D{T}) with per-point covariance shapes (standardized residual). InhomLineFittingProblem is the inhomogeneous y = a + b·x form with errors only in y.

Robust Linear Least Squares

fit_linear is the robust coefficient vector x of y ≈ A·x (rows with gross outliers): a reweighted least squares under a loss shape at one fixed width, efficiency_constant × scale from the caller's scale (or its width), with optional fixed prior row weights — the scalar-residual sibling of fit_rotation.

VisualGeometryToolkitEstimation.fit_linear — Function
fit_linear(A, y[, prior]; optimization_strategy, scale | width, tol)
    -> FitResult{Vector{Float64}, FitMetadata}

The robust coefficients x of y ≈ A·x (A an m × n matrix, y an m-vector), with a fraction of the rows gross outliers. A fit — it seeds itself with the prior-weighted least squares — iterating a reweighted least squares at ONE loss width: residuals rᵢ = yᵢ − aᵢᵀx, the weights of the strategy's loss at that width, times the prior, and the weighted least squares. The width is fixed by the caller's scale input and never re-estimated.

  • prior — fixed non-negative row weights (a bootstrap's resampling counts, a previous fit's weights); a zero weight drops its row. Default all ones.
  • optimization_strategy — the robust weighting, an Irls{K} strategy (its loss K, its efficiency constant and its max_iter; default configs/default.toml [fit_linear] optimization_strategy, Huber), or nothing for the plain prior-weighted least squares. At most max_iter iterations after the seed: Irls{HuberShape}(max_iter = k) makes k + 1 weighted solves.
  • scale | width — with an Irls strategy, EXACTLY ONE of: scale = σ (the residuals' noise scale, in y's units), scale = result (an upstream robust result's noise_scale), or width = w (the loss width itself). The width is w, or c · σ with c the strategy's efficiency constant, by default the shape's at codimension 1 (efficiency_constant(K, 1): Huber 1.345); a shape with none (TLS) needs the strategy's or a width. Neither, both, or one given with optimization_strategy = nothing is an ArgumentError.
  • tol — converged when an iteration moves x by less than tol · max(1, ‖x‖∞) in the max-norm (default configs/default.toml [fit_linear]).

The least squares is a column-pivoted QR, so a column that no row with weight reaches (an unsupported basis function) gets a basic solution's value, not an error; drop such columns before the call when their value matters.

retcode_symbol(result) is :converged, :max_iterations, :solved (least squares), or :degenerate when fewer rows keep a positive weight than there are columns. n is the support (the rows of positive solve weight) and rms the weight-weighted root mean square residual over the rows, √(Σ pᵢwᵢrᵢ² / Σ pᵢwᵢ). The metadata (FitMetadata) carries the weights, the residuals, the scale record and the loss width.

source
VisualGeometryToolkitEstimation.FitMetadata — Type
FitMetadata{L, W}

FitResult metadata of the reweighted fits fit_linear, fit_rotation and fit_rigid_alignment, all at the returned estimate (L the optimization_strategy's type, Nothing for least squares):

  • weights::W — the loss weight ρ′(r²) of every datum, normalized to a maximum of 1 (IrlsWeights); a lazy all-ones vector for least squares (BinaryWeights). The solve's weight of a datum is its prior times this.
  • residuals — every datum's residual at the estimate, in the fit's unit: y − A·x (fit_linear), the angle ∠(R·aᵢ, bᵢ) in radians (fit_rotation), the distance ‖bᵢ − (R·aᵢ + t)‖ in the points' unit (fit_rigid_alignment).
  • scale, scale_source — the scale record (noise_scale(result), scale_source(result)), in the residuals' unit: the scale given (ScaleGiven, ScaleUpstream), or NaN and ScaleNone for least squares or a width-only fit.
  • loss_width — the loss width the weights were computed at (NaN for least squares).
source