investigate switching KDTree usage from SciPy to CuPy

[grlee77]

trafficstars

CuPy's main branch now has a KDTree implementation (cupyx.scipy.spatial.KDTree). It is not released for CuPy 13.x, but we should investigate whether it provides benefit over falling back to the host side implementation from SciPy.

Functions currently replying on SciPy for use of KDTree are:

• cucim.skimage.feature.corner_peaks
• cucim.skimage.feature.peak_local_max (via private utility function cucim.skimage._shared.ensure_spacing)

Other functions that use it in scikit-image, but for which CuPy has an alternative CUDA kernel is the _prune_blobs helper function used by

• cucim.skimage.feature.blob_dog
• cucim.skimage.feature.blob_doh
• cucim.skimage.feature.blob_log

we can check if that kernel or the CuPy KDTree implementation is preferable.

If CuPy KDTree performance is good we can add implementation for the following scikit-image functions that primarily rely on it

• skimage.metrics.hausdorff_distance
• skimage.metrics.hausdorff_pair
• skimage.transform.hough_circle_peaks

[cb11711211]

Hi, I am current investigate to replace scipy cKDTree with cupy KDTree, and could I provide which version of cupy provide the function?

[monzelr]

in my first implementation for the blob algorithms I have used scipy's cKDTree - because it was a CPU solution it was a bottleneck. I will give cupy's KDtree a try to see the performance

@cb11711211 it is not in the official release, but you find it already in the repository you have to build cupy by yourself to test it