Implementation and complexity of the watershed-from-markers algorithm computed as a minimal cost forest

The watershed algorithm belongs to classical algorithms in mathematical mor phology. Lotufo et al. I published a principle of the watershed computation by means of an iterative forest transform (IFT), which computes a shortest path forest from given markers. The algorithm itself was described for a 2 D case (image) without a detailed discussion of its computation and memory demands for real datasets. As IFT cleverly solves the problem of plateaus and as it gives precise resu lts when thin objects have to be segmented, it is obvious to use this algor ithm for 3D datasets taking in mind the minimizing of a higher memory consu mption for the 3D case without loosing low asymptotical time complexity of O(m + C) (and also the real computation speed). The main goal of this paper is an implementation of the IFT algorithm with a priority queue with bucke ts and careful timing of this implementation to reach as minimal memory con sumption as possible. The paper presents five possible modifications and me thods of implementation of the IFT algorithm. All presented implementations keep the time complexity of the standard priority queue with buckets but t he best one minimizes the costly memory allocation and needs only 19-45% of memory for typical 3D medical imaging datasets. Memory saving was reached by an IFT algorithm simplification, which stores more elements in temporary structures but these elements are simpler and thus need less memory. The best presented modification allows segmentation of large 3D medical dat asets (up to 512 x 512 x 680 voxels) with 12- or 16-bits per voxel on curre ntly available PC based workstations.