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

arXiv: https://arxiv.org/abs/1903.09067 · HTML: https://mlsanity.com/paper/1903.09067/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Mar 2019.

## Built on by (most cited first, 16 of 16)

- [Certifiably Optimal Outlier-Robust Geometric Perception: Semidefinite Relaxations and Scalable Global Optimization](https://mlsanity.com/paper/2109.03349/) (2021)
- [Convex Relaxation for Robust Vanishing Point Estimation in Manhattan World](https://mlsanity.com/paper/2505.04788/) (2025)
- [Advances in Global Solvers for 3D Vision](https://mlsanity.com/paper/2602.14662/) (2026)
- [GlobalPointer: Large-Scale Plane Adjustment with Bi-Convex Relaxation](https://mlsanity.com/paper/2407.13537/) (2024)
- [Six-Point Method for Multi-Camera Systems with Reduced Solution Space](https://mlsanity.com/paper/2402.18066/) (2024)
- [Fast and Robust Certifiable Estimation of the Relative Pose Between Two Calibrated Cameras](https://mlsanity.com/paper/2101.08524/) (2021)
- [From Correspondences to Pose: Non-minimal Certifiably Optimal Relative Pose without Disambiguation](https://mlsanity.com/paper/2312.05995/) (2023)
- [Semidefinite Relaxations for Robust Multiview Triangulation](https://mlsanity.com/paper/2301.11431/) (2023)
- [Robust Frame-to-Frame Camera Rotation Estimation in Crowded Scenes](https://mlsanity.com/paper/2309.08588/) (2023)
- [Towards Understanding The Semidefinite Relaxations of Truncated Least-Squares in Robust Rotation Search](https://mlsanity.com/paper/2207.08350/) (2022)
- [Linear Relative Pose Estimation Founded on Pose-only Imaging Geometry](https://mlsanity.com/paper/2401.13357/) (2024)
- [On Relative Pose Recovery for Multi-Camera Systems](https://mlsanity.com/paper/2102.11996/) (2021)
- [Consistent and Optimal Solution to Camera Motion Estimation](https://mlsanity.com/paper/2403.01174/) (2024)
- [A Birotation Solution for Relative Pose Problems](https://mlsanity.com/paper/2505.02025/) (2025)
- [Towards Rotation-only Imaging Geometry: Rotation Estimation](https://mlsanity.com/paper/2511.12415/) (2025)
- [Non-Minimal Sampling and Consensus for Prohibitively Large Datasets](https://mlsanity.com/paper/2604.22518/) (2026)

## Abstract (arXiv)

Finding relative pose between two calibrated images is a fundamental task in computer vision. Given five point correspondences, the classical five-point methods can be used to calculate the essential matrix efficiently. For the case of N (N > 5) inlier point correspondences, which is called N-point problem, existing methods are either inefficient or prone to local minima. In this paper, we propose a certifiably globally optimal and efficient solver for the N-point problem. First we formulate the problem as a quadratically constrained quadratic program (QCQP). Then a certifiably globally optimal solution to this problem is obtained by semidefinite relaxation. This allows us to obtain certifiably globally optimal solutions to the original non-convex QCQPs in polynomial time. The theoretical guarantees of the semidefinite relaxation are also provided, including tightness and local stability. To deal with outliers, we propose a robust N-point method using M-estimators. Though global optimality cannot be guaranteed for the overall robust framework, the proposed robust N-point method can achieve good performance when the outlier ratio is not high. Extensive experiments on synthetic and real-world datasets demonstrated that our N-point method is 2~3 orders of magnitude faster than state-of-the-art methods. Moreover, our robust N-point method outperforms state-of-the-art methods in terms of robustness and accuracy.