Introduction
Robust model estimation is a fundamental challenge in 3D computer vision, essential for tasks ranging from image stitching to autonomous drone navigation. This process typically involves two distinct stages: consensus maximization, which identifies "inlier" data points amidst noise and outliers, and non-minimal solving, which refines model parameters using the full set of identified inliers. Traditionally, these problems are addressed using stochastic methods like RANSAC or bespoke solvers tailored to specific geometric constraints.
This paper introduces a unified mathematical framework that treats these challenges as Polynomial Optimization Problems (POP). By applying convex relaxations—specifically Shor’s and Lasserre’s hierarchies—the authors provide a deterministic approach to global optimization across a wide variety of 3D vision tasks.
Methodology: From Polynomials to Convexity
The core innovation lies in the observation that most 3D vision constraints (e.g., point-on-plane or rigid body motion) can be expressed as low-degree polynomials. The authors leverage this structure through:
- Convex Relaxations: Quadratic problems are addressed using Shor’s relaxation, transforming non-convex constraints into a solvable Semi-Definite Program (SDP). For higher-degree problems, such as those found in non-rigid motion, Lasserre’s hierarchy provides a sequence of increasingly tight relaxations.
- Deterministic Consensus: Unlike the randomness of RANSAC, the framework utilizes Mixed-Integer Semi-Definite Programming (MI-SDP) combined with a Branch-and-Bound search. This ensures the identification of the maximum inlier set with global optimality guarantees.
Experimental Evaluation and Key Results
The framework was rigorously tested on synthetic benchmarks and real-world datasets, including rigid body transformations, camera autocalibration (Fountain and Herz-Jesu datasets), and Non-Rigid Structure-from-Motion (NRSfM).
Robustness to Outliers
A standout feature of the proposed method is its extreme resilience to data corruption. In rigid body transformation tests, the framework maintained high accuracy even when outliers comprised a significant portion of the dataset, outperforming existing global solvers that struggle as the outlier ratio increases.
Computational Efficiency
While SDP solvers are generally more complex than simple linear approximations, the authors demonstrate that their non-minimal solver scales linearly with the number of measurements. This makes the approach feasible for large-scale datasets where precision and optimality are paramount.
Conclusion
By providing a "unified language" for 3D vision, this framework allows researchers to plug in polynomial constraints and achieve globally optimal results without designing problem-specific algorithms. While the computational cost of SDPs remains higher than RANSAC, the deterministic nature and robustness of this approach represent a significant step forward for high-precision vision applications. Future work will focus on further reducing the computational overhead and exploring the theoretical limits of relaxation tightness in geometric problems.
Summary updated