En el estudio del procesamiento de imágenes , una línea divisoria de aguas es una transformación definida en una imagen en escala de grises . El nombre se refiere metafóricamente a una cuenca hidrográfica geológica , o división de drenaje, que separa las cuencas de drenaje adyacentes. La transformación de la cuenca trata la imagen sobre la que opera como un mapa topográfico , con el brillo de cada punto representando su altura, y encuentra las líneas que corren a lo largo de la parte superior de las crestas.
Existen diferentes definiciones técnicas de cuenca. En los gráficos , las líneas de las cuencas hidrográficas se pueden definir en los nodos, en los bordes o líneas híbridas en los nodos y los bordes. Las cuencas hidrográficas también se pueden definir en el dominio continuo. [1] También hay muchos algoritmos diferentes para calcular cuencas hidrográficas. Los algoritmos de cuencas hidrográficas se utilizan en el procesamiento de imágenes principalmente con fines de segmentación .
Alivio de la magnitud del gradiente
Imagen de magnitud de degradado
Cuenca del gradiente
Cuenca del gradiente (relieve)
Definiciones
En geología, una cuenca hidrográfica es una división que separa las cuencas de captación adyacentes.
Cuenca hidrográfica por inundación
La idea fue introducida en 1979 por S. Beucher y C. Lantuéjoul. [2] La idea básica consistía en colocar una fuente de agua en cada mínimo regional en el relieve, para inundar todo el relieve de fuentes y construir barreras cuando se encuentran diferentes fuentes de agua. El conjunto de barreras resultante constituye una línea divisoria de aguas por inundaciones. Desde entonces, se han realizado varias mejoras, denominadas colectivamente Priority-Flood, en este algoritmo. [3]
Cuenca hidrográfica por distancia topográfica
Intuitivamente, una gota de agua que cae sobre un relieve topográfico fluye hacia el mínimo "más cercano". El mínimo "más cercano" es el mínimo que se encuentra al final del camino de descenso más empinado. En términos de topografía, esto ocurre si el punto se encuentra en la cuenca de captación de ese mínimo. La definición anterior no verifica esta condición.
Cuenca por el principio de la gota de agua
Intuitivamente, la cuenca hidrográfica es una separación de los mínimos regionales desde los cuales una gota de agua puede fluir hacia mínimos distintos. Se proporcionó una formalización de esta idea intuitiva en [4] para definir una línea divisoria de aguas de un gráfico ponderado por bordes.
Cuenca hidrográfica entre píxeles
S. Beucher y F. Meyer introdujeron una implementación algorítmica entre píxeles del método de cuencas hidrográficas, [5] dado el siguiente procedimiento:
- Etiquete cada mínimo con una etiqueta distinta. Inicialice un conjunto S con los nodos etiquetados.
- Extraer de S un nodo x de altitud mínima F , es decir F ( x ) = min { F ( y ) | y ∈ S }. Atributo la etiqueta de x a cada nodo no marcado y adyacente a x , e insertar y en S .
- Repita el paso 2 hasta que S esté vacío.
Cuenca topológica
Las nociones anteriores se centran en las cuencas de captación, pero no en la línea de separación producida. La cuenca topológica fue introducida por M. Couprie y G. Bertrand en 1997, [6] y se benefició de la siguiente propiedad fundamental. Una función W es una cuenca de una función F 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 M 1 y M 2 se define como la altitud mínima a la que se debe ascender para pasar de M 1 a M 2 . [7] En el artículo se detalla un algoritmo eficiente. [8]
Algoritmo de cuencas hidrográficas
Se pueden emplear diferentes enfoques para utilizar el principio de cuenca para la segmentación de imágenes .
- Los mínimos locales del gradiente de la imagen se pueden elegir como marcadores, en este caso se produce una segmentación excesiva y un segundo paso implica la fusión de regiones.
- La transformación de cuencas hidrográficas basada en marcadores hace uso de posiciones de marcadores específicas que han sido definidas explícitamente por el usuario o determinadas automáticamente con operadores morfológicos u otras formas.
Algoritmo de inundación de Meyer
Uno de los algoritmos de cuencas hidrográficas más comunes fue introducido por F. Meyer a principios de la década de 1990, aunque desde entonces se han realizado varias mejoras, denominadas colectivamente Priority-Flood, [9] que incluyen variantes adecuadas para conjuntos de datos que constan de billones de píxeles. [10]
El algoritmo funciona en una imagen en escala de grises. Durante las sucesivas inundaciones del relieve del valor gris, se construyen cuencas hidrográficas con cuencas de captación adyacentes. Este proceso de inundación se realiza en la imagen del gradiente, es decir, las cuencas deben emerger a lo largo de los bordes. Normalmente, esto conducirá a una segmentación excesiva de la imagen, especialmente para material de imagen ruidoso, por ejemplo, datos médicos de TC. O la imagen debe procesarse previamente o las regiones deben fusionarse sobre la base de un criterio de similitud posteriormente.
- Se elige un conjunto de marcadores, píxeles donde comenzará la inundación. A cada uno se le asigna una etiqueta diferente.
- Los píxeles vecinos de cada área marcada se insertan en una cola de prioridad con un nivel de prioridad correspondiente a la magnitud del gradiente del píxel.
- El píxel con el nivel de prioridad más alto se extrae de la cola de prioridad. Si todos los vecinos del píxel extraído que ya se han etiquetado tienen la misma etiqueta, el píxel se etiqueta con su etiqueta. Todos los vecinos no marcados que aún no están en la cola de prioridad se colocan en la cola de prioridad.
- Vuelva a realizar el paso 3 hasta que la cola de prioridad esté vacía.
Los píxeles no etiquetados son las líneas divisorias de aguas.
Algoritmos de bosque de expansión óptimos (cortes de cuencas hidrográficas)
Las cuencas hidrográficas como bosque de extensión óptimo han sido introducidas por Jean Cousty et al. [12] Establecen la consistencia de estas cuencas hidrográficas: pueden definirse de manera equivalente por sus “cuencas de captación” (a través de una propiedad de descenso más empinado) o por las “líneas divisorias” que separan estas cuencas de captación (a través del principio de gota de agua). Luego prueban, a través de un teorema de equivalencia, su optimalidad en términos de bosques de extensión mínima. Luego, introducen un algoritmo de tiempo lineal para calcularlos. Vale la pena señalar que propiedades similares no se verifican en otros marcos y el algoritmo propuesto es el algoritmo existente más eficiente, tanto en la teoría como en la práctica.
Una imagen con dos marcadores (verde) y un Bosque de expansión mínimo calculado sobre el degradado de la imagen.
Resultado de la segmentación por bosque de expansión mínima
Vínculos con otros algoritmos en visión artificial
Cortes de gráficos
En 2007, C. Allène et al. [13] estableció vínculos que relacionan Graph Cuts con bosques de expansión óptimos. Más precisamente, muestran que cuando la potencia de los pesos del gráfico está por encima de un cierto número, el corte que minimiza el gráfico corta la energía es un corte por bosque de extensión máxima.
Bosques de camino más corto
La imagen de transformación forestal (IFT) de Falcao et al. [14] es un procedimiento para calcular bosques de ruta más corta. Ha sido probado por J. Cousty et al. [15] que cuando los marcadores del IFT corresponden a los extremos de la función de peso, el corte inducido por el bosque es un corte de cuenca.
Caminante aleatorio
El algoritmo de caminante aleatorio es un algoritmo de segmentación que resuelve el problema de Dirichlet combinatorio , adaptado a la segmentación de imágenes por L. Grady en 2006. [16] En 2011, C. Couprie et al. demostró que cuando la potencia de los pesos del gráfico converge hacia el infinito, el corte que minimiza la energía del caminante aleatorio es un corte por bosque de extensión máxima. [17]
Jerarquías
Una transformación de cuencas hidrográficas jerárquicas convierte el resultado en una representación gráfica (es decir, se determinan las relaciones vecinas de las regiones segmentadas) y aplica más transformaciones de cuencas hidrográficas de forma recursiva. Consulte [18] para obtener más detalles. En [19] se desarrolló una teoría que vincula la cuenca hidrográfica con las segmentaciones jerárquicas .
Notas
- ^ L. Najman y M. Schmitt. Cuenca de función continua . En Signal Processing (número especial sobre morfología matemática), vol. 38 (1994), páginas 99–112
- ↑ Taller de Serge Beucher y Christian Lantuéj sobre procesamiento de imágenes, detección de bordes y movimiento en tiempo real (1979). http://cmm.ensmp.fr/~beucher/publi/watershed.pdf
- ^ Barnes, R., Lehman, C., Mulla, D., 2014. Priority-flood: Un algoritmo óptimo de llenado de depresión y etiquetado de cuencas hidrográficas para modelos digitales de elevación . Computadoras y geociencias 62, 117–127. doi : 10.1016 / j.cageo.2013.04.024
- ^ J. Cousty, G. Bertrand, L. Najman y M. Couprie. Cortes de cuencas hidrográficas: bosques de expansión mínima y el principio de la gota de agua , transacciones IEEE sobre análisis de patrones e inteligencia de máquinas 31 (8) págs. 1362-1374, 2009,
- ^ Serge Beucher y Fernand Meyer. El enfoque morfológico de la segmentación: la transformación de cuencas . En Morfología matemática en el procesamiento de imágenes (Ed. ER Dougherty), páginas 433–481 (1993).
- ^ M. Couprie, G. Bertrand. Transformación de cuencas hidrográficas en escala de grises topológica. En Proc. de SPIE Vision Geometry V, volumen 3168, páginas 136-146 (1997). http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.3.7654&rep=rep1&type=pdf
- ^ G. Bertrand. En cuencas hidrográficas topológicas . Journal of Mathematical Imaging and Vision, 22 (2–3), páginas 217–230 (2005).
- ^ Michel Couprie, Laurent Najman, Gilles Bertrand. Algoritmos cuasi-lineales para la cuenca topológica . Revista de imágenes y visión matemáticas, Springer Verlag, 2005, 22 (2-3), págs.231-249.
- ^ Barnes, R., Lehman, C., Mulla, D., 2014. Priority-flood: Un algoritmo óptimo de llenado de depresión y etiquetado de cuencas hidrográficas para modelos digitales de elevación . Computadoras y geociencias 62, 117–127. doi : 10.1016 / j.cageo.2013.04.024
- ^ Barnes, R., 2016. Relleno de depresión de inundación de prioridad paralela para modelos de elevación digital de billones de células en escritorios o clústeres. Informática y Geociencias. doi : 10.1016 / j.cageo.2016.07.001
- ^ Doerr, FJS y Florence, AJ (2020). Metodología de análisis de imágenes micro-XRT y aprendizaje automático para la caracterización de formulaciones de cápsulas de partículas múltiples. Revista Internacional de Farmacia: X, 2, 100041. https://doi.org/10.1016/j.ijpx.2020.100041
- ^ Jean Cousty, Gilles Bertrand, Laurent Najman y Michel Couprie. Cortes de cuencas hidrográficas: bosques de extensión mínima y el principio de la gota de agua . Transacciones IEEE sobre análisis de patrones e inteligencia de máquinas. 31 (8). Agosto de 2009. págs. 1362-1374.
- ^ Cédric Allène, Jean-Yves Audibert, Michel Couprie y Renaud Keriven: " Algunos vínculos entre cortes mínimos , bosques y cuencas hidrográficas óptimos ", Image and Vision Computing, 2009.
- ^ Falcao, AX Stolfi, J. de Alencar Lotufo, R.: " La transformación forestal de imágenes: teoría, algoritmos y aplicaciones ", en PAMI, 2004
- ^ Jean Cousty, Gilles Bertrand, Laurent Najman y Michel Couprie. Cortes de cuencas hidrográficas: aclareos, bosques de camino más corto y cuencas hidrográficas topológicas . Transacciones IEEE sobre análisis de patrones e inteligencia de máquinas. 32 (5). 2010. págs. 925–939.
- ^ Grady, L .: " Caminatas al azar para la segmentación de imágenes ". PAMI, 2006
- ^ Camille Couprie, Leo Grady, Laurent Najman y Hugues Talbot, " Power Watersheds: A Unifying Graph-Based Optimization Framework ", IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 33, No. 7, págs. 1384-1399, julio 2011
- ^ Laurent Najman, Michel Schmitt. Saliencia geodésica de contornos de cuencas hidrográficas y segmentación jerárquica . IEEE Transactions on Pattern Analysis and Machine Intelligence, Instituto de Ingenieros Eléctricos y Electrónicos, 1996, 18 (12), pp.1163-1173.
- ^ Laurent Najman. Sobre la equivalencia entre segmentaciones jerárquicas y cuencas ultramétricas . Revista de imágenes y visión matemáticas, Springer Verlag, 2011, 40 (3), págs.231-247.
Referencias
- Fernand Meyer. Un algoritmo óptimo para la ligne de partage des eaux. Dans 8 me congrès de reconnaissance des formes et intelligence artificielle , vol. 2 (1991), páginas 847–857, Lyon, Francia.
- Luc Vincent y Pierre Soille. Cuencas hidrográficas en espacios digitales: un algoritmo eficiente basado en simulaciones de inmersión . En IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 13, Núm. 6 (1991), páginas 583–598.
- L. Najman y M. Schmitt. Relevancia geodésica de contornos de cuencas hidrográficas y segmentación jerárquica . En IEEE Transactions on Pattern Analysis and Machine Intelligence , vol. 18, Núm. 12 (1996), páginas 1163-1173.
- JBTM Roerdink y A. Meijster. La transformación de las cuencas hidrográficas: definiciones, algoritmos y estrategias de paralelización . En Fundamenta Informaticae 41 (2000), págs. 187–228.
- Laurent Najman, Michel Couprie y Gilles Bertrand. Cuencas hidrográficas, mosaicos y el paradigma de la emergencia . En Matemáticas Aplicadas Discretas , Vol. 147, Núm. 2–3 (2005), páginas 301–324.
enlaces externos
- La Transformación de Cuenca con animaciones del algoritmo de Cuenca.
- Transformación topológica de cuencas hidrográficas con artículos, diapositivas de conferencias y código fuente.
- Un complemento de cuenca de código abierto para ImageJ .
- El Kit de herramientas de topología (cuencas hidrográficas 2D y 3D basadas en el complejo Morse )