Watershed (algorithm)

In the study of image processing, a watershed is a transformation defined on a grayscale image. The name refers metaphorically to a geological watershed, or drainage divide, which separates adjacent drainage basins. The watershed transformation treats the image it operates upon like a topographic map, with the brightness of each point representing its height, and finds the lines that run along the tops of ridges.

There are different technical definitions of a watershed. In graphs, watershed lines 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. Watershed algorithm is used in image processing primarily for segmentation purposes.

Relief of the gradient magnitude

Gradient magnitude image

Watershed of the gradient

Watershed of the gradient (relief)

In geology, a watershed is a divide that separates adjacent catchment basins.

The idea was introduced in 1979 by S. Beucher and C. Lantuéjoul. The basic idea consisted of placing a water source in each regional minimum in the relief, to flood the entire relief from sources, and build barriers when different water sources meet. The resulting set of barriers constitutes a watershed by flooding. A number of improvements, collectively called Priority-Flood, have since been made to this algorithm.

Intuitively, a drop of water falling on a topographic relief flows towards the "nearest" minimum. The "nearest" minimum is that minimum which lies at the end of the path of steepest descent. In terms of topography, this occurs if the point lies in the catchment basin of that minimum. The previous definition does not verify this condition.

Intuitively, the watershed is a separation of the regional minima from which a drop of water can flow down towards distinct minima. A formalization of this intuitive idea was provided in for defining a watershed of an edge-weighted graph.

S. Beucher and F. Meyer introduced an algorithmic inter-pixel implementation of the watershed method, 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 ∈ S}. Attribute the label of x to each non-labeled node y adjacent to x, and insert y in S.

...
Wikipedia