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.

Basic Usage
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 in 2004, 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.


Weak Boundary
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 (red/green)                                  Segmented image (segmentation boundary in orange)
                  

However, 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 boundary.
            Original "Broken Line" image with input seeds                                 Segmented image (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                                    Segmented image (segmentation boundary in orange)
              

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 wall                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.




3D
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.



Conclusion
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.