Content deleted Content added
repetition |
→Functions of discrete variables with more than two values: disambiguation |
||
Line 97:
:<math>f(\mathbf{x}) = \sum_{i \in V} D(x_i) + \sum_{(i, j) \in E} S(x_i, x_j)</math>
where <math>E \subseteq V \times V</math> and <math>x_i \in \Lambda = \{1, \dots, k\}</math>. The function <math>D(x_i)</math> represents the unary contribution of each variable (often referred as ''data term''), while the function <math>S(x_i, x_j)</math> represents binary interactions between variables (''smoothness term''). In the general case, optimization of such functions is a [[NP-hard]] problem, and [[stochastic optimization]] methods such as [[simulated annealing]] are sensitive to [[local minima]] and in practice they can generate arbitrarily sub-optimal results.<ref name="annealing" group="note" /> With graph cuts it is possible to construct move-making algorithms that allow to reach in polynomial time a local minima with strong optimality properties for a wide family of quadratic functions of practical interest (when the binary interaction <math>S(x_i, x_j)</math> is a [[metric (mathematics)|metric]] or a [[semimetric]]), such that the value of the function in the solution lies within a constant and known factor from the global optimum.<ref name="fast" />
Given a function <math>f: \Lambda^n \to \mathbb{R}</math> with <math>\Lambda = \{1, \dots, k\}</math>, and a certain assignment of values <math>\mathbf{x} = (x_1, \dots, x_n) \in \Lambda^n</math> to the variables, it is possible to associate each assignment <math>\mathbf{x}</math> to a partition <math>P = \{P_l | l \in \Lambda \}</math> of the set of variables, such that, <math>P_l = \{ x_i | x_i = l \in \Lambda \}</math>. Give two distinct assignments <math>P</math> and <math>P'</math> and a value <math>\alpha \in \Lambda</math>, a move that transforms <math>P</math> into <math>P'</math> is said to be an <math>\alpha</math>-expansion if <math>P_\alpha \subset P'_\alpha</math> and <math>P'_l \subset P_l \; \forall l \in \Lambda - \{ \alpha \}</math>. Given a couple of values <math>\alpha</math> and <math>\beta</math>, a move is said to be an <math>\alpha\beta</math>-swap if <math>P_l = P'_l \; \forall l \in \Lambda - \{ \alpha, \beta \}</math>. Intuitively, an <math>\alpha</math>-expansion move from <math>\mathbf{x}</math> assigns the value of <math>\alpha</math> to some variables that have a different value in <math>\mathbf{x}</math>, while an <math>\alpha\beta</math>-swap move assigns <math>\alpha</math> to some variables that have value <math>\beta</math> in <math>\mathbf{x}</math> and vice versa.
Line 127:
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 of 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" />
:<math>f(\mathbf{x}) \le 2 \frac{ \max_{\alpha \ne \beta \in \Lambda} S(\alpha, \beta) }{ \min_{\alpha \ne \beta \in \Lambda} S(\alpha, \beta) } f(\mathbf{x}^*) . </math>
| |||