Grafsnitt i datorseende

Såsom den tillämpas inom datorseende , kan grafklippsoptimering användas för att effektivt lösa en mängd olika datorseendeproblem på låg nivå ( tidig syn ) , såsom bildutjämning , stereokorrespondensproblem , bildsegmentering , objektsamsegmentering och många andra datorseendeproblem som kan formuleras i termer av energiminimering . Många av dessa energiminimeringsproblem kan approximeras genom att lösa ett maximalt flödesproblem i en graf (och därmed definiera ett minimalt snitt av grafen med maxflödesmin-cut-satsen ). Under de flesta formuleringar av sådana problem i datorseende, motsvarar den minimala energilösningen den maximala a posteriori uppskattningen av en lösning. Även om många datorseendealgoritmer involverar skärning av en graf (t.ex. normaliserade skärningar), används termen "grafsnitt" specifikt på de modeller som använder en optimering av maxflöde/minutsnitt (andra grafklippningsalgoritmer kan betraktas som grafpartitionering algoritmer).

"Binära" problem (som att försvaga en binär bild) kan lösas exakt med detta tillvägagångssätt; problem där pixlar kan märkas med mer än två olika etiketter (som stereokorrespondens eller förnedring av en gråskalebild ) kan inte lösas exakt, men lösningar som produceras är vanligtvis nära det globala optimum.

Historia

Teorin om grafsnitt som användes som en optimeringsmetod tillämpades först i datorseende i den nyskapande uppsatsen av Greig, Porteous och Seheult från Durham University . Allan Seheult och Bruce Porteous var medlemmar i Durhams prisade statistikgrupp på den tiden, ledd av Julian Besag och Peter Green (statistiker), med optimeringsexperten Margaret Greig anmärkningsvärd som den första kvinnliga personalen någonsin på Durham Mathematical Sciences Department.

I det Bayesianska statistiska sammanhanget för utjämning av brusiga (eller korrupta) bilder visade de hur den maximala uppskattningen i efterhand av en binär bild kan erhållas exakt genom att maximera flödet genom ett associerat bildnätverk, vilket involverar införandet av en källa och sänka . Problemet visade sig därför vara effektivt lösbart. Före detta resultat ungefärliga tekniker som simulerad glödgning (som föreslagits av bröderna Geman ), eller itererade villkorade lägen (en typ av girig algoritm som föreslagits av Julian Besag ) för att lösa sådana bildutjämningsproblem.

Även om det allmänna $k$ -färgproblemet förblir olöst för $k>2,$ tillvägagångssättet hos Greig, Porteous och Seheult visat sig ha bred tillämpbarhet i allmänna datorseendeproblem. Greig, Porteous och Seheult tillvägagångssätt tillämpas ofta iterativt på en sekvens av binära problem, vanligtvis ger nära optimala lösningar.

År 2011, C. Couprie et al. föreslog ett allmänt ramverk för bildsegmentering, kallat "Power Watershed", som minimerade en verkligt värderad indikatorfunktion från [0,1] över en graf, begränsad av användarfrön (eller unära termer) satta till 0 eller 1, där minimering av indikatorfunktionen över grafen optimeras med avseende på en exponent $p$ . När $p=1$ optimeras Power Watershed genom grafklipp, när $p=0$ optimeras Power Watershed med kortaste vägar, $p=2$ är optimerad av Random walker-algoritmen och $p=\infty$ är optimerad av Watershed (bildbehandling) -algoritmen. På detta sätt kan Power Watershed ses som en generalisering av grafsnitt som ger en enkel koppling med andra energioptimeringssegmenterings-/klustringsalgoritmer.

Binär segmentering av bilder

Notation

Bild: $x\in \{R,G,B\}^{N}$
Utdata: Segmentering (även kallad opacitet) $S\in R^{N}$ (mjuk segmentering). För hård segmentering $S\in \{0{\text{ för bakgrund}},1{\text{ för förgrund/objekt som ska detekteras} }\}^{N}$
Energifunktion : $E(x,S,C,\lambda )$ där C är färgparametern och λ är koherensparametern.
$E(x,S,C,\lambda )=E_{\rm {color} }+E_{\rm {koherens}}$
Optimering: Segmenteringen kan uppskattas som ett globalt minimum över S: ${\arg \min }_{S}E(x,S,C,\ lambda )$

Befintliga metoder

Standard grafsnitt: optimera energifunktionen över segmenteringen (okänt S-värde).
Itererade grafklipp:

Första steget optimerar över färgparametrarna med hjälp av K-medel.
Det andra steget utför den vanliga grafklippningsalgoritmen.

Dessa 2 steg upprepas rekursivt tills konvergens.

Dynamiska grafklipp: Gör det möjligt att köra om algoritmen mycket snabbare efter att ha ändrat problemet (t.ex. efter att nya frön har lagts till av en användare).

Energifunktion

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

där energin $E$ är sammansatt av två olika modeller ( $E_{\rm {color}}$ och $E_{ \rm {koherens}}$ ):

Sannolikhet / Färgmodell / Regional term

$E_{\rm {color}}$ — enär term som beskriver sannolikheten för varje färg.

Denna term kan modelleras med hjälp av olika lokala (t.ex. texoner) eller globala (t.ex. histogram, GMM, Adaboost-sannolikhet) tillvägagångssätt som beskrivs nedan.

Histogram

Vi använder intensiteter av pixlar markerade som frön för att få histogram för objekt (förgrund) och bakgrundsintensitetsfördelningar: P(I|O) och P(I|B).
Sedan använder vi dessa histogram för att ställa in de regionala straffen som negativa log-sannolikheter.

GMM (Gaussisk blandningsmodell)

Vi använder vanligtvis två distributioner: en för bakgrundsmodellering och en annan för förgrundspixlar.
Använd en Gaussisk blandningsmodell (med 5–8 komponenter) för att modellera de två fördelningarna.
Mål: Försök att dra isär de två fördelningarna.

Texon

En texon (eller texton) är en uppsättning pixlar som har vissa egenskaper och som upprepas i en bild.
Steg:

Bestäm en bra naturlig skala för texturelementen.
Beräkna icke-parametrisk statistik för modellens inre texoner, antingen på intensitet eller på Gabor-filtersvar.

Exempel:
- Deformerbar modellbaserad strukturerad objektsegmentering
- Kontur- och texturanalys för bildsegmentering

Tidigare / Sammanhållningsmodell / Gränsterm

$E_{\rm {koherens}}$ — binär term som beskriver koherensen mellan grannskapspixlar.

I praktiken definieras pixlar som grannar om de är angränsande antingen horisontellt, vertikalt eller diagonalt (4-vägs-anslutning eller 8-vägs-anslutning för 2D-bilder).
Kostnaderna kan baseras på lokal intensitetsgradient, Laplacian nollkorsning, gradientriktning, färgblandningsmodell,...
Olika energifunktioner har definierats:
- Standard Markov slumpmässigt fält : Associera ett straff till oense pixlar genom att utvärdera skillnaden mellan deras segmenteringsetikett (grovt mått på längden på gränserna). Se Boykov och Kolmogorov ICCV 2003
- Villkorligt slumpmässigt fält : Om färgen är väldigt olika kan det vara ett bra ställe att sätta en gräns. Se Lafferty et al. 2001; Kumar och Hebert 2003

Kritik

Grafsnittsmetoder har blivit populära alternativ till nivåuppsättningsbaserade metoder för att optimera platsen för en kontur (se för en omfattande jämförelse). Emellertid har graph cut-metoder kritiserats i litteraturen för flera frågor:

Metrikationsartefakter: När en bild representeras av ett 4-kopplat gitter, kan grafsnittsmetoder uppvisa oönskade "blockitets"-artefakter. Olika metoder har föreslagits för att lösa detta problem, såsom att använda ytterligare kanter eller genom att formulera maxflödesproblemet i kontinuerligt utrymme.
Krympande bias: Eftersom grafsnitt hittar ett minimumsnitt, kan algoritmen vara förspänd mot att producera en liten kontur. Till exempel är algoritmen inte väl lämpad för segmentering av tunna föremål som blodkärl (se för en föreslagen fix).
Flera etiketter: Grafklipp kan bara hitta ett globalt optimum för problem med binära märkning (dvs. två etiketter), såsom segmentering av förgrunds-/bakgrundsbilder. Tillägg har föreslagits som kan hitta ungefärliga lösningar för problem med grafsnitt med flera etiketter.
Minne: minnesanvändningen för grafklipp ökar snabbt när bildstorleken ökar. Som en illustration tilldelar Boykov-Kolmogorov maxflödesalgoritmen v2.2 $24n+14m$ byte ( $n$ och $m$ är respektive antalet noder och kanter i grafen). Ändå har en del arbete nyligen gjorts i denna riktning för att reducera graferna före beräkningen av maximalt flöde.

Algoritm

Minimering görs med hjälp av en standard minimisnittsalgoritm.
Tack vare Max-flow min-cut-satsen kan vi lösa energiminimering genom att maximera flödet över nätverket. Max Flow-problemet består av en riktad graf med kanter märkta med kapacitet, och det finns två distinkta noder: källan och sänkan. Intuitivt är det lätt att se att det maximala flödet bestäms av flaskhalsen.

Implementering (exakt)

Boykov-Kolmogorov-algoritmen är ett effektivt sätt att beräkna maxflödet för datorseenderelaterad graf.

Implementering (approximation)

Sim Cut-algoritmen approximerar grafklippet. Algoritmen implementerar en lösning genom simulering av ett elektriskt nätverk. Detta är tillvägagångssättet som föreslås av Cederbaums maximala flödessats . Acceleration av algoritmen är möjlig genom parallell beräkning.

programvara

http://pub.ist.ac.at/~vnk/software.html — En implementering av maxflow-algoritmen som beskrivs i "An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Computer Vision" av Vladimir Kolmogorov
http://vision.csd.uwo.ca/code/ — några grafklippta bibliotek och MATLAB-omslag
http://gridcut.com/ — snabb multi-core max-flow/min-cut lösare optimerad för rutnätsliknande grafer
http://virtualscalpel.com/ — En implementering av Sim Cut ; en algoritm för att beräkna en ungefärlig lösning av minsta st-snitt på ett massivt parallellt sätt.