Ming's Note

**Diffusion Distance**

A few weeks ago, we read two beautifully
written
papers in our graphics seminar. Both were about measuring the distance
between a
pair of points. While one deals with points in the interior of a mesh
[1], the other
one deals with points on a mesh [2]. I especially liked the discussion
we had
for the latter, where Misha gave a nice review of Diffusion Distance
[3] in
the beginning. I decided I should write it down along with some
thoughts before
my memory fades.

**Some quick
math reviews**

·
Delta
Function: a
delta function has zero value everywhere, except the origin where it
has an
impulse response. In 1-D it looks like:

subject to

So it is not really a function rather
a functional that only makes sense when we consider the integral of its
dot-product with some other function. Most importantly, given any
function f(x)
we have the following property:

In the rest of the article, we
will use to denote
a delta function that is translated and centered at p. That is: .

·
Heat
Diffusion on
a manifold: (I am going hand-wavy
here. More details can be found in [4].)

, such that

How can we solve it via Fourier
Decomposition? (See [5] for the analogy between
the eigenfuntions/eigenvectors
of the mesh Laplacian and the Fourier basis.)

Let be
eigenpairs of , where

In the discrete case, the
solution at time t is formulated as:

Given the initial state , we first compute its frequency coefficients
.

Then for any arbitrary time we can
predict the state using the above formulation. (Intuitively, this means
modulating each frequency component separately by and then
recombining them)

**Remark: **From this
interpretation, it becomes clear that Heat Diffusion is a smoothing
process
that suppresses high-frequency components *faster*
than it suppresses low-frequency components. And when goes to
infinity, only the DC term () will survive.

**Diffusion
Distance**

Intuitively, Diffusion Distance between a
pair of
points can be
thought of as following: We create a unit impulse function centered at (imagine a
fixed amount of energy concentrated at a
point), and
we let it diffuse for a period of time t. We create another impulse
function
centered at , and we also let it diffuse for a period
time t. At
the end, we look at the difference (measured by L2-norm) between the
two
distributions. And that is our Diffusion Distance.

Mathematically, this is
described by:

(1)

and are the
distribution functions undergoing Heat Diffusion, with the initial
states and .

We use and to denote
frequency
coefficients of and respectively,
i.e., and .

Now, notice the well-known fact
that forms an *orthonormal* basis. This results in two
consequences. First, (1) can be worked out to:

Second, finding their
coefficients with respect to a certain function is as easy as computing
their
dot-products with that function. In the case of delta functions, it is
even
easier, i.e., and

Putting these together, we
reach the common definition of the diffusion distance between
point and point :

**Relationship
to Commute-Time Distance and Biharmonic Distance**

Commute-Time
Distance [6]:

Biharmonic
Distance [2]:

(To finish...)** **

[1] Rustamov, R.,
Lipman, Y.,
Funkhouser, T. *Interior distance using
barycentric coordinates.* Computer Graphics Forum (Symposium on
Geometry Processing),
28(5), July 2009

[2] Lipman, Y.,
Rustamov, R.,
Funkhouser, T. *Biharmonic
Distance.* ACM Transactions on Graphics 29(3),
June 2010.

[3] GOES, F. D., GOLDENSTEIN, S., AND VELHO,
L. 2008. *A hierarchical segmentation
of articulated bodies*. Computer Graphics Forum (Special
Issue of
Symposium on Geometry Processing) 27, 5, 1349-1356.

[4] http://www.cs.jhu.edu/~misha/Fall08/09.pdf

[5] Taubin, G. 1995. *A signal processing approach to fair surface
design*. In ACM SIGGRAPH Conference
Proceedings,
351-358.

[6] FOUSS, F., PIROTTE, A., MICHEL RENDERS,
J., AND
SAERENS, M. 2006. *Random-walk
computation of similarities between nodes of a graph, with application
to
collaborative recommendation.* IEEE Transactions on Knowledge
and
Data Engineering 19, 2007