Random Walker Segmentation

This page describes how to use the RandomWalker processor to interactively create a high-quality volume segmentation. A multi-label segmentation of our walnut data set generated with this approach is available from the download page.

If you are a developer and want to use the random walker solver directly from your code, we suggest to have a look at the API documentation

Table of Contents

Data-flow

The main component of our random walker implementation is the RandomWalker processor, which is part of the 'randomwalker' module. It expects the volume to segment as well as foreground and background seed points as input. The seed points can be supplied either as point lists (in voxel coordinates) or as mask volumes, in which each non-zero voxel is considered a seed voxel. While all seed inports are technically optional, the random walker solution can only be computed, if at least one foreground and one background seed have been provided.

The RandomWalker processor puts out the computated probability map, in which each voxel is assigned a normalized scalar value specifying the voxel's fuzzy membership to the fore- and background segments. Additionally, a segmentation mask is produced from the probability map by binary thresholding. By default, voxels with a probability value above 0.5 are regarded as foreground voxels, but this threshold is configurable. For debugging purposes, the third outport provides a volume containing the edge weights of the constructed random walker graph.

 

Processor Configuration

The screenshot on the right shows a configuration of the RandomWalker processor in its most basic setup. The main parameters steer the construction of the random walker graph from the input volume , the setup of the conjugate gradient solver that computes the random walker solution on the constructed graph , and the generation of the binary segmentation mask from the probability map . In the following, we describe these parameters in detail.

Besides the provided seed points, the construction of the random walker graph is governed by the edge weight function that assigns weights to edges between neighored voxels/graph nodes. These weights determine the likelihood with which a random walker being located at a certain voxel/graph node chooses a certain neighbor as next step: the higher the weight the higher the chance that the edge is chosen. In order to obtain a meaningful segmentation, we have to somehow derive these edge weights from the underlying volume. In the basic setup, we compute the edge weight from the intensity difference between neighbored voxels. The edge weight function is as follows:

where g_i and g_j are the intensities of the respective voxels and beta is a free parameter that specifies the inverse permeability of boundaries within the volume: the larger beta, the less likely it is that a random walker moves between two voxels with a high intensity differential. The parameter beta is refered to as "Edge Weight Scale" in the user interface and is specified in exponential form, e.g., Edge Weight Scale=12  =>  beta=2^12=4096. In addition, a minimum edge weight can be specified in order to prevent unseeded regions with a strong surrounding boundary to become unconnected in the constructed graph (the edge weight might attain zero due to limited floating point precision). Note that the random walker solution is only defined on a connected graph.

The computation of the random walker solution requires us to solve a large linear equation system, which contains one equation for each unseeded voxel. We use a conjugate gradient solver, which expects the preconditioner to use, the error threshold at which the approximate solution is considered to be correct, and the maximum number of conjugate gradient descents to perform. A smaller error threshold and a higher max iteration value yield more precise results at the expense of a longer computation time. Finally, the conjugate gradient solver implementation to use can be chosen out of three options: a single-threaded CPU version, a OpenMP-parallelized CPU version (requires the 'openmp' module), and a high performance OpenCL version (requires the 'opencl' module). Due to the high computational cost of solving the random walker equation system, we strongly recommend to use the OpenCL implementation!

The solution of the random walker problem yields a normalized probability map that assigns a scalar foregound membership score to each voxel of the input volume. Although this probability map itself can already be regarded as a fuzzy volume segmentation, we are usually interested in a crisp segmentation, which can be obtained by binary thresholding the probability map. The foreground/background separation threshold can be configured in the "Output" section.
 

Ready-to-use Workspaces

Since the random walker is semi-automatic segmentation approach, we have to integrate the seed point definition into a segmentation network. Furthermore, a visual inspection of the generated segmentation in 2D and 3D would be useful. The 'randomwalker' module comes with some pre-defined workspaces that provide that functionality (modules/randomwalker/workspaces):

  • randomwalker-1Dseeds.vws: allows the user to define seed points on axis-aligned slices along one major axis of the volume
  • randomwalker-3Dseeds.vws: allows the user to define seed points on axis-aligned slices along all three major axes of the volume
  • randomwalker-1Dseeds_walnut.vws, randomwalker-3Dseeds_walnut.vws are segmentation examples using our walnut dataset with some predefined seeds

The image below shows the visual output of the randomwalker-3Dseeds_walnut.vws workspace. It contains three axis-aligned slices with foreground (red) and background (blue) seeds painted onto them. The current segmentation boundary is overlaid in yellow. Please note that the boundary is not displayed as a sharp line, but rather fans out at some sections. These "unsharp" parts of the boundary indicate ambiguous regions in the probabilistic segmentation at which the user should place additional seeds in order to guide the algorithm and thereby refine the result. The 3D view in the upper left provides contextual information about the location of the currently selected slices in the volume and also shows a 3D visualization of the segmentation.

The workflow for segmenting your own data would be as follows:

  1. Load the data set via the VolumeSource.
     
  2. Adjust the transfer function of the slice viewers to maximize contrast (the transfer functions are linked, so you need to adjust only one of them).
     
  3. Define seeds points by painting onto the slice views:
    - CTRL+Left-Mouse-Drag adds a foreground seed stroke
    - ALT+Left-Mouse-Drag adds a background seed stroke
    CTRL+Right-Mouse-Click removes the last foreground stroke
    - ALT+Right-Mouse-Click removes the last background stroke
     
  4. Hit "Compute" button of the RandomWalker processor.
     
  5. Inspect the segmentation and repeat steps 3-4 until satisfied with the result.
     
  6. Use the VolumeSave processors to export the segmentation.