Home

Awesome

FastGeodis: Fast Generalised Geodesic Distance Transform

License Downloads status CI Build PyPI version <img src="https://img.shields.io/badge/Python-3.8%20|%203.9%20|%203.10%20|%203.11%20-3776ab.svg"/> <img src="https://img.shields.io/badge/PyTorch-%3E%3D%201.5.0-brightgreen.svg"/>

<!--<img src="https://img.shields.io/pypi/dm/fastgeodis.svg?label=PyPI%20downloads&logo=python&logoColor=green"/>-->

This repository provides CPU (OpenMP) and GPU (CUDA) implementations of Generalised Geodesic Distance Transform in PyTorch for 2D and 3D input data based on parallelisable raster scan ideas from [1]. It includes methods for computing Geodesic, Euclidean distance transform and mixture of both.

2D images, 1 of 4 passes3D volumes, 1 of 6 passes
<img src="https://raw.githubusercontent.com/masadcv/FastGeodis/master/figures/FastGeodis2D.png?raw=true" width="300" /><img src="https://raw.githubusercontent.com/masadcv/FastGeodis/master/figures/FastGeodis3D.png?raw=true" width="300" />

The above raster scan method can be parallelised for each row/plane on an available device (CPU or GPU). This leads to significant speed up as compared to existing non-parallelised raster scan implementations (e.g. https://github.com/taigw/GeodisTK). Python interface is provided (using PyTorch) for enabling its use in deep learning and image processing pipelines.

In addition, implementation of generalised version of Geodesic distance transforms along with Geodesic Symmetric Filtering (GSF) is provided for use in interactive segmentation methods, that were originally proposed in [1, 2, 5].

The raster scan based implementation provides a balance towards speed rather than accuracy of Geodesic distance transform and hence results in efficient hardware utilisation. On the other hand, in case of Euclidean distance transform, exact results can be achieved with other packages (albeit not on necessarilly on GPU) [6, 7, 8]

Citation

If you use this code in your research, then please consider citing:

status

Asad, Muhammad, Reuben Dorent, and Tom Vercauteren. "FastGeodis: Fast Generalised Geodesic Distance Transform." Journal of Open Source Software (JOSS), 2022. (paper link)

Bibtex:

@article{asad2022fastgeodis, 
  doi = {10.21105/joss.04532}, 
  url = {https://doi.org/10.21105/joss.04532}, 
  year = {2022}, 
  publisher = {The Open Journal}, 
  volume = {7}, 
  number = {79}, 
  pages = {4532}, 
  author = {Muhammad Asad and Reuben Dorent and Tom Vercauteren}, 
  title = {FastGeodis: Fast Generalised Geodesic Distance Transform}, 
  journal = {Journal of Open Source Software} 
}

Installation instructions

The provided package can be installed using:

pip install FastGeodis

or

pip install git+https://github.com/masadcv/FastGeodis

or (on conda environments with existing installation of PyTorch with CUDA)

pip install FastGeodis --no-build-isolation

Included methods

Optimised Fast Implementations for GPU/CPU based on [1]

MethodDescriptionDocumentation
Fast Generalised Geodesic Distance 2DParalellised generalised geodesic distance transform for CPU/GPU [1]FastGeodis.generalised_geodesic2d
Fast Generalised Geodesic Distance 3DParalellised generalised geodesic distance transform for CPU/GPU [1]FastGeodis.generalised_geodesic3d
Fast Signed Generalised Geodesic Distance 2DParalellised signed generalised geodesic distance transform for CPU/GPU [1]FastGeodis.signed_generalised_geodesic2d
Fast Signed Generalised Geodesic Distance 3DParalellised signed generalised geodesic distance transform for CPU/GPU [1]FastGeodis.signed_generalised_geodesic3d
Fast Geodesic Symmetric Filtering 2DParalellised geodesic symmetric filtering for CPU/GPU [2]FastGeodis.GSF2d
Fast Geodesic Symmetric Filtering 3DParalellised geodesic symmetric filtering for CPU/GPU [2]FastGeodis.GSF3d

Toivanen's Implementations for CPU based on [9]

MethodDescriptionDocumentation
Toivanen's Generalised Geodesic Distance 2DToivanen's generalised geodesic distance transform for CPU [9]FastGeodis.generalised_geodesic2d_toivanen
Toivanen's Generalised Geodesic Distance 3DToivanen's generalised geodesic distance transform for CPU [9]FastGeodis.generalised_geodesic3d_toivanen
Toivanen's Signed Generalised Geodesic Distance 2DToivanen's signed generalised geodesic distance transform for CPU [9]FastGeodis.signed_generalised_geodesic2d_toivanen
Toivanen's Signed Generalised Geodesic Distance 3DToivanen's signed generalised geodesic distance transform for CPU [9]FastGeodis.signed_generalised_geodesic3d_toivanen
Toivanen's Geodesic Symmetric Filtering 2DToivanen's geodesic symmetric filtering for CPU [2, 9]FastGeodis.GSF2d_toivanen
Toivanen's Geodesic Symmetric Filtering 3DToivanen's geodesic symmetric filtering for CPU [2, 9]FastGeodis.GSF3d_toivanen

Pixel Queue Implementations for CPU based on [11]

MethodDescriptionDocumentation
Pixel Queue Geodesic Distance 2DPixel Queue geodesic distance transform for CPU [11]FastGeodis.geodesic2d_fastmarch
Pixel Queue Geodesic Distance 3DPixel Queue geodesic distance transform for CPU [11]FastGeodis.geodesic3d_pixelqueue
Pixel Queue Signed Geodesic Distance 2DPixel Queue signed geodesic distance transform for CPU [11]FastGeodis.signed_geodesic2d_pixelqueue
Pixel Queue Signed Geodesic Distance 3DPixel Queue signed geodesic distance transform for CPU [11]FastGeodis.signed_geodesic3d_pixelqueue
Pixel Queue Geodesic Symmetric Filtering 2DPixel Queue geodesic symmetric filtering for CPU [2, 11]FastGeodis.GSF2d_pixelqueue
Pixel Queue Geodesic Symmetric Filtering 3DPixel Queue geodesic symmetric filtering for CPU [2, 11]FastGeodis.GSF3d_pixelqueue

Fast Marching Implementations for CPU based on [4, 10]

MethodDescriptionDocumentation
Fast Marching Geodesic Distance 2DFast Marching geodesic distance transform for CPU [9]FastGeodis.geodesic2d_fastmarch
Fast Marching Geodesic Distance 3DFast Marching geodesic distance transform for CPU [9]FastGeodis.geodesic3d_fastmarch
Fast Marching Signed Geodesic Distance 2DFast Marching signed geodesic distance transform for CPU [9]FastGeodis.signed_geodesic2d_fastmarch
Fast Marching Signed Geodesic Distance 3DFast Marching signed geodesic distance transform for CPU [9]FastGeodis.signed_geodesic3d_fastmarch
Fast Marching Geodesic Symmetric Filtering 2DFast Marching geodesic symmetric filtering for CPU [2, 9]FastGeodis.GSF2d_fastmarch
Fast Marching Geodesic Symmetric Filtering 3DFast Marching geodesic symmetric filtering for CPU [2, 9]FastGeodis.GSF3d_fastmarch

Example usage

Fast Geodesic Distance Transform

The following demonstrates a simple example showing FastGeodis usage:

To compute Geodesic Distance Transform:

device = "cuda" if torch.cuda.is_available() else "cpu"
image = np.asarray(Image.open("data/img2d.png"), np.float32)

image_pt = torch.from_numpy(image).unsqueeze_(0).unsqueeze_(0)
image_pt = image_pt.to(device)
mask_pt = torch.ones_like(image_pt)
mask_pt[..., 100, 100] = 0

v = 1e10
# lamb = 0.0 (Euclidean) or 1.0 (Geodesic) or (0.0, 1.0) (mixture)
lamb = 1.0
iterations = 2
geodesic_dist = FastGeodis.generalised_geodesic2d(
    image_pt, mask_pt, v, lamb, iterations
)
geodesic_dist = np.squeeze(geodesic_dist.cpu().numpy())

To compute Euclidean Distance Transform:

device = "cuda" if torch.cuda.is_available() else "cpu"
image = np.asarray(Image.open("data/img2d.png"), np.float32)

image_pt = torch.from_numpy(image).unsqueeze_(0).unsqueeze_(0)
image_pt = image_pt.to(device)
mask_pt = torch.ones_like(image_pt)
mask_pt[..., 100, 100] = 0

v = 1e10
# lamb = 0.0 (Euclidean) or 1.0 (Geodesic) or (0.0, 1.0) (mixture)
lamb = 0.0
iterations = 2
euclidean_dist = FastGeodis.generalised_geodesic2d(
    image_pt, mask_pt, v, lamb, iterations
)
euclidean_dist = np.squeeze(euclidean_dist.cpu().numpy())

For more usage examples see:

DescriptionPythonColab link
Simple 2D Geodesic and Euclidean Distancesamples/simpledemo2d.pyOpen in Colab
Simple Signed 2D Geodesic and Euclidean Distancesamples/simpledemo2d_signed.pyOpen in Colab
Simple 3D Geodesic and Euclidean Distancesamples/simpledemo3d.pyOpen in Colab
Simple Signed 3D Geodesic and Euclidean Distancesamples/simpledemo3d_signed.pyOpen in Colab
2D Geodesic Distancesamples/demo2d.pyOpen in Colab
2D Signed Geodesic Distancesamples/demo2d_signed.pyOpen in Colab
3D Geodesic Distancesamples/demo3d.pyOpen in Colab
3D Signed Geodesic Distancesamples/demo3d_signed.pyOpen in Colab
2D GSF Segmentation Smoothingsamples/demoGSF2d_SmoothingSegExample.ipynbOpen in Colab

Unit Tests

A number of unittests are provided, which can be run as:

pip install -r requirements-dev.txt
python -m unittest

Documentation

Further details of each function implemented in FastGeodis can be accessed at the documentation hosted at: https://fastgeodis.readthedocs.io.

Contributing to FastGeodis

Spotted a bug or have a feature request to improve the package? We would love to have your input! See our guidelines for contributing.

Comparison of Execution Time and Accuracy

FastGeodis (CPU/GPU) is compared with existing GeodisTK (https://github.com/taigw/GeodisTK) in terms of execution speed as well as accuracy.

Execution Time

2D images3D volumes
<img src="https://raw.githubusercontent.com/masadcv/FastGeodis/master/figures/experiment_2d.png?raw=true" width="400" /><img src="https://raw.githubusercontent.com/masadcv/FastGeodis/master/figures/experiment_3d.png?raw=true" width="400" />
<br>

Accuracy

2D case

Qualitative ComparisonQuantitative (joint histogram)
<img src="https://raw.githubusercontent.com/masadcv/FastGeodis/master/figures/fast_marching_compare_2d.png?raw=true?raw=true" width="800" /><img src="https://raw.githubusercontent.com/masadcv/FastGeodis/master/figures/fast_marching_compare_2d_jointhist.png?raw=true" width="400" />

3D case

Qualitative ComparisonQuantitative (joint histogram)
<img src="https://raw.githubusercontent.com/masadcv/FastGeodis/master/figures/fast_marching_compare_3d.png?raw=true" width="800" /><img src="https://raw.githubusercontent.com/masadcv/FastGeodis/master/figures/fast_marching_compare_3d_jointhist.png?raw=true" width="400" />

References