A Direct Least-Squares (DLS) method for PnP

Joel A. Hesch, Stergios I. RoumeliotisICCV 2011 · DOI

Abstract

The Perspective-n-Point (PnP) problem is a cornerstone of computer vision, requiring the estimation of a camera's pose from 3D-to-2D correspondences. We present the Direct Least-Squares (DLS) method, a non-iterative solution that handles any number of points ($n \geq 3$). By formulating the problem as a system of three third-order polynomials, DLS achieves accuracy comparable to iterative Maximum-Likelihood Estimators (MLE) without requiring an initial guess, offering a robust and scalable alternative to existing linear and minimal solvers.

Introduction: The PnP Problem

In robotics and computer vision, determining a camera's 6-degree-of-freedom (6-DOF) position and orientation from known 3D world points and their 2D image projections is known as the Perspective-n-Point (PnP) problem.

Geometry of the PnP problem, showing the relationship between world points and camera frames.

Historically, researchers faced a trade-off between speed and accuracy:

  1. Minimal solvers (P3P): Fast and direct, but only use three points and are highly sensitive to noise.
  2. Linear methods (e.g., EPnP, NPL): Fast and scalable, but often less accurate and sometimes require specific point counts to guarantee a unique solution.
  3. Iterative methods (MLE): Highly accurate, but require a good initial guess to avoid getting stuck in local minima.

The DLS method bridges this gap by providing a "best of both worlds" approach: a method that is as accurate as MLE but doesn't require initialization and can handle any number of points ($n \geq 3$) in both planar and non-planar configurations.

The Direct Least-Squares (DLS) Method

The DLS approach innovates by transforming a nonlinear least-squares cost function into an analytically solvable polynomial system.

Mathematical Formulation

The method utilizes a spherical camera model and parametrizes rotation using Cayley-Gibbs-Rodriguez (CGR) parameters ($s_1, s_2, s_3$). This choice avoids the over-parametrization and orthogonality constraints of standard rotation matrices. Through algebraic manipulation, the unknown scale and translation are eliminated, reducing the optimization to finding the three rotation parameters.

Solving the System

The optimality conditions yield a system of three third-order polynomials. To solve this without iteration, the authors employ the Macaulay resultant method to construct a multiplication matrix. The potential camera poses are then derived from the eigen-decomposition of this matrix. This process identifies all critical points (up to 27), ensuring the global minimum is found without the risk of getting stuck in a local one.

Experimental Evaluation

The DLS method was rigorously tested against synthetic and real-world data. Synthetic tests varied the number of points ($n=3$ to $10$) and image noise levels ($\sigma = 0$ to $7$ pixels).

Performance comparison of DLS against other methods (NPL, EPnP, SDP) under varying image noise levels.

Key Results

  • Accuracy and Robustness: As shown in the noise sensitivity plots, DLS consistently outperforms leading linear methods like EPnP and NPL. Its accuracy is nearly indistinguishable from the iterative Maximum-Likelihood Estimator (DLS-LM), even at high noise levels.
  • Scalability: A major advantage of DLS is its constant complexity; the final polynomial system size is independent of the number of points. Whether solving for 3 points or 3,000, the method always solves three third-order polynomials.
  • Planar Handling: Unlike many predecessors that struggle with co-planar point configurations, DLS handles planar and non-planar scenes with equal ease.
  • Efficiency: With a Matlab execution time of approximately 15ms, DLS is significantly faster than Semi-Definite Programming (SDP) approaches (~200ms) while providing much higher reliability.

Discussion and Future Work

While DLS is highly effective, the CGR parametrization introduces a singularity at 180-degree rotations. Although rare in practical PnP scenarios, future iterations could explore quaternion-based formulations to eliminate this. Additionally, while the current Matlab implementation is efficient, a C++ port would likely enable real-time performance for high-frequency robotics applications. DLS represents a significant step toward a universal, robust, and direct PnP solver that combines the speed of linear methods with the precision of iterative optimization.

Summary updated

BibTeX
@inproceedings{hesch2011direct,
  author = {Joel A. Hesch and Stergios I. Roumeliotis},
  title = {{A Direct Least-Squares (DLS) method for PnP}},
  booktitle = {IEEE/CVF International Conference on Computer Vision},
  year = {2011},
  doi = {10.1109/iccv.2011.6126266},
}
Figure