### Spectral methods in deformable shape analysis

Alex Bronstein, Michael Bronstein, Umberto Castellani

March 14, 2012

### Dimensions of media

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Dimensions of media

### Dimensions of media

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Dimensions of media

### 3D shapes vs. images

Array of pixels

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### 3D shapes vs. images

Array of pixels

### 3D shapes vs. images

Affine, projective

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### 3D shapes vs. images

### 3D shapes vs. images

### 1

### 2 + ^{1} _{2} =

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### 3D shapes vs. images

### 1

### 2 + ^{1} _{2} =

### 1

### 2 + ^{1} _{2} = ?

### Setting

Endow shapes with a structre

Similarity, correspondence, retrieval, etc. = similarity and correspondence between structures

Invariance under bending, scale, affine transformations, etc.

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Setting

Endow shapes with a structre

### Structure

Global structure Metric space

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Structure

Global structure Metric space

Local structure Point descriptors

### Structure

Global structure Metric space

Glocal structure Stable regions

Local structure Point descriptors

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Structure

Global structure Metric space

Glocal structure Stable regions

Local structure Point descriptors

### Agenda

Diffusion processes on surfaces Spectral point of view

Global structure: diffusion geometry Local structure: diffusion kernel descriptors

Semi-local structure: maximally stable components Extensions

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Diffusion processes on surfaces

Heat equation

∆_{X} + ∂

∂t

u = 0

governs heat propagation on manifold X

Solution u(x,t): heat distribution at pointx at time t Initial condition u0(x): heat distribution at time t = 0 Boundary condition if manifold has a boundary

### Diffusion processes on surfaces

Heat equation

∆_{X} + ∂

∂t

u = 0

governs heat propagation on manifold X

Solution u(x,t): heat distribution at pointx at time t Initial condition u0(x): heat distribution at time t = 0 Boundary condition if manifold has a boundary

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Laplace-Beltrami operator ∆

_{X}

For two smooth functionsf,g :X →Rand standard inner product onX

hf,gi= Z

X

f(x)g(x)da the Laplacian satisfies the following properties:

Constant eigenfunction: ∆Xf = 0 if f =const

Symmetry: h∆_{X}f,gi=h∆_{X}g,fi

Locality: (∆Xf)(x) does not depend onf(x^{0}) at anyx^{0}6=x
Linear precision: ifX as a plane andf =ax+by+c, then

∆Xf = 0

Positive semi-definiteness: h∆_{X}f,fi ≥0

Maximum principle: functions satisfying ∆Xf = 0 (harmonic) have no minima/maxima in the interior ofX

### Laplace-Beltrami operator ∆

_{X}

For two smooth functionsf,g :X →Rand standard inner product onX

hf,gi= Z

X

f(x)g(x)da the Laplacian satisfies the following properties:

Constant eigenfunction: ∆Xf = 0 if f =const
Symmetry: h∆_{X}f,gi=h∆_{X}g,fi

Locality: (∆Xf)(x) does not depend onf(x^{0}) at anyx^{0}6=x
Linear precision: ifX as a plane andf =ax+by+c, then

∆Xf = 0

Positive semi-definiteness: h∆_{X}f,fi ≥0

Maximum principle: functions satisfying ∆Xf = 0 (harmonic) have no minima/maxima in the interior ofX

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Laplace-Beltrami operator ∆

_{X}

For two smooth functionsf,g :X →Rand standard inner product onX

hf,gi= Z

X

f(x)g(x)da the Laplacian satisfies the following properties:

Constant eigenfunction: ∆Xf = 0 if f =const
Symmetry: h∆_{X}f,gi=h∆_{X}g,fi

Locality: (∆Xf)(x) does not depend onf(x^{0}) at anyx^{0} 6=x

Linear precision: ifX as a plane andf =ax+by+c, then

∆Xf = 0

Positive semi-definiteness: h∆_{X}f,fi ≥0

Maximum principle: functions satisfying ∆Xf = 0 (harmonic) have no minima/maxima in the interior ofX

### Laplace-Beltrami operator ∆

_{X}

For two smooth functionsf,g :X →Rand standard inner product onX

hf,gi= Z

X

f(x)g(x)da the Laplacian satisfies the following properties:

Constant eigenfunction: ∆Xf = 0 if f =const
Symmetry: h∆_{X}f,gi=h∆_{X}g,fi

Locality: (∆Xf)(x) does not depend onf(x^{0}) at anyx^{0} 6=x
Linear precision: ifX as a plane andf =ax+by+c, then

∆Xf = 0

Positive semi-definiteness: h∆_{X}f,fi ≥0

Maximum principle: functions satisfying ∆Xf = 0 (harmonic) have no minima/maxima in the interior ofX

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Laplace-Beltrami operator ∆

_{X}

For two smooth functionsf,g :X →Rand standard inner product onX

hf,gi= Z

X

f(x)g(x)da the Laplacian satisfies the following properties:

Constant eigenfunction: ∆Xf = 0 if f =const
Symmetry: h∆_{X}f,gi=h∆_{X}g,fi

^{0}) at anyx^{0} 6=x
Linear precision: ifX as a plane andf =ax+by+c, then

∆Xf = 0

Maximum principle: functions satisfying ∆Xf = 0 (harmonic) have no minima/maxima in the interior ofX

### Laplace-Beltrami operator ∆

_{X}

For two smooth functionsf,g :X →Rand standard inner product onX

hf,gi= Z

X

f(x)g(x)da the Laplacian satisfies the following properties:

Constant eigenfunction: ∆Xf = 0 if f =const
Symmetry: h∆_{X}f,gi=h∆_{X}g,fi

^{0}) at anyx^{0} 6=x
Linear precision: ifX as a plane andf =ax+by+c, then

∆Xf = 0

Positive semi-definiteness: h∆_{X}f,fi ≥0

Maximum principle: functions satisfying ∆Xf = 0 (harmonic) have no minima/maxima in the interior ofX

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Discretization of the Laplacian

SurfaceX isdiscretized at n points{x1, . . . ,xn} and points are connected to form a triangular mesh

Function f :X →Rrepresented a vector f ∈R^{n},fi =f(xi)
Discrete version of the Laplacian

(LXf)i = 1 ai

X

j

wij(fi−fj)

wij – edge weights,ai vertex normalization coefficients. In matrix notation

LXf =A^{−1}Lf
where A=diag{ai} and (L)ij =diag

X

k6=i

wik

−wij

### Discretization of the Laplacian

SurfaceX isdiscretized at n points{x1, . . . ,xn} and points are connected to form a triangular mesh

Function f :X →Rrepresented a vector f ∈R^{n},fi =f(xi)

Discrete version of the Laplacian (LXf)i = 1

ai

X

j

wij(fi−fj)

wij – edge weights,ai vertex normalization coefficients. In matrix notation

LXf =A^{−1}Lf
where A=diag{ai} and (L)ij =diag

X

k6=i

wik

−wij

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Discretization of the Laplacian

SurfaceX isdiscretized at n points{x1, . . . ,xn} and points are connected to form a triangular mesh

Function f :X →Rrepresented a vector f ∈R^{n},fi =f(xi)
Discrete version of the Laplacian

(LXf)i = 1 ai

X

j

wij(fi−fj)

wij – edge weights,ai vertex normalization coefficients.

In matrix notation

LXf =A^{−1}Lf
where A=diag{ai} and (L)ij =diag

X

k6=i

wik

−wij

### Discretization of the Laplacian

SurfaceX isdiscretized at n points{x1, . . . ,xn} and points are connected to form a triangular mesh

Function f :X →Rrepresented a vector f ∈R^{n},fi =f(xi)
Discrete version of the Laplacian

(LXf)i = 1 ai

X

j

wij(fi−fj)

wij – edge weights,ai vertex normalization coefficients.

In matrix notation

LXf =A^{−1}Lf
whereA=diag{ai} and (L)ij =diag

X

k6=i

wik

−wij

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Discretization of the Laplacian

xi

xj

xi

xj

α_{ij}
β_{ij}

Discrete Laplacian wij =

1 : xj ∈ N_{1}(xi)
0 : else

Discretized Laplacian wij =

cotα_{ij} + cotβ_{ij} : xj ∈ N_{1}(xi)

0 : else

### Desired properties of discrete Laplacians

Constant eigenfunction: ∆Xf = 0 if f =const

Symmetry: Locality:

Linear precision:

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Desired properties of discrete Laplacians

Constant eigenfunction: Satisfied by construction of LX

Symmetry: Locality:

Linear precision:

### Desired properties of discrete Laplacians

Constant eigenfunction: Satisfied by construction of LX

Symmetry: h∆_{X}f,gi=h∆_{X}g,fi

Locality:

Linear precision:

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Desired properties of discrete Laplacians

Constant eigenfunction: Satisfied by construction of LX

Symmetry: LX =L^{T}_{X}

Locality:

Linear precision:

### Desired properties of discrete Laplacians

Constant eigenfunction: Satisfied by construction of LX

Symmetry: LX =L^{T}_{X}

Reason: To have real eigenvalues and orthogonal eigenvectors

Locality:

Linear precision:

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Desired properties of discrete Laplacians

Constant eigenfunction: Satisfied by construction of LX

Symmetry: LX =L^{T}_{X}

Reason: To have real eigenvalues and orthogonal eigenvectors
Locality: (∆Xf)(x) does not depend onf(x^{0}) at anyx^{0} 6=x

Linear precision:

### Desired properties of discrete Laplacians

Constant eigenfunction: Satisfied by construction of LX

Symmetry: LX =L^{T}_{X}

Reason: To have real eigenvalues and orthogonal eigenvectors
Locality: wij = 0 ifxj 6=N_{1}(xi)

Linear precision:

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Desired properties of discrete Laplacians

Constant eigenfunction: Satisfied by construction of LX

Symmetry: LX =L^{T}_{X}

Reason: To have real eigenvalues and orthogonal eigenvectors
Locality: wij = 0 ifxj 6=N_{1}(xi)

wij stand for random walk transition probabilities along the graph edges.

Linear precision:

### Desired properties of discrete Laplacians

Constant eigenfunction: Satisfied by construction of LX

Symmetry: LX =L^{T}_{X}

Reason: To have real eigenvalues and orthogonal eigenvectors
Locality: wij = 0 ifxj 6=N_{1}(xi)

wij stand for random walk transition probabilities along the graph edges.

Linear precision: ifX as a plane andf =ax+by+c, then

∆_{X}f = 0

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Desired properties of discrete Laplacians

Constant eigenfunction: Satisfied by construction of LX

Symmetry: LX =L^{T}_{X}

Reason: To have real eigenvalues and orthogonal eigenvectors
Locality: wij = 0 ifxj 6=N_{1}(xi)

wij stand for random walk transition probabilities along the graph edges.

Linear precision: equivalently, if X is a plane, then (LXx)i =X

wij(xi −xj) = 0

### Desired properties of discrete Laplacians

Constant eigenfunction: Satisfied by construction of LX

Symmetry: LX =L^{T}_{X}

Reason: To have real eigenvalues and orthogonal eigenvectors
Locality: wij = 0 ifxj 6=N_{1}(xi)

wij stand for random walk transition probabilities along the graph edges.

Linear precision: equivalently, if X is a plane, then (LXx)i =X

j

wij(xi −xj) = 0

Reason: Flat plate must have zero bending energy.

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Desired properties of discrete Laplacians

Positive semi-definiteness: h∆_{X}f,fi ≥0

Positive weights: wij ≥0 and each vertexi has at least one wij >0

Convergence: solution of discrete PDE withLX converges to
solution of continuous PDE with ∆_{X} as n→ ∞

### Desired properties of discrete Laplacians

Positive semi-definiteness: f^{T}LXf ≥0, i.e.,LX 0

Positive weights: wij ≥0 and each vertexi has at least one wij >0

Convergence: solution of discrete PDE withLX converges to
solution of continuous PDE with ∆_{X} as n→ ∞

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Desired properties of discrete Laplacians

Positive semi-definiteness: f^{T}LXf ≥0, i.e.,LX 0
Positive weights: wij ≥0 and each vertexi has at least one
wij >0

Convergence: solution of discrete PDE withLX converges to
solution of continuous PDE with ∆_{X} as n→ ∞

### Desired properties of discrete Laplacians

Positive semi-definiteness: f^{T}LXf ≥0, i.e.,LX 0
Positive weights: wij ≥0 and each vertexi has at least one
wij >0

Reasons: Sufficient condition to satisfy discretemaximum principle

_{X} as n→ ∞

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Desired properties of discrete Laplacians

Positive semi-definiteness: f^{T}LXf ≥0, i.e.,LX 0
Positive weights: wij ≥0 and each vertexi has at least one
wij >0

Reasons: Sufficient condition to satisfy discretemaximum principle

Positive weights + Symmetry⇒ PSD

_{X} as n→ ∞

### Desired properties of discrete Laplacians

^{T}LXf ≥0, i.e.,LX 0
Positive weights: wij ≥0 and each vertexi has at least one
wij >0

Reasons: Sufficient condition to satisfy discretemaximum principle

Positive weights + Symmetry⇒ PSD

_{X} as n→ ∞

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Desired properties of discrete Laplacians

^{T}LXf ≥0, i.e.,LX 0
Positive weights: wij ≥0 and each vertexi has at least one
wij >0

Reasons: Sufficient condition to satisfy discretemaximum principle

Positive weights + Symmetry⇒ PSD

Convergence: solution of discrete PDE withLX converges to solution of continuous PDE with ∆X as n→ ∞

Indispensable for discretization of PDE solutions

### No free lunch

Discrete Laplacians are not convergent

cot weight discretized Laplacians is convergentbut has negative weights

Many attempts have been made to construct discrete Laplacians satisfying above desired properties

“No free lunch theorem” (Wardetzky et al., 2007) There is no discrete Laplacian satisfying the above properties simultaneously!

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### No free lunch

Discrete Laplacians are not convergent

cot weight discretized Laplacians is convergentbut has negative weights

Many attempts have been made to construct discrete Laplacians satisfying above desired properties

“No free lunch theorem” (Wardetzky et al., 2007) There is no discrete Laplacian satisfying the above properties simultaneously!

### No free lunch

Discrete Laplacians are not convergent

cot weight discretized Laplacians is convergentbut has negative weights

Many attempts have been made to construct discrete Laplacians satisfying above desired properties

“No free lunch theorem” (Wardetzky et al., 2007) There is no discrete Laplacian satisfying the above properties simultaneously!

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### No free lunch

Discrete Laplacians are not convergent

cot weight discretized Laplacians is convergentbut has negative weights

Many attempts have been made to construct discrete Laplacians satisfying above desired properties

### Eigendecomposition of Laplacian

Oncompact domains Laplacian admitscountable orthogonal eigendecomposition

∆_{X}φ_{i} =λ_{i}φ_{i}

λ_{i} – eigenvalues;φ_{i}(x) – corresponding eigenfunctions

Discrete generalized eigendecompositionfor LX =A^{−1}L
AΦ = ΛLΦ

Λ =diag{λ_{1}, . . . , λk} – diagonal matrix of firstk eigenvalues
Φ – n×k matrix of corresponding eigenvectors

Spectral decomposition theorem
(∆_{X}f)(x) =X

i≥0

λ_{i}φ_{i}(x)· hφ_{i},fi
Discrete equivalent: LXf =X

i≥0

λ_{i}φ_{i}φ^{T}_{i} f

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Eigendecomposition of Laplacian

Oncompact domains Laplacian admitscountable orthogonal eigendecomposition

∆_{X}φ_{i} =λ_{i}φ_{i}

λ_{i} – eigenvalues;φ_{i}(x) – corresponding eigenfunctions
Discrete generalized eigendecompositionfor LX =A^{−1}L

AΦ = ΛLΦ

Λ =diag{λ_{1}, . . . , λ_{k}} – diagonal matrix of firstk eigenvalues
Φ – n×k matrix of corresponding eigenvectors

Spectral decomposition theorem
(∆_{X}f)(x) =X

i≥0

λ_{i}φ_{i}(x)· hφ_{i},fi
Discrete equivalent: LXf =X

i≥0

λ_{i}φ_{i}φ^{T}_{i} f

### Eigendecomposition of Laplacian

Oncompact domains Laplacian admitscountable orthogonal eigendecomposition

∆_{X}φ_{i} =λ_{i}φ_{i}

λ_{i} – eigenvalues;φ_{i}(x) – corresponding eigenfunctions
Discrete generalized eigendecompositionfor LX =A^{−1}L

AΦ = ΛLΦ

Λ =diag{λ_{1}, . . . , λ_{k}} – diagonal matrix of firstk eigenvalues
Φ – n×k matrix of corresponding eigenvectors

Spectral decomposition theorem
(∆_{X}f)(x) =X

i≥0

λ_{i}φ_{i}(x)· hφ_{i},fi
Discrete equivalent: LXf =X

i≥0

λ_{i}φ_{i}φ^{T}_{i} f

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Finite elements

Discretize {λ_{i}, φ_{i}}directly!

Weak form eigendecomposition

h∆_{X}φ, αi=λhφ, αi

Fix a sufficiently regular basis {α_{1}, . . . , αm} spanning a
subspace of L^{2}(X)

φ(x)≈u1α1(x) +· · ·umαm(x)

Write a system of equations for k = 1, . . . ,m

m

X

i=1

uih∆_{X}α_{i}, α_{j}i

| {z }

aij

=

m

X

i=1

uihα_{i}, α_{j}i

| {z }

bij

In matrix notation: Au=λBu

### Finite elements

Discretize {λ_{i}, φ_{i}}directly!

Weak form eigendecomposition

h∆_{X}φ, αi=λhφ, αi

Fix a sufficiently regular basis {α_{1}, . . . , αm} spanning a
subspace of L^{2}(X)

φ(x)≈u1α1(x) +· · ·umαm(x)

Write a system of equations for k = 1, . . . ,m

m

X

i=1

uih∆_{X}α_{i}, α_{j}i

| {z }

aij

=

m

X

i=1

uihα_{i}, α_{j}i

| {z }

bij

In matrix notation: Au=λBu

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Finite elements

Discretize {λ_{i}, φ_{i}}directly!

Weak form eigendecomposition

h∆_{X}φ, αi=λhφ, αi

Fix a sufficiently regular basis {α_{1}, . . . , αm} spanning a
subspace of L^{2}(X)

φ(x)≈u1α1(x) +· · ·umαm(x)

Write a system of equations for k = 1, . . . ,m

m

X

i=1

uih∆_{X}α_{i}, α_{j}i

| {z }

aij

=

m

X

i=1

uihα_{i}, α_{j}i

| {z }

bij

In matrix notation: Au=λBu

### Finite elements

Discretize {λ_{i}, φ_{i}}directly!

Weak form eigendecomposition

h∆_{X}φ, αi=λhφ, αi

Fix a sufficiently regular basis {α_{1}, . . . , αm} spanning a
subspace of L^{2}(X)

φ(x)≈u1α1(x) +· · ·umαm(x)

Write a system of equations for k = 1, . . . ,m

m

X

i=1

uih∆_{X}α_{i}, α_{j}i

| {z }

aij

=

m

X

i=1

uihα_{i}, α_{j}i

| {z }

bij

In matrix notation: Au=λBu

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Finite elements

Discretize {λ_{i}, φ_{i}}directly!

Weak form eigendecomposition

h∆_{X}φ, αi=λhφ, αi

Fix a sufficiently regular basis {α_{1}, . . . , αm} spanning a
subspace of L^{2}(X)

φ(x)≈u1α1(x) +· · ·umαm(x)

Write a system of equations for k = 1, . . . ,m

m

Xuih∆_{X}α_{i}, α_{j}i =

m

Xuihα_{i}, α_{j}i

In matrix notation: Au=λBu

### Finite elements

Discretize {λ_{i}, φ_{i}}directly!

Weak form eigendecomposition

h∆_{X}φ, αi=λhφ, αi

Fix a sufficiently regular basis {α_{1}, . . . , αm} spanning a
subspace of L^{2}(X)

φ(x)≈u1α1(x) +· · ·umαm(x)

Write a system of equations for k = 1, . . . ,m

m

X

i=1

uih∆_{X}α_{i}, α_{j}i

| {z }

aij

=

m

X

i=1

uihα_{i}, α_{j}i

| {z }

bij

In matrix notation: Au=λBu

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### To see the sound

### Chladni plates

Solutions to stationary Helmholtz equation

∆_{X}f =λf

Laplacian eigenfunctions = plate vibration modes

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Chladni plates

Solutions to stationary Helmholtz equation

∆ f =λf

### Shape DNA

(Reuteret al., 2006) use Laplacian spectrum{λ_{i}} as an
isometry-invariant shape descriptor –shape DNA

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Shape DNA

### “Can we hear the shape of the drum?”

Isometric shapes areisospectral

Are isospectral shapes isometric?

Can one hear the shape of the drum? (Mark Kac)

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### “Can we hear the shape of the drum?”

Isometric shapes areisospectral Are isospectral shapes isometric?

Can one hear the shape of the drum? (Mark Kac)

### “Can we hear the shape of the drum?”

Isometric shapes areisospectral Are isospectral shapes isometric?

Can one hear the shape of the drum? (Mark Kac)

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### “Can we hear the shape of the drum?”

The following shape properties can be recovered (“heard”) from the spectrum of the Laplacian:

Area

Euler characteristic (genus) Total Gaussian curvature Can we hear the metric?

### “Can we hear the shape of the drum?”

The following shape properties can be recovered (“heard”) from the spectrum of the Laplacian:

Area

Euler characteristic (genus)

Total Gaussian curvature Can we hear the metric?

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### “Can we hear the shape of the drum?”

The following shape properties can be recovered (“heard”) from the spectrum of the Laplacian:

Area

Euler characteristic (genus) Total Gaussian curvature

Can we hear the metric?

### “Can we hear the shape of the drum?”

The following shape properties can be recovered (“heard”) from the spectrum of the Laplacian:

Area

Euler characteristic (genus) Total Gaussian curvature Can we hear the metric?

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### One cannot hear the shape of the drum!

### Relation to harmonic analysis

1D signals

− d^{2}

dx^{2}e^{inx} =n^{2}e^{inx}

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Relation to harmonic analysis

1D signals

− d^{2}

e^{inx} n^{2}e^{inx}

3D shapes

∆_{X}φ_{i}(x) =λ_{i}φ_{i}(x)

### Relation to harmonic analysis

A continuous functionf ∈L^{2}(X) can be represented as
Synthesis: f(x) =X

i≥0

F(λ_{i})φ_{i}(x)

Analysis: F(λ_{i}) =
Z

X

f(x)φi(x)da=hf, φ_{i}i
λ=frequency

{F(λ_{i})} =Fourier coefficients

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Relation to harmonic analysis

A continuous functionf ∈L^{2}(X) can be represented as
Synthesis: f(x) =X

i≥0

F(λ_{i})φ_{i}(x)
Analysis: F(λ_{i}) =

Z

X

f(x)φi(x)da=hf, φ_{i}i

λ=frequency

{F(λ_{i})} =Fourier coefficients

### Relation to harmonic analysis

A continuous functionf ∈L^{2}(X) can be represented as
Synthesis: f(x) =X

i≥0

F(λ_{i})φ_{i}(x)
Analysis: F(λ_{i}) =

Z

X

f(x)φi(x)da=hf, φ_{i}i
λ=frequency

{F(λ_{i})} =Fourier coefficients

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Relation to harmonic analysis

A continuous functionf ∈L^{2}(X) can be represented as
Synthesis: f(x) =X

i≥0

F(λ_{i})φ_{i}(x)
Analysis: F(λ_{i}) =

Z

X

f(x)φi(x)da=hf, φ_{i}i
λ=frequency

{F(λ_{i})} =Fourier coefficients

### Heat kernel

Heat equation

∆_{X} + ∂

∂t

u = 0

Solution given by heat operator
u(x,t) = (H^{t}u0)(x) =

Z

X

ht(x,y)u0(y)da(y)

Heat kernel ht(x,y) : solution at pointx at time t with point heat source at y

Impulse responseof heat equation

Intrinsic quantity – invariant to inelastic (isometric) bending Heat operator can be interpreted as a non shift-invariant version of convolution

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Heat kernel

Heat equation

∆_{X} + ∂

∂t

u = 0

Solution given by heat operator
u(x,t) = (H^{t}u0)(x) =

Z

X

ht(x,y)u0(y)da(y)

Heat kernel ht(x,y) : solution at pointx at time t with point heat source at y

Impulse responseof heat equation

Intrinsic quantity – invariant to inelastic (isometric) bending Heat operator can be interpreted as a non shift-invariant version of convolution

### Heat kernel

Heat equation

∆_{X} + ∂

∂t

u = 0

Solution given by heat operator
u(x,t) = (H^{t}u0)(x) =

Z

X

ht(x,y)u0(y)da(y)

Heat kernel ht(x,y) : solution at point x at time t with point heat source at y

Impulse responseof heat equation

Intrinsic quantity – invariant to inelastic (isometric) bending Heat operator can be interpreted as a non shift-invariant version of convolution

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Heat kernel

Heat equation

∆_{X} + ∂

∂t

u = 0

Solution given by heat operator
u(x,t) = (H^{t}u0)(x) =

Z

X

ht(x,y)u0(y)da(y)

Heat kernel ht(x,y) : solution at point x at time t with point heat source at y

Impulse responseof heat equation

### Heat kernel

Heat equation

∆_{X} + ∂

∂t

u = 0

Solution given by heat operator
u(x,t) = (H^{t}u0)(x) =

Z

X

ht(x,y)u0(y)da(y)

Heat kernel ht(x,y) : solution at point x at time t with point heat source at y

Impulse responseof heat equation

Intrinsic quantity – invariant to inelastic (isometric) bending

Heat operator can be interpreted as a non shift-invariant version of convolution

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Heat kernel

Heat equation

∆_{X} + ∂

∂t

u = 0

Solution given by heat operator
u(x,t) = (H^{t}u0)(x) =

Z

X

ht(x,y)u0(y)da(y)

Heat kernel ht(x,y) : solution at point x at time t with point heat source at y

Impulse responseof heat equation

### Heat kernel

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Probabilistic interpretation

Brownian motion x(t) starts at point x

x

x(t)

C

Pr(x(t)∈C) = Z

C

ht(x,y)da(y)

ht(x,y) =transition probability density fromx toy by random walk of length t

### Probabilistic interpretation

Brownian motion x(t) starts at point x

x

x(t)

C

Pr(x(t)∈C) = Z

C

ht(x,y)da(y)

ht(x,y) =transition probability density fromx toy by random walk of length t

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Probabilistic interpretation

Brownian motion x(t) starts at point x

x

x(t)

C

Pr(x(t)∈C) = Z

h (x,y)da(y)

### Spectral interpretation

Let ∆Xφi =λiφi be the Laplacian eigendecomposition

By spectral decomposition theorem ht(x,y) =X

i≥0

e^{−λ}^{i}^{t}φi(x)φi(y)

e^{−λt} =frequency response of heat operatorH^{t}

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Spectral interpretation

Let ∆Xφi =λiφi be the Laplacian eigendecomposition By spectral decomposition theorem

ht(x,y) =X

i≥0

e^{−λ}^{i}^{t}φi(x)φi(y)

e^{−λt} =frequency response of heat operatorH^{t}

### Spectral interpretation

Let ∆Xφi =λiφi be the Laplacian eigendecomposition By spectral decomposition theorem

ht(x,y) =X

i≥0

e^{−λ}^{i}^{t}φi(x)φi(y)

e^{−λt} =frequency response of heat operatorH^{t}

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Diffusion operators

General diffusion operator (Ku)(x) =

Z

X

k(x,y)u(y)da(y)

Diffusion kernel

k(x,y) =X

i≥0

K(λi)φi(x)φi(y)

K(λ) = frequency response (lowpass filter)
K^{t} is also a diffusion operator with response K^{t}(λ)
A scale space of operators {K^{t}}_{t≥0}

### Diffusion operators

General diffusion operator (Ku)(x) =

Z

X

k(x,y)u(y)da(y) Diffusion kernel

k(x,y) =X

i≥0

K(λi)φi(x)φi(y)

K(λ) = frequency response (lowpass filter)
K^{t} is also a diffusion operator with response K^{t}(λ)
A scale space of operators {K^{t}}_{t≥0}

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Diffusion operators

General diffusion operator (Ku)(x) =

Z

X

k(x,y)u(y)da(y) Diffusion kernel

k(x,y) =X

i≥0

K(λi)φi(x)φi(y)

K(λ) = frequency response (lowpass filter)

K^{t} is also a diffusion operator with response K^{t}(λ)
A scale space of operators {K^{t}}_{t≥0}

### Diffusion operators

General diffusion operator (Ku)(x) =

Z

X

k(x,y)u(y)da(y) Diffusion kernel

k(x,y) =X

i≥0

K(λi)φi(x)φi(y)

K(λ) = frequency response (lowpass filter)

K^{t} is also a diffusion operator with response K^{t}(λ)

A scale space of operators {K^{t}}_{t≥0}

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Diffusion operators

General diffusion operator (Ku)(x) =

Z

X

k(x,y)u(y)da(y) Diffusion kernel

k(x,y) =X

i≥0

K(λi)φi(x)φi(y)

K(λ) = frequency response (lowpass filter)

t t

### Properties of diffusion operators

Non-negativity: k(x,y)≥0

Symmetry: k(x,y) =k(y,x)

Positive semidefiniteness: for everyf(x),hKf,fi ≥0 Square integrability:

Z Z

k^{2}(x,y)da(x)da(y)<∞
Conservation:

Z

k(x,y)da(x) = 1

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Properties of diffusion operators

Non-negativity: k(x,y)≥0 Symmetry: k(x,y) =k(y,x)

Positive semidefiniteness: for everyf(x),hKf,fi ≥0 Square integrability:

Z Z

k^{2}(x,y)da(x)da(y)<∞
Conservation:

Z

k(x,y)da(x) = 1

### Properties of diffusion operators

Non-negativity: k(x,y)≥0 Symmetry: k(x,y) =k(y,x)

Positive semidefiniteness: for every f(x),hKf,fi ≥0

Square integrability: Z Z

k^{2}(x,y)da(x)da(y)<∞
Conservation:

Z

k(x,y)da(x) = 1

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Properties of diffusion operators

Non-negativity: k(x,y)≥0 Symmetry: k(x,y) =k(y,x)

Positive semidefiniteness: for every f(x),hKf,fi ≥0 Z Z

k(x,y)f(x)f(y)da(x)da(y)≥0

Square integrability: Z Z

k^{2}(x,y)da(x)da(y)<∞
Conservation:

Z

k(x,y)da(x) = 1

### Properties of diffusion operators

Non-negativity: k(x,y)≥0 Symmetry: k(x,y) =k(y,x)

Positive semidefiniteness: for every f(x),hKf,fi ≥0 Z Z

k(x,y)f(x)f(y)da(x)da(y)≥0 Square integrability:

Z Z

k^{2}(x,y)da(x)da(y)<∞

Conservation: Z

k(x,y)da(x) = 1

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Properties of diffusion operators

Non-negativity: k(x,y)≥0 Symmetry: k(x,y) =k(y,x)

Positive semidefiniteness: for every f(x),hKf,fi ≥0 Z Z

k(x,y)f(x)f(y)da(x)da(y)≥0 Square integrability:

Z Z

k^{2}(x,y)da(x)da(y)<∞
Conservation:

### Properties of diffusion operators

Non-negativity: k(x,y)≥0 Symmetry: k(x,y) =k(y,x)

Positive semidefiniteness: for every f(x),hKf,fi ≥0

Square integrability: Conservation:

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Properties of diffusion operators

Non-negativity: k(x,y)≥0 Symmetry: k(x,y) =k(y,x)

Positive semidefiniteness: K(λi)≥0

Square integrability: Conservation:

### Properties of diffusion operators

Non-negativity: k(x,y)≥0 Symmetry: k(x,y) =k(y,x)

Positive semidefiniteness: K(λi)≥0 Square integrability:

Z Z

k^{2}(x,y)da(x)da(y)<∞

Conservation:

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Properties of diffusion operators

Non-negativity: k(x,y)≥0 Symmetry: k(x,y) =k(y,x)

Positive semidefiniteness: K(λ_{i})≥0
Square integrability: by Parseval’s theorem

X

i≥0

K^{2}(λ_{i})<∞

Conservation:

### Properties of diffusion operators

Non-negativity: k(x,y)≥0 Symmetry: k(x,y) =k(y,x)

Positive semidefiniteness: K(λ_{i})≥0
Square integrability: by Parseval’s theorem

X

i≥0

K^{2}(λi)<∞
Conservation:

Z

k(x,y)da(x) = 1

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Properties of diffusion operators

Non-negativity: k(x,y)≥0 Symmetry: k(x,y) =k(y,x)

Positive semidefiniteness: K(λ_{i})≥0
Square integrability: by Parseval’s theorem

X

i≥0

K^{2}(λ_{i})<∞

Conservation: by Perron-Frobenius theorem λ_{i} ≤1

### Diffusion geometry

Family ofdiffusion metrics

d^{2}(x,y) = kk(x,·)−k(y,·)k^{2}_{L}2(X)

= Z

X

(k(x,z)−k(y,z))^{2}da(z)

Alternatively,

d^{2}(x,y) = kK(λ_{i})φ_{i}(x)−K(λ_{i})φ_{i}(y)k_{`}2

= X

i≥0

K^{2}(λi)(φi(x)−φi(y))^{2}
Equivalent due to Parseval’s theorem

{K^{t}}_{t≥0} define a scale space of metrics {dt}_{t≥0}

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Diffusion geometry

Family ofdiffusion metrics

d^{2}(x,y) = kk(x,·)−k(y,·)k^{2}_{L}2(X)

= Z

X

(k(x,z)−k(y,z))^{2}da(z)
Alternatively,

d^{2}(x,y) = kK(λ_{i})φ_{i}(x)−K(λ_{i})φ_{i}(y)k_{`}2

= X

i≥0

K^{2}(λi)(φi(x)−φi(y))^{2}

{K^{t}}_{t≥0} define a scale space of metrics {dt}_{t≥0}

### Diffusion geometry

Family ofdiffusion metrics

d^{2}(x,y) = kk(x,·)−k(y,·)k^{2}_{L}2(X)

= Z

X

(k(x,z)−k(y,z))^{2}da(z)
Alternatively,

d^{2}(x,y) = kK(λ_{i})φ_{i}(x)−K(λ_{i})φ_{i}(y)k_{`}2

= X

i≥0

K^{2}(λi)(φi(x)−φi(y))^{2}
Equivalent due to Parseval’s theorem

{K^{t}}t≥0 define a scale space of metrics {dt}t≥0

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Diffusion geometry

Heat diffusion metric
K(λ) =e^{−λt}

d_{t}^{2}(x,y) =
X

i≥0

e^{−2λ}^{i}^{t}(φi(x)−φi(y))^{2}

Commute time metric
K(λ) = ^{√}^{1}

λ

d^{2}(x,y) =

“Connectability” of x andy by random walks of length t

“Connectability” by random walks of any length

Scale invariant!

### Diffusion geometry

Heat diffusion metric
K(λ) =e^{−λt}

d_{t}^{2}(x,y) =
X

i≥0

e^{−2λ}^{i}^{t}(φi(x)−φi(y))^{2}

Commute time metric
K(λ) = ^{√}^{1}

λ

d^{2}(x,y) =

“Connectability” of x andy by random walks of length t

“Connectability” by random walks of any length

Scale invariant!

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Diffusion geometry

Heat diffusion metric
K(λ) =e^{−λt}

d_{t}^{2}(x,y) =
X

i≥0

e^{−2λ}^{i}^{t}(φi(x)−φi(y))^{2}

Commute time metric
K(λ) = ^{√}^{1}

λ

d^{2}(x,y) =

“Connectability” of x andy by random walks of length t

“Connectability” by random walks of any length

Scale invariant!

### Diffusion geometry

Heat diffusion metric
K(λ) =e^{−λt}

d_{t}^{2}(x,y) =
X

i≥0

e^{−2λ}^{i}^{t}(φi(x)−φi(y))^{2}

Commute time metric
K(λ) = ^{√}^{1}

λ

d^{2}(x,y) =

“Connectability” of x andy by random walks of length t

“Connectability” by random walks of any length

Scale invariant!

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Diffusion geometry

Heat diffusion metric
K(λ) =e^{−λt}

d_{t}^{2}(x,y) =
X

i≥0

e^{−2λ}^{i}^{t}(φi(x)−φi(y))^{2}

Commute time metric
K(λ) = ^{√}^{1}

λ

d^{2}(x,y) =
X

i≥1 1

λi(φ_{i}(x)−φ_{i}(y))^{2}

“Connectability” of x andy

“Connectability” by random walks of any length

Scale invariant!

### Diffusion geometry

Heat diffusion metric
K(λ) =e^{−λt}

d_{t}^{2}(x,y) =
X

i≥0

e^{−2λ}^{i}^{t}(φ_{i}(x)−φ_{i}(y))^{2}

Commute time metric
K(λ) = ^{√}^{1}

λ

d^{2}(x,y) =
1
2

Z ∞ 0

d_{t}^{2}(x,y)dt

“Connectability” of x andy by random walks of length t

“Connectability” by random walks of any length

Scale invariant!

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Diffusion geometry

Heat diffusion metric
K(λ) =e^{−λt}

d_{t}^{2}(x,y) =
X

i≥0

e^{−2λ}^{i}^{t}(φ_{i}(x)−φ_{i}(y))^{2}

Commute time metric
K(λ) = ^{√}^{1}

λ

d^{2}(x,y) =
1
2

Z ∞ 0

d_{t}^{2}(x,y)dt

“Connectability” of x andy by random walks of length t

“Connectability” by random walks of any length

Scale invariant!

### Diffusion geometry

Heat diffusion metric
K(λ) =e^{−λt}

d_{t}^{2}(x,y) =
X

i≥0

e^{−2λ}^{i}^{t}(φ_{i}(x)−φ_{i}(y))^{2}

Commute time metric
K(λ) = ^{√}^{1}

λ

d^{2}(x,y) =
1
2

Z ∞ 0

d_{t}^{2}(x,y)dt

“Connectability” of x andy by random walks of length t

“Connectability” by random walks of any length

Scale invariant!

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Diffusion maps

Map each pointx onX to asequence Φ(x) ={K(λi)φi(x)}i≥0

Φ(x) areembedding coordinatesof x in `^{2} (“R^{∞}”)
By Parseval’s theorem

kΦ(x)−Φ(y)k^{2}_{`}2 = X

i>0

K^{2}(λ_{i})(φ_{i}(x)−φ_{i}(y))^{2}

= d^{2}(x,y)

Diffusion distance is represented by Euclidean distancein embedding space

### Diffusion maps

Map each pointx onX to asequence Φ(x) ={K(λi)φi(x)}i≥0

Φ(x) are embedding coordinatesof x in `^{2} (“R^{∞}”)

By Parseval’s theorem

kΦ(x)−Φ(y)k^{2}_{`}2 = X

i>0

K^{2}(λ_{i})(φ_{i}(x)−φ_{i}(y))^{2}

= d^{2}(x,y)

Diffusion distance is represented by Euclidean distancein embedding space

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis

### Diffusion maps

Map each pointx onX to asequence Φ(x) ={K(λi)φi(x)}i≥0

Φ(x) are embedding coordinatesof x in `^{2} (“R^{∞}”)
By Parseval’s theorem

kΦ(x)−Φ(y)k^{2}_{`}2 = X

i>0

K^{2}(λi)(φi(x)−φi(y))^{2}

= d^{2}(x,y)

Diffusion distance is represented by Euclidean distancein embedding space

### Diffusion maps

Map each pointx onX to asequence Φ(x) ={K(λi)φi(x)}i≥0

Φ(x) are embedding coordinatesof x in `^{2} (“R^{∞}”)
By Parseval’s theorem

kΦ(x)−Φ(y)k^{2}_{`}2 = X

i>0

K^{2}(λi)(φi(x)−φi(y))^{2}

= d^{2}(x,y)

Diffusion distance is represented by Euclidean distancein embedding space

Alex Bronstein, Michael Bronstein, Umberto Castellani Spectral methods in shape analysis