Oct. 22, 1999

BACK

• Review of the last presentation
• From Invariance to Stability
• Tasks: What are shape representations used for?
• Organization of the Shape Space
• Shock-Based Representation of Shapes and Images
• Recognition of Shape via Matching Shock Graphs: Graduated Assignment
• Tranformation-based Approach to Matching
• Shock Transitions
• Edit Distance Graph Matching
• Categorization, Shock Transitions, and Prototypes
• Open Questions: Need for psychophysics of shape similarity

• Discusss 2D first, since ingredients are now well-known, yet the theory has not quite come together.
• Assymmetry in the notion of similarity [Tversky]
  • 99 is similar to 100, but 100 is not viewed as similar to 99
  • circle with protrusion vs circle
  • tilted stand vs upright stand [Leyton]
  • skewed rectangle vs rectangle

  

• Need for prototypes with fuzzy neighborhoods to partition the shape space
• Need for a notion of scale, e.g., using the heat equation
• Need for a hierarchy of parts
• Need for describing shape with a limited set of parameters, i.e. , approximate each shape with a simpler one in a smaller space, e.g., based on special boundary features, like in the Attneave's cat example, using curvature extrema and a polygonal approximation

Attneave's cat

• What is missing from the following representations?

• Need for Models
  • fewer parameters, smaller space, reduce dimension of variability, make the recognition process managable.
  • Need for DENSE sampling of the shape space
  • Need for APPROPRIATE sampling: singularities are highly significant
• Traditional approches aim to build invariance in shape representation:
  • Eulidean Transformations
  • Affine Transformations
  • Projective Transformations
• Not quite enough! Vision poses scenrios with almost arbitrary transformations!
  • 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 disasterous!
• 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

• 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.
• Approch:
  • 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 suddens changes in the representation (transitions)
  • Only paths going through simpler shapes need to be considered

1. Skeletal Representation of Shapes:

• Focus of a large effort in computer vision
• Evidence from psychophyscis/neurophysiology for central representations of shape
• Medial Axis (Blum)
• Cordal Axes (Brady)
• PISA (Leyton)
• Full Symmetry Set (Giblin, Levine, Pizer, ....)
• Shock Set (Kimia et al)

2. Shock-Based Representation of Shapes:

• Dynamic flow of singularities formed from wave propagation from boundaries
• Four types of shocks
• Shock grammer: organization into shock groups
• Hierarchical organization of shock groups
• Shock group descrption: geometry and dynamics
• Growth model for shape
• Free-form shape design (Ilana Frankel)

3. Shock-Based Representation of Images:

• Figure-Ground Segmentation of Shape is DIFFICULT!
• Segmentation need not preceed recognition
• Extract skeletons directly from grey-scale images:
  • CORE (Pizer)
  • Symmtery Operators (Levine)
  • Full Symmetry Set (Wright et al)
• 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: IndicateTrue Symmetries
    • Semi-degenerate: Indicate Parts, Gaps
    • Degenerate: Indicate Parts, Gaps
  • Examples:
    • Parts, Broken Shapes and the Kanizsa triangle
    • Hand Image
  • Regular Shocks denote true symmtries, other require shock transformations
• Main point: recognition can preceed segmentation in this approah

* Previous work

• Yuille's FORMS (Buther Shop)
• Zucker et al: eigendecomposition 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 assiignment 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 funcational
  • 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-convenxity 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 toplogical coherence, but not link/node similarity
  • Implicit representation of deformations
    • Missing/extra nodes: Slack variable
    • Missing/extra links: Noise

• Characterizing Deformation Paths based on changes in the graph representation
  1. Continuous:
     • Fixed graph structure
     • Continuous changesin graph link and node attributes
     • Stretch/Shrink
     • Bend/Unbend
     • Protrude/Indent
  2. Sudden Changes: transitions
     • Sudden changes in the discrete graph representation

       
       

     • Changes in symmetry
     • Compose parts/partition

       
       

     • Close gaps / break outline

       
       

• The sudden changes break the shape space into regions
  • Need to zip-up at transitions
  • Main Point: Use these transitions as coordinates in the shape space

• Classify shock transitions (collaboration with Peter Giblin)
  • A1A3

    
    

  • A1^2: infinite velocity, zero accelerartion
  • A1^3 plus infinite velocity
  • A1_4

• Use of Edit Distance for String Matching
  • Edit Opertions
    • 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
• Adapation of edit distance algorithm to unrooted planar embedded trees (Collaboration with Philip Klein)
• Edit Operations
  • Splice (prune) A1A3

    
    

  • Merge1

    
    

  • Merge2 and Merge 3
  • Contract A1^4 Transition

    
    

• Results

• Aymmetric Reference
  •  Tilted rectangle --> a vertical one
  • protruded skewed rectangle--> unprotuded 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 proptotypes 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?
    • examplars?
    • examplars 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

• What is the perceptual cost of
  • strecthing/shrinking?
  • bending/unbending?
  • protruding/indenting?
  • compositing/partitioning?
• Are theses dimensions separable?

How should dimensions be combined?

• How are shape categories formed?
• Do shape transitions are more prototypical?

BACK