En Français - In English

Le Probleme Perspective-N-Point/The Perspective-N-Point Problem

Présentation

Le problème perspective-N-point est un problème assez ancien. Il consiste, connaissant un certain nombre de points (N) dans un repère objet et connaissant la projection de ces points sur un plan dans un autre repère, à retrouver la transformation entre les deux repères ou à trouver la position des points dans le second repère. Beaucoup de solutions ont déjà été proposées. Dans l'ensemble des solutions déjà existantes il n'est pas commun de trouver une solution complètement analytique. C'est ce que nous proposons. Nous montrons aussi comment trouver systématiquement une solution analytique pour un cas donné. Notre technique fonctionne pour 3 points alignés et plus, 4 points coplanaires et plus, et au moins 5 points dans une configuration quelconque... Nous l'illustrons ici sur un exemple : le P4P.

Principe

La mise en équation la plus courante repose sur l'expression du cosinus généralisé dans la pyramide de vue. Cette mise en équation conduit à des système lourds et compliqués à résoudre (non linéaire !!!). Nous sommes partis d'une formulation beaucoup plus simple : une mise en équation paramétrique : Considérons par exemple que l'on a 4 points (p1, p2, p3, p4) parfaitement connus dans l'espace. Considérons aussi que nous avons une image de ces 4 points (p'1, p'2, p'3, p'4). Notre capteur d'image calibré notons F les foyer de notre capteur, nous pouvons écrire :

p1 = F + l1 * v1
p2 = F + l2 * v2
p3 = F + l3 * v3
p4 = F + l4 * v4

avec

vi=p'i-F

Dans ce cas, localiser les points revient à trouver les valeurs de l1, l2, l3 et l4. Pour cela il faut trouver suffisamment d'équations qui font intervenir ces inconnues. Nous connaissons les points dans l'espace, nous pouvons donc écrire des relations qui lient les vecteurs pipj. Par exemple :

p1p3 = k1 p1p2+ k2 p1p4 (1)

k1 et k2 étant connus car l'ensemble des points est connu. On a donc 3 équations 4 inconnues, en effet :

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)

or l'équation (1) est en fait un système d'équations ( une équation en x, une en y et une en z). On peut donc exprimer l'une des inconnues li en fonction de toutes les autres.

A ce stade, nous avons fixé l'orientation de la figure dans l'espace. Il reste à estimer la distance. Pour cela il faut trouver l'expression de la dernière inconnue. Il suffit pour cela d'utiliser la norme de l'un des vecteurs, par exemple :

|| p1p3 || = || F + l3 * v3 - (F + l1 * v1) || = Lp1p3 (2)

La résolution de (1) est évidente et on ne peut plus simple, c'est un système linéaire ! la résolution de (2) est presque aussi facile, c'est une équation du second degré (que l'on peut simplifier en plaçant le centre du repère en F). Il ne reste plus qu'à injecter le résultat de (2) dans le résultat de (1) pour avoir une expression de chaque li

Démonstration

--- Video ---

Conclusion

Nous proposons une nouvelle solution simple et analytique au problème pnp, bien adaptée aux traitements temps réels. Nous pouvons fournir une expression analytique de la solution pour n>=3 si les points sont alignés, n>=4 si les points sont coplanaires, n>=5 si les points sont dans une configuration quelconque. Cette solution peut être utilisée directement ou comme initialisation d'une minimisation.

Bibliographie et liens

Pour plus de détails sur la methode voir :

• "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.

Pour une vue d'ensemble des solutions deja proposees :

• "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

Bibliographie :



Articles concernant le 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.