Laplace-spectra as fingerprints for shape matching

ABSTRACT

This paper introduces a method to extract fingerprints of any surface or solid object by taking the eigenvalues of its respective Laplace-Beltrami operator. Using an object's spectrum (i.e. the family of its eigenvalues) as a fingerprint for its shape is motivated by the fact that the related eigenvalues are isometry invariants of the object. Employing the Laplace-Beltrami spectra (not the spectra of the mesh Laplacian) as fingerprints of surfaces and solids is a novel approach in the field of geometric modeling and computer graphics. Those spectra can be calculated for any representation of the geometric object (e.g. NURBS or any parametrized or implicitly represented surface or even for polyhedra). Since the spectrum is an isometry invariant of the respective object this fingerprint is also independent of the spatial position. Additionally the eigenvalues can be normalized so that scaling factors for the geometric object can be obtained easily. Therefore checking if two objects are isometric needs no prior alignment (registration/localization) of the objects, but only a comparison of their spectra. With the help of such fingerprints it is possible to support copyright protection, database retrieval and quality assessment of digital data representing surfaces and solids.

REFERENCES

• 1: Mikhail Belkin , Partha Niyogi, Laplacian Eigenmaps for dimensionality reduction and data representation, Neural Computation, v.15 n.6, p.1373-1396, June 2003 [doi>10.1162/089976603321780317]
• 2: Oliver Benedens, Geometry-Based Watermarking of 3D Models, IEEE Computer Graphics and Applications, v.19 n.1, p.46-55, January 1999 [doi>10.1109/38.736468 ]
• 3: Berger, M., Gauduchon, P., and Mazet, E. 1971. Le Spectre d'une Variété Riemannienne. Lecture Notes in Math. 194, Springer Verlag.
• 4: Jean-Daniel Boissonnat , David Cohen-Steiner , Gert Vegter, Isotopic implicit surface meshing, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007401]
• 5: Bronstein, A. M., Bronstein, M. M., and Kimmel, R. 2003. Expression-invariant 3d face recognition. In Proc. AVBPA, Lecture Notes in Comp. Science No. 2688, Springer, 62--69.
• 6: Chavel, I. 1984. Eigenvalues in Riemannian Geometry. Academic Press.
• 7: Chen, H., and Bishop, J. 1997. Delaunay triangulation for curved surfaces. In 6th International Meshing Roundtable Proceedings, 115--127.
• 8: Courant, R., and Hilbert, D. 1993. Methoden der mathematischen Physik. Springer Verlag.
• 9: Cox, T. F., and Cox, M. A. A. 2001. Multidimensional Scaling, 2nd ed. Chapman and Hall.
• 10: Descloux, J., and Tolley, M. 1983. An accurate algorithm for computing the eigenvalues of a polygonal membrane. Comp. Methods Appl. Mech. Engrg. 39, 37--53.
• 11: Elad, A., and Kimmel, R. 2003. On bending invariant signatures for surfaces. IEEE Transactions on PAMI 25, 10, 1285--1295.
• 12: Thomas Funkhouser , Patrick Min , Michael Kazhdan , Joyce Chen , Alex Halderman , David Dobkin , David Jacobs, A search engine for 3D models, ACM Transactions on Graphics (TOG), v.22 n.1, p.83-105, January 2003 [doi>10.1145/588272.588279]
• 13: Gordon, C., Webb, D., and Wolpert, S. 1992. Isospectral plane domains and surfaces via Riemannian orbifolds. Invent. Math. 110, 1--22.
• 14: Iyer, N., Jayanti, S., Lou, K., Kalyanaraman, Y., and Ramani, K. 2005. Three-dimensional shape searching: state-of-the-art review and future trends. Computer Aided Design 37, 5, 509--530.
• 15: Kac, M. 1966. Can one hear the shape of a drum? The Amer. Math. Monthly 73, 4 (Apr.), 1--23.
• 16: Zachi Karni , Craig Gotsman, Spectral compression of mesh geometry, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.279-286, July 2000 [doi>10.1145/344779.344924]
• 17: Ko, K. H., Maekawa, T., Patrikalakis, N. M., Masuda, H., and Wolter, F.-E. 2003. Shape intrinsic properties for free-form object matching. ASME J. of Comp. and Inf. Sci. in Eng. 3, 4 (Dec.), 325--333.
• 18: Mckean, H., and Singer, I. 1967. Curvature and the eigenvalues of the Laplacian. J. Differential Geometry 1, 43--69.
• 19: Minakshisundaram, S., and Pleijel, A. 1949. Some properties of the eigenfunctions of the Laplace-operator on Riemannian manifolds. Canadian Journal of Mathematics 1, 242--256.
• 20: Ryutarou Ohbuchi , Hiroshi Masuda , Masaki Aono, A Shape-Preserving Data Embedding Algorithm for NURBS Curves and Surfaces, Proceedings of the International Conference on Computer Graphics, p.180, June 07-11, 1999
• 21: Ohbuchi, R., Mukaiyama, A., and Takahashi, S. 2002. A frequency-domain approach to watermarking 3d shapes. Eurographics 21, 3.
• 22: Yutaka Ohtake , Alexander G. Belyaev, Dual/Primal mesh optimization for polygonized implicit surfaces, Proceedings of the seventh ACM symposium on Solid modeling and applications, June 17-21, 2002, Saarbrücken, Germany [doi>10.1145/566282.566308]
• 23: Richard J. Prokop , Anthony P. Reeves, A survey of moment-based techniques for unoccluded object representation and recognition, CVGIP: Graphical Models and Image Processing, v.54 n.5, p.438-460, Sept. 1992 [doi>10.1016/1049-9652(92)90027-U]
• 24: M. H. Protter, Can one hear the shape of a drum? revisited, SIAM Review, v.29 n.2, p.185-197, June 1, 1987 [doi>10.1137/1029041]
• 25: Strang, G. 1986. Introduction to Applied Mathematics. Wesley-Cambridge Press.
• 26: Tucker, T. M., and Kurfess, T. R. 2003. Newton methods for parametric surface registration. Part I. Theory. Computer-Aided Design 35, 1, 107--114.
• 27: F.-E. Wolter , K.-I. Friese, Local and Global Geometric Methods for Analysis Interrogation, Reconstruction, Modification and Design of Shape, Proceedings of the International Conference on Computer Graphics, p.137, June 19-24, 2000
• 28: Wolter, F.-E., Peinecke, N., and Reuter, M. 2004. Geometric modeling of complex shapes and engineering artifacts. In Encyclopedia of Computational Mechanics, E. Stein, R. de Borst, and T. Hugues, Eds., vol. 1. John Wiley and Sons.
• 29: Guoliang Xu, Discrete Laplace-Beltrami operators and their convergence, Computer Aided Geometric Design, v.21 n.8, p.767-784, October 2004 [doi>10.1016/j.cagd.2004.07.007]
• 30: Zelditch, S. 1998. The inverse spectral problem for surfaces of revolution. Journal of Differential Geometry 49, 2, 207--264.
• 31: Zienkiewicz, O., and Taylor, R. 2000. The Finite Element Method - Volume 1: The Basis. Butterworth Heinemann.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Similarity measures

Additional Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

  K. Computing Milieux
  K.5 LEGAL ASPECTS OF COMPUTING
      K.5.1 Hardware/Software Protection
          Subjects: Copyrights

Keywords:
NURBS, copyright protection, database retrieval, fingerprints, laplace-beltrami operator, parameterized surfaces and bodies, polyhedra, shape invariants, shape matching