Watershed - operates differently to description

[Jeremy Adler]

I have been playing the with watershed binary operation - it seems to work differently from the description provided.
       The description says watershed makes an erode to ultimate points, then dilates the points without allowing merging while keeping within the bounds of original binary object.
        see attached stack
The attached stack of images suggests it operated differently - based on the description of the watershed the object should be split midway between the two ultimate points - but it actually divides at a more sensible place.

my guess is that the software is examining the line of pixels between the two ultimate points, using the distance transform, and making the divide at the minima along this line.

In its current form the watershed is much better than described, but exactly how  is the watershed in ImageJ operating ?
--
ImageJ mailing list: http://imagej.nih.gov/ij/list.html

[Michael Schmid]

Hi Jeremy,

yes, Process>Binary>Watershed works on the Euclidian Distance Map (EDM) of an image.

It starts with the 'Ultimate Points". These points are found as local maxima of the EDM, similar to Process>Find Maxima, but with a small correction because an actual maximum can be between pixels. A ridge of the EDM running at some angle will sometimes be at a pixel center, sometimes just between pixels, which would give different height. The correction takes this into account.

Then the EDM is reduced to a maximum of 254 levels irrespective of particle size. Thus the steps of the EDM are not corresponding to a pixel distance of 1 in case of particles more than 508 pixels across. (The reason: The code still stems from the old days when EDMs were restricted to 8 bits; the highest level is used for the ultimate points, and the lowest level for the background.)

Then a dilation operation is performed for each level of the EDM, starting from the highest one (the ultimate points). If dilations from different sides meet, a division line remains.

So the actual process is a mixture of stepping down the EDM and dilation. Except for large particles, you will get a reasonably good watershed of the EDM, without much influence of the 'dilation' component. What remains as a consequence of the dilation-based algorithm is a tendency of the division lines to sometimes run along horizontal or vertical directions, not in the steepest slope direction.
(A few years I tried to fix this but the code became very awful and unreadable, so I did not pursue that project any further).

Michael
________________________________________________________________
On May 19, 2015, at 16:01, Jeremy Adler wrote:

>
> I have been playing the with watershed binary operation - it seems to work differently from the description provided.
>       The description says watershed makes an erode to ultimate points, then dilates the points without allowing merging while keeping within the bounds of original binary object.
>        see attached stack
> The attached stack of images suggests it operated differently - based on the description of the watershed the object should be split midway between the two ultimate points - but it actually divides at a more sensible place.
>
> my guess is that the software is examining the line of pixels between the two ultimate points, using the distance transform, and making the divide at the minima along this line.
>
> In its current form the watershed is much better than described, but exactly how  is the watershed in ImageJ operating ?
> --
> ImageJ mailing list: http://imagej.nih.gov/ij/list.html
> <ImageJ Watershed demo.tif>

--
ImageJ mailing list: http://imagej.nih.gov/ij/list.html

[Gabriel Landini]

On Tuesday 19 May 2015 14:01:08 Jeremy Adler wrote:
> my guess is that the software is examining the line of pixels between the
> two ultimate points, using the distance transform, and making the divide at
> the minima along this line.

Hi,
I think another (however more convoluted) way to achieve that result is:

1) find out how many ultimate points there are (in this case n=2),

2) go back to the original and sequentially erode only until you have 2 blobs,

3) now sequentially dilate without merging inside the original (as a mask,
that is: no_merge_dilation AND original) until idempotence.

I think (but haven't tried) that would get round the 254 EDM levels limitation
that Michael mentioned?
 
Cheers

Gabriel

--
ImageJ mailing list: http://imagej.nih.gov/ij/list.html

[Gabriel Landini]

On Tuesday 19 May 2015 16:22:30 I wrote:
> I think another (however more convoluted) way to achieve that result is:

Well, I tried what I suggested in my previous email, but it is not exactly the
same as the IJ watershed separation because eroding until obtaining the
expected number of blobs does not guarantee that the seeds are placed in the
same regions as the ultimate points.

Although it works fine in the example posted, it can result in segmentation in
the wrong place in other cases.
Cheers

Gabriel

--
ImageJ mailing list: http://imagej.nih.gov/ij/list.html