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.
Yuriy Mishchenko (2021). 3D Euclidean Distance Transform for Variable Data Aspect Ratio (https://www.mathworks.com/matlabcentral/fileexchange/15455-3d-euclidean-distance-transform-for-variable-data-aspect-ratio), MATLAB Central File Exchange. Retrieved .
Interesting functions and nice that the aspect ratio can be taken into account, a major limitation of bwdist. However, when I run the tests (in 2020b) as suggested in bwdistsc, I do see a 20-fold performance drop versus bwdist:
Elapsed time is 0.014897 seconds.
Elapsed time is 0.280845 seconds.
Running bwdistsc straight out of the box. Is the 0.28s typical for bwdistsc and has MATLAB simply really optimized bwdist over the years, or are there easy ways to improve the 0.28s?
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
Find the treasures in MATLAB Central and discover how the community can help you!Start Hunting!