Spectral Methods for Shape Analysis - Mathematical Tools for Shape Analysis and Description - page 40

5. SPECTRAL METHODS FOR SHAPE ANALYSIS
e heat kernel h t .x;y/ is a fundamental solution of equation 5.3 , with point heat source
at x , and heat value at y after time t: in other words, it represents the amount of heat transferred
from x to y in time t due to the diffusion process (Figure 5.4 ).
e value of the heat kernel h t .x;y/ can also be interpreted in terms of transition proba-
bility: given a Brownian motion (continuous analog of a random walk) on S starting at point x
and a subregion CS ,

R

C h t .x;z/dz is the probability that the Brownian motion will be in C

at time t .

Figure 5.4: e heat kernel represents the amount of heat transferred from a source point in time t .

Using spectral decomposition, the heat kernel can be represented as:

X

i t i .x/ i .y/

h t .x;y/D exp (5.4)

i 0

Here, i and i denote, respectively, the eigenfunctions and eigenvalues of the Laplace-Beltrami
operator satisfying i D i i .
Since the coefficients rapidly decay, the heat kernel is generally approximated by the trun-
cated sum:

h t .x;y/D N X
1

i t i .x/ i .y/:

exp (5.5)

e computation of the spectrum of the discrete Laplacian is the main computational bot-
tleneck for the evaluation of the heat kernel; in fact, it takes from O.n/ to O.n 3 / operations,
according to the sparsity of the Laplacian matrix. Recently, a discrete and spectrum-free com-
putation of the diffusion kernel on a 3D shape (either represented as a triangulation or a point
cloud) has been proposed in [ 161 ]. e main idea is to avoid the computation of the full spectrum
adopting the Chebyshev approximation [ 47 , 144 ] of the weighted heat kernel matrix. In practice,
the approximation of the diffusion kernel is reduced to the solution of the sparse linear systems
and a sequence of matrix-vector multiplications, without computing the Laplacian spectrum.

5.2.1 CONCEPTS IN ACTION
e heat kernel signature (HKS) Sun et al. [ 190 ] proposed using the diagonal of the heat kernel,
restricted to the temporal domain, as a local descriptor, referred to as the Heat Kernel Signature