Le Probleme Perspective-N-Point/The Perspective-N-Point Problem
Presentation
Perspectice-N-point problem is an old problem. Given a set of N points well know in a local coordinate space and given a projection of this set of points on a plan in another local coordinate space, to find the transformation between the two coordinate space or to find the position of points in the second coordinate space. Many solutions already exist! We offer a new solution which is completely analytical and it is uncommon to have analytical among state of the art. Our method works with at least 3 aligned points, at least 4 coplanar points and at least 5 points in a general case. We illustrate our solution by solving the P4P.
Principle
This problem is commonly solved using generalized cosines in perspective polyhedron. This lead to non linear systems. Our starting point is simpler as we use parametric representation:
Given 4 points (p1, p2, p3, p4) well know in a coordinate space. Given a projection of these 4 points (p'1, p'2, p'3, p'4). As our sensor is calibrated we know the center of projection F (the fovea of our sensor). We have a expression of all points:
p1 = F + l1 * v1 p2 = F + l2 * v2 p3 = F + l3 * v3 p4 = F + l4 * v4
with
vi=p'i-F
Now, locate points is equivalent to find values of l1, l2, l3 and l4. As we know points in space, it is possible to write relations between vectors (pipj), for example:
p1p3 = k1 p1p2+ k2 p1p4 (1)
k1 and k2 are known because points all pi are known and we have expression vectors (pipj) according to li:
p1p3 = p3-p1 = F + l3 * v3 - (F + l1 * v1) p1p2 = p2-p1 = F + l2 * v2 - (F + l1 * v1) p1p4 = p4-p1 = F + l4 * v4 - (F + l1 * v1)
Combined with equation (1) we get a system (3 equations - according to each axis). We can then express one li according all other.
We have now the orientation of points in space. Now we have to find the distance. We need another equation. To remove
ambiguity we use the norm Lpipj of one vector pipj, for example:
|| p1p3 || = || F + l3 * v3 - (F + l1 * v1) || = Lp1p3 (2)
Solution of equations (1) is obvious as it is a linear system! Solution of equation (2) is almost as simple. It is a quadratic solution (which can be simplified by using F as the center of coordinate space). Combination of solution of (2) in (1) give a solution for each li.
Demonstration
Conclusion
We offer a new simple, fast analytical solution for solving the perspective-N-point problem. We can find this analytical solution for N>=3 aligned points, N>=4 coplanar points and N>=5 in general case. This solution can also be used to initialize a minimization process.
Bibliography and links
To get more details:- "An Analytical Solution to the Perspective-N-Point Problem for Common Planar Camera and for Catadioptric Sensor", J. Fabrizio, J. Devars - International Journal of Image and Graphics (IJIG08)
- "The Perspective-N-Point Problem for Catadioptric Sensors: An Analytical Approach", J. Fabrizio, J. Devars, International Conference on Computer Vision and Graphics (ICCVG'04), Warsaw, september 2004
Published by Kluwer in the book series COMPUTATIONAL IMAGING AND VISION. - "Localisation d'obstacles coopératifs par systèmes de vision classiques et panoramiques", J. Fabrizio - PhD thesis - Université Pierre et Marie Curie - Paris VI - December 15, 2004
- "Une solution analytique au problème « Perspective-N-Points » et son extension aux capteurs catadioptriques", J. Fabrizio, J. Devars 19th GRETSI Symposium on Signal and Image Processing (GRETSI'03), Paris, 8 - 11 September 2003.
- "Localisation d'obstacles coopératifs par systèmes de vision classiques et panoramiques", J. Fabrizio - PhD thesis - Université Pierre et Marie Curie - Paris VI - December 15, 2004
Articles on the pnp:
M. A. Abidi and T. Chandra. "A new efficient and direct solution for pose estimation using quadrangular targets : Algorithm and evaluation.", IEEE Transactions on Pattern Analysis and Machine Intelligence, 17(5) :534-538, 1995
T. D. Alter. "3-d pose from 3 points using weak-perspective.", IEEE Transactions on Pattern Analysis and Machine Intelligence, 16(8) :802-808, 1994.
M-A. Ameller, Long Quan, and B. Triggs. "Camera pose revisited : New linear algorithms. In 14eme Congres Francophone de Reconnaissance des Formes et Intelligence Artificielle, 2002. Paper in French.
Rodrigo L. Carceroni and Christopher M. Brown. "Numerical methods for model-based pose recovery.", Technical Report TR659, University of Rochester - Computer Science Department, 1997.
Daniel DeMenthon and Larry S. Davis. "Exact and approximate solutions of the perspective-three-point problem.", IEEE Transactions on Pattern Analysis and Machine Intelligence, 14(11) :1100-1105, November 1992.
Daniel F. DeMenthon and Larry S. Davis. "Model-based object pose in 25 lines of code.", International Journal of Computer Vision, 15(1-2) :123-141, 1995
Martin A. Fischler and Robert C. Bolles. "Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography.", Communication of the ACM, 24(6) :381-395, 1981.
Xiao-Shan Gao, Xiao-Rong Hou, Jianliang Tang, and Hang-Fei Cheng. "Complete solution classification for the perspective-three-point problem.", IEEE Transactions on Pattern Analysis and Machine Intelligence, 25(8) :930-943, August 2003.
Radu Horaud, Stephane Christy, and Fadi Dornaika. "Object pose: The link between weak perspective, para perspective, and full perspective.", Technical Report 2356, Institut National de Recherche en Informatique et en Automatique, September 1994.
Radu Horaud, Bernard Conio, Olivier Leboulleux, and Bernard Lacolle. "An analytic solution for the perspective-4-point problem.", Computer Vision, Graphics and Image Processing, 47 :33-44, 1989.
Robert M Haralick, Chung Nan Lee, Kartsen Ottenberg, and Michael Nolle. "Analysis and solutions of the three points perspective pose estimation problem.", In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 592-598, 1991.
Z. Y. Hu and F. C. Wu. "A note on the number of solutions of the noncoplanar p4p problem.", IEEE Transactions on Pattern Analysis and Machine Intelligence, 24(4) :550-555, 2002.
Qiang Ji, Mauro S. Costa, Robert M. Haralick, and Linda G. Shapiro. "A robust linear least-squares estimation of camera exterior orientation using multiple geometric features.", ISPRS Journal Of Photogrammetry And Remote Sensing, 55(2) :75-93, June 2000.
D.G. Lowe. "Solving for the parameters of object models from image descriptions." ARPA Image Understanding Workshop, pages 121-127, April 1980.
David G. Lowe. "Three-dimensional object recognition from single twodimensional images." Artificial Intelligence, 31(3) :355-395, 1987.
David G. Lowe. "Fitting parameterized three-dimensional models to images.", IEEE Transactions on Pattern Analysis and Machine Intelligence, 13(5) :441-450, 1991
Long Quan and Zhong-Dan Lan. "Linear n-point camera pose determination.", IEEE Transactions on Pattern Analysis and Machine Intelligence, 21(8) :774-780, August 1999.