IWT - Interactive Watershed Transform: A hierarchical method for efficient interactive and automated segmentation of multidimensional grayscale images

In this paper we present the Interactive Watershed Transform (IWT) for efficient segmentation of multidimensional grayscale images. The IWT builds upon a fast immersion-based watershed transform (WT) followed by a hierarchical organization of the resulting basins in a tree structure. Each local image minimum is represented as an atomic basin at the lowest hierarchy level. The fast WT consists of two steps. First, all image elements are sorted according to their image intensity using a Bucket Sort algorithm. Second, each element is processed exactly once with respect to its neighborhood (e. g., 4, 6, and 8 direct neighbors for 2d, 3d, and 4d transform, respectively) in the specified order. Sorting, processing, and tree generation are of order O(n). After computing the WT, one global parameter, the so-called preflooding height, and an arbitrary number of markers are evaluated in real-time to control tree partitioning and basin merging. The IWT has been successfully applied to a large variety of medical images, e. g., for segmentation and volumetry of neuroanatomic structures as well as bone segmentation, without making assumptions on the objects' shapes. The IWT combines automation and efficient interactive control in a coherent algorithm while completely avoiding oversegmentation which is the major problem of the classical WT.