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.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
Keywords
Computer scienceAlgorithmDigital elevation modelWatershedArtificial intelligencePixelGridQueueImplementationSegmentationImage segmentationDigital imageComputer visionImage processingImage (mathematics)MathematicsRemote sensing
Affiliated Institutions
Related Publications
Region competition: unifying snakes, region growing, energy/Bayes/MDL for multi-band image segmentation
We present a novel statistical and variational approach to image segmentation based on a new algorithm named region competition. This algorithm is derived by minimizing a genera...
Fast segmentation, tracking, and analysis of deformable objects
The authors present a physically based deformable model which can be used to track and analyze non-rigid motion of dynamic structures in time sequences of 2-D or 3-D medical ima...
Entropy-based algorithms for best basis selection
Adapted waveform analysis uses a library of orthonormal bases and an efficiency functional to match a basis to a given signal or family of signals. It permits efficient compress...
Principal warps: thin-plate splines and the decomposition of deformations
The decomposition of deformations by principal warps is demonstrated. The method is extended to deal with curving edges between landmarks. This formulation is related to other a...
A framework for the robust estimation of optical flow
The authors consider the problem of robustly estimating optical flow from a pair of images using a new framework based on robust estimation which addresses violations of the bri...
Publication Info
- Year
- 1991
- Type
- article
- Volume
- 13
- Issue
- 6
- Pages
- 583-598
- Citations
- 5444
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
5444
OpenAlex
Cite This
Luc Vincent,
Pierre Soille
(1991).
Watersheds in digital spaces: an efficient algorithm based on immersion simulations.
IEEE Transactions on Pattern Analysis and Machine Intelligence
, 13
(6)
, 583-598.
https://doi.org/10.1109/34.87344
Identifiers
- DOI
- 10.1109/34.87344