cucim icon indicating copy to clipboard operation
cucim copied to clipboard

skimage.segmentation.watershed implementation?

Open ma-sadeghi opened this issue 3 years ago • 16 comments

Is your feature request related to a problem? Please describe. It's be great if cucim implements skimage's watershed algorithm. watershed is really useful for segmentation and it'd be great if we had a GPU implementation of it.

Describe the solution you'd like Implement skimage's watershed algorithm.

Describe alternatives you've considered None

Additional context None

ma-sadeghi avatar Jun 05 '21 17:06 ma-sadeghi

Thanks @ma-sadeghi for the issue! We had a discussion on this issue before and we found that there are many ways to implement GPU-accelerated watershed algorithms and implementing scikit-image's watershed algorithm directly with CuPy is not feasible or tricky to implement.

We would keep follow up this issue and please let us know if you have any idea/knowledge on GPU-accelerated watershed algorithm.

Thanks!

/cc @grlee77

gigony avatar Jun 09 '21 07:06 gigony

Greg likely has more thoughts here 🙂

Though one thing worth mentioning is we do have a random_walker implementation. Admittedly not exactly what you are looking for, but may still be useful

jakirkham avatar Jun 09 '21 18:06 jakirkham

Looking at the scikit-image watershed demo, the seed points for the watershed are determined via scipy.distance_transform_edt. I did start a CuPy-based implementation for the distance transform based on the code in https://github.com/orzzzjq/Parallel-Banding-Algorithm-plus. I started with the 3D variant and have that working, but wanted to make things a bit more general in terms of not requiring all dimensions of the array to have the same size.

I had not started working on the watershed itself. Some reading turned up some GPU-based implementations in the literature, but I haven't looked into specifics of which might be best to implement. My initial impression of the scikit-image algorithm was that the priority queue data structure approach that is used there would likely not adapt well to the GPU.

grlee77 avatar Jun 15 '21 20:06 grlee77

This reminds me, @JoOkuma pointed me to this watershed implementation, which might also be of interest here 🙂

jakirkham avatar Jun 15 '21 21:06 jakirkham

Hey @jakirkham.

I agree with @gigony, an implementation that produces results equivalent to skimage's watershed is tricky and might not even be that fast.

@alanpeixinho might have the GPU implementation from the article above. However, from my understanding, it does not produce the same results as the original watershed.

JoOkuma avatar Jun 15 '21 22:06 JoOkuma

Two other GPU implementations:

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

2.) A different GPU-based algorithm with corresponding citations at watershed-cuda, but I do not see any license info in that repository. Perhaps @louismullie can indicate if it could be used under an Apache 2.0 or similar license?

grlee77 avatar Jun 15 '21 23:06 grlee77

The implementation on my profile can be used under the Apache 2.0 license.

louismullie avatar Jun 18 '21 20:06 louismullie

The implementation on my profile can be used under the Apache 2.0 license.

Great, thanks @louismullie

grlee77 avatar Jun 19 '21 12:06 grlee77

Any progress on this? @louismullie your implementation only works for 2d, correct?

rijobro avatar Nov 22 '22 12:11 rijobro

Based on recent discussion, another option might be to build on NPP's FloodFill

jakirkham avatar Dec 13 '22 20:12 jakirkham

@jakirkham Would it work for 3D as well?

ma-sadeghi avatar Dec 13 '22 21:12 ma-sadeghi

No it is 2D only

jakirkham avatar Dec 14 '22 00:12 jakirkham

@gigony Could you explain a little bit why porting scikit-image's watershed using cupy is not feasible? Thanks!

ma-sadeghi avatar Dec 14 '22 01:12 ma-sadeghi

Actually Greg's probably the best one to explain that given he's familiar with the scikit-image codebase.

That said, we talked about this again today (hence the comment on this issue). AIUI the primary challenge with the algorithm used in scikit-image is it leverages a priority queue to go through and explore each neighborhood. This isn't particularly friendly for parallelism or working on the GPU. The other algorithms mentioned above may be better for parallelism, but could render results that are qualitatively different from what scikit-image does.

jakirkham avatar Dec 14 '22 01:12 jakirkham

I would like to add that the solution to the watershed is not unique in the tie-zones (objects' boundaries where pixels have the same value). The tie-breaking strategy is usually an implementation detail and will probably yield different results in the GPU implementation.

JoOkuma avatar Dec 14 '22 17:12 JoOkuma

Just noting this is something MONAI had expressed interest in using here.

cc @drbeh

jakirkham avatar Dec 14 '22 21:12 jakirkham