In geometric computer vision, researchers are often drawn to minimal solvers—algorithms that compute geometric properties using the absolute minimum number of data points required. Classic examples include the 3-point algorithm for absolute pose (P3P) or the 5-point algorithm for relative pose. These minimal formulations are mathematically elegant because they exactly constrain the solution space.
However, this elegance comes at a steep practical cost. Minimal solvers typically yield highly non-linear, high-degree polynomial equations. Solving them requires complex root-finding techniques or intensive iterative loops like RANSAC to filter out noise. Furthermore, because they use no redundant data, a single pixel of noise in any input point directly corrupts the entire calculation.
To bypass these limitations, a powerful paradigm shift has emerged: intentionally gathering more data points than mathematically necessary to construct overdetermined linear systems. By embracing redundancy, these methods transform fragile, non-linear geometric problems into robust, stable, and computationally efficient linear algebra operations.
Linearization Through Redundancy
Why does adding more data points make a non-linear problem linear? In a minimal setting, geometric constraints (such as rigidity or epipolar geometry) manifest as quadratic or higher-order polynomial constraints on the unknown parameters. However, when we collect a non-minimal set of observations, we can often reformulate the system by treating non-linear combinations of variables as independent linear terms.
As Lan demonstrated in Linear N>=4-Point Pose Determination, increasing the number of reference points beyond the minimal set simplifies the underlying mathematical structure. This overdetermination allows complex polynomial constraints to be flattened into a direct linear system, which can then be solved cleanly using Singular Value Decomposition (SVD) rather than iterative non-linear optimization.
Minimal Solver (e.g., 3 Points) --> Non-linear Polynomials --> Complex Root-Finding
Overdetermined Solver (N Points) --> Linear Matrix System --> Fast, Direct SVD
This strategy is particularly effective for high-frequency or unconventional sensors where speed is paramount. For instance, Gehrig et al. applied this principle to event cameras in An N-Point Linear Solver for Line and Motion Estimation with Event Cameras. By mapping geometric incidence relations to an overdetermined linear system using an arbitrary number of events ($N \ge 5$), the authors bypassed polynomial root-finding entirely. This resulted in a solver that runs hundreds of times faster than previous state-of-the-art methods while remaining highly resilient to pixel noise and timestamp jitter.
Even when an algebraic framework originates from a minimal solver design, it can be extended to leverage redundancy. As shown by Larsson et al. in Making Minimal Solvers for Absolute Pose Estimation Compact and Robust, applying a nullspace-based parametrization to non-minimal data sets allows a system to maintain the compact efficiency of algebraic solvers while inheriting the accuracy and noise-rejection benefits of redundant information.
Statistical Stability and Noise Suppression
Beyond simplifying the math, overdetermined systems fundamentally alter how measurement errors propagate through an algorithm. When a system is overdetermined, it can be solved using a least-squares formulation that minimizes algebraic error across all available points simultaneously.
In Least-squares Optimal Relative Planar Motion for Vehicle-mounted Cameras, Hajder demonstrated that incorporating all available point correspondences into a quadratic cost function prevents the system from overfitting to noisy localized data. Instead of perfectly fitting a fragile, minimal subset, the solver exploits the shared geometric consistency of the entire point cloud to average out random errors.
This statistical buffering ensures that error growth remains predictable and well-behaved:
- Linear Error Scaling: In a foundational paper on projective reconstruction, Triggs showed in Factorization Methods for Projective Structure and Motion that point-based 3D reconstruction via factorization exhibits high numerical stability, where reconstruction errors scale linearly relative to image noise.
- Predictable Calibration: A similar linear error relationship was leveraged by Pusztai in Accurate Calibration of LiDAR-Camera Systems Using Ordinary Boxes, proving that overdetermined plane-fitting constraints ensure calibration stability even under significant sensor noise or low resolution.
- Occlusion Tolerance: In the domain of human pose tracking, Lüsi et al. demonstrated in SASE: RGB-Depth Database for Human Head Pose Estimation that formulating 3D rotation estimation as an overdetermined linear system allows the algorithm to maintain accurate tracking even when several landmark points are partially occluded or poorly detected.
This statistical consistency is so powerful that it can even replace traditional, computationally heavy outlier rejection loops. In Very Fast Solution to the PnP Problem with Algebraic Outlier Rejection, Ferraz et al. bypassed minimal-subset sampling entirely by utilizing hundreds of redundant correspondences. Because the large inlier set naturally aligns with the true geometric solution, the underlying linear system remains resilient against up to 50% outliers, achieving massive speedups by relying on algebraic consistency rather than iterative guessing.
Smoothing the Optimization Landscape
Redundancy does more than just power linear algebraic solvers; it also reshapes the optimization landscape for numerical tracking algorithms.
Consider Homotopy Continuation (HC), a geometric method that solves complex polynomial systems by tracking numerical paths from a known start solution to a target problem. In Simulator HC: Regression-based Online Simulation of Starting Problem-Solution Pairs for Homotopy Continuation in Geometric Vision, Zhang et al. showed that introducing just a slight amount of redundancy—such as using an eight-point overdetermined system instead of a minimal seven-point formulation—dramatically improves path-tracking success rates. The extra data points act as mathematical anchors, smoothing out the optimization landscape, preventing the solver from falling into incorrect local minima, and stabilizing convergence paths.
This stabilization is equally vital in complex biological inverse problems. As Egger et al. demonstrated in Identification of Chemotaxis Models with Volume-Filling, parameter identification from cell density distributions becomes highly robust against noise when framed as an overdetermined system. The overabundance of observational data effectively constrains the inversion process, preventing mathematical drift and ensuring a unique, stable solution.
Universality Across Modalities
The strategy of trading minimality for overdetermined linear robustness serves as a unifying principle across a wide variety of hardware configurations and physical domains:
Extrinsic Calibration
Calibrating complex optical paths benefits heavily from redundant geometric constraints. Takahashi et al. successfully applied this to mirror-based systems in A new mirror-based extrinsic camera calibration using an orthogonality constraint and to kaleidoscopic optics in A Linear Extrinsic Calibration of Kaleidoscopic Imaging System from Single 3D Point. By constructing overdetermined linear equations from redundant reflections, their methods filter out pixel-level measurement jitter to produce highly stable rotation and translation estimates. Similarly, Zhang utilized an overdetermined system of equations derived from multiple point correspondences on a planar surface in Dynamic calibration of the relative pose and error analysis in a structured light system, significantly enhancing the noise immunity of camera-projector calibration.
Deformable Surface Tracking
In A linear least-squares solution to elastic Shape-from-Template, Malti et al. tackled the non-linear problem of tracking elastic surface deformations. By integrating physics-based mechanical priors into a linear least-squares framework, the authors proved that an overdetermined set of physical constraints provides far greater resilience to imperfect image correspondences than traditional analytical geometric approaches.
Non-Visual and 1D Sensing
Even in highly constrained geometric scenarios, redundancy prevents catastrophic failure modes. In Camera Resection from Known Line Pencils and a Radially Distorted Scanline, Dibene et al. showed that utilizing redundant line observations within a linear framework protects 1D scanline pose estimation from pixel noise and specific geometric degeneracies.
Stepping outside of computer vision entirely, Zimmer et al. applied this concept to laser feedback interferometry in A Novel Signal Processing Strategy for Short-Range Laser Feedback Interferometry Sensors. By utilizing a four-ramp modulation scheme to solve for only two physical variables (distance and velocity), they created an overdetermined mathematical model. This redundancy allowed their algorithm to cluster valid solutions and seamlessly discard outlier errors caused by hardware-induced sensor blind spots.
Conclusion
Whether estimating the trajectory of an autonomous vehicle, calibrating a kaleidoscopic camera array, or tracking a deforming material, the underlying insight remains the same: minimality is a mathematical luxury that real-world data cannot afford. By intentionally collecting redundant observations and assembling overdetermined linear systems, modern geometric solvers trade complex, noise-sensitive polynomial root-finding for the predictable, robust, and lightning-fast world of linear least-squares and singular value decomposition.
Key Foundational Work
Euclidean constraints for uncalibrated reconstruction (1993) — contributed 1 concept elements to this direction.
Factorization Methods for Projective Structure and Motion (1996) — contributed 1 concept elements to this direction.