article

Technical Section: Discrete Laplace-Beltrami operators for shape analysis and segmentation

Authors:

Silvia Biasotti,

Daniela Giorgi,

Giuseppe Patanè,

Michela SpagnuoloAuthors Info & Claims

Computers and Graphics, Volume 33, Issue 3

Pages 381 - 390

https://doi.org/10.1016/j.cag.2009.03.005

Published: 01 June 2009 Publication History

Abstract

Shape analysis plays a pivotal role in a large number of applications, ranging from traditional geometry processing to more recent 3D content management. In this scenario, spectral methods are extremely promising as they provide a natural library of tools for shape analysis, intrinsically defined by the shape itself. In particular, the eigenfunctions of the Laplace-Beltrami operator yield a set of real-valued functions that provide interesting insights in the structure and morphology of the shape. In this paper, we first analyze different discretizations of the Laplace-Beltrami operator (geometric Laplacians, linear and cubic FEM operators) in terms of the correctness of their eigenfunctions with respect to the continuous case. We then present the family of segmentations induced by the nodal sets of the eigenfunctions, discussing its meaningfulness for shape understanding.

References

[1]

ARPACK. The Arnoldi package {http://www.caam.rice.edu/software/ARPACK/}.

[2]

Attene, M., Katz, S., Mortara, M., Patanè, G., Spagnuolo, M. and Tal, A., Mesh segmentation-a comparative study. In: Proceedings of shape modeling international, pp. 14-25.

Digital Library

[3]

Attene, M., Robbiano, F., Spagnuolo, M. and Falcidieno, B., Semantic annotation of 3D surface meshes based on feature characterization. Proceedings of the semantic and digital media technologies. v4816. 126-139.

[4]

Bar, C., On nodal sets for Dirac and Laplace operators. Communications in Mathematical Physics. v188. 709-721.

[5]

Belkin, M. and Niyogi, P., Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computations. v15. 1373-1396.

[6]

Belkin, M., Sun, J. and Wang, Y., Discrete Laplace operator on meshed surfaces. In: Symposium on computational geometry, pp. 278-287.

[7]

Berger, M., Gauduchon, P. and Mazet, E., Le Spectre d'une Variété Riemannienne. 1971. Springer, Berlin.

[8]

Biasotti, S., Falcidieno, B., Frosini, P., Giorgi, D., Landi, C. and Patanè, G., 3D shape description and matching based on properties of real functions. In: Eurographics tutorial proceedings, pp. 949-998.

[9]

Biasotti, S., De Floriani, L., Falcidieno, B., Frosini, P., Giorgi, D. and Landi, C., Describing shapes by geometrical-topological properties of real functions. ACM Computing Surveys. v40 i4. 1-87.

[10]

Biederman, I., Recognition-by-components: a theory of human image understanding. Psychological Review. v94 i2. 115-147.

[11]

Chavel, I., Eigenvalues in Riemannian geometry. 1984. Academic Press, New York.

[12]

Cheng, S.-Y., Eigenfunctions and nodal sets. Comment: Mathematics Helvetici. v51. 43-55.

[13]

Courant, R. and Hilbert, D., Methods of mathematical physics, vol. 1. 1953. Interscience, New York.

[14]

Demmel, J.W., Eisenstat, S.C., Gilbert, J.R., Li, X.S. and Liu, J.W.H., A supernodal approach to sparse partial pivoting. SIAM Journal on Matrix Analysis and Applications. v20 i3. 720-755.

[15]

Desbrun, M., Kanzo, E. and Tong, Y., Discrete differential forms for computational modeling. In: ACM Siggraph '05 course notes on discrete differential geometry,

[16]

Desbrun, M., Meyer, M., Schröder, P. and Barr, A.H., Implicit fairing of irregular meshes using diffusion and curvature flow. In: Proceedings of the ACM Siggraph'99, pp. 317-324.

[17]

Dong, S., Bremer, P.-T., Garland, M. and Pascucci, V., Spectral surface quadrangulation. In: Proceedings of the ACM Siggraph, pp. 1057-1066.

[18]

Donnelly, H. and Fefferman, C., Nodal sets for eigenfunctions of the Laplacian on surfaces. Journal of American Mathematical Society. v3. 333-353.

[19]

Dyer R, Zhang H, Möller T, Clements A. An investigation of the spectral robustness of mesh Laplacians. Technical Report 2007-17, SFU CS School; 2007.

[20]

Dziuk, G., Finite elements for the Beltrami operator on arbitrary surfaces. In: Hildebrandt, S., Leis, R. (Eds.), Partial differential equations and calculus of variations, pp. 142-155.

[21]

Eremenko, A., Jakobson, D. and Nadirashvili, N., On nodal sets and nodal domains on S2 and R2. Annales de l'Istitut Fourier. v57 i7. 2345-2360.

[22]

Floater, M.S. and Hormann, K., Surface parameterization: a tutorial and survey. In: Advances in multiresolution for geometric modelling, Springer, Berlin. pp. 157-186.

[23]

Giorgi D, Biasotti S, Paraboschi L. Watertight models track. Technical Report 09, IMATI, Genova; 2007.

[24]

Gomes FM, Sorensen DC. ARPACK++: A C++ implementation of ARPACK eigenvalue package, 1997.

[25]

Gotsman, C., Gu, X. and Sheffer, A., Fundamentals of spherical parametrization for 3D meshes. ACM Transactions on Graphics. v3 i22. 358-363.

[26]

Hoffman, D.D. and Richards, W.A., Parts of recognition. Cognition. v18 i1-3. 65-96.

[27]

Jain, V. and Zhang, H., Robust 3D shape correspondence in the spectral domain. In: Proceedings of the shape modeling and applications, pp. 118-129.

[28]

Jain, V. and Zhang, H., A spectral approach to shape-based retrieval of articulated 3D models. Computer Aided Design. v39 i5. 398-407.

[29]

Jakobson, D., Nadirashvili, N. and Toth, J., Geometric properties of eigenfunctions. Russian Mathematical Surveys. v56. 67-88.

[30]

Karni, Z. and Gotsman, C., Spectral compression of mesh geometry. In: ACM Siggraph, pp. 279-286.

Digital Library

[31]

Katz, S., Leifman, G. and Tal, A., Mesh segmentation using feature point and core extraction. The Visual Computer. v21. 649-658.

[32]

Keating, J.P., Mezzadri, F. and Monastra, A.G., Nodal domain distributions for quantum maps. Journal of Physics A: Mathematical General. v36 i3. 53-59.

[33]

Lévy, B., Laplace-Beltrami eigenfunctions: towards an algorithm that understands geometry. In: Proceedings of shape modeling and applications, pp. 13

[34]

Lévy, B. and Vallet, B., Spectral geometry processing with manifold harmonics. Computer Graphics Forum. v2 i27.

[35]

Liu, R. and Zhang, H., Mesh segmentation via spectral embedding and contour analysis. Computer Graphics Forum. v26 i3. 385-394.

[36]

Meyer M, Desbrun M, Schröder P, Barr AH. Discrete differential-geometry operators for triangulated 2-manifolds. In: Proceedings of the VisMath, 2002.

[37]

Nadirashvili, N.S., Metric properties of eigenfunctions of the Laplace operator on manifolds. Annales de l'Istitut Fourier. v41 i1. 259-265.

[38]

Niethammer M, Reuter M, Wolter F-E, Bouix S, Peinecke N, Koo M-S, et al. Global medical shape analysis using the Laplace-Beltrami spectrum. In: MICCAI conference, Berlin: Springer; 2007. p. 850-7.

[39]

Ovsjanikov M, Sun J, Guibas L. Global intrinsic symmetries of shapes. In: Eurographics symposium on geometry processing (SGP), 2008.

Digital Library

[40]

Parlett, B.N., The symmetric eigenvalue problem. 1980. Prentice-Hall, Englewood Cliffs, NJ.

[41]

Patanè, G., Spagnuolo, M. and Falcidieno, B., Para-graph: graph-based parameterization of triangle meshes with arbitrary genus. Computer Graphics Forum. v23 i4. 783-797.

[42]

Patanè, G., Spagnuolo, M. and Falcidieno, B., Families of cut-graphs for bordered meshes with arbitrary genus. Graphical Models. v69 i2. 119-138.

[43]

Patanè G, Spagnuolo M, Falcidieno B. Topological generators and cut-graphs of arbitrary triangle meshes. In: Proceedings of shape modeling and applications, 2007. p. 113-22.

Digital Library

[44]

Peinecke, N., Wolter, F.-E. and Reuter, M., Laplace spectra as fingerprints for image recognition. Computer Aided Design. v39 i6. 460-476.

[45]

Pinkall, U. and Polthier, K., Computing discrete minimal surfaces and their conjugates. Experimental Mathematics. v1 i2.

[46]

Reuter M. Laplace Spectra for Shape Recognition. Books on Demand, ISBN 3-8334-5071-1, 2006.

[47]

Reuter M, Niethammer M, Wolter F-E, Bouix S, Shenton ME. Global medical shape analysis using the volumetric Laplace spectrum. In: IEEE Proceedings of the cyberworlds, 2007. p. 417-26.

Digital Library

[48]

Reuter M, Wolter F-E, Peinecke N. Laplace-spectra as fingerprints for shape matching. In: Proceedings of the ACM symposium on solid and physical modeling, 2005. p. 101-6.

Digital Library

[49]

Reuter, M., Wolter, F.-E. and Peinecke, N., Laplace-Beltrami spectra as Shape-DNA of surfaces and solids. Computer Aided Design. v38 i4. 342-366.

[50]

Reuter M, Wolter F-E, Shenton M, Niethammer M. Laplace-Beltrami eigenvalues and topological features of eigenfunctions for statistical shape analysis. Computer Aided Design, 2009.

Digital Library

[51]

Rosenberg, S., The Laplacian on a Riemannian manifold. 1997. Cambridge University Press, Cambridge.

[52]

Rustamov, R.M., Laplace-Beltrami eigenfunctions for deformation invariant shape representation. In: Proceedings of the Symposium on geometry processing, pp. 225-233.

[53]

Savo, A., Lower bounds for the nodal length of eigenfunctions of the Laplacian. Annals of Global Analysis and Geometry. v19 i2. 133-151.

[54]

Shamir, A., Segmentation and shape extraction of 3D boundary meshes. In: Eurographics STAR report,

[55]

Steiner, D. and Fischer, A., Cutting 3D freeform objects with genus-n into single boundary surfaces using topological graphs. In: Proceedings of the symposium on solid modeling and applications, pp. 336-343.

[56]

Strang, G. and Fix, G.J., An analysis of the finite element method. 1973. Prentice-Hall, Englewood Cliffs, NJ.

[57]

Taubin, G., A signal processing approach to fair surface design. In: ACM Siggraph'95, pp. 351-358.

[58]

Wardetzky, M., Bergou, M., Harmon, D., Zorin, D. and Grinspun, E., Discrete quadratic curvature energies. Computer Aided Geometric Design. v8 i21. 398-407.

[59]

Wardetzky, M., Mathur, S., Kalberer, F. and Grinspun, E., Discrete Laplace operators: no free lunch. In: Proceedings of the symposium on geometry processing,

[60]

Xu, G., Discrete Laplace-Beltrami operators and their convergence. Computer Aided Geometric Design. v21. 767-784.

[61]

Zhang, E., Mischaikow, K. and Turk, G., Feature-based surface parameterization and texture mapping. ACM Transactions on Graphics. v24 i1. 1-27.

Digital Library

[62]

Zhang, H., van Kaick, O. and Dyer, R., Spectral methods for mesh processing and analysis. In: Eurographics STAR report, pp. 1-22.

Cited By

Daßler NGünther T(2024)Variational Feature Extraction in Scientific VisualizationACM Transactions on Graphics10.1145/365821943:4(1-16)Online publication date: 19-Jul-2024
https://dl.acm.org/doi/10.1145/3658219
Park JWong LWalters ROh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Modeling dynamics over meshes with gauge equivariant nonlinear message passingProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3666794(15277-15302)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3666794
Bag SGolder RSarkar SMaity S(2023)SENEEngineering Applications of Artificial Intelligence10.1016/j.engappai.2023.106332123:PCOnline publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1016/j.engappai.2023.106332
Show More Cited By

Technical Section: Discrete Laplace-Beltrami operators for shape analysis and segmentation
1. Computing methodologies
  1. Computer graphics
    1. Shape modeling
2. Theory of computation

Recommendations

Hierarchical Shape Segmentation and Registration via Topological Features of Laplace-Beltrami Eigenfunctions

This work introduces a method to hierarchically segment articulated shapes into meaningful parts and to register these parts across populations of near-isometric shapes (e.g. head, arms, legs and fingers of humans in different body postures). The method ...
Laplace-Beltrami eigenvalues and topological features of eigenfunctions for statistical shape analysis

This paper proposes the use of the surface-based Laplace-Beltrami and the volumetric Laplace eigenvalues and eigenfunctions as shape descriptors for the comparison and analysis of shapes. These spectral measures are isometry invariant and therefore ...
Solving eigenvalue problems on curved surfaces using the Closest Point Method

Eigenvalue problems are fundamental to mathematics and science. We present a simple algorithm for determining eigenvalues and eigenfunctions of the Laplace-Beltrami operator on rather general curved surfaces. Our algorithm, which is based on the Closest ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Computers and Graphics

Computers and Graphics Volume 33, Issue 3

June, 2009

247 pages

ISSN:0097-8493

Issue’s Table of Contents

Copyright © Elsevier Ltd © 2009.

Publisher

Pergamon Press, Inc.

United States

Publication History

Published: 01 June 2009

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

57
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 23 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Daßler NGünther T(2024)Variational Feature Extraction in Scientific VisualizationACM Transactions on Graphics10.1145/365821943:4(1-16)Online publication date: 19-Jul-2024
https://dl.acm.org/doi/10.1145/3658219
Park JWong LWalters ROh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Modeling dynamics over meshes with gauge equivariant nonlinear message passingProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3666794(15277-15302)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3666794
Bag SGolder RSarkar SMaity S(2023)SENEEngineering Applications of Artificial Intelligence10.1016/j.engappai.2023.106332123:PCOnline publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1016/j.engappai.2023.106332
Babu MFranciosa PShekhar PCeglarek D(2023)Object Shape Error Modelling and Simulation During Early Design Phase by Morphing Gaussian Random FieldsComputer-Aided Design10.1016/j.cad.2023.103481158:COnline publication date: 1-May-2023
https://dl.acm.org/doi/10.1016/j.cad.2023.103481
Choi GLiu YLui L(2022)Free-Boundary Conformal Parameterization of Point CloudsJournal of Scientific Computing10.1007/s10915-021-01641-690:1Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1007/s10915-021-01641-6
Zhang HWang C(2020)Total variation diffusion and its application in shape decompositionComputers and Graphics10.1016/j.cag.2020.05.02290:C(95-107)Online publication date: 1-Aug-2020
https://dl.acm.org/doi/10.1016/j.cag.2020.05.022
Mao TDong WMao ALi GLuo J(2020)Pose Transfer of 2D Human Cartoon CharactersAdvances in Computer Graphics10.1007/978-3-030-61864-3_22(256-266)Online publication date: 20-Oct-2020
https://dl.acm.org/doi/10.1007/978-3-030-61864-3_22
Zimmer VGonzález Ballester MPiella G(2019)Multimodal image registration using Laplacian commutatorsInformation Fusion10.1016/j.inffus.2018.09.00949:C(130-145)Online publication date: 1-Sep-2019
https://dl.acm.org/doi/10.1016/j.inffus.2018.09.009
Wang YBen-Chen MPolterovich ISolomon J(2018)Steklov Spectral Geometry for Extrinsic Shape AnalysisACM Transactions on Graphics10.1145/315215638:1(1-21)Online publication date: 14-Dec-2018
https://dl.acm.org/doi/10.1145/3152156
Nagar RRaman S(2018)Fast and Accurate Intrinsic Symmetry DetectionComputer Vision – ECCV 201810.1007/978-3-030-01246-5_26(433-450)Online publication date: 8-Sep-2018
https://dl.acm.org/doi/10.1007/978-3-030-01246-5_26
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents