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 , el objeto co-segmentación 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 gráfico [2] (y por lo tanto, mediante lateorema de flujo máximo y corte mínimo, defina un corte mínimo del gráfico). En la mayoría de las formulaciones de tales problemas en la 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 eliminar el ruido de una imagen binaria) se pueden resolver exactamente utilizando este enfoque; Los problemas en los que los píxeles pueden etiquetarse 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 con exactitud, pero las soluciones que se obtienen 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 seminal de Greig, Porteous y Seheult [3] de la Universidad de Durham . Allan Seheult y Bruce Porteous fueron miembros del elogiado grupo de estadísticas de Durham en ese momento, dirigido por Julian Besag y Peter Green (estadístico) , 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 tanto, se demostró que el problema se podía resolver de forma eficaz. Antes de este resultado, se utilizaron técnicas aproximadas como el recocido simulado (propuesto por los hermanos Geman [4] ) o los modos condicionales iterados (un tipo de algoritmo codicioso sugerido por Julian Besag ) [5] para resolver estos problemas de suavizado de imágenes. .
Aunque el general -el problema del color sigue sin resolverseel enfoque de Greig, Porteous y Seheult [3] ha resultado [6] [7] tener 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, lo que generalmente produce soluciones casi óptimas.
En 2011, C. Couprie et al. [8] propuso un marco general de segmentación de imágenes, llamado "Power Watershed", que minimizaba una función de indicador de valor real de [0,1] en 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. Cuándo, Power Watershed se optimiza mediante cortes de gráficos, cuando la Power Watershed está optimizada por caminos más cortos, está optimizado por el algoritmo Random Walker yestá optimizado por el algoritmo Watershed (procesamiento de imágenes) . 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 / agrupamiento de optimización de energía.
Segmentación binaria de imágenes
Notación
- Imagen:
- Salida: segmentación (también llamada opacidad) (segmentación suave). Para segmentación dura
- Función energética : donde C es el parámetro de color y λ es el parámetro de coherencia.
- Optimización: la segmentación se puede estimar como un mínimo global sobre S:
Métodos existentes
- Cortes de gráfico estándar: optimizan la función de energía sobre la segmentación (valor S desconocido).
- Cortes de gráficos iterados:
- El primer paso optimiza los parámetros de color utilizando K-means.
- El segundo paso realiza el algoritmo habitual de cortes de gráficos.
- Estos 2 pasos se repiten de forma recursiva 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 de energía
donde la energia se compone de dos modelos diferentes ( y ):
Probabilidad / modelo de color / término regional
- término unitario que describe la probabilidad de cada color.
- Este término se puede modelar utilizando diferentes enfoques locales (por ejemplo, texons) o globales (por ejemplo, histogramas, GMM, probabilidad de Adaboost) que se describen a continuación.
Histograma
- Usamos intensidades de píxeles marcados como semillas para obtener histogramas para distribuciones de intensidad de objeto (primer plano) y fondo: P (I | O) y P (I | B).
- Luego, usamos estos histogramas para establecer las penalizaciones regionales como verosimilitudes logarítmicas negativas.
GMM (modelo de mezcla gaussiana)
- Por lo general, usamos 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: tratar de separar esas dos distribuciones.
Texon
- Un texon (o texton) es un conjunto de píxeles que tiene ciertas características y se repite en una imagen.
- Pasos:
- Determine una buena escala natural para los elementos de textura.
- Calcule estadísticas no paramétricas de los texones del interior del modelo, ya sea sobre la intensidad o sobre las respuestas del filtro de Gabor.
- Ejemplos:
- Segmentación de objetos texturizados basada en modelos deformables
- Análisis de contornos y texturas para la segmentación de imágenes
Previo / Modelo de coherencia / Término límite
- 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, ya sea horizontal, vertical o diagonalmente (conectividad de 4 vías o conectividad de 8 vías para imágenes 2D).
- Los costos se pueden basar en el gradiente de intensidad local, el cruce por cero de Laplacia, 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 su etiqueta de segmentación (medida bruta 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. Ver Lafferty et al. 2001; Kumar y Hebert 2003
Crítica
Los métodos de cortes 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 medición: cuando una imagen está representada por un enrejado de 4 conexiones, los métodos de corte de gráficos pueden exhibir artefactos de "bloqueos" 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 un espacio continuo. [11]
- Sesgo de contracción: dado que los cortes de 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).
- Múltiples etiquetas: 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 la imagen de primer plano / 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. 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 bordes en el gráfico). Sin embargo, recientemente se ha trabajado en esta dirección para reducir los gráficos antes del cálculo del flujo máximo. [14] [15] [16]
Algoritmo
- La minimización se realiza mediante un algoritmo estándar de corte mínimo.
- Debido al teorema de corte mínimo de flujo máximo, podemos resolver la minimización de energía maximizando el flujo en la red. El problema de Max Flow consiste en 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 de 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] se aproxima al corte del gráfico. 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 a través de la computación en paralelo.
Software
- http://pub.ist.ac.at/~vnk/software.html - Una implementación del algoritmo maxflow descrito en "Una comparación experimental de los algoritmos Min-Cut / Max-Flow para la minimización de energía en la visión por computadora" por 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 múltiples núcleos de flujo máximo / corte mínimo optimizado para gráficos en forma de 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 una manera masivamente paralela.
Referencias
- ^ 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).
- ^ Boykov, Y., Veksler, O. y Zabih, R. (2001), " minimización de energía aproximada mediante cortes de gráficos ", transacciones IEEE sobre análisis de patrones e inteligencia de máquinas, 23 (11): 1222-1239.
- ^ a b D.M. Greig, BT Porteous y AH Seheult (1989), Estimación máxima exacta a posteriori para imágenes binarias , Revista de la Royal Statistical Society, Serie B, 51 , 271-279.
- ^ 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. Intell., 6 , 721–741.
- ^ JE Besag (1986), sobre el análisis estadístico de imágenes sucias (con discusión) , Revista de la Royal Statistical Society Series B, 48 , 259-302
- ^ 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) .
- ^ a b Y. Boykov, O. Veksler y R. Zabih (2001), " Minimización de energía aproximada rápida mediante cortes de gráficos ", Transacciones IEEE sobre análisis de patrones e inteligencia de máquina , 29 , 1222-1239.
- ^ 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
- ^ Leo Grady y Christopher Alvino (2009), " El funcional de Mumford-Shah suave a trozos en un gráfico arbitrario ", IEEE Trans. sobre procesamiento de imágenes, págs. 2547-2561
- ^ Yuri Boykov y Vladimir Kolmogorov (2003), " Computación geodésica y superficies mínimas a través de recortes de gráficos ", Proc. de ICCV
- ^ Ben Appleton y Hugues Talbot (2006), " Superficies globalmente mínimas por flujos máximos continuos ", Transacciones IEEE sobre análisis de patrones e inteligencia de máquinas, págs. 106-118
- ^ Ali Kemal Sinop y Leo Grady, " Un marco de segmentación de imágenes sembradas que unifica los cortes de gráficos y un caminante aleatorio que produce un nuevo algoritmo ", Proc. de ICCV, 2007
- ^ Vladimir Kolmogorov y Yuri Boykov (2005), " Qué métricas pueden ser aproximadas por geo-cortes u optimización global de longitud / área y flujo ", Proc. de ICCV págs. 564–571
- ^ Nicolas Lermé, François Malgouyres y Lucas Létocart (2010), " Reducción de gráficos en la segmentación de corte de gráfico Archivado el 27 de marzo de 2012en la Wayback Machine ", Proc. of ICIP, págs. 3045–3048
- ^ Herve Lombaert, Yiyong Sun, Leo Grady, Chenyang Xu (2005), " Un método de cortes de gráfico multinivel para una rápida segmentación de imágenes ", Proc. de ICCV, págs. 259–265
- ^ Yin Li, Jian Sun, Chi-Keung Tang y Heung-Yeung Shum (2004), " Lazy Snapping ", ACM Transactions on Graphics, págs. 303-308
- ^ Yuri Boykov, Vladimir Kolmogorov: una comparación experimental de algoritmos de corte mínimo / flujo máximo para minimizar la energía en la visión . IEEE Trans. Patrón Anal. Mach. Intell. 26 (9): 1124–1137 (2004)
- ^ PJ Yim: " Método y sistema para la segmentación de imágenes ", patente de Estados Unidos US8929636, 6 de enero de 2016
- ↑ 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 .
- ^ IT Frisch, "Sobre análogos eléctricos para redes de flujo", Actas de IEEE, 57: 2, págs. 209-210, 1969