Object-Image Correspondence for Algebraic Curves under Projections

Joseph M. Burdis ; Irina A. Kogan ; Hoon Hong

Symmetry, integrability and geometry: methods and applications, Tome 9 (2013)

Résumé

We present a novel algorithm for deciding whether a given planar curve is an image of a given spatial curve, obtained by a central or a parallel projection with unknown parameters. The motivation comes from the problem of establishing a correspondence between an object and an image, taken by a camera with unknown position and parameters. A straightforward approach to this problem consists of setting up a system of conditions on the projection parameters and then checking whether or not this system has a solution. The computational advantage of the algorithm presented here, in comparison to algorithms based on the straightforward approach, lies in a significant reduction of a number of real parameters that need to be eliminated in order to establish existence or non-existence of a projection that maps a given spatial curve to a given planar curve. Our algorithm is based on projection criteria that reduce the projection problem to a certain modification of the equivalence problem of planar curves under affine and projective transformations. To solve the latter problem we make an algebraic adaptation of signature construction that has been used to solve the equivalence problems for smooth curves. We introduce a notion of a classifying set of rational differential invariants and produce explicit formulas for such invariants for the actions of the projective and the affine groups on the plane.

Détail

Keywords: central and parallel projections; finite and affine cameras; camera decomposition; curves; classifying differential invariants; projective and affine transformations; signatures; machine vision.

Bibliographie

[1] Arnold G., Stiller P. F., “Mathematical aspects of shape analysis for object recognition”, Visual Communications and Image Processing, Proceedings of IS/SPIE Joint Symposium (San Jose, CA, 2007), SPIE Proceedings, 6508, eds. C. W. Chen, D. Schonfeld, J. Luo, 2007,, 65080E, 11 pp. | DOI

[2] Arnold G., Stiller P. F., Sturtz K., “Object-image metrics for generalized weak perspective projection”, Statistics and Analysis of Shapes, Model. Simul. Sci. Eng. Technol., Birkhäuser Boston, Boston, MA, 2006, 253–279 | DOI | MR | Zbl

[3] Bix R., Conics and cubics. A concrete introduction to algebraic curves, Undergraduate Texts in Mathematics, Springer-Verlag, New York, 1998 | DOI | MR

[4] Blaschke W., Vorlesungen über Differentialgeometrie und geometrische Grundlagen von Einsteins Relativitätstheorie, v. II, Affine Differentialgeometrie, J. Springer, Berlin, 1923 | Zbl

[5] Boutin M., “Numerically invariant signature curves”, Int. J. Comput. Vis., 40 (2000), 235–248, arXiv: math-ph/9903036 | DOI | Zbl

[6] Burdis J. M., Object-image correspondence under projections, Ph. D. thesis, North Carolina State University, 2010 | MR

[7] Burdis J. M., Kogan I. A., Supplementary material for “Object-image correspondence for curves under projections”, http://www.math.ncsu.edu/\allowbreakĩakogan/symbolic/projections.html

[8] Burdis J. M., Kogan I. A., “Object-image correspondence for curves under central and parallel projections”, Proceedings of the Symposium on Computational Geometry (Chapel Hill, NC, 2012), ACM, New York, 2012, 373–382 | DOI

[9] Calabi E., Olver P. J., Shakiban C., Tannenbaum A., Haker S., “Differential and numerically invariant signature curves applied to object recognition”, Int. J. Comput. Vis., 26 (1998), 107–135 | DOI

[10] Cartan E., La théorie des groupes finis et continus et la geómétrie différentielle traitées par la méthode du repère mobile, Gauthier-Villars, Paris, 1937

[11] Caviness B. F., Johnson J. R. (Eds.), Quantifier elimination and cylindrical algebraic decomposition, Texts and Monographs in Symbolic Computation, Springer-Verlag, Vienna, 1998 | DOI | MR

[12] Cox D., Little J., O'Shea D., Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra, Undergraduate Texts in Mathematics, 2nd ed., Springer-Verlag, New York, 1997 | DOI | MR

[13] Faugeras O., “Cartan's moving frame method and its application to the geometry and evolution of curves in the Euclidean, affine and projective planes”, Application of Invariance in Computer Vision, Springer-Verlag Lecture Notes in Computer Science, 825, eds. J. L. Mundy, A. Zisserman, D. Forsyth, Springer-Verlag, Berlin, 1994, 9–46 | DOI

[14] Faugeras O., Luong Q. T., The geometry of multiple images. The laws that govern the formation of multiple images of a scene and some of their applications, MIT Press, Cambridge, MA, 2001 | MR | Zbl

[15] Feldmar J., Ayache N., Betting F., “3D-2D projective registration of free-form curves and surfaces”, Proceedings of the Fifth International Conference on Computer Vision, ICCV'95, IEEE Computer Society, Washington, 1995, 549–556 | DOI

[16] Feng S., Kogan I., Krim H., “Classification of curves in 2D and 3D via affine integral signatures”, Acta Appl. Math., 109 (2010), 903–937, arXiv: 0806.1984 | DOI | MR | Zbl

[17] Fulton W., Algebraic curves. An introduction to algebraic geometry, Advanced Book Classics, Addison-Wesley Publishing Company, Redwood City, CA, 1989 | MR | Zbl

[18] Guggenheimer H. W., Differential geometry, McGraw-Hill, New York, 1963 | MR | Zbl

[19] Hann C. E., Hickman M. S., “Projective curvature and integral invariants”, Acta Appl. Math., 74 (2002), 177–193 | DOI | MR | Zbl

[20] Hartley R., Zisserman A., Multiple view geometry in computer vision, Cambridge University Press, Cambridge, 2001 | MR

[21] Hoff D., Olver P. J., “Extensions of invariant signatures for object recognition”, J. Math. Imaging Vision, 45 (2013), 176–185 | DOI

[22] Hong H. (Ed.), Comput. J., 36, Special issue on computational quantifier elimination (1993)

[23] Hubert E., Kogan I. A., “Smooth and algebraic invariants of a group action: local and global constructions”, Found. Comput. Math., 7 (2007), 455–493 | DOI | MR | Zbl

[24] Kogan I. A., “Two algorithms for a moving frame construction”, Canad. J. Math., 55 (2003), 266–291 | DOI | MR | Zbl

[25] Musso E., Nicolodi L., “Invariant signatures of closed planar curves”, J. Math. Imaging Vision, 35 (2009), 68–85 | DOI | MR

[26] Olver P. J., Applications of Lie groups to differential equations, Graduate Texts in Mathematics, 107, 2nd ed., Springer-Verlag, New York, 1993 | DOI | MR | Zbl

[27] Olver P. J., “Joint invariant signatures”, Found. Comput. Math., 1 (2001), 3–67 | DOI | MR

[28] Popov V. L., Vinberg E. B., “Invariant theory”, Algebraic geometry, v. IV, Encyclopaedia of Mathematical Sciences, 55, Linear algebraic groups. Invariant theory, eds. A. N. Parshin, I. R. Shafarevich, Springer-Verlag, Berlin, 1994, 122–278 | DOI | MR

[29] Sato J., Cipolla R., “Affine integral invariants for extracting symmetry axes”, Image Vision Comput., 15 (1997), 627–635 | DOI

[30] Tarski A., A decision method for elementary algebra and geometry, 2nd ed., University of California Press, Berkeley, 1951 | MR

[31] Taubin G., Cooper D. B., “Object recognition based on moment (or algebraic) invariants”, Geometric Invariance in Computer Vision, Artificial Intelligence, eds. J. L. Mundy, A. Zisserman, MIT Press, Cambridge, MA, 1992, 375–397 | MR

[32] Van Gool L. J., Moons T., Pauwels E., Oosterlinck A., “Semi-differential invariants”, Geometric Invariance in Computer Vision, Artificial Intelligence, eds. J. L. Mundy, A. Zisserman, MIT Press, Cambridge, MA, 1992, 157–192 | MR | Zbl

[33] Xu D., Li H., “3-D affine moment invariants generated by geometric primitives”, Proceedings of 18th International Conference on Pattern Recognition, v. 2, IEEE Computer Society, Washington, 2008, 544–547 | DOI