Graph cut optimization is a combinatorial optimization method applicable to a family of functions of discrete variables, named after the concept of cut in the theory of flow networks. Thanks to the max-flow min-cut theorem, determining the minimum cut over a graph representing a flow network is equivalent to computing the maximum flow over the network. Given a pseudo-Boolean function , if it is possible to construct a flow network with positive weights such that * each cut of the network can be mapped to an assignment of variables to (and vice versa), and * the cost of equals (up to an additive constant) then it is possible to find the global optimum of in polynomial time by computing a minimum cut of the graph. The mapping between cuts and variable assignments is done by representing each variable with one node in the graph and, given a cut, each variable will have a value of 0 if the corresponding node belongs to the component connected to the source, or 1 if it belong to the component connected to the sink. Not all pseudo-Boolean functions can be represented by a flow network, and in the general case the global optimization problem is NP-hard. There exist sufficient conditions to characterise families of functions that can be optimised through graph cuts, such as submodular quadratic functions. Graph cut optimization can be extended to functions of discrete variables with a finite number of values, that can be approached with iterative algorithms with strong optimality properties, computing one graph cut at each iteration. Graph cut optimization is an important tool for inference over graphical models such as Markov random fields or conditional random fields, and it has applications in computer vision problems such as image segmentation, denoising, registration and stereo matching. (en)
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 , ad esempio e , e ha applicazioni in molti problemi di analisi digitale delle immagini e visione artificiale come segmentazione, eliminazione del rumore, registratura e . (it)
Graph cut optimization is a combinatorial optimization method applicable to a family of functions of discrete variables, named after the concept of cut in the theory of flow networks. Thanks to the max-flow min-cut theorem, determining the minimum cut over a graph representing a flow network is equivalent to computing the maximum flow over the network. Given a pseudo-Boolean function , if it is possible to construct a flow network with positive weights such that (en)
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. (it)