Contents

Forewords

Shape modeling is to represent generic object geometry by a number of models which account for the regularity and variablity of natural objects. Shape modeling is the fundation for object recognition under change of pose, deformation, and varying lighting coditions. However, this is an extremely hard problem, and most of the mathematical studies appear to be totally irrelevant to natural object shape description.

Key questions are:

  1. What are the domain or coordinates for shape description? In what mathematical spaces do natural shape live?
  2. How do we define a meaningful metric (distance measure) in such space?
  3. There is no distinct boundary between shape and texture, can we construct shape models living in a continuous spectrum of texture models?

The recent study of texture theory indeed shed light on shape modeling, and we feel these problems can be answered in near future. In our group, we made four attempts to study shape models, mostly on 2D outlines of objects. We are planning for the 5th project on shape sketch which works on both contour and inner curves.

  1. FORMS: a Flexible Object Recognition and Modeling System, 1993-95 --- a generative region-based shape model.
  2. Stochastic medial axis and Gestalt laws in Markov random fields, 1997-98 --- a descriptive shape model.
  3. Shape representation by a sum of linear bases 2000-02 --- a contour-based linear additive model.
  4. A sketch model of shape 02-?? --- a generative model integrating both contour and region based descriptor.
  5. Shape metrics and morphing 02--??

Outside our group, there are many good work by David Cooper, Ben Kimia, David Mumford and Peter Giblin at Brown University.

FORMS: a Flexible Object Recognition and Modeling System

S. C. Zhu and A. L.Yuille, FORMS: A Flexible Object Recognition and Modeling System,
International Journal of Computer Vision, Vol.20, No.3, pp.187-212, 1996. [ps.gz]


1). Compute the medial axis of a shape in a bottom-up and top-down loop. Because the medial axis is ill-defined it must be regularized against some prior shape models. This is accomplished by a set of graph editing operators below. It is a graph matching with graph editing process.

 

2). Then the shape is decomposed according to the computed medial axes. We assumed a hinge joints for all parts: For example: a dog shape is decompsoed into 7 parts

Decomposition of a fish into rectangular and circular parts. Each of these parts are assumed to be flexible deformation from two primitives: a rectangle for elongated limes and a circle for short parts. Such as the fins of the fish. Then the deformation is characterized by principle components analysis, learned from data, the PCA for the two types of parts are shown below.

 

Based on an attributed graph matching, it can be used for object recognition. This work is a truly generative model of shape.

Stochastic Medial Axis and Gestalt Laws in Markov Random Field

The previous FORMS project is a generative shape model. Motivated by the success of texture modeling, we made the second attempt to modeling shape by a descriptive (Gibbs model). Two papers reported this project:

1. S. C. Zhu , "Stochastic Jump-Diffusion process for computing Medial Axes in Markov Random Fields", IEEE Trans. on PAMI, Vol. 21, No.11, pp1158-1169, Nov, 1999.
2. S. C. Zhu, "Embedding Gestalt Laws in Markov Random Fields -- A theory for shape modeling and perceptual organization", IEEE Trans. on PAMI , Vol. 21, No.11, Nov, pp1170-1187, 1999.

Some of the observed shapes as training examples, from which some shape statistics are extracted along the contour (co-linearity and co-circularity) and cross the medial axis for (proximity, parallelism, and symmetry). These are the popular Gestalt features. Then histograms of these features are accumulated across the data set.
By maximum entropy, we construct a shape model which reproduces the observed statistics. This figure shows three stages of the Markov chain sampling of this descriptive shape model. At the beginning, the sample (left) is very irregular. After adding the contour-based statistics, the sampled shape (middel) becomes smooth but bloby. After further adding the region-based statistics, the sample shape (right) has symmetric and elongated limes, just like the natural shapes. This descriptive model does not know parts or joints.
More examples from the Markov chain random walks, look, how much they resemble the spirit of those animal shapes in the training set !

A Linear Additive Model for Shape Modeling

A. Dubinskiy and S.C. Zhu, "A multiscale generative model for animate shape and parts" Proc. of Int'l Conf. on Computer Vision (ICCV), Nice, France, October, 2003.

Now with our match better understanding of the texture and texton theory, we are making a third attempt to model natural object shapes. This time, we try the linear additive model. A shape is a linear sum of a number of "shapelets" (like wavelets for images). This is done by a MS student Alex Dubinskiy.

For each shape, we construct a set of linear bases represented by ellipses in the top row. The bases with the same color add up to a part (wings, tail, and head etc.) When they are all added up, they yield the whole shape (see the dashed curves). Thus we call the bases graph up the "shape script". A desciptive model can be learned on this shape script to generate random animal shapes.

Hierarchic Shape Modeling and Sketch

After three trials, we believe we got some clue !! This is to integrate both generative model and generative model, integrate both region based parts and contour based parts. It becomes a shape sketch following artists footprint. It will be a hierarchic model which capture both the shape contour and the internal boundary (texture or sketches). Here we go !