Revisiting the PnP Problem: A Fast, General and Optimal Solution

TLDR

In this paper, we revisit the classical perspective‑n‑point (PnP) problem and propose the first non‑iterative O(n) solution that is fast, generally applicable, and globally optimal. The authors reformulate the PnP problem as a functional minimization, solve for all stationary points with a Gr\"obner basis approach, and employ a non‑unit quaternion representation and an unconstrained formulation that exploits a two‑fold symmetry to accelerate the solver and enhance numerical stability. Experiment results show that the proposed solution outperforms state‑of‑the‑art O(n) methods in accuracy and is comparable to reprojection‑error minimization.

Abstract

In this paper, we revisit the classical perspective-n-point (PnP) problem, and propose the first non-iterative O(n) solution that is fast, generally applicable and globally optimal. Our basic idea is to formulate the PnP problem into a functional minimization problem and retrieve all its stationary points by using the Gr"obner basis technique. The novelty lies in a non-unit quaternion representation to parameterize the rotation and a simple but elegant formulation of the PnP problem into an unconstrained optimization problem. Interestingly, the polynomial system arising from its first-order optimality condition assumes two-fold symmetry, a nice property that can be utilized to improve speed and numerical stability of a Grobner basis solver. Experiment results have demonstrated that, in terms of accuracy, our proposed solution is definitely better than the state-of-the-art O(n) methods, and even comparable with the reprojection error minimization method.