stringtranslate.com

Cuenca hidrográfica (procesamiento de imágenes)

En el estudio del procesamiento de imágenes , una cuenca hidrográfica 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 divisoria de aguas, que separa cuencas hidrográficas adyacentes . La transformación de cuencas hidrográficas trata la imagen sobre la que opera como un mapa topográfico , donde el brillo de cada punto representa su altura, y encuentra las líneas que recorren las cimas de las crestas.

Existen diferentes definiciones técnicas de una cuenca hidrográfica. En los gráficos , las líneas de cuenca hidrográfica pueden definirse en los nodos, en los bordes o líneas híbridas en los nodos y los bordes. Las cuencas hidrográficas también pueden definirse en el dominio continuo . [1] También existen muchos algoritmos diferentes para calcular las cuencas hidrográficas. Los algoritmos de cuencas hidrográficas se utilizan en el procesamiento de imágenes principalmente con fines de segmentación de objetos , es decir, para separar diferentes objetos en una imagen. Esto permite contar los objetos o realizar un análisis más detallado de los objetos separados.

Definiciones

En geología, una cuenca hidrográfica es una línea divisoria que separa cuencas hidrográficas adyacentes.

Cuenca por inundaciones

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 del relieve, inundar todo el relieve a partir de las fuentes y construir barreras cuando se encuentran diferentes fuentes de agua. El conjunto de barreras resultante constituye una cuenca hidrográfica por inundación. Desde entonces se han realizado varias mejoras a este algoritmo, denominadas colectivamente Priority-Flood. [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 aquel que se encuentra al final del camino de mayor descenso. En términos topográficos, 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.

Principio de la cuenca hidrográfica por 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. En [4] se proporcionó una formalización de esta idea intuitiva para definir una cuenca hidrográfica de un gráfico ponderado por aristas.

Cuenca hidrográfica entre píxeles

S. Beucher y F. Meyer introdujeron una implementación algorítmica entre píxeles del método de cuenca hidrográfica, [5] dado el siguiente procedimiento:

  1. Etiqueta cada mínimo con una etiqueta distinta. Inicializa un conjunto S con los nodos etiquetados.
  2. Extraer de S un nodo x de altitud mínima F , es decir F ( x ) = min{ F ( y )| y  ∈  S }. Atribuir la etiqueta de x a cada nodo no etiquetado y adyacente a x , e insertar y en  S .
  3. Repita el paso 2 hasta que S esté vacío.

Cuenca topológica

Las nociones anteriores se centran en las cuencas hidrográficas, pero no en la línea de separación producida. La cuenca hidrográfica topológica fue introducida por M. Couprie y G. Bertrand en 1997, [6] y se beneficia de la siguiente propiedad fundamental. Una función W es una cuenca hidrográfica de una función F si y solo si W ≤ F y W preserva 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 ir de M 1 a M 2 . [7] En el artículo se detalla un algoritmo eficiente. [8]

Algoritmo de cuenca hidrográfica

Se pueden emplear diferentes enfoques para utilizar el principio de cuenca hidrográfica para la segmentación de imágenes .

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 los años 1990, aunque desde entonces se han realizado varias mejoras a este algoritmo, denominadas colectivamente Priority-Flood, [9] incluidas variantes adecuadas para conjuntos de datos que constan de billones de píxeles. [10]

El algoritmo funciona sobre una imagen en escala de grises. Durante la inundación sucesiva del relieve en escala de grises, se construyen cuencas hidrográficas con cuencas adyacentes. Este proceso de inundación se realiza sobre la imagen de gradiente, es decir, las cuencas deben emerger a lo largo de los bordes. Normalmente, esto conducirá a una sobresegmentación de la imagen, especialmente en el caso de material de imagen ruidoso, por ejemplo, datos de TC médicos. La imagen debe procesarse previamente o las regiones deben fusionarse posteriormente sobre la base de un criterio de similitud.

  1. Se elige un conjunto de marcadores, píxeles donde comenzará la inundación. A cada uno se le asigna una etiqueta diferente.
  2. 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.
  3. El píxel con el nivel de prioridad más bajo se extrae de la cola de prioridad. Si los vecinos del píxel extraído que ya han sido etiquetados tienen todos la misma etiqueta, entonces 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.
  4. Repita el paso 3 hasta que la cola de prioridad esté vacía.

Los píxeles no etiquetados son las líneas divisorias de aguas.

Ejemplo de una transformación de línea divisoria de aguas con soporte de marcadores para una población de gránulos farmacéuticos. Las líneas divisorias de aguas se superponen en negro sobre la pila de imágenes de TC. [11]

Algoritmos óptimos de forestación extensiva (cortes de cuencas hidrográficas)

Jean Cousty et al. [12] introdujeron las cuencas hidrográficas como bosques de expansión óptima. Establecieron 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 pronunciado) o por las “líneas divisorias” que separan estas cuencas de captación (a través del principio de la gota de agua). Luego demostraron, a través de un teorema de equivalencia, su optimalidad en términos de bosques de expansión mínima. Después, introdujeron un algoritmo de tiempo lineal para calcularlos. Vale la pena señalar que no se verifican propiedades similares en otros marcos y el algoritmo propuesto es el algoritmo existente más eficiente, tanto en teoría como en la práctica.

Enlaces con otros algoritmos en visión artificial

Recortes de gráficos

En 2007, C. Allène et al. [13] establecieron vínculos que relacionan los cortes de grafos con los bosques de expansión óptimos. Más precisamente, muestran que cuando la potencia de los pesos del grafo es superior a un cierto número, el corte que minimiza la energía de los cortes de grafos es un corte por bosque de expansión máxima.

Bosques de caminos más cortos

La transformada de forestación de imágenes (IFT) de Falcao et al. [14] es un procedimiento para calcular bosques de caminos más cortos. J. Cousty et al. [15] han demostrado que cuando los marcadores de la IFT corresponden a los extremos de la función de peso, el corte inducido por el bosque es un corte divisorio de aguas.

Caminante aleatorio

El algoritmo del caminante aleatorio es un algoritmo de segmentación que resuelve el problema combinatorio de Dirichlet , adaptado a la segmentación de imágenes por L. Grady en 2006. [16] En 2011, C. Couprie et al. demostraron 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 máxima expansión. [17]

Jerarquías

Una transformación de cuenca hidrográfica jerárquica convierte el resultado en una representación gráfica (es decir, se determinan las relaciones vecinales de las regiones segmentadas) y aplica otras transformaciones de cuenca hidrográfica de forma recursiva. Véase [18] para obtener más detalles. En [19] se ha desarrollado una teoría que vincula la cuenca hidrográfica con las segmentaciones jerárquicas.

Notas

  1. ^ L. Najman y M. Schmitt. Cuenca de una función continua. En Procesamiento de señales (Número especial sobre morfología matemática), vol. 38 (1994), páginas 99-112
  2. ^ Taller de Serge Beucher y Christian Lantuéj sobre procesamiento de imágenes, detección de movimiento y bordes en tiempo real (1979). http://cmm.ensmp.fr/~beucher/publi/watershed.pdf
  3. ^ Barnes, R., Lehman, C., Mulla, D., 2014. Inundación prioritaria: un algoritmo óptimo de llenado de depresiones y etiquetado de cuencas hidrográficas para modelos digitales de elevación. Computers & Geosciences 62, 117–127. doi :10.1016/j.cageo.2013.04.024
  4. ^ J. Cousty, G. Bertrand, L. Najman y M. Couprie. Cortes de cuencas hidrográficas: bosques de mínima extensión y el principio de la gota de agua, IEEE Transactions on Pattern Analysis and Machine Intelligence 31(8) pp. 1362-1374, 2009,
  5. ^ Serge Beucher y Fernand Meyer. El enfoque morfológico de la segmentación: la transformación de cuenca hidrográfica. En Morfología matemática en el procesamiento de imágenes (Ed. ER Dougherty), páginas 433–481 (1993).
  6. ^ M. Couprie, G. Bertrand. Transformada topológica de cuencas hidrográficas en escala de grises. En Proc. of 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
  7. ^ G. Bertrand. Sobre cuencas hidrográficas topológicas. Journal of Mathematical Imaging and Vision, 22(2–3), páginas 217–230 (2005).
  8. ^ Michel Couprie, Laurent Najman, Gilles Bertrand. Algoritmos cuasi-lineales para la cuenca hidrográfica topológica. Journal of Mathematical Imaging and Vision, Springer Verlag, 2005, 22 (2-3), pp.231-249.
  9. ^ Barnes, R., Lehman, C., Mulla, D., 2014. Inundación prioritaria: un algoritmo óptimo de llenado de depresiones y etiquetado de cuencas hidrográficas para modelos digitales de elevación. Computers & Geosciences 62, 117–127. doi :10.1016/j.cageo.2013.04.024
  10. ^ Barnes, R., 2016. Relleno de depresiones por inundación con prioridad paralela para modelos de elevación digital de billones de celdas en computadoras de escritorio o clústeres. Computers & Geosciences. doi :10.1016/j.cageo.2016.07.001
  11. ^ Doerr, FJS y Florence, AJ (2020). Análisis de imágenes micro-XRT y metodología de aprendizaje automático para la caracterización de formulaciones de cápsulas multiparticuladas. Revista internacional de farmacia: X, 2, 100041. https://doi.org/10.1016/j.ijpx.2020.100041
  12. ^ Jean Cousty, Gilles Bertrand, Laurent Najman y Michel Couprie. Cortes de cuencas hidrográficas: bosques de mínima extensión y el principio de la gota de agua. IEEE Transactions on Pattern Analysis and Machine Intelligence. 31 (8). Agosto de 2009. págs. 1362–1374.
  13. ^ Cédric Allène, Jean-Yves Audibert, Michel Couprie y Renaud Keriven: "Algunos vínculos entre cortes mínimos, bosques de cobertura óptima y cuencas hidrográficas", Image and Vision Computing, 2009.
  14. ^ Falcao, AX Stolfi, J. de Alencar Lotufo, R. : "La transformación de forestación de imágenes: teoría, algoritmos y aplicaciones", en PAMI, 2004
  15. ^ Jean Cousty, Gilles Bertrand, Laurent Najman y Michel Couprie. Cortes de cuencas hidrográficas: aclareos, bosques de caminos más cortos y cuencas hidrográficas topológicas. IEEE Transactions on Pattern Analysis and Machine Intelligence. 32 (5). 2010. págs. 925–939.
  16. ^ Grady, L.: "Recorridos aleatorios para la segmentación de imágenes". PAMI, 2006
  17. ^ Camille Couprie, Leo Grady, Laurent Najman y Hugues Talbot, "Cuencas hidrográficas de potencia: un marco de optimización basado en gráficos unificador", IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 33, n.º 7, págs. 1384-1399, julio de 2011
  18. ^ 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), págs. 1163-1173.
  19. ^ Laurent Najman. Sobre la equivalencia entre segmentaciones jerárquicas y cuencas hidrográficas ultramétricas. Journal of Mathematical Imaging and Vision, Springer Verlag, 2011, 40 (3), pp.231-247.

Referencias

Enlaces externos