La biblioteca OpenCV utiliza para su función aproximada cv::distanceTransform un algoritmo que pasa la imagen de arriba a la izquierda a la parte inferior derecha y atrás. El algoritmo se describe en el documento "Transformaciones de distancia en imágenes digitales" de Gunilla Borgefors (Comput. Vision Graph. Image Process., 34 3, pp 344-371, 1986).
El algoritmo calcula la distancia mediante una combinación de algunos saltos básicos (horizontal, vertical, diagonal y el movimiento del caballero). Cada salto incurre en costos. La siguiente tabla muestra los costos de los diferentes saltos.
+------+------+------+------+------+
| 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 |
+------+------+------+------+------+
La distancia de un píxel a otro es la suma de los costes de los saltos necesarios. La siguiente imagen muestra la distancia desde las 0 celdas a cada celda. Las flechas están mostrando el camino a algunas celdas. Los números coloreados reflejan la distancia exacta (euclidiana).
El algoritmo funciona así: Tras la máscara
+------+------+------+
| 0 | 1 | 2 |
+------+------+------+
| 1 | 1.4 |2.1969|
+------+------+------+
| 2 |2.1969| 2.8 |
+------+------+------+
se mueve desde la parte superior izquierda de la imagen de abajo a la derecha. Durante este pase, las celdas que se encuentran dentro de los límites de la máscara conservan su valor (si se conoce y es más pequeño) o obtienen el valor calculado sumando el valor de máscara y el valor de celda (si se conoce) de la celda debajo de la máscara-0-celda. Después de eso, se realiza un segundo pase desde la parte inferior derecha a la parte superior izquierda (con una máscara volteada vertical y horizontal). Después del segundo pase, se calculan las distancias.
Este método es considerablemente más lento que las técnicas modernas (la más notable es la de A. Meijster). –