File Exchange

## 3D Euclidean Distance Transform for Variable Data Aspect Ratio

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

Updated 09 Jan 2015

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.

### Cite As

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 .

Hans Harms

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:

bw=zeros(100,100,100);
bw(40:60,40:60,40:60)=1;
tic;D=bwdist(bw);toc
tic;D=bwdistsc(bw);toc
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

William Warriner

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.

Jean-Yves Tinevez

JIA GUO

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

Peter Beemiller

Ilya Belevich

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.

Yuriy Mishchenko

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'.

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

Oliver Woodford

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

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