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.
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.
Can you also return the index of the closest non-zero pixel for each pixel as an optional output argument?
Very useful and fast. Thanks for sharing!
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'.
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?
Does the job.
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.
I tested this on two spheres overlapping in a 81x81x81 binary image. Elapsed time shows bwdistsc to be faster than bwdist by 0.92sec
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
Added citation information as many people had requested.
Replaces bwdistsc with the earlier introduced experimental bwdistX, which uses forward-backward version of algorithm, improving speed up to 10x vs native bwdist
Adds experimental bwdistX for user testing, which uses forward-backward version of algorithm and is up to 10x faster than native bwdist
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.
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.