Quickly Computing a Good Segmentation

Dan Huttenlocher

Cornell University


We introduce a framework for characterizing what constitutes a good segmentation of an image, and present an efficient algorithm for computing such segmentations. The framework provides precise definitions of what it means for a segmentation to be too coarse or too fine. This framework applies to any segmentation technique that uses pairwise region comparison. Within the framework we define a particular region comparison function, based on the intuition that the self-similarity within a region should be higher than the similarity between two regions. We then develop a highly efficient segmentation algorithm using this comparison function. This talk will discuss the framework and the algorithm, and sketch the proofs that the algorithm produces segmentations that are neither too coarse nor too fine. We will then illustrate how the framework and algorithm apply to a broader range of clustering and segmentation problems. Finally, we will consider some applications of the algorithm to computer vision problems, including segmenting a single image, segmenting a sequence of video frames, and segmentation-based detection of moving objects in video.

This is joint work with Pedro Felzenszwalb.

Dan Huttenlocher is an Associate Professor of Computer Science and Stephen H. Weiss Fellow at Cornell University, and a principal scientist at Xerox PARC. His research interests are in computer vision, primarily the areas of object recognition and image segmentation. At Xerox he is applying computer vision techniques to problems of document image representation and compression.

Edited by Leonidas Guibas