A complete symbolic-numeric linear method for camera pose determination

ABSTRACT

Camera pose estimation is the problem of determining the position and orientation of an internally calibrated camera from known 3D reference points and their images. We briefly survey several existing methods for pose estimation, then introduce our new complete linear method, which is based on a symbolic-numeric method from the geometric (Jet) theory of partial differential equations. The method is stable and robust. In particular, it can deal with the points near critical configurations. Numerical experiments are given to show the performance of the new method.

REFERENCES

• 1: M. a. Abidi , 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, v.17 n.5, p.534-538, May 1995 [doi>10.1109/34.391388]
• 2: M.A. Ameller, B. Triggs and L. Quan, Camera Pose Revisited - New Linear Algorithms, ECCV'00, 2000.
• 3: W. Auzinger, H. Stetter, An Elimination Algorithm for the Computation of All Zeros of a System of Multivariate Polynomial Equations, Numerical Mathematics, Proceedings of the International Conference, Singapore, 1988, Vol 86 of Int. Ser. Numer. Math., 11--30.
• 4: J. Bonasia, G.J. Reid, L.H. Zhi, Experiments in Symbolic-Numeric Completion of Linear Differential Systems, Preprint, ORCCA, Canada, 2002.
• 5: B. Buchberger, An Algorithm for Finding a Basis for the Residue Class Ring of a Zero-Dimensional Polynomial Ideal, PhD. Thesis, Univ. of Innsbruck, Math. Inst. 1965.
• 6: Robert M. Corless , Patrizia M. Gianni , Barry M. Trager, A reordered Schur factorization method for zero-dimensional polynomial systems with multiple roots, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.133-140, July 21-23, 1997, Kihei, Maui, Hawaii, United States [doi>10.1145/258726.258767]
• 7: J. Emsalem, Géométrie des points épais, Bull. Soc. Math. France, Vol.106, 399--416, 1978.
• 8: Martin A. Fischler , Robert C. Bolles, Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography, Communications of the ACM, v.24 n.6, p.381-395, June 1981 [doi>10.1145/358669.358692]
• 9: Xiao-Shan Gao , Xiao-Rong Hou , Jianliang Tang , Hang-Fei Cheng, Complete Solution Classification for the Perspective-Three-Point Problem, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.8, p.930-943, August 2003 [doi>10.1109/TPAMI.2003.1217599]
• 10: X.S. Gao, J.L. Tang On the Solution Number of Solutions for the $P4P$ Problem, Mathematics-Mechanization Research Center Preprints Preprint, No.21, 64--76, 2002.
• 11: Vladimir P. Gerdt , Yuri A. Blinkov, Involutive bases of polynomial ideals, Mathematics and Computers in Simulation, v.45 n.5-6, p.519-541, March 1998 [doi>10.1016/S0378-4754(97)00127-4]
• 12: G. Golub and C.V. Loan. Matrix Computations. John Hopkins U. Press, 3rd ed., 1996.
• 13: R.M. Haralick, C. Lee, K. Ottenberg and M. Nolle, Analysis and Solutions of The Three Point Perspective Pose Estimation Problem, Proc. of the Int. Conf. on Computer Vision and Pattern Recognition, 592--598, 1991.
• 14: K. Hazaveh, D. Jeffrey, G.J. Reid and S.M. Watt. An Exploration of Homotopy solving in Maple, to appear in the Proceedings of the Asian Symposium on Computer Mathematics (ASCM'03), 2003.
• 15: Radu Horaud , Bernard Conio , Oliver Leboulleux , Bernard Lacolle, An analytic solution for the perspective 4-point problem, Computer Vision, Graphics, and Image Processing, v.47 n.1, p.33-44, July 1989 [doi>10.1016/0734-189X(89)90052-2]
• 16: B.K.P. Horn, Closed Form Solution of Absolute Orientation Using Unit Quaternions, Journal of the Optical Society of America, 5(7): 1127--1135, 1987.
• 17: Z. Y. Hu , F. C. Wu, A Note on the Number of Solutions of the Noncoplanar P4P Problem, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.4, p.550-555, April 2002 [doi>10.1109/34.993561]
• 18: E. Kähler, Einführung in die Theorie der Systeme von Differential gleichungen, B.G. Teubner, Leipzig, 1934.
• 19: M. Kuranishi, On E. Cartan's Prolongation Theorem of Exterior Differential Systems, Amer. J. Math, Vol. 79: 1--47, 1957.
• 20: F.S. Macaulay, The Algebraic Theory of Modular Systems. Cambridge Univ. Press, Vol. 19, Cambridge tracts in Math. and Math. Physics, 1916.
• 21: H.M. Möller, T. Sauer, H-bases for polynomial interpolation and system solving. Advances Comput. Math., To appear.
• 22: B. Mourrain, Isolated points, duality and residues. J. of Pure and Applied Algebra, Vol. 117 & 118, 469--493, 1996, Special issue for the Proc. of the 4th Int. Symp. on Effective Methods in Algebraic Geometry (MEGA).
• 23: H. Michael Möller , Hans J. Stetter, Multivariate polynomial equations with multiple zeros solved by matrix eigenproblems, Numerische Mathematik, v.70 n.3, p.311-329, May 1995 [doi>10.1007/s002110050122]
• 24: B. Mourrain, Computing the isolated roots by matrix methods, Journal of Symbolic Computation, v.26 n.6, p.715-738, Dec. 1998 [doi>10.1006/jsco.1998.0236]
• 25: Bernard Mourrain, A New Criterion for Normal Form Algorithms, Proceedings of the 13th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.430-443, November 15-19, 1999
• 26: Bernard Mourrain , Philippe Trebuchet, Solving projective complete intersection faster, Proceedings of the 2000 international symposium on Symbolic and algebraic computation, p.234-241, July 2000, St. Andrews, Scotland [doi>10.1145/345542.345642]
• 27: Ph. Trébuchet, Vers une résolution stable et rapide des équations algébriques. PhD. Thesis, Université Pierre et Marie Curie, 2002.
• 28: J.F. Pommaret. Systems of Partial Differential Equations and Lie Pseudogroups. Gordon and Breach Science Publishers, 1978.
• 29: Long Quan , Zhongdan Lan, Linear N-Point Camera Pose Determination, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.21 n.8, p.774-780, August 1999 [doi>10.1109/34.784291]
• 30: G.J. Reid, P. Lin, and A.D. Wittkopf. Differential elimination-completion algorithms for DAE and PDAE. Studies in Applied Mathematics 106(1): 1--45, 2001.
• 31: Greg Reid , Chris Smith , Jan Verschelde, Geometric completion of differential systems using numeric-symbolic continuation, ACM SIGSAM Bulletin, v.36 n.2, p.1-17, June 2002 [doi>10.1145/581316.581317]
• 32: P. Rives, P. Bouthémy, B. Prasada, and E. Dubois, Recovering the Orientation and the position of a Rigid Body in Space from a Single View, Technical Report, INRS-Télécommunications, 3, place du commerce, Ile-des-Soeurs, Verdun, H3E 1H6, Quebec, Canada, 1981.
• 33: M. Saito, B. Sturmfels and N. Takayama, Gröbner Deformations of Hypergeometric Differential Equations, Algorithms and Computation in Mathematics, Vol. 6, 2000.
• 34: W.M. Seiler, Analysis and Application of the Formal Theory of Partial Differential Equations. PhD. Thesis, Lancaster University, 1994.
• 35: Andrew J. Sommese , Jan Verschelde , Charles W. Wampler, Numerical Decomposition of the Solution Sets of Polynomial Systems into Irreducible Components, SIAM Journal on Numerical Analysis, v.38 n.6, p.2022-2046, 2001 [doi>10.1137/S0036142900372549]
• 36: J. Tuomela and T. Arponen. On the numerical solution of involutive ordinary differential systems. IMA J. Numer. Anal. Vol 20, 561--599, 2000.
• 37: D. Wang, Characteristic Sets and Zero Structures of Polynomial Sets, Preprint, RISC-LINZ. 1989.
• 38: A.D. Wittkopf and G.J. Reid. Fast Differential Elimination in C: The CDiffElim Environment. Comp. Phys. Comm. vol 139(2): 192--217, 2001.
• 39: Wen-tsün Wu, Mechanical theorem proving in geometries, Springer-Verlag New York, Inc., New York, NY, 1994

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS

General Terms:
Algorithms

Keywords:
calibration, camera pose estimation, involutive bases, jet spaces, numeric elimination, numeric jet geometry, numerical linear algebra, partial differential equations, polynomial solving