En el procesamiento de imágenes , la transformación grassfire es el cálculo de la distancia desde un píxel hasta el borde de una región. Puede describirse como "prender fuego" a los bordes de una región de la imagen para producir descriptores como el esqueleto o el eje medial de la región . Harry Blum introdujo el concepto en 1967. [1]
Motivación
El esqueleto de una región puede ser un descriptor útil, porque describe cosas como la simetría de la región, así como sus subpartes, depresiones y protuberancias. [2] También proporciona una forma de relacionar el interior de una región con la forma del límite. En la transformación Grassfire, el esqueleto se forma en los puntos de la región donde se encuentran los "incendios". En la literatura, esto se describe como el lugar de encuentro de formas de onda. [2]
Otra ventaja de utilizar el resultado de la transformación grassfire como descriptor es que es invertible. Suponiendo que se mantiene la información sobre cuándo se crea el eje medial o el esqueleto al encontrar formas de onda, entonces el esqueleto se puede restaurar radiando hacia afuera. [1]
Algoritmo de ejemplo
El siguiente algoritmo es un método simple de dos pasos para calcular la distancia de Manhattan desde el borde de una región. Por supuesto, hay varios otros algoritmos para realizar la transformación grassfire.
para cada fila en la imagen de izquierda a derecha para cada columna en la imagen de arriba a abajo si (el píxel está en la región ) { establece el píxel en 1 + valor mínimo de los vecinos norte y oeste } else { establece el píxel en cero } } } para cada fila de la derecha a la izquierda de cada columna de abajo a arriba , si ( píxel es en la región ) { conjunto de píxeles a min ( valor de la píxeles , 1 + mínimo valor de la al sur y al este vecinos ) } otro { conjunto de píxeles a cero } } }
A continuación se muestra el resultado de esta transformación. Es importante señalar que las líneas más intensas componen el esqueleto.
Aplicaciones
La transformación grassfire se puede abstraer para adaptarse a una variedad de problemas informáticos. Se ha demostrado que puede extenderse más allá del contexto de las imágenes a funciones arbitrarias. [3] Esto incluye aplicaciones en problemas de minimización de energía como los manejados por el algoritmo de Viterbi , propagación de creencias de producto máximo, asignación de recursos y métodos de control óptimos. [3]
También se puede utilizar para calcular la distancia entre regiones configurando el fondo como una región.
Ver también
Referencias
- ^ a b Blum, Harry. Una transformación para extraer nuevos descriptores de forma , 1967, " http://pageperso.lif.univ-mrs.fr/~edouard.thiel/rech/1967-blum.pdf ", 6/8/2012
- ^ a b Leymarie, F; Levine, MD (1992). "Simulación de la transformación Grassfire utilizando un modelo de contorno activo". Transacciones IEEE sobre análisis de patrones e inteligencia de máquinas . 14 : 56–75. doi : 10.1109 / 34.107013 .
- ^ a b Felzenszwalb, Pedro F; Huttenlocher, Daniel P (2012). "Transformaciones de distancia de funciones muestreadas". Teoría de la Computación . 8 : 415-28. CiteSeerX 10.1.1.88.1647 . doi : 10.4086 / toc.2012.v008a019 .