Spectral shape analysis

From Wikipedia, the free encyclopedia

Spectral shape analysis relies on the spectrum (eigenvalues and/or eigenfunctions) of the Laplace–Beltrami operator to compare and analyze geometric shapes. Since the spectrum of the Laplace–Beltrami operator is invariant under isometries, it is well suited for the analysis or retrieval of non-rigid shapes, i.e. bendable objects such as humans, animals, plants, etc.

Laplace

The Laplace–Beltrami operator is involved in many important differential equations, such as the heat equation and the wave equation. It can be defined on a Riemannian manifold as the divergence of the gradient of a real-valued function f:

$\Delta f:=\operatorname {div}\;\operatorname {grad}f.$

Its spectral components can be computed by solving the Helmholtz equation (or Laplacian eigenvalue problem):

$\Delta \phi _{i}+\lambda _{i}\phi _{i}=0.\,$

The solutions are the eigenfunctions $\phi _{i}$ (modes) and corresponding eigenvalues $\lambda _{i}$ , representing a diverging sequence of positive real numbers. The first eigenvalue is zero for closed domains or when using the Neumann boundary condition. 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 spherical harmonics.

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.

Discretizations

Geometric shapes are often represented as 2D curved surfaces, 2D surface meshes (usually triangle meshes) or 3D solid objects (e.g. using voxels or tetrahedra 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.

Several discretizations of the Laplace operator exist (see Discrete Laplace operator) for the different types of geometry representations. Many of these operators do not approximate well the underlying continuous operator.

Spectral shape descriptors

ShapeDNA

The ShapeDNA is one of the first spectral shape descriptors. It is the normalized beginning sequence of the eigenvalues of the Laplace–Beltrami operator.^[1]^[2] 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.^[3] However, the eigenvalues are a global descriptor, therefore the shapeDNA cannot be used for local or partial shape analysis.

Global point signature (GPS)

The global point signature^[4] at a point $x$ is a vector of scaled eigenfunctions of the Laplace–Beltrami operator computed at $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.

Heat kernel signature (HKS)

The heat kernel signature^[5] makes use of the eigen-decomposition of the heat kernel:

$h_{t}(x,y)=\sum _{{i=0}}^{\infty }\exp(-\lambda _{i}t)\phi _{i}(x)\phi _{i}(y).$

For each point on the surface the diagonal of the heat kernel $h_{t}(x,x)$ is sampled at specific time values $t_{j}$ and yields a local signature that can also be used for partial matching or symmetry detection.

References

↑ Reuter, M. and Wolter, F.-E. and Peinecke, N. (2005). "Laplace-Spectra as Fingerprints for Shape Matching". Proceedings of the 2005 ACM Symposium on Solid and Physical Modeling. pp. 101–106.
↑ Reuter, M. and Wolter, F.-E. and 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.
↑ 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.
↑ Rustamov, R.M. (2007). "Laplace–Beltrami eigenfunctions for deformation invariant shape representation". Proceedings of the fifth Eurographics symposium on Geometry processing. pp. 225–233. Unknown parameter |organization= ignored (help)
↑ Sun, J. and Ovsjanikov, M. and Guibas, L. (2009). "A Concise and Provably Informative Multi-Scale Signature-Based on Heat Diffusion". Computer Graphics Forum 28 (5). pp. 1383–1392.

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.