An Efficient Solution to Non-Minimal Case Essential Matrix Estimation.

Area of Science:

• Computer Vision
• Robotics
• Geometric Deep Learning

Background:

• Relative pose estimation is crucial for 3D reconstruction and navigation.
• Classical five-point methods are efficient but limited to specific cases.
• Existing N-point solvers for multiple correspondences often suffer from inefficiency or local minima.

Purpose of the Study:

• To develop a certifiably globally optimal and efficient solver for the N-point problem.
• To address the limitations of existing methods in handling multiple point correspondences.
• To provide theoretical guarantees for the proposed solution.

Main Methods:

• Formulating the N-point problem as a quadratically constrained quadratic program (QCQP).
• Employing semidefinite relaxation to achieve certifiably globally optimal solutions.
• Developing a robust N-point method using M-estimators to handle outliers.

Main Results:

• The proposed method achieves certifiably globally optimal solutions in polynomial time.
• Theoretical guarantees, including tightness and local stability, are provided for the semidefinite relaxation.
• The N-point method demonstrates 2-3 orders of magnitude speed improvement over state-of-the-art techniques.
• The robust N-point method shows superior performance in accuracy and robustness, especially with moderate outlier ratios.

Conclusions:

• The novel N-point solver offers a significant advancement in efficient and globally optimal relative pose estimation.
• Semidefinite relaxation provides a powerful tool for solving non-convex optimization problems in computer vision.
• The robust extension effectively handles outliers, enhancing practical applicability.
• This work advances the state-of-the-art in solving fundamental geometric problems in computer vision.