elgw / edt Goto Github PK

This repo contains an implementation of the Euclidean Distance Transform (EDT) based on the work by Meijster et. al ¹ with wrappers for MATLAB and Python. Most likely you should use the implementation in DIPlib ² instead of this one since it is better tested and more flexible with input and output formats.

The Euclidean distance transform, $D$, of a binary image, $B$, sets each voxel in $D$ to the shortest distance to any non-zero voxel in $B$. If the voxel is considered to have the same length in each dimension it is called isotropic, otherwise anisotropic. The computational burden increases quadratically with the number of pixels in the obvious, brute-force implementation. State of the art methods are linear in the number of pixels and the number of dimensions, i.e., they are $\mathcal{O}(dN)$.

This implementation has competitive performance and handles anisotropic pixel sizes at no extra cost. Compared to ¹ this implementation:

• Extended to 3D (however not nD, although that is possible).
• Handles anisotropic voxels. Basically this modification just required insertion of the pixel sizes at the proper places. The $\mbox{Sep}$ function looks different and in some places equality tests are replaced by greater(smaller) or equal.
• Only the Euclidean distance transform is implemented, not the other alternatives that are discussed in the paper.

The timings are for a $1042\times1024\times60$ image with isotropic pixels, on an AMD Ryzen 3700X.

Here are some further comparisons to the bwdist function in MATLAB.

• Write tests for corner cases and for invalid input.
• ND image implementation?
• The Python wrapper needs attention.