Content deleted Content added
fix citation and sentence not connected with the rest of the section |
Sun Creator (talk | contribs) m General fixes, typo(s) fixed: dependant upon → dependent upon |
||
Line 24:
* ''Partial optimality'': if <math>f</math> is submodular, then QPBO produces a global minimum exactly, equivalent to [[graph cut optimization|graph cut]], and all variables have a non-undefined value; if submodularity is not satisfied, the result will be a partial solution <math>\mathbf{x}</math> where a subset <math>\hat{V} \subseteq V</math> of the variables have a non-undefined value. A partial solution is always part of a global solution, i.e. there exists a global minimum point <math>\mathbf{x^*}</math> for <math>f</math> such that <math>x_i = x_i^*</math> for each <math>i \in \hat{V}</math>.
* ''Persistence'': given a solution <math>\mathbf{x}</math> generated by QPBO and an arbitrary assignment of values <math>\mathbf{y}</math> to the variables, if a new solution <math>\hat{\mathbf{y}}</math> is constructed by replacing <math>y_i</math> with <math>x_i</math> for each <math>i \in \hat{V}</math>, then <math>f(\hat{\mathbf{y}}) \le f(\mathbf{y})</math>.<ref name="review" />
Line 44 ⟶ 43:
Once the minimum cut is known, each variable receives a value depending upon the position of its corresponding nodes <math>p</math> and <math>p'</math>: if <math>p</math> belongs to the connected component containing the source and <math>p'</math> belongs to the connected component containing the sink then the variable will have value of 0. Vice versa, if <math>p</math> belongs to the connected component containing the sink and <math>p'</math> to the one containing the source, then the variable will have value of 1. If both nodes <math>p</math> and <math>p'</math> belong to the same connected component, then the value of the variable will be undefined.<ref name="rother" />
The way undefined variables can be handled is
== Higher order terms ==
|