Convex Relaxations for Consensus and Non-Minimal Problems in 3D Vision

Thomas Probst, Danda Pani Paudel, Ajad Chhatkuli, Luc Van Gool

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.

Figure 6: Robustness to outliers. The proposed method (green) maintains significantly lower rotation and translation errors as the number of outliers increases compared to existing global solvers.

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.

Figure 5: Computational efficiency. Execution time vs. number of points shows that the proposed method scales linearly and remains competitive with or faster than alternative global optimization techniques.

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

Abstract

In this paper, we formulate a generic non-minimal solver using the existing tools of Polynomials Optimization Problems (POP) from computational algebraic geometry. The proposed method exploits the well known Shor's or Lasserre's relaxations, whose theoretical aspects are also discussed. Notably, we further exploit the POP formulation of non-minimal solver also for the generic consensus maximization problems in 3D vision. Our framework is simple and straightforward to implement, which is also supported by three diverse applications in 3D vision, namely rigid body transformation estimation, Non-Rigid Structure-from-Motion (NRSfM), and camera autocalibration. In all three cases, both non-minimal and consensus maximization are tested, which are also compared against the state-of-the-art methods. Our results are competitive to the compared methods, and are also coherent with our theoretical analysis. The main contribution of this paper is the claim that a good approximate solution for many polynomial problems involved in 3D vision can be obtained using the existing theory of numerical computational algebra. This claim leads us to reason about why many relaxed methods in 3D vision behave so well? And also allows us to offer a generic relaxed solver in a rather straightforward way. We further show that the convex relaxation of these polynomials can easily be used for maximizing consensus in a deterministic manner. We support our claim using several experiments for aforementioned three diverse problems in 3D vision.
BibTeX
@inproceedings{probst2019convex,
  author = {Thomas Probst and Danda Pani Paudel and Ajad Chhatkuli and Luc Van Gool},
  title = {{Convex Relaxations for Consensus and Non-Minimal Problems in 3D Vision}},
  booktitle = {IEEE/CVF International Conference on Computer Vision},
  year = {2019},
  doi = {10.1109/iccv.2019.01033},
}
Figure