Skip to main content
SpringerLink
Log in

Iterative point matching for registration of free-form curves and surfaces

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

Abstract

A heuristic method has been developed for registering two sets of 3-D curves obtained by using an edge-based stereo system, or two dense 3-D maps obtained by using a correlation-based stereo system. Geometric matching in general is a difficult unsolved problem in computer vision. Fortunately, in many practical applications, some a priori knowledge exists which considerably simplifies the problem. In visual navigation, for example, the motion between successive positions is usually approximately known. From this initial estimate, our algorithm computes observer motion with very good precision, which is required for environment modeling (e.g., building a Digital Elevation Map). Objects are represented by a set of 3-D points, which are considered as the samples of a surface. No constraint is imposed on the form of the objects. The proposed algorithm is based on iteratively matching points in one set to the closest points in the other. A statistical method based on the distance distribution is used to deal with outliers, occlusion, appearance and disappearance, which allows us to do subset-subset matching. A least-squares technique is used to estimate 3-D motion from the point correspondences, which reduces the average distance between points in the two sets. Both synthetic and real data have been used to test the algorithm, and the results show that it is efficient and robust, and yields an accurate motion estimate.

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.

Similar content being viewed by others

References

  • Arun, K., Huang, T. and Blostein, S.: 1987, Least-squares fitting of two 3-D point sets,IEEE Trans. PAMI 9(5), 698–700.

    Google Scholar 

  • Ayache, N. and Faugeras, O. D.: 1989, Maintaining Representations of the Environment of a Mobile Robot,IEEE Trans. RA 5(6), 804–819.

    Google Scholar 

  • Besl, P. and Jain, R.: 1985, Three-dimensional object recognition,ACM Computing Surveys 17(1), 75–145.

    Google Scholar 

  • Besl, P. J.: 1988, Geometric modeling and computer vision,Proc. IEEE 76(8), 936–958.

    Google Scholar 

  • Besl, P. J. and McKay, N. D.: 1992, A method for registration of 3-D shapes,IEEE Trans. PAMI 14(2), 239–256.

    Google Scholar 

  • Blostein, S. and Huang, T.: 1987, Error analysis in stereo determination of a 3-D point position,IEEE Trans. PAMI 9(6), 752–765.

    Google Scholar 

  • Bolles, R. and Cain, R.: 1982, Recognizing and locating partially visible objects, the local-feature-focus method,Int'l J. Robotics Res. 1 (3), 57–82.

    Google Scholar 

  • Brockett, R.: 1989, Least squares matching problems,Linear Algebra and Its Applications 122/123/124, 761–777.

    Google Scholar 

  • Champleboux, G., Lavallée, S., Szeliski, R. and Brunie, L.: 1992, From accurate range imaging sensor calibration to accurate model-based 3-D object localization,Proc. IEEE Conf. Comput. Vision Pattern Recog., Champaign, Illinois, pp. 83–89.

  • Chen, X.: 1992,Vision-Based Geometric Modeling, Ph.D. dissertation, Ecole Nationale Supérieure des Télécommunications, Paris, France.

    Google Scholar 

  • Chen, Y. and Medioni, G.: 1992, Object modelling by registration of multiple range images,Image and Vision Computing 10(3), 145–155.

    Google Scholar 

  • Chin, R. and Dyer, C.: 1986, Model-based recognition in robot vision,ACM Computing Surveys 18(1), 67–108.

    Google Scholar 

  • Faugeras, O. and Hebert, M.: 1986, The representation, recognition, and locating of 3D shapes from range data,Int'l J. Robotics Res. 5(3), 27–52.

    Google Scholar 

  • Faugeras, O. D., Lebras-Mehlman, E. and Boissonnat, J.: 1990, Representing Stereo data with the Delaunay Triangulation,Artif. Intell.

  • Faugeras, O., Fua, P., Hotz, B., Ma, R., Robert, L., Thonnat, M. and Zhang, Z.: 1992, Quantitative and qualitative comparison of some area and feature-based stereo algorithms, in W. Föstner and S. Ruwiedel (eds),Robust Computer Vision: Quality of Vision Algorithms, Wichmann, Karlsruhe, Germany, pp. 1–26.

    Google Scholar 

  • Fua, P.: 1992, A parallel stereo algorithm that produces dense depth maps and preserves image features,Machine Vision and Applications. Accepted for publication.

  • Gennery, D. B.: 1989, Visual terrain matching for a Mars rover,Proc. IEEE Conf. Comput. Vision Pattern Recog., San Diego, CA, pp. 483–491.

  • Goldgof, D. B., Huang, T. S. and Lee, H.: 1988, Feature extraction and terrain matching,Proc. IEEE Conf. Comput. Vision Pattern Recog., Ann Arbor, Michigan, pp. 899–904.

  • Grimson, W.: 1985, Computational experiments with a feature based stereo algorithm,IEEE Trans. PAMI 7(1), 17–34.

    Google Scholar 

  • Gueziec, A. and Ayache, N.: 1992, Smoothing and matching of 3-D space curves,Proc. Second European Conf. Comput. Vision, Santa Margharita Ligure, Italy, pp. 620–629.

  • Haralick, R. et al.: 1989, Pose estimation from corresponding point data,IEEE Trans. SMC 19(6), 1426–1446.

    Google Scholar 

  • Hebert, M., Caillas, C., Krotkov, E., Kweon, I. S. and Kanade, T.: 1989, Terrain mapping for a roving planetary explorer,Proc. Int'l Conf. Robotics Automation, pp. 997–1002.

  • Horn, B.: 1987, Closed-form solution of absolute orientation using unit quaternions,Journal of the Optical Society of America A 7, 629–642.

    Google Scholar 

  • Horn, B. and Harris, J.: 1991, Rigid body motion from range image sequences,CVGIP: Image Understanding 53(1), 1–13.

    Google Scholar 

  • Kamgar-Parsi, B., Jones, J. L. and Rosenfeld, A.: 1991, Registration of multiple overlapping range images: Scenes without distinctive features,IEEE Trans. PAMI 13(9), 857–871.

    Google Scholar 

  • Kehtarnavaz, N. and Mohan, S.: 1989, A framework for estimation of motion parameters from range images,Comput. Vision, Graphics Image Process. 45, 88–105.

    Google Scholar 

  • Kriegman, D., Triendl, E. and Binford, T.: 1989, Stereo vision and navigation in buildings for mobile robots,IEEE Trans. RA 5 (6), 792–803.

    Google Scholar 

  • Kweon, I. and Kanade, T.: 1992, High-resolution terrain map from multiple sensor data,IEEE Trans. PAMI 14(2), 278–292.

    Google Scholar 

  • Liang, P. and Todhunter, J. S.: 1990, Representation and recognition of surface shapes in range images: A differential geometry approach,Comput. Vision, Graphics Image Process. 52, 78–109.

    Google Scholar 

  • Matthies, L. and Shafer, S. A.: 1987, Error modeling in stereo navigation,IEEE J. RA 3(3), 239–248.

    Google Scholar 

  • zMayhew, J. E. W. and Frisby, J. P.: 1981, Psychophysical and computational studies towards a theory of human stereopsis,Artif. Intell. 17, 349–385.

    Google Scholar 

  • Menq, C.-H., Yau, H.-T. and Lai, G.-Y.: 1992, Automated precision measurement of surface profile in CAD-directed inspection,IEEE Trans. RA 8(2), 268–278.

    Google Scholar 

  • Milios, E. E.: 1989, Shape matching using curvature processes,Comput. Vision, Graphics Image Process. 47, 203–226.

    Google Scholar 

  • Navab, N. and Zhang, Z.: 1992, From multiple objects motion analysis to behavior-based object recognition,Proc. ECAI 92, Vienna, Austria, pp. 790–794.

  • Pavlidis, T.: 1980, Algorithms for shape analysis of contours and waveforms,IEEE Trans. PAMI 2(4), 301–312.

    Google Scholar 

  • Pollard, S., Mayhew, J. and Frisby, J.: 1985, PMF: A stereo correspondence algorithm using a disparity gradient limit,Perception 14, 449–470.

    Google Scholar 

  • Preparata, F. and Shamos, M.: 1986,Computational Geometry, An Introduction, Springer, Berlin, Heidelberg, New-York.

    Google Scholar 

  • Radack, G. M. and Badler, N. I.: 1989, Local matching of surfaces using a boundary-centered radial decomposition,Comput. Vision, Graphics Image Process. 45, 380–396.

    Google Scholar 

  • Robert, L. and Faugeras, O.: 1991, Curve-based stereo: Figural continuity and curvature,Proc. IEEE Conf. Comput. Vision Pattern Recog., Maui, Hawaii, pp. 57–62.

  • Rodriguez, J. J. and Aggarwal, J. K.: 1989, Navigation using image sequence analysis and 3-D terrain matching,Proc. Workshop on Interpretation of 3D Scenes, Austin, TX, pp. 200–207.

  • Safaee-Rad, R., Tchoukanov, I., Benhabib, B. and Smith, K. C.: 1991, Accurate parameter estimation of quadratic curves from grey-level images,CVGIP: Image Understanding 54(2), 259–274.

    Google Scholar 

  • Sampson, R. E.: 1987, 3D range sensor-phase shift detection,Computer 20, 23–24.

    Google Scholar 

  • Schwartz, J. T. and Sharir, M.: 1987, Identification of partially obscured objects in two and three dimensions by matching noisy characteristic curves,Int'l J. Robotics Res. 6(2), 29–44.

    Google Scholar 

  • Szeliski, R.: 1988, Estimating motion from sparse range data without correspondence,Proc. Second Int'l Conf. Comput. Vision, IEEE, Tampa, FL, pp. 207–216.

  • Szeliski, R.: 1990, Bayesian modeling of uncertainty in low-level vision,Int'l J. Comput. Vision 5(3), 271–301.

    Google Scholar 

  • Taubin, G.: 1991, Estimation of planar curves, surfaces, and non-planar space curves defined by implicit equations with applications to edge and range image segmentation,IEEE Trans. PAMI 13(11), 1115–1138.

    Google Scholar 

  • Walker, M. W., Shao, L. and Volz, R. A.: 1991, Estimating 3-D location parameters using dual number quaternions,CVGIP: Image Understanding 54(3), 358–367.

    Google Scholar 

  • Walters, D.: 1987, Selection of image primitives for general-purpose visual processing,Comput. Vision, Graphics Image Process. 37 (3), 261–298.

    Google Scholar 

  • Wolfson, H.: 1990, On curve matching,IEEE Trans. PAMI 12 (5), 483–489.

    Google Scholar 

  • Zhang, Z.: 1991, Recalage de deux cartes de profondeur denses: L'état de l'art,Rapport VAP de la phase 4, CNES, Toulouse, France.

    Google Scholar 

  • Zhang, Z.: 1992a, Iterative point matching for registration of free-form curves,Research Report 1658, INRIA Sophia-Antipolis.

  • Zhang, Z.: 1992b, On local matching of free-form curves,Proc. British Machine Vision Conf., University of Leeds, UK, pp. 347–356.

  • Zhang, Z. and Faugeras, O.: 1991, Determining motion from 3D line segments: A comparative study,Image and Vision Computing 9(1), 10–19.

    Google Scholar 

  • Zhang, Z. and Faugeras, O.: 1992a,3D Dynamic Scene Analysis: A Stereo Based Approach, Springer, Berlin, Heidelberg.

    Google Scholar 

  • Zhang, Z. and Faugeras, O.: 1992b, Three-dimensional motion computation and object segmentation in a long sequence of stereo frames,Int'l J. Comput. Vision 7(3), 211–241.

    Google Scholar 

  • Zhang, Z., Faugeras, O. and Ayache, N.: 1988, Analysis of a sequence of stereo scenes containing multiple moving objects using rigidity constraints,Proc. Second Int'l Conf. Comput. Vision, Tampa, FL, pp. 177–186. Also as a chapter in R. Kasturi and R.C. Jain (eds),Computer Vision: Principles, IEEE computer society press, 1991.

Download references

Author information

Authors and Affiliations

  1. INRIA Sophia-Antipolis, 2004 route des Lucioles, BP 93, F-06902, Sophia-Antipolis Cedex, France

    Zhengyou Zhang

Authors
  1. Zhengyou Zhang
    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

Zhang, Z. Iterative point matching for registration of free-form curves and surfaces. Int J Comput Vision 13, 119–152 (1994). https://doi.org/10.1007/BF01427149

Download citation

  • Received:

  • Revised:

  • Issue Date:

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

Keywords

Search

Navigation