A Robust O(n) Solution to the Perspective-n-Point Problem

We propose a noniterative solution for the Perspective-n-Point ({\rm P}n{\rm P}) problem, which can robustly retrieve the optimum by solving a seventh order polynomial. The central idea consists of three steps: 1) to divide the reference points into 3-point subsets in order to achieve a series of fourth order polynomials, 2) to compute the sum of the square of the polynomials so as to form a cost function, and 3) to find the roots of the derivative of the cost function in order to determine the optimum. The advantages of the proposed method are as follows: First, it can stably deal with the planar case, ordinary 3D case, and quasi-singular case, and it is as accurate as the state-of-the-art iterative algorithms with much less computational time. Second, it is the first noniterative {\rm P}n{\rm P} solution that can achieve more accurate results than the iterative algorithms when no redundant reference points can be used (n\le 5). Third, large-size point sets can be handled efficiently because its computational complexity is O(n).

1 Introduction

The term “Perspective-n-Point problem” (PnP) was coined by Fischler and Bolles [1] for the problem of determining the pose of a calibrated camera from correspondences between 3D reference points and their 2D projections. It has many applications in computer vision [2]–, [4], photogrammetry [5], robotics, augmented reality, etc. In practice, applications such as feature point-based camera tracking [6], [7] require solutions that can deal with both hundreds of feature points efficiently and a few feature points accurately.