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.
Odpowiedzi:
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.
źródło
maskSize
idistanceType
. Zobacz: opencv.willowgarage.com/documentation/cpp/…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.
źródło
Oto kod C # kwadratowej transformacji odległości euklidesowej 1D według pracy Felzenszwald & Huttenlocher :
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.
źródło