Geometric perception—whether tracking a robot's pose, reconstructing a 3D scene, or fitting an ellipse to an object—relies on finding mathematical models that explain spatial data. The classical tool for this is least-squares estimation. However, least-squares possesses a fatal flaw: it assumes errors follow a symmetric, Gaussian distribution.
In the real world, sensor glitches, occlusions, and incorrect data associations produce outliers—data points that do not belong to any valid model. Because least-squares penalizes errors quadratically, a single extreme outlier can exert an infinite "pull," dragging the fitted model completely away from the true geometry.
To solve this, a major research direction focuses on making geometric fitting robust to outliers. The core challenge is a chicken-and-egg problem: to find the correct geometric model, we must reject the outliers; but to identify which points are outliers, we must already know the correct model. Modern techniques break this cycle using five core mechanisms.
1. Local Consistency and Preference Spaces
One way to break the chicken-and-egg cycle is to look at the data locally. While global outliers are chaotic and scattered, true inliers are locally coherent and adhere to low-dimensional structures.
Szlam et al. and Zhang et al. leverage this intuition for hybrid linear modeling (fitting multiple subspaces simultaneously). They use a scale-invariant metric called Jones' $\beta_2$ numbers to automatically determine the optimal local neighborhood size for every point. By fitting "local best-fit flats" and minimizing a global $\ell_1$ error—which penalizes outliers linearly rather than quadratically—the authors isolate underlying linear structures without being distorted by background noise.
Another perspective is to map data points into a "preference space" based on how well they fit a set of candidate models. As Zhang et al. demonstrate, when residuals are quantized into a preference space, inliers that belong to the same geometric structure naturally cluster together, while outliers form distinct, unstructured distributions. Minimizing energy over this space allows for clean outlier rejection. Similarly, Lai et al. construct hypergraphs where hyperedges connect variable numbers of points based on geometric consensus, transforming model fitting into a hypergraph partitioning problem that naturally isolates noise.
Least-Squares (Quadratic Penalty):
Inliers: |---*---| (Small penalty)
Outlier: |---------------------------------------*| (Massive penalty, pulls model)
L1 / Robust Penalty (Linear/Bounded):
Inliers: |---*---| (Small penalty)
Outlier: |---------------------------------------*| (Bounded penalty, ignored)
2. Probabilistic Soft-Assignment and Mixture Models
Instead of making hard, binary decisions about whether a point is an inlier or an outlier early on, probabilistic approaches treat outlier-ness as a continuous spectrum.
For instance, when fitting complex shapes like ellipsoids, traditional algebraic distance minimization fails under heavy noise. Zhao et al. reframe the problem by modeling the ellipsoid as a Gaussian Mixture Model (GMM) and introducing an adaptive outlier score within an Expectation-Maximization (EM) framework. The outliers are effectively modeled as a uniform background distribution, allowing the EM algorithm to progressively down-weight them as the ellipsoid parameters converge.
In a similar vein, Babacan et al. move from deterministic optimization to Bayesian inference for subspace clustering. By placing sparsity-inducing priors on the data representation, their framework automatically infers both the number of subspaces and their dimensionalities while treating heavy noise and missing data as latent variables. For curved geometries, Wu et al. use Jensen-Shannon divergence to measure the global compatibility of edge arcs, applying Singular Value Decomposition (SVD) for adaptive co-clustering to robustly detect ellipses amidst heavy occlusion and background clutter.
3. Deep Learning as a Differentiable Filter
Classical robust estimators like RANSAC (Random Sample Consensus) rely on non-differentiable random sampling loops to find an outlier-free subset. This scales poorly when the outlier ratio is high. Modern approaches integrate deep learning to act as an intelligent, differentiable filter that learns global context.
Ranftl et al. show how a neural network can be trained to predict weights for image correspondences. These weights are then fed into a weighted least-squares solver to estimate a fundamental matrix. Because the entire pipeline is differentiable, the network directly learns to identify "good" matches and reject outliers based on the global context of the image.
[Noisy Input Matches] ---> (Deep Neural Network) ---> [Predicted Weights] ---> (Weighted Least Squares) ---> [Robust Geometry]
To avoid the numerical instability of traditional geometric solvers within deep networks, Dang et al. introduce an eigendecomposition-free loss function. By minimizing the fit of ground-truth eigenvectors directly against predicted matrices, the network maintains high accuracy in 3D pose estimation even when a vast majority of input correspondences are outliers. This allows single-stage architectures, such as the one proposed by Fua et al., to directly regress 6D object poses from candidate correspondences without needing a separate, fragile PnP-RANSAC stage.
Hybrid architectures also use deep learning to narrow down the search space before geometry takes over. Wang et al. use a bounding-box detector to isolate potential ellipse regions, filtering out environmental noise before applying geometric constraints. For camera calibration, Lee et al. combine raw pixels with detected line segments, using a neural parser to ignore irrelevant or accidental lines that do not converge at true vanishing points.
4. Certifiable Optimality and Estimation Contracts
While heuristics and deep networks work well in practice, safety-critical applications like robotics demand mathematical guarantees. If an algorithm outputs a geometric estimate, we must be certain it was not fooled by a clever configuration of outliers.
Yang et al. address this by reformulating robust estimation as a sparse polynomial optimization problem. Using a fast first-order solver (Douglas-Rachford Splitting), their framework provides a "certificate" of global optimality. If the certificate holds, the user is guaranteed that the algorithm has found the globally optimal geometric solution, completely bypassing the local minima that plague traditional non-linear solvers.
Expanding on this theoretical foundation, Carlone establishes "estimation contracts." These are rigorous mathematical bounds derived from algorithmic robust statistics. They define the exact conditions—such as the maximum permissible outlier ratio (which can safely exceed 50%) and the spatial distribution of noise—under which an algorithm is guaranteed to recover the exact ground-truth geometric models.
5. Combinatorial and Quantum Formulations
When a dataset contains multiple geometric structures mixed with outliers, the problem becomes a complex combinatorial puzzle: which points belong to which model, and which belong to none?
To tackle this, researchers have begun mapping multi-model fitting to adiabatic quantum computers. Farina et al. formulate multi-model fitting as a "disjoint set cover" problem, translating it into a Quadratic Unconstrained Binary Optimization (QUBO) objective. By leveraging quantum annealing, the system explores the massive combinatorial solution space simultaneously, outperforming classical heuristics in separating valid structures from noise.
Building directly on this, Pandey introduces R-QuMF, which explicitly incorporates outlier rejection into the QUBO formulation by framing the task as a maximum set coverage problem. This allows quantum annealers to solve motion segmentation and 3D reconstruction problems without needing prior knowledge of the number of models, demonstrating extreme resilience to high outlier ratios.
Key Foundational Work
Randomized hybrid linear modeling by local best-fit flats (2010) — contributed 1 concept elements to this direction.
Probabilistic Low-Rank Subspace Clustering (2012) — contributed 1 concept elements to this direction.
Hybrid Linear Modeling via Local Best-Fit Flats. (2012) — contributed 1 concept elements to this direction.