algorithm - levenshtein - algoritmos para comparar textos
El algoritmo más rápido disponible para la transformación de distancia (5)
Estoy buscando el algoritmo más rápido disponible para la transformación de distancia.
Según este sitio http://homepages.inf.ed.ac.uk/rbf/HIPR2/distance.htm , describe: "La transformación de distancia se puede calcular de manera mucho más eficiente utilizando algoritmos inteligentes en solo dos pasadas (por ejemplo, Rosenfeld y Pfaltz 1968) ".
Buscando alrededor, encontré: "Rosenfeld, A y Pfaltz, JL 1968. Funciones de distancia en imágenes digitales. Reconocimiento de patrones, 1, 33-61."
¿Pero creo que deberíamos tener un algoritmo mejor y más rápido que el de 1968? De hecho, no pude encontrar la fuente desde 1968, por lo que cualquier ayuda es muy apreciada.
Este artículo revisa los conocidos algoritmos de transformación de distancia exacta:
"Algoritmos euclidianos 2D de transformación de distancia: una encuesta comparativa"
http://liu.diva-portal.org/smash/get/diva2:23335/FULLTEXT01
La transformación de distancia exacta más rápida es de Meijster:
"Algoritmo general para computar transformaciones de distancia en tiempo lineal".
http://fab.cba.mit.edu/classes/S62.12/docs/Meijster_distance.pdf
El diseño del algoritmo es particularmente adecuado para cálculos paralelos.
Esto se implementa en mi biblioteca de código abierto que intenta emular el "Estilo de capa" de Photoshop.
Felzenszwalb y Huttenlocher presentan un algoritmo elegante que es exacto y O (N) en su papel "Transformaciones de distancia de funciones muestreadas" disponible here . Explotan el hecho de que el cuadrado de la transformada de distancia euclidiana es una parábola que se puede evaluar independientemente en cada dimensión.
El código fuente también está available .
Hay toneladas de trabajo más nuevo en calcular las funciones de distancia.
- Algoritmos de marcha rápida que originalmente provenían de Tsitsiklis (no de Sethian como dice Wikipedia). Toneladas de implementaciones están disponibles para esto.
- Algoritmos de barrido rápido de Zhao
- O (n) (aproximada) marcha rápida por Yatziv
Por cierto, realmente querrías usar estos en lugar del trabajo de Rosenfeld, específicamente cuando quieras calcular distancias en presencia de obstáculos.
He implementado el método O (N) de Meijster citado en la respuesta de Vinnie. "Algoritmo general para computar transformaciones de distancia en tiempo lineal". http://fab.cba.mit.edu/classes/S62.12/docs/Meijster_distance.pdf
Lo bueno es que se puede paralelizar de manera muy eficiente, calculando cada línea de píxeles de forma independiente (es un método separable). Al funcionar con 12 núcleos de CPU, el campo de distancia de una imagen volumétrica de 1000 ^ 3 se computa en unos pocos segundos.
La solución de Felzenszwalb y Huttenlocher "Transformaciones de distancia de las funciones muestreadas" que data de 2012 (citada en la respuesta de bw1024) se basa exactamente en la misma idea. Curiosamente, no citan el trabajo de Meijster hecho 12 años antes.
La biblioteca OpenCV utiliza para su función cv::distanceTransform aproximada un algoritmo que pasa la imagen desde la parte superior izquierda a la parte inferior derecha y viceversa. 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 costos 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í: Máscara siguiente
+------+------+------+
| 0 | 1 | 2 |
+------+------+------+
| 1 | 1.4 |2.1969|
+------+------+------+
| 2 |2.1969| 2.8 |
+------+------+------+
se mueve desde la esquina superior izquierda de la imagen a la esquina inferior 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.