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

Binary watershed

From Mathematics Is A Science

Jump to: navigation, search

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.

(1) the original image of particles that touch each other, (2) the distance of each pixels to the nearest white pixel is illustrated with its gray level. (3) the result of the watershed transform - the particles are separated

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).

bad watershed - wrong separation (half way) good watershed (the place of the cut is proportional to the sizes of the particles

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:

the negative of the particles image above - now the particles are white watershed results if we if apply the same watershed, meaningless cuts

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:

the image of rings = both white and black circles, which ones are the particles? the result of "black" watershed - meaningless the result of "black" watershed applied to the negative of the image (same as "white" watershed applied to the original) - meaningless too

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

rings image analyzed with Pixcavator the negative of the rings image analyzed with Pixcavator

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.