Hispanopedia WikiEn la práctica del procesamiento de imágenes digitales, Alexandre X. Falcao, Jorge Stolfi y Roberto de Alencar Lotufo crearon y demostraron que la Transformación de Bosque de Imagen (IFT) puede utilizarse para ahorrar tiempo en el procesamiento de imágenes 2D, 3D e imágenes en movimiento. [ 1 ]
Historia
En 1959, Dijkstra utilizó una estructura de datos de montón balanceado [ 1 ] [ 2 ] para mejorar un algoritmo presentado por Moore en 1957 [ 1 ] [ 3 ] y Bellman en 1958 [ 1 ] [ 4 ] que calculaba el costo de los caminos en un grafo general. La técnica de ordenación por cubetas fue como Dial mejoró el algoritmo una década después. [ 1 ] [ 5 ] El algoritmo ha sido ajustado y modificado de muchas maneras desde entonces. Es sobre esta versión que Falcao, Stolfi y Lotufo mejoraron. [ 1 ]
Definición
La transformación es una versión modificada del algoritmo de ruta más corta de Dijkstra, optimizada para usar más de una entrada y maximizar los operadores de procesamiento de imágenes digitales. [ 1 ] [ 2 ] La transformación crea un gráfico de los píxeles de una imagen, y las conexiones entre estos puntos representan el "costo" de la ruta. El costo se calcula inspeccionando las características, por ejemplo, escala de grises, color, gradiente, entre muchas otras, de la ruta entre píxeles. Se crean árboles conectando los píxeles que tienen el mismo costo o uno similar para aplicar el operador seleccionado. La robustez de la transformación tiene un costo y utiliza mucho espacio de almacenamiento para el código y los datos que se procesan. Una vez finalizada la transformación, se devuelven el predecesor, el costo y la etiqueta. La mayoría de los operadores que se utilizan para el procesamiento de imágenes digitales pueden usar esta información para optimizarse.
Mejoramiento
Dependiendo del operador de procesamiento de imágenes digitales seleccionado, el algoritmo puede ajustarse para su optimización según las herramientas que utilice dicho operador. También puede optimizarse eliminando el recálculo de trayectorias. Esto se logra mediante el uso de una tabla de referencia externa para registrar las trayectorias calculadas. Los "arcos inversos" pueden eliminarse comparando el costo de la trayectoria en ambas direcciones y descartando la más costosa. Asimismo, existe el caso en que el algoritmo devuelve infinito para algunas trayectorias. En este caso, se puede establecer un umbral para reemplazar el infinito, o bien la trayectoria se descartará y no se utilizará en cálculos posteriores.
Véase también
Referencias
- 1 2 3 4 5 6 7 Falcao, AX Stolfi, J. de Alencar Lotufo, R. : " La transformación de bosque de imágenes: teoría, algoritmos y aplicaciones ", En IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 26, NO. 1, ENERO DE 2004
- 1 2 E.W. Dijkstra, “ Una nota sobre dos problemas relacionados con grafos ”, Numerische Mathematik, vol. 1, págs. 269-271, 1959
- ↑ EF Moore, “El camino más corto a través de un laberinto”, Actas del Simposio Internacional sobre Teoría de la Conmutación, págs. 285-292, abril de 1959.
- ↑ R. Bellman, “ Sobre un problema de enrutamiento ”, Quarterly of Applied Math., vol. 16, pp. 87-90, 1958
- ↑ RB Dial, “ Bosque de caminos más cortos con ordenamiento topológico ”, Comm. ACM, vol. 12, n.º 11, págs. 632-633, noviembre de 1969
- Procesamiento de imágenes
