Talls de grafs en la visió per computador

El tall de grafs és un mètode de segmentació d'imatges basat en regions que pot ser utilitzat per resoldre de manera eficient una àmplia varietat de problemes de baix nivell en la visió per computador (visió artificial) com suavitzar imatges, el problema de correspondència estereoscòpica, i molts altres que poden ser formulats en termes de minimització de l'energia.

Es basa en la teoria de grafs on el problema de minimització d'energia es pot reduir en termes del problema del flux màxim d'un graf i, per tant, gràcies al teorema de flux màxim tall mínim es defineix un tall mínim del graf de forma que la mida del tall no és més gran en cap altre tall. En la majoria de les formulacions d'aquest tipus de problemes en la visió per computador, la solució de mínima energia correspon a l'estimació del màxim a posteriori d'una solució.

Encara que molts algorismes de visió per computador impliquen tallar un gràfic (per exemple, talls normalitzats), el terme "talls de grafs" s'aplica específicament als models que empren optimització màxim flux/tall mínim (altres algoritmes de tall de grafs poden ser considerats com algorismes de partició gràfica).

Història

La teoria dels talls de grafs es va aplicar per primera vegada en la visió per computador en el treball de Greig, Porteous i Seheult de la Universitat de Durham. En el context de l'estadística bayesiana de suavitzar imatges sorolloses (o danyades), ells van mostrar com l'estimació del màxim a posteriori d'una imatge binària es pot obtenir exactament al maximitzar el flux a través d'una xarxa d'imatges associades, que suposen la incorporació d'una font i un pou. El problema es mostra per tant, per ser una solució eficaç.

Abans d'aquest resultat, tècniques aproximades, com ara l'algorisme del recuit simulat (proposat pels germans Geman), o els modes de reiteració condicional (com el que suggereix Julian Besag [3]) van ser utilitzats per resoldre problemes de suavitzar imatges.

Encara que el problema general amb k colors segueix sense resoldre per k> 2, l'aproximació de Greig, Porteous i Seheult s'ha presentat per tenir una àmplia aplicació en els problemes generals de visió per computador.

Les aproximacions de Greig, Porteous i Seheult sovint s'apliquen de manera iterativa per a una seqüència de problemes binaris, en general donant solucions gairebé òptimes.

Conceptes

• Segmentació d'imatges: Divisió d'una imatge en regions connexes i disjuntes relacionades amb els objectes de l'escena i que compleixin un cert criteri d'homogeneïtat

• Classificació de regions: Identificar cada una de les regions d'una partició com a part d'una classe o categoria (segmentació amb regions no necessàriament connexes)

• Etiquetat de regions: Assignar una etiqueta (un color) diferent a cada component connexa.

• Connectivitat entre píxels: Dos píxels d'un conjunt estan connectats si existeix un camí que uneix els dos píxels, de tal manera que tots els píxels del camí estiguin en el mateix conjunt
  • Connectivitat 4 (la utilitzada en segmentació): Cada píxel té 4 veïns, en vertical i horitzontal
  • Connectivitat 8: Cada píxel té 8 veïns, en vertical, horitzontal i diagonal

Procediment

Exemples de talls en una xarxa de flux

La imatge es modela com una xarxa de flux on un píxel o un grup de píxels s'associen amb els nodes i els pesos dels arcs defineixen la similitud entre els píxels veïns. Aquesta xarxa de flux té dos vèrtex diferenciats S (Font) i T (Pou), que es corresponen amb les dos llavors de la inicialització, i les capacitats a cada arc.

Un flux és una funció que a cada arc li assigna un valor entre 0 i la seva capacitat, representant la llei de conservació (per cada vèrtex, excepte la Font i el Pou, el flux que entra és igual que el que surt). El valor d'un flux és el que entra en el Pou i el que es busca és un flux de valor màxim

• Un tall en la xarxa és una partició dels vèrtexs en dos subconjunts disjunts, C_1 i C_2 de tal manera que S ∈ C_1 i T ∈ C_2
• Els arcs del tall són els que van de C_1 a C_2
• El valor del tall és la suma de les capacitats dels seus arcs. Busquem un tall de valor mínim
  • El flux de la xarxa a través del tall és la suma de totes les capacitats del voltant des de S a T menys la suma de totes les capacitats del voltant al des de T a S
  • La capacitat del tall és la suma de totes les capacitats del voltant des de S a T
  • Un tall mínim és un tall on la seva capacitat és el mínim en tots els talls del graf.

Els problemes binaris (com l'eliminació de soroll d'una imatge binària) es poden resoldre exactament amb aquest enfocament, els problemes en què els píxels es poden etiquetar amb més de dues etiquetes diferents (per exemple, la correspondència estèreoscopica o l'eliminació de soroll d'una imatge en escala de grisos) no es poden resoldre amb exactitud, però les solucions produïdes són en general a prop de l'òptim global.

Algorismes per resoldre el problema de flux màxim

• Algorisme Ford-Fulkerson: Proposa buscar camins en els que es pugui augmentar el flux, fins que s'arribi el flux màxim.
• Algorisme Edmonds-Karp: Idèntic al de Ford–Fulkerson a excepció que definim l'ordre de cerca per trobar els camins no saturats. El camí trobat ha de ser el més curt entre els que encara tenen capacitat disponible.
• Algorisme Push-Relabel: S'ajusta l'alçada dels nodes perquè el flux passi a través de la xarxa com l'aigua a través d'un paisatge. El flux a través de la xarxa no és necessàriament un flux legal a través de l'execució de l'algorisme

Mètodes existents

• Talls de grafs estàndards: Optimitzen la funció d'energia sobre la segmentació.
• Talls de grafs iterants:

1. Primer s'optimitzen els paràmetres de color utilitzant K-means

2. Després es porta a terme l'algorisme habitual de talls gràfics.

Aquests dos passos es repeteixen de forma recursiva fins a la convergència.

• Talls de grafs dinàmics: Permet tornar a executar l'algorisme molt més ràpid després de modificar el problema (per exemple, després que noves llavors hagin estat afegides per l'usuari).

Crítica

Els mètodes de talls de grafs s'han convertit en una alternativa popular a les aproximacions de nivell basades en conjunts per optimitzar la localització d'un contorn. No obstant això, les aproximacions amb talls de grafs han estat criticades per diverses qüestions:

• Artefactes de conversió al sistema mètric: Quan una imatge està representada per una xarxa de connectivitat 4, els mètodes de talls gràfics poden exhibir artefactes no desitjats en forma de block. Diversos mètodes han estat proposats per abordar aquesta qüestió, com l'ús de vores addicionals o per la formulació del problema de flux màxim en un espai continu.
• Disminució del tall: D'ençà que els talls de grafs troben un tall mínim, l'algorisme pot tendir a produir un contorn prim. Per exemple, l'algorisme no és molt adequat per a la segmentació d'objectes prims com els vasos sanguinis
• Diverses etiquetes: Els talls de grafs només són capaços de trobar un òptim global per als problemes d'etiquetatge binari (és a dir, dues etiquetes), com la segmentació d'imatge primer pla / fons. S'han proposat ampliacions que poden trobar solucions aproximades pels problemes de talls gràfics de multietiquetat
• Memòria: La utilització de memòria dels talls de grafs augmenta ràpidament amb l'augment de mida de la imatge.

Referències

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