Efficiently Computing a Good Segmentation

Pedro F. Felzenszwalb
Daniel P. Huttenlocher


This paper is concerned with the problem of segmenting an image into regions, using a local measure of the difference between image pixels. We develop a general framework for a broad range of segmentation problems, based on pairwise comparison of regions in a segmentation. This framework provides precise definitions of when a segmentation is too coarse or too fine. Within this framework, we define a particular pairwise region comparison function for graph-based segmentation problems. Then we provide an efficient algorithm for computing a segmentation using this comparison function, and prove that it produces good segmentations -- those that are neither too coarse nor too fine by our definitions. We apply this algorithm to image segmentation. An important characteristic of this method is its ability to preserve detail in low-variability image regions while ignoring detail in high-variability regions. We illustrate the method with several examples on both real and sythetic images.

Click here for the paper to appear in the 1998 DARPA Image Understanding Workshop (postscript, gzip).

Click here for the paper in CVPR '98 (postscript, gzip).
P. Felzenszwalb, D. Huttenlocher. Image Segmentation Using Local Variation. Proceedings IEEE Conference on Computer Vision and Pattern Recognition, pages 98-104, 1998.

Click here for the poster presented in CVPR '98.

Example results

Click on the images to see segmentation results.

street10-small.jpg synt.jpg new11__0.jpg (1965 bytes)

Download binaries and source code (last update: 6/18/99)

binaries for Windows NT: segment-bin.zip
source: segment-src.zip


Back to Vision Homepage