IBM, Watson Research Center, Oct. 28, 1999
SymmetryBased Shape Representations
Benjamin B. Kimia
Laboratory for Engineering Man/Machine
Systems (LEMS)
In Vision, simplified worlds can easily be more
complicated to analyze!
* Outline *
** End of Outline **
Back to Outline
*Fundamental Issues
in Shape Representation: from Invariance to Stability *

Shape Representations: Boundarybased or Regionbased

Boundarybased:

Polygonal Models [Romer, Attneave, ...], boundary partitioning
Attneave's cat

Fourier Descriptors [Zhan and Roskies]

Splines, higher order constructs

Curvature Models, etc.

Regionbased:

Superquadrics

Fourier Descriptors

Implicit Polynomials

Blum's skeletons

Both aspects must be captured, in qualitative sense
* Tasks and Shape Representations*

Recognition: Indexing into image databases based on shape

SHARP: what styles or types of
pottery does this fragment belong to?

FreeForm Shape Design

Solid Modeling, e.g., for Industrial Design

SHARP: Interactively form the
initial shape hypothesis

Morphing Shapes from one to another

Entertainment Industry

SHARP: Provide a language to
quantify and measure stylistic change

Segmentation/Grouping!

Recognition and Segmentation should not be separated

SHARP: Shape Recovery by evolving
initial shapes towards objects of interest
Back to Outline
* SymmetryBased Representations: SHOCKS
*

Medial Axis (MA): Locus of centers of maximal
(bitangent) circles [Blum], grouped into distinct branches.

Symmetry Set (SS): locus of centers of bitangent circles
[Bruce, Giblin, and Gibson].

Shock Set (SH): dynamic view, MA points with velocity (and
acceleration); grouped shock points have the same direction of
velocity.

Notation: order of contact

Collaborative work with PETER GIBLIN
Back to Outline
* Reconstruction of Shape from Shocks*

Reconstructing the Shape from the SHOCK GRAPH

Pointwise reconstruction needs

shock location

shock time

velocity vector
Main Theorem: The first and second order properties of the boundary
Back to Outline
* The Recovery of Shocks from Shapes
and Images *

Our approach (Huseyin Tek):

Form shocks from the propagation of orientation elements (edges)

Requires a network for propagation
of waves on a discrete grid (ISMM98)

Label shocks into three classes depending on whether the colliding
waves are rarefaction waves

Regular: Indicate
True Symmetries

Semidegenerate: Indicate
Parts, Gaps

Degenerate: Indicate Parts,
Gaps

Discrete Wave Front Propagation

Shock Propagation

Examples
Back to Outline
* Symmetry Map: An intermediate
representation for Perceptual Grouping *

Smoothing Shape Using the Splice Transform

Edge Grouping and Gap Completion

Removing Spurious Edge Elements

Occlusion Transform

Part Transform
Back to Outline
* Shape Comparison by Matching Shock
Graphs*

Previous work

Yuille's FORMS (Buther Shop)

Zucker et al.: eigen decomposition for shock graph
matching

Zhu: Stochastic Skeletons Geiger: Dynamic programming approach

Shock Graph Matching by Graduated Assignment (Daniel
Sharvit: SPIE97, CVPR98, JVIS98)

Adapted from Gold and Rangarajan's graduated assignment graph matching

Consider all permutations of node assignments

Pick the optimal correspondence by optimizing an energy functional

Energy represents goodness of match

Node similarity

Link similarity

Quadratic functional

Move from current match matrix to the optimal by a form of gradient
descent

Nonbinary (fuzzy) match matrix

Graduated nonconvexity to avoid local minima and converge to a
permutation

Update using gradient descent: equivalent to solving an assignment
problem

Examples and Results

Maintaining coherence of shape in the matching process

Quadratic energy functional: only pairwise consistency

Maximum clique approaches: treat topological coherence, but not
link/node similarity

Implicit representation of deformations

Missing/extra nodes: Slack variable

Missing/extra links: Noise
Back to Outline
* Transformationbased Approach to Matching *

Unidimensional sequences of shapes arise from stretching, bending,
protruding, etc.

Slightly more complex
collections defies organization into a small number of
dimensions

Shape Space has infinite
dimensions of variations

Goal: Gain an understanding of this structure, its
neighborhood relations, distances and similarities.

Approach:

Relate a shape to another by paths connecting them (thus, morphing one
to another)

Distance between two shapes is the cost of the optimal  least action
 path between them

Paths are sequences of continuous deformations punctuated by sudden
changes in the representation (transitions)

Only paths going through simpler shapes need to be considered

Main Point: Use these transitions as coordinates in
the shape space

Use of Edit Distance for String Matching

Edit Operations

Delete: TELEVIISION > TELEVISION

Insert: TELEVSION > TELEVISION

relabel: TELEVUSION > TELEVISION

Cost associated with each edit operation

Dynamic Programming approach to finding the least action (optimal)
path

Adaptation of edit distance algorithm to unrooted planar embedded trees
(Collaboration with Philip Klein SODA 99)

Edit Operations

Splice (prune) A1A3

Contact A1^4 (two flavors)

Merge (three flavors)

Results

Asymmetric Reference

Tilted rectangle > a vertical one

protruded skewed rectangle> unprotruded skewed rectangle

skewed rectangle > rectangle

rectangle > square

Matching two squarelike object requires a path going through a square

Main point:

shapes at transition become a "traffic hub"

transition shapes with higher degrees of degeneracy attract more
"traffic"

formation of prototypes from transition shapes?

who has ever seen a circle?
* Image
Indexing: Need for Categorization *
Successful Image Retrieval requires Efficient Access

A large number of objects introduces organizational complexities

Research Questions (work with Ana Popescu)

How can we form categories/clusters from metric data, d(x,y)?

How can formed categories be represented?

prototypes?

examples?

examples with outliers?

How can hierarchies of categories be formed for efficient indexing and
search?

Clustering Techniques:

Nearest neighbor search (KD trees, VP trees, etc.)

Minimal Spanning Trees

Physical Analogy: Granular Magnetic Model

Currently, we are constructing a very large database of shapes
* SymmetryBased Representations for
Segmentation*
Back to Outline
* 3D Representations of Shape *
Frederic F. Leymarie
*Applications: Digital Archaeology *
Last update: Oct. 28, 1999