Heat kernel signature

Since ${\displaystyle h_{t}(x,x)}$ is, in general, a non-parametric continuous function, HKS is in practice represented as a discrete sequence of ${\displaystyle \{h_{t_{1}}(x,x),\ldots ,h_{t_{n}}(x,x)\}}$ values sampled at times ${\displaystyle 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 ${\displaystyle \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]

${\displaystyle L=A^{-1}W}$

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

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

The elements ${\displaystyle k_{t}(i,j)}$ represents the heat diffusion between vertices ${\displaystyle i}$ and ${\displaystyle j}$ after time ${\displaystyle 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]

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.

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]

The discrete heat kernel requires eigendecomposition of a matrix of size ${\displaystyle n\times n}$, where ${\displaystyle n}$ is the number of vertices in the mesh representation of the manifold. Computing the eigendecomposition is an expensive operation, especially as ${\displaystyle 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.

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.

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

${\displaystyle 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 ${\displaystyle x}$ at scale ${\displaystyle t}$.

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

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

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

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

where ${\displaystyle f}$ is the initial energy distribution. By fixing a family of these energy distributions ${\displaystyle f_{i}(x)}$, the WKS can be obtained as a discrete sequence ${\displaystyle \{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.

Similar to the HKS, the GPS[5] is based on the Laplace-Beltrami operator. GPS at a point ${\displaystyle x}$ is a vector of scaled eigenfunctions of the Laplace–Beltrami operator computed at ${\displaystyle 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.

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.

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:

${\displaystyle {\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]

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]

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.