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/).
翻译:图像分割的随机漫步器方法是一个常见的半自动图像分割工具,特别是在生物医学领域。然而,其线性无症状运行时间和内存要求使得3D数据集的应用不切实际。我们建议了一个等级框架,根据我们所知,这是为随机漫步算法克服这些限制并实现亚线运行时间和恒定记忆复杂性的首次尝试。这个框架的目标是 -- -- 而不是提高与基线方法相比的分离质量 -- -- 使核心数据集外的交互分割成为可能。该方法对合成数据和CT-ORG数据集进行了量度评估,在这些数据中,算法运行时间的预期改进在保持高分割质量的同时得到了确认。递增(即互动更新)运行时间在标准PC的几秒钟内,即使数量达数百千兆字节。在一个小的案例研究中,演示了当前生物医学研究对大现实世界的可适用性。所展示的方法在广泛使用的卷积/Vreen/Vorimeen软件的5.2版本中公开提供。