Abstract.
For many medical segmentation tasks, the contrast along most of the boundary of the target ob ject is high, allowing simple thresh- olding or region growing approaches to provide nearly sufficient solu- tions for the task. However, the regions recovered by these techniques frequently leak through bottlenecks in which the contrast is low or non- existent. We propose a new approach based on a novel speed-up of the isoperimetric algorithm [1] that can solve the problem of leaks through a bottleneck. The speed enhancement converts the isoperimetric segmen- tation algorithm to a fast, linear-time computation by using a tree repre- sentation as the underlying graph instead of a standard lattice structure. In this paper, we show how to create an appropriate tree substrate for the segmentation problem and how to use this structure to perform a linear- time computation of the isoperimetric algorithm. This approach is shown to overcome common problems with watershed-based techniques and to provide fast, high-quality results on large datasets.