Graph cut optimization: Difference between revisions

Revision as of 20:28, 24 January 2019

Revision as of 10:02, 27 January 2019

Line 125:

<math>\text{exit} := 0</math>

In both cases, the optimization problem in the innermost loop can be solved exactly and efficiently with a graph cut. Both algorithms terminate certainly in a finite number of iterations of the outer loop, and in practice such number is small, with most of the improvement happening at the first iteration. The algorithms can generate different solutions depending ofon 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.<ref name="fast" />

The solution generated by such algorithms is not necessarily a global optimum, but it has strong guarantees of optimality. If <math>S(x_i, x_j)</math> is a [[metric (mathematics)|metric]] and <math>\mathbf{x}</math> is a solution generated by the <math>\alpha</math>-expansion algorithm, or if <math>S(x_i, x_j)</math> is a [[semimetric]] and <math>\mathbf{x}</math> is a solution generated by the <math>\alpha\beta</math>-swap algorithm, then <math>f(\mathbf{x})</math> lies within a known and constant factor from the global minimum <math>f(\mathbf{x}^*)</math>:<ref name="fast" />