IBM, Watson Research Center, Oct. 28, 1999

Symmetry-Based Shape Representations

• Fundamental Issues in Shape Representation: from Invariance to Stability
• Tasks and Shape Representations
• Symmetry-Based Representations: SHOCKS
• Reconstruction of Shape from Shocks
• The recovery of shocks from shapes and Images
• Symmetry Map: An intermediate representation for perceptual grouping
• Shape Comparison by Matching Shock Graphs
• Transformation-based Approach to Matching: Edit Distance
• Categorization and Prototypes
• Symmetry-based Representation for Segmentation
• 3D Representations of Shape
• Applications: Digital Archaeology

• Shape Representations: Boundary-based or Region-based

• Boundary-based:
  • Polygonal Models [Romer, Attneave, ...], boundary partitioning

  Attneave's cat

  • Fourier Descriptors [Zhan and Roskies]
  • Splines, higher order constructs
  • Curvature Models, etc.
• Region-based:
  • Superquadrics
  • Fourier Descriptors
  • Implicit Polynomials
  • Blum's skeletons
• Both aspects must be captured, in qualitative sense

• Need for Models
  • fewer parameters, smaller space, reduce dimension of variability, make the recognition process manageable.
  • Need for DENSE sampling of the shape space
  • Need for APPROPRIATE sampling: singularities are highly significant
• Traditional approaches aim to build invariance in shape representation:
  • Euclidean Transformations
  • Affine Transformations
  • Projective Transformations
• Not quite enough! Vision poses scenarios with almost arbitrary transformations! The shape space is rich in transformation!
  • Partial Occlusion
  • Split Occlusion, Fragments
  • Boundary Removal: Gaps
  • Articulation

  

  • Changes in Viewpoint

  

  • Spurious Edge Elements
  • Boundary Noise

  

  • ETC!
• Need: Representation must reflect the desired shape topology (geography), i.e., as the shape changes continuously (and arbitrarily) so should the representation; any discontinuous jumps will prove disastrous!
• Refer to this as the STABILITY of representation with almost arbitrary deformations

  1) Projective Transformations --> Much larger space of deformations
  2) Invariance --> Stability

  Back to Outline

• Recognition: Indexing into image databases based on shape
  • SHARP: what styles or types of pottery does this fragment belong to?
• Free-Form 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

• 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

• This leads to the notion of a SHOCK GRAPH

  

  • Recognition using Shock Graphs

  

• 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

• 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
    • Semi-degenerate: Indicate Parts, Gaps
    • Degenerate: Indicate Parts, Gaps
• Discrete Wave Front Propagation
• Shock Propagation
• Examples

• Smoothing Shape Using the Splice Transform
  • Example 1 (L shape)
  • Example 2 (Noisy Square)
• Edge Grouping and Gap Completion
  • Rectangle with gaps
• Removing Spurious Edge Elements
  • Rectangle With Noise Edges
• Occlusion Transform
  • Occluded Rectangle
• Part Transform
  • Rectangle With a Part

• 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
  • Two example graphs
  • MATCH matrix
  • Slack variable for extra/missing nodes
• 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
  • Non-binary (fuzzy) match matrix
  • Graduated non-convexity 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

• Uni-dimensional 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 square-like 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?

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

• Link

• Link

Last update: Oct. 28, 1999