Cuenca hidrográfica (procesamiento de imágenes)

En geología, una cuenca hidrográfica es una división que separa cuencas de captación adyacentes.

Cuenca hidrográfica por inundacióneditar

La idea fue introducida en 1979 por S. Beucher y C. Lantuéjoul. La idea básica consistía en colocar una fuente de agua en cada mínimo regional del relieve, inundar todo el relieve de las fuentes y construir barreras cuando se encuentran diferentes fuentes de agua. El conjunto de barreras resultante constituye una cuenca hidrográfica por inundaciones. Desde entonces, se han realizado una serie de mejoras en este algoritmo, denominadas colectivamente Inundación de prioridades.

Cuenca hidrográfica por distancia topográficaeditar

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 mayor pendiente. 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.

Principio de la cuenca hidrográfica por gota de aguaeditar

Intuitivamente, la cuenca hidrográfica es una separación de los mínimos regionales desde los que una gota de agua puede fluir hacia mínimos distintos. Se proporcionó una formalización de esta idea intuitiva para definir una línea divisoria de aguas de un gráfico ponderado por bordes.

Entre píxeles watershedEdit

S. Beucher y F. Meyer introdujeron una implementación algorítmica entre píxeles del método watershed, dado el siguiente procedimiento:

1. Etiqueta cada mínimo con una etiqueta distinta. Inicialice 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}. Atribuya la etiqueta de x a cada nodo sin etiqueta y adyacente a x e inserte y en S.
3. Repita el paso 2 hasta que S esté vacío.

Cuenca hidrográfica topológicaeditar

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, beneficiándose de la siguiente propiedad fundamental.Una función W es una divisoria de aguas 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 M1 y M2 se define como la altitud mínima a la que se debe subir para pasar de M1 a M2. En el documento se detalla un algoritmo eficiente.

Algoritmo de cuenca

Se pueden emplear diferentes enfoques para usar 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 sobre-segmentación y un segundo paso implica la fusión de regiones.
• Transformación de cuencas basada en marcadores haga 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 cuenca hidrográfica más comunes fue introducido por F. Meyer a principios de la década de 1990, aunque una serie de mejoras, llamadas colectivamente Inundación de prioridad, se han realizado desde entonces a este algoritmo, incluidas variantes adecuadas para conjuntos de datos que consisten en billones de píxeles.

El algoritmo funciona en una imagen de 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 de 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, p. ej. datos de TAC médicos. O bien la imagen debe ser preprocesada o las regiones deben fusionarse sobre la base de un criterio de similitud posterior.

1. Se elige un conjunto de marcadores, píxeles donde comenzará la inundación. A cada uno se le da 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 alto 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. Rehacer 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 sustentada por marcadores para una población de pellets farmacéuticos. Las líneas divisorias de aguas se superponen en negro en la pila de imágenes de TC .

Algoritmos de bosque de expansión óptima (cortes de cuencas hidrográficas)Editar

Las cuencas hidrográficas como bosque de expansión óptima han sido introducidas por Jean Cousty et al. Establecen la consistencia de estas cuencas hidrográficas: pueden definirse de forma equivalente por sus «cuencas hidrográficas» (a través de una propiedad de descenso más pronunciada) o por las «líneas divisorias» que separan estas cuencas hidrográficas (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 expansión mínimos. Después, 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 teoría como en la práctica.

• Una imagen con dos marcadores (verde) y un Bosque de expansión mínimo calculado en el gradiente de la imagen.

• Resultado de la segmentación por Mínimo que Abarca el Bosque