Grafic tăiat

Graficul tăiat este o metodă de optimizare aplicabilă unei familii numeroase de funcții variabile discrete, care își datorează numele faptului că se bazează pe teoria rețelelor de flux . Datorită teoremei debitului maxim și a tăierii minime , determinarea tăierii minime pe un grafic care reprezintă o rețea de flux este echivalentă cu calcularea debitului maxim pe rețea. Având în vedere o funcție pseudo-booleană , dacă este posibil să se construiască o rețea de flux astfel încât pentru fiecare posibilă tăiere valoarea debitului tăiat să corespundă cu o atribuire de variabile funcției și invers, este posibil să se găsească minimul global de funcția în timp polinomial prin calcularea unei tăieturi minime a graficului care reprezintă această rețea de flux.

Nu toate funcțiile pseudo-booleene sunt reprezentabile printr-o rețea de flux, iar căutarea minimului global în cazul general este o problemă NP-hard . Există condiții suficiente care caracterizează familiile de funcții care pot fi optimizate prin tăierea graficului în timp polinomial, cum ar fi de exemplu funcțiile pătratice submodulare. Este posibil să se extindă metoda la funcții cu variabile discrete cu mai mult de două valori prin algoritmi iterativi aproximativi, cu garanții puternice de optimitate a rezultatului, care calculează o reducere minimă la fiecare iterație.

Optimizarea tăierii graficului este un instrument util pentru deducerea modelelor grafice , cum ar fi câmpurile Markov aleatorii și câmpurile condiționate aleatorii , și are aplicații în numeroase probleme de analiză digitală a imaginii și de vedere computerizată , cum ar fi segmentarea , ^[1] ^[2] anularea zgomotului , ^{[3 ]} înregistrare ^[4] ^[5] și potrivire stereo . ^[6] ^[7]

Reprezentabilitate

O funcție pseudo-booleană $f:\{0,1\}^{n}\to \mathbb {R}$ ${\ displaystyle f: \ {0,1 \} ^ {n} \ to \ mathbb {R}}$ ${\ displaystyle f: \ {0,1 \} ^ {n} \ to \ mathbb {R}}$ se spune că este reprezentat printr-un grafic $G.$ ${\ displaystyle G}$ $G.$ dacă există un grafic cu greutăți non-negative $G=(V,E)$ ${\ displaystyle G = (V, E)}$ ${\ displaystyle G = (V, E)}$ cu noduri terminale sursă $s$ ${\ displaystyle s}$ $s$ si bine $t$ ${\ displaystyle t}$ $t$ și un subset de vârfuri $V_{0}=\{v_{1},\dots ,v_{n}\}\subset V-\{s,t\}$ ${\ displaystyle V_ {0} = \ {v_ {1}, \ dots, v_ {n} \} \ subset V - \ {s, t \}}$ ${\ displaystyle V_ {0} = \ {v_ {1}, \ dots, v_ {n} \} \ subset V - \ {s, t \}}$ astfel încât, pentru orice tuplu de valori $(x_{1},\dots ,x_{n})\in \{0,1\}^{n}$ ${\ displaystyle (x_ {1}, \ dots, x_ {n}) \ in \ {0,1 \} ^ {n}}$ ${\ displaystyle (x_ {1}, \ dots, x_ {n}) \ in \ {0,1 \} ^ {n}}$ atribuit variabilelor, $f(x_{1},\dots ,x_{n})$ ${\ displaystyle f (x_ {1}, \ dots, x_ {n})}$ ${\ displaystyle f (x_ {1}, \ dots, x_ {n})}$ este egală (mai mică decât o constantă) cu valoarea fluxului determinată de o tăiere minimă $C=(S,T)$ ${\ displaystyle C = (S, T)}$ ${\ displaystyle C = (S, T)}$ a graficului $G.$ ${\ displaystyle G}$ $G.$ astfel încât $v_{i}\in S$ ${\ displaystyle v_ {i} \ în S}$ ${\ displaystyle v_ {i} \ în S}$ de sine $x_{i}=0$ ${\ displaystyle x_ {i} = 0}$ ${\ displaystyle x_ {i} = 0}$ Și $v_{i}\in T$ ${\ displaystyle v_ {i} \ în T}$ ${\ displaystyle v_ {i} \ în T}$ de sine $x_{i}=1$ ${\ displaystyle x_ {i} = 1}$ ${\ displaystyle x_ {i} = 1}$ . ^[8]

Funcțiile pseudo-booleene pot fi clasificate în funcție de ordinea lor, determinată de numărul maxim de variabile conținute într-un singur termen. Toate funcțiile de prim ordin sunt întotdeauna reprezentabile. Funcții quadratice, care au formă

f(\mathbf {x} )=w_{0}+\sum _{i}w_{i}(x_{i})+\sum _{i<j}w_{ij}(x_{i},x_{j}).

{\ displaystyle f (\ mathbf {x}) = w_ {0} + \ sum _ {i} w_ {i} (x_ {i}) + \ sum _ {i <j} w_ {ij} (x_ {i }, x_ {j}).}

{\ displaystyle f (\ mathbf {x}) = w_ {0} + \ sum _ {i} w_ {i} (x_ {i}) + \ sum _ {i <j} w_ {ij} (x_ {i }, x_ {j}).}

pot fi reprezentate dacă și numai dacă îndeplinesc o condiție numită submodularitate sau dacă pentru fiecare termen $w_{ij}$ ${\ displaystyle w_ {ij}}$ ${\ displaystyle w_ {ij}}$ a părții pătratice apare că

w_{ij}(0,0)+w_{ij}(1,1)\leq w_{ij}(0,1)+w_{ij}(1,0).

{\ displaystyle w_ {ij} (0,0) + w_ {ij} (1,1) \ leq w_ {ij} (0,1) + w_ {ij} (1,0).}

{\ displaystyle w_ {ij} (0,0) + w_ {ij} (1,1) \ leq w_ {ij} (0,1) + w_ {ij} (1,0).}

Funcțiile cubice, care au formă

f(\mathbf {x} )=w_{0}+\sum _{i}w_{i}(x_{i})+\sum _{i<j}w_{ij}(x_{i},x_{j})+\sum _{i<j<k}w_{ijk}(x_{i},x_{j},x_{k})

{\ displaystyle f (\ mathbf {x}) = w_ {0} + \ sum _ {i} w_ {i} (x_ {i}) + \ sum _ {i <j} w_ {ij} (x_ {i }, x_ {j}) + \ sum _ {i <j <k} w_ {ijk} (x_ {i}, x_ {j}, x_ {k})}

{\ displaystyle f (\ mathbf {x}) = w_ {0} + \ sum _ {i} w_ {i} (x_ {i}) + \ sum _ {i <j} w_ {ij} (x_ {i }, x_ {j}) + \ sum _ {i <j <k} w_ {ijk} (x_ {i}, x_ {j}, x_ {k})}

pot fi reprezentate dacă și numai dacă sunt regulate, adică toate proiecțiile posibile în două variabile ale funcției (obținute prin fixarea uneia dintre cele trei variabile) sunt submodulare. Pentru funcțiile de ordin superior, regularitatea este o condiție necesară pentru reprezentabilitate. ^[8]

Construcția graficului

Construcția graficului unei funcții reprezentabile este simplificată de faptul că suma a două funcții reprezentabile $f^{'}$ ${\ displaystyle f '}$ $f '$ Și $f^{″}$ ${\ displaystyle f ''}$ $f ''$ este la rândul său reprezentabil, iar graficul corespunzător $G=(V'\cup V'',E'\cup E'')$ ${\ displaystyle G = (V '\ cup V' ', E' \ cup E '')}$ ${\ displaystyle G = (V '\ cup V' ', E' \ cup E '')}$ este dat de unirea graficelor respective $G'=(V',E')$ ${\ displaystyle G '= (V', E ')}$ ${\ displaystyle G '= (V', E ')}$ Și $G''=(V'',E'')$ ${\ displaystyle G '' = (V '', E '')}$ ${\ displaystyle G '' = (V '', E '')}$ . Această teoremă permite construirea de grafice separate pentru fiecare termen, care pot fi unite pentru a obține graficul întregii funcții. ^[8]

Graficul asociat cu o funcție pătratică a $n$ ${\ displaystyle n}$ $n$ variabile conține $n+2$ ${\ displaystyle n + 2}$ ${\ displaystyle n + 2}$ noduri, dintre care două reprezintă sursa și puțul, iar restul reprezintă variabilele. Pentru funcțiile de ordin superior, graficul conține noduri auxiliare care vă permit să reprezentați interacțiuni de ordin superior.

Termeni unari

Un termen unar $w_{i}$ ${\ displaystyle w_ {i}}$ $w_ {i}$ dependent de o singură variabilă $x_{i}$ ${\ displaystyle x_ {i}}$ $x_i$ poate fi reprezentat printr-un grafic cu un nod non-terminal $v_{i}$ ${\ displaystyle v_ {i}}$ $tu}$ și un arc $s\rightarrow v_{i}$ ${\ displaystyle s \ rightarrow v_ {i}}$ ${\ displaystyle s \ rightarrow v_ {i}}$ cu greutate $w_{i}(1)-w_{i}(0)$ ${\ displaystyle w_ {i} (1) -w_ {i} (0)}$ ${\ displaystyle w_ {i} (1) -w_ {i} (0)}$ de sine $w_{i}(1)\geq w_{i}(0)$ ${\ displaystyle w_ {i} (1) \ geq w_ {i} (0)}$ ${\ displaystyle w_ {i} (1) \ geq w_ {i} (0)}$ , sau $v_{i}\rightarrow t$ ${\ displaystyle v_ {i} \ rightarrow t}$ ${\ displaystyle v_ {i} \ rightarrow t}$ cu greutate $w_{i}(0)-w_{i}(1)$ ${\ displaystyle w_ {i} (0) -w_ {i} (1)}$ ${\ displaystyle w_ {i} (0) -w_ {i} (1)}$ de sine $w_{i}(1)<w_{i}(0)$ ${\ displaystyle w_ {i} (1) <w_ {i} (0)}$ ${\ displaystyle w_ {i} (1) <w_ {i} (0)}$ . ^[8]

Termeni binari

Exemplu de grafic reprezentând un termen pătratic

w_{ij}(x_{i},x_{j})

{\ displaystyle w_ {ij} (x_ {i}, x_ {j})}

{\ displaystyle w_ {ij} (x_ {i}, x_ {j})}

În cazul în care

w_{ij}(1,0)-w_{ij}(0,0)>0

{\ displaystyle w_ {ij} (1,0) -w_ {ij} (0,0)> 0}

{\ displaystyle w_ {ij} (1,0) -w_ {ij} (0,0)> 0}

Și

w_{ij}(1,1)-w_{ij}(1,0)<0

{\ displaystyle w_ {ij} (1,1) -w_ {ij} (1,0) <0}

{\ displaystyle w_ {ij} (1,1) -w_ {ij} (1,0) <0}

.

Un termen pătratic (sau binar) $w_{ij}$ ${\ displaystyle w_ {ij}}$ ${\ displaystyle w_ {ij}}$ poate fi reprezentat printr-un grafic care conține două noduri non-terminale $v_{i}$ ${\ displaystyle v_ {i}}$ $tu}$ Și $v_{j}$ ${\ displaystyle v_ {j}}$ $v_ {j}$ . Termenul poate fi rescris în mod echivalent ca

w_{ij}(x_{i},x_{j})=w_{ij}(0,0)+k_{i}x_{i}+k_{j}x_{j}+k_{ij}\left((1-x_{i})x_{j}+x_{i}(1-x_{j})\right)

{\ displaystyle w_ {ij} (x_ {i}, x_ {j}) = w_ {ij} (0,0) + k_ {i} x_ {i} + k_ {j} x_ {j} + k_ {ij } \ left ((1-x_ {i}) x_ {j} + x_ {i} (1-x_ {j}) \ right)}

{\ displaystyle w_ {ij} (x_ {i}, x_ {j}) = w_ {ij} (0,0) + k_ {i} x_ {i} + k_ {j} x_ {j} + k_ {ij } \ left ((1-x_ {i}) x_ {j} + x_ {i} (1-x_ {j}) \ right)}

cu

{\begin{aligned}k_{i}&={\frac {1}{2}}(w_{ij}(1,0)-w_{ij}(0,0))\\k_{j}&={\frac {1}{2}}(w_{ij}(1,1)-w_{ij}(1,0))\\k_{ij}&={\frac {1}{2}}(w_{ij}(0,1)+w_{ij}(1,0)-w_{ij}(0,0)-w_{ij}(1,1)).\end{aligned}}

{\ displaystyle {\ begin {align} k_ {i} & = {\ frac {1} {2}} (w_ {ij} (1,0) -w_ {ij} (0,0)) \\ k_ { j} & = {\ frac {1} {2}} (w_ {ij} (1,1) -w_ {ij} (1,0)) \\ k_ {ij} & = {\ frac {1} { 2}} (w_ {ij} (0,1) + w_ {ij} (1,0) -w_ {ij} (0,0) -w_ {ij} (1,1)). \ End {align} }}

{\ displaystyle {\ begin {align} k_ {i} & = {\ frac {1} {2}} (w_ {ij} (1,0) -w_ {ij} (0,0)) \\ k_ { j} & = {\ frac {1} {2}} (w_ {ij} (1,1) -w_ {ij} (1,0)) \\ k_ {ij} & = {\ frac {1} { 2}} (w_ {ij} (0,1) + w_ {ij} (1,0) -w_ {ij} (0,0) -w_ {ij} (1,1)). \ End {align} }}

În această expresie, primul termen este o constantă și nu este reprezentat de niciun vârf, cei doi termeni următori depind de o variabilă și, prin urmare, sunt reprezentați de un arc, în modul descris mai sus pentru termenii unari, în cele din urmă, al patrulea termen este reprezentat dintr-un arc $v_{i}\rightarrow v_{j}$ ${\ displaystyle v_ {i} \ rightarrow v_ {j}}$ ${\ displaystyle v_ {i} \ rightarrow v_ {j}}$ cu greutate $w_{ij}(0,1)+w_{ij}(1,0)-w_{ij}(0,0)-w_{ij}(1,1)$ ${\ displaystyle w_ {ij} (0,1) + w_ {ij} (1,0) -w_ {ij} (0,0) -w_ {ij} (1,1)}$ ${\ displaystyle w_ {ij} (0,1) + w_ {ij} (1,0) -w_ {ij} (0,0) -w_ {ij} (1,1)}$ (starea submodulară garantează că greutatea este negativă). ^[8]

Termeni ternari

Un termen cubic (sau ternar) $w_{ijk}$ ${\ displaystyle w_ {ijk}}$ ${\ displaystyle w_ {ijk}}$ poate fi reprezentat printr-un grafic cu patru noduri non-terminale, dintre care trei $v_{i}$ ${\ displaystyle v_ {i}}$ $tu}$ , $v_{j}$ ${\ displaystyle v_ {j}}$ $v_ {j}$ Și $v_{k}$ ${\ displaystyle v_ {k}}$ $v_ {k}$ acestea sunt asociate cu cele trei variabile, cu adăugarea unui al patrulea nod auxiliar $v_{ijk}$ ${\ displaystyle v_ {ijk}}$ ${\ displaystyle v_ {ijk}}$ .^[9] Un termen ternar generic poate fi rescris ca suma unei constante, trei termeni unari, trei termeni binari și un termen ternar în formă simplificată. Pot apărea două cazuri diferite, în funcție de semnul cantității $p=w_{ijk}(0,0,0)+w_{ijk}(0,1,1)+w_{ijk}(1,0,1)+w_{ijk}(1,1,0)$ ${\ displaystyle p = w_ {ijk} (0,0,0) + w_ {ijk} (0,1,1) + w_ {ijk} (1,0,1) + w_ {ijk} (1,1, 0)}$ ${\ displaystyle p = w_ {ijk} (0,0,0) + w_ {ijk} (0,1,1) + w_ {ijk} (1,0,1) + w_ {ijk} (1,1, 0)}$ . De sine $p>0$ ${\ displaystyle p> 0}$ $p> 0$ da ai

w_{ijk}(x_{i},x_{j},x_{k})=w_{ijk}(0,0,0)+p_{1}(x_{i}-1)+p_{2}(x_{j}-1)+p_{3}(x_{k}-1)+p_{23}(x_{j}-1)x_{k}+p_{31}x_{i}(x_{k}-1)+p_{12}(x_{i}-1)x_{j}-px_{i}x_{j}x_{k}

{\ displaystyle w_ {ijk} (x_ {i}, x_ {j}, x_ {k}) = w_ {ijk} (0,0,0) + p_ {1} (x_ {i} -1) + p_ {2} (x_ {j} -1) + p_ {3} (x_ {k} -1) + p_ {23} (x_ {j} -1) x_ {k} + p_ {31} x_ {i} (x_ {k} -1) + p_ {12} (x_ {i} -1) x_ {j} -px_ {i} x_ {j} x_ {k}}

{\ displaystyle w_ {ijk} (x_ {i}, x_ {j}, x_ {k}) = w_ {ijk} (0,0,0) + p_ {1} (x_ {i} -1) + p_ {2} (x_ {j} -1) + p_ {3} (x_ {k} -1) + p_ {23} (x_ {j} -1) x_ {k} + p_ {31} x_ {i} (x_ {k} -1) + p_ {12} (x_ {i} -1) x_ {j} -px_ {i} x_ {j} x_ {k}}

Exemplu de grafic reprezentând termenul ternar

px_{i}x_{j}x_{k}

{\ displaystyle px_ {i} x_ {j} x_ {k}}

{\ displaystyle px_ {i} x_ {j} x_ {k}}

În cazul în care

p>0

{\ displaystyle p> 0}

p> 0

(stânga) e

p<0

{\ displaystyle p <0}

{\ displaystyle p <0}

(dreapta).

cu

{\begin{aligned}p_{1}&=w_{ijk}(1,0,1)-w_{ijk}(0,0,1)\\p_{2}&=w_{ijk}(1,1,0)-w_{ijk}(1,0,1)\\p_{3}&=w_{ijk}(0,1,1)-w_{ijk}(0,1,0)\\p_{23}&=w_{ijk}(0,0,1)+w_{ijk}(0,1,0)-w_{ijk}(0,0,0)-w_{ijk}(0,1,1)\\p_{31}&=w_{ijk}(0,0,1)+w_{ijk}(1,0,0)-w_{ijk}(0,0,0)-w_{ijk}(1,0,1)\\p_{12}&=w_{ijk}(0,1,0)+w_{ijk}(1,0,0)-w_{ijk}(0,0,0)-w_{ijk}(1,1,0).\end{aligned}}

{\ displaystyle {\ begin {align} p_ {1} & = w_ {ijk} (1,0,1) -w_ {ijk} (0,0,1) \\ p_ {2} & = w_ {ijk} (1,1,0) -w_ {ijk} (1,0,1) \\ p_ {3} & = w_ {ijk} (0,1,1) -w_ {ijk} (0,1,0) \\ p_ {23} & = w_ {ijk} (0,0,1) + w_ {ijk} (0,1,0) -w_ {ijk} (0,0,0) -w_ {ijk} (0 , 1,1) \\ p_ {31} & = w_ {ijk} (0,0,1) + w_ {ijk} (1,0,0) -w_ {ijk} (0,0,0) -w_ {ijk} (1,0,1) \\ p_ {12} & = w_ {ijk} (0,1,0) + w_ {ijk} (1,0,0) -w_ {ijk} (0,0 , 0) -w_ {ijk} (1,1,0). \ End {align}}}

{\ displaystyle {\ begin {align} p_ {1} & = w_ {ijk} (1,0,1) -w_ {ijk} (0,0,1) \\ p_ {2} & = w_ {ijk} (1,1,0) -w_ {ijk} (1,0,1) \\ p_ {3} & = w_ {ijk} (0,1,1) -w_ {ijk} (0,1,0) \\ p_ {23} & = w_ {ijk} (0,0,1) + w_ {ijk} (0,1,0) -w_ {ijk} (0,0,0) -w_ {ijk} (0 , 1,1) \\ p_ {31} & = w_ {ijk} (0,0,1) + w_ {ijk} (1,0,0) -w_ {ijk} (0,0,0) -w_ {ijk} (1,0,1) \\ p_ {12} & = w_ {ijk} (0,1,0) + w_ {ijk} (1,0,0) -w_ {ijk} (0,0 , 0) -w_ {ijk} (1,1,0). \ End {align}}}

De sine $p<0$ ${\ displaystyle p <0}$ ${\ displaystyle p <0}$ construcția este analogă, dar variabilele vor lua valori opuse. Dacă funcția de pornire este regulată, atunci toate proiecțiile sale în două variabile sunt submodulare, garantând acest lucru $p_{23}$ ${\ displaystyle p_ {23}}$ ${\ displaystyle p_ {23}}$ , $p_{31}$ ${\ displaystyle p_ {31}}$ ${\ displaystyle p_ {31}}$ Și $p_{12}$ ${\ displaystyle p_ {12}}$ ${\ displaystyle p_ {12}}$ sunt pozitive și, prin urmare, că toți termenii care alcătuiesc noua reprezentare sunt submodulari.

În această descompunere, termenii constanți, unari și binari pot fi reprezentați așa cum se vede mai sus. De sine $p>0$ ${\ displaystyle p> 0}$ $p> 0$ ultimul termen ternar poate fi reprezentat printr-un grafic cu patru muchii $v_{i}\rightarrow v_{ijk}$ ${\ displaystyle v_ {i} \ rightarrow v_ {ijk}}$ ${\ displaystyle v_ {i} \ rightarrow v_ {ijk}}$ , $v_{j}\rightarrow v_{ijk}$ ${\ displaystyle v_ {j} \ rightarrow v_ {ijk}}$ ${\ displaystyle v_ {j} \ rightarrow v_ {ijk}}$ , $v_{k}\rightarrow v_{ijk}$ ${\ displaystyle v_ {k} \ rightarrow v_ {ijk}}$ ${\ displaystyle v_ {k} \ rightarrow v_ {ijk}}$ , $v_{ijk}\rightarrow t$ ${\ displaystyle v_ {ijk} \ rightarrow t}$ ${\ displaystyle v_ {ijk} \ rightarrow t}$ toate cu greutate $p$ ${\ displaystyle p}$ $p$ , în timp ce dacă $p<0$ ${\ displaystyle p <0}$ ${\ displaystyle p <0}$ termenul poate fi reprezentat prin patru arce $v_{ijk}\rightarrow v_{i}$ ${\ displaystyle v_ {ijk} \ rightarrow v_ {i}}$ ${\ displaystyle v_ {ijk} \ rightarrow v_ {i}}$ , $v_{ijk}\rightarrow v_{j}$ ${\ displaystyle v_ {ijk} \ rightarrow v_ {j}}$ ${\ displaystyle v_ {ijk} \ rightarrow v_ {j}}$ , $v_{ijk}\rightarrow v_{k}$ ${\ displaystyle v_ {ijk} \ rightarrow v_ {k}}$ ${\ displaystyle v_ {ijk} \ rightarrow v_ {k}}$ , $s\rightarrow v_{ijk}$ ${\ displaystyle s \ rightarrow v_ {ijk}}$ ${\ displaystyle s \ rightarrow v_ {ijk}}$ cu greutate $-p$ ${\ displaystyle -p}$ ${\ displaystyle -p}$ . ^[8]

Calculul tăierii minime

Odată ce graficul reprezentând o funcție pseudo-booleană a fost construit, este posibil să se calculeze reducerea minimă utilizând unul dintre diferiții algoritmi pentru rețelele de flux, cum ar fi cei de la Ford-Fulkerson , Edmonds-Karp sau Boykov-Kolmogorov . Rezultatul este o partiție a graficului în două componente conectate $S.$ ${\ displaystyle S}$ $S.$ Și $T.$ ${\ displaystyle T}$ $T.$ astfel încât $s\in S$ ${\ displaystyle s \ în S}$ $s \ în S$ Și $t\in T$ ${\ displaystyle t \ in T}$ $t \ in T$ , iar minimul global al funcției este atins când $x_{i}=0$ ${\ displaystyle x_ {i} = 0}$ ${\ displaystyle x_ {i} = 0}$ pentru fiecare $the$ ${\ displaystyle i}$ $the$ astfel încât nodul corespunzător $v_{i}\in S$ ${\ displaystyle v_ {i} \ în S}$ ${\ displaystyle v_ {i} \ în S}$ , Și $x_{i}=1$ ${\ displaystyle x_ {i} = 1}$ ${\ displaystyle x_ {i} = 1}$ pentru fiecare $the$ ${\ displaystyle i}$ $the$ astfel încât nodul corespunzător $v_{i}\in T$ ${\ displaystyle v_ {i} \ în T}$ ${\ displaystyle v_ {i} \ în T}$ .

Algoritmii de flux maxim, cum ar fi cel Boykov-Kolmogorov, sunt foarte eficienți în practică pentru calcularea secvenței minime, dar au dezavantajul de a nu fi ușor paralelizabili, ceea ce împiedică exploatarea paralelismului inerent al hardware-ului modern și restricționează utilizarea în aplicațiile de calcul distribuite . S-au dezvoltat mai mulți algoritmi paraleli pentru calculul fluxului maxim, inclusiv push-relabel ^[10] și jump-flood , ^[1] care pot profita, de asemenea, de accelerația hardware în implementările GPGPU . ^[1] ^[11] ^[12]

Funcțiile variabilelor discrete cu mai mult de două valori

Construcția anterioară permite optimizarea globală a funcțiilor pseudo-booleene, dar este posibilă extinderea optimizării tăieturii graficului la funcțiile pătratice ale variabilelor discrete cu un număr finit de valori în formă

f(\mathbf {x} )=\sum _{i\in V}D(x_{i})+\sum _{(i,j)\in E}S(x_{i},x_{j})

{\ displaystyle f (\ mathbf {x}) = \ sum _ {i \ in V} D (x_ {i}) + \ sum _ {(i, j) \ in E} S (x_ {i}, x_ {j})}

{\ displaystyle f (\ mathbf {x}) = \ sum _ {i \ in V} D (x_ {i}) + \ sum _ {(i, j) \ in E} S (x_ {i}, x_ {j})}

cu $E\subseteq V\times V$ ${\ displaystyle E \ subseteq V \ times V}$ ${\ displaystyle E \ subseteq V \ times V}$ Și $x_{i}\in \Lambda =\{1,\dots ,k\}$ ${\ displaystyle x_ {i} \ in \ Lambda = \ {1, \ dots, k \}}$ ${\ displaystyle x_ {i} \ in \ Lambda = \ {1, \ dots, k \}}$ . Functia $D(x_{i})$ ${\ displaystyle D (x_ {i})}$ ${\ displaystyle D (x_ {i})}$ reprezintă contribuția unitară a variabilelor unice (adesea denumită termen de date ), în timp ce funcția $S(x_{i},x_{j})$ ${\ displaystyle S (x_ {i}, x_ {j})}$ ${\ displaystyle S (x_ {i}, x_ {j})}$ reprezintă interacțiunea binară între variabile ( termen de netezime ). În general, optimizarea globală a unor astfel de funcții este o problemă NP-hard , iar metodele de optimizare stocastică, cum ar fi recoacerea simulată, sunt sensibile la minimele locale și, în practică, pot genera rezultate arbitraj sub-optime. ^[13] Prin tăierea graficului este posibil să se construiască algoritmi de mișcare care să permită obținerea în timp polinomial a unui minim local cu proprietăți de optimitate puternice pentru o familie largă de funcții pătratice de interes practic (în cazul interacțiunii binare $S(x_{i},x_{j})$ ${\ displaystyle S (x_ {i}, x_ {j})}$ ${\ displaystyle S (x_ {i}, x_ {j})}$ este metric sau semimetric ), astfel încât valoarea funcției din soluție să se afle într-un factor cunoscut din minimul global. ^[14]

Având o funcție $f:\Lambda ^{n}\to \mathbb {R}$ ${\ displaystyle f: \ Lambda ^ {n} \ to \ mathbb {R}}$ ${\ displaystyle f: \ Lambda ^ {n} \ to \ mathbb {R}}$ cu $\Lambda =\{1,\dots ,k\}$ ${\ displaystyle \ Lambda = \ {1, \ dots, k \}}$ ${\ displaystyle \ Lambda = \ {1, \ dots, k \}}$ , și o anumită atribuire de valori $\mathbf {x} =(x_{1},\dots ,x_{n})\in \Lambda ^{n}$ ${\ displaystyle \ mathbf {x} = (x_ {1}, \ dots, x_ {n}) \ in \ Lambda ^ {n}}$ ${\ displaystyle \ mathbf {x} = (x_ {1}, \ dots, x_ {n}) \ in \ Lambda ^ {n}}$ variabilelor, este posibil să se asocieze fiecare sarcină $\mathbf {x}$ ${\ displaystyle \ mathbf {x}}$ $\ mathbf {x}$ cu o singură partiție $P=\{P_{l}|l\in \Lambda \}$ ${\ displaystyle P = \ {P_ {l} | l \ in \ Lambda \}}$ ${\ displaystyle P = \ {P_ {l} | l \ in \ Lambda \}}$ a setului de variabile, astfel încât $P_{l}=\{x_{i}|x_{i}=l\in \Lambda \}$ ${\ displaystyle P_ {l} = \ {x_ {i} | x_ {i} = l \ in \ Lambda \}}$ ${\ displaystyle P_ {l} = \ {x_ {i} | x_ {i} = l \ in \ Lambda \}}$ . Având două atribuții variabile diferite $P.$ ${\ displaystyle P}$ $P.$ Și ${P.}^{'}$ ${\ displaystyle P '}$ $P '$ și o valoare $\alpha \in \Lambda$ ${\ displaystyle \ alpha \ in \ Lambda}$ ${\ displaystyle \ alpha \ in \ Lambda}$ , o mișcare care se transformă $P.$ ${\ displaystyle P}$ $P.$ în ${P.}^{'}$ ${\ displaystyle P '}$ $P '$ se spune $\alpha$ ${\ displaystyle \ alpha}$ $\ alfa$ -expansiune dacă $P_{\alpha }\subset P'_{\alpha }$ ${\ displaystyle P _ {\ alpha} \ subset P '_ {\ alpha}}$ ${\ displaystyle P _ {\ alpha} \ subset P '_ {\ alpha}}$ Și $P'_{l}\subset P_{l}\;\forall l\in \Lambda -\{\alpha \}$ ${\ displaystyle P '_ {l} \ subset P_ {l} \; \ forall l \ in \ Lambda - \ {\ alpha \}}$ ${\ displaystyle P '_ {l} \ subset P_ {l} \; \ forall l \ in \ Lambda - \ {\ alpha \}}$ . Având în vedere o pereche de valori $\alpha$ ${\ displaystyle \ alpha}$ $\ alfa$ Și $\beta$ ${\ displaystyle \ beta}$ $\ beta$ , se spune o mutare $\alpha \beta$ ${\ displaystyle \ alpha \ beta}$ ${\ displaystyle \ alpha \ beta}$ -intercambiați dacă $P_{l}=P'_{l}\;\forall l\in \Lambda -\{\alpha ,\beta \}$ ${\ displaystyle P_ {l} = P '_ {l} \; \ forall l \ in \ Lambda - \ {\ alpha, \ beta \}}$ ${\ displaystyle P_ {l} = P '_ {l} \; \ forall l \ in \ Lambda - \ {\ alpha, \ beta \}}$ . Intuitiv, o mișcare de $\alpha$ ${\ displaystyle \ alpha}$ $\ alfa$ -expansiune începând de la $\mathbf {x}$ ${\ displaystyle \ mathbf {x}}$ $\ mathbf {x}$ constă în atribuirea valorii $\alpha$ ${\ displaystyle \ alpha}$ $\ alfa$ la unele variabile care au o valoare diferită în $\mathbf {x}$ ${\ displaystyle \ mathbf {x}}$ $\ mathbf {x}$ . O mutare de $\alpha \beta$ ${\ displaystyle \ alpha \ beta}$ ${\ displaystyle \ alpha \ beta}$ -swap este de a atribui $\alpha$ ${\ displaystyle \ alpha}$ $\ alfa$ la unele variabile care în $\mathbf {x}$ ${\ displaystyle \ mathbf {x}}$ $\ mathbf {x}$ au valoare $\beta$ ${\ displaystyle \ beta}$ $\ beta$ si invers.

La fiecare iterație, algoritmul $\alpha$ ${\ displaystyle \ alpha}$ $\ alfa$ -calcule de expansiune, pentru fiecare valoare posibilă $\alpha$ ${\ displaystyle \ alpha}$ $\ alfa$ , minimul funcției tuturor sarcinilor $\mathrm {A} (\mathbf {x} )$ ${\ displaystyle \ mathrm {A} (\ mathbf {x})}$ ${\ displaystyle \ mathrm {A} (\ mathbf {x})}$ care poate fi obținut printr-o mișcare de $\alpha$ ${\ displaystyle \ alpha}$ $\ alfa$ -expansiune pornind de la soluția actuală $\mathbf {x}$ ${\ displaystyle \ mathbf {x}}$ $\ mathbf {x}$ și o atribuie ca nouă valoare a soluției.

 $\mathbf {x} :={\text{valore arbitrario in }}\Lambda ^{n}$  $X$   $: =$   $valoare arbitrară în$   $Λ$   $n$   ${\ displaystyle \ mathbf {x}: = {\ text {valoare arbitrară în}} \ Lambda ^ {n}}$   ${\ displaystyle \ mathbf {x}: = {\ text {valoare arbitrară în}} \ Lambda ^ {n}}$ 
 ${\text{exit}}:=0$  $Ieșire$   $: =$   $0$   ${\ displaystyle {\ text {exit}}: = 0}$   ${\ displaystyle {\ text {exit}}: = 0}$ 
in timp ce ${\text{exit}}\neq 1$  $Ieșire$   $\neq$   $1$   ${\ displaystyle {\ text {exit}} \ neq 1}$   ${\ displaystyle {\ text {exit}} \ neq 1}$  :
     ${\text{exit}}=1$  $Ieșire$   $=$   $1$   ${\ displaystyle {\ text {exit}} = 1}$   ${\ displaystyle {\ text {exit}} = 1}$ 
    pentru fiecare $\alpha \in \Lambda$  $α$   $\in$   $Λ$   ${\ displaystyle \ alpha \ in \ Lambda}$   ${\ displaystyle \ alpha \ in \ Lambda}$  :
         $\mathbf {\hat {x}} :=\arg \min _{\mathbf {y} \in \mathrm {A} (\mathbf {x} )}f(\mathbf {y} )$  $X$   $^$   $: =$   $arg$    $min$   $y$   $\in$   $LA$   $($   $X$   $)$   $f$   $($   $y$   $)$   ${\ displaystyle \ mathbf {\ hat {x}}: = \ arg \ min _ {\ mathbf {y} \ in \ mathrm {A} (\ mathbf {x})} f (\ mathbf {y})}$   ${\ displaystyle \ mathbf {\ hat {x}}: = \ arg \ min _ {\ mathbf {y} \ in \ mathrm {A} (\ mathbf {x})} f (\ mathbf {y})}$ 
        dacă  $f(\mathbf {\hat {x}} )<\mathbf {x}$  $f$   $($   $X$   $^$   $)$   $<$   $X$   ${\ displaystyle f (\ mathbf {\ hat {x}}) <\ mathbf {x}}$   ${\ displaystyle f (\ mathbf {\ hat {x}}) <\ mathbf {x}}$  :
             $\mathbf {x} =\mathbf {\hat {x}}$  $X$   $=$   $X$   $^$   ${\ displaystyle \ mathbf {x} = \ mathbf {\ hat {x}}}$   ${\ displaystyle \ mathbf {x} = \ mathbf {\ hat {x}}}$ 
             ${\text{exit}}:=0$  $Ieșire$   $: =$   $0$   ${\ displaystyle {\ text {exit}}: = 0}$   ${\ displaystyle {\ text {exit}}: = 0}$

Algoritmul $\alpha \beta$ ${\ displaystyle \ alpha \ beta}$ ${\ displaystyle \ alpha \ beta}$ -swap este similar, dar caută cea mai mică dintre toate sarcinile $\mathrm {A} \mathrm {B} (\mathbf {x} )$ ${\ displaystyle \ mathrm {A} \ mathrm {B} (\ mathbf {x})}$ ${\ displaystyle \ mathrm {A} \ mathrm {B} (\ mathbf {x})}$ obținută printr-o mutare de $\alpha \beta$ ${\ displaystyle \ alpha \ beta}$ ${\ displaystyle \ alpha \ beta}$ -swap începând de la $\mathbf {x}$ ${\ displaystyle \ mathbf {x}}$ $\ mathbf {x}$ .

 $\mathbf {x} :={\text{valore arbitrario in }}\Lambda ^{n}$  $X$   $: =$   $valoare arbitrară în$   $Λ$   $n$   ${\ displaystyle \ mathbf {x}: = {\ text {valoare arbitrară în}} \ Lambda ^ {n}}$   ${\ displaystyle \ mathbf {x}: = {\ text {valoare arbitrară în}} \ Lambda ^ {n}}$ 
 ${\text{exit}}:=0$  $Ieșire$   $: =$   $0$   ${\ displaystyle {\ text {exit}}: = 0}$   ${\ displaystyle {\ text {exit}}: = 0}$ 
in timp ce ${\text{exit}}\neq 1$  $Ieșire$   $\neq$   $1$   ${\ displaystyle {\ text {exit}} \ neq 1}$   ${\ displaystyle {\ text {exit}} \ neq 1}$  :
     ${\text{exit}}=1$  $Ieșire$   $=$   $1$   ${\ displaystyle {\ text {exit}} = 1}$   ${\ displaystyle {\ text {exit}} = 1}$ 
    pentru fiecare  $(\alpha ,\beta )\in \Lambda ^{2}$  $($   $α$   $,$   $β$   $)$   $\in$   $Λ$   $2$   ${\ displaystyle (\ alpha, \ beta) \ in \ Lambda ^ {2}}$   ${\ displaystyle (\ alpha, \ beta) \ in \ Lambda ^ {2}}$  :
         $\mathbf {\hat {x}} :=\arg \min _{\mathbf {y} \in \mathrm {A} \mathrm {B} (\mathbf {x} )}f(\mathbf {y} )$  $X$   $^$   $: =$   $arg$    $min$   $y$   $\in$   $LA$   $B.$   $($   $X$   $)$   $f$   $($   $y$   $)$   ${\ displaystyle \ mathbf {\ hat {x}}: = \ arg \ min _ {\ mathbf {y} \ in \ mathrm {A} \ mathrm {B} (\ mathbf {x})} f (\ mathbf { y})}$   ${\ displaystyle \ mathbf {\ hat {x}}: = \ arg \ min _ {\ mathbf {y} \ in \ mathrm {A} \ mathrm {B} (\ mathbf {x})} f (\ mathbf { y})}$ 
        dacă  $f(\mathbf {\hat {x}} )<\mathbf {x}$  $f$   $($   $X$   $^$   $)$   $<$   $X$   ${\ displaystyle f (\ mathbf {\ hat {x}}) <\ mathbf {x}}$   ${\ displaystyle f (\ mathbf {\ hat {x}}) <\ mathbf {x}}$  :
             $\mathbf {x} =\mathbf {\hat {x}}$  $X$   $=$   $X$   $^$   ${\ displaystyle \ mathbf {x} = \ mathbf {\ hat {x}}}$   ${\ displaystyle \ mathbf {x} = \ mathbf {\ hat {x}}}$ 
             ${\text{exit}}:=0$  $Ieșire$   $: =$   $0$   ${\ displaystyle {\ text {exit}}: = 0}$   ${\ displaystyle {\ text {exit}}: = 0}$

În ambele cazuri, problema de minimizare conținută în bucla cea mai interioară poate fi rezolvată exact și eficient prin tăierea graficului. Ambii algoritmi se încheie cu siguranță într-un număr finit de iterații, iar în practică numărul iterațiilor este mic și cea mai mare parte a îmbunătățirii soluției are loc la prima iterație. Algoritmii pot produce rezultate diferite în funcție de valoarea inițială atribuită soluției, dar în practică sunt robuste în ceea ce privește inițializarea și pornirea de la o soluție inițială cu toate variabilele atribuite aceleiași valori arbitrare este în general suficientă pentru a obține rezultate bune. ^[14]

Soluția produsă de acești algoritmi nu este neapărat un punct de optim global, dar are în continuare garanții puternice de optimitate. De sine $S(x_{i},x_{j})$ ${\ displaystyle S (x_ {i}, x_ {j})}$ ${\ displaystyle S (x_ {i}, x_ {j})}$ este o metrică și $\mathbf {x}$ ${\ displaystyle \ mathbf {x}}$ $\ mathbf {x}$ este o soluție generată de algoritmul $\alpha$ ${\ displaystyle \ alpha}$ $\ alfa$ -expansiune, sau dacă $S(x_{i},x_{j})$ ${\ displaystyle S (x_ {i}, x_ {j})}$ ${\ displaystyle S (x_ {i}, x_ {j})}$ este un semimetric și $\mathbf {x}$ ${\ displaystyle \ mathbf {x}}$ $\ mathbf {x}$ este o soluție generată de algoritmul $\alpha \beta$ ${\ displaystyle \ alpha \ beta}$ ${\ displaystyle \ alpha \ beta}$ -Swap, atunci $f(\mathbf {x} )$ ${\ displaystyle f (\ mathbf {x})}$ $f ({\ mathbf {x}})$ se află într-un factor cunoscut și constant al minimului global $f(\mathbf {x} ^{*})$ ${\ displaystyle f (\ mathbf {x} ^ {*})}$ ${\ displaystyle f (\ mathbf {x} ^ {*})}$ : ^[14]

f(\mathbf {x} )\leq 2{\frac {\max _{\alpha \neq \beta \in \Lambda }S(\alpha ,\beta )}{\min _{\alpha \neq \beta \in \Lambda }S(\alpha ,\beta )}}f(\mathbf {x} ^{*}).

{\ displaystyle f (\ mathbf {x}) \ leq 2 {\ frac {\ max _ {\ alpha \ neq \ beta \ in \ Lambda} S (\ alpha, \ beta)} {\ min _ {\ alpha \ neq \ beta \ in \ Lambda} S (\ alpha, \ beta)}} f (\ mathbf {x} ^ {*}).}

{\ displaystyle f (\ mathbf {x}) \ leq 2 {\ frac {\ max _ {\ alpha \ neq \ beta \ in \ Lambda} S (\ alpha, \ beta)} {\ min _ {\ alpha \ neq \ beta \ in \ Lambda} S (\ alpha, \ beta)}} f (\ mathbf {x} ^ {*}).}

Funcții non submodulare

Optimizare pseudo-booleană quadratică .

În general, problema minimizării unei funcții pseudo-booleene non-submodulare este NP-hard și nu poate fi întotdeauna rezolvată în timp polinomial cu o simplă tăiere grafică. Cea mai simplă abordare practică este aproximarea funcției obiective cu o funcție similară, dar submodulară, de exemplu prin trunchierea tuturor termenilor non-submodulari sau înlocuirea lor cu expresii similare, dar submodulare. Cu toate acestea, această abordare produce în general rezultate sub-optime, a căror calitate este acceptabilă numai dacă numărul termenilor non-submodulari este relativ mic. ^[15]

În cazul funcțiilor pătratice non-submodulare, este posibil să se obțină o soluție parțială în timp polinomial folosind algoritmi precum QPBO . ^[15] Funcțiile de ordin superior pot fi reduse în timp polinomial în formă pătratică care poate fi optimizată prin QPBO. ^[16]

Funcții de ordin superior

Multe rezultate s-au concentrat pe optimizarea funcțiilor pătratice, care au fost studiate și caracterizate în profunzime, dar au fost dezvoltate și condiții mai generale pentru funcții de ordin superior. În timp ce funcțiile pătratice ne permit să modelăm eficient multe probleme, ele sunt totuși limitate de faptul că pot exprima doar interacțiuni binare între variabile. Abilitatea de a integra interacțiuni de ordin superior într-un model în anumite contexte vă permite să surprindeți mai eficient natura problemei și să oferiți rezultate de calitate superioară. Un exemplu sunt aplicațiile de procesare a imaginii digitale, în care fiecare variabilă reprezintă un pixel sau un voxel al imaginii și interacțiunile de ordin superior pot capta, de exemplu, informații despre textură, care ar fi dificil sau imposibil de încorporat într-un model exprimat printr-o funcție pătratică. ^[17]

Au fost studiate condiții suficiente analogi submodularității pentru a caracteriza funcțiile pseudo-booleene de ordin superior care pot fi optimizate în timp polinomial ^[18] și există extensii ale $\alpha$ ${\ displaystyle \ alpha}$ $\ alfa$ -expansiune e $\alpha \beta$ ${\ displaystyle \ alpha \ beta}$ ${\ displaystyle \ alpha \ beta}$ - schimb pentru unele familii de funcții de ordin superior. ^[17] Problema este totuși NP-hard în cazul general și au fost dezvoltate metode aproximative pentru optimizarea eficientă a funcțiilor care nu îndeplinesc aceste condiții. ^[18] ^[19]

Notă

^ ^a ^b ^c Peng și colab. , pp. 655-666 .
^ Rother și colab. , pp. 309-314 .
^ Lombaert și Cheriet , pp. 264-268 .
^ Deci și colab. , pp. 2450-2467 .
^ Tang și Chung , pp. 916-924 .
^ Kim și colab. , pp. 1033-1040 .
^ Hong și Chen , pp. 74-81 .
^ ^a ^b ^c ^d ^e ^f Kolmogorov și Zabin , pp. 1645-1656 .
^ Este necesară adăugarea unui nod auxiliar, deoarece un grafic fără noduri auxiliare poate reprezenta doar interacțiuni binare între variabile.
^ Goldberg și Tarjan , pp. 921-940 .
^ Vineet și Narayanan , pp. 1-8 .
^ Stich .
^ Algoritmi precum recoacerea simulată au proprietăți teoretice puternice de convergență pentru programarea temperaturii la infinit. Cu toate acestea, o astfel de programare nu este fezabilă în practică.
^ ^a ^b ^c Boykov și colab. , pp. 1222-1239 .
^ ^a ^b Kolmogorov și Rother , pp. 1274-1279 .
^ Ishikawa , pp. 1362-1369 .
^ ^a ^b Kohli și colab. (2009) , pp. 1645-1656 .
^ ^a ^b Freedman și Drineas , pp. 939-946 .
^ Kohli și colab. (2008) , pp. 1-9.

Bibliografie

Yuri Boykov, Olga Veksler și Ramin Zabih, Minimizarea rapidă a energiei prin reduceri de grafic , în IEEE Tranzacții privind analiza modelelor și inteligența mașinilor , vol. 23, n. 11, IEEE, 2001, pp. 1222-1239.
Daniel Freedman și Petros Drineas, Minimizarea energiei prin tăieturi de grafice: soluționarea a ceea ce este posibil , IEEE Computer Society Conference on Computer Vision and Pattern Recognition , vol. 2, 2005.
Andrew V Goldberg și Robert E Tarjan, O nouă abordare a problemei fluxului maxim , în Jurnalul ACM (JACM) , vol. 35, nr. 4, ACM, 1988, pp. 921–940.
Hiroshi Ishikawa, Reducerea clicii de ordin superior fără variabile auxiliare , Conferința IEEE privind viziunea computerizată și recunoașterea modelelor , IEEE, 2014.
Li Hong și George Chen, potrivire stereo bazată pe segmente folosind tăieturi grafice , Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition , vol. 1, 2004.
Pushmeet Kohli, M. Pawan Kumar și Philip HS Torr, P ³ & Beyond: Mutarea algoritmilor pentru rezolvarea funcțiilor de ordine superioară , în IEEE Transactions on Pattern Analysis and Machine Intelligence , vol. 31, n. 9, IEEE, 2009.
Junhwan Kim, Vladimir Kolmogorov și Ramin Zabih, Corespondență vizuală utilizând minimizarea energiei și informații reciproce , Proceedings of the IX A International Conference on Computer Vision , 2003.
Pushmeet Kohli, Lubor Ladicky și PHS Torr, Grafice pentru reducerea potențialelor robuste de comandă superioară , Raport tehnic, Oxford Brookes University, 2008.
Vladimir Kolmogorov și Carsten Rother, Minimizarea funcțiilor nesubmodulare: o revizuire , în IEEE Transactions on Pattern Analysis and Machine Intelligence , vol. 29, nr. 7, IEEE, iulie 2007.
Vladimir Kolmogorov și Ramin Zabin, Ce funcții energetice pot fi reduse la minimum prin tăierea graficului? , în tranzacțiile IEEE privind analiza modelelor și inteligența mașinilor , vol. 26, n. 2, IEEE, 2004.
Herve Lombaert și Farida Cheriet, Dezactivarea și înregistrarea simultană a imaginilor folosind tăieturi de grafice: Aplicație la imagini medicale corupte , a 11-a Conferință internațională despre știința informației, procesarea semnalului și aplicațiile acestora , 2012.
Yi Peng, Li Chen, Fang-Xin Ou-Yang, Wei Chen și Jun-Hai Yong, JF-Cut: o abordare paralelă a graficului pentru imagini și video la scară largă , în IEEE Transactions on Image Processing , vol. 24, n. 2, IEEE, 2015, pp. 655-666.
Carsten Rother, Vladimir Kolmogorov și Andrew Blake, Grabcut: Extragere interactivă de prim-plan folosind tăieri grafice iterate , tranzacții ACM pe grafică , vol. 23, 2004.
Ronald WK Deci, Tommy WH Tang și Albert CS Chung, Înregistrarea non-rigidă a imaginilor cu rezonanță magnetică a creierului utilizând tăieturi grafice , în Pattern Recognition , vol. 44, nr. 10-11, Elsevier, 2011, pp. 2450–2467.
Timo Stich, Graph Cuts with CUDA ( PDF ), GPU Technology Conference , 2009.
Tommy WH Tang și Albert CS Chung, Înregistrare de imagini non-rigide folosind grafic-tăieturi , Conferința internațională despre calculul imaginilor medicale și intervenția asistată de computer , 2007.
Vibhav Vineet și PJ Narayanan, tăieturi CUDA: tăieri rapide ale graficelor pe GPU , IEEE Computer Society Conference on Computer Vision și Pattern Recognition Workshops , 2008.

linkuri externe

Implementarea în C ++ a mai multor algoritmi de optimizare a tăierilor grafice, de Vladimir Kolmogorov.
GCO , bibliotecă de optimizare a graficelor de Olga Veksler și Andrew Delong.

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

[peng-1] Peng și colab. , pp. 655-666 .

[grabcut-2] Rother și colab. , pp. 309-314 .

[lombaert-3] Lombaert și Cheriet , pp. 264-268 .

[so-4] Deci și colab. , pp. 2450-2467 .

[tang-5] Tang și Chung , pp. 916-924 .

[kim-6] Kim și colab. , pp. 1033-1040 .

[hong-7] Hong și Chen , pp. 74-81 .

[what-8] ^ ^a ^b ^c ^d ^e ^f Kolmogorov și Zabin , pp. 1645-1656 .

[fn_auxiliary_node-9] Este necesară adăugarea unui nod auxiliar, deoarece un grafic fără noduri auxiliare poate reprezenta doar interacțiuni binare între variabile.

[goldberg-10] Goldberg și Tarjan , pp. 921-940 .

[cudacuts-11] Vineet și Narayanan , pp. 1-8 .

[stich-12] Stich .

[annealing-13] Algoritmi precum recoacerea simulată au proprietăți teoretice puternice de convergență pentru programarea temperaturii la infinit. Cu toate acestea, o astfel de programare nu este fezabilă în practică.

[fast-14] Boykov și colab. , pp. 1222-1239 .

[review-15] Kolmogorov și Rother , pp. 1274-1279 .

[elc-16] Ishikawa , pp. 1362-1369 .

[p3-17] Kohli și colab. (2009) , pp. 1645-1656 .

[freedman-18] Freedman și Drineas , pp. 939-946 .

[kohli-19] Kohli și colab. (2008) , pp. 1-9.

[1]

[2]

[3 ]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]