Najszybszy dostępny algorytm transformacji odległości

W artykule omówiono znane algorytmy transformacji odległości:

"algorytmy transformacji odległości euklidesowej 2D: badanie porównawcze"
http://liu.diva-portal.org/smash/get/diva2:23335/FULLTEXT01

Najszybsza transformacja dokładnej odległości pochodzi od Meijstera:

" ogólny algorytm obliczania przekształceń odległości w czasie liniowym."
http://fab.cba.mit.edu/classes/S62.12/docs/Meijster_distance.pdf

Konstrukcja algorytmu jest szczególnie dobrze nadaje się do obliczeń równoległych.

Jest to zaimplementowane w mojej bibliotece open source, która próbuje emulować "Styl warstwy Photoshopa:"

Https://github.com/vinniefalco/LayerEffects

Biblioteka OpenCV wykorzystuje do swojej przybliżonej funkcji CV::distanceTransform algorytm, który przekazuje obraz z lewego górnego rogu do prawego dolnego rogu iz powrotem. Algorytm został opisany w pracy" transformacje odległości w obrazach cyfrowych " autorstwa Gunilli Borgefors (Oblicz. Wykres Wizji. Proces Obrazu. 34 3, pp 344-371, 1986).

Algorytm oblicza odległość poprzez kombinację niektórych podstawowych skoków (poziome, pionowe, ukośne i ruch rycerza). Każdy skok ponosi koszty. Poniższa tabela przedstawia koszty poszczególnych skoków.

+------+------+------+------+------+
| 2.8  |2.1969|   2  |2.1969|  2.8 |
+------+------+------+------+------+
|2.1969|  1.4 |   1  |  1.4 |2.1969|
+------+------+------+------+------+
|   2  |   1  |   0  |   1  |   2  |
+------+------+------+------+------+
|2.1969|  1.4 |   1  |  1.4 |2.1969|
+------+------+------+------+------+
| 2.8  |2.1969|   2  |2.1969|  2.8 |
+------+------+------+------+------+

Odległość od jednego piksela do drugiego jest sumą kosztów niezbędnych skoków. Poniższy obraz pokazuje odległość od 0-komórek do siebie komórki. Strzałki wskazują drogę do niektórych komórek. Kolorowe cyfry odzwierciedlają dokładną (euklidesową) odległość.

Algorytm działa w następujący sposób: po masce

+------+------+------+
|   0  |   1  |   2  |
+------+------+------+
|   1  |  1.4 |2.1969|
+------+------+------+
|   2  |2.1969|  2.8 |
+------+------+------+

Jest przesuwany z lewego górnego rogu obrazka do na dole po prawej. Podczas tego przejścia komórki leżące wewnątrz granic maski albo zachowują swoją wartość (jeśli jest znana i mniejsza), albo otrzymują wartość obliczoną przez zsumowanie wartości maski i wartości komórki (jeśli jest znana) z komórki poniżej komórki Maska-0. Następnie wykonuje się drugie przejście od prawego dolnego rogu do lewego górnego rogu(z pionową i poziomą maską odwróconą). Po drugim przejściu odległości są obliczane.

Felzenszwalb i Huttenlocher prezentują elegancki algorytm, który jest dokładny I O(N) w swojej pracy "transformacje odległości próbkowanych funkcji" dostępnej tutaj . Wykorzystują one fakt, że kwadrat euklidesowej transformacji odległości jest parabolą, która może być oceniana niezależnie w każdym wymiarze.

Kod źródłowy jest również Dostępny .

Zaimplementowałem metodę O(N) meijstera cytowaną w odpowiedzi Vinniego. "A General Algorithm for Computing Distance Transforms in Linear Time." http://fab.cba.mit.edu/classes/S62.12/docs/Meijster_distance.pdf

Fajną rzeczą jest to, że można ją bardzo efektywnie paralelizować, obliczając każdą linię pikseli niezależnie (jest to metoda rozdzielna). Działa na 12 rdzeniach procesora, pole odległości obrazu wolumetrycznego 1000^3 oblicza się w ciągu kilku sekund.

Rozwiązanie Felzenszwalb i Huttenlocher "transformacje odległości funkcji samplowanych" z 2012 roku (cytowane w odpowiedzi bw1024) oparte są na dokładnie tym samym pomyśle. Co ciekawe, nie cytują pracy Meijstera wykonanej 12 lat wcześniej.