The flooding algorithm step by step
Optional · supplementary note 5 of 6 for IP 10 · Image Segmentation I: Edge Detection, Thresholding, and Region Detection. Nothing in the main text depends on it; citation numbers refer to the reference list at the bottom of this page.
Navigate: this page and this track: Navigate: this page and this track
The watershed treats an image (usually a gradient magnitude) as a landscape and floods it from its regional minima.
A dam is built with the morphology of IP 09. When two flooded components are about to merge, dilate both with a structuring element, restricted to pixels below the current level; pixels reached by both in the same step become dam pixels, set higher than the image maximum. The dams are one pixel thick and connected.
Let be the regional minima of an image , let and be its extreme values, and let be the set of pixels below level . Let be the union of the flooded parts of all catchment basins at level . Flooding proceeds for . Start with . At each level, take each connected component of and compare it with :
- is empty: a new minimum has appeared; becomes a new basin.
- contains one component of : lies inside one existing basin; add it.
- contains two or more components: two basins are meeting; build a dam inside as described above.
References
- R. C. Gonzalez and R. E. Woods, Digital Image Processing, 4th ed., Pearson, 2018, Ch. 10. publisher page
- D. Marr and E. Hildreth, “Theory of edge detection,” Proceedings of the Royal Society of London. Series B, vol. 207, no. 1167, pp. 187–217, 1980. doi
- J. Canny, “A Computational Approach to Edge Detection,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. PAMI-8, no. 6, pp. 679–698, 1986. doi
- R. O. Duda and P. E. Hart, “Use of the Hough transformation to detect lines and curves in pictures,” Communications of the ACM, vol. 15, pp. 11–15, 1972. doi
- N. Otsu, “A Threshold Selection Method from Gray-Level Histograms,” IEEE Transactions on Systems, Man, and Cybernetics, vol. 9, no. 1, pp. 62–66, 1979. doi
- M. Sezgin and B. Sankur, “Survey over image thresholding techniques and quantitative performance evaluation,” Journal of Electronic Imaging, vol. 13, no. 1, pp. 146–165, 2004. doi
- J. Sauvola and M. Pietikäinen, “Adaptive document image binarization,” Pattern Recognition, vol. 33, no. 2, pp. 225–236, 2000. doi
- R. Achanta, A. Shaji, K. Smith, A. Lucchi, P. Fua and S. Süsstrunk, “SLIC Superpixels Compared to State-of-the-Art Superpixel Methods,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 34, no. 11, pp. 2274–2282, 2012. doi
- J. Shi and J. Malik, “Normalized cuts and image segmentation,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 22, no. 8, pp. 888–905, 2000. doi
- L. Vincent and P. Soille, “Watersheds in digital spaces: an efficient algorithm based on immersion simulations,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 13, no. 6, pp. 583–598, 1991. doi
- S. Minaee, Y. Boykov, F. Porikli, A. Plaza, N. Kehtarnavaz and D. Terzopoulos, “Image Segmentation Using Deep Learning: A Survey,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 44, no. 7, pp. 3523–3542, 2022. doi · arXiv
- T. Zhou, W. Xia, F. Zhang, B. Chang, W. Wang, Y. Yuan, E. Konukoglu and D. Cremers, “Image Segmentation in Foundation Model Era: A Survey,” arXiv:2408.12957, 2024. arXiv
- J. Long, E. Shelhamer and T. Darrell, “Fully Convolutional Networks for Semantic Segmentation,” arXiv:1411.4038, 2014. arXiv
- O. Ronneberger, P. Fischer and T. Brox, “U-Net: Convolutional Networks for Biomedical Image Segmentation,” in Medical Image Computing and Computer-Assisted Intervention – MICCAI 2015, Lecture Notes in Computer Science, vol. 9351, pp. 234–241, Springer, 2015. doi · arXiv
- K. He, G. Gkioxari, P. Dollár and R. Girshick, “Mask R-CNN,” arXiv:1703.06870, 2017. arXiv
- L.-C. Chen, G. Papandreou, I. Kokkinos, K. Murphy and A. L. Yuille, “DeepLab: Semantic Image Segmentation with Deep Convolutional Nets, Atrous Convolution, and Fully Connected CRFs,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 40, no. 4, pp. 834–848, 2018. doi · arXiv
- A. Kirillov, E. Mintun, N. Ravi et al., “Segment Anything,” arXiv:2304.02643, 2023. arXiv
- R. Sun, T. Lei, Q. Chen, Z. Wang, X. Du, W. Zhao and A. K. Nandi, “Survey of Image Edge Detection,” Frontiers in Signal Processing, 2022. doi
- S. Xie and Z. Tu, “Holistically-Nested Edge Detection,” arXiv:1504.06375, 2015. arXiv
- D. Stutz, A. Hermans and B. Leibe, “Superpixels: An Evaluation of the State-of-the-Art,” Computer Vision and Image Understanding, vol. 166, pp. 1–27, 2018. doi
- I. Arganda-Carreras, S. C. Turaga, D. R. Berger et al., “Crowdsourcing the creation of image segmentation algorithms for connectomics,” Frontiers in Neuroanatomy, vol. 9, 2015. doi
- M. Maška, V. Ulman, D. Svoboda et al., “A benchmark for comparison of cell tracking algorithms,” Bioinformatics, vol. 30, no. 11, pp. 1609–1617, 2014. doi · Cell Tracking Challenge