TY - JOUR

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

AU - Lin, Yung Chieh

AU - Tsai, Yu Pao

AU - Hung, Yi Ping

AU - Shih, Zen-Chung

PY - 2006/3/1

Y1 - 2006/3/1

N2 - 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 1/30 s for a 256 × 256 image and 1/5 s for a 512 × 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 the immersion algorithm for almost all the test images we have used, especially when the image is large, say, 512 × 512 or larger. This paper also gives some explanation as to why the toboggan algorithm can be more efficient in most cases.

AB - 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 1/30 s for a 256 × 256 image and 1/5 s for a 512 × 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 the immersion algorithm for almost all the test images we have used, especially when the image is large, say, 512 × 512 or larger. This paper also gives some explanation as to why the toboggan algorithm can be more efficient in most cases.

KW - Immersion approach

KW - Order-invariance

KW - Toboggan approach

KW - Watershed image segmentation

UR - http://www.scopus.com/inward/record.url?scp=32944475758&partnerID=8YFLogxK

U2 - 10.1109/TIP.2005.860996

DO - 10.1109/TIP.2005.860996

M3 - Article

C2 - 16519350

AN - SCOPUS:32944475758

SN - 1057-7149

VL - 15

SP - 632

EP - 640

JO - IEEE Transactions on Image Processing

JF - IEEE Transactions on Image Processing

IS - 3

ER -