02-05-2011, 04:21 PM
Abstract
This paper addresses the problem of segmenting an image into regions. We de¯ne
a predicate for measuring the evidence for a boundary between two regions using a
graph-based representation of the image. We then develop an e±cient segmentation
algorithm based on this predicate, and show that although this algorithm makes greedy
decisions it produces segmentations that satisfy global properties. We apply the algorithm
to image segmentation using two di®erent kinds of local neighborhoods in
constructing the graph, and illustrate the results with both real and synthetic images.
The algorithm runs in time nearly linear in the number of graph edges and is also fast
in practice. An important characteristic of the method is its ability to preserve detail
in low-variability image regions while ignoring detail in high-variability regions.
Keywords: image segmentation, clustering, perceptual organization, graph algorithm.
1 Introduction
The problems of image segmentation and grouping remain great challenges for computer
vision. Since the time of the Gestalt movement in psychology (e.g., [17]), it
has been known that perceptual grouping plays a powerful role in human visual perception. A wide range of computational vision problems could in principle make
good use of segmented images, were such segmentations reliably and e±ciently computable.
For instance intermediate-level vision problems such as stereo and motion
estimation require an appropriate region of support for correspondence operations.
Spatially non-uniform regions of support can be identi¯ed using segmentation techniques.
Higher-level problems such as recognition and image indexing can also make
use of segmentation results in matching, to address problems such asgure-ground
separation and recognition by parts.
Our goal is to develop computational approaches to image segmentation that are
broadly useful, much in the way that other low-level techniques such as edge detection
are used in a wide range of computer vision tasks. In order to achieve such broad
utility, we believe it is important that a segmentation method have the following
properties:
1. Capture perceptually important groupings or regions, which often re°ect global
aspects of the image. Two central issues are to provide precise characterizations
of what is perceptually important, and to be able to specify what a given segmentation
technique does. We believe that there should be precise de¯nitions
of the properties of a resulting segmentation, in order to better understand the
method as well as to facilitate the comparison of di®erent approaches.
2. Be highly e±cient, running in time nearly linear in the number of image pixels.
In order to be of practical use, we believe that segmentation methods should
run at speeds similar to edge detection or other low-level visual processing
techniques, meaning nearly linear time and with low constant factors. For
example, a segmentation technique that runs at several frames per second can
be used in video processing applications.
While the past few years have seen considerable progress in eigenvector-based
methods of image segmentation (e.g., [14, 16]), these methods are too slow to be
practical for many applications. In contrast, the method described in this paper
has been used in large-scale image database applications as described in [13]. While
there are other approaches to image segmentation that are highly e±cient, these
methods generally fail to capture perceptually important non-local properties of an
image as discussed below. The segmentation technique developed here both captures
certain perceptually important non-local image characteristics and is computationally
e±cient { running in O(n log n) time for n image pixels and with low constant factors,
and can run in practice at video rates.
As with certain classical clustering methods [15, 19], our method is based on
selecting edges from a graph, where each pixel corresponds to a node in the graph,
and certain neighboring pixels are connected by undirected edges. Weights on each
edge measure the dissimilarity between pixels. However, unlike the classical methods,
our technique adaptively adjusts the segmentation criterion based on the degree of
variability in neighboring regions of the image. This results in a method that, while
making greedy decisions, can be shown to obey certain non-obvious global properties.
We also show that other adaptive criteria, closely related to the one developed here,
result in problems that are computationally di±cult (NP hard).
We now turn to a simple synthetic example illustrating some of the non-local image
characteristics captured by our segmentation method. Consider the image shown in
the top left of Figure 1. Most people will say that this image has three distinct
regions: a rectangular-shaped intensity ramp in the left half, a constant intensity
region with a hole on the right half, and a high-variability rectangular region inside
the constant region. This example illustrates some perceptually important properties
that we believe should be captured by a segmentation algorithm. First, widely varying
intensities should not alone be judged as evidence for multiple regions. Such wide
variation in intensities occurs both in the ramp on the left and in the high variability
region on the right. Thus it is not adequate to assume that regions have nearly
constant or slowly varying intensities.
A second perceptually important aspect of the example in Figure 1 is that the
three meaningful regions cannot be obtained using purely local decision criteria. This
is because the intensity di®erence across the boundary between the ramp and the
constant region is actually smaller than many of the intensity di®erences within the
high variability region. Thus, in order to segment such an image, some kind of
adaptive or non-local criterion must be used.
The method that we introduce in Section 3.1 measures the evidence for a boundary
between two regions by comparing two quantities: one based on intensity di®erences
across the boundary, and the other based on intensity di®erences between neighboring
pixels within each region. Intuitively, the intensity di®erences across the boundary
of two regions are perceptually important if they are large relative to the intensity
di®erences inside at least one of the regions.
DOWNLOAD FULL REPORT
http://people.cs.uchicago.edu/~pff/papers/seg-ijcv.pdf
