Page 184 -

3.7 Global optimization 163

(a) initial labeling (b) standard move (c) α-β-swap (d) α-expansion
Figure 3.58 Multi-level graph optimization from (Boykov, Veksler, and Zabih 2001) c 2001 IEEE: (a) initial
problem configuration; (b) the standard move only changes one pixel; (c) the α-β-swap optimally exchanges all
α and β-labeled pixels; (d) the α-expansion move optimally selects among current pixel values and the α label.

al. 2006a), natural image matting (Levin, Lischinski, and Weiss 2008), and image restoration
(Tappen, Liu, Freeman et al. 2007).
When ρ d or ρ p are non-quadratic functions, gradient descent techniques such as non-
linear least squares or iteratively re-weighted least squares can sometimes be used (Ap-
pendix A.3). However, if the search space has lots of local minima, as is the case for stereo
matching (Barnard 1989; Boykov, Veksler, and Zabih 2001), more sophisticated techniques
are required.
The extension of graph cut techniques to multi-valued problems was first proposed by
Boykov, Veksler, and Zabih (2001). In their paper, they develop two different algorithms,
called the swap move and the expansion move, which iterate among a series of binary labeling
sub-problems to find a good solution (Figure 3.58). Note that a global solution is generally not
achievable, as the problem is provably NP-hard for general energy functions. Because both
these algorithms use a binary MRF optimization inside their inner loop, they are subject to the
kind of constraints on the energy functions that occur in the binary labeling case (Kolmogorov
and Zabih 2004). Appendix B.5.4 discusses these algorithms in more detail, along with some
more recently developed approaches to this problem.
Another MRF inference technique is belief propagation (BP). While belief propagation
was originally developed for inference over trees, where it is exact (Pearl 1988), it has more
recently been applied to graphs with loops such as Markov random fields (Freeman, Pasz-
tor, and Carmichael 2000; Yedidia, Freeman, and Weiss 2001). In fact, some of the better
performing stereo-matching algorithms use loopy belief propagation (LBP) to perform their
inference (Sun, Zheng, and Shum 2003). LBP is discussed in more detail in Appendix B.5.3
as well as the comparative survey paper on MRF optimization (Szeliski, Zabih, Scharstein et
al. 2008).
Figure 3.57 shows an example of image denoising and inpainting (hole filling) using a
non-quadratic energy function (non-Gaussian MRF). The original image has been corrupted
by noise and a portion of the data has been removed (the black bar). In this case, the loopy
belief propagation algorithm computes a slightly lower energy and also a smoother image
than the alpha-expansion graph cut algorithm.
Of course, the above formula (3.113) for the smoothness term E p (i, j) just shows the
simplest case. In more recent work, Roth and Black (2009) propose a Field of Experts (FoE)
model, which sums up a large number of exponentiated local filter outputs to arrive at the