Graph cut optimization: Difference between revisions

Revision as of 21:29, 16 January 2019

Revision as of 03:27, 19 January 2019

Line 2:

'''Graph cut optimization''' is a [[combinatorial optimization]] method applicable to a family of [[function (mathematics)|function]]s of [[Continuous or discrete variable|discrete variable]]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 65:

- p x_i x_j x_k

</math>

[[File:Graph cut ternary.svg|thumb|upright=2|Example of a graph representing the ternary term <math>p x_i x_j x_k</math> when <math>p > 0</math> (left) and when <math>p < 0</math> (right).]]

Line 135 ⟶ 134:

{{see also|Quadratic pseudo-Boolean optimization}}

Generally speaking, the problem of optimizing a non-submodular pseudo-Boolean function is [[NP-hard]] and cannot be solved in polynomial time with a simple graph cut. The simplest approach is to approximate the function with a similar but submodular one, for instance truncating all non-submodular terms or replacing them with similar submodular expressions. Such approach is generally sub-optimal, and it produces acceptable results only if the number of non-submodular terms is relatively small. <ref name="review" />

In case of quadratic non-submodular functions, it is possible to compute in polynomial time a partial solution using algorithms such as [[QPBO]].<ref name="review" /> Higher-order functions can be reduced in polynomial time to a quadratic form that can be optimised with QPBO.<ref name="elc" />

Line 194 ⟶ 193:

*[https://github.com/nsubtil/gco-v3.0 GCO], graph cut optimization library by Olga Veksler and Andrew Delong.

{{DEFAULTSORT|:Graph cut optimization}}

[[Category:Combinatorial optimization]]

[[Category:Computer vision]]