Hierarchical Shape Segmentation and Registration via Topological Features of Laplace-Beltrami Eigenfunctions
Open accessThe DOI matches its Crossref record; 65 of the 65 references it cites were found in a registry or an index.
Abstract
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 exploits the isometry invariance of eigenfunctions of the Laplace-Beltrami operator and uses topological features (level sets at important saddles) for the segmentation. Concepts from persistent homology are employed for a hierarchical representation, for the elimination of topological noise and for the comparison of eigenfunctions. The obtained parts can be registered via their spectral embedding across a population of near isometric shapes. This work also presents the highly accurate computation of eigenfunctions and eigenvalues with cubic finite elements on triangle meshes and discusses the construction of persistence diagrams from the Morse-Smale complex as well as the relation to size functions.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Lecture Notes in Computer Science 1205
(1999) · Industrial Robot: An International Journal · doi:10.1108/ir.1999.04926fae.001 · Cited by 38,662
Zienkiewicz, O. C. (1989) · Cited by 14,802
Methods of Mathematical Physics
Courant, R., & Hilbert, D. (1989) · Wiley eBooks · doi:10.1002/9783527617210 · Cited by 8,067
Laplacian Eigenmaps for Dimensionality Reduction and Data Representation
Belkin, M., & Niyogi, P. (2003) · Neural Computation · doi:10.1162/089976603321780317 · Cited by 7,621 · cited 3×
“These spectral embeddings have been described in the past in manifold learning (Belkin and Niyogi 2003; Coifman et al. 2005) and are also used in this work for the final registration step, but not for the segmentation. Note that the segmentations in Rustamov (2007) depend on the number of desired clusters and do not g…”
BackgroundMethodInfluentialAn Analysis of the Finite Element Method
I., E., Strang, G., & Fix, G. J. (1974) · Mathematics of Computation · doi:10.2307/2005716 · Cited by 3,484
An analysis of the finite element method
(1980) · Advances in Water Resources · doi:10.1016/0309-1708(80)90069-x · Cited by 3,466
The Symmetric Eigenvalue Problem
Parlett, B. N. (1998) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611971163 · Cited by 3,192
Topological Persistence and Simplification
Edelsbrunner, Letscher, & Zomorodian (2002) · Discrete & Computational Geometry · doi:10.1007/s00454-002-2885-2 · Cited by 1,779
Eigenvalues in Riemannian Geometry
(1984) · Pure and Applied Mathematics · doi:10.1016/s0079-8169(08)x6051-9 · Cited by 1,742 · cited 1×
“(6)) and div the divergence both defined on the manifold (see Chavel [35]).”
BackgroundSurvey of graph database models
Angles, R., & Gutierrez, C. (2008) · ACM Computing Surveys · doi:10.1145/1322432.1322433 · Cited by 1,706
Metric Structures for Riemannian and Non-Riemannian Spaces
(2007) · Modern Birkhäuser Classics · doi:10.1007/978-0-8176-4583-0 · Cited by 1,694 · cited 1×
“To better define this term, we shall use the Gromov-Hausdorff distance [33,34], which is a useful measure of distance between two metric spaces (here bounded Riemannian manifolds M 1 , M 2 ).”
MethodCoifman, R. R., Lafon, S., Lee, A. B., Maggioni, M., Nadler, B., Warner, F., & Zucker, S. W. (2005) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0500334102 · Cited by 1,675
Implicit fairing of irregular meshes using diffusion and curvature flow
Desbrun, M., Meyer, M., Schröder, P., & Barr, A. H. (1999) · Proceedings of the 26th annual conference on Computer graphics and interactive techniques - SIGGRAPH '99 · doi:10.1145/311535.311576 · Cited by 1,538 · cited 1×
“Note that the linear FEM case leads to the mesh Laplace operator also known as cotangent weights with area adjustment (Desbrun et al. 1999) after lumping the mass matrix B (adding each off-diagonal entry to the diagonal).”
BackgroundMilnor, J. (1963) · doi:10.1515/9781400881802 · Cited by 1,390
Deformation transfer for triangle meshes
Sumner, R. W., & Popović, J. (2004) · ACM Transactions on Graphics · doi:10.1145/1015706.1015736 · Cited by 1,052
Edelsbrunner, H., & Harer, J. (2008) · Contemporary Mathematics · doi:10.1090/conm/453/08802 · Cited by 848 · cited 6×
“A pose invariant shape representation based on geodesic distances and multidimensional scaling (as proposed in Elad and Kimmel 2003 with application to shape classification) has been used for shape segmentation in Katz et al. (2005) by extracting feature points and cores. The method can produce consistent segmentation…”
MethodInfluentialA Supernodal Approach to Sparse Partial Pivoting
Demmel, J. W., Eisenstat, S. C., Gilbert, J. R., Li, X. S., & Liu, J. W. H. (1999) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/s0895479895291765 · Cited by 840 · cited 2×
“We use ARPACK for solving the shift-inverse problem and SuperLU (Demmel et al. 1999) for the sparse factorization.”
MethodLaplace–Beltrami spectra as ‘Shape-DNA’ of surfaces and solids
Reuter, M., Wolter, F.-E., & Peinecke, N. (2006) · Computer-Aided Design · doi:10.1016/j.cad.2005.10.011 · Cited by 779 · cited 5×
“The presented method for shape segmentation can also be extended to 3D solids using the 3D Laplacian on tetrahedra or voxel representations as described in [23,26].”
MethodInfluentialSelf-citationMethods of Mathematical Physics: Partial Differential Equations
Courant, R., & Hilbert, D. (1989) · doi:10.1002/9783527617234 · Cited by 735
A survey on Mesh Segmentation Techniques
Shamir, A. (2008) · Computer Graphics Forum · doi:10.1111/j.1467-8659.2007.01103.x · Cited by 593 · cited 1×
“Recent over-views on segmentation algorithms can be found in [4] and [5].”
BackgroundHierarchical mesh decomposition using fuzzy clustering and cuts
Katz, S., & Tal, A. (2003) · ACM SIGGRAPH 2003 Papers · doi:10.1145/1201775.882369 · Cited by 577 · cited 1×
“Quite a few segmentation methods, e.g. [8,9], are hierarchical (as is the one in this paper).”
Methods of Mathematical Physics, Vol. I
Courant, R., & Hilbert, D. (1954) · Physics Today · doi:10.1063/1.3061619 · Cited by 556 · cited 1×
“For more details we refer the reader to our earlier work [23,36] and to Courant and Hilbert [37].”
MethodLaplace-Beltrami eigenfunctions for deformation invariant shape representation
Rustamov, R. M. (2007) · doi:10.5555/1281991.1282022 · Cited by 541
Hierarchical mesh decomposition using fuzzy clustering and cuts
Katz, S., & Tal, A. (2003) · ACM Transactions on Graphics · doi:10.1145/882262.882369 · Cited by 477
Hoffman, D. D., & Singh, M. (1997) · Cognition · doi:10.1016/s0010-0277(96)00791-3 · Cited by 469 · cited 1×
“by identifying concave regions or regions of negative principal curvature ( Hoffmann and Singh 1997 ), ignoring insignificant noise.”
BackgroundHierarchical mesh segmentation based on fitting primitives
Attene, M., Falcidieno, B., & Spagnuolo, M. (2006) · The Visual Computer · doi:10.1007/s00371-006-0375-x · Cited by 462
On bending invariant signatures for surfaces
Elad, A., & Kimmel, R. (2003) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2003.1233902 · Cited by 458 · cited 1×
“A pose invariant shape representation based on geodesic distances and multidimensional scaling (as proposed in [11] with application to shape clas-sification) has been used for shape segmentation in [12] by extracting feature points and cores.”
MethodLaplace-Beltrami Eigenfunctions Towards an Algorithm That "Understands" Geometry
Levy, B. (2006) · IEEE International Conference on Shape Modeling and Applications 2006 (SMI'06) · doi:10.1109/smi.2006.21 · Cited by 422
Smale, S. (1961) · The Annals of Mathematics · doi:10.2307/1970311 · Cited by 396 · cited 1×
“The reader is referred to [38,39] for more background on Morse theory and on the Morse-Smale complex.”
MethodSpectral Geometry Processing with Manifold Harmonics
Vallet, B., & Lévy, B. (2008) · Computer Graphics Forum · doi:10.1111/j.1467-8659.2008.01122.x · Cited by 386 · cited 1×
“Other work employing spectral entities of the Laplace Beltrami operator includes retrieval (Reuter et al. 2006; Peinecke et al. 2007), medical shape analysis (Niethammer et al. 2007; Reuter et al. 2007, 2009; Shi et al. 2008), filtering/smoothing (Levy 2006; Qiu et al. 2006; Vallet and Levy 2008 ) of which specificall…”
MethodFinite Elements for the Beltrami operator on arbitrary surfaces
Dziuk, G. (1988) · Lecture Notes in Mathematics · doi:10.1007/bfb0082865 · Cited by 378
Mesh segmentation using feature point and core extraction
Katz, S., Leifman, G., & Tal, A. (2005) · The Visual Computer · doi:10.1007/s00371-005-0344-9 · Cited by 375 · cited 1×
“A pose invariant shape representation based on geodesic distances and multidimensional scaling (as proposed in [11] with application to shape clas-sification) has been used for shape segmentation in [12] by extracting feature points and cores.”
MethodDiscrete Laplace–Beltrami operators for shape analysis and segmentation
Reuter, M., Biasotti, S., Giorgi, D., Patanè, G., & Spagnuolo, M. (2009) · Computers & Graphics · doi:10.1016/j.cag.2009.03.005 · Cited by 319 · cited 6×
“In Rustamov (2007) a very similar Laplace operator is used, however, constructed by only linear finite elements with a lumped (diagonal) mass matrix (see also Reuter et al. 2009 for a comparison of different Laplace Beltrami discretizations).”
BackgroundMethodInfluentialSelf-citationSpectral surface quadrangulation
Dong, S., Bremer, P.-T., Garland, M., Pascucci, V., & Hart, J. C. (2006) · ACM Transactions on Graphics · doi:10.1145/1141911.1141993 · Cited by 315
A Theoretical and Computational Framework for Isometry Invariant Recognition of Point Cloud Data
Mémoli, F., & Sapiro, G. (2005) · Foundations of Computational Mathematics · doi:10.1007/s10208-004-0145-y · Cited by 311 · cited 1×
“To better define this term, we shall use the Gromov-Hausdorff distance [33,34], which is a useful measure of distance between two metric spaces (here bounded Riemannian manifolds M 1 , M 2 ).”
MethodMesh Segmentation - A Comparative Study
Attene, M., Katz, S. M., Mortara, M., Patanè, G., Spagnuolo, M., & Tal, A. (2006) · IEEE International Conference on Shape Modeling and Applications · doi:10.1109/smi.2006.24 · Cited by 298 · cited 1×
“Recent overviews on segmentation algorithms can be found in [4] and [5].”
BackgroundHierarchical Morse--Smale Complexes for Piecewise Linear 2-Manifolds
Edelsbrunner, H., Harer, J., & Zomorodian, A. (2003) · Discrete and Computational Geometry · doi:10.1007/s00454-003-2926-5 · Cited by 293
Stability of persistence diagrams
Cohen-Steiner, D., Edelsbrunner, H., & Harer, J. (2005) · Proceedings of the twenty-first annual symposium on Computational geometry · doi:10.1145/1064092.1064133 · Cited by 251 · cited 1×
“A good way to represent the topology of the function h is given by the persistence diagram [42,43], where the persistence pairs are plotted as a set of points ( x, y ) = ( h ( a ) , h ( b )) for each minimum/saddle or saddle/maximum pair ( a, b ).”
BackgroundMorse-smale complexes for piecewise linear 3-manifolds
Edelsbrunner, H., Harer, J., Natarajan, V., & Pascucci, V. (2003) · Proceedings of the nineteenth annual symposium on Computational geometry · doi:10.1145/777792.777846 · Cited by 237
Efficient Computation of Isometry‐Invariant Distances Between Surfaces
Bronstein, A. M., Bronstein, M. M., & Kimmel, R. (2006) · SIAM Journal on Scientific Computing · doi:10.1137/050639296 · Cited by 237 · cited 1×
“Further examples are the centaur [61], the lion and the horse family [62].”
BackgroundGlobal Intrinsic Symmetries of Shapes
Ovsjanikov, M., Sun, J., & Guibas, L. (2008) · Computer Graphics Forum · doi:10.1111/j.1467-8659.2008.01273.x · Cited by 228 · cited 1×
“Actually this problem is nicely exploited in [60] who use it to detect the intrinsic symmetries.”
BackgroundDescribing shapes by geometrical-topological properties of real functions
Biasotti, S., De Floriani, L., Falcidieno, B., Frosini, P., Giorgi, D., Landi, C., Papaleo, L., & Spagnuolo, M. (2008) · ACM Computing Surveys · doi:10.1145/1391729.1391731 · Cited by 213 · cited 1×
“A good overview also treating the evolution of the used concepts (size functions, Morse-Smale complex, Reeb graph and persistent homology) can be found in Biasotti et al. (2008).”
BackgroundSegmentation of 3D meshes through spectral clustering
Liu, R., & Zhang, H. (2004) · 12th Pacific Conference on Computer Graphics and Applications, 2004. PG 2004. Proceedings. · doi:10.1109/pccga.2004.1348360 · Cited by 213 · cited 1×
“Similar methods, but without the isometry invariance, include [13] who use a spectral embedding of an affinity matrix containing geodesic distances plus non-intrinsic angular distances of faces to perform a k -means clustering.”
MethodZhang, H., Van Kaick, O., & Dyer, R. (2010) · Computer Graphics Forum · doi:10.1111/j.1467-8659.2010.01655.x · Cited by 212 · cited 1×
“More details on constructing form functions can be found in Zienkiewicz and Taylor (2000). The local matrices I1 to I4 of the integrals are shown in Table 1.”
BackgroundA topological hierarchy for functions on triangulated surfaces
Bremer, P.-T., Hamann, B., Edelsbrunner, H., & Pascucci, V. (2004) · IEEE Transactions on Visualization and Computer Graphics · doi:10.1109/tvcg.2004.3 · Cited by 207 · cited 1×
“Usually the paths are not completely deleted, but only hidden and stored in a hierarchical representation (see also [41]) making it possible to vary the desired level of detail freely.”
BackgroundDeformation transfer for triangle meshes
Sumner, R. W., & Popović, J. (2004) · ACM SIGGRAPH 2004 Papers · doi:10.1145/1186562.1015736 · Cited by 203
Reuter, M., Wolter, F.-E., Shenton, M., & Niethammer, M. (2009) · Computer-Aided Design · doi:10.1016/j.cad.2009.02.007 · Cited by 191 · cited 1×
“Note that [22] employs level sets of eigenfunctions to implictly construct correspondence of brain structures for statistical shape analysis.”
BackgroundSelf-citationArticulated Shape Matching Using Laplacian Eigenfunctions and Unsupervised Point Registration
Mateus, D., Horaud, R., Knossow, D., Cuzzolin, F., & Boyer, E. (2008) · Cited by 166
Laplace-spectra as fingerprints for shape matching
Reuter, M., Wolter, F.-E., & Peinecke, N. (2005) · Proceedings of the 2005 ACM symposium on Solid and physical modeling · doi:10.1145/1060244.1060256 · Cited by 161 · cited 1×
“The higher order approach used here is already described in [53,23,36] for triangle meshes, NURBS patches, other parametrized surfaces and (parametrized) 3D tetrahedra meshes and in [26] for voxels.”
MethodSelf-citationFast mesh segmentation using random walks
Lai, Y., Hu, S., Martin, R. R., & Rosin, P. L. (2008) · ACM Symposium on Solid and Physical Modeling (SPM) · doi:10.1145/1364901.1364927 · Cited by 154 · cited 1×
“A recent example is [7] which extends a random walk method to meshes for automatic segmentation (see also the related work section for a good overview).”
MethodRobust 3D Shape Correspondence in the Spectral Domain
Jain, V., & Zhang, H. (2006) · IEEE International Conference on Shape Modeling and Applications 2006 (SMI'06) · doi:10.1109/smi.2006.31 · Cited by 148 · cited 2×
“[19] again use an embedding space of the affinity matrix filtered with a Gaussian kernel, while the other two methods rely on a graph Laplacian (borrowed from manifold learning) for the embedding of the 2D surface meshes and 3D voxel-based shapes respectively.”
MethodQiu, A., Bitouk, D., & Miller, M. I. (2006) · IEEE Transactions on Medical Imaging · doi:10.1109/tmi.2006.882143 · Cited by 134 · cited 1×
“Other work employing spectral entities of the Laplace Beltrami operator includes retrieval (Reuter et al. 2006; Peinecke et al. 2007), medical shape analysis (Niethammer et al. 2007; Reuter et al. 2007, 2009; Shi et al. 2008), filtering/smoothing (Levy 2006; Qiu et al. 2006; Vallet and Levy 2008) of which specifically…”
MethodA Hierarchical Segmentation of Articulated Bodies
de Goes, F., Goldenstein, S. K., & Velho, L. C. P. R. (2008) · Computer Graphics Forum · doi:10.1111/j.1467-8659.2008.01274.x · Cited by 131 · cited 2×
“Nevertheless, [18] shows some impressive hierarchical segmentations.”
BackgroundArticulated shape matching using Laplacian eigenfunctions and unsupervised point registration
Mateus, D., Horaud, R., Knossow, D., Cuzzolin, F., & Boyer, E. (2008) · 2008 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2008.4587538 · Cited by 130 · cited 1×
“Actually no intrinsic method, neither eigenfunction histograms (Mateus et al. 2008) nor correspondence in the spectral domain (Jain et al.”
MethodMesh Segmentation via Spectral Embedding and Contour Analysis
Liu, R., & Zhang, H. (2007) · Computer Graphics Forum · doi:10.1111/j.1467-8659.2007.01061.x · Cited by 125 · cited 1×
“The authors later remove the dependency on geodesic distances in [14] and instead propose to use the graph Laplacian and another more geometric operator M to embed the shape into the plane via the first two non constant eigenvectors.”
MethodExtending Persistence Using Poincaré and Lefschetz Duality
Cohen‐Steiner, D., Edelsbrunner, H., & Harer, J. (2009) · Foundations of Computational Mathematics · doi:10.1007/s10208-008-9038-9 · Cited by 124 · cited 1×
“Nevertheless, for higher genus surfaces ( g > 0), the Reeb graph can be used to additionally pair so called “essential” homology classes (see [49,50]) that represent important features such as handles (this is called extended persistence).”
Extending Persistence Using Poincaré and Lefschetz Duality
Cohen‐Steiner, D., Edelsbrunner, H., & Harer, J. (2008) · Foundations of Computational Mathematics · doi:10.1007/s10208-008-9027-z · Cited by 124
NON-RIGID SPECTRAL CORRESPONDENCE OF TRIANGLE MESHES
Jain, V., Zhang, H., & van Kaick, O. M. (2007) · International Journal of Shape Modeling · doi:10.1142/s0218654307000968 · Cited by 113 · cited 4×
“2008) nor correspondence in the spectral domain (Jain et al. 2007), can solve this.”
BackgroundInfluentialExtreme Elevation on a 2-Manifold
Agarwal, P. K., Edelsbrunner, H., Harer, J., & Wang, Y. (2006) · Discrete & Computational Geometry · doi:10.1007/s00454-006-1265-8 · Cited by 108
A distance for similarity classes of submanifolds of a Euclidean space
Frosini, P. (1990) · Bulletin of the Australian Mathematical Society · doi:10.1017/s0004972700028574 · Cited by 105 · cited 2×
“Size functions (Frosini 1990; Frosini and Landi 1997) are defined on the half-plane H+ := {(x, y) ∈”
BackgroundGlobal Medical Shape Analysis Using the Laplace-Beltrami Spectrum
Niethammer, M., Reuter, M., Wolter, F.-E., Sylvain Bouix, A., Peinecke, N., Koo, M., & Shenton, M. E. (2007) · Springer eBooks · doi:10.1007/978-3-540-75757-3_103 · Cited by 84
Self-citationAnisotropic Laplace-Beltrami eigenmaps: Bridging Reeb graphs and skeletons
Shi, Y., Lai, R., Krishna, S., Sicotte, N. L., Dinov, I. D., & Toga, A. W. (2008) · 2009 IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops · doi:10.1109/cvprw.2008.4563018 · Cited by 63
Connections between Size Functions and Critical Points
Frosini, P. (1996) · Mathematical Methods in the Applied Sciences · doi:10.1002/(sici)1099-1476(19960510)19:7<555::aid-mma787>3.0.co;2-x · Cited by 35 · cited 1×
“A negative saddle merged two level set components when coming from below so now (coming from above) we split them, cre-4 See also Frosini [47] who proves that it is sufficient to only analyze the Morse graph for the construction of the size function. ating a new component.”
BackgroundSurface matching using consistent pants decomposition
Li, X. S., Gu, X. D., & Qin, H. (2008) · ACM Symposium on Solid and Physical Modeling (SPM) · doi:10.1145/1364901.1364920 · Cited by 19 · cited 1×
“A mesh segmentation that can be used to construct a mapping between two shapes is given in [10].”
MethodA novel approach to express emotions through a flock of virtual beings
Ibáñez, J., Delgado-Mata, C., & Gómez-Caballero, F. (2007) · International Conference on Cyberworlds · doi:10.1109/cw.2007.39 · Cited by 16
Cited by
FastSurfer - A fast and accurate deep learning based neuroimaging pipeline
Henschel, L., Conjeti, S., Estrada, S., Diers, K., Fischl, B., & Reuter, M. (2020) · NeuroImage · doi:10.1016/j.neuroimage.2020.117012 · Cited by 660
Self-citationOne Point Isometric Matching with the Heat Kernel
Ovsjanikov, M., Mérigot, Q., Mémoli, F., & Guibas, L. (2010) · Computer Graphics Forum · doi:10.1111/j.1467-8659.2010.01764.x · Cited by 301
“Spectral invariants such as the eigenfunctions of the Laplace-Beltrami operator have been used for near-isometric shape matching by Mateus et al. [MHK + 08] and Jain et al. [JZvK07] as well as for segmentation [dGGV08,Reu10] and intrinsic symmetry detection [OSG08] among many others.”
Metadata
- Authors
- Reuter, M.
- Venue
- International Journal of Computer Vision
- Published
- 2009-08-14
- Volume
- 89
- Issue
- 2-3
- Pages
- 287-308
- ISSN
- 0920-5691 (ISSN-L)
- 1573-1405
- OpenAlex
- W2030797443
- Cited by
- 161
- References
- 65
- FWCI
- 13.52
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.