IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 28, NO. 11, NOV. 2006 1
Random Walks for Image Segmentation
Leo Grady
Abstract— A novel method is proposed for performing multi-
label, interactive image segmentation. Given a small number
of pixels with user-defined (or pre-defined) labels, one can
analytically and quickly determine the probability that a random
walker starting at each unlabeled pixel will first reach one of
the pre-labeled pixels. By assigning each pixel to the label for
which the greatest probability is calculated, a high-quality image
segmentation may be obtained. Theoretical properties of this
algorithm are developed along with the corresponding connec-
tions to discrete potential theory and electrical circuits. This
algorithm is formulated in discrete space (i.e., on a graph) using
combinatorial analogues of standard operators and principles
from continuous potential theory, allowing it to be applied in
arbitrary dimension on arbitrary graphs.
Index Terms—Image segmentation, interactive segmentation,
graph theory, random walks, combinatorial Dirichlet problem,
harmonic functions, Laplace equation, graph cuts, boundary
completion
I. INTRODUCTION
I
MAGE segmentation has often been defined as the problem
of localizing regions of an image relative to content (e.g.,
image homogeneity). However, recent image segmentation
approaches have provided interactive methods that implicitly
define the segmentation problem relative to a particular task
of content localization. This approach to image segmentation
requires user (or preprocessor) guidance of the segmentation
algorithm to define the desired content to be extracted.
A practical interactive segmentation algorithm must provide
four qualities: 1) Fast computation, 2) Fast editing, 3) An
ability to produce an arbitrary segmentation with enough
interaction, 4) Intuitive segmentations. The random walker al-
gorithm introduced here exhibits all of these desired qualities.
We note that this algorithm was first presented in a shortened
form as a conference paper [1]. The random walker algorithm
requires the solution of a sparse, symmetric positive-definite
system of linear equations which may be solved quickly
through a variety of methods. The algorithm may perform fast
editing by using the previous solution as the initialization of
an iterative matrix solver. An arbitrary segmentation may also
be achieved through enough user interaction.
In this paper, we present a novel approach to K-way image
segmentation given user-defined seeds indicating regions of
the image belonging to K objects. Each seed specifies a
location with a user-defined label. The algorithm labels an
unseeded pixel by resolving the question: Given a random
walker starting at this location, what is the probability that
Published in: IEEE Trans. on Pattern Analysis and Machine Intelligence,
Vol. 28, No. 11, pp. 1768–1783, Nov., 2006
Leo Grady is with Siemens Corporate Research, Department of Imaging
and Visualization, 755 College Road East, Princeton, NJ 08540, E-mail:
Leo.Grady@siemens.com
it first reaches each of the K seed points? It will be shown
that this calculation may be performed exactly without the
simulation of a random walk. By performing this calculation,
we assign a K-tuple vector to each pixel that specifies the
probability that a random walker starting from each unseeded
pixel will first reach each of the K seed points. A final
segmentation may be derived from these K-tuples by selecting
for each pixel the most probable seed destination for a random
walker. By biasing the random walker to avoid crossing sharp
intensity gradients, a quality segmentation is obtained that
respects object boundaries (including weak boundaries). In a
uniform image (e.g., all black) or, as will be proved in Section
IV, an image of pure noise, a segmentation will be obtained
that roughly corresponds to Voronoi cells for each set of seed
points. We term this segmentation the neutral segmentation
since the image is neutral (i.e., devoid of meaningful content).
In our approach, we treat an image (or volume) as a purely
discrete object — a graph with a fixed number of vertices and
edges. Each edge is assigned a real-valued weight correspond-
ing to the likelihood that a random walker will cross that edge
(e.g., a weight of zero means that the walker may not move
along that edge). The advantage of formulating the problem on
a graph is that purely combinatorial operators may be used that
require no discretization and therefore incur no discretization
errors or ambiguities. Formulation of the algorithm on a graph
also allows the application of the algorithm to surface meshes
or space-variant images [2], [3]. Regardless of the dimensions
of the data, we will use the term pixel throughout this paper to
refer to the basic picture element in the context of its intensity
values. In contrast, the term node will be used in the context
of a graph-theoretical discussion.
Although the present algorithm is motivated in terms of
random walks, an adequate sampling from this distribution
would be completely infeasible for segmentation problems of
interest. Fortunately, it has been previously established [4], [5]
that the probability a random walker first reaches a seed point
exactly equals the solution to the Dirichlet problem [6] with
boundary conditions at the locations of the seed points and
the seed point in question fixed to unity while the others are
set to zero. For a popular account of this connection, see [7].
The development of a fully discrete calculus [8] has allowed
for the connection between random walks on graphs [9] and
discrete potential theory [10] to be made completely explicit
[5]. The solution to the combinatorial Dirichlet problem on
an arbitrary graph is given exactly by the distribution of
electric potentials on the nodes of an electrical circuit with
resistors representing the inverse of the weights (i.e., the
weights represent conductance) and the “boundary conditions”
given by voltage sources fixing the electric potential at the
“boundary nodes”.
In light of the connection between random walks on graphs
剩余16页未读，继续阅读
资源评论
