Research Abstracts - 2007

The Problem

We wish to model the variability of 2-D shapes (or a set of views of 3-D shapes), in order to robustly perform inference tasks such as object recognition and object boundary estimation in the presence of sensor noise, occlusions, and rigid transformations.

Motivation

In computer vision, most work on 2-D shape recognition has focussed on discriminative models of sensing. Shape dissimilarity metrics (or shape distances) are formed, and one compares a new shape to a database of exemplars in order to find the best match. Much of the work has gone into finding the right shape distance, and typically a transformation is taken on the raw geometric data (e.g. an object silhouette contour) in order to perform the classification in the more discriminative shape space. In addition, care must be taken in choosing the exemplar shapes so that the size of the classification problem does not blow up with the number of object classes. Such techniques typically work well when the ability to discriminate between classes (i.e. classification) is the most important problem to be solved.

However, if the geometry of objects within the same shape class varies in a significant way (such as in figure 1), or one wishes to perform additional inference tasks such as boundary estimation (such as in figure 2), it can be very difficult to construct an appropriate shape distance. Discriminative techniques can be difficult to us for robust shape modeling of both the object class and boundary estimation. Some methods require a transformation which makes it very difficult or even impossible to recover the original geometry (e.g. fourier descriptors [6], curvature scale space [7]). Other methods require many hard decisions to be made in the modeling process (e.g. skeletons [8], part-based models [5,9]), making it very difficult to develop statistical variants of the complete shape of the model. Thus, we seek a model for shape which is generative, and is as close to the raw geometric data (e.g. pixel or range measurement locations) as possible.

Figure 1. Object recognition is a challenge for shape classes with high variance, due to articulation (left) and biology (right). It is very difficult to construct a single shape metric which will enable robust, accurate discrimination of shape categories for classes such as these.

Figure 2. Boundary estimation is a challenge when part of the object is occluded. We want to predict the spatial location of every point on an object's boundary (both hidden and observed).

Approach

We will use a seemingly simple, yet powerful model-- representing object shape as the complete set of boundary points. The drawbacks to this model are obvious--we are (for now) restricted to closed contours, we cannot represent continuous curves, and we must solve a correspondence problem in order to compare shapes. However, the advantages are (i) it can be made entirely non-parametric (i.e. we can incorporate the pixel or range measurement locations in the model), (ii) we have a natural cyclic ordering of points around the contour, and (iii) most importantly, we can draw upon a vast amount of established literature on the statistical shape modeling of sets of ordered landmarks [1,4].

Preliminary Results

We have demonstrated the ability to perform boundary estimation in the presence of occlusions [3], and we have also worked on methods for finding point correspondences between two shapes [2].

Figure 3. Shape completion and classification of a partial contour (top-left). In the second, third and fourth image, the mean shape of the shape class is shown in blue on the left, and the approximate maximum likelihood completion to the partial contour is shown on the right. The correct completion is the bottom left image, completing the partial tool as a complete tool.

Figure 4. Examples of correspondences found with our method in [2].

Future Work

In future work, we plan to apply statistical shape modeling to image segmentation, robotic navigation under uncertainty, and robotic manipulation.

References:

[1] I. Dryden and K. Mardia. Statistical Shape Analysis. John Wiley and Sons, 1998.

[2] Jared Glover, Christian Uldall Pedersen, and Erik Taarnhøj. Solving the cyclic order preserving assignment problem. Advanced Algorithms (6.854) Final Project, December 2006.

[3] Jared Glover, Daniela Rus, Nicholas Roy, and Geoff Gordon. Robust models of object geometry. In Proceedings of the IROS Workshop on From Sensors to Human Spatial Concepts, Beijing, China, 2006.

[4] D.G. Kendall, D. Barden, T.K. Carne, and H. Le. Shape and Shape Theory. John Wiley and Sons, 1999.

[5] L. J. Latecki and R. Lakamper. Contour-based shape similarity. In Proc. of Int. Conf. on Visual Information Systems, volume LNCS 1614, pages 617-624, June 1999.

[6] C. C. Lin and R. Chellappa. Classification of partial 2-d shapes using fourier descriptors. IEEE Trans. Pattern Anal. Mach. Intell., 9(5):686- 690, 1987.

[7] F. Mokhtarian and A. K. Mackworth. A theory of multiscale curvaturebased shape representation for planar curves. In IEEE Trans. Pattern Analysis and Machine Intelligence, volume 14, 1992.

[8] Kaleem Siddiqi, Ali Shokoufandeh, Sven J. Dickinson, and Steven W. Zucker. Shock graphs and shape matching. In ICCV, pages 222-229, 1998.

[9] Mirela Tanase and Remco C. Veltkamp. Part-based shape retrieval. In MULTIMEDIA '05: Proceedings of the 13th annual ACM international conference on Multimedia, pages 543-546, New York, NY, USA, 2005.