Heat kernel signature

Last updated January 17, 2024

A heat kernel signature (HKS) is a feature descriptor for use in deformable shape analysis and belongs to the group of spectral shape analysis methods. For each point in the shape, HKS defines its feature vector representing the point's local and global geometric properties. Applications include segmentation, classification, structure discovery, shape matching and shape retrieval.

Overview
Technical details
Practical considerations
Limitations
Non-repeating eigenvalues
Time parameter selection
Time complexity
Non-isometric transformations
Relation with other methods
Curvature
Wave kernel signature (WKS)
Global point signature (GPS)
Spectral graph wavelet signature (SGWS)
Extensions
Scale invariance
Volumetric HKS
Shape Search
References

HKS was introduced in 2009 by Jian Sun, Maks Ovsjanikov and Leonidas Guibas.^[1] It is based on heat kernel, which is a fundamental solution to the heat equation. HKS is one of the many recently introduced shape descriptors which are based on the Laplace–Beltrami operator associated with the shape.^[2]

Overview

Shape analysis is the field of automatic digital analysis of shapes, e.g., 3D objects. For many shape analysis tasks (such as shape matching/retrieval), feature vectors for certain key points are used instead of using the complete 3D model of the shape. An important requirement of such feature descriptors is for them to be invariant under certain transformations. For rigid transformations, commonly used feature descriptors include shape context, spin images, integral volume descriptors and multiscale local features, among others.^[2] HKS allows isometric transformations which generalizes rigid transformations.

HKS is based on the concept of heat diffusion over a surface. Given an initial heat distribution $u_{0}(x)$ over the surface, the heat kernel $h_{t}(x,y)$ relates the amount of heat transferred from $x$ to $y$ after time $t$ . The heat kernel is invariant under isometric transformations and stable under small perturbations to the isometry.^[1] In addition, the heat kernel fully characterizes shapes up to an isometry and represents increasingly global properties of the shape with increasing time.^[3] Since $h_{t}(x,y)$ is defined for a pair of points over a temporal domain, using heat kernels directly as features would lead to a high complexity. HKS instead restricts itself to just the temporal domain by considering only $h_{t}(x,x)$ . HKS inherits most of the properties of heat kernels under certain conditions.^[1]

Technical details

The heat diffusion equation over a compact Riemannian manifold $M$ (possibly with a boundary) is given by,

\left(\Delta -{\frac {\partial }{\partial t}}\right)u(x,t)=0

where $\Delta$ is the Laplace–Beltrami operator and $u(x,t)$ is the heat distribution at a point $x$ at time $t$ . The solution to this equation can be expressed as,^[1]

u(x,t)=\int h_{t}(x,y)u_{0}(y)dy.

The eigen decomposition of the heat kernel is expressed as,

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

where $\lambda _{i}$ and $\phi _{i}$ are the $i^{th}$ eigenvalue and eigenfunction of $\Delta$ . The heat kernel fully characterizes a surface up to an isometry: For any surjective map $T:M\rightarrow N$ between two Riemannian manifolds $M$ and $N$ , if $h_{t}(x,y)=h_{t}(T(x),T(y))$ then $T$ is an isometry, and vice versa.^[1] For a concise feature descriptor, HKS restricts the heat kernel only to the temporal domain,

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

HKS, similar to the heat kernel, characterizes surfaces under the condition that the eigenvalues of $\Delta$ for $M$ and $N$ are non-repeating. The terms $\exp(-\lambda _{i}t)$ can be intuited as a bank of low-pass filters, with $\lambda _{i}$ determining the cutoff frequencies.^[2]

Practical considerations

Since $h_{t}(x,x)$ is, in general, a non-parametric continuous function, HKS is in practice represented as a discrete sequence of $\{h_{t_{1}}(x,x),\ldots ,h_{t_{n}}(x,x)\}$ values sampled at times $t_{1},\ldots ,t_{n}$ .

In most applications, the underlying manifold for an object is not known. The HKS can be computed if a mesh representation of the manifold is available, by using a discrete approximation to $\Delta$ and using the discrete analogue of the heat equation. In the discrete case, the Laplace–Beltrami operator is a sparse matrix and can be written as,^[1]

L=A^{-1}W

where $A$ is a positive diagonal matrix with entries $A(i,i)$ corresponding to the area of the triangles in the mesh sharing the vertex $i$ , and $W$ is a symmetric semi-definite weighting matrix. $L$ can be decomposed into $L=\Phi \Lambda \Phi ^{T}A$ , where $\Lambda$ is a diagonal matrix of the eigenvalues of $L$ arranged in the ascending order, and $\Phi$ is the matrix with the corresponding orthonormal eigenvectors. The discrete heat kernel is the matrix given by,

K_{t}=\Phi \exp(-t\Lambda )\Phi ^{T}.

The elements $k_{t}(i,j)$ represents the heat diffusion between vertices $i$ and $j$ after time $t$ . The HKS is then given by the diagonal entries of this matrix, sampled at discrete time intervals. Similar to the continuous case, the discrete HKS is robust to noise.^[1]

Limitations

Non-repeating eigenvalues

The main property that characterizes surfaces using HKS up to an isometry holds only when the eigenvalues of the surfaces are non-repeating. There are certain surfaces (especially those with symmetry) where this condition is violated. A sphere is a simple example of such a surface.

Time parameter selection

The time parameter in the HKS is closely related to the scale of global information. However, there is no direct way to choose the time discretization. The existing method chooses time samples logarithmically which is a heuristic with no guarantees^[4]

Time complexity

The discrete heat kernel requires eigendecomposition of a matrix of size $n\times n$ , where $n$ is the number of vertices in the mesh representation of the manifold. Computing the eigendecomposition is an expensive operation, especially as $n$ increases. Note, however, that because of the inverse exponential dependence on the eigenvalue, typically only a small (less than 100) eigenvectors are sufficient to obtain a good approximation of the HKS.

Non-isometric transformations

The performance guarantees for HKS only hold for truly isometric transformations. However, deformations for real shapes are often not isometric. A simple example of such transformation is closing of the fist by a person, where the geodesic distances between two fingers changes.

Relation with other methods

Source:^[2]

Curvature

The (continuous) HKS at a point $x$ , $h_{t}(x,x)$ on the Riemannian manifold is related to the scalar curvature $s(x)$ by,

h_{t}(x,x)={\frac {1}{4\pi t}}+{\frac {s(x)}{12\pi }}+O(t).

Hence, HKS can as be interpreted as the curvature of $x$ at scale $t$ .

Wave kernel signature (WKS)

The WKS^[4] follows a similar idea to the HKS, replacing the heat equation with the Schrödinger wave equation,

\left(i\Delta +{\frac {\partial }{\partial t}}\right)\psi (x,t)=0

where $\psi (x,t)$ is the complex wave function. The average probability of measuring the particle at a point $x$ is given by,

p(x)=\sum _{i=0}^{\infty }f^{2}(\lambda _{i})\phi _{i}^{2}(x)

where $f$ is the initial energy distribution. By fixing a family of these energy distributions $f_{i}(x)$ , the WKS can be obtained as a discrete sequence $\{p_{f_{1}}(x),\ldots ,p_{f_{n}}(x)\}$ . Unlike HKS, the WKS can be intuited as a set of band-pass filters leading to better feature localization. However, the WKS does not represent large-scale features well (as they are filtered out) yielding poor performance at shape matching applications.

Global point signature (GPS)

Similar to the HKS, the GPS^[5] is based on the Laplace-Beltrami operator. GPS at a point $x$ is a vector of scaled eigenfunctions of the Laplace–Beltrami operator computed at $x$ . The GPS is a global feature whereas the scale of the HKS can be varied by varying the time parameter for heat diffusion. Hence, the HKS can be used in partial shape matching applications whereas the GPS cannot.

Spectral graph wavelet signature (SGWS)

SGWS^[6] provides a general form for spectral descriptors, where one can obtain HKS by specifying the filter function. SGWS is a multiresolution 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.

Extensions

Scale invariance

Even though the HKS represents the shape at multiple scales, it is not inherently scale invariant. For example, the HKS for a shape and its scaled version are not the same without pre-normalization. A simple way to ensure scale invariance is by pre-scaling each shape to have the same surface area (e.g. 1). Using the notation above, this means:

${\begin{aligned}s&=\sum _{j}A_{j}\\A&=A/s\\\lambda _{i}&=s\lambda _{i}{\text{ for each }}i\\\phi _{i}&={\sqrt {s}}\phi _{i}{\text{ for each }}i\\\end{aligned}}$

Alternatively, scale-invariant version of the HKS can also be constructed by generating a Scale space representation.^[7] In the scale-space, the HKS of a scaled shape corresponds to a translation up to a multiplicative factor. The Fourier transform of this HKS changes the time-translation into the complex plane, and the dependency on translation can be eliminated by considering the modulus of the transform. Demo of Scale-invariant HKS on YouTube. An alternative scale invariant HKS can be established by working out its construction through a scale invariant metric, as defined in.^[8]

Volumetric HKS

The HKS is defined for a boundary surface of a 3D shape, represented as a 2D Riemannian manifold. Instead of considering only the boundary, the entire volume of the 3D shape can be considered to define the volumetric version of the HKS.^[9] The Volumetric HKS is defined analogous to the normal HKS by considering the heat equation over the entire volume (as a 3-submanifold) and defining a Neumann boundary condition over the 2-manifold boundary of the shape. Volumetric HKS characterizes transformations up to a volume isometry, which represent the transformation for real 3D objects more faithfully than boundary isometry.^[9]

Shape Search

The scale-invariant HKS features can be used in the bag-of-features model for shape retrieval applications.^[10] The features are used to construct geometric words by taking into account their spatial relations, from which shapes can be constructed (analogous to using features as words and shapes as sentences). Shapes themselves are represented using compact binary codes to form an indexed collection. Given a query shape, similar shapes in the index with possibly isometric transformations can be retrieved by using the Hamming distance of the code as the nearness-measure.

Related Research Articles

In physics, mathematics and statistics, scale invariance is a feature of objects or laws that do not change if scales of length, energy, or other variables, are multiplied by a common factor, and thus represent a universality.

In mathematics, a Killing vector field, named after Wilhelm Killing, is a vector field on a Riemannian manifold that preserves the metric. Killing fields are the infinitesimal generators of isometries; that is, flows generated by Killing fields are continuous isometries of the manifold. More simply, the flow generates a symmetry, in the sense that moving each point of an object the same distance in the direction of the Killing vector will not distort distances on the object.

In system analysis, among other fields of study, a linear time-invariant (LTI) system is a system that produces an output signal from any input signal subject to the constraints of linearity and time-invariance; these terms are briefly defined below. These properties apply (exactly or approximately) to many important physical systems, in which case the response $y (t)$ of the system to an arbitrary input $x (t)$ can be found directly using convolution: $y (t) = (x * h)(t)$ where $h (t)$ is called the system's impulse response and ∗ represents convolution (not to be confused with multiplication). What's more, there are systematic methods for solving any such system (determining $h (t)$ ), whereas systems not meeting both properties are generally more difficult (or impossible) to solve analytically. A good example of an LTI system is any electrical circuit consisting of resistors, capacitors, inductors and linear amplifiers.

In mathematics, the discrete Laplace operator is an analog of the continuous Laplace operator, defined so that it has meaning on a graph or a discrete grid. For the case of a finite-dimensional graph, the discrete Laplace operator is more commonly called the Laplacian matrix.

In mathematics, the Poincaré metric, named after Henri Poincaré, is the metric tensor describing a two-dimensional surface of constant negative curvature. It is the natural metric commonly used in a variety of calculations in hyperbolic geometry or Riemann surfaces.

In differential geometry, the Laplace–Beltrami operator is a generalization of the Laplace operator to functions defined on submanifolds in Euclidean space and, even more generally, on Riemannian and pseudo-Riemannian manifolds. It is named after Pierre-Simon Laplace and Eugenio Beltrami.

In physics, a symmetry of a physical system is a physical or mathematical feature of the system that is preserved or remains unchanged under some transformation.

In cartography, a Tissot's indicatrix is a mathematical contrivance presented by French mathematician Nicolas Auguste Tissot in 1859 and 1871 in order to characterize local distortions due to map projection. It is the geometry that results from projecting a circle of infinitesimal radius from a curved geometric model, such as a globe, onto a map. Tissot proved that the resulting diagram is an ellipse whose axes indicate the two principal directions along which scale is maximal and minimal at that point on the map.

In the theory of von Neumann algebras, a part of the mathematical field of functional analysis, Tomita–Takesaki theory is a method for constructing modular automorphisms of von Neumann algebras from the polar decomposition of a certain involution. It is essential for the theory of type III factors, and has led to a good structure theory for these previously intractable objects.

In the mathematical study of heat conduction and diffusion, a heat kernel is the fundamental solution to the heat equation on a specified domain with appropriate boundary conditions. It is also one of the main tools in the study of the spectrum of the Laplace operator, and is thus of some auxiliary importance throughout mathematical physics. The heat kernel represents the evolution of temperature in a region whose boundary is held fixed at a particular temperature, such that an initial unit of heat energy is placed at a point at time t = 0.

In theoretical physics, scalar field theory can refer to a relativistically invariant classical or quantum theory of scalar fields. A scalar field is invariant under any Lorentz transformation.

In mathematics, the structure tensor, also referred to as the second-moment matrix, is a matrix derived from the gradient of a function. It describes the distribution of the gradient in a specified neighborhood around a point and makes the information invariant respect the observing coordinates. The structure tensor is often used in image processing and computer vision.

Thin plate splines (TPS) are a spline-based technique for data interpolation and smoothing. "A spline is a function defined by polynomials in a piecewise manner." They were introduced to geometric design by Duchon. They are an important special case of a polyharmonic spline. Robust Point Matching (RPM) is a common extension and shortly known as the TPS-RPM algorithm.

In operator theory, a bounded operator T: X → Y between normed vector spaces X and Y is said to be a contraction if its operator norm ||T || ≤ 1. This notion is a special case of the concept of a contraction mapping, but every bounded operator becomes a contraction after suitable scaling. The analysis of contractions provides insight into the structure of operators, or a family of operators. The theory of contractions on Hilbert space is largely due to Béla Szőkefalvi-Nagy and Ciprian Foias.

In mathematics, a quasi-isometry is a function between two metric spaces that respects large-scale geometry of these spaces and ignores their small-scale details. Two metric spaces are quasi-isometric if there exists a quasi-isometry between them. The property of being quasi-isometric behaves like an equivalence relation on the class of metric spaces.

In mathematics, the Plancherel theorem for spherical functions is an important result in the representation theory of semisimple Lie groups, due in its final form to Harish-Chandra. It is a natural generalisation in non-commutative harmonic analysis of the Plancherel formula and Fourier inversion formula in the representation theory of the group of real numbers in classical harmonic analysis and has a similarly close interconnection with the theory of differential equations. It is the special case for zonal spherical functions of the general Plancherel theorem for semisimple Lie groups, also proved by Harish-Chandra. The Plancherel theorem gives the eigenfunction expansion of radial functions for the Laplacian operator on the associated symmetric space X; it also gives the direct integral decomposition into irreducible representations of the regular representation on $L 2 (X)$ . In the case of hyperbolic space, these expansions were known from prior results of Mehler, Weyl and Fock.

Diffusion maps is a dimensionality reduction or feature extraction algorithm introduced by Coifman and Lafon which computes a family of embeddings of a data set into Euclidean space whose coordinates can be computed from the eigenvectors and eigenvalues of a diffusion operator on the data. The Euclidean distance between points in the embedded space is equal to the "diffusion distance" between probability distributions centered at those points. Different from linear dimensionality reduction methods such as principal component analysis (PCA), diffusion maps are part of the family of nonlinear dimensionality reduction methods which focus on discovering the underlying manifold that the data has been sampled from. By integrating local similarities at different scales, diffusion maps give a global description of the data-set. Compared with other methods, the diffusion map algorithm is robust to noise perturbation and computationally inexpensive.

Spectral shape analysis relies on the spectrum 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.

In mathematics, the Weil–Brezin map, named after André Weil and Jonathan Brezin, is a unitary transformation that maps a Schwartz function on the real line to a smooth function on the Heisenberg manifold. The Weil–Brezin map gives a geometric interpretation of the Fourier transform, the Plancherel theorem and the Poisson summation formula. The image of Gaussian functions under the Weil–Brezin map are nil-theta functions, which are related to theta functions. The Weil–Brezin map is sometimes referred to as the Zak transform, which is widely applied in the field of physics and signal processing; however, the Weil–Brezin Map is defined via Heisenberg group geometrically, whereas there is no direct geometric or group theoretic interpretation from the Zak transform.

In cosmology, Gurzadyan theorem, proved by Vahe Gurzadyan, states the most general functional form for the force satisfying the condition of identity of the gravity of the sphere and of a point mass located in the sphere's center. This theorem thus refers to the first statement of Isaac Newton’s shell theorem but not the second one, namely, the absence of gravitational force inside a shell.

References

1 2 3 4 5 6 7 Sun, J. and Ovsjanikov, M. and Guibas, L. (2009). "A Concise and Provably Informative Multi-Scale Signature-Based on Heat Diffusion". Computer Graphics Forum. Vol. 28. pp. 1383–1392.{{cite conference}}: CS1 maint: multiple names: authors list (link)
1 2 3 4 Alexander M. Bronstein (2011). "Spectral descriptors for deformable shapes". arXiv: 1110.5015 . Bibcode:2011arXiv1110.5015B.{{cite journal}}: Cite journal requires |journal= (help)
↑ Grigor'yan, Alexander (2006). "Heat kernels on weighted manifolds and applications". The ubiquitous heat kernel. Contemporary Mathematics. Vol. 398. Providence, RI: American Mathematical Society. pp. 93–191. doi:10.1090/conm/398/07486. MR 2218016.
1 2 Aubry, M. and Schlickewei, U. and Cremers, D. (2011). "The Wave Kernel Signature—A Quantum Mechanical Approach to Shape Analysis". IEEE International Conference on Computer Vision (ICCV) - Workshop on Dynamic Shape Capture and Analysis (4DMOD).{{cite conference}}: CS1 maint: multiple names: authors list (link)
↑ Rustamov, R.M. (2007). "Laplace–Beltrami eigenfunctions for deformation invariant shape representation". Proceedings of the fifth Eurographics symposium on Geometry processing. Eurographics Association. pp. 225–233.
↑ C. Li; A. Ben Hamza (2013). "A multiresolution descriptor for deformable 3D shape retrieval". The Visual Computer. 29 (6–8): 513–524. doi:10.1007/s00371-013-0815-3. S2CID 10125228.
↑ Bronstein, M.M.; Kokkinos, I. (2010). "Scale-invariant heat kernel signatures for non-rigid shape recognition". Computer Vision and Pattern Recognition (CVPR), 2010. IEEE. pp. 1704–1711.
↑ Aflalo, Yonathan; Kimmel, Ron; Raviv, Dan (2013). "Scale Invariant Geometry for Nonrigid Shapes". SIAM Journal on Imaging Sciences. 6 (3): 1579–1597. CiteSeerX 10.1.1.406.3701 . doi:10.1137/120888107.
1 2 Raviv, D. and Bronstein, M.M. and Bronstein, A.M. and Kimmel, R. (2010). "Volumetric heat kernel signatures". Proceedings of the ACM workshop on 3D object retrieval. ACM. pp. 30–44.{{cite conference}}: CS1 maint: multiple names: authors list (link)
↑ Bronstein, A.M. and Bronstein, M.M. and Guibas, L.J. and Ovsjanikov, M. (2011). "Shape google: Geometric words and expressions for invariant shape retrieval". ACM Transactions on Graphics. 30 (1). doi:10.1145/1899404.1899405. S2CID 7964594.{{cite journal}}: CS1 maint: multiple names: authors list (link)

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[sun2009concise-1] 1 2 3 4 5 6 7 Sun, J. and Ovsjanikov, M. and Guibas, L. (2009). "A Concise and Provably Informative Multi-Scale Signature-Based on Heat Diffusion". Computer Graphics Forum. Vol. 28. pp. 1383–1392.{{cite conference}}: CS1 maint: multiple names: authors list (link)

[bronstein2011spectral-2] 1 2 3 4 Alexander M. Bronstein (2011). "Spectral descriptors for deformable shapes". arXiv: 1110.5015 . Bibcode:2011arXiv1110.5015B.{{cite journal}}: Cite journal requires |journal= (help)

[grigor2006heat-3] Grigor'yan, Alexander (2006). "Heat kernels on weighted manifolds and applications". The ubiquitous heat kernel. Contemporary Mathematics. Vol. 398. Providence, RI: American Mathematical Society. pp. 93–191. doi:10.1090/conm/398/07486. MR 2218016.

[aubry2011wks-4] 1 2 Aubry, M. and Schlickewei, U. and Cremers, D. (2011). "The Wave Kernel Signature—A Quantum Mechanical Approach to Shape Analysis". IEEE International Conference on Computer Vision (ICCV) - Workshop on Dynamic Shape Capture and Analysis (4DMOD).{{cite conference}}: CS1 maint: multiple names: authors list (link)

[rustamov2007gps-5] Rustamov, R.M. (2007). "Laplace–Beltrami eigenfunctions for deformation invariant shape representation". Proceedings of the fifth Eurographics symposium on Geometry processing. Eurographics Association. pp. 225–233.

[Li13SGWS-6] C. Li; A. Ben Hamza (2013). "A multiresolution descriptor for deformable 3D shape retrieval". The Visual Computer. 29 (6–8): 513–524. doi:10.1007/s00371-013-0815-3. S2CID 10125228.

[bronstein2010si-7] Bronstein, M.M.; Kokkinos, I. (2010). "Scale-invariant heat kernel signatures for non-rigid shape recognition". Computer Vision and Pattern Recognition (CVPR), 2010. IEEE. pp. 1704–1711.

[raviv2013scale-8] Aflalo, Yonathan; Kimmel, Ron; Raviv, Dan (2013). "Scale Invariant Geometry for Nonrigid Shapes". SIAM Journal on Imaging Sciences. 6 (3): 1579–1597. CiteSeerX 10.1.1.406.3701 . doi:10.1137/120888107.

[raviv2010volumetric-9] 1 2 Raviv, D. and Bronstein, M.M. and Bronstein, A.M. and Kimmel, R. (2010). "Volumetric heat kernel signatures". Proceedings of the ACM workshop on 3D object retrieval. ACM. pp. 30–44.{{cite conference}}: CS1 maint: multiple names: authors list (link)

[bronsteing2011google-10] Bronstein, A.M. and Bronstein, M.M. and Guibas, L.J. and Ovsjanikov, M. (2011). "Shape google: Geometric words and expressions for invariant shape retrieval". ACM Transactions on Graphics. 30 (1). doi:10.1145/1899404.1899405. S2CID 7964594.{{cite journal}}: CS1 maint: multiple names: authors list (link)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]