Najszybszy algorytm transformacji odległości

Szukam najszybszego dostępnego algorytmu do przekształcania odległości.

Według tej strony http://homepages.inf.ed.ac.uk/rbf/HIPR2/distance.htm opisuje:

Transformację odległości można obliczyć znacznie wydajniej przy użyciu sprytnych algorytmów tylko w dwóch przebiegach (np. Rosenfeld i Pfaltz 1968).

Rozglądając się, znalazłem: „Rosenfeld, A and Pfaltz, J L. 1968. Funkcje odległości na obrazach cyfrowych. Rozpoznawanie wzorów, 1, 33-61”.

Ale uważam, że powinniśmy mieć lepszy i szybszy algorytm niż ten z 1968 roku? W rzeczywistości nie mogłem znaleźć źródła z 1968 roku, więc każda pomoc jest bardzo ceniona.

Pedro F. Felzenszwalb i Daniel P. Huttenlocher opublikowali swoją implementację transformacji odległości . Nie można go używać do obrazów wolumetrycznych, ale być może można go rozszerzyć o obsługę danych 3d. Użyłem go tylko jako czarnej skrzynki.

W tym artykule omówiono wszystkie współczesne dokładne przekształcenia odległości:

„2D Euklidesowe transformacje odległości: badanie porównawcze”, ACM Computing Surveys, tom 40, wydanie 1, luty 2008 http://www.lems.brown.edu/~rfabbri/stuff/fabbri-EDT-survey-ACMCSurvFeb2008.pdf

Artykuł cytuje technikę Meijster i in. glin. jako najszybszy cel ogólny, dokładna transformacja. Ta technika jest szczegółowo opisana tutaj:

„Ogólny algorytm obliczania transformacji odległości w czasie liniowym”, A. Meijster, JBTM Roerdink i WH Hesselink. http://fab.cba.mit.edu/classes/S62.12/docs/Meijster_distance.pdf

Algorytm Meijster jest używany w mojej bibliotece efektów open source: https://github.com/vinniefalco/LayerEffects

Mam nadzieję, że to komuś pomoże.

Oto kod C # kwadratowej transformacji odległości euklidesowej 1D według pracy Felzenszwald & Huttenlocher :

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]]);
    }
}

Można to łatwo zastosować do obrazów binarnych i w skali szarości poprzez zastosowanie go najpierw do kolumn obrazów, a następnie wierszy (lub odwrotnie, oczywiście).

Transformacja jest rzeczywiście bardzo szybka.

Oto obrazy źródłowe i wyjściowe:

Czarne piksele mają wartość 0, a białe mają pewną dużą wartość (muszą być większe niż największa możliwa kwadratowa odległość na obrazach, ale nie nieskończoność), aby transformacja zwróciła odległość od czarnych pikseli, a białe zostaną pominięte.

Aby uzyskać prawdziwą euklidesową transformację odległości, wystarczy wyjąć pierwiastek kwadratowy z każdego piksela z obrazu wyjściowego.