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

Yinqiang Zheng, Yubin Kuang, Shigeki Sugimoto, Kalle Astrom, Masatoshi Okutomi; Proceedings of the IEEE International Conference on Computer Vision (ICCV), 2013, pp. 2344-2351

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??bner 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 Gr??bner basis solver. Experiment results have demonstrated that, in terms of accuracy, our proposed solution is definitely better than the state-ofthe-art O(n) methods, and even comparable with the reprojection error minimization method.