Graph cut optimization: Difference between revisions

Revision as of 15:03, 16 January 2019

Revision as of 15:06, 16 January 2019

Line 1:

{{Use mdy dates|date=January 2019}}

{{short description|Combinatorial optimization method for a family of functions of discrete variables}}

'''Graph cut optimization''' is a [[combinatorial optimization]] method applicable to a family of [[function (mathematics)|functionsfunction]]s of [[Continuous or discrete variable|discrete variablesvariable]]s, named after the concept of [[cut (graph theory)|cut]] in the theory of [[flow network]]s. Thanks to the [[max-flow min-cut theorem]], determining the [[minimum cut]] over a [[graph (discrete mathematics)|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 such that the variables of the function are represented by nodes in the network, and for each possible cut the value of the flow equals the value of the function when each variable assumes a binary value depending on the belonging of its representing node to the source or sink component after the cut, then it is possible to find the [[global optimum]] of such function in [[polynomial time]] by computing a minimum cut of the graph.

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 [[Pseudo-Boolean functionBoolean_function#Submodularity|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 field]]s or [[conditional random field]]s, and it has applications in [[computer vision]] problems such as [[image segmentation]],<ref name="peng" /><ref name="grabcut" /> [[image denoising|denoising]],<ref name="lombaert" /> [[image registration|registration]]<ref name="so" /><ref name="tang" /> and [[stereo cameras|stereo matching]].<ref name="kim" /><ref name="hong" />

Line 91 ⟶ 90:

S</math>, and <math>x_i = 1</math> for each <math>i</math> such that the corresponding node <math>v_i \in T</math>.

Max-flow algorithms such as Boykov–KolmogorovBoykov&ndash;Kolmogorov's are very efficient in practice for sequential computation, but they are difficult to parallelise, making them not suitable for [[distributed computing]] applications and preventing them from exploiting the potential of modern [[Central Processing Unit|CPUsCPU]]s. Parallel max-flow algorithms were developed, such as [[Push–relabel maximum flow algorithm|push-relabel]]<ref name="goldberg" /> and [[jump-flood algorithm|jump-flood]],<ref name="peng" /> that can also take advantage of hardware acceleration in [[GPGPU]] implementations.<ref name="cudacuts" /><ref name="peng" /><ref name="stich" />

== Functions of discrete variables with more than two values ==

Line 147 ⟶ 146:

== References ==

<references />

<ref name="cudacuts">Vineet and Narayanan (2008).</ref>

<ref name="elc">Ishikawa (2014).</ref>

Line 165 ⟶ 164:

<ref name="tang">Tang and Chung (2007).</ref>

<ref name="what">Kolmogorov and Zabin (2004).</ref>

<references /references>

* {{cite journal|title=Fast approximate energy minimization via graph cuts|year=2001|journal=IEEE Transactions on pattern analysis and machine intelligence|volume=23|issue=11|publisher=IEEE|last1=Boykov|first1=Yuri|last2=Veksler|first2=Olga|last3=Zabih|first3=Ramin|pages=1222–1239}}

Line 189 ⟶ 188:

<ref name="annealing">Algorithms such as [[simulated annealing]] have strong theoretical convergence properties for some scheduling of the temperature to infinity. Such scheduling cannot be realised in practice.</ref>

<ref name="fn auxiliary node">Adding one node is necessary, graphs without auxiliary nodes can only represent binary interactions between variables.</ref>

<references /references>

== External links ==