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