Cortes de grafos en la visión por computador

El corte de grafos es un método de segmentación de imágenes basado en regiones que puede ser utilizado para resolver de manera eficiente una amplia variedad de problemas de bajo nivel en la visión por computadora (visión artificial) como suavizar imágenes, el problema de correspondencia estereoscópica, y muchos otros que pueden ser formulados en términos de minimización de la energía.

Se basa en la teoría de grafos donde el problema de minimización de energía se puede reducir en términos del problema de flujo máximo de un grafo y, por consiguiente, gracias al teorema de flujo máximo corte mínimo se define un corte mínimo del grafo de forma que el tamaño del corte no es más grande en ningún otro corte. En la mayoría de las formulaciones de este tipo de problemas en la visión por computador, la solución de mínima energía corresponde a la estimación del máximo a posteriori de una solución.

Aunque muchos algoritmos de visión por computador impliquen cortar un grafo (por ejemplo, cortes normalizados), el término “cortes de grafos” se aplica específicamente a los modelos que utilizan optimización máximo flujo/ corte mínimo (otros algoritmos de corte de grafos pueden ser considerados como algoritmos de partición gráfica).

Historia

La teoría de los cortes de grafos se aplicó por primera vez en la visión por computador en el trabajo de Greig, Porteus i Seheult de la Universidad de Durham. En el contexto de la estadística bayesiana de suavizar imágenes ruidosas (o dañadas), ellos mostraron como la estimación del máximo a posteriori de una imagen binaria se puede obtener exactamente al maximizar el flujo a través de una red de imágenes asociadas, que suponen la incorporación de una fuente y un pozo. El problema se muestra por lo tanto, por ser una solución eficaz.

Antes de estos resultados, técnicas aproximadas, como el algoritmo del recozido simulado (propuesto por los hermanos German), o los modelos de reiteración condicional (como el que sugiere Julian Besag) fueron utilizados para resolver problemas de suavizar imágenes. Aunque el problema general con k colores siga sin resolver-se para k>2, la aproximación de Greig, Porteous i Seheult se ha presentado por tener una amplia aplicación en los problemas generales de visión por computador. Las aproximaciones de Greig, Porteus i Seheult acostumbran a aplicarse de forma iterativa para una secuencia de problemas binarios, en general dando soluciones prácticamente óptimas.

Conceptos

• Segmentación de imágenes: División de una imagen en regiones conexas y disjuntas relacionadas con los objetos de la escena y que cumplen un cierto criterio de homogeneidad.

• Clasificación de regiones: Identificar cada una de las regiones de una partición como parte de una clase o categoría (segmentación con regiones no necesariamente conexas).

• Etiquetado de regiones: Asignar una etiqueta (un color) diferente a cada componente conexa

• Conectividad entre píxeles: Dos píxeles de un conjunto están conectados si existe un camino que une los dos píxeles, de tal forma que todos los píxeles del camino estén en el mismo conjunto.
  • Conectividad 4 (la utilizada en segmentación): Cada píxel tiene 4 vecinos, en vertical y horizontal
  • Conectividad 8: Cada píxel tiene 8 vecinos, en vertical, horizontal y diagonal

Procedimiento

 

Ejemplos de cortes en una red de flujo

La imagen se modela como una red de flujo donde un píxel o un grupo de píxeles se asocian con los nodos y los pesos de los arcos definen la similitud entre los píxeles vecinos. Esta red de flujo tiene dos vértices diferenciados S (Fuente) y T (Pozo), que se corresponden con las dos semillas de la inicialización, y las capacidades de cada arco.

Un flujo es una función que a cada arco le asigna un valor entre 0 y su capacidad, representando la ley de conservación (para cada vórtice, excepto la Fuente y el Pozo, el flujo que entra es igual al que sale). El valor de un flujo es el que entra en el Pozo y se busca un flujo de valor máximo.

• Un corte en la red es una partición de los vértices en dos subconjuntos disyuntos, C_1 y C_2 de tal manera que S ∈ C_1 y T ∈ C_2
• Los arcos del corte son los que van de C_1 a C_2
• El valor del corte es la suma de las capacidades de sus arcos. Buscamos un corte de valor mínimo
  • El flujo de la red a través del corte es la suma de todas las capacidades alrededor desde S a T menos la suma de todas las capacidades alrededor desde T a S
  • La capacidad del corte es la suma de todas la capacidades alrededor desde S a T
  • Un corte mínimo es un corte donde su capacidad es la mínima de todos los cortes del grafo

Los problemas binarios (como la eliminación de ruido de una imagen binaria) se pueden resolver exactamente con este enfoque, los problemas en que los píxeles se pueden etiquetar con más de dos etiquetas diferentes (por ejemplo, la correspondencia estereoscópica o la eliminación de ruido de una imagen en niveles de gris) no se pueden resolver con exactitud, pero las soluciones producidas son, en general, cerca del óptimo global.

Algoritmos para resolver el problema del flujo máximo

• Algoritmo Ford-Fulkerson: Propone buscar caminos en los que se pueda aumentar el flujo, hasta que se llegue al flujo máximo.
• Algoritmo Edmonds-Karp: Idéntico al de Ford-Fulkerson a excepción de que definimos el orden de búsqueda para encontrar los caminos no saturados.. El camino encontrado tiene que ser el más corto entre los que aún tienen capacidad disponible.
• Algoritmo Push-Relabel: Se ajusta la altura de los nodos para que el flujo pase a través de la red como el agua a través de un paisaje. El flujo a través de la red no es necesariamente un flujo legal a través de la ejecución del algoritmo

Métodos existentes

• Cortes de grafos estándares: optimizan la función de energía sobre la segmentación
• Cortes de grafos repetitivos:

1. Primero se optimizan los parámetros de color utilizando K-means

2. Después se aplica el algoritmo habitual de cortes de grafos

Estos dos pasos se repiten de forma recursiva hasta la convergencia

• Cortes de grafos dinámicos: Permiten volver a ejecutar el algoritmo mucho más rápido después de modificar el problema (por ejemplo, después de que nuevas semillas se hayan incluido por el usuario).

Crítica

Los métodos de cortes de grafos se han convertido en una alternativa popular a las aproximaciones de nivel basadas en conjuntos para optimizar la localización de un contorno. Aun así, las aproximaciones con cortes de grafos han estado criticadas por diversas cuestiones:

• Artefactos de conversión al sistema métrico: Cuando una imagen está representad por una red de conectividad 4, los métodos de cortes de grafos pueden exhibir artefactos no deseados en forma de block. Diversos métodos han estado propuestos para abordar esta cuestión, como el uso de valores adicionales o por la formulación del problema de flujo máximo en un espacio continuo
• Disminución del corte: Desde que los cortes de grafos encuentran un corte mínimo, el algoritmo puede tender a producir un contorno fino. Por ejemplo, el algoritmo no es muy adecuado para la segmentación de objetos delgados como los vasos sanguíneos.
• Diversas etiquetas: Los cortes de grafos solo son capaces de encontrar un óptimo global para los problemas de etiquetaje binario (es decir, dos etiquetas), como la segmentación de imágenes primer plano/fondo. Se han propuesto ampliaciones que pueden encontrar soluciones aproximadas para los problemas de cortes de grafos de multietiquetaje.
• Memoria: La utilización de memoria de los cortes de grafos aumenta rápidamente con el aumento del tamaño de la imagen.

Referencias

• Aplicación de Graph Cuts en la edición de imágenes y vídeo
• Graph Cuts Approach to the Problems of Image

•   Datos: Q3774432