21
$\begingroup$

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

According to this site http://homepages.inf.ed.ac.uk/rbf/HIPR2/distance.htm, it describes:

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.

| improve this question | |
$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – mkli90 Mar 27 '16 at 20:03
  • $\begingroup$ Please ask a new question. Don't post questions as answers. $\endgroup$ – MBaz Mar 27 '16 at 21:16
  • $\begingroup$ Welcome to Signal Processing SE. You can ask a question using the "Ask Question" in top right corner. $\endgroup$ – jojek♦ Mar 27 '16 at 23:45
14
$\begingroup$

Pedro F. Felzenszwalb and Daniel P. Huttenlocher have published their implementation for the distance transform. 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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Do you happen to know if this is implemented in OpenCV? $\endgroup$ – Matt M. Oct 8 '11 at 10:38
  • $\begingroup$ Yes, for certain values of maskSize and distanceType. See: opencv.willowgarage.com/documentation/cpp/… $\endgroup$ – bjoernz Oct 9 '11 at 6:04
  • $\begingroup$ is there any implementations for volumetric images (e.g., kinect depth image) till now? $\endgroup$ – zhangxaochen Jul 29 '15 at 10:10
9
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ It would be useful to know where in your library can we find the particular code. $\endgroup$ – akaltar Aug 23 '15 at 14:03
6
$\begingroup$

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:

enter image description here

enter image description here

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Interesting. What is a common use of the distance transform, Libor? $\endgroup$ – Spacey Aug 21 '12 at 13:57
  • 1
    $\begingroup$ 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. $\endgroup$ – Libor Aug 21 '12 at 19:54
  • 1
    $\begingroup$ 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. $\endgroup$ – Rethunk Sep 19 '12 at 20:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.