Watersheds in digital spaces: an efficient algorithm based on immersion simulations
- 1 June 1991
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 13 (6) , 583-598
- https://doi.org/10.1109/34.87344
Abstract
A fast and flexible algorithm for computing watersheds in digital gray-scale images is introduced. A review of watersheds and related motion is first presented, and the major methods to determine watersheds are discussed. The algorithm is based on an immersion process analogy, in which the flooding of the water in the picture is efficiently simulated using of queue of pixel. It is described in detail provided in a pseudo C language. The accuracy of this algorithm is proven to be superior to that of the existing implementations, and it is shown that its adaptation to any kind of digital grid and its generalization to n-dimensional images (and even to graphs) are straightforward. The algorithm is reported to be faster than any other watershed algorithm. Applications of this algorithm with regard to picture segmentation are presented for magnetic resonance (MR) imagery and for digital elevation models. An example of 3-D watershed is also provided.<>Keywords
This publication has 23 references indexed in Scilit:
- Image segmentation techniquesPublished by Elsevier ,2006
- Distance transformations in digital imagesPublished by Elsevier ,2006
- An efficient uniform cost algorithm applied to distance transformsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1989
- Computing distance transformations in convex and non-convex domainsPattern Recognition, 1987
- Grayscale morphologyComputer Vision, Graphics, and Image Processing, 1986
- Topographic Partition of Watersheds with Digital Elevation ModelsWater Resources Research, 1986
- Geodesic methods in quantitative image analysisPattern Recognition, 1984
- Euclidean distance mappingComputer Graphics and Image Processing, 1980
- Sequential Operations in Digital Picture ProcessingJournal of the ACM, 1966
- Sorting by Address CalculationJournal of the ACM, 1956