Globally Optimal O(n) Solution to the PnP Problem for General Camera Models

We present a novel and fast algorithm to solve the Perspective-n-Point problem. The PnP problem- estimating the pose of a calibrated camera based on measurements and known 3D scene, is recasted as a minimization problem of the Object Space Cost. Instead of limiting the algorithm to perspective cameras, we use a formulation for general camera models. The minimization problem, together with a quaternion based representation of the rotation, is transferred into a semi definite positive program (SDP). This transfer is done in O(n) time and leads to an SDP of constant size. The solution of the SDP is a global minimizer of the PnP problem, which can be estimated in less than 0.15 seconds for 100 points. 1