Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Spectral shape analysis
open-in-new
<h2 id="laplace">Laplace</h2> <p>The <a href="/facts/Laplace%E2%80%93Beltrami_operator/AJmyUpWz">Laplace–Beltrami operator</a> is involved in many important differential equations, such as the <a href="/facts/Heat_equation/2JPPr5GG">heat equation</a> and the <a href="/facts/Wave_equation/J2ksD2Az">wave equation</a>. It can be defined on a <a href="/facts/Riemannian_manifold/5KYnmEgF">Riemannian manifold</a> as the <a href="/facts/Divergence/zpwwkFoU">divergence</a> of the <a href="/facts/Gradient/TsR7uukj">gradient</a> of a real-valued function <i>f</i>: </p> Δ f := div grad f . {\displaystyle \Delta f:=\operatorname {div} \operatorname {grad} f.} <p>Its spectral components can be computed by solving the <a href="/facts/Helmholtz_equation/SWfaXrTB">Helmholtz equation</a> (or Laplacian eigenvalue problem): </p> Δ φ i + λ i φ i = 0. {\displaystyle \Delta \varphi _{i}+\lambda _{i}\varphi _{i}=0.} <p>The solutions are the eigenfunctions φ i {\displaystyle \varphi _{i}} (modes) and corresponding eigenvalues λ i {\displaystyle \lambda _{i}} , representing a diverging sequence of positive real numbers. The first eigenvalue is zero for closed domains or when using the <a href="/facts/Neumann_boundary_condition/0e0YBW4G">Neumann boundary condition</a>. For some shapes, the spectrum can be computed analytically (e.g. rectangle, flat torus, cylinder, disk or sphere). For the sphere, for example, the eigenfunctions are the <a href="/facts/Spherical_harmonics/bn98Gv2L">spherical harmonics</a>. </p><p>The most important properties of the eigenvalues and eigenfunctions are that they are isometry invariants. In other words, if the shape is not stretched (e.g. a sheet of paper bent into the third dimension), the spectral values will not change. Bendable objects, like animals, plants and humans, can move into different body postures with only minimal stretching at the joints. The resulting shapes are called near-isometric and can be compared using spectral shape analysis. </p> <h2 id="discretizations">Discretizations</h2> <p>Geometric shapes are often represented as 2D curved surfaces, 2D <a href="/facts/Polygon_mesh/6WLD80ER">surface meshes</a> (usually <a href="/facts/Triangle_mesh/EphfTInp">triangle meshes</a>) or 3D solid objects (e.g. using <a href="/facts/Voxel/xo077lPE">voxels</a> or <a href="/facts/Tetrahedron/7mkSrl6j">tetrahedra</a> meshes). The Helmholtz equation can be solved for all these cases. If a boundary exists, e.g. a square, or the volume of any 3D geometric shape, boundary conditions need to be specified. </p><p>Several discretizations of the Laplace operator exist (see <a href="/facts/Discrete_Laplace_operator/w3fdFNC4">Discrete Laplace operator</a>) for the different types of geometry representations. Many of these operators do not approximate well the underlying continuous operator. </p> <h2 id="spectral-shape-descriptors">Spectral shape descriptors</h2> <h3>ShapeDNA and its variants</h3> <p>The ShapeDNA is one of the first spectral shape descriptors. It is the normalized beginning sequence of the eigenvalues of the Laplace–Beltrami operator.<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a><a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> Its main advantages are the simple representation (a vector of numbers) and comparison, scale invariance, and in spite of its simplicity a very good performance for shape retrieval of non-rigid shapes.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> Competitors of shapeDNA include singular values of Geodesic Distance Matrix (SD-GDM) <a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> and Reduced BiHarmonic Distance Matrix (R-BiHDM).<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> However, the eigenvalues are global descriptors, therefore the shapeDNA and other global spectral descriptors cannot be used for local or partial shape analysis. </p> <h3>Global point signature (GPS)</h3> <p>The global point signature<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> at a point x {\displaystyle x} is a vector of scaled eigenfunctions of the Laplace–Beltrami operator computed at x {\displaystyle x} (i.e. the spectral embedding of the shape). The GPS is a global feature in the sense that it cannot be used for partial shape matching. </p> <h3>Heat kernel signature (HKS)</h3> <p>The heat kernel signature<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> makes use of the eigen-decomposition of the <a href="/facts/Heat_kernel/EbLKLbJH">heat kernel</a>: </p> h t ( x , y ) = ∑ i = 0 ∞ exp ( − λ i t ) φ i ( x ) φ i ( y ) . {\displaystyle h_{t}(x,y)=\sum _{i=0}^{\infty }\exp(-\lambda _{i}t)\varphi _{i}(x)\varphi _{i}(y).} <p>For each point on the surface the diagonal of the heat kernel h t ( x , x ) {\displaystyle h_{t}(x,x)} is sampled at specific time values t j {\displaystyle t_{j}} and yields a local signature that can also be used for partial matching or symmetry detection. </p> <h3>Wave kernel signature (WKS)</h3> <p>The WKS<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> follows a similar idea to the HKS, replacing the heat equation with the Schrödinger wave equation. </p> <h3>Improved wave kernel signature (IWKS)</h3> <p>The IWKS<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a> improves the WKS for non-rigid shape retrieval by introducing a new scaling function to the eigenvalues and aggregating a new curvature term. </p> <h3>Spectral graph wavelet signature (SGWS)</h3> <p>SGWS is a local descriptor that is not only isometric invariant, but also compact, easy to compute and combines the advantages of both band-pass and low-pass filters. An important facet of SGWS is the ability to combine the advantages of WKS and HKS into a single signature, while allowing a multiresolution representation of shapes.<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a> </p> <h2 id="spectral-matching">Spectral Matching</h2> <p>The spectral decomposition of the graph Laplacian associated with complex shapes (see <a href="/facts/Discrete_Laplace_operator/w3fdFNC4">Discrete Laplace operator</a>) provides eigenfunctions (modes) which are invariant to isometries. Each vertex on the shape could be uniquely represented with a combinations of the eigenmodal values at each point, sometimes called spectral coordinates: </p> s ( x ) = ( φ 1 ( x ) , φ 2 ( x ) , … , φ N ( x ) ) for vertex x . {\displaystyle s(x)=(\varphi _{1}(x),\varphi _{2}(x),\ldots ,\varphi _{N}(x)){\text{ for vertex }}x.} <p>Spectral matching consists of establishing the point correspondences by pairing vertices on different shapes that have the most similar spectral coordinates. Early work <a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a><a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a><a class="footnote-ref" id="fnref:13" href="#fn:13"><sup>13</sup></a> focused on sparse correspondences for stereoscopy. Computational efficiency now enables dense correspondences on full meshes, for instance between cortical surfaces.<a class="footnote-ref" id="fnref:14" href="#fn:14"><sup>14</sup></a> Spectral matching could also be used for complex non-rigid <a href="/facts/Image_registration/y2KUwdRL">image registration</a>, which is notably difficult when images have very large deformations.<a class="footnote-ref" id="fnref:15" href="#fn:15"><sup>15</sup></a> Such image registration methods based on spectral eigenmodal values indeed capture <i>global</i> shape characteristics, and contrast with conventional non-rigid image registration methods which are often based on local shape characteristics (e.g., image gradients). </p> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Reuter, M.; Wolter, F.-E.; Peinecke, N. (2005). "Laplace-Spectra as Fingerprints for Shape Matching". Proceedings of the 2005 ACM Symposium on Solid and Physical Modeling. pp. 101–106. doi:10.1145/1060244.1060256. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>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. doi:10.1016/j.cad.2005.10.011. S2CID 7566792. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Lian, Z.; et al. (2011). "SHREC'11 track: shape retrieval on non-rigid 3D watertight meshes". Proceedings of the Eurographics 2011 Workshop on 3D Object Retrieval (3DOR'11). pp. 79–88. doi:10.2312/3DOR/3DOR11/079-088. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Smeets, Dirk; Fabry, Thomas; Hermans, Jeroen; Vandermeulen, Dirk; Suetens, Paul (2009). "Isometric deformation modelling for object recognition". Computer Analysis of Images and Patterns. Lecture Notes in Computer Science. Vol. 5702. pp. 757–765. Bibcode:2009LNCS.5702..757S. doi:10.1007/978-3-642-03767-2_92. ISBN 978-3-642-03766-5. <a href="978-3-642-03766-5" target="_blank">978-3-642-03766-5</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Ye, J.; Yu, Y. (2015). "A fast modal space transform for robust nonrigid shape retrieval". The Visual Computer. 32 (5): 553–568. doi:10.1007/s00371-015-1071-5. hdl:10722/215522. S2CID 16707677. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Rustamov, R.M. (July 4, 2007). "Laplace–Beltrami eigenfunctions for deformation invariant shape representation". Proceedings of the fifth Eurographics symposium on Geometry processing. Eurographics Association. pp. 225–233. ISBN 978-3-905673-46-3. <a href="978-3-905673-46-3" target="_blank">978-3-905673-46-3</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Sun, J.; Ovsjanikov, M.; Guibas, L. (2009). "A Concise and Provably Informative Multi-Scale Signature-Based on Heat Diffusion". Computer Graphics Forum. Vol. 28. pp. 1383–92. CiteSeerX 10.1.1.157.2592. doi:10.1111/j.1467-8659.2009.01515.x. <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>Aubry, M.; Schlickewei, U.; Cremers, D. (2011). "The wave kernel signature: A quantum mechanical approach to shape analysis". Computer Vision Workshops (ICCV Workshops), 2011 IEEE International Conference on. pp. 1626–1633. doi:10.1109/ICCVW.2011.6130444. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>Limberger, F. A. & Wilson, R. C. (2015). "Feature Encoding of Spectral Signatures for 3D Non-Rigid Shape Retrieval". Proceedings of the British Machine Vision Conference (BMVC). pp. 56.1 – 56.13. doi:10.5244/C.29.56 (inactive 2024-11-18). ISBN 978-1-901725-53-7.{{cite conference}}: CS1 maint: DOI inactive as of November 2024 (link) <a href="978-1-901725-53-7" target="_blank">978-1-901725-53-7</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>Masoumi, Majid; Li, Chunyuan; Ben Hamza, A (2016). "A spectral graph wavelet approach for nonrigid 3D shape retrieval". Pattern Recognition Letters. 83: 339–48. Bibcode:2016PaReL..83..339M. doi:10.1016/j.patrec.2016.04.009. <a href="/wiki/Bibcode_(identifier)" target="_blank">/wiki/Bibcode_(identifier)</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>Umeyama, S (1988). "An eigendecomposition approach to weighted graph matching problems". IEEE Transactions on Pattern Analysis and Machine Intelligence. 10 (5): 695–703. doi:10.1109/34.6778. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> <li id="fn:12"><p>Scott, GL; Longuet-Higgins, HC (1991). "An algorithm for associating the features of two images". Proceedings of the Royal Society of London. Series B: Biological Sciences. 244 (1309): 21–26. Bibcode:1991RSPSB.244...21S. doi:10.1098/rspb.1991.0045. PMID 1677192. S2CID 13011932. <a href="/wiki/Bibcode_(identifier)" target="_blank">/wiki/Bibcode_(identifier)</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li> <li id="fn:13"><p>Shapiro, LS; Brady, JM (1992). "Feature-based correspondence: an eigenvector approach". Image and Vision Computing. 10 (5): 283–8. doi:10.1016/0262-8856(92)90043-3. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></p></li> <li id="fn:14"><p>Lombaert, H; Grady, L; Polimeni, JR; Cheriet, F (2013). "FOCUSR: Feature Oriented Correspondence using Spectral Regularization - A Method for Precise Surface Matching". IEEE Transactions on Pattern Analysis and Machine Intelligence. 35 (9): 2143–2160. doi:10.1109/tpami.2012.276. PMC 3707975. PMID 23868776. <a href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3707975" target="_blank">https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3707975</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></p></li> <li id="fn:15"><p>Lombaert, H; Grady, L; Pennec, X; Ayache, N; Cheriet, F (2014). "Spectral Log-Demons - Diffeomorphic Image Registration with Very Large Deformations". International Journal of Computer Vision. 107 (3): 254–271. CiteSeerX 10.1.1.649.9395. doi:10.1007/s11263-013-0681-5. S2CID 3347129. <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></p></li> </ol>