More Web Proxy on the site http://driver.im/

research-article

Shape analysis using the auto diffusion function

Authors:

J. A. Bærentzen,

R. LarsenAuthors Info & Claims

SGP '09: Proceedings of the Symposium on Geometry Processing

Pages 1405 - 1413

Published: 15 July 2009 Publication History

Abstract

Scalar functions defined on manifold triangle meshes is a starting point for many geometry processing algorithms such as mesh parametrization, skeletonization, and segmentation. In this paper, we propose the Auto Diffusion Function (ADF) which is a linear combination of the eigenfunctions of the Laplace-Beltrami operator in a way that has a simple physical interpretation. The ADF of a given 3D object has a number of further desirable properties: Its extrema are generally at the tips of features of a given object, its gradients and level sets follow or encircle features, respectively, it is controlled by a single parameter which can be interpreted as feature scale, and, finally, the ADF is invariant to rigid and isometric deformations.

We describe the ADF and its properties in detail and compare it to other choices of scalar functions on manifolds. As an example of an application, we present a pose invariant, hierarchical skeletonization and segmentation algorithm which makes direct use of the ADF.

References

[1]

{ABS03} Attene M., Biasotti S., Spagnuolo M.: Shape understanding by contour-driven retiling. The Visual Computer 19, 2--3 (2003), 127--138.

[2]

{AHLD07} Aujay G., Hétroy F., Lazarus F., Depraz C.: Harmonic skeleton for realistic character animation. In Symposium on Computer Animation, SCA 07, August, 2007 (San Diego, California, Etats-Unis, 2007), Metaxas D., Popović J., (Eds.), ACM-Siggraph/Eurographics, pp. 151--160.

Digital Library

[3]

{Ale03} Alexa M.: Differential coordinates for local mesh morphing and deformation. The Visual Computer 19, 2--3 (2003), 105--114.

[4]

{ATC*08} Au O. K.-C., Tai C.-L., Chu H.-K., Cohen-Or D., Lee T.-Y.: Skeleton extraction by mesh contraction. In SIGGRAPH '08: ACM SIGGRAPH 2008 papers (New York, NY, USA, 2008), ACM, pp. 1--10.

Digital Library

[5]

{Ber03} Berger M.: A panoramic view of Riemannian geometry. Springer, 2003.

[6]

{BFS00} Biasotti S., Falcidieno B., Spagnuolo M.: Extended reeb graphs for surface understanding and description. In DGCI '00: Proceedings of the 9th International Conference on Discrete Geometry for Computer Imagery (London, UK, 2000), Springer-Verlag, pp. 185--197.

Digital Library

[7]

{BN02} Belkin M., Niyogi P.: Laplacian eigenmaps and spectral techniques for embedding and clustering. In Advances in Neural Information Processing Systems 14 (2002), MIT Press, pp. 585--591.

[8]

{CMEH*03} Cole-McLaughlin K., Edelsbrunner H., Harer J., Natarajan V., Pascucci V.: Loops in reeb graphs of 2-manifolds. In SCG '03: Proceedings of the nineteenth annual symposium on Computational geometry (New York, NY, USA, 2003), ACM, pp. 344--350.

Digital Library

[9]

{CRD84} Chavel I., Randol B., Dodziuk J.: Eigenvalues in Riemannian geometry. Acad. Press, 1984.

[10]

{DBG*06} Dong S., Bremer P.-T., Garland M., Pascucci V., Hart J. C.: Spectral surface quadrangulation. ACM Trans. Graph. 25, 3 (2006), 1057--1066.

Digital Library

[11]

{dGGV08} de Goes F., Goldenstein S., Velho L.: A hierarchical segmentation of articulated bodies. Comput. Graph. Forum 27, 5 (2008), 1349--1356.

[12]

{DHLM05} Desbrun M., Hirani A. N., Leok M., Marsden J. E.: Discrete exterior calculus. http://arxiv.org/abs/math?papernum=0508341, Aug 2005.

[13]

{DKG05} Dong S., Kircher S., Garland M.: Harmonic functions for quadrilateral remeshing of arbitrary manifolds. Comput. Aided Geom. Des. 22, 5 (2005), 392--423.

Digital Library

[14]

{HWAG09} Huang Q., Wicke M., Adams B., Guibas L.: Shape decomposition using modal analysis. Computer Graphics Forum 28, 2 (2009). to appear.

[15]

{JWYG04} Jin M., Wang Y., Yau S.-T., Gu X.: Optimal global conformal surface parameterization. In VIS '04: Proceedings of the conference on Visualization '04 (Washington, DC, USA, 2004), IEEE Computer Society, pp. 267--274.

Digital Library

[16]

{KLT05} Katz S., Leifman G., Tal A.: Mesh segmentation using feature point and core extraction. The Visual Computer 21, 8--10 (2005), 649--658.

[17]

{KT03} Katz S., Tal A.: Hierarchical mesh decomposition using fuzzy clustering and cuts. ACM Transactions on Graphics 22, 3 (July 2003), 954--961.

Digital Library

[18]

{Lev06} Levy B.: Laplace-beltrami eigenfunctions: Towards an algorithm that understands geometry. In IEEE International Conference on Shape Modeling and Applications, invited talk (2006).

Digital Library

[19]

{LZ07} Liu R., Zhang H.: Mesh segmentation via spectral embedding and contour analysis. Computer Graphics Forum (Special Issue of Eurographics 2007) 26, 3 (2007), 385--394.

[20]

{MHK*08} Mateus D., Horaud R. P., Knossow D., Cuzzolin F., Boyer E.: Articulated shape matching using laplacian eigenfunctions and unsupervised point registration. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (2008).

[21]

{MTAD08} Mullen P., Tong Y., Alliez P., Desbrun M.: Spectral conformal parameterization. Computer Graphics Forum 27, 5 (July 2008), 1487--1494.

[22]

{NGH04} Ni X., Garland M., Hart J. C.: Fair morse functions for extracting the topological structure of a surface mesh. In SIGGRAPH '04: ACM SIGGRAPH 2004 Papers (New York, NY, USA, 2004), ACM, pp. 613--622.

Digital Library

[23]

{NISA06} Nealen A., Igarashi T., Sorkine O., Alexa M.: Laplacian mesh optimization. In GRAPHITE '06: Proceedings of the 4th international conference on Computer graphics and interactive techniques in Australasia and Southeast Asia (New York, NY, USA, 2006), ACM, pp. 381--389.

Digital Library

[24]

{OSG08} Ovsjanikov M., Sun J., Guibas L.: Global intrinsic symmetries of shapes. Computer Graphics Forum 27, 5 (July 2008), 1341--1348.

Digital Library

[25]

{PP93} Pinkall U., Polthier K.: Computing discrete minimal surfaces and their conjugates. Experimental Mathematics 2 (1993), 15--36.

[26]

{PSF08} Patane G., Spagnuolo M., Falcidieno B.: Reeb graph computation based on a minimal contouring. 2008 IEEE International Conference on Shape Modeling and Applications (2008), 73--82.

[27]

{RBG*09} Reuter M., Biasotti S., Giorgi D., Patane G., Spagnuolo M.: Discrete laplace-beltrami operators for shape analysis and segmentation.

[28]

{Reu06} Reuter M.: Laplace Spectra for Shape Recognition. Books on Demand GmbH, 2006.

[29]

{Ros97} Rosenberg S.: The Laplacian on a Riemannian Manifold. No. 31 in London Mathematical Society Student Texts. Cambridge University Press, 1997.

[30]

{Rus07} Rustamov R. M.: Laplace-beltrami eigenfunctions for deformation invariant shape representation. In SGP '07: Proceedings of the fifth Eurographics symposium on Geometry processing (Aire-la-Ville, Switzerland, Switzerland, 2007), Eurographics Association, pp. 225--233.

Digital Library

[31]

{RWP05} Reuter M., Wolter F.-E., Peinecke N.: Laplace-spectra as fingerprints for shape matching. In SPM '05: Proceedings of the 2005 ACM symposium on Solid and physical modeling (New York, NY, USA, 2005), ACM, pp. 101--106.

Digital Library

[32]

{SCOL*04} Sorkine O., Cohen-Or D., Lipman Y., Alexa M., Rössl C., Seidel H.-P.: Laplacian surface editing. In SGP '04: Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing (New York, NY, USA, 2004), ACM, pp. 175--184.

Digital Library

[33]

{SF01} Steiner D., Fischer A.: Topology recognition of 3d closed freeform objects based on topological graphs. In PG '01: Proceedings of the 9th Pacific Conference on Computer Graphics and Applications (Washington, DC, USA, 2001), IEEE Computer Society, p. 82.

Digital Library

[34]

{SLK*08} Shi Y., Lai R., Krishna S., Sicotte N., Dinov I., Toga A.: Anisotropic laplace-beltrami eigenmaps: Bridging reeb graphs and skeletons. pp. 1--7.

[35]

{Tie08} Tierny J.: Reeb graph based 3D shape modeling and applications. PhD thesis, TELECOM Lille 1, Universite des Sciences et Technologies de Lille, 2008.

[36]

{TVD07} Tierny J., Vandeborre J.-P., Daoudi M.: Topology driven 3D mesh hierarchical segmentation. In IEEE International Conference on Shape Modeling and Applications (SMI 2007) (Lyon, France, 2007), pp. 215--220.

Digital Library

[37]

{XZCOX09} Xu K., Zhang H., Cohen-Or D., Xiong Y.: Dynamic harmonic fields for surface processing. Computers and Graphics (Special Issue of Shape Modeling International) 33 (2009), 391--398.

Digital Library

[38]

{ZvKD07} Zhang H., van Kaick O., Dyer R.: Spectral methods for mesh processing and analysis. In Proc. of Eurographics State-of-the-art Report (2007), pp. 1--22.

Cited By

Nasikun AHildebrandt K(2022)The Hierarchical Subspace Iteration Method for Laplace–Beltrami EigenproblemsACM Transactions on Graphics10.1145/349520841:2(1-14)Online publication date: 4-Jan-2022
https://dl.acm.org/doi/10.1145/3495208
Melzi SOvsjanikov MRoffo GCristani MCastellani U(2018)Discrete Time Evolution Process Descriptor for Shape Analysis and MatchingACM Transactions on Graphics10.1145/314445437:1(1-18)Online publication date: 29-Jan-2018
https://dl.acm.org/doi/10.1145/3144454
Medimegh NBelaid SAtri MWerghi N(2018)3D mesh watermarking using salient pointsMultimedia Tools and Applications10.1007/s11042-018-6252-677:24(32287-32309)Online publication date: 1-Dec-2018
https://dl.acm.org/doi/10.1007/s11042-018-6252-6
Show More Cited By

Index Terms

Shape analysis using the auto diffusion function
1. Computing methodologies
  1. Computer graphics
    1. Shape modeling
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Shape analysis in shape space
2D-Shape Analysis Using Conformal Mapping

The study of 2D shapes and their similarities is a central problem in the field of vision. It arises in particular from the task of classifying and recognizing objects from their observed silhouette. Defining natural distances between 2D shapes creates ...
Shape preserving surface reconstruction using locally anisotropic radial basis function interpolants

In this paper we deal with the problem of reconstructing surfaces from unorganized sets of points, while capturing the significant geometry details of the modelled surface, such as edges, flat regions, and corners. This is obtained by exploiting the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

SGP '09: Proceedings of the Symposium on Geometry Processing

July 2009

278 pages

Conference Chair:
Konrad Polthier
Freie Universität Berlin
,
Program Chairs:
Marc Alexa
Technische Universität Berlin
,
Michael Kazhdan
Johns Hopkins University

Publisher

Eurographics Association

Goslar, Germany

Publication History

Published: 15 July 2009

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

46
Total Citations
View Citations
19
Total Downloads

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

Reflects downloads up to 23 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Nasikun AHildebrandt K(2022)The Hierarchical Subspace Iteration Method for Laplace–Beltrami EigenproblemsACM Transactions on Graphics10.1145/349520841:2(1-14)Online publication date: 4-Jan-2022
https://dl.acm.org/doi/10.1145/3495208
Melzi SOvsjanikov MRoffo GCristani MCastellani U(2018)Discrete Time Evolution Process Descriptor for Shape Analysis and MatchingACM Transactions on Graphics10.1145/314445437:1(1-18)Online publication date: 29-Jan-2018
https://dl.acm.org/doi/10.1145/3144454
Medimegh NBelaid SAtri MWerghi N(2018)3D mesh watermarking using salient pointsMultimedia Tools and Applications10.1007/s11042-018-6252-677:24(32287-32309)Online publication date: 1-Dec-2018
https://dl.acm.org/doi/10.1007/s11042-018-6252-6
Herholz PDavis TAlexa M(2017)Localized solutions of sparse linear systems for geometry processingACM Transactions on Graphics10.1145/3130800.313084936:6(1-8)Online publication date: 20-Nov-2017
https://dl.acm.org/doi/10.1145/3130800.3130849
Wang MWang LFang YLiu QLienhart RWang HChen SBoll SChen PFriedland GLi JYan S(2017)3DensiNetProceedings of the 25th ACM international conference on Multimedia10.1145/3123266.3123340(961-969)Online publication date: 23-Oct-2017
https://dl.acm.org/doi/10.1145/3123266.3123340
Aumentado-Armstrong TSiddiqi K(2017)Stochastic Heat Kernel Estimation on Sampled ManifoldsComputer Graphics Forum10.1111/cgf.1325136:5(131-138)Online publication date: 1-Aug-2017
https://dl.acm.org/doi/10.1111/cgf.13251
Brandt CScandolo LEisemann EHildebrandt K(2017)Spectral Processing of Tangential Vector FieldsComputer Graphics Forum10.1111/cgf.1294236:6(338-353)Online publication date: 1-Sep-2017
https://dl.acm.org/doi/10.1111/cgf.12942
Patané G(2017)Accurate and Efficient Computation of Laplacian Spectral Distances and KernelsComputer Graphics Forum10.1111/cgf.1279436:1(184-196)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1111/cgf.12794
Masoumi MBen Hamza A(2017)Spectral shape classificationJournal of Visual Communication and Image Representation10.1016/j.jvcir.2017.01.00143:C(198-211)Online publication date: 1-Feb-2017
https://dl.acm.org/doi/10.1016/j.jvcir.2017.01.001
Masoumi MHamza A(2017)Shape classification using spectral graph waveletsApplied Intelligence10.1007/s10489-017-0955-747:4(1256-1269)Online publication date: 1-Dec-2017
https://dl.acm.org/doi/10.1007/s10489-017-0955-7
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents