This site is devoted to mathematics and its applications. Created and run by Peter Saveliev.

# Binary watershed

### From Intelligent Perception

According the ImageJ site: “Watershed segmentation is a way of automatically separating or cutting apart particles that touch”.

Suppose black is the particles and white is the background. The the procedure is fairly simple.

First, for each pixel compute the distance to the nearest white pixel. This is called the distance function. It’s a scalar function of two variables.

Next, find the local maximum points of this function. The goal is to make each of these pixels the center of a "particle".

Starting from these pixels as centers, one carries out multiple rounds of dilation that gradually grow the particles. The dilation, however, has to have two restrictions. First, the particles aren’t allowed to grow beyond the original set of black pixels. This way we guarantee that we end up with the same set of pixels, except it has been “cut” into pieces. Second, a new pixel isn’t added if it’s adjacent to a pixel that belongs to another particle. This way the particles start to “push” onto each other but never overlap.

The tricky part of the latter restriction is that the growth rate will have to be different for particles of different sizes. Otherwise, two particles will always be separated by a cut exactly half way between their centers. That wouldn’t make sense if one is significantly larger than the other. Roughly speaking, the rate of the dilation should be proportional to the value of the distance function (or the average distance to a white pixel, etc).

Some questions remain. For example, how does one efficiently find the maxima? Everything is discrete, so forget about derivatives etc. You have to visit every point.

How does one deal with particles that are simply noise? If you remove all small particles, you may have nothing left. One answer usually is to discard the maxima with low values of the distance function; they represent little bumps on the surface of that function.

Another issue is typical for many image analysis techniques. Once again to quote the ImageJ site, “Watershed segmentation works best for smooth convex objects that don't overlap too much.” Basically, the person has to view (i.e., analyze) the image himself and decide ahead of time whether the method is appropriate! And there is a good reason to be cautious – non-convex particles may cause the watershed method to produce undesirable results, below.

Also, you have to choose ahead of time whether you have white or black particles. If you don’t choose correctly, you end up with non-convex black “particles”. Then the result of watershed segmentation isn’t what you expect:

It is also easy to think of an image (rings below) that can’t possibly be analyzed correctly by watershed regardless of the black/white choice:

Needless to say that the topological approach (i.e. Pixcavator) produces the correct segmentation here:

Pixcavator can’t however separate particles yet (the math will appear here under Robustness of topology).

Many examples of image analysis don't require watershed, but some do.

See also Gray scale watershed and Image segmentation.