Quadratic pseudo-Boolean optimisation (QPBO) is a combinatorial optimization method for minimizing quadratic pseudo-Boolean functions in the form
f ( x ) = w 0 + ∑ p ∈ V w p ( x p ) + ∑ ( p , q ) ∈ E w p q ( x p , x q ) {\displaystyle f(\mathbf {x} )=w_{0}+\sum _{p\in V}w_{p}(x_{p})+\sum _{(p,q)\in E}w_{pq}(x_{p},x_{q})}
in the binary variables x p ∈ { 0 , 1 } ∀ p ∈ V = { 1 , … , n } {\displaystyle x_{p}\in \{0,1\}\;\forall p\in V=\{1,\dots ,n\}} , with E ⊆ V × V {\displaystyle E\subseteq V\times V} . If f {\displaystyle f} is submodular then QPBO produces a global optimum equivalently to graph cut optimization, while if f {\displaystyle f} contains non-submodular terms then the algorithm produces a partial solution with specific optimality properties, in both cases in polynomial time. QPBO is a useful tool for inference on Markov random fields and conditional random fields, and has applications in computer vision problems such as image segmentation and stereo matching.
Optimization of non-submodular functions If the coefficients w p q {\displaystyle w_{pq}} of the quadratic terms satisfy the submodularity condition
w p q ( 0 , 0 ) + w p q ( 1 , 1 ) ≤ w p q ( 0 , 1 ) + w p q ( 1 , 0 ) {\displaystyle w_{pq}(0,0)+w_{pq}(1,1)\leq w_{pq}(0,1)+w_{pq}(1,0)}
then the function can be efficiently optimised with graph cut optimization. It is indeed possible to represent it with a non-negative weighted graph, and the global minimum can be found in polynomial time by computing a minimum cut of the graph, which can be computed with algorithms such as Ford–Fulkerson, Edmonds–Karp, and Boykov–Kolmogorov's. If the function is not submodular, then the problem is NP-hard in the general case and it is not always possible to solve it exactly in polynomial time. It is possible to replace the target function with a similar but submodular approximation, e.g. by removing all non-submodular terms or replacing them with submodular approximations, but such approach is generally sub-optimal and it produces satisfying results only if the number of non-submodular terms is relatively small. QPBO builds an extended graph, introducing a set of auxiliary variables ideally equivalent to the negation of the variables in the problem. If the nodes in the graph associated to a variable (representing the variable itself and its negation) are separated by the minimum cut of the graph in two different connected components, then the optimal value for such variable is well defined, otherwise it is not possible to infer it. Such method produces results generally superior to submodular approximations of the target function.
Properties QPBO produces a solution where each variable assumes one of three possible values: true, false, and undefined, noted in the following as 1, 0, and ∅ {\displaystyle \emptyset } respectively. The solution has the following two properties.
… excerpt ends here. Continue reading the full article.
