Najszybszy algorytm transformacji odległości

21

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.

Karl
źródło
Przepraszamy za ponowne uruchomienie tego wątku, ale próbuję również zaimplementować GDT, ale używając Pythona. def of_column (dataInput): output = zera (dataInput.shape) n = len (dataInput) k = 0 v = zera ((n,)) z = zera ((n + 1,)) v [0] = 0 z [0] = -inf z [1] = + inf s = 0 dla qw zakresie (1, n): while True: s = (((dataInput [q] + q * q) - (dataInput [v [k ]] + v [k] * v [k])) / (2,0 * q - 2,0 * v [k])) jeśli s <= z [k]: k - = 1 else: break k + = 1 v [ k] = qz [k] = sz [k + 1] = + inf k = 0 dla q w zakresie (n): podczas gdy z [k + 1] <q: k + = 1 wyjście [q] = ((q - v [k]) * (q - v [k]) + dataInput [v [k]]) zwraca dane wyjściowe Jednak przy oferowaniu
mkli90
Proszę zadać nowe pytanie. Nie publikuj pytań jako odpowiedzi.
MBaz
Witamy w Signal Processing SE. Możesz zadać pytanie, używając „Zadaj pytanie” w prawym górnym rogu.
jojek

Odpowiedzi:

14

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.

Bjoernz
źródło
Czy wiesz, czy jest to zaimplementowane w OpenCV?
Matt M.,
Tak, dla niektórych wartości maskSizei distanceType. Zobacz: opencv.willowgarage.com/documentation/cpp/…
bjoernz
czy są do tej pory jakieś implementacje obrazów wolumetrycznych (np. obraz głębokości kinect)?
zhangxaochen
9

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.

Vinnie Falco
źródło
Przydałoby się wiedzieć, gdzie w Twojej bibliotece możemy znaleźć konkretny kod.
akaltar
6

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:

wprowadź opis zdjęcia tutaj

wprowadź opis zdjęcia tutaj

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.

Libor
źródło
Ciekawy. Jakie jest powszechne zastosowanie transformacji odległości, Libor?
Spacey,
1
Myślę, że powszechne zastosowania to znajdowanie ścieżek, segmentacja, pomiary geometryczne (środek masy) i efekty (efekt fazy). Potrzebowałem transformacji odległości do panoramicznego łączenia obrazów - aby znaleźć geometrycznie optymalną maskę do mieszania. Wymagało to przekształcenia odległości biegu na każdym obrazie, a następnie obliczenia maski mieszania na podstawie ciężarów.
Libor,
1
Transformacji odległości można używać w dopasowywaniu obrazów [krawędzi], jedną z technik jest „dopasowanie fazowania” ( umiacs.umd.edu/~mingyliu/papers/liu_cvpr2010.pdf ). ID można również wykorzystać do znalezienia osi środkowej (szkieletu) i wykonania innych zadań, takich jak wspomniany Libor.
Rethunk,