Hispanopedia Wiki
Articulo de referencia

Cortes de grafos en visión por computadora e inteligencia artificial

Tal como se aplica en el campo de la visión por computadora , la optimización de corte de grafos se puede emplear para resolver de manera eficiente una amplia variedad de proble...

Hispanopedia WikiContenido en espanolLectura gratuita

Tal como se aplica en el campo de la visión por computadora , la optimización de 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 , numerosas aplicaciones militares (por ejemplo, reconocimiento automático de objetivos ) y muchos otros problemas que se pueden formular en términos de minimización de energía (por ejemplo, ciencia climática y modelado ambiental ).

Las técnicas de corte de grafos se utilizan cada vez más en combinación con técnicas de inteligencia artificial espacial más generales (por ejemplo, para reforzar la estructura en la salida de modelos de lenguaje grandes para definir mejor los límites de los tumores y de forma similar para diversas aplicaciones de realidad aumentada , coches autónomos , robótica , Google Maps, etc.).

Muchos de estos problemas de minimización de energía pueden aproximarse resolviendo un problema de flujo máximo en un grafo [ 2 ] (y, por lo tanto, mediante el teorema de flujo máximo y corte mínimo , se define un corte mínimo del grafo). En la mayoría de las formulaciones de estos problemas en visión artificial, la solución de energía mínima corresponde a la estimación a posteriori máxima de una solución.

Aunque muchos algoritmos de visión artificial implican el corte de 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 algoritmos de partición de grafos ).

Los problemas binarios (como la eliminación de ruido en una imagen binaria ) se pueden resolver de forma exacta utilizando este método; 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 en una imagen en escala de grises ) no se pueden resolver de forma exacta, pero las soluciones obtenidas suelen estar cerca del óptimo global.

Historia

La teoría fundamental de los cortes de grafos en visión por computadora fue desarrollada por primera vez por Margaret Greig, Bruce Porteous y Allan Seheult (GPS) de la Universidad de Durham en una contribución a la discusión, ahora legendaria, del artículo de Julian Besag de 1986 [ 3 ] y un artículo posterior más detallado [ 4 ] en 1989. En el contexto estadístico bayesiano del suavizado de imágenes ruidosas, utilizando un campo aleatorio de Markov como distribución a priori de la imagen, demostraron con una prueba matemáticamente elegante cómo la estimación a posteriori máxima de una imagen binaria puede obtenerse exactamente maximizando el flujo a través de una red de imágenes asociada, o grafo, lo que implica la introducción de una fuente y un sumidero y razones de verosimilitud logarítmica . Se demostró que el problema era eficientemente resoluble exactamente, un resultado inesperado ya que se creía que el problema era computacionalmente intratable (NP-difícil).

GPS también abordó el costo computacional del algoritmo de flujo máximo en grafos grandes, una preocupación importante en ese momento. Propusieron un algoritmo de particionamiento (véase la Sección 4 de GPS) que implicaba la fusión recursiva de bloques o teselas no superpuestos, lo que proporcionó un aumento de velocidad de 12X. Este enfoque resolvía y fusionaba recursivamente subgrafos independientes hasta que se resolvía el grafo completo. Si bien contemporáneos como Geman y Geman [ 5 ] habían defendido la computación paralela en el contexto del recocido simulado , la estrategia de bloqueo de GPS ofrecía una estructura determinista susceptible de paralelización y anticipaba el diseño moderno de inteligencia artificial en múltiples GPU . Sin embargo, hasta hace poco, este aspecto del artículo fue ignorado en gran medida y la investigación posterior se centró en árboles de búsqueda global de computadoras seriales , como el algoritmo de Boykov-Kolmogorov [ 6 ] .

Aunque el generalk{\displaystyle k}-el problema del color es NP difícil parak>2,{\displaystyle k>2,}El enfoque GPS ha demostrado tener una amplia aplicabilidad en problemas generales de visión por computadora. Esto fue demostrado por primera vez por Boykov, Veksler y Zabih [ 2 ] , quienes, en un artículo fundamental publicado más de 10 años después del artículo original sobre GPS, y en otros trabajos importantes, encendieron la chispa para la adopción general de técnicas de corte de grafos en visión por computadora. Demostraron que, para problemas generales, el enfoque GPS puede aplicarse iterativamente a secuencias de problemas binarios, utilizando su ahora omnipresente algoritmo de expansión alfa, produciendo soluciones casi óptimas. Antes de estos resultados, se utilizaban técnicas de optimización local aproximadas , como el recocido simulado (como propusieron los hermanos Geman [ 5 ] ) o los modos condicionales iterados (un tipo de algoritmo voraz sugerido por Julian Besag [ 3 ] ), para resolver dichos problemas de suavizado de imágenes.

Partiendo de estos avances, la optimización de corte de grafos GPS se adaptó posteriormente para la segmentación interactiva de imágenes, sobre todo mediante el algoritmo "GrabCut" introducido por Carsten Rother, Vladimir Kolmogorov y Andrew Blake [ 7 ] de Microsoft Research, Cambridge. GrabCut amplió los métodos anteriores de corte de grafos interactivos al sustituir los histogramas de imágenes monocromáticas por modelos de mezcla gaussiana para estimar las distribuciones de color y al emplear un esquema iterativo de minimización de energía GPS. Este enfoque simplificó significativamente la interacción del usuario, requiriendo solo un cuadro delimitador aproximado alrededor del objeto objetivo en lugar de trazos detallados dibujados por el usuario, y rápidamente se convirtió en una herramienta estándar tanto en la investigación académica como en el software comercial de edición de imágenes.

El artículo sobre GPS conectó y unió ideas profundas de la estadística matemática ( teorema de Bayes , campo aleatorio de Markov [ 8 ] [ 9 ] ), la física ( modelo de Ising ), la optimización ( función de energía ) y la informática ( problema de flujo de red ), y lideró el cambio de los enfoques de optimización locales aproximados y lentos (por ejemplo, el recocido simulado) a técnicas de optimización global más potentes, exactas o casi exactas. Ahora se reconoce como fundamental, ya que se adelantó a su tiempo y, en particular, se publicó años antes de la revolución de la capacidad de cálculo de la ley de Moore y las GPU .

Es significativo que GPS se publicara en una revista de estadística matemática (en lugar de una de visión por computadora), lo que provocó que la comunidad de visión por computadora lo pasara por alto durante muchos años. Se le conoce extraoficialmente como el artículo de " The Velvet Underground " de la visión por computadora (es decir, aunque muy pocos expertos en visión por computadora leyeron el artículo [compraron el disco], quienes lo hicieron, sobre todo Boykov, Veksler y Zabih, [ 2 ] iniciaron una investigación nueva e importante [formaron un grupo]). Esto se confirma por la altísima tasa de amplificación de GPS (citas de segundo orden/citas de primer orden), estimada en más de 100.

A pesar de la naturaleza fundamental del trabajo de GPS, el reconocimiento formal de la comunidad de visión por computadora se ha otorgado principalmente a los investigadores que posteriormente extendieron y popularizaron el método de corte de grafos. Por ejemplo, Boykov, Veksler y Zabih [ 2 ] recibieron merecidamente el Premio Helmholtz del ICCV en 2011. [ 10 ] Este premio reconoce los artículos del ICCV de 10 años o más de antigüedad que han tenido un impacto significativo en la investigación de la visión por computadora.

En 2011, Couprie et al . [ 11 ] propusieron un marco general de segmentación de imágenes, llamado "Power Watershed", que minimizaba una función indicadora de valor real de [0,1] sobre un grafo, restringida 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 grafo se optimiza con respecto a un exponente.pag{\displaystyle p}. Cuandopag=1{\displaystyle p=1}, el Power Watershed se optimiza mediante cortes de grafos, cuandopag=0{\displaystyle p=0}La cuenca hidrográfica Power Watershed se optimiza mediante las rutas más cortas,pag=2{\displaystyle p=2}se optimiza mediante el algoritmo de caminante aleatorio ypag=∞{\displaystyle p=\infty }Se optimiza mediante el algoritmo de cuencas hidrográficas . De esta forma, el algoritmo Power Watershed puede considerarse una generalización de los cortes de grafos que proporciona una conexión directa con otros algoritmos de segmentación/agrupación para la optimización energética.

Segmentación binaria de imágenes

Notación

  • Imagen:incógnita∈{R,GRAMO,B}norte{\displaystyle x\in \{R,G,B\}^{N}}
  • Salida: Segmentación (también llamada opacidad)S∈Rnorte{\displaystyle S\in R^{N}}(segmentación suave). Para segmentación duraS∈{0 para obtener información de fondo,1 para que se detecte el primer plano/objeto}norte{\displaystyle S\in \{0{\text{ for background}},1{\text{ for foreground/object to be detected}}\}^{N}}
  • Función energética :mi(incógnita,S,do,λ){\displaystyle E(x,S,C,\lambda )}donde C es el parámetro de color y λ es el parámetro de coherencia.
  • mi(incógnita,S,do,λ)=midoolor+midoohmirminortedomi{\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:arg⁡minSmi(incógnita,S,do,λ){\displaystyle {\arg \min }_{S}E(x,S,C,\lambda )}

Métodos existentes

  • Cortes de grafos estándar: optimizar la función de energía sobre la segmentación (valor S desconocido).
  • Cortes de grafos iterados:
  1. El primer paso optimiza los parámetros de color utilizando el algoritmo K-means.
  2. El segundo paso ejecuta el algoritmo habitual de cortes de grafos.
Estos 2 pasos se repiten recursivamente hasta la convergencia.
  • Recortes dinámicos de grafos: 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 añadido nuevas semillas).

Función de energía

Pr(incógnita∣S)=K−mi{\displaystyle \Pr(x\mid S)=K^{-E}}

donde la energíami{\displaystyle E}está compuesto por dos modelos diferentes (midoolor{\displaystyle E_{\rm {color}}}ymidoohmirminortedomi{\displaystyle E_{\rm {coherence}}}):

Probabilidad / Modelo de color / Término regional

midoolor{\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, verosimilitud de Adaboost) que se describen a continuación.
Histograma
  • Utilizamos las intensidades de los píxeles marcados como semillas para obtener histogramas de 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 logaritmos de verosimilitud negativos.
GMM (modelo de mezcla gaussiana)
  • Normalmente utilizamos dos distribuciones: una para el modelado del fondo y otra para los píxeles del primer plano.
  • Utilice un modelo de mezcla gaussiana (con 5 a 8 componentes) para modelar esas 2 distribuciones.
  • Objetivo: Intentar separar esas dos distribuciones.
Texon
  • Un texón (o textón ) es un conjunto de píxeles que posee ciertas características y se repite en una imagen.
  • Pasos:
  1. Determina una escala natural adecuada para los elementos de textura.
  2. Calcular estadísticas no paramétricas de los texones del interior del modelo , ya sea en función de la intensidad o de 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

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

midoohmirminortedomi{\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 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, etc.
  • Se han definido diferentes funciones de energía:
    • Campo aleatorio de Markov estándar : Asocia una penalización a los píxeles que no coinciden, evaluando la diferencia entre su etiqueta 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 colocar 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 nivel para optimizar la ubicación de un contorno (véase [ 12 ] para una comparación exhaustiva). Sin embargo, los enfoques de corte de grafos han sido criticados en la literatura por varios problemas:

  • Artefactos de métrica: Cuando una imagen se representa mediante una red 4-conectada, los métodos de corte de grafos pueden presentar artefactos de "bloqueo" no deseados. Se han propuesto varios métodos para abordar este problema, como el uso de aristas adicionales [ 13 ] o la formulación del problema de flujo máximo en un espacio continuo [ 14 ] .
  • Sesgo de reducción: Dado que los cortes de grafos encuentran un corte mínimo, el algoritmo puede estar sesgado hacia la producción de un contorno pequeño. [ 15 ] Por ejemplo, el algoritmo no es adecuado para la segmentación de objetos delgados como los vasos sanguíneos (véase [ 16 ] para una solución propuesta).
  • Etiquetas múltiples: El método de cortes de grafos solo permite 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 permiten encontrar soluciones aproximadas para problemas de cortes de grafos con múltiples etiquetas. [ 2 ]
  • Memoria: el uso de memoria de los cortes de grafos 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 asigna24norte+14metro{\displaystyle 24n+14m}bytes (norte{\displaystyle n}ymetro{\displaystyle m}son respectivamente el número de nodos y aristas en el grafo). Sin embargo, recientemente se ha realizado cierto trabajo en esta dirección para reducir los grafos antes del cálculo del flujo máximo. [ 17 ] [ 18 ] [ 19 ]

Limitaciones históricas

Si bien los cortes de grafos proporcionan soluciones matemáticamente óptimas para funciones de energía específicas, su uso como método independiente para el reconocimiento general de objetos disminuyó con la llegada del aprendizaje profundo. Las principales limitaciones incluyen:

  • Brecha semántica: Los cortes de grafos se basan en señales de bajo nivel (intensidad de píxeles, color, textura) y carecen de comprensión semántica de alto nivel. No pueden distinguir entre objetos semánticamente diferentes que comparten características visuales similares (por ejemplo, distinguir un perro de un gato del mismo color).
  • Costo computacional: La naturaleza iterativa de los algoritmos de flujo máximo (típicamenteO(V2mi){\displaystyle O(V^{2}E)}oO(V3){\displaystyle O(V^{3})}) hace que sean computacionalmente costosos para vídeo de alta resolución en comparación con la inferencia de alimentación directa de las redes neuronales.
  • Paralelización: A diferencia de las multiplicaciones de matrices en las redes neuronales, los algoritmos de corte de grafos son difíciles de paralelizar de manera eficiente en las GPU modernas , lo que crea un cuello de botella en las canalizaciones en tiempo real.

Sin embargo, siguen siendo una herramienta estándar para la segmentación interactiva (por ejemplo, la rotoscopia en efectos visuales), donde el usuario proporciona la intención semántica (mediante trazos) y el algoritmo se encarga de la precisión de los límites. Como se describe a continuación, se están integrando cada vez más en la inteligencia artificial moderna.

Aplicaciones modernas

En la era del aprendizaje profundo, los cortes de grafos han pasado de ser solucionadores de segmentación independientes a componentes integrados en arquitecturas neuronales complejas. Si bien las primeras aplicaciones se centraron en el etiquetado discreto de imágenes 2D, los casos de uso modernos aprovechan la capacidad del algoritmo para proporcionar una estructura espacial y temporal matemáticamente rigurosa a las salidas "flexibles" de las redes neuronales.

Integración con aprendizaje profundo

El principal desafío en la integración de la IA moderna radica en que la naturaleza discreta del algoritmo de corte mínimo/flujo máximo no es naturalmente diferenciable.

  • Capas diferenciables: Los marcos de trabajo recientes han introducido relajaciones "suaves" o continuas de la energía de corte del grafo. Esto permite utilizar el algoritmo como una capa estructurada dentro de una red neuronal convolucional (CNN) o un transformador. La red aprende a generar pesos de aristas y potenciales de nodos óptimos, que la capa de corte del grafo optimiza posteriormente para producir resultados espacialmente consistentes.
  • Funciones de pérdida híbridas: Las metodologías modernas utilizan la energía de corte de grafos como función de pérdida durante el entrenamiento. Esto obliga al modelo a aprender segmentaciones que se alinean con los límites de alto contraste en la entrada original, enseñando así a la IA a respetar los bordes "físicos" sin necesidad de grandes cantidades de datos de entrenamiento con precisión de píxel.

Modelos básicos y segmentación proactiva

Con la llegada de los modelos de base a gran escala, como el Modelo de Segmentación de Cualquier Objeto (SAM), los cortes de grafos han adquirido una nueva función en los "cabezales de refinamiento". Si bien estos modelos son excelentes para identificar objetos generales, pueden generar límites "difusos" o no manifold. Los cortes de grafos se aplican como un paso de posprocesamiento para "ajustar" los límites de la máscara a los bordes de alto contraste. En regímenes de datos reducidos, los cortes de grafos propagan etiquetas desde unos pocos "puntos guía" proporcionados por el usuario a través de las incrustaciones de características de alta dimensión generadas por el transformador.

Imágenes médicas y reconstrucción 3D

Los análisis de cortes de grafos siguen siendo un método de referencia en el diagnóstico médico, donde los datos suelen ser ruidosos o escasos.

  • Segmentación volumétrica: En el análisis de resonancia magnética y tomografía computarizada, los cortes de grafos garantizan la "consistencia topológica" en 3D. Si bien una red neuronal podría identificar erróneamente píxeles individuales, el corte de grafos asegura que las estructuras anatómicas, como vasos sanguíneos o tumores, se representen como volúmenes continuos y conectados.
  • Segmentación interactiva: Las plataformas médicas modernas (por ejemplo, MONAI) utilizan cortes de grafos para habilitar la IA con intervención humana. Un radiólogo proporciona algunos "clics de guía" (semillas), y el corte de grafos combina estas restricciones manuales con mapas de características de aprendizaje profundo para calcular un límite óptimo global en tiempo real.

Defensa y teledetección

En defensa e inteligencia, se aplican recortes de grafos a datos de sensores de alta resolución donde se debe minimizar la aparición de falsos positivos.

  • Análisis mediante radar de apertura sintética (SAR) y satélite: Las imágenes de radar de apertura sintética (SAR) suelen verse afectadas por el ruido de moteado. Se utilizan cortes de grafos para reducir el ruido y segmentar estas imágenes, lo que permite detectar vehículos camuflados o cambios en el terreno.
  • Seguimiento espacio-temporal: Para la vigilancia autónoma, los cortes de grafos se extienden a la dimensión temporal. Al vincular píxeles a través de diferentes intervalos de tiempo, el sistema impone una "restricción de fisicalidad", lo que garantiza que los objetivos rastreados mantengan un volumen 3D consistente y no se "desplacen" ni se fragmenten entre fotogramas de vídeo.

Modelización climática y ciencias ambientales

La ciencia climática moderna utiliza la optimización basada en grafos para salvar la brecha entre los datos discretos de las estaciones meteorológicas y los modelos atmosféricos continuos.

  • Conjuntos multimodelos: Al combinar diferentes modelos climáticos globales (MCG), los cortes de grafos seleccionan el modelo más preciso para regiones geográficas específicas. Esto garantiza que las transiciones entre modelos regionales sean espacialmente suaves y físicamente consistentes, evitando discontinuidades o artefactos en los mapas globales de precipitación y temperatura.
  • Monitoreo de la cobertura terrestre: Al tratar los datos de series temporales satelitales como un gráfico 3D, los investigadores utilizan cortes de gráficos para diferenciar entre el cambio permanente de la cobertura terrestre (deforestación, urbanización) y las variaciones estacionales temporales.

Robótica y planificación de trayectorias

En robótica, los cortes de grafos se utilizan para el mapeo semántico . Un robot que se desplaza por un entorno debe dividir su nube de puntos 3D en espacio navegable, obstáculos y regiones "desconocidas". Los cortes de grafos proporcionan una forma robusta de combinar datos LIDAR ruidosos con etiquetas semánticas visuales, asegurando que el mapa resultante esté segmentado en zonas lógicas y no superpuestas que un algoritmo de planificación de rutas pueda recorrer.

Inteligencia artificial que preserva la privacidad y síntesis de datos

Los cortes de grafos se utilizan cada vez más en el campo del aprendizaje automático que preserva la privacidad . Al generar conjuntos de datos sintéticos o "anonimizar" imágenes, los cortes de grafos pueden utilizarse para identificar y extraer regiones sensibles (como rostros o matrículas) basándose en la minimización de energía. Esto garantiza que los límites de los datos eliminados sean lo suficientemente precisos como para que no quede información privada "residual" en los bordes del corte, lo cual es un punto débil común en las técnicas de desenfoque puramente generativas (basadas en GAN).

Dinámica de fluidos computacional (CFD)

En la industria aeroespacial y la predicción meteorológica, los cortes de grafos facilitan la partición dinámica de mallas . Para optimizar los recursos de supercomputación, los cortes de grafos identifican regiones de alta complejidad —como el ojo de un huracán o el borde de una pala de turbina— y distribuyen la carga computacional en consecuencia. Esto garantiza que la zona donde se produce la física más compleja reciba la mayor densidad de potencia de procesamiento.

Algoritmo

  • La minimización se realiza utilizando un algoritmo estándar de corte mínimo.
  • Gracias al teorema del flujo máximo y el corte mínimo, podemos minimizar la energía maximizando el flujo en la red. El problema del flujo máximo consiste en un grafo dirigido con aristas etiquetadas con capacidades, y existen 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 [ 6 ] es una forma eficiente de calcular el flujo máximo para grafos relacionados con la visión por computadora.

Implementación (aproximación)

El algoritmo Sim Cut [ 20 ] 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 del flujo máximo de Cederbaum . [ 21 ] [ 22 ] 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 grafos y adaptadores para MATLAB
  • http://gridcut.com/ — Solucionador rápido de flujo máximo/corte mínimo multinúcleo optimizado para gráficos tipo cuadrícula

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. 1 2 3 4 5 Boykov, Y., Veksler, O., y Zabih, R. (2001), " Minimización rápida aproximada de energía mediante cortes de grafos ", IEEE Transactions on Pattern Analysis and Machine Intelligence, 23(11): 1222-1239.
  3. 1 2 J.E. 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
  4. ↑ DM Greig, BT Porteous y AH Seheult (1989), Estimación exacta de máxima probabilidad a posteriori para imágenes binarias , Journal of the Royal Statistical Society, Serie B, 51 , 271–279.
  5. 1 2 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.
  6. 1 2 Yuri Boykov, Vladimir Kolmogorov: Una comparación experimental de algoritmos Min-Cut/Max-Flow para la minimización de energía en visión . IEEE Trans. Pattern Anal. Mach. Intell. 26(9): 1124–1137 (2004)
  7. ↑ Rother, Carsten; Kolmogorov, Vladimir; Blake, Andrew (agosto de 2004)."GrabCut": extracción interactiva de primer plano mediante cortes de grafos iterados". ACM Transactions on Graphics . 23 (3): 309– 314. doi : 10.1145/1015706.1015720 .
  8. ↑ Besag, Julian (1974-01-01). "Interacción espacial y análisis estadístico de sistemas reticulares" . Journal of the Royal Statistical Society Series B: Statistical Methodology . 36 (2): 192– 225.
  9. ↑ Hammersley, JM; Clifford, P. (1971). Campos de Markov en grafos y retículos finitos (PDF) (Manuscrito inédito). Cambridge, Reino Unido: Universidad de Cambridge.
  10. ↑ "Premios de Visión por Computadora – The Computer Vision Foundation" . www.thecvf.com . Archivado del original el 12 de enero de 2026. Consultado el 27 de enero de 2026 .
  11. ↑ 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, n.º 7, págs. 1384-1399, julio de 2011
  12. ↑ Leo Grady y Christopher Alvino (2009), " El funcional de Mumford-Shah suave por partes en un grafo arbitrario ", IEEE Trans. on Image Processing, págs. 2547–2561
  13. ↑ Yuri Boykov y Vladimir Kolmogorov (2003), " Cálculo de geodésicas y superficies mínimas mediante cortes de grafos ", Actas de ICCV
  14. ↑ 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
  15. ↑ Ali Kemal Sinop y Leo Grady, " Un marco de segmentación de imágenes con semillas que unifica cortes de grafos y caminante aleatorio que da como resultado un nuevo algoritmo ", Actas de ICCV, 2007
  16. ↑ 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 ", Actas de ICCV, págs. 564–571
  17. ↑ Nicolas Lermé, François Malgouyres y Lucas Létocart (2010), " Reducción de grafos en la segmentación por corte de grafos. Archivado el 27 de marzo de 2012 en Wayback Machine ", Actas de ICIP, págs. 3045–3048
  18. ↑ Herve Lombaert, Yiyong Sun, Leo Grady, Chenyang Xu (2005), " Un método de cortes de grafos de bandas multinivel para la segmentación rápida de imágenes ", Actas de ICCV, págs. 259–265
  19. ↑ Yin Li, Jian Sun, Chi-Keung Tang y Heung-Yeung Shum (2004), " Lazy Snapping ", ACM Transactions on Graphics, págs. 303–308
  20. ↑ PJ Yim: " Método y sistema para la segmentación de imágenes ", Patente de Estados Unidos US8929636, 6 de enero de 2016
  21. ↑ Cederbaum, I. (1962-08-01). "Sobre el funcionamiento óptimo de las redes de comunicación". Journal of the Franklin Institute . 274 (2): 130– 141. doi : 10.1016/0016-0032(62)90401-5 . ISSN 0016-0032 . 
  22. ↑ IT Frisch, "Sobre análogos eléctricos para redes de flujo", Actas del IEEE, 57:2, págs. 209-210, 1969