Recortes de gráficos en visión por computadora

Tal como se aplica en el campo de la visión por computadora , la optimización del corte de gráficos 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 el suavizado de imágenes , el problema de correspondencia estéreo , la segmentación de imágenes y la segmentación de objetos. co-segmentación y muchos otros problemas de visión por computadora que pueden formularse 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 gráfico ^[2] (y así, mediante el teorema de corte mínimo de flujo máximo , definir un corte mínimo del gráfico). En la mayoría de las formulaciones de este tipo de 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 gráfico (por ejemplo, cortes normalizados), el término "cortes de gráfico" se aplica específicamente a aquellos modelos que emplean una optimización de flujo máximo/corte mínimo (otros algoritmos de corte de gráficos pueden considerarse como particiones de gráficos). algoritmos).

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

Historia

La teoría de los cortes de gráficos utilizada como método de optimización se aplicó por primera vez en visión por computadora en el artículo fundamental 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 se destacó como 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), mostraron 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 utilizaron técnicas aproximadas como el recocido simulado (propuesto por los hermanos Geman ), ^[4] o modos condicionales iterados (un tipo de algoritmo codicioso sugerido por Julian Besag ) ^[5] para resolver dichos problemas de suavizado de imágenes.

Aunque el problema general del color sigue sin resolverse para el enfoque de Greig, Porteous y Seheult ^[3] han demostrado que ^{[6] [7]} tienen una amplia aplicabilidad en problemas generales de visión por computadora. Los enfoques de Greig, Porteous y Seheult a menudo se aplican de forma iterativa a una secuencia de problemas binarios, y generalmente producen soluciones cercanas a las óptimas. ${\displaystyle k}$ ${\displaystyle k>2,}$

En 2011, C. Couprie et al . ^[8] propuso un marco general de segmentación de imágenes, llamado "Power Watershed", que minimizó una función de indicador de valor real de [0,1] sobre un gráfico, restringido por semillas de usuario (o términos unarios) establecidos en 0 o 1. en el que la minimización de la función del indicador sobre el gráfico se optimiza con respecto a un exponente . Cuando , Power Watershed se optimiza mediante cortes de gráficos, 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 . De esta manera, Power Watershed puede verse como una generalización de cortes de gráficos que proporciona una conexión directa con otros algoritmos de segmentación/agrupación 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 una 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-medias.
2. El segundo paso realiza el algoritmo habitual de corte 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

• Usamos intensidades de píxeles marcados como semillas para obtener histogramas para las distribuciones de intensidad del objeto (primer plano) y del fondo: P(I|O) y P(I|B).
• Luego, utilizamos estos histogramas para establecer las penalizaciones regionales como probabilidades 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 a 8 componentes) para modelar esas 2 distribuciones.
• Objetivo: intentar separar esas dos distribuciones.

texón

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

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

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

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 u conectividad de 8 vías para imágenes 2D).
• Los costos pueden basarse en el gradiente de intensidad local, el cruce por cero laplaciano, la dirección del gradiente, el modelo de mezcla de colores,...
• Se han definido diferentes funciones energéticas:
  • Campo aleatorio estándar de Markov : asocia una penalización a los píxeles que no están de acuerdo evaluando la diferencia entre sus etiquetas de segmentación (medida aproximada de la longitud de los límites). Véase 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 gráficos se han convertido en alternativas populares a los enfoques basados ​​en conjuntos de niveles para optimizar la ubicación de un contorno (ver ^[9] para una comparación extensa). Sin embargo, los enfoques de corte de gráficos han sido criticados en la literatura por varias cuestiones:

• Artefactos de métrica: cuando una imagen está representada por una red de 4 conexiones, los métodos de corte de gráficos pueden exhibir artefactos de "bloqueo" no deseados. Se han propuesto varios métodos para abordar este problema, como el uso de aristas adicionales ^[10] o la formulación del problema de flujo máximo en un espacio continuo. ^[11]
• Sesgo de contracción: dado que los cortes del gráfico 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 vasos sanguíneos (ver ^[13] para 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 y de fondo. Se han propuesto extensiones que pueden encontrar soluciones aproximadas para problemas de cortes de gráficos de etiquetas múltiples. ^[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. A modo de ilustración, el algoritmo de flujo máximo v2.2 de Boykov-Kolmogorov asigna bytes ( y son, respectivamente, el número de nodos y aristas en el gráfico). Sin embargo, recientemente se ha trabajado algo 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 mediante un algoritmo de corte mínimo estándar.
• Debido al teorema de corte mínimo de flujo máximo, podemos resolver la minimización de energía maximizando el flujo a través de la red. El problema de flujo máximo consta de un gráfico dirigido con bordes etiquetados 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 eficaz 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] se aproxima al corte mínimo del gráfico. El algoritmo implementa una solución mediante 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: implementación del algoritmo maxflow descrito en "An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Computer Vision" de Vladimir Kolmogorov.
• http://vision.csd.uwo.ca/code/: algunas bibliotecas de corte de gráficos y contenedores 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 forma 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 de procesamiento visual 1.2 (1991).
2. Boykov, Y., Veksler, O. y Zabih, R. (2001), "Minimización rápida de energía aproximada mediante 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 máxima exacta 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. Patrón Anal. Mach. Intel., 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, "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
9. Leo Grady y Christopher Alvino (2009), "El funcional Mumford-Shah suave por partes en un gráfico arbitrario", IEEE Trans. sobre procesamiento de imágenes, págs. 2547–2561
10. Yuri Boykov y Vladimir Kolmogorov (2003), "Computación de geodésicas y superficies mínimas mediante cortes de gráficos", Proc. del 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.
12. Ali Kemal Sinop y Leo Grady, "Un marco de segmentación de imágenes sembradas que unifica cortes de gráficos y caminantes aleatorios 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. de ICCV págs. 564–571
14. Nicolas Lermé, François Malgouyres y Lucas Létocart (2010), "Reducción de gráficos en segmentación de corte de gráficos Archivado el 27 de marzo de 2012 en Wayback Machine ", Proc. del ICIP, págs. 3045-3048
15. Herve Lombaert, Yiyong Sun, Leo Grady, Chenyang Xu (2005), "Un método de cortes de gráficos con bandas multinivel para una segmentación rápida de imágenes", Proc. de ICCV, págs. 259-265
16. Yin Li, Jian Sun, Chi-Keung Tang y Heung-Yeung Shum (2004), "Lazy Snapping", ACM Transactions on Graphics, págs. 303–308
17. Yuri Boykov, Vladimir Kolmogorov: una comparación experimental de algoritmos de corte mínimo/flujo máximo para la minimización de energía en la visión. Traducción IEEE. Patrón Anal. Mach. Intel. 26(9): 1124-1137 (2004)
18. PJ Yim: "Método y sistema para segmentación de imágenes", patente estadounidense US8929636, 6 de enero de 2016
19. Cederbaum, I. (1 de agosto de 1962). "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 de IEEE, 57:2, págs. 209-210, 1969