Skip to main content
SpringerLink
Log in

Efficient registration of stereo images by matching graph descriptions of edge segments

  • Published:
International Journal of Computer Vision Aims and scope Submit manuscript

Abstract

We present a new approach to the stereo-matching problem. Images are individually described by aneighborhood graph of line segments coming from a polygonal approximation of the contours. The matching process is defined as the exploration of the largest components of adisparity graph built from the descriptions of the two images, and is performed by an efficient prediction and propagation technique. This approach was tested on a variety of man-made environments, and it appears to be fast and robust enough for mobile robot navigation and three-dimensional part-positioning applications.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. D. Marr and T. Poggio, “Cooperative computation of stereo disparity,” SCIENCE vol. 194, pp. 283–287, 1976.

    Google Scholar 

  2. W.E.L. Grimson. FROM IMAGES TO SURFACES. M.I.T. Press: Cambridge, MA, 1981.

    Google Scholar 

  3. W.E.L. Grimson. “Computational experiments with a feature based stereo algorithm,” M.I.T., Cambridge, MA, A.I. Memo. 762, 1984.

    Google Scholar 

  4. Y. Ohta and T. Kanade, “Stereo by intra- and interscanline search,” IEEE TRANS. PAMI vol. PAMI-7, pp. 139–154, 1985.

    Google Scholar 

  5. H. Baker and T.O. Binford, “Depth from edge and intensity based stereo,” in PROC. 7TH INT. JOINT CONF. ARTIF. INTELL., Vancouver, Canada, 1981, pp. 631–636.

  6. K. Ben Rhouma et al., “A K2-D perception approach for assembly robots,” in PROC. EURASIP 1983, Erlangen, FRG, 1983.

  7. M. Benard, “Extracting 3-D coordinates of an object from a digital stereopair: an automated method,” in PROC EURASIP, Erlangen, FRG, 1983, pp. 227–230.

  8. R. Mohr and W. Wrobel, “La correspondance en stéréovision vue comme unc recherche de chemin optimal” [in French], in PROC. 4TH AFCET-INRIA CONF. REC. FORMES INTELL. ARTIF., 1984, pp. 71–79.

  9. G. Medioni and R. Nevatia, “Segment based stereo matching,” in PROC. IMAGE UNDERSTANDING WORKSHOP, Arlington, VA, 1983, pp. 128–136.

  10. M. Berthod and P. Long, “Graph matching by parallel optimization methods: an application to stereo vision,” in PROC. 7TH INT. CONF. PATTERN RECOGNITION, Montreal, Canada, 1984, pp. 841–843.

  11. S.T. Barnard and W.B. Thompson, “Disparity analysis of images,” IEEE TRANS. PAMI vol. PAMI-2, pp. 333–340, 1980.

    Google Scholar 

  12. J.E.W. Mayhew and J.P. Frisby, “Computational and psychophysical studies towards a theory of human stereopsis,” ANTIF. INTELL. vol. 17, pp. 349–386, 1981.

    Google Scholar 

  13. S. Pollard, J. Porril, J. Mayhew, and J. Frisby, “Disparity gradient, Lipschitz continuity, and computing binocular correspondence,” University of Sheffield, England, Intern. Rep. AIVRU-010, 1986.

  14. H.K. Nishihara, “Prism, a practical real-time imaging stereo matcher,” M.I.T., Cambridge, MA, A.I. Memo. 780, 1984, 31 pages.

    Google Scholar 

  15. S. Castan and J. Shen, “A stereo vision algorithm taking into account the perspective distorsions,” in PROC. 7TH INT. CONF. PATTERN RECOGNITION, Montreal, Canada, 1984, pp. 444–446.

  16. H.P. Moravec, “Towards automatic visual obstacle avoidance,” in PROC. 5TH INT. JOINT CONF. ARTIF. INTELL., Cambridge, MA, 1977, p. 584.

  17. R. Nevatia, “Depth measurement by motion stereo,” COMPUT. VISION, GRAPHICS AND IMAGE PROCESSING vol. 5, pp. 203–214, 1976.

  18. D.B. Gennery, “A stereovision system for an autonomous vehiele,” in PROC. 5TH INT. JOINT CONF. ARTIF, INTELL., Cambridge, MA, 1977, pp. 576–582.

  19. K. Mori, M. Kidode, and H. Asada, “An iterative prediction and correction method for automatic stereocomparison,” COMPUT. VISION, GRAPHICS IMAGE PROCESSING vol. 2, pp. 393–401, 1973.

    Google Scholar 

  20. M.D. Levine et al., “Computer determination of depth maps,” COMPUT. VISION, GRAPHICS IMAGE PROCESSING vol. 2, pp. 131–150, 1973.

    Google Scholar 

  21. J.J. Hwang and E.L. Hall, “Matching of featured objects using relational tables from stereo images,” COMPUT. VISION, GRAPHICS IMAGE PROCESSING vol. 20, pp. 22–42, 1982.

    Google Scholar 

  22. G. Poggio and T. Poggio, “The analysis of stereopsis,” ANNU. REV. NEUROSCI. vol. 7, pp. 379–412, 1984.

    Google Scholar 

  23. N. Ayache and B. Faverjon, “Fast stereo matching of edge segments using prediction and verification of hypotheses,” in PROC. CONF. COMPUT. VISION AND PATTERN RECOGNITION, San Francisco, CA, 1985, pp. 662–664.

  24. N. Ayache and B. Faverjon, “A fast stereovision matcher based on prediction and recursive verification of hypotheses,” in PROC. 3RD WORKSHOP COMPUT. VISION: REPRESENTATION AND CONTROL, Bellaire, MI, 1985, pp. 27–37.

  25. D. Marr and E. Hildreth, “Theory of edge detection,” PROC. R. SOC. LONDON [B] vol. 207, pp. 187–217, 1980.

    Google Scholar 

  26. N. Keskes, A. Boulanouar, and O.D. Faugeras, “Application of images analysis techniques to seismic data,” in PROC. INT. CONF. ASSP, Paris, pp. 855–857, 1982.

  27. N. Ayache and O.D. Faugeras, “Hyper: a new approach for the recognition and positioning of 2-D objects,” IEEE TRANS. PAMI vol. PAMI-8, pp. 44–54, 1986.

    Google Scholar 

  28. J.F. Canny, “Finding edges and lines in images,” M.I.T. Artif. Intell. Lab., Cambridge, MA, A.I. Memo, 720, 1983.

    Google Scholar 

  29. R.Deriche, “Optimal edge detection using recursive filtering,” INT. J. COMPUT. VISION, 1987.

  30. T. Pavlidis, STRUCTURAL PATTERN RECOGNITION. Springer-Verlag: New York, 1977.

    Google Scholar 

  31. M. Berthod, “Polygonal approximation of edge chains,” INRIA Intern. Rep. 1987 (in press).

  32. D. Knuth, THE ART OF COMPUTER PROGRAMMING, vol. 3: SORTING AND SEARCHING. Addison Wesley: Reading, MA, 1975.

    Google Scholar 

  33. O.D. Faugeras and G. Toscani, “The calibration problem for stereo,” in PROC. CONF. COMPUT. VISION AND PATTERN RECOGNITION, Miami, FL, 1986, pp. 15–20.

  34. R.D. Arnold and T.O. Binford, “Geometric constraints in stereo vision,” in PROC. SPIE, 238, San Diego, CA, 1980, pp. 281–292.

  35. N. Ayache, O.D. Faugeras, B. Faverjon, and G. Toscani, “Matching depth maps obtained by passive stereovision,” in PROC. 3RD WORKSHOP COMPUT. VISION: REPRESENTATION AND CONTROL, Bellaire, MI, 1985, pp. 197–204.

  36. O.D. Faugeras, N. Ayache, and B. Faverjon, “Building visual maps by combining noisy stereo measurements,” in PROC. INT. CONF. ROBOTICS AND AUTOMATION, vol. 3, San Francisco, CA, 1986, pp. 1433–1438.

  37. N. Ayache and O.D. Faugeras, “Building, registrating and fusing noisy visual maps,” in PROC. 1ST INT. CONF. COMPUT. VISION, London, England, 1987.

Download references

Author information

Authors and Affiliations

  1. Institut National de Recherche en Informatique et Automatique (INRIA) Domaine de Voluceau, BP 105, F-78153, Le Chesnay Cedex, France

    Nicholas Ayache & Bernard Faverjon

Authors
  1. Nicholas Ayache
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Bernard Faverjon
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Ayache, N., Faverjon, B. Efficient registration of stereo images by matching graph descriptions of edge segments. Int J Comput Vision 1, 107–131 (1987). https://doi.org/10.1007/BF00123161

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF00123161

Keywords

Search

Navigation