Graph cut optimization

Graph cut optimization is a <a href="/facts/Combinatorial_optimization/PTcloS79">combinatorial optimization</a> method applicable to a family of <a href="/facts/Function_(mathematics)/CdReEKCh">functions</a> of <a href="/facts/Continuous_or_discrete_variable/TWl5feEw">discrete variables</a>, named after the concept of <a href="/facts/Cut_(graph_theory)/1lKf2IIW">cut</a> in the theory of <a href="/facts/Flow_network/k0LCoRwD">flow networks</a>. Thanks to the <a href="/facts/Max-flow_min-cut_theorem/qrXp2ut7">max-flow min-cut theorem</a>, determining the <a href="/facts/Minimum_cut/xWTNp1hN">minimum cut</a> over a <a href="/facts/Graph_(discrete_mathematics)/kw3eIBUe">graph</a> representing a flow network is equivalent to computing the <a href="/facts/Maximum_flow/aSal0FGF">maximum flow</a> over the network. Given a <a href="/facts/Pseudo-Boolean_function/U0zWqAL8">pseudo-Boolean function</a> 
 
 
 
 f
 
 
 {\displaystyle f}
 
, if it is possible to construct a flow network with positive weights such that

<ul><li>each cut 
 
 
 
 C
 
 
 {\displaystyle C}
 
 of the network can be mapped to an assignment of variables 
 
 
 
 
 x
 
 
 
 {\displaystyle \mathbf {x} }
 
 to 
 
 
 
 f
 
 
 {\displaystyle f}
 
 (and vice versa), and</li>
<li>the cost of 
 
 
 
 C
 
 
 {\displaystyle C}
 
 equals 
 
 
 
 f
 (
 
 x
 
 )
 
 
 {\displaystyle f(\mathbf {x} )}
 
 (up to an additive constant)</li></ul>
then it is possible to find the <a href="/facts/Global_optimum/ADlgnyzV">global optimum</a> of 
 
 
 
 f
 
 
 {\displaystyle f}
 
 in <a href="/facts/Polynomial_time/77T62gmf">polynomial time</a> 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 <a href="/facts/NP-hard/mQeNPv4R">NP-hard</a>. There exist sufficient conditions to characterise families of functions that can be optimised through graph cuts, such as <a href="/facts/Pseudo-Boolean_function/U0zWqAL8">submodular quadratic functions</a>. 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 <a href="/facts/Graphical_models/XxfmKhmM">graphical models</a> such as <a href="/facts/Markov_random_field/DJazwaeP">Markov random fields</a> or <a href="/facts/Conditional_random_field/TNuLaGzM">conditional random fields</a>, and it has <a href="/facts/Graph_cuts_in_computer_vision/czXstoTB">applications in computer vision problems</a> such as <a href="/facts/Image_segmentation/jofAhbxa">image segmentation</a>, <a href="/facts/Image_denoising/9jrDQnAN">denoising</a>, <a href="/facts/Image_registration/y2KUwdRL">registration</a> and <a href="/facts/Stereo_cameras/gyYagbWd">stereo matching</a>.

Graph cut optimization open-in-new

Graph cut optimization