### Computational metric geometry

```Michael Bronstein Computational metric geometry
Computational metric geometry
Michael Bronstein
Department of Computer Science
Technion – Israel Institute of Technology
1
2
Michael Bronstein Computational metric geometry
What is metric geometry?
?
Metric
space
Similarity of
metric spaces
Metric
representation
3
Michael Bronstein Computational metric geometry
information retrieval
object detection
shape analysis
inverse problems
Similarity
medical imaging
4
Michael Bronstein Computational metric geometry
Non-rigid world from macro to nano
Organs
Nanomachines
Proteins
Microorganisms
Animals
5
Michael Bronstein Computational metric geometry
Rock, paper, scissors
Rock
Scissors
Paper
6
Michael Bronstein Computational metric geometry
Rock, paper, scissors
Hands
Rock
Scissors
Paper
Michael Bronstein Analysis of non-rigid shapes
Invariant similarity
Similarity
Transformation
7
8
Michael Bronstein Computational metric geometry
Metric model

Shape
Similarity
metric space
Distance between metric
spaces
and
Invariance
isometry w.r.t.
.
9
Michael Bronstein Computational metric geometry
Isometry
Two metric spaces
and
are isometric if there exists a
bijective distance preserving map
and
map
which is

distance preserving

surjective
‘‘
are -isometric if there exists a
‘‘
Two metric spaces
such that
-similar = -isometric
In which metric?
10
Michael Bronstein Computational metric geometry
Examples of metrics
Euclidean
Geodesic
Diffusion
11
Michael Bronstein Computational metric geometry
Rigid similarity
Isometry between metric spaces
Congruence
Unknown correspondence!
Min Hausdorff distance over
Euclidean isometries
12
Michael Bronstein Computational metric geometry
Non-rigid similarity
Rigid similarity
Non-rigid similarity
Part of same metric space
Different metric spaces
SOLUTION: Find a representation of
in a common metric space
and
Michael Bronstein Computational metric geometry
Canonical forms
Compare
canonical
forms as
rigid shapes
Compute
canonical
forms
Non-rigid shape similarity
= Rigid similarity of canonical forms
13
Michael Bronstein Computational metric geometry
Multidimensional scaling
SF
7200
4000
1630
Paris
NY
TA
Rio
Find a configuration of points in the plane best representing
distances between the cities
14
15
Michael Bronstein Computational metric geometry
Multidimensional scaling
Best possible embedding with minimum distortion
Non-linear non-convex optimization problem in
variables
16
Michael Bronstein Computational metric geometry
Multigrid MDS
Fine grid
Solution
Decimate
Interpolate
Relax
Coarse grid
B et al. 2005
Improved solution
17
Michael Bronstein Computational metric geometry
Multigrid MDS
Execution time (sec)
Multigrid MDS
Stress
Standard MDS
Complexity (MFLOPs)
B et al. 2005, 2006
Michael Bronstein Computational metric geometry
Examples of canonical forms
18
Michael Bronstein Computational metric geometry
Embedding distortion limits discriminative power!
19
20
Michael Bronstein Computational metric geometry
Canonical forms, revisited
Min distortion
embedding
Min distortion
embedding
Fix
some
metric
space
Compute
Computecanonical
Hausdorff
forms
distance
(defined
between
up
tocanonical
an isometry
forms
in )
No fixed (data-independent) embedding space will give
distortion-less canonical forms!
21
Michael Bronstein Computational metric geometry
Metric coupling
Isometric embedding
Isometric embedding
Disjoint union
?
?
How to choose the metric?
Michael Bronstein Computational metric geometry
Gromov-Hausdorff distance
Find the smallest possible metric
Gromov-Hausdorff distance
Distance between metric spaces (how isometric two spaces are)
Generalization of the Hausdorff distance
Gromov 1981
22
23
Numerical geometry of non-rigid shapes A journey to non-rigid world
Canonical forms
Gromov-Hausdorff
Fixed embedding space
Optimal data-dependent
embedding space
Approximate metric
(error dependent on the data)
Metric on equivalence classes of
isometric shapes
-isometric
-isometric
Consistent to sampling
for
24
Michael Bronstein Computational metric geometry
Gromov-Hausdorff distance
Theorem: for compact spaces,
is a correspondence satisfying
for every
there exists
s.t.
for every
there exists
s.t.
Optimization over all possible correspondences is NP-hard problem!
Gromov 1981
Michael Bronstein Computational metric geometry
Multidimensional scaling
Best possible embedding with minimum distortion
25
Michael Bronstein Computational metric geometry
26
Generalized multidimensional scaling
Best possible embedding with minimum distortion
 Geodesic distances have no closed-form expression
 No global representation for optimization variables
 How to perform optimization on a manifold?
B et al. 2006
Michael Bronstein Computational metric geometry
GMDS: some technical details
 No global system of coordinates
Use local barycentric coordinates
 No closed-form distances
Interpolate distances from those
pre-computed on the mesh
 How to perform optimization?
Perform path unfolding to go across triangles
B et al. 2005
27
28
Michael Bronstein Computational metric geometry
Canonical forms
(MDS based on 500 points)
BBK, SIAM J. Sci. Comp 2006
Gromov-Hausdorff distance
(GMDS based on 50 points)
Numerical Geometry of Non-Rigid Shapes Expression-invariant face recognition
Application to face recognition
x
x’

Euclidean metric
y
y’
29
Numerical Geometry of Non-Rigid Shapes Expression-invariant face recognition
Application to face recognition
x
x’

Distance
distortion
distribution
Geodesic
metric
y
y’
30
Michael Bronstein Computational metric geometry
31
32
Michael Bronstein Computational metric geometry
Eikonal vs heat equation
Boundary conditions:
Viscosity solution: arrival time
(geodesic distance from source)
Kimmel & Sethian 1998
Weber, Devir, B2, Kimmel 2008
Initial conditions:
Solution
: heat
distribution at time t
Michael Bronstein Computational metric geometry: a new tool in image sciences
Heat equation on manifolds
1D
3D
33
Michael Bronstein Computational metric geometry: a new tool in image sciences
Heat equation on manifolds
1D
3D
Heat kernel
34
Michael Bronstein Computational metric geometry: a new tool in image sciences
Heat equation on manifolds
1D
3D
Heat kernel
“Convolution”
35
Michael Bronstein Computational metric geometry
Diffusion distance
“Connectivity rate” from
to
by paths of length
 Small if there are many paths
 Large if there are a few paths
Geodesic = minimum-length path
Diffusion distance = “average” length path (less sensitive to bottlenecks)
Berard, Besson, Gallot, 1994; Coifman et al. PNAS 2005
36
37
Michael Bronstein Computational metric geometry
Invariance: Euclidean metric
Rigid
Wang, B, Paragios 2010
Scale
Inelastic
Topology
38
Michael Bronstein Computational metric geometry
Invariance: geodesic metric
Rigid
Wang, B, Paragios 2010
Scale
Inelastic
Topology
39
Michael Bronstein Computational metric geometry
Invariance: diffusion metric
Rigid
Wang, B, Paragios 2010
Scale
Inelastic
Topology
Michael Bronstein Computational metric geometry
40
41
Michael Bronstein Computational metric geometry
information retrieval
object detection
shape analysis
inverse problems
Similarity
medical imaging
42
Michael Bronstein Computational metric geometry
Metric learning
“Similar”
“Dissimilar”
Generalization
Data space
Sampling of
Metric learning:
Representation space
on training set
43
Michael Bronstein Computational metric geometry
Similarity-sensitive hashing
0001
0011
0100
0111
1111
Data space
Shakhnarovich 2005
B2, Kimmel 2010; Strecha, B, Fua 2010
Hamming space
44
Michael Bronstein Computational metric geometry
Video copy detection
Lightsaber
Luke vs Vader – Starwars classic
Original copy
Pirated copy
45
Michael Bronstein Computational metric geometry
Mutation
Biological DNA
“Video DNA”
So, what do you
think?
C A A T T A
G C
C A
G C C
Substitution
B2, Kimmel 2010
In/Del
Substitution In/Del
46
Michael Bronstein Computational metric geometry
Mutation-invariant metric
T
So, what do you think?
positive
So, what do you think?
So, what do you think?
negative
So, what do you think?
B2, Kimmel 2010
Michael Bronstein Computational metric geometry: a new tool in image sciences
Video DNA alignment
Gap
Pairwise cost
Optimal alignment = minimum-cost
Gap continuation path
Gap
 Dynamic programming sequence alignment with gaps to account
for In/Del mutations (Smith-WATerman algorithm)
 Learned mutation-invariant pairwise matching cost
B2, Kimmel 2010
47
Michael Bronstein Computational metric geometry
B2, Kimmel 2010
48
Michael Bronstein Computational metric geometry
B2, Kimmel 2010
49
50
Michael Bronstein Computational metric geometry
Summary
0001
1001
1111
0111
1110
MDS
Metric space
Gromov-Hausdorff
Object similarity is
also
distance
a metric
+ GMDS
space
Metric
choice=invariance
Examples
of similarity
(metric sampling)
Metric
learning
Michael Bronstein Computational metric geometry
Thank you
51
```