Abstract

The standard approach to the motion and structure estimation problem consists of two stages: (1) using the eight-point algorithm to estimate the nine essential parameters defined up to a scale factor and (2) refining the motion estimation based on some statistically optimal criteria, which is a nonlinear estimation problem on a five-dimensional space. Unfortunately, the results obtained are often not satisfactory. The problem is that the second stage is very sensitive to the initial guess and that it is very difficult to obtain a precise initial estimate from the first stage. This is because one performs a projection of a set of quantities that are estimated in a space of eight dimensions (by neglecting the constraints on the essential parameters), a much higher dimension than that of the real space, which is five dimensional. A novel approach is proposed by the introduction of an intermediate stage, which consists in estimating a 3×3 matrix defined up to a scale factor by imposing the rank-2 constraint (the matrix has seven independent parameters and is known as the fundamental matrix). The idea is to project parameters estimated in a high-dimensional space gradually onto a slightly lower-dimensional space, namely, from eight dimensions to seven and finally to five. The proposed approach has been tested with synthetic and real data, and a considerable improvement has been observed. The conjecture is that the imposition of the constraints arising from projective geometry should be used as an intermediate step to obtain reliable three-dimensional Euclidean motion and structure estimation from multiple calibrated images. The software is available on the Internet.

© 1997 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. H. Nagel, “Image sequences—ten (octal) years—from phenomenology towards a theoretical foundation,” in Proceedings of the 8th International Conference on Pattern Recognition, J.-C. Simon, J.-P. Haton, eds. (Institute of Electrical and Electronic Engineers, New York, 1986), pp. 1174–1185.
  2. J. K. Aggarwal, N. Nandhakumar, “On the computation of motion from sequences of images—a review,” Proc. IEEE 76, 917–935 (1988).
    [CrossRef]
  3. T. S. Huang, A. N. Netravali, “Motion and structure from feature correspondences: a review,” Proc. IEEE 82, 252–268 (1994).
    [CrossRef]
  4. Z. Zhang, “Estimating motion and structure from correspondences of line segmentsbetween two perspective images,” IEEE Trans. Pattern Anal. Mach. Intell. 17, 1129–1139 (1995).
    [CrossRef]
  5. H. C. Longuet-Higgins, “A computer algorithm for reconstructing a scene from two projections,” Nature (London) 293, 133–135 (1981).
    [CrossRef]
  6. R. Y. Tsai, T. S. Huang, “Uniqueness and estimation of three-dimensional motion parameters ofrigid objects with curved surface,” IEEE Trans. Pattern Anal. Mach. Intell. 6, 13–26 (1984).
    [CrossRef] [PubMed]
  7. O. Faugeras, S. Maybank, “Motion from point matches: multiplicity of solutions,” Int. J. Comput. Vision 4, 225–246 (1990).
    [CrossRef]
  8. S. J. Maybank, Theory of Reconstruction from Image Motion (Springer-Verlag, Berlin, 1992).
  9. O. Faugeras, Three-Dimensional Computer Vision: A Geometric Viewpoint (MIT Press, Cambridge, Mass., 1993).
  10. M. E. Spetsakis, Y. Aloimonos, “Optimal visual motion estimation: a note,” IEEE Trans. Pattern Anal. Mach. Intell. 14, 959–964 (1992).
    [CrossRef]
  11. J. Weng, N. Ahuja, T. S. Huang, “Optimal motion and structure estimation,” IEEE Trans. Pattern Anal. Mach. Intell. 15, 864–884 (1993).
    [CrossRef]
  12. K. Kanatani, Statistical Optimization for Geometric Computation: Theory and Practice (Elsevier, Amsterdam, 1996).
  13. Z. Zhang, “An automatic and robust algorithm for determining motion and structure from two perspective images,” in Proceedings of the 6th International Conference on Computer Analysis of Images and Patterns, V. Hlavac, R. Sara, eds. (Springer-Verlag, Berlin, 1995), pp. 174–181.
  14. P. Torr, “Motion segmentation and outlier detection,” Ph.D thesis (Department of Engineering Science, University of Oxford, 1995).
  15. S. Ullman, The Interpretation of Visual Motion (MIT Press, Cambridge, Mass., 1979).
  16. T. S. Huang, C. H. Lee, “Motion and structure from orthographic projections,” IEEE Trans. Pattern Anal. Mach. Intell. 11, 536–540 (1989).
    [CrossRef]
  17. J. J. Koenderink, A. J. van Doorn, “Affine structure from motion,” J. Opt. Soc. Am. A 8, 377–385 (1991).
    [CrossRef] [PubMed]
  18. L. S. Shapiro, A. Zisserman, M. Brady, “3D motion recovery via affine epipolar geometry,” Int. J. Comput. Vision 16, 147–182 (1995).
    [CrossRef]
  19. M. D. Pritt, “Structure and motion from two orthographic views,” J. Opt. Soc. Am. A 13, 916–921 (1996).
    [CrossRef]
  20. T. J. Broida, S. Chandrashekhar, R. Chellappa, “Recursive 3-D motion estimation from a monocular image sequence,” IEEE Trans. Aerosp. Electron. Syst. 26, 639–656 (1990).
    [CrossRef]
  21. Z. Zhang, O. D. Faugeras, “Motion and structure from motion from a long monocular sequence,” in Progress in Image Analysis and Processing II, V. Cantoni, M. Ferretti, S. Levialdi, R. Negrini, R. Stefanelli, eds. (World Scientific, Singapore, 1991), pp. 264–271.
  22. C. Tomasi, T. Kanade, “Shape and motion from image streams under orthography: a factorizationmethod,” Int. J. Comput. Vision 9, 137–154 (1992).
    [CrossRef]
  23. J. Oliensis, J. I. Thomas, “Incorporating motion error in multi-frame structure from motion,” in Proceedings of the IEEE Workshop on Visual Motion, T. S. Huang, P. J. Burt, E. H. Adelson, eds. (IEEE Computer Society Press, Los Alamitos, Calif., 1991), pp. 8–13.
  24. R. Szeliski, S. B. Kang, “Recovering 3D shape and motion from image streams using nonlinear leastsquares,” J. Visual Commun. Image Represent. 5, 10–28 (1994).
    [CrossRef]
  25. S. Soatto, R. Frezza, P. Perona, “Motion estimation on the essential manifold,” in Proceedings of the 3rd European Conference on Computer Vision, Vol. II of Lecture Notes in Computer Science, J-O. Eklundh, ed. (Springer-Verlag, Berlin, 1994), pp. 61–72.
  26. M. Lee, G. Medioni, R. Deriche, “Structure and motion from a sparse set of views,” presented at the IEEE International Symposium on Computer Vision, Coral Gables, Fla., November 1995.
  27. C. Braccini, G. Gambardella, A. Grattarola, S. Zappatore, “Motion estimation of rigid bodies: effects of the rigidity constraints,” in Proceedings of EUSIPCO, Signal Processing III: Theories and Applications, L. Torres, E. Masgrau, M. A. Lagunas, eds. (Elsevier North-Holland, Amsterdam, 1986), pp. 645–648.
  28. J. Oliensis, V. Govindu, “Experimental evaluation of projective reconstruction in structure from motion,” Tech. Rep. (NEC Research Institute, Princeton, N.J., 1995).
  29. Z. Zhang, “A new multistage approach to motion and structure estimation: from essential parameters to Euclidean motion via fundamental matrix,” (Institut National de Recherche en Informatique et Automatique, Sophia-Antipolis, France, 1996). The complete software can be checked out from my home page: http://www.inria.fr/robotvis/personnel/zzhang/zzhang-eng.html .
  30. K. Kanatani, “Automatic singularity test for motion analysis by an information criterion,” in Proceedings of the 4th European Conference on Computer Vision, B. Buxton, ed. (Springer-Verlag, Berlin, 1996), pp. 697–708.
  31. Q.-T. Luong, O. D. Faugeras, “The fundamental matrix: theory, algorithms and stability analysis,” Int. J. Comput. Vision 1, 43–76 (1996).
    [CrossRef]
  32. O. Faugeras, “Stratification of 3-D vision: projective, affine, and metric representations,” J. Opt. Soc. Am. A 12, 465–484 (1995).
    [CrossRef]
  33. T. S. Huang, O. D. Faugeras, “Some properties of the E matrix in two-view motion estimation,” IEEE Trans. Pattern Anal. Mach. Intell. 11, 1310–1312 (1989).
    [CrossRef]
  34. B. K. P. Horn, “Motion fields are hardly ever ambiguous,” Int. J. Comput. Vision 1, 263–278 (1987).
  35. H. C. Longuet-Higgins, “Multiple interpretations of a pair of images of a surface,” Proc. R. Soc. London Ser. A 418, 1–15 (1988).
    [CrossRef]
  36. C.-H. Lee, “Time-varying images: the effect of finite resolution on uniqueness,” CVGIP: Image Understand. 54, 325–332 (1991).
    [CrossRef]
  37. J. J. More, “The Levenberg–Marquardt algorithm, implementation and theory,” in Numerical Analysis, Lecture Notes in Mathematics 630, G. A. Watson, ed. (Springer-Verlag, Berlin, 1977).
  38. G. H. Golub, C. F. Van Loan, Matrix Computations, 2nd ed. (John Hopkins U. Press, Baltimore, Md., 1989).
  39. Z. Zhang, R. Deriche, O. Faugeras, Q.-T. Luong, “A robust technique for matching two uncalibrated images through therecovery of the unknown epipolar geometry,” Artif. Intel. 78, 87–119 (1995).
    [CrossRef]
  40. P. J. Huber, Robust Statistics (Wiley, New York, 1981).
  41. P. J. Rousseeuw, A. M. Leroy, Robust Regression and Outlier Detection (Wiley, New York, 1987).

1996 (2)

M. D. Pritt, “Structure and motion from two orthographic views,” J. Opt. Soc. Am. A 13, 916–921 (1996).
[CrossRef]

Q.-T. Luong, O. D. Faugeras, “The fundamental matrix: theory, algorithms and stability analysis,” Int. J. Comput. Vision 1, 43–76 (1996).
[CrossRef]

1995 (4)

O. Faugeras, “Stratification of 3-D vision: projective, affine, and metric representations,” J. Opt. Soc. Am. A 12, 465–484 (1995).
[CrossRef]

Z. Zhang, “Estimating motion and structure from correspondences of line segmentsbetween two perspective images,” IEEE Trans. Pattern Anal. Mach. Intell. 17, 1129–1139 (1995).
[CrossRef]

L. S. Shapiro, A. Zisserman, M. Brady, “3D motion recovery via affine epipolar geometry,” Int. J. Comput. Vision 16, 147–182 (1995).
[CrossRef]

Z. Zhang, R. Deriche, O. Faugeras, Q.-T. Luong, “A robust technique for matching two uncalibrated images through therecovery of the unknown epipolar geometry,” Artif. Intel. 78, 87–119 (1995).
[CrossRef]

1994 (2)

R. Szeliski, S. B. Kang, “Recovering 3D shape and motion from image streams using nonlinear leastsquares,” J. Visual Commun. Image Represent. 5, 10–28 (1994).
[CrossRef]

T. S. Huang, A. N. Netravali, “Motion and structure from feature correspondences: a review,” Proc. IEEE 82, 252–268 (1994).
[CrossRef]

1993 (1)

J. Weng, N. Ahuja, T. S. Huang, “Optimal motion and structure estimation,” IEEE Trans. Pattern Anal. Mach. Intell. 15, 864–884 (1993).
[CrossRef]

1992 (2)

M. E. Spetsakis, Y. Aloimonos, “Optimal visual motion estimation: a note,” IEEE Trans. Pattern Anal. Mach. Intell. 14, 959–964 (1992).
[CrossRef]

C. Tomasi, T. Kanade, “Shape and motion from image streams under orthography: a factorizationmethod,” Int. J. Comput. Vision 9, 137–154 (1992).
[CrossRef]

1991 (2)

C.-H. Lee, “Time-varying images: the effect of finite resolution on uniqueness,” CVGIP: Image Understand. 54, 325–332 (1991).
[CrossRef]

J. J. Koenderink, A. J. van Doorn, “Affine structure from motion,” J. Opt. Soc. Am. A 8, 377–385 (1991).
[CrossRef] [PubMed]

1990 (2)

T. J. Broida, S. Chandrashekhar, R. Chellappa, “Recursive 3-D motion estimation from a monocular image sequence,” IEEE Trans. Aerosp. Electron. Syst. 26, 639–656 (1990).
[CrossRef]

O. Faugeras, S. Maybank, “Motion from point matches: multiplicity of solutions,” Int. J. Comput. Vision 4, 225–246 (1990).
[CrossRef]

1989 (2)

T. S. Huang, C. H. Lee, “Motion and structure from orthographic projections,” IEEE Trans. Pattern Anal. Mach. Intell. 11, 536–540 (1989).
[CrossRef]

T. S. Huang, O. D. Faugeras, “Some properties of the E matrix in two-view motion estimation,” IEEE Trans. Pattern Anal. Mach. Intell. 11, 1310–1312 (1989).
[CrossRef]

1988 (2)

J. K. Aggarwal, N. Nandhakumar, “On the computation of motion from sequences of images—a review,” Proc. IEEE 76, 917–935 (1988).
[CrossRef]

H. C. Longuet-Higgins, “Multiple interpretations of a pair of images of a surface,” Proc. R. Soc. London Ser. A 418, 1–15 (1988).
[CrossRef]

1987 (1)

B. K. P. Horn, “Motion fields are hardly ever ambiguous,” Int. J. Comput. Vision 1, 263–278 (1987).

1984 (1)

R. Y. Tsai, T. S. Huang, “Uniqueness and estimation of three-dimensional motion parameters ofrigid objects with curved surface,” IEEE Trans. Pattern Anal. Mach. Intell. 6, 13–26 (1984).
[CrossRef] [PubMed]

1981 (1)

H. C. Longuet-Higgins, “A computer algorithm for reconstructing a scene from two projections,” Nature (London) 293, 133–135 (1981).
[CrossRef]

Aggarwal, J. K.

J. K. Aggarwal, N. Nandhakumar, “On the computation of motion from sequences of images—a review,” Proc. IEEE 76, 917–935 (1988).
[CrossRef]

Ahuja, N.

J. Weng, N. Ahuja, T. S. Huang, “Optimal motion and structure estimation,” IEEE Trans. Pattern Anal. Mach. Intell. 15, 864–884 (1993).
[CrossRef]

Aloimonos, Y.

M. E. Spetsakis, Y. Aloimonos, “Optimal visual motion estimation: a note,” IEEE Trans. Pattern Anal. Mach. Intell. 14, 959–964 (1992).
[CrossRef]

Braccini, C.

C. Braccini, G. Gambardella, A. Grattarola, S. Zappatore, “Motion estimation of rigid bodies: effects of the rigidity constraints,” in Proceedings of EUSIPCO, Signal Processing III: Theories and Applications, L. Torres, E. Masgrau, M. A. Lagunas, eds. (Elsevier North-Holland, Amsterdam, 1986), pp. 645–648.

Brady, M.

L. S. Shapiro, A. Zisserman, M. Brady, “3D motion recovery via affine epipolar geometry,” Int. J. Comput. Vision 16, 147–182 (1995).
[CrossRef]

Broida, T. J.

T. J. Broida, S. Chandrashekhar, R. Chellappa, “Recursive 3-D motion estimation from a monocular image sequence,” IEEE Trans. Aerosp. Electron. Syst. 26, 639–656 (1990).
[CrossRef]

Chandrashekhar, S.

T. J. Broida, S. Chandrashekhar, R. Chellappa, “Recursive 3-D motion estimation from a monocular image sequence,” IEEE Trans. Aerosp. Electron. Syst. 26, 639–656 (1990).
[CrossRef]

Chellappa, R.

T. J. Broida, S. Chandrashekhar, R. Chellappa, “Recursive 3-D motion estimation from a monocular image sequence,” IEEE Trans. Aerosp. Electron. Syst. 26, 639–656 (1990).
[CrossRef]

Deriche, R.

Z. Zhang, R. Deriche, O. Faugeras, Q.-T. Luong, “A robust technique for matching two uncalibrated images through therecovery of the unknown epipolar geometry,” Artif. Intel. 78, 87–119 (1995).
[CrossRef]

M. Lee, G. Medioni, R. Deriche, “Structure and motion from a sparse set of views,” presented at the IEEE International Symposium on Computer Vision, Coral Gables, Fla., November 1995.

Faugeras, O.

Z. Zhang, R. Deriche, O. Faugeras, Q.-T. Luong, “A robust technique for matching two uncalibrated images through therecovery of the unknown epipolar geometry,” Artif. Intel. 78, 87–119 (1995).
[CrossRef]

O. Faugeras, “Stratification of 3-D vision: projective, affine, and metric representations,” J. Opt. Soc. Am. A 12, 465–484 (1995).
[CrossRef]

O. Faugeras, S. Maybank, “Motion from point matches: multiplicity of solutions,” Int. J. Comput. Vision 4, 225–246 (1990).
[CrossRef]

O. Faugeras, Three-Dimensional Computer Vision: A Geometric Viewpoint (MIT Press, Cambridge, Mass., 1993).

Faugeras, O. D.

Q.-T. Luong, O. D. Faugeras, “The fundamental matrix: theory, algorithms and stability analysis,” Int. J. Comput. Vision 1, 43–76 (1996).
[CrossRef]

T. S. Huang, O. D. Faugeras, “Some properties of the E matrix in two-view motion estimation,” IEEE Trans. Pattern Anal. Mach. Intell. 11, 1310–1312 (1989).
[CrossRef]

Z. Zhang, O. D. Faugeras, “Motion and structure from motion from a long monocular sequence,” in Progress in Image Analysis and Processing II, V. Cantoni, M. Ferretti, S. Levialdi, R. Negrini, R. Stefanelli, eds. (World Scientific, Singapore, 1991), pp. 264–271.

Frezza, R.

S. Soatto, R. Frezza, P. Perona, “Motion estimation on the essential manifold,” in Proceedings of the 3rd European Conference on Computer Vision, Vol. II of Lecture Notes in Computer Science, J-O. Eklundh, ed. (Springer-Verlag, Berlin, 1994), pp. 61–72.

Gambardella, G.

C. Braccini, G. Gambardella, A. Grattarola, S. Zappatore, “Motion estimation of rigid bodies: effects of the rigidity constraints,” in Proceedings of EUSIPCO, Signal Processing III: Theories and Applications, L. Torres, E. Masgrau, M. A. Lagunas, eds. (Elsevier North-Holland, Amsterdam, 1986), pp. 645–648.

Golub, G. H.

G. H. Golub, C. F. Van Loan, Matrix Computations, 2nd ed. (John Hopkins U. Press, Baltimore, Md., 1989).

Govindu, V.

J. Oliensis, V. Govindu, “Experimental evaluation of projective reconstruction in structure from motion,” Tech. Rep. (NEC Research Institute, Princeton, N.J., 1995).

Grattarola, A.

C. Braccini, G. Gambardella, A. Grattarola, S. Zappatore, “Motion estimation of rigid bodies: effects of the rigidity constraints,” in Proceedings of EUSIPCO, Signal Processing III: Theories and Applications, L. Torres, E. Masgrau, M. A. Lagunas, eds. (Elsevier North-Holland, Amsterdam, 1986), pp. 645–648.

Horn, B. K. P.

B. K. P. Horn, “Motion fields are hardly ever ambiguous,” Int. J. Comput. Vision 1, 263–278 (1987).

Huang, T. S.

T. S. Huang, A. N. Netravali, “Motion and structure from feature correspondences: a review,” Proc. IEEE 82, 252–268 (1994).
[CrossRef]

J. Weng, N. Ahuja, T. S. Huang, “Optimal motion and structure estimation,” IEEE Trans. Pattern Anal. Mach. Intell. 15, 864–884 (1993).
[CrossRef]

T. S. Huang, C. H. Lee, “Motion and structure from orthographic projections,” IEEE Trans. Pattern Anal. Mach. Intell. 11, 536–540 (1989).
[CrossRef]

T. S. Huang, O. D. Faugeras, “Some properties of the E matrix in two-view motion estimation,” IEEE Trans. Pattern Anal. Mach. Intell. 11, 1310–1312 (1989).
[CrossRef]

R. Y. Tsai, T. S. Huang, “Uniqueness and estimation of three-dimensional motion parameters ofrigid objects with curved surface,” IEEE Trans. Pattern Anal. Mach. Intell. 6, 13–26 (1984).
[CrossRef] [PubMed]

Huber, P. J.

P. J. Huber, Robust Statistics (Wiley, New York, 1981).

Kanade, T.

C. Tomasi, T. Kanade, “Shape and motion from image streams under orthography: a factorizationmethod,” Int. J. Comput. Vision 9, 137–154 (1992).
[CrossRef]

Kanatani, K.

K. Kanatani, “Automatic singularity test for motion analysis by an information criterion,” in Proceedings of the 4th European Conference on Computer Vision, B. Buxton, ed. (Springer-Verlag, Berlin, 1996), pp. 697–708.

K. Kanatani, Statistical Optimization for Geometric Computation: Theory and Practice (Elsevier, Amsterdam, 1996).

Kang, S. B.

R. Szeliski, S. B. Kang, “Recovering 3D shape and motion from image streams using nonlinear leastsquares,” J. Visual Commun. Image Represent. 5, 10–28 (1994).
[CrossRef]

Koenderink, J. J.

Lee, C. H.

T. S. Huang, C. H. Lee, “Motion and structure from orthographic projections,” IEEE Trans. Pattern Anal. Mach. Intell. 11, 536–540 (1989).
[CrossRef]

Lee, C.-H.

C.-H. Lee, “Time-varying images: the effect of finite resolution on uniqueness,” CVGIP: Image Understand. 54, 325–332 (1991).
[CrossRef]

Lee, M.

M. Lee, G. Medioni, R. Deriche, “Structure and motion from a sparse set of views,” presented at the IEEE International Symposium on Computer Vision, Coral Gables, Fla., November 1995.

Leroy, A. M.

P. J. Rousseeuw, A. M. Leroy, Robust Regression and Outlier Detection (Wiley, New York, 1987).

Longuet-Higgins, H. C.

H. C. Longuet-Higgins, “Multiple interpretations of a pair of images of a surface,” Proc. R. Soc. London Ser. A 418, 1–15 (1988).
[CrossRef]

H. C. Longuet-Higgins, “A computer algorithm for reconstructing a scene from two projections,” Nature (London) 293, 133–135 (1981).
[CrossRef]

Luong, Q.-T.

Q.-T. Luong, O. D. Faugeras, “The fundamental matrix: theory, algorithms and stability analysis,” Int. J. Comput. Vision 1, 43–76 (1996).
[CrossRef]

Z. Zhang, R. Deriche, O. Faugeras, Q.-T. Luong, “A robust technique for matching two uncalibrated images through therecovery of the unknown epipolar geometry,” Artif. Intel. 78, 87–119 (1995).
[CrossRef]

Maybank, S.

O. Faugeras, S. Maybank, “Motion from point matches: multiplicity of solutions,” Int. J. Comput. Vision 4, 225–246 (1990).
[CrossRef]

Maybank, S. J.

S. J. Maybank, Theory of Reconstruction from Image Motion (Springer-Verlag, Berlin, 1992).

Medioni, G.

M. Lee, G. Medioni, R. Deriche, “Structure and motion from a sparse set of views,” presented at the IEEE International Symposium on Computer Vision, Coral Gables, Fla., November 1995.

More, J. J.

J. J. More, “The Levenberg–Marquardt algorithm, implementation and theory,” in Numerical Analysis, Lecture Notes in Mathematics 630, G. A. Watson, ed. (Springer-Verlag, Berlin, 1977).

Nagel, H.

H. Nagel, “Image sequences—ten (octal) years—from phenomenology towards a theoretical foundation,” in Proceedings of the 8th International Conference on Pattern Recognition, J.-C. Simon, J.-P. Haton, eds. (Institute of Electrical and Electronic Engineers, New York, 1986), pp. 1174–1185.

Nandhakumar, N.

J. K. Aggarwal, N. Nandhakumar, “On the computation of motion from sequences of images—a review,” Proc. IEEE 76, 917–935 (1988).
[CrossRef]

Netravali, A. N.

T. S. Huang, A. N. Netravali, “Motion and structure from feature correspondences: a review,” Proc. IEEE 82, 252–268 (1994).
[CrossRef]

Oliensis, J.

J. Oliensis, V. Govindu, “Experimental evaluation of projective reconstruction in structure from motion,” Tech. Rep. (NEC Research Institute, Princeton, N.J., 1995).

J. Oliensis, J. I. Thomas, “Incorporating motion error in multi-frame structure from motion,” in Proceedings of the IEEE Workshop on Visual Motion, T. S. Huang, P. J. Burt, E. H. Adelson, eds. (IEEE Computer Society Press, Los Alamitos, Calif., 1991), pp. 8–13.

Perona, P.

S. Soatto, R. Frezza, P. Perona, “Motion estimation on the essential manifold,” in Proceedings of the 3rd European Conference on Computer Vision, Vol. II of Lecture Notes in Computer Science, J-O. Eklundh, ed. (Springer-Verlag, Berlin, 1994), pp. 61–72.

Pritt, M. D.

Rousseeuw, P. J.

P. J. Rousseeuw, A. M. Leroy, Robust Regression and Outlier Detection (Wiley, New York, 1987).

Shapiro, L. S.

L. S. Shapiro, A. Zisserman, M. Brady, “3D motion recovery via affine epipolar geometry,” Int. J. Comput. Vision 16, 147–182 (1995).
[CrossRef]

Soatto, S.

S. Soatto, R. Frezza, P. Perona, “Motion estimation on the essential manifold,” in Proceedings of the 3rd European Conference on Computer Vision, Vol. II of Lecture Notes in Computer Science, J-O. Eklundh, ed. (Springer-Verlag, Berlin, 1994), pp. 61–72.

Spetsakis, M. E.

M. E. Spetsakis, Y. Aloimonos, “Optimal visual motion estimation: a note,” IEEE Trans. Pattern Anal. Mach. Intell. 14, 959–964 (1992).
[CrossRef]

Szeliski, R.

R. Szeliski, S. B. Kang, “Recovering 3D shape and motion from image streams using nonlinear leastsquares,” J. Visual Commun. Image Represent. 5, 10–28 (1994).
[CrossRef]

Thomas, J. I.

J. Oliensis, J. I. Thomas, “Incorporating motion error in multi-frame structure from motion,” in Proceedings of the IEEE Workshop on Visual Motion, T. S. Huang, P. J. Burt, E. H. Adelson, eds. (IEEE Computer Society Press, Los Alamitos, Calif., 1991), pp. 8–13.

Tomasi, C.

C. Tomasi, T. Kanade, “Shape and motion from image streams under orthography: a factorizationmethod,” Int. J. Comput. Vision 9, 137–154 (1992).
[CrossRef]

Torr, P.

P. Torr, “Motion segmentation and outlier detection,” Ph.D thesis (Department of Engineering Science, University of Oxford, 1995).

Tsai, R. Y.

R. Y. Tsai, T. S. Huang, “Uniqueness and estimation of three-dimensional motion parameters ofrigid objects with curved surface,” IEEE Trans. Pattern Anal. Mach. Intell. 6, 13–26 (1984).
[CrossRef] [PubMed]

Ullman, S.

S. Ullman, The Interpretation of Visual Motion (MIT Press, Cambridge, Mass., 1979).

van Doorn, A. J.

Van Loan, C. F.

G. H. Golub, C. F. Van Loan, Matrix Computations, 2nd ed. (John Hopkins U. Press, Baltimore, Md., 1989).

Weng, J.

J. Weng, N. Ahuja, T. S. Huang, “Optimal motion and structure estimation,” IEEE Trans. Pattern Anal. Mach. Intell. 15, 864–884 (1993).
[CrossRef]

Zappatore, S.

C. Braccini, G. Gambardella, A. Grattarola, S. Zappatore, “Motion estimation of rigid bodies: effects of the rigidity constraints,” in Proceedings of EUSIPCO, Signal Processing III: Theories and Applications, L. Torres, E. Masgrau, M. A. Lagunas, eds. (Elsevier North-Holland, Amsterdam, 1986), pp. 645–648.

Zhang, Z.

Z. Zhang, R. Deriche, O. Faugeras, Q.-T. Luong, “A robust technique for matching two uncalibrated images through therecovery of the unknown epipolar geometry,” Artif. Intel. 78, 87–119 (1995).
[CrossRef]

Z. Zhang, “Estimating motion and structure from correspondences of line segmentsbetween two perspective images,” IEEE Trans. Pattern Anal. Mach. Intell. 17, 1129–1139 (1995).
[CrossRef]

Z. Zhang, “An automatic and robust algorithm for determining motion and structure from two perspective images,” in Proceedings of the 6th International Conference on Computer Analysis of Images and Patterns, V. Hlavac, R. Sara, eds. (Springer-Verlag, Berlin, 1995), pp. 174–181.

Z. Zhang, O. D. Faugeras, “Motion and structure from motion from a long monocular sequence,” in Progress in Image Analysis and Processing II, V. Cantoni, M. Ferretti, S. Levialdi, R. Negrini, R. Stefanelli, eds. (World Scientific, Singapore, 1991), pp. 264–271.

Z. Zhang, “A new multistage approach to motion and structure estimation: from essential parameters to Euclidean motion via fundamental matrix,” (Institut National de Recherche en Informatique et Automatique, Sophia-Antipolis, France, 1996). The complete software can be checked out from my home page: http://www.inria.fr/robotvis/personnel/zzhang/zzhang-eng.html .

Zisserman, A.

L. S. Shapiro, A. Zisserman, M. Brady, “3D motion recovery via affine epipolar geometry,” Int. J. Comput. Vision 16, 147–182 (1995).
[CrossRef]

Artif. Intel. (1)

Z. Zhang, R. Deriche, O. Faugeras, Q.-T. Luong, “A robust technique for matching two uncalibrated images through therecovery of the unknown epipolar geometry,” Artif. Intel. 78, 87–119 (1995).
[CrossRef]

CVGIP: Image Understand. (1)

C.-H. Lee, “Time-varying images: the effect of finite resolution on uniqueness,” CVGIP: Image Understand. 54, 325–332 (1991).
[CrossRef]

IEEE Trans. Aerosp. Electron. Syst. (1)

T. J. Broida, S. Chandrashekhar, R. Chellappa, “Recursive 3-D motion estimation from a monocular image sequence,” IEEE Trans. Aerosp. Electron. Syst. 26, 639–656 (1990).
[CrossRef]

IEEE Trans. Pattern Anal. Mach. Intell. (6)

T. S. Huang, O. D. Faugeras, “Some properties of the E matrix in two-view motion estimation,” IEEE Trans. Pattern Anal. Mach. Intell. 11, 1310–1312 (1989).
[CrossRef]

Z. Zhang, “Estimating motion and structure from correspondences of line segmentsbetween two perspective images,” IEEE Trans. Pattern Anal. Mach. Intell. 17, 1129–1139 (1995).
[CrossRef]

R. Y. Tsai, T. S. Huang, “Uniqueness and estimation of three-dimensional motion parameters ofrigid objects with curved surface,” IEEE Trans. Pattern Anal. Mach. Intell. 6, 13–26 (1984).
[CrossRef] [PubMed]

M. E. Spetsakis, Y. Aloimonos, “Optimal visual motion estimation: a note,” IEEE Trans. Pattern Anal. Mach. Intell. 14, 959–964 (1992).
[CrossRef]

J. Weng, N. Ahuja, T. S. Huang, “Optimal motion and structure estimation,” IEEE Trans. Pattern Anal. Mach. Intell. 15, 864–884 (1993).
[CrossRef]

T. S. Huang, C. H. Lee, “Motion and structure from orthographic projections,” IEEE Trans. Pattern Anal. Mach. Intell. 11, 536–540 (1989).
[CrossRef]

Int. J. Comput. Vision (5)

L. S. Shapiro, A. Zisserman, M. Brady, “3D motion recovery via affine epipolar geometry,” Int. J. Comput. Vision 16, 147–182 (1995).
[CrossRef]

O. Faugeras, S. Maybank, “Motion from point matches: multiplicity of solutions,” Int. J. Comput. Vision 4, 225–246 (1990).
[CrossRef]

B. K. P. Horn, “Motion fields are hardly ever ambiguous,” Int. J. Comput. Vision 1, 263–278 (1987).

Q.-T. Luong, O. D. Faugeras, “The fundamental matrix: theory, algorithms and stability analysis,” Int. J. Comput. Vision 1, 43–76 (1996).
[CrossRef]

C. Tomasi, T. Kanade, “Shape and motion from image streams under orthography: a factorizationmethod,” Int. J. Comput. Vision 9, 137–154 (1992).
[CrossRef]

J. Opt. Soc. Am. A (3)

J. Visual Commun. Image Represent. (1)

R. Szeliski, S. B. Kang, “Recovering 3D shape and motion from image streams using nonlinear leastsquares,” J. Visual Commun. Image Represent. 5, 10–28 (1994).
[CrossRef]

Nature (London) (1)

H. C. Longuet-Higgins, “A computer algorithm for reconstructing a scene from two projections,” Nature (London) 293, 133–135 (1981).
[CrossRef]

Proc. IEEE (2)

J. K. Aggarwal, N. Nandhakumar, “On the computation of motion from sequences of images—a review,” Proc. IEEE 76, 917–935 (1988).
[CrossRef]

T. S. Huang, A. N. Netravali, “Motion and structure from feature correspondences: a review,” Proc. IEEE 82, 252–268 (1994).
[CrossRef]

Proc. R. Soc. London Ser. A (1)

H. C. Longuet-Higgins, “Multiple interpretations of a pair of images of a surface,” Proc. R. Soc. London Ser. A 418, 1–15 (1988).
[CrossRef]

Other (19)

J. J. More, “The Levenberg–Marquardt algorithm, implementation and theory,” in Numerical Analysis, Lecture Notes in Mathematics 630, G. A. Watson, ed. (Springer-Verlag, Berlin, 1977).

G. H. Golub, C. F. Van Loan, Matrix Computations, 2nd ed. (John Hopkins U. Press, Baltimore, Md., 1989).

P. J. Huber, Robust Statistics (Wiley, New York, 1981).

P. J. Rousseeuw, A. M. Leroy, Robust Regression and Outlier Detection (Wiley, New York, 1987).

S. Soatto, R. Frezza, P. Perona, “Motion estimation on the essential manifold,” in Proceedings of the 3rd European Conference on Computer Vision, Vol. II of Lecture Notes in Computer Science, J-O. Eklundh, ed. (Springer-Verlag, Berlin, 1994), pp. 61–72.

M. Lee, G. Medioni, R. Deriche, “Structure and motion from a sparse set of views,” presented at the IEEE International Symposium on Computer Vision, Coral Gables, Fla., November 1995.

C. Braccini, G. Gambardella, A. Grattarola, S. Zappatore, “Motion estimation of rigid bodies: effects of the rigidity constraints,” in Proceedings of EUSIPCO, Signal Processing III: Theories and Applications, L. Torres, E. Masgrau, M. A. Lagunas, eds. (Elsevier North-Holland, Amsterdam, 1986), pp. 645–648.

J. Oliensis, V. Govindu, “Experimental evaluation of projective reconstruction in structure from motion,” Tech. Rep. (NEC Research Institute, Princeton, N.J., 1995).

Z. Zhang, “A new multistage approach to motion and structure estimation: from essential parameters to Euclidean motion via fundamental matrix,” (Institut National de Recherche en Informatique et Automatique, Sophia-Antipolis, France, 1996). The complete software can be checked out from my home page: http://www.inria.fr/robotvis/personnel/zzhang/zzhang-eng.html .

K. Kanatani, “Automatic singularity test for motion analysis by an information criterion,” in Proceedings of the 4th European Conference on Computer Vision, B. Buxton, ed. (Springer-Verlag, Berlin, 1996), pp. 697–708.

J. Oliensis, J. I. Thomas, “Incorporating motion error in multi-frame structure from motion,” in Proceedings of the IEEE Workshop on Visual Motion, T. S. Huang, P. J. Burt, E. H. Adelson, eds. (IEEE Computer Society Press, Los Alamitos, Calif., 1991), pp. 8–13.

Z. Zhang, O. D. Faugeras, “Motion and structure from motion from a long monocular sequence,” in Progress in Image Analysis and Processing II, V. Cantoni, M. Ferretti, S. Levialdi, R. Negrini, R. Stefanelli, eds. (World Scientific, Singapore, 1991), pp. 264–271.

S. J. Maybank, Theory of Reconstruction from Image Motion (Springer-Verlag, Berlin, 1992).

O. Faugeras, Three-Dimensional Computer Vision: A Geometric Viewpoint (MIT Press, Cambridge, Mass., 1993).

K. Kanatani, Statistical Optimization for Geometric Computation: Theory and Practice (Elsevier, Amsterdam, 1996).

Z. Zhang, “An automatic and robust algorithm for determining motion and structure from two perspective images,” in Proceedings of the 6th International Conference on Computer Analysis of Images and Patterns, V. Hlavac, R. Sara, eds. (Springer-Verlag, Berlin, 1995), pp. 174–181.

P. Torr, “Motion segmentation and outlier detection,” Ph.D thesis (Department of Engineering Science, University of Oxford, 1995).

S. Ullman, The Interpretation of Visual Motion (MIT Press, Cambridge, Mass., 1979).

H. Nagel, “Image sequences—ten (octal) years—from phenomenology towards a theoretical foundation,” in Proceedings of the 8th International Conference on Pattern Recognition, J.-C. Simon, J.-P. Haton, eds. (Institute of Electrical and Electronic Engineers, New York, 1986), pp. 1174–1185.

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (9)

Fig. 1
Fig. 1

Geometry of motion and structure from motion.

Fig. 2
Fig. 2

Images of two planar grids hinged together with θ = 45 ° . Gaussian noise of σ = 0.5 pixel has been added to each grid point.

Fig. 3
Fig. 3

3D reconstruction of the images shown in Fig. 2 with the two-stage algorithm: (a) front and (b) top views.

Fig. 4
Fig. 4

3D reconstruction of the images shown in Fig. 2 with the three-stage algorithm: (a) front and (b) top views.

Fig. 5
Fig. 5

Comparison of the standard and new algorithms for (a) θ = 60 ° and (b) θ = 90 ° with respect to noise level.

Fig. 6
Fig. 6

Comparison of the standard and new algorithms for σ = 0.5 pixel with respect to the angle θ of the object.

Fig. 7
Fig. 7

Two images of a rock scene.

Fig. 8
Fig. 8

Reconstructed 3D points of the rock scene of Fig. 7: (a) front and (b) top views.

Fig. 9
Fig. 9

Stereogram of the reconstructed 3D points of the rock scene of Fig. 7.

Tables (1)

Tables Icon

Table 1 Comparison of the Number of Successful Trials out of 100 between the Standard Two-Stage (2S) Algorithm and the New Multistage (3S) Algorithm

Equations (36)

Equations on this page are rendered with MathJax. Learn more.

s u v 1 = P x y z 1 , or s m ˜ = P M ˜ ,
P = A [ R t ] with A = α u c u 0 0 α v v 0 0 0 1 ,
s 1 m ˜ 1 = A 1 [ I 0 ] M ˜ ,
s 2 m ˜ 2 = A 2 [ R t ] M ˜ ,
m ˜ 2 T A 2 - T [ t ] × RA 1 - 1 m ˜ 1 = 0 ,
F = A 2 - T [ t ] × RA 1 - 1 ,
p ˜ 2 T E p ˜ 1 = 0 with E = [ t ] × R ,
1 × 2 2 + 2 × 3 2 + 3 × 1 2
= 1 4   ( 1 2 + 2 2 + 3 2 ) 2 ,
u T = 0 ,
u = [ x 1 x 2 ,   y 1 x 2 , x 2 ,   x 1 y 2 ,   y 1 y 2 ,   y 2 ,   x 1 ,   y 1 ,   1 ] T ,
= [ E 11 ,   E 12 ,   E 13 ,   E 21 ,   E 22 ,   E 23 ,   E 31 ,   E 32 ,   E 33 ] T .
U = 0 ,
det [ α E 1 + ( 1 - α ) E 2 ] = 0 ,
min U 2 .
min U 2 subject to = 2 .
d ( m ˜ 2 ,   F m ˜ 1 ) = m ˜ 2 T F m ˜ 1 [ ( F m ˜ 1 ) 1 2 + ( F m ˜ 1 ) 2 2 ] 1 / 2 ,
i [ d 2 ( m ˜ 2 i ,   F m ˜ 1 i ) + d 2 ( m ˜ 1 i ,   F T m ˜ 2 i ) ] ,
i 1 ( F m ˜ 1 i ) 1 2 + ( F m ˜ 1 i ) 2 2 + 1 ( F T m ˜ 2 i ) 1 2 + ( F T m ˜ 2 i ) 2 2 × ( m ˜ 2 i T F m ˜ 1 i ) 2 .
M ˆ = arg   min M [ m 1 - h 1 ( a ,   M ) 2 + m 2 - h 2 ( a ,   M ) 2 ] ,
θ = [ a T ,   M 1 T ,   ,   M j T ,   ,   M n T ] T .
θ ˆ = arg   min θ   i = 1 2 j = 1 n δ m ij T Λ ij - 1 δ m ij with δ m ij = m ij - h i ( a ,   M j ) ,
θ ˆ = arg   min θ   i = 1 2 j = 1 n m ij - h i ( a ,   M j ) 2 .
θ ˆ = arg   min a   j = 1 n { min M j [ m 1 j - h 1 ( a ,   M j ) 2 + m 2 j - h 2 ( a ,   M j ) 2 ] } .
F = a b - ax 1 - by 1 c d - cx 1 - dy 1 - ax 2 - cy 2 - bx 2 - dy 2 ( ax 1 + by 1 ) x 2 + ( cx 1 + dy 1 ) y 2
M = USV T
F = US ˆ V T ,
F e ˜ 1 = 0 , F T e ˜ 2 = 0 .
x i = e i 1 / e i 3 , y i = e i 2 / e i 3 for i = 1 ,   2 .
min   i ρ ( r i ) ,
min   median i ( r i 2 ) .
M J = median i = 1 , , n [ d 2 ( m ˜ 2 i ,   F J m ˜ 1 i ) + d 2 ( m ˜ 1 i ,   F J T m ˜ 2 i ) ] .
P = 1 - [ 1 - ( 1 - ) p ] m .
σ ˆ = 1.4826 [ 1 + 5 / ( n - p ) ] M J ,
w i = 1 if r i 2 ( 2.5 σ ˆ ) 2 0 otherwise ,
min R , t   i w i r i 2 ,

Metrics