Graph cut

Graph cut è un metodo di ottimizzazione applicabile a un'ampia famiglia di funzioni di variabili discrete, che deve il suo nome al fatto di essere basato sulla teoria delle reti di flusso. Grazie al teorema del flusso massimo e taglio minimo, determinare il taglio minimo su un grafo rappresentante una rete di flusso è equivalente a calcolare il flusso massimo sulla rete stessa. Data una funzione pseudo-booleana, se è possibile costruire una rete di flusso tale che per ogni possibile taglio il valore del flusso tagliato corrisponda a un assegnamento di variabili alla funzione e viceversa, è possibile trovare il minimo globale della funzione in tempo polinomiale calcolando un taglio minimo del grafo che rappresenta tale rete di flusso.

Non tutte le funzioni pseudo-booleane sono rappresentabili tramite una rete di flusso, e la ricerca del minimo globale nel caso generale è un problema NP-hard. Esistono condizioni sufficienti che caratterizzano famiglie di funzioni ottimizzabili tramite graph cut in tempo polinomiale, come ad esempio le funzioni quadratiche submodulari. È possibile estendere il metodo a funzioni a variabili discrete con più di due valori tramite algoritmi iterativi approssimati, con forti garanzie di ottimalità del risultato, che calcolano un taglio minimo a ogni iterazione.

L'ottimizzazione tramite graph cut è uno strumento utile per l'inferenza su modelli grafici, ad esempio campi di Markov casuali e campi condizionali casuali, e ha applicazioni in molti problemi di analisi digitale delle immagini e visione artificiale come segmentazione, eliminazione del rumore, registratura e stereo matching.

Rappresentabilità

Una funzione pseudo-booleana $f:\{0,1\}^{n}\to \mathbb {R}$ è detta rappresentabile tramite un grafo $G$ se esiste un grafo a pesi non negativi $G=(V,E)$ con nodi terminali sorgente $s$ e pozzo $t$ e un sottinsieme di vertici $V_{0}=\{v_{1},\dots ,v_{n}\}\subset V-\{s,t\}$ tale che, per ogni tupla di valori $(x_{1},\dots ,x_{n})\in \{0,1\}^{n}$ assegnati alle variabili, $f(x_{1},\dots ,x_{n})$ è uguale (a meno di una costante) al valore del flusso determinato da un taglio minimo $C=(S,T)$ del grafo $G$ tale che $v_{i}\in S$ se $x_{i}=0$ e $v_{i}\in T$ se $x_{i}=1$.

È possibile classificare le funzioni pseudo-booleane in base al loro ordine, determinato dal numero massimo di variabili contenute in un singolo termine. Tutte le funzioni di primo ordine sono sempre rappresentabili. Le funzioni quadratiche, che hanno forma

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

sono rappresentabili se e solo se soddisfano una condizione detta di submodularità, ovvero se per ogni termine $w_{ij}$ della parte quadratica si verifica che

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

Le funzioni cubiche, che hanno forma

$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})$

sono rappresentabili se e solo se sono regolari, ovvero tutte le possibili proiezioni in due variabili della funzione (ottenute fissando una delle tre variabili) sono submodulari. Per funzioni di ordine superiore, la regolarità è una condizione necessaria per la rappresentabilità.

Costruzione del grafo

La costruzione del grafo di una funzione rappresentabile è semplificata dal fatto che la somma di due funzioni rappresentabili $f'$ e $f''$ è a sua volta rappresentabile, e il corrispondente grafo $G=(V'\cup V'',E'\cup E'')$ è dato dall'unione dei rispettivi grafi $G'=(V',E')$ e $G''=(V'',E'')$. Tale teorema consente di costruire grafi separati per ogni termine, che possono essere uniti per ottenere il grafo dell'intera funzione.

Il grafo associato ad una funzione quadratica a $n$ variabili contiene $n+2$ nodi, due dei quali rappresentano la sorgente e il pozzo, e i restanti rappresentano le variabili. Per funzioni di ordine superiore, il grafo contiene nodi ausiliari che permettono di rappresentare interazioni di ordine più elevato.

Termini unari

Un termine unario $w_{i}$ dipendente da una sola variabile $x_{i}$ può essere rappresentato da un grafo con un nodo non terminale $v_{i}$ e un arco $s\rightarrow v_{i}$ con peso $w_{i}(1)-w_{i}(0)$ se $w_{i}(1)\geq w_{i}(0)$, o $v_{i}\rightarrow t$ con peso $w_{i}(0)-w_{i}(1)$ se $w_{i}(1)<w_{i}(0)$.

Termini binari

Esempio di grafo rappresentante un termine quadratico $w_{ij}(x_{i},x_{j})$ nel caso in cui $w_{ij}(1,0)-w_{ij}(0,0)>0$ e $w_{ij}(1,1)-w_{ij}(1,0)<0$.

Un termine quadratico (o binario) $w_{ij}$ può essere rappresentato da un grafo contenente due nodi non terminali $v_{i}$ e $v_{j}$. Il termine può essere riscritto equivalentemente come

$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)$

con

${\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}}$

In questa espressione, il primo termine è una costante e non è rappresentato da alcun vertice, i due termini successivi dipendono da una variabile e sono dunque rappresentati da un arco, nella maniera descritta in precedenza per i termini unari, infine il quarto termine è rappresentato da un arco $v_{i}\rightarrow v_{j}$ con peso $w_{ij}(0,1)+w_{ij}(1,0)-w_{ij}(0,0)-w_{ij}(1,1)$ (la condizione di submodularità garantisce che il peso sia non negativo).

Termini ternari

Un termine cubico (o ternario) $w_{ijk}$ può essere rappresentato da un grafo con quattro nodi non terminali, tre dei quali $v_{i}$, $v_{j}$ e $v_{k}$ sono associati alle tre variabili, con l'aggiunta di un quarto nodo ausiliario $v_{ijk}$. Un generico termine ternario può essere riscritto come somma di una costante, tre termini unari, tre termini binari e un termine ternario in forma semplificata. Si possono verificare due casi diversi a seconda del segno della quantità $p=w_{ijk}(0,0,0)+w_{ijk}(0,1,1)+w_{ijk}(1,0,1)+w_{ijk}(1,1,0)$. Se $p>0$ si ha

$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}$

Esempio di grafo rappresentante il termine ternario $px_{i}x_{j}x_{k}$ nel caso in cui $p>0$ (sinistra) e $p<0$ (destra).

con

${\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}}$

Se $p<0$ la costruzione è analoga ma le variabili assumeranno valore opposto. Se la funzione di partenza è regolare allora tutte le sue proiezioni in due variabili sono submodulari, garantendo che $p_{23}$, $p_{31}$ e $p_{12}$ siano positivi e che dunque tutti i termini che compongono la nuova rappresentazione siano submodulari.

In questa decomposizione, i termini costante, unari e binari possono essere rappresentati come visto in precedenza. Se $p>0$ l'ultimo termine ternario può essere rappresentato da un grafo con quattro archi $v_{i}\rightarrow v_{ijk}$, $v_{j}\rightarrow v_{ijk}$, $v_{k}\rightarrow v_{ijk}$, $v_{ijk}\rightarrow t$ tutti con peso $p$, mentre se $p<0$ il termine può essere rappresentato da quattro archi $v_{ijk}\rightarrow v_{i}$, $v_{ijk}\rightarrow v_{j}$, $v_{ijk}\rightarrow v_{k}$, $s\rightarrow v_{ijk}$ con peso $-p$.

Calcolo del taglio minimo

Una volta costruito il grafo rappresentante una funzione pseudo-booleana, è possibile calcolare il taglio minimo usando uno tra i vari algoritmi per reti di flusso, come quelli di Ford-Fulkerson, Edmonds-Karp o Boykov-Kolmogorov. Il risultato è una partizione del grafo in due componenti connesse $S$ e $T$ tali che $s\in S$ e $t\in T$, e il minimo globale della funzione è raggiunto quando $x_{i}=0$ per ogni $i$ tale che il corrispondente nodo $v_{i}\in S$, e $x_{i}=1$ per ogni $i$ tale che il corrispondente nodo $v_{i}\in T$.

Algoritmi di flusso massimo come quello di Boykov-Kolmogorov sono molto efficienti in pratica per il calcolo del taglio minimo in maniera sequenziale, ma hanno lo svantaggio di non essere facilmente parallelizzabili, fatto che impedisce di sfruttare l'inerente parallelismo dell'hardware moderno e ne limita l'uso in applicazioni di calcolo distribuito. Diversi algoritmi paralleli per il calcolo del flusso massimo sono stati sviluppati, tra i quali push-relabel e jump-flood, che possono anche trarre vantaggio dell'accelerazione hardware in implementazioni GPGPU.

Funzioni di variabili discrete con più di due valori

La costruzione precedente permette l'ottimizzazione globale di funzioni pseudo-booleane, ma è possibile estendere l'ottimizzazione graph cut a funzioni quadratiche di variabili discrete con un numero finito di valori nella forma

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

con $E\subseteq V\times V$ e $x_{i}\in \Lambda =\{1,\dots ,k\}$. La funzione $D(x_{i})$ rappresenta il contributo unario delle singole variabili (spesso riferito come data term), mentre la funzione $S(x_{i},x_{j})$ rappresenta l'interazione binaria fra le variabili (smoothness term). In generale, l'ottimizzazione globale di tali funzioni è un problema NP-hard, e metodi di ottimizzazione stocastica come ad esempio simulated annealing sono sensibili a minimi locali e in pratica possono generare risultati arbitrariamente sub-ottimali. Tramite graph cut è possibile costruire algoritmi di move-making che consentono di ottenere in tempo polinomiale un minimo locale con forti proprietà di ottimalità per un'ampia famiglia di funzioni quadratiche di interesse pratico (nel caso l'interazione binaria $S(x_{i},x_{j})$ sia una metrica o semimetrica), tale che il valore della funzione nella soluzione si trova entro un fattore noto dal minimo globale.

Data una funzione $f:\Lambda ^{n}\to \mathbb {R}$ con $\Lambda =\{1,\dots ,k\}$, e un certo assegnamento di valori $\mathbf {x} =(x_{1},\dots ,x_{n})\in \Lambda ^{n}$ alle variabili, è possibile associare ogni assegnamento $\mathbf {x}$ con una partizione $P=\{P_{l}|l\in \Lambda \}$ dell'insieme delle variabili, tale che $P_{l}=\{x_{i}|x_{i}=l\in \Lambda \}$. Dati due diversi assegnamenti di variabili $P$ e $P'$ e un valore $\alpha \in \Lambda$, una mossa che trasforma $P$ in $P'$ è detta $\alpha$-expansion se $P_{\alpha }\subset P'_{\alpha }$ e $P'_{l}\subset P_{l}\;\forall l\in \Lambda -\{\alpha \}$. Data una coppia di valori $\alpha$ e $\beta$, una mossa è detta $\alpha \beta$-swap se $P_{l}=P'_{l}\;\forall l\in \Lambda -\{\alpha ,\beta \}$. Intuitivamente, una mossa di $\alpha$-expansion a partire da $\mathbf {x}$ consiste nell'assegnare il valore $\alpha$ ad alcune variabili che hanno un valore differente in $\mathbf {x}$. Una mossa di $\alpha \beta$-swap consiste nell'assegnare $\alpha$ ad alcune variabili che in $\mathbf {x}$ hanno valore $\beta$ e viceversa.

Ad ogni iterazione, l'algoritmo di $\alpha$-expansion calcola, per ogni possibile valore $\alpha$, il minimo della funzione fra tutti gli assegnamenti $\mathrm {A} (\mathbf {x} )$ che possono essere ottenuti tramite una mossa di $\alpha$-expansion a partire dalla soluzione corrente $\mathbf {x}$, e lo assegna come nuovo valore della soluzione.

$\mathbf {x} :={\text{valore arbitrario in }}\Lambda ^{n}$
${\text{exit}}:=0$
while ${\text{exit}}\neq 1$:
    ${\text{exit}}=1$
    foreach $\alpha \in \Lambda$:
        $\mathbf {\hat {x}} :=\arg \min _{\mathbf {y} \in \mathrm {A} (\mathbf {x} )}f(\mathbf {y} )$
        if $f(\mathbf {\hat {x}} )<\mathbf {x}$:
            $\mathbf {x} =\mathbf {\hat {x}}$
            ${\text{exit}}:=0$

L'algoritmo di $\alpha \beta$-swap è simile, ma cerca il minimo tra tutti gli assegnamenti $\mathrm {A} \mathrm {B} (\mathbf {x} )$ ottenibili tramite una mossa di $\alpha \beta$-swap a partire da $\mathbf {x}$.

$\mathbf {x} :={\text{valore arbitrario in }}\Lambda ^{n}$
${\text{exit}}:=0$
while ${\text{exit}}\neq 1$:
    ${\text{exit}}=1$
    foreach $(\alpha ,\beta )\in \Lambda ^{2}$:
        $\mathbf {\hat {x}} :=\arg \min _{\mathbf {y} \in \mathrm {A} \mathrm {B} (\mathbf {x} )}f(\mathbf {y} )$
        if $f(\mathbf {\hat {x}} )<\mathbf {x}$:
            $\mathbf {x} =\mathbf {\hat {x}}$
            ${\text{exit}}:=0$

In entrambi i casi, il problema di minimizzazione contenuto nel ciclo più interno può essere risolto esattamente ed efficientement tramite graph cut. Entrambi gli algoritmi terminano certamente in un numero finito di iterazioni, ed in pratica il numero di iterazioni è piccolo e la maggior parte del miglioramento della soluzione avviene alla prima iterazione. Gli algoritmi possono produrre risultati diversi a seconda del valore iniziale assegnato alla soluzione, ma in pratica sono robusti rispetto all'inizializzazione e partire da una soluzione iniziale con tutte le variabili assegnate ad uno stesso valore arbitrario è generalmente sufficiente per ottenere buoni risultati.

La soluzione prodotta da tali algoritmi non è necessariamente un punto di ottimo globale, ma ha comunque forti garanzie di ottimalità. Se $S(x_{i},x_{j})$ è una metrica e $\mathbf {x}$ è una soluzione generata dall'algoritmo di $\alpha$-expansion, oppure se $S(x_{i},x_{j})$ è una semimetrica e $\mathbf {x}$ è una soluzione generata dall'algoritmo di $\alpha \beta$-swap, allora $f(\mathbf {x} )$ si trova entro un fattore noto e costante dal minimo globale $f(\mathbf {x} ^{*})$:

$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} ^{*}).$

Funzioni non submodulari

In generale, il problema di minimizzare una funzione pseudo-booleana non submodulare è NP-hard e non può sempre essere risolto in tempo polinomiale con un semplice graph cut. L'approccio pratico più semplice è quello di approssimare la funzione obiettivo con una funzione simile ma submodulare, ad esempio troncando tutti i termini non submodulari o sostituendoli con espressioni simili ma submodulari. Tuttavia, tale approccio produce in genere risultati sub-ottimali, la cui qualità è accettabile solo se il numero di termini non submodulari è relativamente piccolo.

Nel caso di funzioni non-submodulari quadratiche, è possibile ottenere in tempo polinomiale una soluzione parziale tramite algoritmi come QPBO. Funzioni di ordine superiore possono essere ridotte in tempo polinomiale in forma quadratica ottimizzabile tramite QPBO.

Funzioni di ordine superiore

Molti risultati sono concentrati sull'ottimizzazione di funzioni quadratiche, che sono state studiate e caratterizzate in maniera approfondita, ma condizioni più generali sono state sviluppate anche per funzioni di ordine superiore. Mentre infatti le funzioni quadratiche permettono di modellare efficacemente molti problemi, sono tuttavia limitate dal fatto di poter esprimere solo interazioni binarie tra le variabili. La possibilità di integrare interazioni di ordine superiore in un modello in alcuni contesti permette di catturare più efficacemente la natura del problema e fornisce risultati di qualità più elevata. Un esempio sono applicazioni di elaborazione digitale delle immagini, dove ogni variabile rappresenta un pixel o voxel dell'immagine e interazioni di ordine superiore possono catturare ad esempio informazioni sulle texture, che sarebbero difficili o impossibili da incorporare in un modello espresso da una funzione quadratica.

Condizioni sufficienti analoghe alla submodularità sono state studiate per caratterizzare funzioni pseudo-booleane di ordine superiore che possono essere ottimizzate in tempo polinomiale, ed esistono estensioni degli algoritmi di $\alpha$-expansion e $\alpha \beta$-swap per alcune famiglie di funzioni di ordine superiore. Il problema è comunque NP-hard nel caso generale, e metodi approssimati sono stati sviluppati per l'ottimizzazione efficiente di funzioni che non soddisfano tali condizioni.

Bibliografia

• Yuri Boykov, Olga Veksler e Ramin Zabih, Fast approximate energy minimization via graph cuts, in IEEE Transactions on pattern analysis and machine intelligence, vol. 23, n. 11, IEEE, 2001, pp. 1222–1239.
• Daniel Freedman e Petros Drineas, Energy minimization via graph cuts: Settling what is possible, IEEE Computer Society Conference on Computer Vision and Pattern Recognition, vol. 2, 2005.
• Andrew V Goldberg e Robert E Tarjan, A new approach to the maximum-flow problem, in Journal of the ACM (JACM), vol. 35, n. 4, ACM, 1988, pp. 921–940.
• Hiroshi Ishikawa, Higher-Order Clique Reduction Without Auxiliary Variables, IEEE Conference on Computer Vision and Pattern Recognition, IEEE, 2014.
• Li Hong e George Chen, Segment-based stereo matching using graph cuts, Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, vol. 1, 2004.
• Pushmeet Kohli, M. Pawan Kumar e Philip H.S. Torr, P³ & Beyond: Move Making Algorithms for Solving Higher Order Functions, in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 31, n. 9, IEEE, 2009.
• Junhwan Kim, Vladimir Kolmogorov e Ramin Zabih, Visual correspondence using energy minimization and mutual information, Proceedings of the Ninth IEEE International Conference on Computer Vision, 2003.
• Pushmeet Kohli, Lubor Ladicky e PHS Torr, Graph cuts for minimizing robust higher order potentials, Technical report, Oxford Brookes University, 2008.
• Vladimir Kolmogorov e Carsten Rother, Minimizing Nonsubmodular Functions: A Review, in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 29, n. 7, IEEE, luglio 2007.
• Vladimir Kolmogorov e Ramin Zabin, What energy functions can be minimized via graph cuts?, in IEEE transactions on pattern analysis and machine intelligence, vol. 26, n. 2, IEEE, 2004.
• Herve Lombaert e Farida Cheriet, Simultaneous image de-noising and registration using graph cuts: Application to corrupted medical images, 11th International Conference on Information Science, Signal Processing and their Applications, 2012.
• Yi Peng, Li Chen, Fang-Xin Ou-Yang, Wei Chen e Jun-Hai Yong, JF-Cut: a parallel graph cut approach for large-scale image and video, in IEEE Transactions on Image Processing, vol. 24, n. 2, IEEE, 2015, pp. 655–666.
• Carsten Rother, Vladimir Kolmogorov e Andrew Blake, Grabcut: Interactive foreground extraction using iterated graph cuts, ACM transactions on graphics, vol. 23, 2004.
• Ronald WK So, Tommy WH Tang e Albert CS Chung, Non-rigid image registration of brain magnetic resonance images using graph-cuts, in Pattern Recognition, vol. 44, n. 10-11, Elsevier, 2011, pp. 2450–2467.
• Timo Stich, Graph Cuts with CUDA (PDF), GPU Technology Conference, 2009.
• Tommy WH Tang e Albert CS Chung, Non-rigid image registration using graph-cuts, International Conference on Medical Image Computing and Computer-Assisted Intervention, 2007.
• Vibhav Vineet e PJ Narayanan, CUDA cuts: Fast graph cuts on the GPU, IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops, 2008.

Collegamenti esterni

• Implementazione in C++ di diversi algoritmi di ottimizzazione graph cut, a cura di Vladimir Kolmogorov.
• GCO, libreria di ottimizzazione graph cut a cura di Olga Veksler e Andrew Delong.