Skip to main content
SpringerLink
Log in

Smoothing and matching of 3-d space curves

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

Abstract

We present a new approach to the problem of matching 3-D curves. The approach has a low algorithmic complexity in the number of models, and can operate in the presence of noise and partial occlusions.

Our method builds upon the seminal work of Kishon et al. (1990), where curves are first smoothed using B-splines, with matching based on hashing using curvature and torsion measures. However, we introduce two enhancements:

  1. -

    We make use of nonuniform B-spline approximations, which permits us to better retain information at high-curvature locations. The spline approximations are controlled (i.e., regularized) by making use of normal vectors to the surface in 3-D on which the curves lie, and by an explicit minimization of a bending energy. These measures allow a more accurate estimation of position, curvature, torsion, and Frénet frames along the curve.

  2. -

    The computational complexity of the recognition process is relatively independent of the number of models and is considerably decreased with explicit use of the Frénet frame for hypotheses generation. As opposed to previous approaches, the method better copes with partial occlusion. Moreover, following a statistical study of the curvature and torsion covariances, we optimize the hash table discretization and discover improved invariants for recognition, different than the torsion measure. Finally, knowledge of invariant uncertainties is used to compute an optimal global transformation using an extended Kalman filter.

We present experimental results using synthetic data and also using characteristic curves extracted from 3-D medical images. An earlier version of this article was presented at the 2nd European Conference on Computer Vision in Italy.

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

  • Arbogast, E. 1990. La représentation des contours et leur segmentation. Tech. Rept. RR 115, LIFIA, juillet.

  • Ayache, N. 1991.Artificial Vision for Mobile Robots—Stereo-Vision and Multisensory Perception. MIT Press: Cambridge, MA.

    Google Scholar 

  • Ayache, N., and Faugeras, O.D. 1986. Hyper: A new approach for the recognition and positioning of two-dimensional objects,IEEE Trans. Patt. Anal. Mach. Intell. 8(1):44–54.

    Google Scholar 

  • Ayache, N., Boissonnat, J.D., Brunet, E., Cohen, L., Chièze, J.P., Geiger, B., Monga, O., Rocchisani, J.M., and Sander, P. 1989. Building highly structured volume representations in 3-D medical images. InComputer Aided Radiology, Berlin, West-Germany.

  • Ayache, N., Boissonnat, J.D., Cohen, L., Geiger, B., Levy-Vehel, J., Monga, O., and Sander, P. 1990. Steps toward the automatic interpretation of 3-D images. In H. Fuchs, K. Hohne, and S. Pizer, eds.,3D Imaging in Medicine, NATO ASI Series, Springer-Verlag: New York, pp. 107–120.

    Google Scholar 

  • Bartels, R., Beatty, J., and Barsky, B., 1987.An Introduction to Splines for Use in Computer Graphics and Geometric Modelling. Morgan Kaufmann: San Mateo, CA.

    Google Scholar 

  • Benayoun, S., Monga, O., Guéziec, A., and Ayache, N. 1992. Using surface curvatures for 3-D image registration,Proc. 11th Conf. Comput. Appl. Radiol., Baltimore, MD.

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

    Google Scholar 

  • Bohm, W., Farin, G., and Kahmann, J. 1984.A Survey of Curve and Surface Methods in CAGD, Elsevier Science Publishers: North Holland, in Computer Aided Geometric Design, pp. 1–60.

  • Cinquin, P. 1981. Splines unidimsionnelles sous tension et bidimen-sionnelles paramétrées, Thèse de Doctorat de troisième cycle, Université de St-Etienne, Octobre.

  • Cinquin, P. 1987. Application des fonctions-spline au traitement d'images num ériques. Thèse de Doctorat de mathématiques, Septembre.

  • Cohen, I. Cohen, L.D., and Ayache, N. 1991. Introducing deformable surfaces to segment 3-D images and infer differential structures,Proc. Conf. Comput. Vis. Patt. Recog., Hawaii, June.

  • Cohen, L.D. and Cohen I. 1990. A finite element method applied to new active contour models and 3-D reconstruction from cross sections,Proc. 3rd Intern. Conf. Comput. Vis., Osaka, Japan, December.

  • Craven, P. and Wahba, G. 1979. Smoothing noisy data with spline functions.Numerische Mathematik 31:377–403.

    Google Scholar 

  • Cutting, C.B. 1989. Applications of computer graphics to the evaluation and treatment of major craniofacial malformation. In Udupa and Herman, eds.,3-D Imaging in Medicine, CRC Press: Boca Raton, FL.

    Google Scholar 

  • de Boor, C. 1978.A practical Guide to Splines. Springer-Verlag: New York.

    Google Scholar 

  • de Hoog, F.R. and Hutchinson, M.F. 1987. An efficient method for calculating smoothing splines using orthogonal transformations,Numerische Mathematik 50:311–319.

    Google Scholar 

  • do Carmo, M.P. 1976.Differential Geometry of Curves and Surfaces. Prentice-Hall: Englewood Cliffs, NJ.

    Google Scholar 

  • Duda, R., and Hart, P. 1973.Pattern Classification and Scene Analysis. Wiley: New York.

    Google Scholar 

  • Farin, C. 1988.Curves and Surfaces for Computer Aided Geometric Design. Academic Press: San Diego, CA.

    Google Scholar 

  • Girard, D. 1989. A fast “monte-carlo cross-validation procedure” for large least squares problems with noisy data,Numerische Mathematik 56:1–23.

    Google Scholar 

  • Grimson, W.E.L., and Huttenlocher, D.P. 1991. On the verification of hypothesized matches in model-based recognition,IEEE Trans. Patt. Anal. Mach. Intell. 13(12):1201–1213, December.

    Google Scholar 

  • Grimson, W.E.L. and Lozano-Perèz, T. 1984. Model-based recognition and localization from sparse range or tactile data,Intern. J. Robot. Res. 3(3):3–35.

    Google Scholar 

  • Grossman, M. 1971. Parametric curve fitting,Computer Journal 14:169–172.

    Google Scholar 

  • Guéziec, A. 1993. Large deformable splines, crest lines and matching,Proc. 4th Intern. Conf. Comput. Vis., Berlin, May.

  • Guéziec, A., and Ayache, N. 1992. Smoothing and matching of 3-D-space curves,Proc. 2nd Europ. Conf. Comput. Vis., Santa Margherita Ligure, Italy, May.

  • Herlin, I., and Ayache, N. 1992. Features extraction and analysis methods for sequences of ultrasound images,Proc. 2nd Europ. Conf. Comput. Vis., Santa Margherita Ligure, Italy, May.

  • Holladay, J.C. 1957. Smoothest curve approximation,Math. Tables Aids Computation 11:233–243.

    Google Scholar 

  • Kishon, E., Hastie, T., and Wolfson, H. 1990. 3-D curve matching using splines,Proc. 1st Europ. Conf. Comput. Vis., Antibes, France, April.

  • Lancaster, P., and Salkauskas, K. 1986.Curve and Surface Fitting, an Introduction. Academic Press, San Diego, CA.

    Google Scholar 

  • Malandain, G., Bertrand, G., and Ayache, N. 1991. Topological segmentation of discrete surface structures,Proc. Conf. Comput. Vis. Patt. Recog., Hawaii, June.

  • Marin, S.P. 1984. An approach to data parametrization in parametric cubic spine interpolation,J. Approx. Theory 41:64–86.

    Google Scholar 

  • Monga, O., Ayache, N., and Sander P. 1991. From voxels to curvature,Proc. Conf. Comput. Vis. Patt. Recog., Hawaii, June.

  • Monga, O., Benayoun, S. and Faugeras, O.D. 1992. Using third order derivatives to extract ridge lines in 3-D images,Proc. Conf. Comput. Vis. Patt. Recog., Urbana Champaign, June.

  • Monga, O., Deriche, R. and Rocchisani, J.-M. 1991. 3-D edge detection using recursive filtering: Application to scanner images,Comput. Vis. Graph. Image Process., January.

  • Nilson, E.N., Ahlberg, J.H., and Walsh, J.L. 1967.The Theory of Splines and Their Applications. Academic Press: New York.

    Google Scholar 

  • Pavlidis, T. 1977.Structural Pattern Recognition. Springer-Verlag: New York.

    Google Scholar 

  • Plass, M. and Stone, M. 1983. Curve fitting with piecewise parametric cubics,Siggraph, pp. 229–239, July.

  • Reinsch, C.H. 1967. Smoothing by spline functions,Numerische Mathematik 10:177–183.

    Google Scholar 

  • Reinsch, C.H. 1970. Smoothing by spline functions II,Numerische Mathematik 16:451–454.

    Google Scholar 

  • Rigoutsos, I. 1992.Massively parallel Bayesian object recognition. Ph.D. thesis, New York University.

  • Rigoutsos, I., and Hummel, R. 1991. Robust similarity invariant matching in the presence of noise: A data parallel approach,Proc. 8th Israeli Conf. Artif. Intell. Comput. Vis., December.

  • Saint-Marc, P. and Medioni, G. 1990. B-spline contour representation and symmetry detection,Proc. 1st Europ. Conf. Comput. Vis., Antibes, April.

  • Schwartz, J.T., and Sharir, M. 1987. Identification of partially obscured objects in two and three dimensions by matching noisy characteristic curves,Intern. J. Robot. Res. 6:229–244.

    Google Scholar 

  • Silverman, B.W. 1984. A fast and efficient cross-validation method for smoothing parameter choice in spline regression,J. Amer. Statist. Assoc. 79:584–589, September.

    Google Scholar 

  • Stein, F. 1991. Structural hashing: Efficient 3-D object recognition,Proc. Intern. Conf. Comput. Vis. Patt. Recog., Hawaii, June.

  • Thirion, J.P. and Gourdon, A. 1992. The 3-D matching lines algorithm and its application to crest lines extraction, Tech. Rept. 1672, INRIA, May.

  • Thirion, J.P. and Gjoourdon, A. 1993. The matching lines algorithm: new results and proofs, Tech. Rept. 1881, INRIA.

  • Thirion, J.P., Gourdon, A., Monga, O., Guéziec, A., and Ayache, N. 1992. Automatic registraction of 3-D CAT-SCAN images using surface curvature,Proc. 14th Annu. Intern. Conf. IEEE Engineer. Med. Biol. Soc. Satellite Symposium on 3-D Advanced Image Processing in Medicine, Rennes, France. November.

  • Thompson, D.W. and Mundy, J.L. 1987. 3-D model matching from an unconstrained viewpoint,Proc. Intern. Conf. Robot. Autom., pp. 208–220.

  • Wang, Shin, Ywan and Ferrari, L.A. 1990. Automatic data visualization using spline functions. Unpublished manuscript, Department of Electrical and Computer Engineering, University of California, Irvine CA 92717.

    Google Scholar 

  • Zhang, Zhengyou. 1992. Iterative point matching for registration of free-form curves, Tech. Rept. 1658, INRIA, March.

Download references

Author information

Authors and Affiliations

  1. INRIA, project Epidaure, F-06902, Sophia-Antipolis

    André Guéziec & Nicholas Ayache

Authors
  1. André Guéziec
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Nicholas Ayache
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

André Guéziec is currently a Visiting Researcher and an Adj. Faculty at New York University, Courant Institute, 251 Mercer Street, New York, NY 10012.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Guéziec, A., Ayache, N. Smoothing and matching of 3-d space curves. Int J Comput Vision 12, 79–104 (1994). https://doi.org/10.1007/BF01420985

Download citation

  • Received:

  • Issue Date:

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

Keywords

Search

Navigation