Determining watersheds in digital pictures via flooding simulations
Pierre Soille, Luc M. Vincent · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 1990
The watershed transformation is a very powerful image analysis tool provided by mathematical morphology. However, most existing watershed algorithms are either too time consuming or insufficiently accurate. The purpose of this paper is to introduce a new and flexible implementation of this transformation. It is based on a progressive flooding of the picture and it works for n-dimensional images. Pixels are first sorted in the increasing order of their gray values. Then, the successive gray levels are processed in order to simulate the flooding propagation. A distributive sorting technique combined with breadth-first scannings of each gray level allow an extremely fast computation. Furthermore, the present algorithm is very general since it deals with any kind of digital grid and its extension to general graphs is straightforward. Its interest with respect to image segmentation is illustrated by the extraction of geometrical shapes from a noisy image, the separation of 3-dimensional overlapping particles and by the segmentation of a digital elevation model using watersheds on images and graphs.