File Exchange

image thumbnail

3D Euclidean Distance Transform for Variable Data Aspect Ratio

version 1.8.0.0 (53.8 KB) by Yuriy Mishchenko
Implementation of 3D Euclidean distance transform for data with non-trivial aspect ratio.

12 Downloads

Updated 09 Jan 2015

View License

This function computes Euclidean distance transform for 3D binary image with non-trivial aspect ratio (i.e. anisotropic pixels). The algorithm uses fast optimized line-scans and is actually faster than MATLAB's BWDIST implementation of search on optimized kd-tree for many cases. It also uses cell-array representation for internal data, and thus is less demanding to physical memory.
If you use this function in your research or a paper, you can cite it as follows:
Y. Mishchenko (2015) A fast algorithm for computation of discrete Euclidean distance transform in three or more dimensions on vector processing architectures. Signal, Image and Video Processing, 9(1), 19-27.

Comments and Ratings (18)

Thanks for publishing! Very helpful for space and time savings. Worth noting there is a slight discrepancy as compared with bwdist. When required, bwdist is exact as proved in the paper cited in the matlab documentation. Error does not appear to be correlated with input, but error / max_distance is typically less than 10^-4.

JIA GUO

Can you also return the index of the closest non-zero pixel for each pixel as an optional output argument?

Ben

Very useful and fast. Thanks for sharing!

Ben

JakobK

Deepak

Nice code! Can you also return the index of the closest non-zero pixel for each pixel as an optional output argument? It is needed in a few cases.

Hi Catarina, you can use [1 1 2.56] directly in place of the 'aspect' parameter, and the distance transform will be directly calculated in 'mm'.

Asadullah

Catarina

Hey!
First of all thanks for sharing this code, I am finding it very useful. However, there are some points I'd like to clarify since it is the first time I am looking at distance transformations.

I am trying to compute distance transformations for some 3D binary masks images. However, the pixel spacing in mm is not constant, but [1 1 2.56]mm. To avoid resampling of the images, I want to make sure I can use your code using that matrix as the aspect. If I can, my doubt is in how to interpret the output matrix in mm too?

leila

tudor dima

Does the job.

Kishore Kuchibhotla

This has been a huge help. Thanks for posting this--bwdist continuously gave me out of memory problems (I'm computing 3D distance transforms on 512*512*100 size datasets), whereas bwdistsc works very well. The controllable aspect ratio is also helpful.

Jeremy Kress

I tested this on two spheres overlapping in a 81x81x81 binary image. Elapsed time shows bwdistsc to be faster than bwdist by 0.92sec
nice job!

ivan scardanzan

not much slower than matlab bwdist (Image Processing Toolbox)
but it requires much less memory and get where you get 'OUT OF MEMORY' with bwdist

so on overall -to me- it is better than bwdist

Updates

1.8.0.0

Added citation information as many people had requested.

1.7.0.0

Replaces bwdistsc with the earlier introduced experimental bwdistX, which uses forward-backward version of algorithm, improving speed up to 10x vs native bwdist

1.6.0.0

Adds experimental bwdistX for user testing, which uses forward-backward version of algorithm and is up to 10x faster than native bwdist

1.3.0.0

Included bwdistsc1 that allows restricting calculations out to a certain distance, which may accelerate calculations in some cases, see readme. Also contains a fix for Matlab version detection routine, thanks to Tudor Dima.

1.0.0.0

The code had been improved to better handle certain type of problems (cavities). It also contains fix allowing use of function with plain 2D images.

MATLAB Release Compatibility
Created with R14SP2
Compatible with any release
Platform Compatibility
Windows macOS Linux