# Fastest Algorithm for Distance Transform

I am looking for the fastest available algorithm for distance transform.

The distance transform can be calculated much more efficiently using clever algorithms in only two passes (e.g. Rosenfeld and Pfaltz 1968).

Searching around, I found: "Rosenfeld, A and Pfaltz, J L. 1968. Distance Functions on Digital Pictures. Pattern Recognition, 1, 33-61."

But I believe we should have a better and faster algorithm than the one in 1968 already? In fact, I could not find the source from 1968, so any help is highly appreciated.

• Sorry for getting this thread up again, but I'm trying to implement the GDT as well, but using Python. def of_column(dataInput): output = zeros(dataInput.shape) n = len(dataInput) k = 0 v = zeros((n,)) z = zeros((n + 1,)) v[0] = 0 z[0] = -inf z[1] = +inf s = 0 for q in range(1, n): while True: s = (((dataInput[q] + q * q) - (dataInput[v[k]] + v[k] * v[k])) / (2.0 * q - 2.0 * v[k])) if s <= z[k]: k -= 1 else: break k += 1 v[k] = q z[k] = s z[k + 1] = +inf k = 0 for q in range(n): while z[k + 1] < q: k += 1 output[q] = ((q - v[k]) * (q - v[k]) + dataInput[v[k]]) return output However when offeri Commented Mar 27, 2016 at 20:03
– MBaz
Commented Mar 27, 2016 at 21:16
• Welcome to Signal Processing SE. You can ask a question using the "Ask Question" in top right corner.
– jojeck
Commented Mar 27, 2016 at 23:45

Pedro F. Felzenszwalb and Daniel P. Huttenlocher have published their implementation for the distance transform [archive]. You cannot use it for volumetric images, but maybe you can extend it to support 3d data. I have only used it as a black box.

• Do you happen to know if this is implemented in OpenCV? Commented Oct 8, 2011 at 10:38
• Yes, for certain values of maskSize and distanceType. See: opencv.willowgarage.com/documentation/cpp/… Commented Oct 9, 2011 at 6:04
• is there any implementations for volumetric images (e.g., kinect depth image) till now? Commented Jul 29, 2015 at 10:10

This paper discusses all of the modern exact distance transforms:

"2D Euclidean distance transforms: a comparative survey", ACM Computing Surveys, Vol 40, Issue 1, Feb 2008 http://www.lems.brown.edu/~rfabbri/stuff/fabbri-EDT-survey-ACMCSurvFeb2008.pdf

The paper cites the technique from Meijster, et. al. as the fastest general purpose, exact transform. This technique is detailed here:

"A General Algorithm for Computing Distance Transforms in Linear Time", A. Meijster, J. B. T. M. Roerdink and W. H. Hesselink. http://fab.cba.mit.edu/classes/S62.12/docs/Meijster_distance.pdf

The Meijster algorithm is used in my open source effects library: https://github.com/vinniefalco/LayerEffects

I hope this helps someone.

• It would be useful to know where in your library can we find the particular code. Commented Aug 23, 2015 at 14:03

Here is a C# code for 1D squared euclidean distance transform according to the Felzenszwald & Huttenlocher's paper:

private static void DistanceTransform(double[] dataInput, ref double[] dataOutput)
{
int n = dataInput.Length;

int k = 0;
int[] v = new int[n];
double[] z = new double[n + 1];

v[0] = 0;
z[0] = Double.NegativeInfinity;
z[1] = Double.PositiveInfinity;

double s;

for (int q = 1; q < n; q++)
{
while (true)
{
s = (((dataInput[q] + q * q) - (dataInput[v[k]] + v[k] * v[k])) / (2.0 * q - 2.0 * v[k]));

if (s <= z[k])
{
k--;
}
else
{
break;
}
}

k++;

v[k] = q;
z[k] = s;
z[k + 1] = Double.PositiveInfinity;
}

k = 0;

for (int q = 0; q < n; q++)
{
while (z[k + 1] < q)
{
k++;
}

dataOutput[q] = ((q - v[k]) * (q - v[k]) + dataInput[v[k]]);
}
}


This can be readily used for binary and grayscale images by applying it first on image columns and then rows (or vice versa, of course).

The transform is indeed very fast.

Here are the source and output images:

The black pixels have value 0 and the white have some large value (have to be larger than largest possible squared distance in the images but not infinity) so that the transform returns distance from the black pixels and the white ones are ommited.

To get true euclidean distance transform, simply take a square root of each pixel from the output image.

• Interesting. What is a common use of the distance transform, Libor? Commented Aug 21, 2012 at 13:57
• I think the common uses are in finding paths, segmentation, geometrical measurements (center of mass) and effects (bevel effect). I needed distance transform for panoramic image stitching - to find a geometrically optimal blending mask. This involved running distance transform on each image, and then computing blending mask from the weights. Commented Aug 21, 2012 at 19:54
• The distance transform can be used in matching [edge] images, one technique being "chamfer matching"(umiacs.umd.edu/~mingyliu/papers/liu_cvpr2010.pdf). The DT can also be used to find medial axis (skeleton) and to perform other tasks such as Libor mentioned. Commented Sep 19, 2012 at 20:43
• @Libor How should the input array ( double[] ) be filled, and subsequently called? Is it an array of normalized values between 0 and 1, where 0 is black and 1 is white? Or is it an array of values between 0 and double.MaxValue? Please consider including an example where you populate the input array and call the method. Commented Mar 23, 2021 at 2:39