Recortes de gráficos en visión artificial

Tal como se aplica en el campo de la visión por computadora , la optimización del corte de grafos se puede emplear para resolver de manera eficiente una amplia variedad de problemas de visión por computadora de bajo nivel ( visión temprana ^[1] ), como suavizado de imágenes , el problema de correspondencia estéreo , segmentación de imágenes , cosegmentación de objetos y muchos otros problemas de visión por computadora que se pueden formular en términos de minimización de energía . Muchos de estos problemas de minimización de energía se pueden aproximar resolviendo un problema de flujo máximo en un grafo ^[2] (y así, por el teorema de flujo máximo-corte mínimo , definir un corte mínimo del grafo). Bajo la mayoría de las formulaciones de tales problemas en visión por computadora, la solución de energía mínima corresponde a la estimación máxima a posteriori de una solución. Aunque muchos algoritmos de visión por computadora implican cortar un grafo (por ejemplo, cortes normalizados), el término "cortes de grafos" se aplica específicamente a aquellos modelos que emplean una optimización de flujo máximo/corte mínimo (otros algoritmos de corte de grafos pueden considerarse como algoritmos de partición de grafos ).

Los problemas "binarios" (como la eliminación de ruido de una imagen binaria ) se pueden resolver con exactitud utilizando este enfoque; los problemas en los que los píxeles se pueden etiquetar con más de dos etiquetas diferentes (como la correspondencia estéreo o la eliminación de ruido de una imagen en escala de grises ) no se pueden resolver con exactitud, pero las soluciones producidas suelen estar cerca del óptimo global.

Historia

La teoría de los cortes de grafos utilizada como método de optimización se aplicó por primera vez en la visión por computadora en el artículo seminal de Greig, Porteous y Seheult ^[3] de la Universidad de Durham . Allan Seheult y Bruce Porteous eran miembros del elogiado grupo de estadística de Durham de la época, dirigido por Julian Besag y Peter Green , y la experta en optimización Margaret Greig era conocida por ser la primera mujer miembro del personal del Departamento de Ciencias Matemáticas de Durham.

En el contexto estadístico bayesiano de suavizado de imágenes ruidosas (o corruptas), demostraron cómo la estimación máxima a posteriori de una imagen binaria se puede obtener exactamente maximizando el flujo a través de una red de imágenes asociada, lo que implica la introducción de una fuente y un sumidero . Por lo tanto, se demostró que el problema se podía resolver de manera eficiente. Antes de este resultado, se utilizaban técnicas aproximadas como el recocido simulado (como propusieron los hermanos Geman ), ^[4] o los modos condicionales iterados (un tipo de algoritmo voraz sugerido por Julian Besag ) ^[5] para resolver tales problemas de suavizado de imágenes.

Aunque el problema general de los colores sigue sin resolverse con el enfoque de Greig, Porteous y Seheult ^[3], se ha demostrado ^{[6] [7]} que tiene una amplia aplicabilidad en problemas generales de visión por computadora. Los enfoques de Greig, Porteous y Seheult se aplican a menudo de forma iterativa a una secuencia de problemas binarios, y normalmente producen soluciones casi óptimas. ${\displaystyle k}$ ${\displaystyle k>2,}$

En 2011, C. Couprie et al . ^[8] propusieron un marco de segmentación de imágenes general, llamado "Power Watershed", que minimizaba una función indicadora de valor real de [0,1] sobre un gráfico, restringido por semillas de usuario (o términos unarios) establecidas en 0 o 1, en el que la minimización de la función indicadora sobre el gráfico se optimiza con respecto a un exponente . Cuando , Power Watershed se optimiza mediante cortes de gráfico, cuando Power Watershed se optimiza mediante caminos más cortos, se optimiza mediante el algoritmo de caminante aleatorio y se optimiza mediante el algoritmo de cuenca hidrográfica . De esta manera, Power Watershed puede verse como una generalización de cortes de gráfico que proporciona una conexión directa con otros algoritmos de segmentación/agrupamiento de optimización de energía. ${\displaystyle p}$ ${\displaystyle p=1}$ ${\displaystyle p=0}$ ${\displaystyle p=2}$ ${\displaystyle p=\infty }$

Segmentación binaria de imágenes

Notación

• Imagen: ${\displaystyle x\in \{R,G,B\}^{N}}$
• Salida: Segmentación (también llamada opacidad) (segmentación suave). Para la segmentación dura ${\displaystyle S\in R^{N}}$ ${\displaystyle S\in \{0{\text{ for background}},1{\text{ for foreground/object to be detected}}\}^{N}}$
• Función de energía : donde C es el parámetro de color y λ es el parámetro de coherencia. ${\displaystyle E(x,S,C,\lambda )}$
• ${\displaystyle E(x,S,C,\lambda )=E_{\rm {color}}+E_{\rm {coherence}}}$
• Optimización: La segmentación se puede estimar como un mínimo global sobre S: ${\displaystyle {\arg \min }_{S}E(x,S,C,\lambda )}$

Métodos existentes

• Cortes de gráficos estándar: optimiza la función de energía sobre la segmentación (valor S desconocido).
• Cortes de gráficos iterados:

1. El primer paso optimiza los parámetros de color utilizando K-means.
2. El segundo paso ejecuta el algoritmo habitual de cortes de gráficos.

Estos 2 pasos se repiten recursivamente hasta la convergencia.

• Cortes de gráficos dinámicos:
  permite volver a ejecutar el algoritmo mucho más rápido después de modificar el problema (por ejemplo, después de que un usuario haya agregado nuevas semillas).

Función energética

${\displaystyle \Pr(x\mid S)=K^{-E}}$

donde la energía se compone de dos modelos diferentes ( y ): ${\displaystyle E}$ ${\displaystyle E_{\rm {color}}}$ ${\displaystyle E_{\rm {coherence}}}$

Probabilidad / Modelo de color / Término regional

${\displaystyle E_{\rm {color}}}$— término unario que describe la probabilidad de cada color.

• Este término se puede modelar utilizando diferentes enfoques locales (por ejemplo, texones) o globales (por ejemplo, histogramas, GMM, probabilidad Adaboost) que se describen a continuación.

Histograma

• Utilizamos intensidades de píxeles marcados como semillas para obtener histogramas para distribuciones de intensidad de objetos (primer plano) y fondo: P(I|O) y P(I|B).
• Luego, utilizamos estos histogramas para establecer las penalizaciones regionales como verosimilitudes logarítmicas negativas.

GMM (modelo de mezcla gaussiana)

• Normalmente utilizamos dos distribuciones: una para el modelado de fondo y otra para los píxeles de primer plano.
• Utilice un modelo de mezcla gaussiana (con 5–8 componentes) para modelar esas 2 distribuciones.
• Objetivo: Intentar separar esas dos distribuciones.

Texón

• Un texón (o textón) es un conjunto de píxeles que tiene ciertas características y se repite en una imagen.
• Pasos:

1. Determinar una buena escala natural para los elementos de textura.
2. Calcular estadísticas no paramétricas de los texones del interior del modelo, ya sea en intensidad o en respuestas del filtro de Gabor.

• Ejemplos:
  • Segmentación de objetos texturizados basada en modelos deformables
  • Análisis de contornos y texturas para segmentación de imágenes

Modelo previo / Modelo de coherencia / Término límite

${\displaystyle E_{\rm {coherence}}}$— término binario que describe la coherencia entre píxeles vecinos.

• En la práctica, los píxeles se definen como vecinos si son adyacentes horizontal, vertical o diagonalmente (conectividad de 4 vías o conectividad de 8 vías para imágenes 2D).
• Los costos pueden basarse en el gradiente de intensidad local, el cruce por cero de Laplacio, la dirección del gradiente, el modelo de mezcla de colores,...
• Se han definido diferentes funciones energéticas:
  • Campo aleatorio estándar de Markov : Asocie una penalización a los píxeles en desacuerdo evaluando la diferencia entre sus etiquetas de segmentación (medida cruda de la longitud de los límites). Consulte Boykov y Kolmogorov ICCV 2003
  • Campo aleatorio condicional : si el color es muy diferente, podría ser un buen lugar para poner un límite. Véase Lafferty et al. 2001; Kumar y Hebert 2003

Crítica

Los métodos de corte de grafos se han convertido en alternativas populares a los enfoques basados ​​en conjuntos de niveles para optimizar la ubicación de un contorno (consulte ^[9] para una comparación exhaustiva). Sin embargo, los enfoques de corte de grafos han sido criticados en la literatura por varios problemas:

• Artefactos de metrificación: cuando una imagen se representa mediante una red de 4 conexiones, los métodos de corte de gráficos pueden presentar artefactos de "bloqueo" no deseados. Se han propuesto varios métodos para abordar este problema, como el uso de bordes adicionales ^[10] o la formulación del problema de flujo máximo en el espacio continuo. ^[11]
• Sesgo de contracción: dado que los cortes de gráficos encuentran un corte mínimo, el algoritmo puede estar sesgado hacia la producción de un contorno pequeño. ^[12] Por ejemplo, el algoritmo no es adecuado para la segmentación de objetos delgados como los vasos sanguíneos (consulte ^[13] para obtener una solución propuesta).
• Etiquetas múltiples: los cortes de gráficos solo pueden encontrar un óptimo global para problemas de etiquetado binario (es decir, dos etiquetas), como la segmentación de imágenes de primer plano/fondo. Se han propuesto extensiones que pueden encontrar soluciones aproximadas para problemas de cortes de gráficos con múltiples etiquetas. ^[7]
• Memoria: el uso de memoria de los cortes de gráficos aumenta rápidamente a medida que aumenta el tamaño de la imagen. Como ilustración, el algoritmo de flujo máximo de Boykov-Kolmogorov v2.2 asigna bytes ( y son respectivamente el número de nodos y aristas en el gráfico). Sin embargo, recientemente se ha realizado cierta cantidad de trabajo en esta dirección para reducir los gráficos antes del cálculo del flujo máximo. ^{[14] [15] [16]} ${\displaystyle 24n+14m}$ ${\displaystyle n}$ ${\displaystyle m}$

Algoritmo

• La minimización se realiza utilizando un algoritmo de corte mínimo estándar.
• Gracias al teorema de flujo máximo y corte mínimo, podemos resolver la minimización de energía maximizando el flujo en la red. El problema del flujo máximo consiste en un gráfico dirigido con aristas etiquetadas con capacidades y hay dos nodos distintos: la fuente y el sumidero. Intuitivamente, es fácil ver que el flujo máximo está determinado por el cuello de botella.

Implementación (exacta)

El algoritmo Boykov-Kolmogorov ^[17] es una forma eficiente de calcular el flujo máximo para gráficos relacionados con la visión por computadora.

Implementación (aproximación)

El algoritmo Sim Cut ^[18] aproxima el corte mínimo del grafo. El algoritmo implementa una solución mediante la simulación de una red eléctrica. Este es el enfoque sugerido por el teorema de flujo máximo de Cederbaum . ^{[19] [20]} La aceleración del algoritmo es posible mediante computación paralela .

Software

• http://pub.ist.ac.at/~vnk/software.html — Una implementación del algoritmo maxflow descrito en "Una comparación experimental de algoritmos Min-Cut/Max-Flow para la minimización de energía en visión artificial" de Vladimir Kolmogorov
• http://vision.csd.uwo.ca/code/ — algunas bibliotecas de corte de gráficos y envoltorios de MATLAB
• http://gridcut.com/ — solucionador rápido de flujo máximo/corte mínimo de múltiples núcleos optimizado para gráficos tipo cuadrícula
• http://virtualscalpel.com/ — Una implementación de Sim Cut ; un algoritmo para calcular una solución aproximada del corte st mínimo de manera masivamente paralela.

Referencias

1. Adelson, Edward H. y James R. Bergen (1991), "La función plenóptica y los elementos de la visión temprana", Modelos computacionales del procesamiento visual 1.2 (1991).
2. Boykov, Y., Veksler, O. y Zabih, R. (2001), "Minimización rápida de energía aproximada a través de cortes de gráficos", IEEE Transactions on Pattern Analysis and Machine Intelligence, 23(11): 1222-1239.
3. DM Greig, BT Porteous y AH Seheult (1989), Estimación exacta máxima a posteriori para imágenes binarias , Journal of the Royal Statistical Society, Serie B, 51 , 271–279.
4. D. Geman y S. Geman (1984), Relajación estocástica, distribuciones de Gibbs y restauración bayesiana de imágenes , IEEE Trans. Pattern Anal. Mach. Intell., 6 , 721–741.
5. JE Besag (1986), Sobre el análisis estadístico de imágenes sucias (con discusión) , Journal of the Royal Statistical Society Series B, 48 , 259–302
6. Y. Boykov, O. Veksler y R. Zabih (1998), "Campos aleatorios de Markov con aproximaciones eficientes", Conferencia internacional sobre visión por computadora y reconocimiento de patrones (CVPR) .
7. Y. Boykov, O. Veksler y R. Zabih (2001), "Minimización rápida de energía aproximada mediante cortes de gráficos", IEEE Transactions on Pattern Analysis and Machine Intelligence , 29 , 1222–1239.
8. 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
9. Leo Grady y Christopher Alvino (2009), "La función Mumford-Shah suave por partes en un gráfico arbitrario", IEEE Trans. on Image Processing, págs. 2547–2561
10. Yuri Boykov y Vladimir Kolmogorov (2003), "Cálculo de geodésicas y superficies mínimas mediante cortes de gráficos", Proc. de ICCV
11. Ben Appleton y Hugues Talbot (2006), "Superficies globalmente mínimas mediante flujos máximos continuos", IEEE Transactions on Pattern Analysis and Machine Intelligence, págs. 106-118
12. Ali Kemal Sinop y Leo Grady, "Un marco de segmentación de imágenes con semillas que unifica los cortes de gráficos y el caminante aleatorio que produce un nuevo algoritmo", Proc. de ICCV, 2007
13. Vladimir Kolmogorov y Yuri Boykov (2005), "¿Qué métricas se pueden aproximar mediante cortes geográficos u optimización global de longitud/área y flujo?", Proc. of ICCV, págs. 564-571
14. Nicolas Lermé, François Malgouyres y Lucas Létocart (2010), "Reducción de gráficos en la segmentación por corte de gráficos Archivado el 27 de marzo de 2012 en Wayback Machine ", Proc. de ICIP, págs. 3045–3048
15. Herve Lombaert, Yiyong Sun, Leo Grady, Chenyang Xu (2005), "Un método de corte de gráficos en bandas de múltiples niveles para la segmentación rápida de imágenes", Proc. of ICCV, págs. 259-265
16. Yin Li, Jian Sun, Chi-Keung Tang y Heung-Yeung Shum (2004), "Ajuste perezoso", ACM Transactions on Graphics, págs. 303-308
17. Yuri Boykov, Vladimir Kolmogorov: Una comparación experimental de algoritmos de flujo máximo/corte mínimo para la minimización de energía en la visión. IEEE Trans. Pattern Anal. Mach. Intell. 26(9): 1124–1137 (2004)
18. PJ Yim: "Método y sistema para la segmentación de imágenes", patente de Estados Unidos US8929636, 6 de enero de 2016
19. Cederbaum, I. (1962-08-01). "Sobre el funcionamiento óptimo de las redes de comunicación". Revista del Instituto Franklin . 274 (2): 130–141. doi :10.1016/0016-0032(62)90401-5. ISSN  0016-0032.
20. IT Frisch, "Sobre análogos eléctricos para redes de flujo", Actas del IEEE, 57:2, págs. 209-210, 1969