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.
Similar content being viewed by others
References
ARPACK (2009) Arnoldi package. http://www.caam.rice.edu/software/ARPACK/.
Agarwal, P. K., Edelsbrunner, H., Harer, J., & Wang, Y. (2006). Extreme elevation on a 2-manifold. Discrete Computational Geometry, 36(4), 553–572.
Attene, M., Falcidieno, B., & Spagnuolo, M. (2006). Hierarchical mesh segmentation based on fitting primitives. The Visual Computer, 22(3), 181–193.
Attene, M., Katz, S., Mortara, M., Patanè, G., Spagnuolo, M., & Tal, A. (2006). Mesh segmentation—a comparative study. In International conference on shape modeling and applications (SMI 06) (pp. 14–25). Matsushima, Japan.
Belkin, M., & Niyogi, P. (2003). Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computations, 15(6), 1373–1396.
Biasotti, S., De Floriani, L., Falcidieno, B., Frosini, P., Giorgi, D., Landi, C., Papaleo, L., & Spagnuolo, M. (2008). Describing shapes by geometrical-topological properties of real functions. ACM Computing Surveys, 40(4), 1–87 ISSN 0360-0300.
Bremer, P. T., Edelsbrunner, H., Hamann, B., & Pascucci, V. (2004). A topological hierarchy for functions on triangulated surfaces. IEEE Transactions on Visualization and Computer Graphics, 10(4), 385–396.
Bronstein, A. M., Bronstein, M. M., & Kimmel, R. (2006). Efficient computation of isometry-invariant distances between surfaces. SIAM Journal on Scientific Computing, 28(5), 1812–1836.
Chavel, I. (1984). Eigenvalues in Riemannian geometry. San Diego: Academic Press.
Cohen-Steiner, D., Edelsbrunner, H., & Harer, J. (2005). Stability of persistence diagrams. In SCG ’05: proceedings of the twenty-first annual symposium on computational geometry (pp. 263–271). New York: ACM. ISBN 1-58113-991-8.
Cohen-Steiner, D., Edelsbrunner, H., & Harer, J. (2008). Extending persistence using Poincaré and Lefschetz duality. Foundations of Computational Mathematics, 9(1), 79–103.
Coifman, R. R., Lafon, S., Lee, A., Maggioni, M., Nadler, B., Warner, F. J., & Zucker, S. W. (2005). Geometric diffusions as a tool for harmonic analysis and structure definition of data. Part I: Diffusion maps. In Proc. of nat. acad. sci. (Vol. 102, pp. 7426–7431).
Courant, R., & Hilbert, D. (1953). Methods of Mathematical Physics (Vol. I). New York: Interscience.
de Goes, F., Goldenstein, S., & Velho, L. (2008). A hierarchical segmentation of articulated bodies. In Eurographics symposium on geometry processing (Vol. 27(5), pp. 1349–1356).
Demmel, J. W., Eisenstat, S. C., Gilbert, J. R., Li, X. S., & Liu, J. W. H. (1999). A supernodal approach to sparse partial pivoting. SIAM Journal Matrix Analysis and Applications, 20(3), 720–755.
Desbrun, M., Meyer, M., Schröder, P., & Barr, A. (1999). Implicit fairing of irregular meshes using diffusion and curvature flow. In Proc. ACM SIGGRAPH ’99 (pp. 317–324).
Dong, S., Bremer, P. T., Garland, M., Pascucci, V., & Hart, J. C. (2006). Spectral surface quadrangulation. In ACM SIGGRAPH 2006 (pp. 1057–1066).
Dziuk, G. (1988). Finite elements for the Beltrami operator on arbitrary surfaces. In S. Hildebrandt & R. Leis (Eds.), Lecture notes in mathematics : Vol. 1357. Partial differential equations and calculus of variations (pp. 142–155). Berlin: Springer.
Edelsbrunner, H., & Harer, J. (2008). Persistent homology—a survey. In J. E. Goodman, J. Pach, & R. Pollack (Eds.), Contemporary mathematics : Vol. 453. Surveys on discrete and computational geometry: twenty years later (pp. 257–281). Providence: AMS.
Edelsbrunner, H., Harer, J., & Zomorodian, A. (2003). Hierarchical Morse-Smale complexes for piecewise linear 2-manifolds. Discrete and Computational Geometry, 30(1), 87–107.
Edelsbrunner, H., Letscher, D., & Zomorodian, A. (2002). Topological persistence and simplification. Discrete and Computational Geometry, 28(4), 511–533.
Elad, A., & Kimmel, R. (2003). On bending invariant signatures for surfaces. IEEE Transactions on Pattern Analysis and Machine Intelligence, 25(10), 1285–1295.
Frosini, P. (1990). A distance for similarity classes of submanifolds of a euclidean space. Bulletin of the Australian Mathematical Society, 42, 407–416.
Frosini, P. (1996). Connections between size functions and critical points. Mathematical Methods in the Applied Sciences, 19, 555–569.
Frosini, P., & Landi, C. (1997). Size functions and morphological transformations. Acta Applicandae Mathematicae, 49(1), 85–104.
Frosini, P., & Pittore, M. (1999). New methods for reducing size graphs. International Journal of Computer Mathematics, 70(3), 505–517.
Gomes, F. M., & Sorensen, D. C. (1997) Arpack++: A C++ implementation of ARPACK eigenvalue package. http://citeseer.ist.psu.edu/67128.html.
Gromov, M. (1999). Metric structures for Riemannian and non-Riemannian spaces. Progress in mathematics (Vol. 152). Boston: Birkhäuser.
Hoffmann, D., & Singh, M. (1997). Salience of visual parts. Cognition, 63, 29–78.
Jain, V., & Zhang, H. (2006). Robust 3D shape correspondence in the spectral domain. In Proc. shape modeling international 2006 (pp. 118–129).
Jain, V., Zhang, H., & van Kaick, O. (2007). Non-rigid spectral correspondence of triangle meshes. International Journal on Shape Modeling, 13(1), 101–124.
Katz, S., Leifman, G., & Tal, A. (2005). Mesh segmentation using feature point and core extraction. The Visual Computer, 21(8), 649–658.
Katz, S., & Tal, A. (2003). Hierarchical mesh decomposition using fuzzy clustering and cuts. ACM Transactions on Graphics, 22(3), 954–961.
Lai, Y. K., Hu, S. M., Martin, R. R., & Rosin, P. L. (2008). Fast mesh segmentation using random walks. In SPM 08: proceedings of the 2008 ACM symposium on solid and physical modeling (pp. 183–191). New York: ACM. ISBN 978-1-60558-106-2.
Lévy, B. (2006). Laplace-Beltrami eigenfunctions: towards an algorithm that understands geometry. In Proc. of the IEEE shape modeling and applications (p. 13).
Li, X., Gu, X., & Qin, H. (2008). Surface matching using consistent pants decomposition. In SPM ’08: proceedings of the 2008 ACM symposium on solid and physical modeling (pp. 125–136). New York: ACM. ISBN 978-1-60558-106-2.
Liu, R., & Zhang, H. (2004). Segmentation of 3D meshes through spectral clustering. In Proc. of computer graphics and applications (pp. 298–305). ISBN 0-7695-2234-3.
Liu, R., & Zhang, H. (2007). Mesh segmentation via spectral embedding and contour analysis. In EUROGRAPHICS 2007 (Vol. 26, pp. 385–394).
Mateus, D., Horaud, R. P., Knossow, D., Cuzzolin, F., & Boyer, E. (2008). Articulated shape matching using Laplacian eigenfunctions and unsupervised point registration. In IEEE conference on computer vision and pattern recognition (pp. 1–8).
Mémoli, F., & Sapiro, G. (2005). A theoretical and computational framework for isometry invariant recognition of point cloud data. Foundations of Computational Mathematics, 5(3), 313–347.
Milnor, J. (1963). Morse theory. Annals of mathematics studies (Vol. 51). Princeton: Princeton University Press.
Niethammer, M., Reuter, M., Wolter, F. E., Bouix, S., Peinecke, N., Koo, M. S., & Shenton, M. (2007). Global medical shape analysis using the Laplace-Beltrami spectrum. In Lecture notes in computer science : Vol. 4791. Conference on medical image computing and computer assisted intervention, Part I (pp. 850–857). Brisbane: Springer. ISBN 978-3-540-75756-6.
Ovsjanikov, M., Sun, J., & Guibas, L. (2008). Global intrinsic symmetries of shapes. In Eurographics symposium on geometry processing (SGP).
Parlett, B. N. (1980). The symmetric eigenvalue problem. Englewood Cliffs: Prentice Hall.
Peinecke, N., Wolter, F. E., & Reuter, M. (2007). Laplace spectra as fingerprints for image recognition. Computer-Aided Design, 39(6), 460–476.
Qiu, A., Bitouk, D., & Miller, M. I. (2006). Smooth functional and structural maps on the neocortex via orthonormal bases of the Laplace-Beltrami operator. IEEE Transactions on Medical Imaging, 25(10), 1296–1306.
Reeb, G. (1946). Sur les points singuliers d’une forme de Pfaff completement intégrable ou d’une fonction numérique. Comptes Rendus de l’Académie des Sciences, Paris, 222, 847–849.
Reuter, M. (2006). Laplace spectra for shape recognition. Norderstedt: Books on Demand. ISBN 3-8334-5071-1.
Reuter, M., Biasotti, S., Giorgi, D., Patanè, G., & Spagnuolo, M. (2009). Discrete Laplace-Beltrami operators for shape analysis and segmentation. Computers & Graphics. doi:10.1016/j.cag.2009.03.005.
Reuter, M., Niethammer, M., Wolter, F. E., Bouix, S., & Shenton, M. (2007). Global medical shape analysis using the volumetric Laplace spectrum. In Proceedings of the 2007 international conference on cyberworlds (NASAGEM) (pp. 417–426). Los Alamitos: IEEE Comput. Soc.
Reuter, M., Wolter, F. E., & Peinecke, N. (2005). Laplace-spectra as fingerprints for shape matching. In SPM ’05: proceedings of the 2005 ACM symposium on solid and physical modeling (pp. 101–106). New York: ACM.
Reuter, M., Wolter, F. E., & Peinecke, N. (2006). Laplace-Beltrami spectra as shape-DNA of surfaces and solids. Computer-Aided Design, 38(4), 342–366.
Reuter, M., Wolter, F. E., Shenton, M., & Niethammer, M. (2009). Laplace-Beltrami eigenvalues and topological features of eigenfunctions for statistical shape analysis. Computer-Aided Design. doi:10.1016/j.cad.2009.02.007.
Rustamov, R. M. (2007). Laplace-Beltrami eigenfunctions for deformation invariant shape representation. In SGP ’07: proceedings of the fifth Eurographics symposium on geometry processing (pp. 225–233). Aire-la-Ville: Eurographics Association.
Shamir, A. (2008). A survey on mesh segmentation techniques. Computer Graphics Forum, 27(6), 1539–1556.
Shi, Y., Lai, R., Krishna, S., Dinov, I., & Toga, A. W. (2008). Anisotropic Laplace-Beltrami eigenmaps: Bridging Reeb graphs and skeletons. In Computer vision and pattern recognition workshops, 2008. CVPR workshops (pp. 1–7). Anchorage: IEEE Comput. Soc.
Smale, S. (1961). On gradient dynamical systems. Annals of Mathematics, 74, 199–206.
Strang, G., & Fix, G. J. (1973). An analysis of the finite element method. New York: Prentice Hall.
Sumner, R. W., & Popović, J. (2004). Deformation transfer for triangle meshes. In SIGGRAPH ’04: ACM SIGGRAPH 2004 papers (pp. 399–405). New York: ACM.
Vallet, B. (2008). Function bases on manifolds. Ph.D. thesis, Institut National Polytechnique de Lorraine.
Vallet, B., & Lévy, B. (2008). Spectral geometry processing with manifold harmonics. In Computer graphics forum (proc. Eurographics 2007) (Vol. 2(27)).
Xu, G. (2004). Discrete Laplace-Beltrami operators and their convergence. Computer Aided Geometric Design, 21, 767–784.
Zhang, H., van Kaick, O., & Dyer, R. Spectral mesh processing. In Computer graphics forum (2009).
Zienkiewicz, O., & Taylor, R. (2000). The finite element method—volume 1: the basis. Oxford: Butterworth-Heinemann.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Reuter, M. Hierarchical Shape Segmentation and Registration via Topological Features of Laplace-Beltrami Eigenfunctions. Int J Comput Vis 89, 287–308 (2010). https://doi.org/10.1007/s11263-009-0278-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11263-009-0278-1