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

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 n. This is in contrast to state-of-the-art method that are O(n^5) or even O(n^8), without being more accurate. Our method is applicable for all n greater than 4 and handles properly both planar and non-planar configurations. Our central idea is to express the n 3--D 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 $O(n)$ time by expressing these coordinates as weighted sum of the eigenvectors of a $12\times12$ 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.