Accurate Non-Iterative O(n) Solution to the PnP Problem

Francesc Moreno-Noguer, Vincent Lepetit, Pascal FuaICCV 2007 · OpenReview

Introduction

The Perspective-n-Point (PnP) problem is a cornerstone of computer vision, essential for tasks in robotics, augmented reality, and 3D reconstruction. It involves determining a camera's position and orientation from known 3D points and their 2D projections. This paper introduces EPnP (Efficient Perspective-n-Point), a non-iterative solution that achieves $O(n)$ complexity, meaning its computational cost grows linearly with the number of points.

The PnP Problem

Historically, researchers faced a trade-off between speed and accuracy. Iterative methods are accurate but slow and require a good initial guess. Non-iterative methods are faster but often computationally complex ($O(n^5)$ or higher), unstable under noise, or limited to few points. EPnP addresses these challenges by providing a method that is simultaneously fast, accurate, and robust without requiring initialization.

The EPnP Method

The core innovation of EPnP is a dimensionality reduction technique. Instead of treating all $n$ points as independent variables, the authors express each 3D point as a weighted sum of four virtual control points (three for planar cases).

  1. Barycentric Coordinates: Reference points are expressed relative to four control points in the world coordinate system.
  2. Linear System: Projection equations form a linear system $Mx = 0$, where $x$ represents the control points' coordinates in the camera frame.
  3. Constant-Sized Kernel: The matrix $M^T M$ is always $12 \times 12$, regardless of $n$. The $O(n)$ cost is limited to constructing this matrix.
  4. Quadratic Constraints: The solution is refined using quadratic equations that preserve distances between control points, ensuring the geometry remains consistent between world and camera frames.

Experimental Evaluation

The algorithm was tested using synthetic data with varying Gaussian noise, point counts ($n=4$ to $150$), and outlier percentages. Both centered and uncentered data distributions were evaluated. Real-world testing involved tracking a textured box with a calibrated camera, generating roughly 200 correspondences per frame.

Key Results

EPnP demonstrates significant advantages in both speed and robustness. As shown in the performance comparisons, EPnP maintains low error rates even as noise increases, and its computation time remains remarkably low compared to iterative alternatives.

Comparison of rotation error distributions and computation time across different PnP solvers.

The method is approximately 200 times faster than previous $O(n^8)$ non-iterative methods and 10 to 30 times faster than popular iterative methods like LHM. While slightly less precise than perfectly converged iterative methods in some cases, EPnP is far more robust against local minima.

Comprehensive performance evaluation of EPnP against state-of-the-art methods under various noise, point count, and outlier conditions.

Furthermore, EPnP serves as an ideal initialization for iterative solvers, providing a high-quality starting point that leads to rapid convergence and maximum precision.

Conclusion

EPnP offers a powerful, scalable solution to the PnP problem. By reducing the problem to a fixed number of control points, it achieves $O(n)$ efficiency without sacrificing stability. While sensitive to outliers like other least-squares methods, its integration into RANSAC frameworks makes it highly effective for real-world applications. Future work may extend this "control point" framework to other fundamental vision problems like Essential matrix estimation.

Summary updated

Abstract

We propose a non-iterative solution to the PnP problem-the estimation of the pose of a calibrated camera from n 3D-to-2D point correspondences—whose computational complexity grows linearly with 𝑛<. This is in contrast to state-of-the-art methods that are 𝑂(𝑛 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">5</sup> ) or even 𝑂(𝑛 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">8</sup> ), without being more accurate. Our method is applicable for all 𝑛≥4 and handles properly both planar and non-planar configurations. Our central idea is to express the 𝑛 3D points as a weighted sum of four virtual control points. The problem then reduces to estimating the coordinates of these control points in the camera referential, which can be done in 𝑂(𝑛) time by expressing these coordinates as weighted sum of the eigenvectors of a 12 × 12 matrix and solving a small constant number of quadratic equations to pick the right weights. The advantages of our method are demonstrated by thorough testing on both synthetic and real-data.
BibTeX
@inproceedings{morenonoguer2007accurate,
  author = {Francesc Moreno-Noguer and Vincent Lepetit and Pascal Fua},
  title = {{Accurate Non-Iterative O(n) Solution to the PnP Problem}},
  booktitle = {IEEE/CVF International Conference on Computer Vision},
  year = {2007},
  url = {https://openreview.net/forum?id=r1ECsZGdZS},
}
Figure