  The random walker method for image segmentation is a popular tool for
semi-automatic image segmentation, especially in the biomedical field. However,
its linear asymptotic run time and memory requirements make application to 3D
datasets of increasing sizes impractical. We propose a hierarchical framework
that, to the best of our knowledge, is the first attempt to overcome these
restrictions for the random walker algorithm and achieves sublinear run time
and constant memory complexity. The method is evaluated on synthetic data and
real data from current biomedical research, where high segmentation quality is
quantitatively confirmed and visually observed, respectively. The incremental
(i.e., interaction update) run time is demonstrated to be in seconds on a
standard PC even for volumes of hundreds of Gigabytes in size. An
implementation of the presented method is publicly available in version 5.2 of
the widely used volume rendering and processing software Voreen
(https://www.uni-muenster.de/Voreen/).
