H. Ishikawa and D. Geiger

IEEE Conference on Computer Vision and Pattern Recognition (CVPR'98), 1998.

We propose a method for segmenting gray-value images. By segmentation, we mean a map from the set of pixels to a small set of levels, such that each connected component of the set of pixels with the same level forms a relatively large and ``meaningful'' region. The method finds a set of levels with associated gray values and the segmentation that maps each pixel to the level with the closest gray value to the pixel data, within a smoothness constraint. For a convex smoothing penalty, we show the global optimal solution for an energy function that fits the data can be obtained in a polynomial time, by a novel use of the maximum-flow algorithm. Our approach is in contrast with a view in computer vision where segmentation is driven by intensity gradient, usually not yielding closed boundaries.