Framework for Matching Shock Graphs

Deformation-based 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 least-cost path to deform A to B

The space of shapes and deformation paths is infinite-dimensional; has to be discretized to make the search for the least-cost 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 least-cost 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

Edit-distance algorithm

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

We have developed a polynomial-time edit-distance 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) re-label a character

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

Traditional tree edit-distance has two operations (i) delete an edge, (ii) re-label 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 degree-three nodes

Three types of Merge: combines two branches at a degree-two 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

Edit costs must be

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 minimum-cost 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

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

Significant for indexing into large databases