A heat kernel signature (HKS) is a feature descriptor for use in deformable
shape analysis and belongs to the group of
spectral shape analysis 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 ...
methods. For each point in the shape, HKS defines its
feature vector
In machine learning and pattern recognition, a feature is an individual measurable property or characteristic of a phenomenon. Choosing informative, discriminating and independent features is a crucial element of effective algorithms in pattern r ...
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
Leonidas John Guibas ( el, Λεωνίδας Γκίμπας) is the Paul Pigott Professor of Computer Science and Electrical Engineering at Stanford University. He heads the Geometric Computation group in the Computer Science Department.
Guibas ...
.
It is based on
heat kernel
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 spectru ...
, which is a fundamental solution to the
heat equation
In mathematics and physics, the heat equation is a certain partial differential equation. Solutions of the heat equation are sometimes known as caloric functions. The theory of the heat equation was first developed by Joseph Fourier in 1822 for t ...
. HKS is one of the many recently introduced shape descriptors which are based on the
Laplace–Beltrami operator
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 af ...
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 vector
In machine learning and pattern recognition, a feature is an individual measurable property or characteristic of a phenomenon. Choosing informative, discriminating and independent features is a crucial element of effective algorithms in pattern r ...
s for certain key points are used instead of using the complete
3D model
In 3D computer graphics, 3D modeling is the process of developing a mathematical coordinate-based representation of any surface of an object (inanimate or living) in three dimensions via specialized software by manipulating edges, vertices, an ...
of the shape. An important requirement of such feature descriptors is for them to be invariant under certain transformations. For
rigid transformation
In mathematics, a rigid transformation (also called Euclidean transformation or Euclidean isometry) is a geometric transformation of a Euclidean space that preserves the Euclidean distance between every pair of points.
The rigid transformations ...
s, commonly used feature descriptors include
shape context
A shape or figure is a graphical representation of an object or its external boundary, outline, or external surface, as opposed to other properties such as color, texture, or material type.
A plane shape or plane figure is constrained to lie on ...
, spin images, integral volume descriptors and multiscale local features, among others.
HKS allows
isometric transformation
In mathematics, an isometry (or congruence, or congruent transformation) is a distance-preserving transformation between metric spaces, usually assumed to be bijective. The word isometry is derived from the Ancient Greek: ἴσος ''isos'' mea ...
s which generalizes rigid transformations.
HKS is based on the concept of
heat diffusion
In mathematics and physics, the heat equation is a certain partial differential equation. Solutions of the heat equation are sometimes known as caloric functions. The theory of the heat equation was first developed by Joseph Fourier in 1822 fo ...
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
In mathematics and physics, the heat equation is a certain partial differential equation. Solutions of the heat equation are sometimes known as caloric functions. The theory of the heat equation was first developed by Joseph Fourier in 1822 fo ...
equation over a
compact
Compact as used in politics may refer broadly to a pact or treaty; in more specific cases it may refer to:
* Interstate compact
* Blood compact, an ancient ritual of the Philippines
* Compact government, a type of colonial rule utilized in British ...
Riemannian manifold
In differential geometry, a Riemannian manifold or Riemannian space , so called after the German mathematician Bernhard Riemann, is a real manifold, real, smooth manifold ''M'' equipped with a positive-definite Inner product space, inner product ...
(possibly with a boundary) is given by,
:
where
is the
Laplace–Beltrami operator
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 af ...
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
In mathematics, a surjective function (also known as surjection, or onto function) is a function that every element can be mapped from element so that . In other words, every element of the function's codomain is the image of one element of i ...
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
A mesh is a barrier made of connected strands of metal, fiber, or other flexible or ductile materials. A mesh is similar to a web or a net in that it has many attached or woven strands.
Types
* A plastic mesh may be extruded, oriented, ex ...
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
Time complexity
The discrete heat kernel requires eigendecomposition of a matrix of size
, where
is the number of vertices in the mesh representation of the manifold. Computing the eigendecomposition is an expensive operation, especially as
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
Curvature
The (continuous) HKS at a point
,
on the Riemannian manifold is related to the
scalar curvature
In the mathematical field of Riemannian geometry, the scalar curvature (or the Ricci scalar) is a measure of the curvature of a Riemannian manifold. To each point on a Riemannian manifold, it assigns a single real number determined by the geometry ...
by,
:
Hence, HKS can as be interpreted as the curvature of
at scale
.
Wave kernel signature (WKS)
The WKS
follows a similar idea to the HKS, replacing the heat equation with the
Schrödinger wave equation,
:
where
is the complex wave function. The average probability of measuring the particle at a point
is given by,
:
where
is the initial energy distribution. By fixing a family of these energy distributions
, the WKS can be obtained as a discrete sequence
. 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
is based on the Laplace-Beltrami operator. GPS at a point
is a vector of scaled eigenfunctions of the Laplace–Beltrami operator computed at
. 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
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:
Alternatively, scale-invariant version of the HKS can also be constructed by generating a
Scale space representation
Scale-space theory is a framework for multi-scale signal representation developed by the computer vision, image processing and signal processing communities with complementary motivations from physics and biological vision. It is a formal th ...
.
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.
.
An alternative scale invariant HKS can be established by working out its construction through a scale invariant metric, as defined in.
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.
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
In mathematics, the Neumann (or second-type) boundary condition is a type of boundary condition, named after Carl Neumann.
When imposed on an ordinary or a partial differential equation, the condition specifies the values of the derivative appl ...
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.
Shape Search
The scale-invariant HKS features can be used in the
bag-of-features model for shape retrieval applications.
[{{cite journal
, author = Bronstein, A.M. and Bronstein, M.M. and Guibas, L.J. and Ovsjanikov, M.
, year = 2011
, title = Shape google: Geometric words and expressions for invariant shape retrieval
, journal = ACM Transactions on Graphics
, volume = 30
, number = 1
, doi = 10.1145/1899404.1899405
, s2cid = 7964594
] 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.
References
Image processing
Heat transfer
Digital geometry
Topology
Differential geometry