distance transform algorithms in scipy

Question

Since there are a lot of different algorithms for distance transformations (see e.g. here), I have some difficulty to understand how scipy's distance_transform_edt and distance_transform_bf work. Are there any detailed descriptions availible for that?

Answer 1

Following through the source...

distance_transform_edt ends up at code starting with the following helpful comment:

/* Exact euclidean feature transform, as described in: C. R. Maurer,
   Jr., R. Qi, V. Raghavan, "A linear time algorithm for computing
   exact euclidean distance transforms of binary images in arbitrary
   dimensions. IEEE Trans." PAMI 25, 265-270, 2003. */

int NI_EuclideanFeatureTransform(PyArrayObject* input,
           PyArrayObject *sampling_arr,
           PyArrayObject* features)

And distance_transform_bf ends up at a function which is looks to be a brute force calculation. But here the algorithm is also well described in the main documentation and elsewhere that turn up in a basic search.