Random walker algorithm
The random walker algorithm is a way to separate objects from the background in an image. It starts with user-provided seeds: a few pixels labeled as “object” and “background.” All the other pixels are unlabeled.
The image is treated as a graph. Each pixel is a node, and nodes are connected to their neighbors with edges. The edge weights reflect how similar two pixels are (for example, how close their colors or intensities are). For every unlabeled pixel, we ask: what is the probability that a random walker starting at that pixel will first reach an object seed rather than a background seed?
These probabilities are found by solving a small, sparse linear system based on the graph’s Laplacian. After computing the probabilities, each pixel is assigned to the label with the highest probability. So, if a pixel is more likely to reach an object seed first, it becomes part of the object.
Two important ideas make this work easy to extend. First, the method can be made fully automatic by adding a data fidelity term that encodes prior information (for example, a color model of the object). Second, the approach can handle more than two labels (multiple objects) by solving a larger system that includes all seeds.
There are also two intuitive interpretations. One is an electrical circuit view: each pixel is a node, edges are resistors whose conductances come from the edge weights, and the resulting steady-state voltages match the random-walker probabilities. The second is a conductance view: a pixel is labeled by comparing how easily it connects to object seeds versus background seeds; the label with the stronger connection wins.
The algorithm was introduced by Leo Grady. While it’s described here for two labels, it naturally generalizes to any number of labels and has been extended to other image-related tasks.
This page was last edited on 2 February 2026, at 08:03 (CET).