Recognizing Pictorial Structures

Daniel Huttenlocher
Computer Science Department
Cornell University

SPECIAL TIME

1305 Newell-Simon Hall
Refreshments 4:15 pm
Talk 4:30 pm

Abstract

We present an approach to the problem of efficiently recognizing objects that can be modeled as rigid subparts with flexible connections, such as people and many animals. We use a modeling scheme first introduced nearly 30 years ago by Fischler and Elschlager, where an object is represented as a set of image patches together with constraints on the relative locations of those patches. Finding the best match of such a model to an image can be phrased as an energy minimization problem, but generic solution methods are inefficient and not guaranteed to find the best match. The main contribution of our work is a highly efficient method that finds the best match (up to a discretization factor) and which is applicable to a broad range of objects.

For most objects the connections between parts can be represented using a tree structure, and the relationship between neighboring parts can be expressed as a distance in some space. We show how these two properties can be used to develop a highly efficient algorithm, which runs in O(MN) time for an object with N parts where each part can be in M possible locations. This method uses two levels of dynamic programming, including one based on a novel generalization of distance transforms. The generalized distance transform method is of potential interest for solving other problems as well.

This recognition method is quite efficient in practice. Our implementation can find the best (global) match of a model with a half-dozen parts in just a few seconds. We illustrate the approach using simple generic models of a person and of a car, showing results for complex scenes under a range of lighting conditions and in varied poses.

This is joint work with Pedro Felzenszwalb from MIT.

Speaker Biography

Daniel Huttenlocher is Professor of Computer Science and Stephen H. Weiss Fellow at Cornell University, and Principal Scientist at the Xerox Palo Alto Research Center (PARC). His research interests are in computer vision, electronic document systems and computational geometry. Huttenlocher received his bachelors degree from the University of Michigan and his masters and doctorate from MIT. Since 1988 he has split his time between Cornell and Xerox PARC.

Professor Huttenlocher has published over 50 articles in professional journals and conferences, and holds 17 US patents. In addition to research, he has been widely recognized for his contributions to undergraduate education, receiving both national and Cornell awards. Most recently he has developed CS 130, a course on creating interactive Web documents. Huttenlocher also chairs the Provost's task force at Cornell which has recently recommended that the University create a new Faculty of Computing and Information.

Speaker Appointments

For appointments, please contact the host, Robert Collins (rcollins@ri.cmu.edu).