CUDA accelerated Hausdorff distance

[jakubMitura14]

Hello some time ago I had written about proposition of contributing improved CUDA accelerated Hausdorff distance (HD), sorry for a delay .

What should I do next to adapt it, so it could be usefull for You, are there any benchmarks of MONAI Hausdorff distance comparing to other implementations?

First comparison of execution times in plot and in table.

Link to source code of Pytorch CUDA C++ extension [1]
Link to analysis of the benchmarking data [2]

Details:
Algorithms are implemented using mathemathical morphology principles - basically it is heavily modified idea from [3].
There is only CUDA implementation and only metric implemented is L1 metric (no euclidean).
Values of HD are diffrent in case of my implementation than in current MONAI one as it follows dirent methodology yet as shown in table above those values are strongly correlated, with extremely low p-values (also very high values of Bayes Factor - not presented above). Correlation for robust version is moderate.
In case of all implementations The execution time of my algorithm is about 10 times faster than Oliviera [3] algorithm and around 100 times faster than MONAI version. Additionally In case of my algorithm it is possible to establish exactly which voxel was covered in which iteration adding potential possibility for detailed visualization and plotting - if You are intrested I will provide example.

Replication:
CUDA extension is compiled via JIT compilation CUDA 11.3 python 3.6
Execution file is a check.py file.

All was tested on GPU tensors (memory copy times not included - it is assumed we already have a GPU tensor), data was converted to boolean arrays - not required for my algorithm - but simplify comparison.

In [1] there is full code needed for results replication. In order to execute one need to change paths
a) csvPath - path to save csv with results
b) data_dir - folder with files from [4] ; files of volumes should be in subfolder "volumes 0-49" and files with labels in "labels" folder

Dataset is created for multiple organ segmentation and collected from various devices and diffrent studies - such variability is one of the reasons why it was used for benchmarks. Yet becouse of some time constraints I did not run benchmarks on all of the images - How many tests were executed can be seen in added csv.
In benchmarks label from one organ was compared to other organ, with or without affine transformationa and with or without added gaussian noise. The csv file is available at the end of the post.
Below columns in the csv file / variables in benchmark file are described
"noise" - is there added noise
"distortion" - is there added affine transformation
"hdToTestRobustTime" - execution time of MONAI robust ( 0.90 ) Hausdorff distance algorithm
"hdToTestTime" - execution time of MONAI not robust Hausdorff distance algorithm
"avSurfDistToTestTime" - execution time of MONAI average surface distance algorithm
"myRobustHdTime" - execution time of my robust ( 0.90 ) Hausdorff distance algorithm
"myHdTime" -execution time of my not robust Hausdorff distance algorithm
"mymedianHdTime" -execution time of my average surface distance algorithm (it is not median)
"olivieraTime" - execution time of Oliviera [3] not robust Hausdorff distance algorithm

"hdToTestRobustValue" - value of MONAI robust ( 0.90 ) Hausdorff distance algorithm
"hdToTestValue" - value of MONAI not robust Hausdorff distance algorithm
"myRobustHdValue"- value of my robust ( 0.90 ) Hausdorff distance algorithm
"myHdValue"- value of my not robust Hausdorff distance algorithm
"mymeanHdValue" - value of my average surface distance algorithm
"olivieraValue"- value of Oliviera [3] not robust Hausdorff distance algorithm
"avSurfDistToTestValue"- value of MONAI average surface distance algorithm
"WIDTH" "HEIGHT" "DEPTH" - dimensions of the image used for tests
"translations" - in case image was translated how many voxels it was translated in z axis

1. https://github.com/jakubMitura14/extension-cpp/blob/master/README.md
2. https://github.com/jakubMitura14/extension-cpp/blob/master/analyzeBench.Rmd
3. Érick Oliveira Rodrigues,An efficient and locality-oriented Hausdorff distance algorithm: Proposal and analysis of paradigms and implementations, Pattern Recognition,Volume 117,2021
   4)https://wiki.cancerimagingarchive.net/display/Public/CT-ORG%3A+CT+volumes+with+multiple+organ+segmentations

someFromTransformed.csv

[Nic-Ma]

Hi @jakubMitura14 ,

Thanks very much for your interest and cool CUDA implementation.
I think maybe you can refer to the existing GMM extension:
https://github.com/Project-MONAI/MONAI/tree/dev/monai/_extensions/gmm
@wyli Do we have any documentation of the contribution guide for C++/CUDA extension?

Thanks in advance.

[wyli]

Thanks, the URLs don't seem to work, is it a public repo?

[jakubMitura14]

Yes my mistake, please check now 🙂

[wyli]

Now I have the access. Thanks for the details, the jit implementation looks good. If you are interested in contributing it to MONAI, @charliebudd and I could help...

An initial step would be making a pull request to add the relevant computational logic to the current codebase's python API https://github.com/Project-MONAI/MONAI/blob/dev/monai/metrics/hausdorff_distance.py such as:

from monai._extensions.loader import load_module
...
def compute_hausdorff_distance_v2(...):
   compiled_module = load_module("hausdorff")
   return compiled_module.getHausdorffDistance(...)

(a similar jit module is here

MONAI/monai/networks/layers/gmm.py

Lines 42 to 46 in de97391

	self.compiled_extension = load_module(
	"gmm",
	{"CHANNEL_COUNT": channel_count, "MIXTURE_COUNT": mixture_count, "MIXTURE_SIZE": mixture_size},
	verbose_build=verbose_build,
	)

).

And in monai/_extensions creating a folder, e.g. monai/_extensions/hausdorff with two files in it:

• hausdorff.cpp
  • (define the PYBIND11_MODULE entry point)
• hausdorff_cuda.cu

Finally please add a unit test like this https://github.com/Project-MONAI/MONAI/blob/dev/tests/test_hausdorff_distance.py

[jakubMitura14]

Thanks i will work on it !

[jakubMitura14]

Ok I created a pull request with first simple test in
#4078

Hovewer It is not tested as I had no idea how to compile monai and run the test of my files - can you guide me in it ?

I have currently copied on windows 10 pc monai added my modifications:
test_hausdorff_distance.py to tests
hausdorff folder to _extension folder with C++ code
morphological_hausdorff_distance.py file with MorphologicalHausdorffDistanceMetric class to metrics folder

I also upload pdf with some description of the algorithm (work in progress), just for some reference. look into Algorithm description

Hausdorff.pdf