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.
HKS was introduced in 2009 by Jian Sun, Maks Ovsjanikov and Leonidas Guibas. 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.
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. 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 over the surface, the heat kernel relates the amount of heat transferred from to after time . The heat kernel is invariant under isometric transformations and stable under small perturbations to the isometry. In addition, the heat kernel fully characterizes shapes up to an isometry and represents increasingly global properties of the shape with increasing time. Since 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 . HKS inherits most of the properties of heat kernels under certain conditions.
Technical details
The heat diffusion equation over a compact Riemannian manifold (possibly with a boundary) is given by,
where is the Laplace–Beltrami operator and is the heat distribution at a point at time . The solution to this equation can be expressed as,
The eigen decomposition of the heat kernel is expressed as,
where and are the eigenvalue and eigenfunction of . The heat kernel fully characterizes a surface up to an isometry: For any surjective map between two Riemannian manifolds and , if then is an isometry, and vice versa. For a concise feature descriptor, HKS restricts the heat kernel only to the temporal domain,
HKS, similar to the heat kernel, characterizes surfaces under the condition that the eigenvalues of for and are non-repeating. The terms can be intuited as a bank of low-pass filters, with determining the cutoff frequencies.
Practical considerations
Since is, in general, a non-parametric continuous function, HKS is in practice represented as a discrete sequence of values sampled at times .
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 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,
where is a positive diagonal matrix with entries corresponding to the area of the triangles in the mesh sharing the vertex , and is a symmetric semi-definite weighting matrix. can be decomposed into , where is a diagonal matrix of the eigenvalues of arranged in the ascending order, and is the matrix with the corresponding orthonormal eigenvectors. The discrete heat kernel is the matrix given by,
The elements represents the heat diffusion between vertices and after time . 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.
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