Shape Representation/Recovery

Generic object recognition requires modeling the shape of an object in a way that the resulting description is invariant to within-class shape deformation. Since two coffee cups can have different surface markings, handle shapes, and body profiles, a class-based description simply cannot describe local shape or appearance. Still, there are some big questions to answer. For example, should shape representations be object-centered or viewer-centered? What are the component primitives of such descriptions? How do we recover these primitives? Do we represent shape differently at different scales? Below you'll find a number of generic shape descriptions we've explored over the years.

Geometric Disentanglement

Part-Based Views

Deformable Models

Functional Models

Saliency Maps

Shock Graphs

Bone Graphs

Other Skeletal Descriptions

Blobs and Ridges

Top Points

Geons

Canonical View Modeling

View Degeneracy

Shape Abstraction

The failure of the early generic recognition systems was due to their inability to bridge the representational gap between the kinds of low-level features (e.g., edges, corners, lines, and regions) they could extract and the complex primitives that made up their generic object descriptions. The critical assumption these systems made was that there was a one-to-one correspondence between an extracted image feature and a generic model feature. This assumption restricted the approach to somewhat contrived objects where the assumption held. If a line was detected in the image, it must have matched an occluding boundary (limb) or salient surface discontinuity on a prototypical model of the object. Somehow, we must "lift" the extracted low-level features to more abstract descriptions at the level of our prototypical models. I call this the problem of abstraction, and think it's the greatest obstacle to generic object recognition the community faces. Below you'll find some approaches we've taken to solving this problem.

General Issues

Geometric Disentanglement

Learning Abstract Shape Descriptions from Examples

Multi-Scale Skeletal Abstraction

Multi-Scale Blob/Ridge Abstraction

Learning Decompositional Models from Examples

Part-Based Shape Abstraction

Human Vision

How is it that humans can recognize scenes depicted in line drawings almost as effectively as they can in color photographs? In this body of work, we study the problem of human shape perception in the context contour images, seeking to understand the role of nonaccidental relations in rapid scene classification.

Object Indexing

Object recognition consists of two component problems: indexing and matching (or verification). Indexing is the process that takes the query image (containing one or more objects) and quickly finds a small set of model candidates that might account for the object(s) in the image. It has to be fast and it has to be sublinear, for the database may have thousands or millions of objects. Below you'll find some approaches we've taken to this problem.

3-D Object Indexing using Part-Based Views

2-D Shape Indexing using a Modal Description of Shape

Structural Indexing using Grapha Spectra

Viewpoint-Invariant Shape Indexing for Content-Based Image Retrieval

Object Matching

Once the indexing process has pruned the large database down to a small number of candidates, the final step consists of verifying the candidates (hypotheses), returning a distance measure used to rank-order the candidates. When the object to be recognized is occluded, perturbed by noise, embedded in a cluttered scene, or represented at a different scale from the model being matched to it, the matching problem becomes more challenging. We have explored these issues in a number of matching strategies, which we include below.

Object Recognition using Part-Based Aspect Graphs

Object Recognition using Saliency Maps

Object Recognition using Shock Graphs

Object Recognition using Blobs and Ridges

Object Recognition using Top Points

Object Recognition as Many-to-Many Feature Matching

Object Tracking

Tracking is a form of object recognition in which the object you're searching for in an image is simply the same one you found in the previous frame, along with some degree of knowledge of how it may have moved in between. Whether or not a prior shape model exists for the object, whether such a model is object-centered or viewer-centered, the representational gap between the model and the tracked exemplar, whether or not the object can deform or articulate as it moves are all issues that we have addressed in developing a number of tracking frameworks below.

3-D Object Tracking using Networks of Active Contours

Tracking 3-D Deformable Models in 2-D Images

Incremental Deformable 3-D Model Estimation through Tracking

Detecting and Tracking the Shapes of Multiple Independently Moving Objects

Content-Based Image Retrieval

I once heard Jitendra Malik say in a talk, "Takeo Kanade once said that robotics is where computer vision meets the real world, while I think content-based image retrieval is where object recognition meets the real world." I couldn't agree more, for searching images on the web (for example) simply does not permit recognition strategies that rely on exact modeling of geometry or appearance. There is no better venue for generic object recognition than semantic-level image retrieval. We have explored a number of problems in CBIR, which we outline below.

Querying fMRI Images using Earth Mover's Distance

Querying Dental Radiographs using the Qualitative Shape of Lesions

Viewpoint-Invariant Shape Indexing for Content-Based Image Retrieval

3-D Model Retrieval using Medial Surfaces

Activity Recognition

Representing an activity in support of activity recognition is no less challenging than representing an object in support of object recognition. Just as the number of parts of an object and the relationships between the parts may vary, so too can the number of "actors" in an activity and the relationships between the actors. Moreover, the identifies of the actors may vary (a "ball" or a "bat" may be "thrown"). The scope of within-class variation of an activity, in terms of the number, relationships, and motions of the "parts" is therefore typically larger than that of an object. On the other hand, the motions of the parts may make them easier to segment in a video than segmenting an object's parts in a static image. While there are strong similarities between these two problems, they typically draw on very different tools. Below, we look at some image-based activity recognition systems applied to different applications.

Monitoring the Workflow of Construction Vehicles

Recognizing the Activities of Humans in a Natural Setting

Vision-Based Navigation

Landmark-based navigation is a recognition problem, but not necessarily a generic one. Granted, if I tell you to turn left at the next fire station, you need to recognize a fire station you've never seen before using some sort of generic model. However, it's not clear that on your next trip by the fire station, its representation as a visual landmark at which you turn right is the same. How do we represent landmarks? What constitutes a good landmark? How do we automatically acquire good landmarks? And how do we navigate by them? These are some of the issues we explored in the links below.

Navigation using a Linear Combination of Landmark Views

Expert Vision Systems for ALV Road Following

Automatic Landmark Acquisition for Vision-Based Navigation

Behaviour-Based Vision

During my dissertation work, I focused primarily on the problem of unexpected, or bottom-up object recognition, which assumed that you didn't know what object you were looking at but knew it must be contained in the database. As a postdoc, I realized that this was a rather narrow view of recognition and that an intelligent agent employed a collection of recognition "behaviours." For example, when the agent walks into a room, it discovers what objects are in the room, perhaps with no prior expectation. This is analagous to the unexpected object recognition problem. Alternatively, the agent may enter the room with the goal of finding and retrieving a particular object, say a cup. This is the target, or top-down recognition problem, in which knowledge of the target object should constrain how features are extracted and matched to the model. If the handle of the cup is facing away from the agent, the cup may look like a glass. To resolve the ambiguity, the agent must plan a viewpoint change to a position at which the identity of the object can be disambiguated. This is the active recognition problem. As the agent moves to the preferred viewpoint or moves closer to the object, it must track the object. When it gets close enough to grasp the cup, it must both localize the object and recover sufficient shape information to grasp the object. I felt that these 5-6 recognition behaviours must sit on top of a single representational framework to allow them to be interchangeable in response to a complex task. I spent several years unifying these recognition behaviours through a single representational framework, which is described below.

Unifying Recognition Behaviours using a Single Representational Framework

Vision-Based Aids for the Disabled

The multi-behaviour recognition model described above came to me while working on the PLAYBOT project at the University of Toronto, where I was a postdoc. PLAYBOT was the brain child of John Tsotsos, who envisioned a computer vision system that could help severely disabled children play with toys. The project brought together researchers from the University of Toronto and York University. Each of the behaviours described in the previous section had a corresponding behaviour in PLAYBOT's constrained world, and we came up with novel approaches to each of the subproblems. It also provided an ideal platform on which I could explore the unification of these recognition behaviours. Links describing the PLAYBOT system, along with our thoughts on task-driven vs. reactive beaviours are found below

PLAYBOT: A Robotic Vision System to Allow Disabled Children to Play with Toys

Integrating Vision and Language

Every time I built a recognition system, I'd always type in some label for an object model entered into the database. I began to wonder if there was a way I could somehow automatically learn the semantics (or at least the label) of a shape model. Could I build a system that exploited associations in web documents between the nouns in figure captions and the generic shapes found in their corresponding images? This would certainly require a powerful generic shape segmentation/matching engine that would have to deal with segmentation errors, occlusion, and significant within-class shape deformation. The representational gap alluded to earlier wreaks havoc here, for "salient" features, such as segmented regions often cannot be directly mapped to words. In the case of oversegmentation, such regions must be grouped, while for undersegmentation, such regions must be split. We have developed a new approach that can associate nouns and generic shape models in the presence of segmentation errors.

Automatic Image Annotation of Poorly Segmented Objects

Image-Guided Word-Sense Disambiguation

Language-Driven Perceptual Grouping

Learning the Motion Semantics of Verbs

American Sign Language Video Analysis

Generating Sentential Descriptions of Videos

Space Robotics

We have been working with MD Robotics, developers of the NASA Space Shuttle Canadarm and the International Space Station (ISS) robotic arms, to develop a "visual supervisor" for spaceborne safety monitoring for the ISS. From a low-resolution, wide field of view camera, the system draws on our object tracking and recognition algorithms to detect the silhouette boundaries of multiple independently moving objects (against moving background), identify the objects' categories, compare the motions and identities of the objects to an active task library, and finally to detect anomalous behaviours. The system provides a "visual sanity check" of a space environment, and directs task-specific resources to further investigate anomalous behaviours. The system is described below:

Vision and Learning

Learning can play an important role in generic object modeling. Given a set of exemplars belonging to a single, known object class, can we automatically learn a prototypical, possibly hierarchical description for the class? Or, in a collection of images with captions, in which there are references in the captions to objects in the image, can we automatically learn the names of the shapes? These are some of the learning problems we're exploring.

Learning Geometric Disentanglement

Learning Medial Representations

Learning Abstract Model Descriptions from Examples

Learning Semantic Labels for Image Objects

Learning the Motion Semantics of Verbs

Learning Decompositional Models from Examples

Graph Algorithms in Computer Vision

My interest in generic object recognition led to various abstract shape representations -- structural models with primitives and spatial relations and often organized in a hierarchy or a scale space. I quickly discovered that graphs provide a powerful abstraction for representing shape structures in computer vision. Consequently, the problems of shape indexing and matching (together comprising object recognition), can be formulated as graph indexing and matching problems. The graph algorithms community is a mature one, and has much to offer vision researchers working with graphs. We have worked extensively with graphs, whether directed or undirected, hierarchical or flat. Moreover, we have explored both one-to-one and many-to-many matching strategies. Below you'll find some links to our work on the convergence of graph algorithms and object recognition. A nice collection of papers on the topic can be found in a special issue of PAMI that I co-edited (with Marcello Pelillo and Ramin Zabih), which appeared in October, 2001/2002 (Volume 23, Number 10).

General Issues

Motion Segmentation as a Metric Embedding Problem

Part Recovery as an Undirected Graph Covering Problems

Multi-Scale Shape Matching as a Directed Acyclic Graph Matching Problem

A Low-Dimensional Encoding of Hierarchical Shape using Spectral Graph Theory

Visual Landmark Selection as a Graph Covering Problem

Hierarchical Shape Indexing as a Graph Indexing Problem

Hierarchical Shape Matching as a Tree Matching Problem

Hierarchical Shape Matching as a Directed Acyclic Graph Matching Problem

Many-to-Many Graph Matching

A Unified Approach to Hierarchical Shape Indexing and Matching using Spectral Graph Theory

View-Based 3-D Object Recognition as a Graph Indexing/Matching Problem

Shape Matching as a Bipartite Graph Matching Problem

Shape Matching as a Graph Embedding Problem

Perceptual Grouping as a Graph Cut Problem

Segmentation and Perceptual Grouping

Part abstraction first requires the segmentation and grouping of features that belong to an object. I have looked at the use of weak shape priors in the generation of superpixels, a form of region oversegmentation. On the perceptual grouping side, I have looked at the use of intermediate-level shape priors for perceptual grouping and abstraction of image contours and superpixels for both static and dynamic scenes.

Region Segmentation

Perceptual Grouping

Page created: Dec 1, 2000      
Last modified: Jan 1, 2021
Maintained by: Sven Dickinson