stringtranslate.com

Cuenca (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 geológica , o división de drenaje, que separa cuencas de drenaje adyacentes . La transformación de cuenca 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 cuenca. En los gráficos , las líneas divisorias de aguas pueden definirse en los nodos, en los bordes o líneas híbridas tanto en los nodos como en los bordes. Las cuencas hidrográficas también pueden definirse en el dominio continuo . [1] También existen muchos algoritmos diferentes para calcular cuencas hidrográficas. Los algoritmos de cuenca 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 división 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, para inundar todo el relieve desde las fuentes, y construir barreras cuando se encuentren diferentes fuentes de agua. El conjunto de barreras resultante constituye una cuenca hidrográfica por inundación. Desde entonces, se han realizado en este algoritmo una serie de mejoras, denominadas colectivamente Priority-Flood. [3]

Cuenca 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 mínimo que se encuentra al final del camino de descenso más pronunciado. En términos topográficos, esto ocurre si el punto se encuentra en la cuenca de ese mínimo. La definición anterior no verifica esta condición.

Cuenca hidrográfica por el principio de la gota de agua.

Intuitivamente, la cuenca es una separación de los mínimos regionales desde la cual una gota de agua puede fluir hacia mínimos distintos. En [4] se proporcionó una formalización de esta idea intuitiva 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 la cuenca, [5] dado el siguiente procedimiento:

  1. Etiquete cada mínimo con una etiqueta distinta. Inicialice un conjunto S con los nodos etiquetados.
  2. Extraer de S un nodo x de mínima altitud F , es decir F ( x ) = min{ F ( y )| y  ∈  S }. Atribuya la etiqueta de x a cada nodo no etiquetado y adyacente a x e inserte 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 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 línea divisoria de aguas de una función F si y sólo 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 pasar de M 1 a M 2 . [7] En el artículo se detalla un algoritmo eficiente. [8]

Algoritmo de cuenca

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 la década de 1990, aunque desde entonces se han realizado en este algoritmo una serie de mejoras, 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 las sucesivas inundaciones del relieve de valor gris, se construyen cuencas hidrográficas con cuencas hidrográficas adyacentes. Este proceso de inundación se realiza en la imagen de gradiente, es decir, las cuencas deben emerger a lo largo de los bordes. Normalmente, esto dará lugar a una sobresegmentación de la imagen, especialmente en el caso de material de imagen ruidoso, por ejemplo, datos de TC médicos. O es necesario preprocesar la imagen o fusionar posteriormente las regiones según 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 todos los vecinos del píxel extraído que ya han sido etiquetados tienen 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.

Ejemplo de una transformación de cuenca hidrográfica apoyada por marcadores para una población de gránulos farmacéuticos. Las líneas divisorias de aguas están superpuestas en negro en la pila de imágenes de CT. [11]

Algoritmos óptimos de extensión forestal (cortes de cuencas)

Jean Cousty et al. han presentado las cuencas hidrográficas como bosques de extensión óptima. [12] Establecen la consistencia de estas cuencas: 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 prueban, mediante un teorema de equivalencia, su optimización 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 que el algoritmo propuesto es el algoritmo existente más eficiente, tanto en la teoría como en la práctica.

Vínculos con otros algoritmos en visión por computadora

Cortes de gráficos

En 2007, C. Allène et al. [13] establecieron vínculos que relacionan Graph Cuts con bosques de extensión óptima. 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 la energía del gráfico es un corte de bosque de máxima extensión.

Bosques de camino más corto

La transformada de forestación de imágenes (IFT) de Falcao et al. [14] es un procedimiento para calcular bosques de camino más corto. Ha sido demostrado por J. Cousty et al. [15] que cuando los marcadores del IFT corresponden a 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 combinatorio de Dirichlet , 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 de bosque de máxima extensión. [17]

Jerarquías

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

Notas

  1. ^ L. Najman y M. Schmitt. Cuenca de una función continua. En Signal Processing (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 movimientos 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 depresión y etiquetado de cuencas hidrográficas para modelos de elevación digitales. Computadoras y geociencias 62, 117–127. doi :10.1016/j.cageo.2013.04.024
  4. ^ J. Cousty, G. Bertrand, L. Najman y M. Couprie. Cortes de cuencas: bosques de extensión mínima y el principio de la gota de agua, IEEE Transactions on Pattern Analysis and Machine Intelligence 31(8) págs. 1362-1374, 2009,
  5. ^ Serge Beucher y Fernand Meyer. El enfoque morfológico de la segmentación: la transformación de la cuenca. En Morfología matemática en el procesamiento de imágenes (Ed. ER Dougherty), páginas 433–481 (1993).
  6. ^ M. Couprie, G. Bertrand. Transformación topológica de cuencas hidrográficas en escala de grises. 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
  7. ^ G. Bertrand. Sobre cuencas 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 topológica. Revista de visión y imágenes matemáticas, Springer Verlag, 2005, 22 (2-3), páginas 231-249.
  9. ^ Barnes, R., Lehman, C., Mulla, D., 2014. Inundación prioritaria: un algoritmo óptimo de llenado de depresión y etiquetado de cuencas hidrográficas para modelos de elevación digitales. Computadoras y geociencias 62, 117–127. doi :10.1016/j.cageo.2013.04.024
  10. ^ Barnes, R., 2016. Relleno paralelo de depresión de inundación prioritaria para modelos de elevación digitales de billones de células en computadoras de escritorio o clústeres. Computadoras y Geociencias. doi :10.1016/j.cageo.2016.07.001
  11. ^ Doerr, FJS y Florence, AJ (2020). Una metodología de aprendizaje automático y análisis de imágenes micro-XRT para la caracterización de formulaciones de cápsulas multipartículas. Revista Internacional de Farmacéutica: 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: bosques de extensión mínima y el principio de la gota de agua. Transacciones IEEE sobre análisis de patrones e inteligencia artificial. 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 extensión óptima y cuencas hidrográficas", Image and Vision Computing, 2009.
  14. ^ Falcao, AX Stolfi, J. de Alencar Lotufo, R.: "La transformación del bosque de imágenes: teoría, algoritmos y aplicaciones", en PAMI, 2004
  15. ^ Jean Cousty, Gilles Bertrand, Laurent Najman y Michel Couprie. Cortes de cuencas: aclareos, bosques de camino más corto y cuencas topológicas. Transacciones IEEE sobre análisis de patrones e inteligencia artificial. 32 (5). 2010. págs. 925–939.
  16. ^ Grady, L.: "Paseos aleatorios para segmentación de imágenes". PAMI, 2006
  17. ^ 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
  18. ^ Laurent Najman, Michel Schmitt. Prominencia geodésica de los contornos de cuencas hidrográficas y segmentación jerárquica. Transacciones IEEE sobre análisis de patrones e inteligencia de máquinas, Instituto de Ingenieros Eléctricos y Electrónicos, 1996, 18 (12), páginas 1163-1173.
  19. ^ Laurent Najman. Sobre la equivalencia entre segmentaciones jerárquicas y cuencas ultramétricas. Revista de visión y imágenes matemáticas, Springer Verlag, 2011, 40 (3), páginas 231-247.

Referencias

enlaces externos