Graph cut optimization
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.
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.
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,[1][2] denoising,[3] registration[4][5] and stereo matching.
equals (up to a constant) the value of the flow determined by a minimum cut
[8] It is possible to classify pseudo-Boolean functions according to their order, determined by the maximum number of variables contributing to each single term.
All first order functions, where each term depends upon at most one variable, are always representable.
the following condition is satisfied Cubic functions are representable if and only if they are regular, i.e. all possible binary projections to two variables, obtained by fixing the value of the remaining variable, are submodular.
In this decomposition, the constant, unary and binary terms can be represented as shown in the previous sections.
Max-flow algorithms such as Boykov–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 CPUs.
Parallel max-flow algorithms were developed, such as push-relabel[9] and jump-flood,[1] that can also take advantage of hardware acceleration in GPGPU implementations.
[10][1][11] The previous construction allows global optimization of pseudo-Boolean functions only, but it can be extended to quadratic functions of discrete variables with a finite number of values, in the form where
represents the unary contribution of each variable (often referred as data term), while the function
In the general case, optimization of such functions is a NP-hard problem, and stochastic optimization methods such as simulated annealing are sensitive to local minima and in practice they can generate arbitrarily sub-optimal results.
[note 2] With graph cuts it is possible to construct move-making algorithms that allow to reach in polynomial time a local minima with strong optimality properties for a wide family of quadratic functions of practical interest (when the binary interaction
is a metric or a semimetric), such that the value of the function in the solution lies within a constant and known factor from the global optimum.
In both cases, the optimization problem in the innermost loop can be solved exactly and efficiently with a graph cut.
The algorithms can generate different solutions depending on the initial guess, but in practice they are robust with respect to initialisation, and starting with a point where all variables are assigned to the same random value is usually sufficient to produce good quality results.
[12] The solution generated by such algorithms is not necessarily a global optimum, but it has strong guarantees of optimality.
:[12] 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.
Such approach is generally sub-optimal, and it produces acceptable results only if the number of non-submodular terms is relatively small.
[13] In case of quadratic non-submodular functions, it is possible to compute in polynomial time a partial solution using algorithms such as QPBO.
[13] Higher-order functions can be reduced in polynomial time to a quadratic form that can be optimised with QPBO.
While quadratic functions can indeed model many problems of practical interest, they are limited by the fact they can represent only binary interactions between variables.
The possibility to capture higher-order interactions allows to better capture the nature of the problem and it can provide higher quality results that could be difficult to achieve with quadratic models.
For instance in computer vision applications, where each variable represents a pixel or voxel of the image, higher-order interactions can be used to model texture information, that would be difficult to capture using only quadratic functions.
[15] Sufficient conditions analogous to submodularity were developed to characterise higher-order pseudo-Boolean functions that can be optimised in polynomial time,[16] and there exists algorithms analogous to
[15] The problem is NP-hard in the general case, and approximate methods were developed for fast optimization of functions that do not satisfy such conditions.
