SpringerLink
Log in

Topology-Invariant Similarity of Nonrigid Shapes

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

Abstract

This paper explores the problem of similarity criteria between nonrigid shapes. Broadly speaking, such criteria are divided into intrinsic and extrinsic, the first referring to the metric structure of the object and the latter to how it is laid out in the Euclidean space. Both criteria have their advantages and disadvantages: extrinsic similarity is sensitive to nonrigid deformations, while intrinsic similarity is sensitive to topological noise. In this paper, we approach the problem from the perspective of metric geometry. We show that by unifying the extrinsic and intrinsic similarity criteria, it is possible to obtain a stronger topology-invariant similarity, suitable for comparing deformed shapes with different topology. We construct this new joint criterion as a tradeoff between the extrinsic and intrinsic similarity and use it as a set-valued distance. Numerical results demonstrate the efficiency of our approach in cases where using either extrinsic or intrinsic criteria alone would fail.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

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

  • Amberg, B., Romdhani, S., & Vetter, T. (2007). Optimal step nonrigid ICP algorithms for surface registration. In Proc. CVPR.

  • Anguelov, D., Srinivasan, P., Koller, D., Thrun, S., Rodgers, J., & Davis, J. (2005). SCAPE: shape completion and animation of people. Proc. SIGGRAPH, 24(3), 408–416.

    Google Scholar 

  • Belkin, M., & Niyogi, P. (2003). Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation, 13, 1373–1396.

    Article  Google Scholar 

  • Berger, M. (2002). A panoramic view of Riemannian geometry. Berlin: Springer.

    Google Scholar 

  • Besl, P. J., & McKay, N. D. (1992). A method for registration of 3D shapes. IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 14, 239–256.

    Article  Google Scholar 

  • Borg, I., & Groenen, P. (1997). Modern multidimensional scaling—theory and applications. Berlin: Springer.

    MATH  Google Scholar 

  • Bronstein, A. M., & Bronstein, M. M. (2008). Not only size matters: regularized partial matching of nonrigid shapes. In Proc. workshop on non-rigid shape analysis and deformable image alignment (NORDIA).

  • Bronstein, A. M., Bronstein, M. M., & Kimmel, R. (2005). Three-dimensional face recognition. International Journal of the Computer Vision (IJCV), 64(1), 5–30.

    Article  Google Scholar 

  • Bronstein, A. M., Bronstein, M. M., & Kimmel, R. (2006a). Efficient computation of isometry-invariant distances between surfaces. SIAM Journal on Scientific Computing, 28(5), 1812–1836.

    Article  MATH  MathSciNet  Google Scholar 

  • Bronstein, A. M., Bronstein, M. M., & Kimmel, R. (2006b). Generalized multidimensional scaling: a framework for isometry-invariant partial surface matching. Proc. National Academy of Science (PNAS), 103(5), 1168–1172.

    Article  MATH  MathSciNet  Google Scholar 

  • Bronstein, A. M., Bronstein, M. M., & Kimmel, R. (2006c). Robust expression-invariant face recognition from partially missing data. In Proc. European conf. computer vision (ECCV) (pp. 396–408).

  • Bronstein, M. M., Bronstein, A. M., Kimmel, R., & Yavneh, I. (2006d). Multigrid multidimensional scaling. Numerical Linear Algebra with Applications (NLAA), 13, 149–171.

    Article  MathSciNet  MATH  Google Scholar 

  • Bronstein, A. M., Bronstein, M. M., & Kimmel, R. (2007a). Calculus of non-rigid surfaces for geometry and texture manipulation. IEEE Transactions on Visualization and Computer Graphics, 13(5), 902–913.

    Google Scholar 

  • Bronstein, A. M., Bronstein, M. M., & Kimmel, R. (2007b). Expression-invariant representation of faces. IEEE Transactions on Image Processing, 16(1), 188–197.

    Article  MathSciNet  Google Scholar 

  • Bronstein, A. M., Bronstein, M. M., & Kimmel, R. (2007c). Rock, paper, and scissors: extrinsic vs. intrinsic similarity of non-rigid shapes. In Proc. int. conf. computer vision (pp. 1–6) (ICCV).

  • Bronstein, A. M., Bronstein, M. M., Bruckstein, A. M., & Kimmel, R. (2008a). Partial similarity of objects, or how to compare a centaur to a horse. International Journal of the Computer Vision (IJCV), to appear.

  • Bronstein, A. M., Bronstein, M. M., Bruckstein, A. M., & Kimmel, R. (2008b). Analysis of two-dimensional non-rigid shapes. International Journal of the Computer Vision (IJCV), 78(1), 67–88.

    Article  Google Scholar 

  • Bronstein, A. M., Bronstein, M. M., & Kimmel, R. (2008c). Numerical geometry of nonrigid shapes. New York: Springer.

    Google Scholar 

  • Bruckstein, A. M., Katzir, N., Lindenbaum, M., & Porat, M. (1992). Similarity-invariant signatures for partially occluded planar shapes. IJCV, 7(3), 271–285.

    Article  Google Scholar 

  • Burago, D., Burago, Y., & Ivanov, S. (2001). A course in metric geometry. Graduate studies in mathematics (Vol. 33). Providence: AMS.

    MATH  Google Scholar 

  • Chen, Y., & Medioni, G. (1991). Object modeling by registration of multiple range images. In Proc. conf. robotics and automation.

  • Chui, H., & Rangarajan, A. (2003). A new point matching algorithm for non-rigid registration. Computer Vision and Image Understanding, 89(2–3), 114–141.

    Article  MATH  Google Scholar 

  • Chung, F. R. K. (1997). Spectral graph theory. Providence: AMS.

    MATH  Google Scholar 

  • Coifman, R. R., Lafon, S., Lee, A. B., Maggioni, M., Nadler, B., Warner, F., & Zucker, S. W. (2005). Geometric diffusions as a tool for harmonic analysis and structure definition of data: Diffusion maps. Proc. National Academy of Sciences (PNAS), 102(21), 7426–7431.

    Article  Google Scholar 

  • Donoho, D., & Grimes, C. (2003). Hessian eigenmaps: Locally linear embedding techniques for high-dimensional data. Proc. National Academy of Science (PNAS), 100, 5591–5596.

    Article  MATH  MathSciNet  Google Scholar 

  • Eckstein, I., Pons, J. P., Tong, Y., Kuo, C. C. J., & Desbrun, M. (2007). Generalized surface flows for mesh processing. In Proc. symposium on geometry processing.

  • Elad, A., & Kimmel, R. (2002). Spherical flattening of the cortex surface. In Geometric methods in bio-medical image processing (Vol. 2191, pp. 77–89). Berlin: Springer.

    Google Scholar 

  • Elad, A., & Kimmel, R. (2003). On bending invariant signatures for surfaces. IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 25(10), 1285–1295.

    Article  Google Scholar 

  • Gelfand, N., Mitra, N. J., Guibas, L., & Pottmann, H. (2005). Robust global registration. In Proc. symp. geometry processing (SGP).

  • Gonzalez, T. F. (1985). Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 38(2), 293–306.

    Article  MATH  MathSciNet  Google Scholar 

  • Gordon, C., Webb, D. L., & Wolpert, S. (1992). One cannot hear the shape of the drum. Bulletin AMS, 27(1), 134–138.

    Article  MATH  MathSciNet  Google Scholar 

  • Groemer, H. (1996). Geometric applications of Fourier series and spherical harmonics. New York: Cambridge University Press.

    MATH  Google Scholar 

  • Gromov, M. (1981). Structures métriques pour les variétés Riemanniennes. Textes Mathématiques (no. 1).

  • Grossman, R., Kiryati, N., & Kimmel, R. (2002). Computational surface flattening: a voxel-based approach. IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 24(4), 433–441.

    Article  Google Scholar 

  • Hahnel, D., Thrun, S., & Burgard, W. (2003). An extension of the ICP algorithm for modeling nonrigid objects with mobile robots. In Proc. IJCAI.

  • Hochbaum, D. S., & Shmoys, D. B. (1985a). A best possible approximation algorithm for the k-center problem. Mathematics of Operations Research, 10(2).

  • Hochbaum, D. S., & Shmoys, D. B. (1985b). A best possible heuristic for the k-center problem. Mathematics of Operations Research, 10(2), 180–184.

    Article  MATH  MathSciNet  Google Scholar 

  • Horn, B. K. P. (1987). Closed-form solution of absolute orientation using unit quaternions. Journal of the Optical Society of America (JOSA) A, 4, 629–642.

    Article  Google Scholar 

  • Jacobs, D., Weinshall, D., & Gdalyahu, Y. (2000a). Class representation and image retrieval with non-metric distances. IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 22, 583–600.

    Article  Google Scholar 

  • Jacobs, D., Weinshall, D., & Gdalyahu, Y. (2000b). Class representation and image retrieval with non-metric distances. IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 22, 583–600.

    Article  Google Scholar 

  • Kac, M. (1966). Can one hear the shape of a drum? American Mathematical Monthly, 73, 1–23.

    Article  Google Scholar 

  • Katz, S., Leifman, G., & Tal, A. (2005). Mesh segmentation using feature point and core extraction. The Visual Computer, 21(8), 649–658.

    Article  Google Scholar 

  • Kazhdan, M., Funkhouser, T., & Rusinkiewicz, S. (2003). Rotation invariant spherical harmonic representation of 3D shape descriptors. In Proc. symposium on geometry processing (pp. 156–164).

  • Kilian, M., Mitra, N. J., & Pottmann, H. (2007). Geometric modeling in shape space. In Proc. SIGGRAPH (Vol. 26).

  • Kimmel, R., & Sethian, J. A. (1998). Computing geodesic paths on manifolds. Proc. National Academy of Sciences (PNAS), 95(15), 8431–8435.

    Article  MATH  MathSciNet  Google Scholar 

  • Latecki, L. J., & Lakaemper, R. (2000). Shape similarity measure based on correspondence of visual parts. IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 22, 1185–1190.

    Article  Google Scholar 

  • Latecki, L. J., Lakaemper, R., & Wolter, D. (2005). Optimal partial shape similarity. Image and Vision Computing, 23, 227–236.

    Article  Google Scholar 

  • Leopoldseder, S., Pottmann, H., & Zhao, H. (2003). The d2-tree: A hierarchical representation of the squared distance function (Tech. report). Institute of Geometry, Vienna University of Technology.

  • Lévy, B. (2006). Laplace-Beltrami eigenfunctions towards an algorithm that “understands” geometry. In Int’l conf. shape modeling and applications.

  • Ling, H., & Jacobs, D. (2005a). Deformation invariant image matching. In Proc. ICCV.

  • Ling, H., & Jacobs, D. (2005b). Using the inner-distance for classification of articulated shapes. In Proc. CVPR.

  • Linial, N., London, E., & Rabinovich, Y. (1995). The geometry of graphs and some its algorithmic applications. Combinatorica, 15, 333–344.

    Article  MathSciNet  Google Scholar 

  • Litke, N., Droske, M., Rumpf, M., & Schroder, P. (2005) An image processing approach to surface matching.

  • Mémoli, F., & Sapiro, G. (2005). A theoretical and computational framework for isometry invariant recognition of point cloud data. Foundations of Computational Mathematics, 5, 313–346.

    Article  MATH  MathSciNet  Google Scholar 

  • Mitra, N. J., Gelfand, N., Pottmann, H., & Guibas, L. (2004). Registration of point cloud data from a geometric optimization perspective. In Proc. Eurographics symposium on geometry processing (pp. 23–32).

  • Mohar, B. (1991). The Laplacian spectrum of graphs. In Graph theory, combinatorics, and applications (Vol. 2, pp. 871–898). New York: Wiley.

    Google Scholar 

  • Novotni, M., & Klein, R. (2003). In 3D Zernike descriptors for content based shape retrieval (pp. 216–225).

  • Osada, R., Funkhouser, T., Chazelle, B., & Dobkin, D. (2002). Shape distributions. ACM Transactions on Graphics (TOG), 21(4), 807–832.

    Article  Google Scholar 

  • Paquet, E., Rioux, M., Murching, A., Naveen, T., & Tabatabai, A. (2000). Description of shape information for 2-D and 3-D objects. Signal Processing: Image Communication, 16(1–2), 103–122.

    Article  Google Scholar 

  • Raviv, D., Bronstein, A. M., Bronstein, M. M., & Kimmel, R. (2007). Symmetries of non-rigid shapes. In Proc. workshop on non-rigid registration and tracking through learning (NRTL).

  • Reuter, M., Wolter, F.-E., & Peinecke, N. (2006). Laplace-Beltrami spectra as “shape-DNA” of surfaces and solids. Computer Aided Design, 38, 342–366.

    Article  Google Scholar 

  • Rosman, G., Bronstein, M. M., Bronstein, A. M., & Kimmel, R. (2007). Topologically constrained isometric embedding. In D. Metaxas, R. Klette, & B. Rosenhahn (Eds.), Computational Imaging and Vision : Vol. 36. Workshop on human motion understanding, modeling, capture and animation (pp. 243–262). Berlin: Springer.

    Google Scholar 

  • Roweis, S. T., & Saul, L. K. (2000). Nonlinear dimensionality reduction by locally linear embedding. Science, 290(5500), 2323–2326.

    Article  Google Scholar 

  • Rustamov, R. M. (2007). Laplace-Beltrami eigenfunctions for deformation invariant shape representation. In Proc. symp. geometry processing (SGP) (pp. 225–233).

  • Salukwadze, M. E. (1979). Vector-valued optimization problems in control theory. New York: Academic Press.

    Google Scholar 

  • Salzmann, M., Pilet, J., Ilic, S., & Fua, P. (2007). Surface deformation models for nonrigid 3D shape recovery. Transactions on PAMI, 29(8).

  • Schwartz, E. L., Shaw, A., & Wolfson, E. (1989). A numerical solution to the generalized mapmaker’s problem: Flattening nonconvex polyhedral surfaces. IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 11, 1005–1008.

    Article  Google Scholar 

  • Shum, H. Y., Hebert, M., & Ikeuchi, K. (1995). On 3D shape similarity. School of Computer Science, Carnegie Mellon University.

  • Tal, A., Elad, M., & Ar, S. (2001). Content based retrieval of VRML objects—an iterative and interactive approach. In Proc. Eurographics workshop on multimedia.

  • Tangelder, J. W. H., & Veltkamp, R. C. (2004). A survey of content based 3D shape retrieval methods. In Proc. shape modeling applications (pp. 145–156).

  • Teague, M. R. (1979). Image analysis via the general theory of moments. Journal of Optical Society of America (JOSA), 70, 920–930.

    Article  MathSciNet  Google Scholar 

  • Tennenbaum, J. B., de Silva, V., & Langford, J. C. (2000). A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500), 2319–2323.

    Article  Google Scholar 

  • Vranic, D. V., Saupe, D., & Richter, J. (2001). Tools for 3D-object retrieval: Karhunen-Loeve transform and spherical harmonics. In Proc. IEEE fourth workshop on multimedia signal processing (pp. 293–298).

  • Walter, J., & Ritter, H. (2002). On interactive visualization of high-dimensional data using the hyperbolic plane. In Proc. int’l conf. knowledge discovery and data mining (KDD) (pp. 123–131).

  • Weber, O., Devir, Y. S., Bronstein, A. M., Bronstein, M. M., & Kimmel, R., (2008). Parallel algorithms for approximation of distance maps on parametric surfaces. Proc. ACM Trans. Graphics, to appear.

  • Yu, M., Atmosukarto, I., Leow, W. K., Huang, Z., & Xu, R. (2003). 3D model retrieval with morphing-based geometric and topological feature maps. In Proc. CVPR (Vol. 2).

  • Zhang, Z. Y. (1994). Iterative point matching for registration of free-form curves and surfaces. International Journal of the Computer Vision (IJCV), 13, 119–152.

    Article  Google Scholar 

  • Zhang, C., & Chen, T. (2001a). Efficient feature extraction for 2D/3D objects in meshrepresentation. In Proc. IEEE ICIP (Vol. 3).

  • Zhang, C., & Chen, T. (2001b). Indexing and retrieval of 3D models aided by active learning. ACM Multimedia, 615–616.

  • Zhang, Z., & Zha, H. (2002). Principal manifolds and nonlinear dimension reduction via local tangent space alignment (Technical Report CSE-02-019). Department of Computer Science and Engineering, Pennsylvania State University.

  • Zigelman, G., Kimmel, R., & Kiryati, N. (2002). Texture map** using surface flattening via multi-dimensional scaling. IEEE Transactions on Visualization and Computer Graphics (TVCG), 9(2), 198–207.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science Technion, Israel Institute of Technology, Haifa, 32000, Israel

    Alexander M. Bronstein, Michael M. Bronstein & Ron Kimmel

Authors
  1. Alexander M. Bronstein
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Michael M. Bronstein
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ron Kimmel
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Alexander M. Bronstein.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bronstein, A.M., Bronstein, M.M. & Kimmel, R. Topology-Invariant Similarity of Nonrigid Shapes. Int J Comput Vis 81, 281–301 (2009). https://doi.org/10.1007/s11263-008-0172-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11263-008-0172-2

Keywords

Search

Navigation