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.
5.0
15 Ratings

2 Downloads

Updated 09 Jan 2015

View Version History

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.

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 .

Comments and Ratings (18)

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

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

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

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!