[Tracking] Implement Watershed Algorithm

[gigony]

This issue is related to #49 and would like to discuss and track the issue here.
(@grlee77 Please feel free to edit/update this description).

Tracking

• Currently collecting information for deciding a proper approach/implementation.

Problem

Watershed algorithm in scikit-image (https://scikit-image.org/docs/dev/api/skimage.segmentation.html?highlight=watershed#skimage.segmentation.watershed) is a popular algorithm for segmentation. However, cuCIM doesn't support it so would like to provide the algorithm through cucim.skimage.segmentation.watershed method.

It turns out that using the same algorithm used in scikit-image with CuPy is not feasible or tricky to implement:

• The watershed itself is implemented in Cython and uses a heap data structure where the elements on the heap are small structs which is not GPU-friendly.

Candidate Implementations

There are some GPU implementations:

1. 2D implementation based on cellular automata in recent NPP

• https://docs.nvidia.com/cuda/npp/group__image__filter__watershed__segmentation.html
• Based on Efficient 2D and 3D Watershed on Graphics Processing Unit: Block-Asynchronous
  Approaches Based on Cellular Automata

2. A different GPU-based algorithm with corresponding citations at watershed-cuda

• https://github.com/louismullie/watershed-cuda
• Can be used under Appach 2.0 license (see skimage.segmentation.watershed implementation? #49 (comment))

3. CLIJ's approach

• https://clij.github.io/clij2-docs/reference_watershed
• Its implementation has some issues (delivers results of limited quality) so alternatives are recommended (see this link)

[isVoid]

Hi there, forgive my intrusion on following questions, as this is my first appearance on the repo. What criterion do you adopt to compare between algorithms?

Since it's about GPU implementations - performance should be one of them. This paper also measures average wall clock time / element (besides wall clock time on image size).

In terms of quality, do you consider over-segmentation problem here? An issue we can alleviate by preprocessing or use provided markers.

[ma-sadeghi]

It would really be great if the implementation supports passing markers (similar to scikit-image's implementation). We make use of the markers extensively in our package porespy.

[ma-sadeghi]

Hi there, just wanted to see if this feature is being worked on. Thanks!

[gigony]

Hi @ma-sadeghi, Thank you for following up on the issue!

We currently don't have the bandwidth to work on it but we'll keep an eye on this feature as the watershed algorithm is widely used.

/cc @grlee77

[rahedges]

I would be interested in using this feature.