Framework for Matching Shock Graphs
Deformationbased Distance between shapes

Shape space: Collection
of all shapes

Shape is a point in this space

Shape deformation sequence is a path in this space

Distance between two shapes A and B is defined as
the leastcost path
to deform A to B

The space of shapes and deformation paths is infinitedimensional; has
to be discretized to make the search for the leastcost path practical

This is done using three measures
Partitioning the shape space

In most cases when a shape is deformed slightly, shock graph topology remains
unchanged; only the attributes of the links change

This describes a local neighborhood for most shapes

Equivalence based on shock graph topology defines
a shape cell

At certain shapes, however, small changes in shape can lead to abrupt changes
in the shock graph topology

These transition shapes shapes are
the instabilities of the shock graph/ medial axis and formally enumerated
and classified [Giblin:Kimia:ICCV99]

At transition shapes the local shape
space topology breaks down

The transitions must be explicitly embedded in the definition of a neighborhood
Defining a Deformation Path Bundle

Define an equivalence class: A shape
deformation bundle is the collection of
deformation paths between two shapes which pass through the same set of
transitions

This grouping of a set of deformation paths is a
discretization of space of deformation paths
Avoiding unnecessarily venturing into
complexity

A shape A can be deformed to a shape B through a
large circuitous route!

Deformation paths that first introduce and then remove
complexity are excluded from the search

Each deformation path from A to B, is replaced with
a composition: a pair of simplifying deformation
paths from A and B to a simpler shape
C

The leastcost path is obtained by searching all
pairs of simplifying deformation paths

Deformation of a shape to its adjacent simpler transition
shape is done via a shock transition

This corresponds to an edit
operation in the graph domain
Editdistance algorithm

Even with the above "discretizations", there are
numerous deformation paths to consider

We have developed a polynomialtime
editdistance algorithm for comparing
unrooted trees [Klein:etal:SODA1999, Klein:etal:SODA2001]

Edit distance originally used for comparing character
strings [Wagner:Fischer]

String edit distance has two edit operations are
(i)
delete a character, (ii) relabel a character

Extended to matching rooted trees [Tai, Zhang:Shasha]

Traditional tree editdistance has two operations
(i)
delete an edge, (ii) relabel an edge

Four groups of edit operations are needed to compare
shock graphs and are derived from shock transitions [Giblin:Kimia]

Splice: deletes
a shock branch and merges the remaining two branches

Two types of Contract:
deletes a shock branch connecting two degreethree nodes

Three types of Merge:
combines two branches at a degreetwo node

Deform: relates
two shapes in the same shape cell (same shock graph topology but different
attributes) by changing the shock graph attributes

Globally optimal sequence of transitions (edits)
is computed using dynamic programming in polynomial time
Assigning costs to edit operations

consistent with each other

and consistent with our perceptual metrics of similarity

Our Approach: The cost of all edits are defined as
limits of the deform costs

Deform cost relies on the exension of a metric developed
to compare curves [Sebastian:Klein:Kimia MMBIA2000, IWVF2001]

Finds the minimumcost deformation of one curve to
another

Cost is defined as the sum of stretching and
bending energies [Cohen:ECCV92,Younes:JAM96]

Measured by length and curvature differences

Introduces the notion of an alignment curve to ensure
symmetric treatment of the two curves

Each shock segment represents a pair of segments
on the boundary of the shape

Comparing shock edges can be viewed as a joint
curve matching problem

Deform cost is measured as a sum of

Local length and curvature differences of the two
boundary segments

Relative pose of the boundary segments

The distance between two shapes A and B, D(A, B), is defined
as sum of cost of edits in
the optimal edit sequence
An edit sequence
A more complicated edit sequence

Proposition: The distance measure D(A,
B) is a metric

Significant for indexing into large databases