The random walker algorithm is an algorithm for
image segmentation. In the first description of the algorithm,
[Grady, L.:]
Random walks for image segmentation
. PAMI, 2006 a user interactively labels a small number of pixels with known labels (called seeds), e.g., "object" and "background". The unlabeled pixels are each imagined to release a random walker, and the probability is computed that each pixel's random walker first arrives at a seed bearing each label, i.e., if a user places K seeds, each with a different label, then it is necessary to compute, for each pixel, the probability that a random walker leaving the pixel will first arrive at each seed. These probabilities may be determined analytically by solving a system of linear equations. After computing these probabilities for each pixel, the pixel is assigned to the label for which it is most likely to send a random walker. The image is modeled as a
graph, in which each pixel corresponds to a node which is connected to neighboring pixels by edges, and the edges are weighted to reflect the similarity between the pixels. Therefore, the random walk occurs on the weighted graph (see Doyle and Snell for an introduction to random walks on graphs).
Although the initial algorithm was formulated as an interactive method for image segmentation, it has been extended to be a fully automatic algorithm, given a
data fidelity term (e.g., an intensity prior).
[Leo Grady:]
Multilabel Random Walker Image Segmentation Using Prior Models
, Proc. of CVPR, Vol. 1, pp. 763–770, 2005. It has also been extended to other applications.
The algorithm was initially published b
Leo Gradyas a conference paper and later as a journal paper.
Mathematics
Although the algorithm was described in terms of
random walks, the probability that each node sends a random walker to the seeds may be calculated analytically by solving a sparse, positive-definite system of linear equations with the graph
Laplacian matrix
In the mathematical field of graph theory, the Laplacian matrix, also called the graph Laplacian, admittance matrix, Kirchhoff matrix or discrete Laplacian, is a matrix representation of a graph. Named after Pierre-Simon Laplace, the graph Laplac ...
, which we may represent with the variable
. The algorithm was shown to apply to an arbitrary number of labels (objects), but the exposition here is in terms of two labels (for simplicity of exposition).
Assume that the image is represented by a
graph, with each node
associated with a pixel and each edge
connecting neighboring pixels
and
. The edge weights are used to encode node similarity, which may be derived from differences in image intensity, color, texture or any other meaningful features. For example, using image intensity
at node
, it is common to use the edge weighting function
:
The nodes, edges and weights can then be used to construct the graph
Laplacian matrix
In the mathematical field of graph theory, the Laplacian matrix, also called the graph Laplacian, admittance matrix, Kirchhoff matrix or discrete Laplacian, is a matrix representation of a graph. Named after Pierre-Simon Laplace, the graph Laplac ...
.
The random walker algorithm optimizes the energy
:
where
represents a real-valued variable associated with each node in the graph and the optimization is constrained by
for
and
for
, where
and
represent the sets of foreground and background seeds, respectively. If we let
represent the set of nodes which are seeded (i.e.,
) and
represent the set of unseeded nodes (i.e.,
where
is the set of all nodes), then the optimum of the energy minimization problem is given by the solution to
:
where the subscripts are used to indicate the portion of the graph Laplacian matrix
indexed by the respective sets.
To incorporate likelihood (unary) terms into the algorithm, it was shown in
that one may optimize the energy
:
for positive, diagonal matrices
and
. Optimizing this energy leads to the system of linear equations
:
The set of seeded nodes,
, may be empty in this case (i.e.,
), but the presence of the positive diagonal matrices allows for a unique solution to this linear system.
For example, if the likelihood/unary terms are used to incorporate a color model of the object, then
would represent the confidence that the color at node
would belong to object (i.e., a larger value of
indicates greater confidence that
belonged to the object label) and
would represent the confidence that the color at node
belongs to the background.
Algorithm interpretations
The random walker algorithm was initially motivated by labelling a pixel as object/background based on the probability that a random walker dropped at the pixel would first reach an object (foreground) seed or a background seed. However, there are several other interpretations of this same algorithm which have appeared in.
Circuit theory interpretations
There are well-known connections between
electrical circuit
An electrical network is an interconnection of electrical components (e.g., batteries, resistors, inductors, capacitors, switches, transistors) or a model of such an interconnection, consisting of electrical elements (e.g., voltage sources, ...
theory and random walks on graphs. Consequently, the random walker algorithm has two different interpretations in terms of an electric circuit. In both cases, the graph is viewed as an electric circuit in which each edge is replaced by a passive linear
resistor
A resistor is a passive two-terminal electrical component that implements electrical resistance as a circuit element. In electronic circuits, resistors are used to reduce current flow, adjust signal levels, to divide voltages, bias active el ...
. The resistance,
, associated with edge
is set equal to
(i.e., the edge weight equals
electrical conductance).
In the first interpretation, each node associated with a background seed,
, is tied directly to
ground
Ground may refer to:
Geology
* Land, the surface of the Earth not covered by water
* Soil, a mixture of clay, sand and organic matter present on the surface of the Earth
Electricity
* Ground (electricity), the reference point in an electrical c ...
while each node associated with an object/foreground seed,
is attached to a unit
direct current ideal
voltage source tied to ground (i.e., to establish a unit potential at each
). The steady-state electrical circuit potentials established at each node by this circuit configuration will exactly equal the random walker probabilities. Specifically, the electrical potential,
at node
will equal the probability that a random walker dropped at node
will reach an object/foreground node before reaching a background node.
In the second interpretation, labeling a node as object or background by thresholding the random walker probability at 0.5 is equivalent to labeling a node as object or background based on the relative effective conductance between the node and the object or background seeds. Specifically, if a node has a higher effective conductance (lower effective resistance) to the object seeds than to the background seeds, then node is labeled as object. If a node has a higher effective conductance (lower effective resistance) to the background seeds than to the object seeds, then node is labeled as background.
Extensions
The traditional random walker algorithm described above has been extended in several ways:
* Random walks with restart
* Alpha matting
* Threshold selection
* Soft inputs
* Run on a presegmented image
* Scale space random walk
* Fast random walker using offline
precomputation
* Generalized random walks allowing flexible compatibility functions
[R. Shen, I. Cheng, J. Shi, A. Basu]
Generalized Random Walks for Fusion of Multi-exposure Images
IEEE Trans. on Image Processing, 2011.
* Power watersheds unifying graph cuts, random walker and shortest path
* Random walker watersheds
* Multivariate Gaussian conditional random field
[R. Shen, I. Cheng, A. Basu]
QoE-Based Multi-Exposure Fusion in Hierarchical Multivariate Gaussian CRF
IEEE Trans. on Image Processing, 2013.
Applications
Beyond image segmentation, the random walker algorithm or its extensions has been additionally applied to several problems in computer vision and graphics:
* Image Colorization
* Interactive rotoscoping
* Medical image segmentation
* Merging multiple segmentations
* Mesh segmentation
* Mesh denoising
* Segmentation editing
* Shadow elimination
* Stereo matching (i.e., one-dimensional
image registration)
* Image fusion
References
{{Reflist
External links
Matlab code implementing the original random walker algorithmMatlab code implementing the random walker algorithm with precomputationin the image processing toolbo
scikit-image
Image segmentation