[FEA] CUDA accelerated foolfill algorithm with distance return

[JonasFrey96]

Hello everyone,

Thanks for the well-maintained and fast image processing library.

Feature Description In robotics, we often would like to solve some planning problem on cost maps - e.g. solving a floodfill algorithm starting from one pixel and knowing the distance to all other pixels while accounting for "untraversable" pixels. Given the similarity to the distance_transform_edt, I was wondering if anyone would be interested in implementing such a feature or can point me to a reference implementation.

A minimum example could look as follows: One would like to start planning at (4,4) and know the distance to all cells. However, only cells contacting a 1 are traversable.

[[1. 1. 1. 1. 1.]
 [1. 2. 1. 1. 1.]
 [1. 2. 1. 1. 1.]  
 [1. 2. 1. 1. 1.]
 [1. 2. 1. 1. 0.]]

The current distance_transform_edt would provide:

[[5.7 5.  4.5 4.1 4. ]
 [5.  4.2 3.6 3.2 3. ]
 [4.5 3.6 2.8 2.2 2. ]
 [4.1 3.2 2.2 1.4 1. ]
 [4.  3.  2.  1.  0. ]] 

However we would like to obtain:

[[5.7   5.  4.5  4.1 4. ]
 [6.7   -1  3.6  3.2 3. ]
 [7.7  -1  2.8  2.2 2. ]
 [8.7  -1  2.2  1.4 1. ]
 [9.7  -1   2.   1.  0. ]] 

If anyone could point me to a fast existing implementation or some ideas on how to achieve this in the best way I would be very glad. Currently, I am looking roughly at a size of (200,200) - (2000,2000) and for a performance below <2ms on a Jetson Orin. Performing the same in 3D would be specifically useful for drones. Specifically thanks a lot @grlee77 for the distance_transform_edt implementation.

[grlee77]

Thanks @JonasFrey96 for the kind words and for providing a concrete example. It helped me to understand what you are asking for. Let me think about it and see what might be the best option.

There is an implementation of flood fill in NPP, but I don't think it will work for your purposes. As far as I understand, it operates more like a paint bucket tool to fill a region around the seed and does not return distances. That also does not currently have Python bindings.

I don't see how to modify the distance transform kernels we have in cuCIM to do this, but am wondering if we might be able to build a graph to represent the image and then use an appropriate graph algorithm from cuGraph to compute the distance. I think this problem may be called "single source shortest path" (SSSP). I am not too familiar with such graph algorithms, but think this could be a possibility worth exploring. I do see SSSP listed under "Traversal" algorithms on this page in the cuGraph guide.

We would have to figure out how to convert a binary image into the graph format it expects. I know upstream scikit-image does have some graph-related algorithms that utilize NetworkX, but we don't currently have any of the skimage.graph module implemented in cuCIM.

[JonasFrey96]

Hello @grlee77,

Thanks a lot for your kind response. I found an efficient workaround by using the FastGeodis library (BSD-3): https://github.com/masadcv/FastGeodis This avoids creating a graph. Creating python bindings for NPP would be most likely the best solution.