In the first description of the algorithm,[1] 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.
Therefore, the random walk occurs on the weighted graph (see Doyle and Snell for an introduction to random walks on graphs[2]).
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).
[1] 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, 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
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.
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
represent the sets of foreground and background seeds, respectively.
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
To incorporate likelihood (unary) terms into the algorithm, it was shown in [3] that one may optimize the energy for positive, diagonal matrices
Optimizing this energy leads to the system of linear equations The set of seeded nodes,
), 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
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.
[1] There are well-known connections between electrical circuit theory and random walks on graphs.
[5] 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.
(i.e., the edge weight equals electrical conductance).
, is tied directly to ground 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.
will equal the probability that a random walker dropped at 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.
The traditional random walker algorithm described above has been extended in several ways: Beyond image segmentation, the random walker algorithm or its extensions has been additionally applied to several problems in computer vision and graphics: