3D STRUCTURE RECONSTRUCTION FROM POINT CORRESPONDENCES BETWEEN 2 PERSPECTIVE PROJECTIONS

An iterative algorithm for 3D structure reconstruction from two perspe ctive projections is proposed. The basis of the method is the eight-po int algorithm (Longuet-Higgins, Nature 293(10), 1981, 133-135; Tsai an d Huang, IEEE Trans. PAMI 6, 1984, 13-27). A drawback of the eight-poi nt algorithm is that it requires at least eight point correspondences. Further, there are certain point configurations for which the algorit hm fails. For example, the eight corners of a cube on a quadratic surf ace passing through the focal points of the cameras form such a degene rate configuration. By combining the eight-point algorithm with an SVD (singular value decomposition) characterization of the so-called E-ma trix (Faugeras and Maybank, Internat. J. Comput. Vision 4, 1990, 225-2 46; Huang and Faugeras, IEEE Trans. PAMI 11, 1989, 1310-1312), the pro posed iterative algorithm solves the 3D reconstruction problem even fr om less than eight points. The algorithm is also free from the artific ial degeneracy problem inherent to the eight-point algorithm. The iter ation in the algorithm takes place only if the configuration is degene rate or violates the SVD characterization due to measurement error. Ot herwise the computation is O(N) as in the eight-point algorithm. (C) 1 994 Academic Press, Inc.