Cuenca hidrográfica (procesamiento de imágenes)

En el estudio del procesamiento de imágenes , una transformación de cuenca hidrográfica se define sobre una imagen en escala de grises . El nombre alude metafóricamente a una divisoria de aguas geológica , o divisoria de drenaje, que separa cuencas hidrográficas adyacentes . La transformación de cuenca hidrográfica 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 hidrográfica. En grafos , las líneas de cuenca pueden definirse en los nodos, en las aristas o ser líneas híbridas que abarquen tanto nodos como aristas. Las cuencas hidrográficas también pueden definirse en el dominio continuo . ^{[ 1 ]} Asimismo, existen numerosos algoritmos para calcular cuencas hidrográficas. Estos algoritmos se utilizan en el procesamiento de imágenes principalmente para la 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 profundo de los objetos separados.

• 
  Alivio de la magnitud del gradiente
• 
  imagen de magnitud de gradiente
• 
  Cuenca hidrográfica de la pendiente
• 
  Cuenca hidrográfica de la pendiente (relieve)

En geología, una divisoria de aguas es una línea divisoria que separa cuencas de captación adyacentes.

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 desde las fuentes y construir barreras donde confluyen diferentes fuentes de agua. El conjunto resultante de barreras constituye una cuenca hidrográfica por inundación. Desde entonces, se han introducido varias mejoras a este algoritmo, denominadas colectivamente Priority-Flood. ^{[ 3 ]}

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 de la trayectoria de mayor pendiente. En términos topográficos, esto ocurre si el punto se ubica en la cuenca de captación de dicho mínimo. La definición anterior no verifica esta condición.

Intuitivamente, la cuenca hidrográfica 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 cuenca hidrográfica de un grafo ponderado por aristas.

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:

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

Las nociones previas se centran en las cuencas hidrográficas, pero no en la línea divisoria resultante. La división 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 división 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 ₁ y M ₂ se define como la altitud mínima a la que se debe ascender para ir de M ₁ ^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 .

• Los mínimos locales del gradiente de la imagen pueden elegirse como marcadores; en este caso, se produce una sobresegmentación y un segundo paso implica la fusión de regiones.
• La transformación de cuencas hidrográficas basada en marcadores utiliza posiciones de marcadores específicas que han sido definidas explícitamente por el usuario o determinadas automáticamente con operadores morfológicos u otros métodos.

Uno de los algoritmos de cuenca hidrográfica 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, a este algoritmo, ^{[ 9 ]} incluyendo variantes adecuadas para conjuntos de datos que constan de billones de píxeles. ^{[ 10 ]}

El algoritmo funciona con una imagen en escala de grises. Durante la inundación sucesiva del relieve de valores grises, se construyen cuencas hidrográficas con cuencas de captación adyacentes. Este proceso de inundación se realiza sobre la imagen de gradiente, es decir, las cuencas deberían emerger a lo largo de los bordes. Normalmente, esto conlleva una sobresegmentación de la imagen, especialmente en el caso de material de imagen ruidoso, como por ejemplo datos de tomografía computarizada médica. En estos casos, es necesario preprocesar la imagen o fusionar las regiones posteriormente según un criterio de similitud.

1. Se selecciona 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 cuyo nivel de prioridad corresponde 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 agregan a dicha cola.
4. Repita el paso 3 hasta que la cola de prioridad esté vacía.

Los píxeles sin etiquetar son las líneas de división de aguas.

^{Jean Cousty et al. [ 12 ]} introdujeron las cuencas hidrográficas como bosques de expansión óptima. Establecen la consistencia de estas cuencas: pueden definirse de forma equivalente mediante sus cuencas de captación (a través de la propiedad de descenso más pronunciado) o mediante las líneas divisorias que las separan (a través del principio de la gota de agua). Posteriormente, demuestran, mediante un teorema de equivalencia, su optimalidad en términos de bosques de expansión mínima. A continuación, introducen un algoritmo de tiempo lineal para calcularlas. Cabe destacar que propiedades similares no se verifican en otros marcos teóricos y que el algoritmo propuesto es el más eficiente existente, tanto en teoría como en la práctica.

• 
  Una imagen con dos marcadores (verdes) y un bosque de expansión mínima calculado sobre el gradiente de la imagen.
• 
  Resultado de la segmentación mediante el algoritmo Minimum Spanning Forest.

En 2007, C. Allène et al. ^{[ 13 ]} establecieron vínculos entre los cortes de grafos y los bosques de expansión óptimos. Más precisamente, muestran que cuando la potencia de los pesos del grafo supera un cierto valor, el corte que minimiza la energía de los cortes del grafo es un corte realizado por un bosque de expansión máximo.

La transformación de bosque 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 ]} demostraron 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 de cuenca hidrográfica.

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. demostraron que cuando la potencia de los pesos del grafo 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 ]}

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

• Fernando Meyer. Un algoritmo óptimo para la línea de partición de aguas. 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 transformada de cuencas hidrográficas: definiciones, algoritmos y estrategias de paralelización . En Fundamenta Informaticae 41 (2000), pp. 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.

• La transformación de cuencas hidrográficas se archivó el 11 de abril de 2011 en la Wayback Machine con animaciones del algoritmo de cuencas hidrográficas.
• Transformación topológica de cuencas hidrográficas con artículos, diapositivas de clase y código fuente.
• Un plugin de código abierto para la gestión de cuencas hidrográficas en ImageJ .
• El kit de herramientas de topología (cuencas hidrográficas 2D y 3D basadas en el complejo de Morse )