|
Transformación divisoriaUna imagen en escala de grises puede ser vista como un relieve topográfico, donde se interpreta el nivel de gris de un píxel como su altura en el relieve. Una gota de agua que cae sobre un relieve topográfico fluye a lo largo de un camino para finalmente llegar a un mínimo local. Intuitivamente, la divisoria de un relieve corresponde a los límites de las cuencas hidrográficas adyacentes. En el procesamiento de imágenes se pueden calcular diversas líneas divisorias. En los grafos algunas pueden ser definidas sobre los nodos, las aristas o líneas híbridas sobre los nodos y aristas. Las divisorias también se puede definir en el dominio continuo.[1] También hay muchos algoritmos diferentes para calcular las divisorias. Para un propósito de segmentación de imágenes, la longitud del gradiente se interpreta como información de elevación.
ClasificaciónDivisoria por inundación La idea fue introducida en 1979 por S. Beucher y C. Lantuéjoul en.[2] Consiste en colocar una fuente de agua en cada mínimo regional para inundar el relieve desde las fuentes y construir barreras donde las distintas fuentes se unen. El conjunto resultante de barreras constituye una divisoria por inundación. Divisoria por distancia topográfica Intuitivamente, una gota de agua que cae sobre un relieve topográfico fluye más rápidamente hacia un mínimo. En la clase anterior no se verifica esta condición. Divisoria inter-pixelS. Beucher y F. Meyer introdujeron en[3] una definición algorítmica de la divisoria inter-pixel, dando el siguiente procedimiento: 1. Etiquete cada mínimo con una etiqueta distinta. Inicialice un conjunto S con los nodos etiquetados. 2. Extraiga de S un nodo x de mínima altitud F, es decir, F(x) = min{F(y)|y en S}. Asigne la etiqueta de x a cada nodo y no etiquetado adyacente a x, e inserte y en S. 3. Repita el paso 2 hasta que S esté vacío. Divisoria topológicaLas nociones anteriores se centran en las cuencas, pero no en la línea de separación producida. La divisoria topológica fue introducida por M. Couprie y G. Bertrand en 1997.[4] Se beneficia de la siguiente propiedad fundamental: una función W es una divisoria de una función F (F es una función que asigna pesos en las aristas de la gráfica asociada a la imagen) si y solo si W ≤ F y W conserva el contraste entre los mínimos regionales de F, donde el contraste entre dos mínimos regionales M1 y M2 se define como la altura mínima a la que hay que subir para ir de M1 a M2.[5] AlgoritmosDiversos enfoques pueden ser empleados para utilizar el principio de la divisoria para la segmentación de imágenes:
Algoritmo de inundación de MeyerUno de los algoritmos de divisoria más común fue presentado por F. Meyer en los años 90. El algoritmo funciona sobre una imagen en escala de grises. Durante las inundaciones sucesivas del relieve con valores de gris, las divisorias con cuencas adyacentes se construyen. Este proceso de inundaciones se lleva a cabo en la imagen del gradiente, es decir, las cuencas deben surgir a lo largo de los bordes. Normalmente, esto dará lugar a un exceso de segmentación de la imagen, especialmente para imágenes con ruido, por ejemplo, una TAC. O bien la imagen debe ser preprocesada o las regiones deben ser fusionadas después sobre la base de un criterio de similitud. Pasos:
Los píxeles no-etiquetados son las líneas divisorias. Algoritmos bosque de expansión óptimo (watershed cuts)Las divisorias como bosque de expansión óptimo han sido introducidas por Jean Cousty et al.[6] Ellos establecieron la compatibilidad de estas divisorias: pueden ser definidas equivalentemente por sus "cuencas de captación" (a través de la propiedad de descenso más rápido) o por la "línea divisoria" que separa las cuencas (a través del principio de la caída del agua). Luego, ellos prueban, a través de un teorema de equivalencia, su optimalidad en términos de bosques de expansión mínimo. Después, introducen un algoritmo de tiempo lineal para calcularlas. Vale la pena señalar que propiedades similares no se verifican en otros marcos y que el algoritmo propuesto es el algoritmo más eficiente existente, tanto en la teoría como en la práctica.
Vínculos con otros algoritmos de visión por computadorGraph CutsEn 2007, C. Allène et al.[7] establecieron vínculos que relacionan graph cuts a los bosques de expansión óptima. Más precisamente, muestran que cuando la potencia de los pesos del grafo está por encima de un cierto número, el corte que minimiza la energía de los graph cuts es un corte por bosques de expansión máxima. Bosques de camino más cortoLa image foresting transform (IFT) de Falcao et al.[8] es un procedimiento para calcular bosques de caminos más cortos. J. Cousty et al.[9] demostraron que cuando los marcadores de la IFT corresponden a extremos de la función peso, el corte inducido por el bosque es un watershed cut. Random WalkerEl algoritmo random walker es un algoritmo de segmentación que resuelve el problema de Dirichlet, adaptado para segmentación de imágenes por L. Grady en 2006.[10] En 2009, C. Couprie et al. demostraron que cuando el poder de los pesos del grafo convergen hacia el infinito, el corte que minimiza la energía del random walker es un corte por bosque de expansión máxima.[11] JerarquíasUna transformación jerárquica de divisorias transforma el resultado en un despliegue gráfico (es decir, se determinan las relaciones de vecindad de las regiones segmentadas) y aplica después transformaciones divisorias de forma recursiva. Referencias
Enlaces externos
|
