Biblioteka OpenCV używa w przybliżeniu funkcji cv::distanceTransform algorytmu, który przekazuje obraz z góry z lewej na prawą i z powrotem. Algorytm opisany jest w artykule "Transformacje odległości w obrazach cyfrowych" z Gunilla Borgefors (Comput .. Vision Graph, Image Process, 34 3, str. 344-371, 1986).
Algorytm oblicza odległość poprzez kombinację podstawowych skoków (poziomego, pionowego, ukośnego i rycerskiego). Każdy skok wiąże się z kosztami. Poniższa tabela pokazuje koszty różnych 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 obrazek pokazuje odległość od komórek 0 do każdej innej komórki. Strzałki pokazują drogę do niektórych komórek. Kolorowe cyfry odzwierciedlają dokładną odległość (euklidesową).
Algorytm działa tak: Po maska
+------+------+------+
| 0 | 1 | 2 |
+------+------+------+
| 1 | 1.4 |2.1969|
+------+------+------+
| 2 |2.1969| 2.8 |
+------+------+------+
został przeniesiony z lewej górnej części obrazu do prawej dolnej. Podczas tego przejścia komórki leżące wewnątrz granic maski zachowują swoją wartość (jeśli są znane i mniejsze) lub uzyskują wartość obliczoną przez zsumowanie wartości maski i wartości komórki (jeśli jest znana) z komórki poniżej komórki-maski. Następnie wykonywane jest drugie przejście od prawego dolnego rogu do lewego górnego rogu (z odwróconą maską pionową i poziomą). Po drugim przejściu obliczane są odległości.
Metoda ta jest znacznie wolniejsza od nowoczesnych technik (najbardziej godna uwagi jest ta pochodząca od A. Meijstera). –