FastGeodis: Fast Generalised Geodesic Distance Transform
Muhammad Asad, Reuben Dorent, Tom K. Vercauteren · The Journal of Open Source Software · 2022
Geodesic and Euclidean distance transforms have been widely used in a number of applications where distance from a set of reference points is computed.Methods from recent years have shown effectiveness in applying the Geodesic distance transform to interactively annotate 3D medical imaging data (Criminisi et al., 2008;Wang et al., 2018).The Geodesic distance transform enables providing segmentation labels, i.e., voxel-wise labels, for different objects of interests.Despite existing methods for efficient computation of the Geodesic distance transform on GPU and CPU devices (Criminisi et al., 2008(Criminisi et al., , 2009;;Toivanen, 1996;Weber et al., 2008), an open-source implementation of such methods on the GPU does not exist.On the contrary, efficient methods for the computation of the Euclidean distance transform (Felzenszwalb & Huttenlocher, 2012) have open-source implementations (Abadi et al., 2015; Seung-Lab, 2018).Existing libraries, e.g., Wang (2020), provide C++ implementations of the Geodesic distance transform; however, they lack efficient utilisation of the underlying hardware and hence result in significant computation time, especially when applying them on 3D medical imaging volumes.The FastGeodis package provides an efficient implementation for computing Geodesic and Euclidean distance transforms (or a mixture of both), targeting efficient utilisation of CPU and GPU hardware.In particular, it implements the paralellisable raster scan method from Criminisi et al. (2009), where elements in a row (2D) or plane (3D) can be computed with parallel threads.This package is able to handle 2D as well as 3D data, where it achieves up to a 20x speedup on a CPU and up to a 74x speedup on a GPU as compared to an existing open-source library (Wang, 2020) that uses a non-parallelisable single-thread CPU implementation.The performance speedups reported here were evaluated using 3D volume data on an Nvidia GeForce Titan X (12 GB) with a 6-Core Intel Xeon E5-1650 CPU.Further in-depth comparison of performance improvements is discussed in the FastGeodis documentation.