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).
- Barycentric Coordinates: Reference points are expressed relative to four control points in the world coordinate system.
- Linear System: Projection equations form a linear system $Mx = 0$, where $x$ represents the control points' coordinates in the camera frame.
- 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.
- 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.
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.
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