Quadratic pseudo-Boolean optimization: Difference between revisions

Revision as of 18:40, 15 November 2020

Revision as of 18:41, 15 November 2020

Line 4:

:<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 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 [[https://en.wikipedia.org/wiki/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" />