I needed a Generalized Distance Transform in my python program and didn't find any open source implementation that did what I needed. So in case anybody needs an Squared Euclidean Distance Transform implementationt that

• can deal with inf
• has runtime O(n) here you go.

Pull requests are welcome, of course.

C_gdt.c implements a Squared Euclidean Distance Transform. Ie. v(p) = min_q (u(q) + |p-q|^2), where p and q are 2D coordinates in the image, |.|^2 is the squared euclidean distance, u(.) is the original image, and v(.) is the output image.

On top of that the python function prob_dt implements what I call a Probabilistic Distance Transform. The input is a map of probabilities, and you want to smear the probabilities around. More specifically you want them to decay according to a Guassian distribution with standard deviation sigma.

The function is prob_dt(x) = max_y (p(y) * exp(-|x-y|^2 / (2 * sigma^2))), which I solve in logspace: log p(y) - |x-y|^2 / (2 * sigma^2). You can already see how the gaussian turned into a squared euclidean distance. Now we just have to isolate the distance term. The final result is prob_dt(x) = exp(1/(2*sigma^2) * gdt(log(p(x)) * 2 * sigma^2)).