Abstract
The watershed transformation is an efficient tool for segmenting grayscale images. An original approach to the watershed [1,4] consists in modifying the original image by lowering some points until stability while preserving some topological properties, namely, the connectivity of each lower cross-section. Such a transformation (and its result) is called a topological watershed. In this paper, we propose quasi-linear algorithms for computing topological watersheds. These algorithms are proved to give correct results with respect to the definitions, and their time complexity is analyzed.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Bertrand, G.: On topological watersheds. Journal of Mathematical Imaging and Vision 22, 217–230 (2005)
Beucher, S., Lantuéjoul, C.: Use of watersheds in contour detection. In: Proc. Int. Workshop on Image Processing, Real-Time Edge and Motion Detection/Estimation, Rennes, France (1979)
Beucher, S., Meyer, F.: The morphological approach to segmentation: the watershed transformation. In: Dougherty (ed.) Mathematical Morphology in Image Processing, Ch. 12, Marcel Dekker, pp. 433–481 (1993)
Couprie, M., Bertrand, G.: Topological grayscale watershed transformation. In: Proc. SPIE Vision Geometry VI, vol. 3168, pp. 136–146 (1997)
Couprie, M., Najman, L., Bertrand, G.: Quasi-linear algorithms for the topological watershed. Journal of Mathematical Imaging and Vision 22, 231–249 (2005)
Meyer, F.: Un algorithme optimal de ligne de partage des eaux. In: AFCET Ed., Proc. 8th Conf. Reconnaissance des Formes et Intelligence Artificielle, Lyon, vol. 2, pp. 847–859 (1991)
Najman, L., Couprie, M.: Quasi-linear algorithm for the component tree. In: Proc. SPIE Vision Geometry XII, vol. 5300, pp. 98–107 (2004)
Najman, L., Couprie, M., Bertrand, G.: Watersheds, extension maps, and the emergence paradigm, report IGM2004-04 of the Institut Gaspard Monge (University of Marne-la-Vallée), to appear in Discrete Applied Mathematics (2004)
Roerdink, J., Meijster, A.: The watershed transform: definitions, algorithms and parallelization strategies. In: Fundamenta Informaticae, vol. 41, pp. 187–228 (2000)
Tarjan, R.E.: Disjoint sets. In: Data Structures and Network Algorithms, Ch. 2, pp. 23–31. SIAM, Philadelphia (1978)
Thorup, M.: On RAM priority queues. In: 7th ACM-SIAM Symposium on Discrete Algorithms, pp. 59–67 (1996)
Vincent, L., Soille, P.: Watersheds in digital spaces: an efficient algorithm based on immersion simulations. IEEE Trans. on PAMI 13(6), 583–598 (1991)
Vincent, L.: Morphological Grayscale Reconstruction in Image Analysis: Application and Efficient Algorithms. IEEE Trans. on PAMI 2(2), 176–201 (1993)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Couprie, M., Najman, L., Bertrand, G. (2005). Algorithms for the Topological Watershed. In: Andres, E., Damiand, G., Lienhardt, P. (eds) Discrete Geometry for Computer Imagery. DGCI 2005. Lecture Notes in Computer Science, vol 3429. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-31965-8_17
Download citation
DOI: https://doi.org/10.1007/978-3-540-31965-8_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-25513-0
Online ISBN: 978-3-540-31965-8
eBook Packages: Computer ScienceComputer Science (R0)
