  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 goal of this framework is -- rather than
improving the segmentation quality compared to the baseline method -- to make
interactive segmentation on out-of-core datasets possible. The method is
evaluated quantitavely on synthetic data and the CT-ORG dataset where the
expected improvements in algorithm run time while maintaining high segmentation
quality are confirmed. 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. In a small case study the applicability to large real world
from current biomedical research is demonstrated. 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/).
