Content deleted Content added
→Higher order terms: cn sentence that does not contribute |
No edit summary |
||
| (One intermediate revision by one other user not shown) | |||
Line 1:
{{short description|Combinatorial optimization method for pseudo-Boolean functions}}
'''Quadratic pseudo-Boolean optimisation''' ('''QPBO''') is a [[combinatorial optimization]] method for minimizing quadratic [[pseudo-Boolean function]]s in the form
:<math> f(\mathbf{x}) = w_0 + \sum_{p \in V} w_p(x_p) + \sum_{(p, q) \in E} w_{pq}(x_p, x_q) </math>
in the [[binary data|binary variables]] <math>x_p \in \{0, 1\} \; \forall p \in V = \{1, \dots, n\}</math>, with <math>E \subseteq V \times V</math>. If <math>f</math> is [[Pseudo-Boolean_function#Submodularity|submodular]] then QPBO produces a global optimum equivalently to [[graph cut optimization]], while if <math>f</math> contains non-submodular terms then the algorithm produces a partial solution with specific optimality properties, in both cases in [[polynomial time]].<ref name="review" />
QPBO is a useful tool for inference on [[Markov random field]]s and [[conditional random field]]s, and has applications in [[computer vision]] problems such as [[image segmentation]] and [[stereo cameras|stereo matching]].<ref name="rother" />
| |||