Comparison between immersion-based and toboggan-based watershed image segmentation

Watershed segmentation has recently become a popular tool for image segmentation. There are two approaches to implementing watershed segmentation: immersion approach and toboggan simulation. Conceptually, the immersion approach can be viewed as an approach that starts from low altitude to high altitude and the toboggan approach as an approach that starts from high altitude to low altitude. The former seemed to be more popular recently (e.g., Vincent and Soille), but the latter had its own supporters (e.g., Mortensen and Barrett). It was not clear whether the two approaches could lead to exactly the same segmentation result and which approach was more efficient. In this paper, we present two "order-invariant" algorithms for watershed segmentation, one based on the immersion approach and the other on the toboggan approach. By introducing a special RIDGE label to achieve the property of order-invariance, we find that the two conceptually opposite approaches can indeed obtain the same segmentation result. When running on a Pentium-III PC, both of our algorithms require only less than 1130 s for a 256 x 256,image and 115 s for a 512 x 512 image, on average. What is more surprising is that the toboggan algorithm, which is less well known in the computer vision community, turns out to run faster than immersion algorithm for almost all the test images we have used, especially when the image is large, say, 512 x 512 or larger. This paper also gives some explanation as to Why the toboggan algorithm can be more efficient in most cases.