Random Walker Image Segmentation
This page contains the main points of a demo I've
given of the random walker segmentation algorithm. Due to the
interest generated by these demos, I have decided to make this page
available online in a "self-guided demo" format.
The random walker segmentation
algorithm is a recently developed, general-purpose interactive
segmentation method using a "graph cuts" interface. The
algorithm was originally described in
a conference paper
extended in 2005,
and published in journal form in 2006.
This video shows a user
identifying four different objects (cerebellum, corpus callosum,
brainstem and background) by using the mouse to "paint" the different
objects with different colors. The solution is computed using an
iterative linear system solver (conjugate gradients) on the GPU and
the on-screen solution is updated every ten iterations until
convergence. After the solution has converged, the user may use
the mouse to quickly edit the results by adding more paint.
A primary feature of
the random walker algorithm is the ability to "complete" missing
boundaries in a segmentation problem. As an illustration, first
consider this simple segmentation problem of seperating two touching
triangles with a high-contrast, consistent boundary:
Original, trivial segmentation problem, with input seeds
Segmented image (segmentation boundary in
boundaries (or boundary models) are rarely so consistent in real
images. In real images, it is much more common for a boundary to
be missing data. A primary strength of the random walker
segmentation approach is a natural ability to perform the segmentation
even in the presence of a degraded boundary. As a first example,
consider the "touching triangles" image again, but now with a missing
part of the boundary. Note that these images are synthetic and,
therefore, there is no contrast at the missing part of the
Original "Broken Line" image with input seeds
(segmentation boundary in orange)
In addition to a signal dropout on the boundary, the
boundary may also be degraded due to noise. In the two images
below, the "touching triangles" example is repeated again, except now
the boundary has been degraded with a large block of noise.
Original "Noisy Line" image with input seeds
(segmentation boundary in
There's nothing special about diagonal
segments or on-axis noise, either:
This property of weak/noisy boundary resistance is
crucial in the segmentation of real-world images. For example,
this lung tumor image has no contrast between the tumor intensity and
the lung wall tissue intensity, yet the random walker algorithm is
capable of performing the segmentation:
Original image - Note lack
of contrast between tumor and
Segmented image - Segmentation boundary shown in orange
Therefore, the primary characteristics of the random
walker algorithm are: 1) Versitility and 2) Weak/noisy boundary
detection. The video below demonstrates both properties.
First, the user selects the lung tumor with a weak boundary.
Then, without any change to the algorithm, the user is able to segment
the entire lung (including the tumor). Note that all videos are
shown in real-time.
The random walker
algorithm also operates in 3D (in fact, the algorithm works on a
general graph). This video demonstrates that it is only
necessary to place seeds on a single slice in order to get a 3D
segmentation. The segmentation target is the aorta in a
low-resolution CT scan.
There is much more to
say about the random walker algorithm and its relationship to other
leading segmentation algorithms (most notably, the "graph cuts"
technique). If you are interested in looking into the details of
the algorithm, please see the PAMI paper. Please feel free to
re-use any of this material, and don't hesitate to contact me with
questions/comments about the work or this self-guided demo.