Watershed (algorithm)
Encyclopedia
A grey-level image may be seen as a topographic relief, where the grey level of a pixel is interpreted as its altitude in the relief.
A drop of water falling on a topographic relief flows along a path to finally reach a local minimum. Intuitively, the watershed of a relief correspond to the limits of the adjacent catchment basins of the drops of water.
In image processing
, different watershed lines may be computed. In graphs, some may be defined on the nodes, on the edges, or hybrid lines on both nodes and edges. Watersheds may also be defined in the continuous domain . There are also many different algorithms to compute watersheds.
For a segmentation
purpose, the length of the gradient is interpreted as elevation information.
1. Label each minimum with a distinct label. Initialize a set S with the labeled nodes.
2. Extract from S a node x of minimal altitude F, that is to say F(x) = min{F(y)|y in S}.
Attribute the label of x to each non labeled node y adjacent to x, and insert y in S.
3. Repeat Step 2. Until S is empty.
A function W is a watershed of a function F if and only if W ≤ F and W preserves the contrast between the regional minima of F; where the contrast between two regional minima M1 and M2 is defined as the minimal altitude to which one must climb in order to go from M1 to M2.
.
The algorithm works on a gray scale image. During the successive flooding of the grey value relief, watersheds with adjacent catchment basins are constructed. This flooding process is performed on the gradient image, i.e. the basins should emerge along the edges. Normally this will lead to an over-segmentation of the image, especially for noisy image material, e.g. medical CT data. Either the image must be pre-processed or the regions must be merged on the basis of a similarity criterion afterwards.
The non-labeled pixels are the watershed lines.
through an equivalence theorem, their optimality in terms of minimum spanning forests. Afterward, they introduce a linear-time algorithm to compute them. It is worthwhile to note that similar properties are not verified in other frameworks and the proposed algorithm is the most efficient existing algorithm, both in theory and practice.
to optimal spanning forests. More precisely, they show that when the power of the weights of the graph is above a certain number, the cut minimizing the graph cuts energy is a cut by maximum spanning forest.
algorithm is a segmentation algorithm solving the combinatorial Dirichlet problem
, adapted to image segmentation by L. Grady in 2006 .
In 2009, C. Couprie et al. proved that when the power of the weights of the graph converge toward infinity, the cut minimizing the random walker energy is a cut by maximum spanning forest .
A drop of water falling on a topographic relief flows along a path to finally reach a local minimum. Intuitively, the watershed of a relief correspond to the limits of the adjacent catchment basins of the drops of water.
In image processing
Image processing
In electrical engineering and computer science, image processing is any form of signal processing for which the input is an image, such as a photograph or video frame; the output of image processing may be either an image or, a set of characteristics or parameters related to the image...
, different watershed lines may be computed. In graphs, some may be defined on the nodes, on the edges, or hybrid lines on both nodes and edges. Watersheds may also be defined in the continuous domain . There are also many different algorithms to compute watersheds.
For a segmentation
Segmentation (image processing)
In computer vision, segmentation refers to the process of partitioning a digital image into multiple segments . The goal of segmentation is to simplify and/or change the representation of an image into something that is more meaningful and easier to analyze...
purpose, the length of the gradient is interpreted as elevation information.
Watershed by flooding
The idea has been introduced in 1979 by S. Beucher and C. Lantuéjoul in . It consists in placing a water source in each regional minimum, to flood the relief from sources, and build barriers when different sources are meeting. The resulting set of barriers constitutes a watershed by flooding.Watershed by topographic distance
Intuitively, a drop of water falling on a topographic relief flows most rapidly toward a minimum. The previous definition does not verify this condition.Inter-pixel watershed
S. Beucher and F.Meyer introduced in an algorithmic inter-pixel definition of the watershed, given the following procedure:1. Label each minimum with a distinct label. Initialize a set S with the labeled nodes.
2. Extract from S a node x of minimal altitude F, that is to say F(x) = min{F(y)|y in S}.
Attribute the label of x to each non labeled node y adjacent to x, and insert y in S.
3. Repeat Step 2. Until S is empty.
Topological watershed
Previous notions focus on catchment basins, but not to the produced separating line. The topological watershed was introduced by M. Couprie and G. Bertrand in 1997, and beneficiate of the following fundamental property.A function W is a watershed of a function F if and only if W ≤ F and W preserves the contrast between the regional minima of F; where the contrast between two regional minima M1 and M2 is defined as the minimal altitude to which one must climb in order to go from M1 to M2.
Algorithms
Different approaches may be employed to use the watershed principle for image segmentationSegmentation (image processing)
In computer vision, segmentation refers to the process of partitioning a digital image into multiple segments . The goal of segmentation is to simplify and/or change the representation of an image into something that is more meaningful and easier to analyze...
.
- Local minima of the gradient of the image may be chosen as markers, in this case an over-segmentation is produced and a second step involves region merging.
- Marker based watershed transformation make use of specific marker positions which have been either explicitly defined by the user or determined automatically with morphological operators or other ways.
Meyer's flooding algorithm
One of the most common watershed algorithms was introduced by F. Meyer in the early 90's.The algorithm works on a gray scale image. During the successive flooding of the grey value relief, watersheds with adjacent catchment basins are constructed. This flooding process is performed on the gradient image, i.e. the basins should emerge along the edges. Normally this will lead to an over-segmentation of the image, especially for noisy image material, e.g. medical CT data. Either the image must be pre-processed or the regions must be merged on the basis of a similarity criterion afterwards.
- A set of markers, pixels where the flooding shall start, are chosen. Each is given a different label.
- The neighboring pixels of each marked area are inserted into a priority queue with a priority level corresponding to the gray level of the pixel.
- The pixel with the highest priority level is extracted from the priority queue. If the neighbors of the extracted pixel that have already been labeled all have the same label, then the pixel is labeled with their label. All non-marked neighbors that are not yet in the priority queue are put into the priority queue.
- Redo step 3 until the priority queue is empty.
The non-labeled pixels are the watershed lines.
Optimal Spanning Forest algorithms (watershed cuts)
Watersheds as optimal spanning forest have been introduced by Jean Cousty et al. They establish the consistency of these watersheds: they can be equivalently defined by their “catchment basins” (through a steepest descent property) or by the “dividing lines” separating these catchment basins (through the drop of water principle). Then they prove,through an equivalence theorem, their optimality in terms of minimum spanning forests. Afterward, they introduce a linear-time algorithm to compute them. It is worthwhile to note that similar properties are not verified in other frameworks and the proposed algorithm is the most efficient existing algorithm, both in theory and practice.
Graph Cuts
In 2007, C. Allène et al. established links relating Graph CutsGraph cuts in computer vision
As applied in the field of computer vision, graph cuts can be employed to efficiently solve a wide variety of low-level computer vision problems , such as image smoothing, the stereo correspondence problem, and many other computer vision problems that can be formulated in terms of energy minimization...
to optimal spanning forests. More precisely, they show that when the power of the weights of the graph is above a certain number, the cut minimizing the graph cuts energy is a cut by maximum spanning forest.
Shortest Path Forests
The image foresting transform (IFT) of Falcao et al. is a procedure computing shortest path forests. It has been proved by J. Cousty et al. that when the markers of the IFT corresponds to extrema of the weight function, the cut induced by the forest is a watershed cut.Random Walker
The Random WalkerRandom Walker (Computer Vision)
The random walker algorithm is an algorithm for image segmentation. In the first description of the algorithm, a user interactively labels a small number of pixels with known labels , e.g., "object" and "background"...
algorithm is a segmentation algorithm solving the combinatorial Dirichlet problem
Dirichlet problem
In mathematics, a Dirichlet problem is the problem of finding a function which solves a specified partial differential equation in the interior of a given region that takes prescribed values on the boundary of the region....
, adapted to image segmentation by L. Grady in 2006 .
In 2009, C. Couprie et al. proved that when the power of the weights of the graph converge toward infinity, the cut minimizing the random walker energy is a cut by maximum spanning forest .
Hierarchies
A hierarchic watershed transformation converts the result into a graph display (i.e. the neighbor relationships of the segmented regions are determined) and applies further watershed transformations recursively.Works cited
- Fernand Meyer. Un algorithme optimal pour la ligne de partage des eaux. Dans 8me congrès de reconnaissance des formes et intelligence artificielle, Vol. 2 (1991), pages 847-857, Lyon, France.
- Luc Vincent and Pierre Soille. Watersheds in digital spaces: an efficient algorithm based on immersion simulations. In IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 13, Num. 6 (1991), pages 583-598.
- L. Najman and M. Schmitt. Geodesic saliency of watershed contours and hierarchical segmentation. In IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 18, Num. 12 (1996), pages 1163-1173.
- J.B.T.M. Roerdink and A. Meijster. The watershed transform: definitions, algorithms, and parallelization strategies. In Fundamenta Informaticae 41 (2000), pp. 187–228.
- Laurent Najman, Michel Couprie and Gilles Bertrand. Watersheds, mosaics, and the emergence paradigm. In Discrete Applied Mathematics, Vol. 147, Num. 2-3(2005), Pages 301-324.
External links
- The Watershed Transformation with animations of the watershed algorithm.
- Topological Watershed Transform with papers, lecture slides and source code.
- An open source watershed plugin for ImageJImageJImageJ is a public domain, Java-based image processing program developed at the National Institutes of Health. ImageJ was designed with an open architecture that provides extensibility via Java plugins and recordable macros. Custom acquisition, analysis and processing plugins can be developed using...
. - An introduction of principle among other segmentation algorithms
- A presentation of the Image Foresting transform, based on shortest path forests