An implementation of the surprisingly simple $O(n)$ watershed cuts (WSC) algorithm from Cousty et al. ¹. While the algorithm is presented in the framework of undirected graphs the code in this repo only runs on 2D and 3D images and the graph structure is implicit by using 4-connectivity in 2D and 6-connectivity in 3D.

There are a few choices to make, one of them is how to define the function on the edges, $F(\{x,y\})$ where $\{x,y\}$ denotes the connecting vertex $x$ and $y$.

This implementation use

$$F(\{x,y\}) = \min \left( I(x) , I(y) \right)$$

which give the standard watershed behavior. Another option, suggested in the paper, is

$$F(\{x,y\}) = | I(x) - I(y) |$$

which has the property that it locates the boundaries of the watershed regions along image edges.

Performance

An obvious difference to the standard watershed methods is the lack of contours or watersheds between labeled regions. The actual boundaries are on the graph edges, i.e., between the pixels.

Below is an example image demonstrating the differences in output from the watershed² function in MATLAB. In the bottom-right image boundary pixels are artificially introduced (pixels set to 0 when they differ from the erosion by a small structuring element, see matlab/test_watershed_cuts.m).

Here is another example, borrowed from the documentation of watershed showing the result of watershed cuts to the right.

A quick benchmark on images of size $\left[n \times n \times n\right]$ reveals that WSC has a competitive performance.

In the table below this implementation of WSC is compared to the watershed implementation in MATLAB R2020b and he one in DIPlib ³. Using two types of images: "flat", where all pixels are set to 0 and "rand" where pixels got a random value. Timing are reported in seconds. Interestingly, WSC is faster on complex images than on simple, this is due to more cache-misses in the latter case.

n	MATLAB/flat	MATLAB/rand	WSC/flat	WSC/rand	DIPlib/flat	DIPlib/rand
128	0.31	1.3	0.11	0.060	0.072	0.47
256	2.3	15	1.2	0.52	0.65	6.3
512	19	150	11	5.2	5.3	64

At some point it could be interesting to compare this to the implementation scikit-image for Python ⁴.

Footnotes

1. Cousty, Jean and Bertrand, Gilles and Najman, Laurent and Couprie, Michel, Watershed Cuts: Minimum Spanning Forests and the Drop of Water Principle, IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009 31(8), pp 1362-1374, doi:10.1109/TPAMI.2008.173 see also [https://perso.esiee.fr/~coustyj/] ↩

2. MATLAB watershed documentation ↩

3. DIPlib watershed documentation ↩

4. scikit-image documentation on watershed there is also a demo ↩