Symmetry Maps and Transforms

For

Perceptual Grouping and Object Recognition

Benjamin B. Kimia

Brown Univeristy

In collaboration with
               Peter Giblin     University of Liverpool
                Philip Klein     Brown University
                Huseyin Tek    Siemens Corporate Research

Graduate Students
              Thomas Sebastian
                Frederic Leymarie
                Marc Johannes
                Christopher Cyr
                Srikanta Tirthapura
                Daniel Sharvit

Overview

Q: What sort intermediate models can mediate between pixel-bound edge/region maps and pixel-free object models?

Q: What are suitable representations for the shape of object models

Q: Segmentation and Recognition: Distinct Modules or Integrated Processes?

o Curves serve as an implicit/explicit intermediate representation

o Zucker et al Relaxation labeling

o Williams et al Completion Field

o Shashua & Ullman Saliency networks

o …

o Elastica for gap completion [Mumford], Euler Spiral [Kimia et al]

o Symmetry Maps Augment this picture

o Represent a pair of curve segments

o Individual curve geometry AND their relative spatial arrangement

o A skeletal segment as glue between a pair of (grouped) edge elements

o Joint continuity across occlusion/gaps

o Joint matching for recognition

• Two major challenges must be met
1. The instability of the skeletal representation

2 . The medial-axis is typically defined for segmented shape

• Figure-Ground segmentation is a difficult and unsolved problem
• General theme:
• segmentation and recognition should not be separated
• Skeletons from gray-scale images
• Tari&Shah: edge strength functional
• Pizer, Kelly&Levine, Wright et.al.: retrieve the full symmetry set: too many branches to present an advantge over the edge map itself

• skeletons are distorted drastically due to gaps, occlusions, spurious elements, etc.
• Recognize the affinity of the edge map of a shape and the shape itself
• Need for inter-changability of edge maps and shape representations
• Allow the “shape space” to include edge maps!

I. A Theoretical Examination of the Geometry of the Medical Axis/Shock Set

• Classification of Medial Axis/Shock Set Points and their local form [Giblin&Kimia, ICCV00]
• Transitions of the Medical Axis/Shock Set: Dealing with Instability [Giblin&Kimia, ICCV00]
• Reconstruction from the Shock Set [Giblin&Kimia, CVPR99]
• 3D Skeletal Geometry [Giblin&Kimia, CVPR00]

II. Shock Detection and Organization

• Separation of Detection and Regularization [Tek&Kimia, ICCV00]
• Our wave propagation approach combines two approaches:
• Grassfire/level set/curve evolution PDE approach
• Computational Geometry/ Voronoi Diagram approach
• Not only closed shapes, but also curve segments and junctions
• Analytically exact
• Organizes shocks into a hierarchical graph (directed planar graph)
• Modifications due to changes are straightforward: additional wave propagations
• Computationally very efficient
• 3D shock scaffold [Leymarie&Kimia, IWVF01 submitted]

III. Perceptual Grouping and Object Recognition under one roof

• Symmetry Map: Shock Graph of Edge Maps
• Intermediate-level representation mediating between pixel-bound edge maps and pixel-free object descriptions
•  Symmetry Transform [Tek&Kimia:CVPR99]
• Implement Perceptual Grouping Operations
• Basic building block of a deformation sequence
•  Object Recognition [Klein, Sebastian & Kimia, SODA 00, SODA 01]
• Seek the least action path in the space of all deformation paths  morphing a shape to another
• Cost of optimal path is shape dissimilarity
• Novel notion of shape prototype
• Recognition, indexing into image databases
• Allows for bottom-up and top-down interaction between the recognition and edge detection modules
• Perceptual Grouping
• Special case of recognition: not a pair, but a deformation path eminating from a single object
• Seek the optimal simplifying deformation path to “good form”

---

---

---

I.  Theoretical examination of geometry of the medial axis/shock set

• Medial axis (MA) [Blum]
• locus of maximal inscribed balls: skeletal graph
• 
• Shock set (SH) [Kimia:PhD 90]
• attach a sense of flow to each point
• 
  animation
• assigning a direction to each segment leads to a refinement of the skeletal graph
• perceptually meaningful segments (nodes)

o Applicable to an edge map by re-interpreting “maximal” circles

Q: How many types of Medial Axis / Shock Set points? What is their local geometry? [Giblin:Kimia:ICCV90]

• Contact with circles (spheres in 3D)

·

Symmetry Set (SS) 

The medial axis is a subset of the symmetry set

Resort to the local form of the symmetry set

• : An ordinary smooth point of the symmetry set, where the bitangent circle has ordinary contact at two places on the curve
• : An endpoint of the symmetry set, where the center of the circle is the center of curvature at a vertex (stationary point of curvature)
• : A cusp on the symmetry set, where the center is the center of curvature at one of the tangency points
• /:  the symmetry set has a crossing which is the center of two circles of different radii both bitangent to the curve
• : A triple crossing on the symmetry set, brought about by a circle tangent to the curve in three places.

Medial Axis (MA)

• : Curve segment
• : Isolated point
• : Isolated point

Shock Set (SH)

• is augmented with -J, where J =
• 1 means monotonic flow, both in and out
• 2 means outward flow in both directions
• 4 means inward flow in both directions
• 3 means infinitely fast flow: not generic
• -1     points form a curve
• -2     initial shock flow
• -4     terminal shock flow
• initial shock flow
• -1     both initial and terminal (junction)
• -4     terminal shock flow

Classification of 3D MA/SH

• 5 types
• sheets
• ridge curves
• "generalized axis" curves, geon-like descriptors
• points where 4  curves meet
• points where  and  curves meet
• Shock Scaffold
• Nodes  , 
• Links , 
• Hyperlinks 
• Reduce dimensionality in
• representation
• computation
• Examples (Gaile’s Face, Petra pot, Cube)

---

Q: What happens to the MA/SH as the shape is deformed?

---

• Typically, the locus changes smoothly and so does the radius function.

• However, near certain shapes sudden changes can occur.

§ Noted by Yuille&Zhu, Gieger

· Are there other instabilities?

• Transitions of the symmetry set/MA/SH
• Use the classification of SS transitions [Bruce and Giblin] to derive MA/SH transitions

• Transitions of the symmetry set occurring in a generic one-parameter family of curve deformations [Bruce:Giblin]. Transitions can occur either in the direction of the arrows, left to right, or in the reverse direction, right to left.  Note:  In this figure, the dashed line is the {\em evolute} (locus of centers of curvature) of the deforming curve, which is not shown. The medial axis will be a part of the symmetry set, and this part will never include the cusps on the symmetry set. The MA can come to an end only at endpoints of the symmetry set or at triple crossing points. Thus only $A_1^4$ and $A_1A_3$ can actually occur on the medial axis, but $A_4$ and $A_2^2$ `nib' transitions on the symmetry set can have later repercussions for the medial axis.
• First case: transition: of four points which is “visible”?

• What are the allowable directions of flow?

• Shock Transitions at

Shock Transitions

o Examine the first of these in further detail: the creation of a protrusion on an ellipse

o Each protrusion creates an indentation on the other side: examine an indentation on an ellipse

---

Q: Can shapes be reconstructed from their shock graphs?

---

• Reconstruction of the shape (edge map) from the shock set
• points
• shock point, tangent, velocity and time of formation give two boundary characteristic points and their tangents
• shock curvature and acceleration give boundary curvatures at characteristic points
• derivatives of curvature and acceleration give boundary curvature derivatives
• shock segments are modeled intrinsically by curvature and acceleration functions
• points
• shock point, tangent and time of formation give the characteristic boundary point and its tangent (velocity = 1)
• shock curvatures relate to higher order curvature derivatives of the boundary.
• points
• bringing together 3 branches smoothly implies redundancy. Which subset of three "geometries" and three "dynamics" is sufficient?
• two geometries and one dynamics is sufficient but is not symmetric
• three geometries is not sufficient: curvature constraint
• three dynamics is not sufficient: acceleration constraint
• even parts of curvature and acceleration are free while the odd parts are determined!
• segregation of intrinsic shape information from extrinsic parameters (size, position, orientation)
• progress towards modeling shape by interactively manipulating the shock set

o FINALLY: The shock graph also store the propagated intensities.

o Refer to each shock segment with associated intensity functions as “Shape Fragments”

o A step closer to organizing the image as a collection of objects

The reconstruction of shape from a shock graph as presented here. Nodes contain first order (tangent and speed) properties, while links contain second-order properties (curvature and acceleration). Note that the reconstruction allows selective interaction with pieces of shape, e.g. for bending the shape or removing a part.

---

---

---

II. Shock Dectection and Organization

---

---

---

• Traditional approaches often include regularization of the skeleton in the detection process

• Siddiqi&Kimia:CVPR96, Siddiqi:CVPR2000, Zhu:etal
• unpredictable results and lack of connectivity, robustness with translation, rotation, and scaling
• Alternatively, pruning methods are employed, but these round corners and other salient features
• Ogniewicz&Kubler, Shaked&Bruckstein, Ho&Dyer

• Curve evolution approach [Kimia:Phd90, Siddiqi:Kimia:CVPR96]
• subpixel accurate and robust estimates: ENO schemes and Shock Grammar
• add diffusion to remove branches due to "noise"
• can lead to disconnected skeletons; need to relate pre-diffusion topology
• Mainly, however, curve evolution does not deal with junctions and curve segments prominent in edge maps
• Computational geometry approach
• focuses on analytically accurate results
• Voronoi Diagrams for points  [Ogniewicz:etal]
• recent research on VD of curves objects
• approach: compute bisector curves for every pair of geometric models and trim
• trimming very expensive [Faroukhi:etal]

• Wave propagation combines these approaches
• Shock propagation (no grid): Lagrangian propagation
• a set of geometrically described curve segments (circular arcs)
• Observe that many bisectors should never be considered!
• Observe that if we identify all shock sources, propagation from these to shock sinks should recover all shocks

• Discrete wave propagation (grid): Eulerian propagation
• Observe that not all initial shock sources actually lead to propagation. (few do!)
• Traditional Distance Transform propagates just distances. Propagate geometric models
• Use discrete grid propagation to signal when analytic computations should take place, avoid at other times

• The above wavefront algorithm is almost, but not totally error-free
• The region of influence of a boundary segment becomes too small
• it does not contain any discrete point

• These errors are independent of boundary representation.

Solution: shockwave propagation: secondary grid (dynamic) to determine influence zones

Our Approach:

o Detect all shock sources:

§ second order shocks centers of bitangent circles whose  radius grows in both directions animation

§ curvature extrema animation

§ contact shockwaves

·

§ junctions, centers of tritangent circles,  where two incoming branches meet with one outgoing shock branch

o Propagate these shocks along their bisector curves

§ image (edge map) consist of  N free form curve segments

· geometric model

· two end points

· circular arcs, conic arcs, etc.

§ Distance function from each model can be analytically computed as un(x,y)

§ The bisector curve between two geometric model, gn and gm can be computed by

§ un(x,y)-um(x,y) = 0

o Shockwaves and discrete waves are propagated simultaneously.

o Single source animation

Examples:

animation

animation

• Combined discrete shock wave propagation is shown to give analytically accurate results
• Very efficient: nearly optimal
• Shock organization
• Shocks are organized as segments
• Shocks segments are organized as a graph
• Works both with closed shapes and unorganized cloud of points/curve segments
• Resulting map is called the symmetry map
• Symmetry map can be transformed by additional wave propagation

---

---

III. Perceptual Grouping and Object Recognition under One Roof

---

---

III.1 Object Recognition

---

Q: How to relate two shapes? What is a good measure of shape similarity?

Previous Approaches using skeleton matching:

Yuille and Zhu: FORMS

Geiger tree matching

Siddiqi etal, eigenvalues of the match matrix

Sharvit etal, graduated assignment

Current Approach:

• The Shape Space: The collection of all “shapes” with the neighborhood topology determined by some class of local deformations

• Two shapes can be related by an arbitrary defomation which continuously morphs the initial shape A until it eventually equals the second shape B

• Numerous paths: infinite variations in paths, very high dimensional space
• Critical Issue 1: How to search this enormous space? How to discretize this space?
• We are interested in the "best" or least action path
• Shape similarity = cost of least action path
• Critical Issue 2: How to measure the similarity for an infinitesimal change along a path?
• Observe that
• Shapes with the same shock graph topology are rather similar: Slight changes in the boundary lead to slight changes in the shock graph
• Shapes with different shock graph topology are similar if and only if they can be related by a shock transition: Slight changes in the boundary lead to large changes in shock graph topology only near a transition

• Thus,
• Changes in the shape when the shock graph topology remains constant can be measured by comparing shock graph attributes (curvature and acceleration)

• Changes in the shape when the shock graph topology is altered is the sum of the change of each shape to the common transition, but no cost for crossing the transition itself

• This suggests annotating each deformation path by a sequence of transitions

• Definition: A shape cell is the collection of shapes with the same shock graph topology

• Definition: A deformation path bundle is the set of deformation paths that undergo the same set of shock transitions between two shape cells
• Observe that not all deformation paths are of interest!

• We consider only paths of increasing simplicity for each shape to a common shape:
• The transition shapes are considered to be simpler than shapes in their vicinity

A Discretization of the Shape Space

• Generate all shapes from A to B by considering the deformations which cause a simplifying transition sequence for A and for B, and seek a common shape cell C

• The operation of deforming a shape (edge map) to one with a shock transition is a symmetry transform (described below).
• The cost of this operation is defined via a physical model penalizing stretching and bending (generalization of curve matching [Cohen:etal, Younes, Tagare, Sebastian:etal]
• This cost is then cast in the language of shock graph attributes within each shape cell
• The total cost of each path is the sum of the costs between each pair of adjacent transitions

• Critical Issue 3: This space is still fairly large! How to find the least action path in an efficient and robust manner.
• Collaboration with Philip Klein: development of a polynomial time algorithm, the adaptation of "edit distance" generalized from string matching to graph matching.
• insert: HELO --> HELLO
• modify: JELLO --> HELLO
• delete: HELLOW --> HELLO
• There is some previous work on Tree Edit Distance [Zhang and Shasha]
• Edit Operations
• relabel an edge
• contract end edge
• unconstruct an edge
• Shape comparison requires other edit operations
• incorporate merge in the edit matching
• comparison of rooted trees
• Extension to unrooted trees
• reduce running time
• reduce storage requirement
• Assignment of Edit costs
• The cost of deforming two shock segments is given by the cost of matching the corresponding boundary segments (joint curve matching)

• The other costs are computed as limiting cases of the deform cost

Example edit sequences

• fish-to-fish

• dog-to-cat

• plane-to-plane

Matching Results

Shape classification table

Stability of the match with visual transformations

Indexing results

• Our edit operations are the symmetry transforms

---

Symmetry Transforms

---

• Symmetry transforms relates shapes on either side of the transition with the transition shape itself.

• Deform transform: is the operation of altering the symmetries to relate two object within the same cell. Only attributes are affected. This is the only symmetry transform that does not alter the shock graph topology
• Splice transform: This transform removes a branch from the shock graph by replacing the boundary with a circular arc

• Symmetrize transform: contract edge

• Merge Transform: merge two nodes

• Loop Transform: removes loop

• Gap/part transform: This transform removes a degenerate shock branch and smooths the joining branch by connecting the corresponding end points (by an Euler spiral which has no curvature extrema)

Perceptual Grouping

• Object Recognition:  Find optimal path connecting two shapes
• Perceptual Grouping:  First shape is Given, second shape is a Floating Target
• If a sequence of operations is of low cost, but given a simplified object, apply the sequence.

                - Optimize paths to a “good form”
                - Currently: simply gradient descent.

• Sequences of splices smoothes boundary

                - Note that course scale corner is recovered.

L Shape
Noisy Corner

• Edge grouping and gap completion

Rectangle with Gaps
Dot-grouping

• Removing spurious edge elements

Rectangle with Noisy Edges
Occluded Rectangle
Rectangle with a Part

Conclusion

§ The symmetry map as an intermediate representation for images (includes both geometry and intensity)

§ Analysis of the local form of MA/SH allows for analytically accurate and efficient shock detection

§ Analysis of the reconstruction of shape from shocks; shape modeling

§ Analysis of the transitions of the MA/SH lead to edit operations for recognition and symmetry transforms for perceptual grouping

§ Characterizing deformation paths by a sequence of transitions and a graph edit distance algorithm leads to the efficient computation of the optimal path

§ Object recognition and perceptual grouping as finding least action paths in the shape space

§ Generalizations to 3D