2

Graph Cuts—Combinatorial Optimization in Vision

Hiroshi Ishikawa

Department of Computer Science and Engineering
Waseda University
Tokyo, Japan

Email: [email protected]

CONTENTS

2.1    Introduction

2.1.1    Chapter Summary

2.2    Markov Random Field

2.2.1    Labeling Problem: A Simple Example

2.2.1.1    Denoising Problem

2.2.1.2    Image Similarity

2.2.1.3    Denoising Criterion

2.2.2    Markov Random Field

2.2.2.1    Order of an MRF

2.2.2.2    Energy of an MRF

2.2.2.3    Bayesian Inference

2.3    Basic Graph Cuts: Binary Labels

2.3.1    Minimum-Cut Algorithms

2.3.2    The Graph Cuts

2.3.3    Submodularity

2.3.4    Nonsubmodular Case: The BHS Algorithm

2.3.5    Reduction of Higher-Order Energies

2.4    Multi-Label Minimization

2.4.1    Globally Minimizable Case: Energies with Convex Prior

2.4.2    Move-Making Algorithms

2.4.2.1    α-β Swap and α-Expansion

2.4.2.2    Fusion Moves

2.4.2.3    α-β Range Moves

2.4.2.4    Higher-Order Graph Cuts

2.5    Examples

2.6    Conclusion

Bibliography

2.1    Introduction

Many problems in computer vision, image processing, and computer graphics can be put into labeling problems [1]. In such a problem, an undirected graph is given as an abstraction of locations and their neighborhood structure, along with a set of labels. Then, the solutions to the problem is identified with labelings, or assignments of a label to each vertex in the graph. The problem is then to find the best labeling according to the criteria in the problem’s requirements. An energy is a translation of the criteria into a function that evaluates how good the given labeling is, so that smaller energy for a labeling means a better corresponding solution to the problem. Thus, the problem becomes an “energy minimization problem”. This separates the problem and the technique to solve it in a useful way by formulating the problem as an energy, it tends to make the problem more clearly defined, and also, once the problem is translated into an energy minimization problem, it can be solved using general algorithms.

In this chapter, we describe a class of combinatorial optimization methods for energy minimization called the graph cuts. It has become very popular in computer vision, image processing, and computer graphics, used for various tasks such as segmentation [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13], motion segmentation [14, 15, 16, 17], stereo [18, 19, 20, 21, 22, 23, 24], texture and image synthesis [25, 26], image stitching [27, 28, 29, 30], object recognition [31, 32, 33], computing geodesics and modeling gradient flows of contours and surfaces [34, 35], computational photography [36], and motion magnification [37].

Minimization of such energies in general is known to be NP-hard [38]. Stochastic approximation methods, such as the iterated conditional modes (ICM) [39] and simulated annealing [40] have been used, but the former is prone to falling into local minima, while the latter, although the convergence to global minima is theoretically guaranteed, it is very slow in practice.

Graph cuts are methods utilizing the s-t mincut algorithms. Known in operations research for a long time [41], it was first introduced into image processing in the late 1980s [42, 43], when it was shown capable of exactly minimizing an energy devised to denoise binary images. At the time, the exact solution was compared to the results by annealing, which turned out to oversmooth the images [44, 43].

In late 1990s, graph cuts were introduced to the vision community [19, 45, 6, 46, 23]. This time the method was used for multilabel cases, and it was shown [19, 6] that energies with real numbers as labels can be exactly minimized if the prior is linear in terms of the absolute value of the difference between the labels at neighboring sites. This was later generalized to the construction for the case when the prior is any convex function of the difference [47]. Also, approximation algorithms for the energies with for arbitrary label sets and Potts priors were introduced [19, 38], which lead to the current popularity.

At first, there was some duplication of efforts in the vision community. The condition for the binary energy to be exactly solved, long known in the OR community as the submodularity condition, was rediscovered [48]. The “linear” case mentioned above was also devised without the knowledge that a similar method had been used for the problem of task assignment to multiple processors [49]. Now, methods long known in the OR community have been introduced to vision, such as the BHS (a.k.a. QPBO / roof duality) algorithm [50, 51, 52, 53] that proved very useful.

Other new minimization methods such as belief propagation (BP) [54, 55, 56] and the tree-reweighted message passing (TRW) [57, 58]) have also been introduced to vision. An experimental comparison [59] of these methods with graph cuts were conducted using stereo and segmentation as examples. It showed that these new methods are much superior to ICM, which was used as the representative of the older methods. When the neighborhood structure was relatively sparse, such as the 4-neighbors, TRW performed better than graph cuts. However, according to another study [60], when the connectivity is larger, as in the case of stereo models with occlusion, graph cuts considerably outperformed both BP and TRW in both the minimum energy and the error compared to the ground truth.

2.1.1    Chapter Summary

We first introduce the energy minimization formalisms used in the image-related areas (§2.2). Next (§2.3), we describe the graph cut algorithm in the case of binary labels, which is the most fundamental case where the energy-minimization problem directly translates to the minimum-cut problem, and global minima can be computed in a polynomial time under certain condition called submodularity. For the binary case, we also describe the BHS algorithm, which can partially minimize even the energies that do not satisfy the submodularity condition, as well as the reduction of higher-order energies to first order. Finally (§2.4), we describe graph cuts to minimize energies when there are more than two labels. One approach to this is to translate multilabel energies into binary ones. In some cases, the resulting problem is globally optimizable. Another way is the approximate algorithms to solve the multilabel problems by iteratively solving binary problems with graph cuts.

2.2    Markov Random Field

2.2.1    Labeling Problem: A Simple Example

As the simplest example, we consider the denoising problem of binary (black-and-white) images. Such an image consists of pixels that can be black or white, arranged in a rectangle. This is an example of labeling. Each pixel in the image has a color; we consider this as assigning a label—0 for white and 1 for black—to each pixel. A labeling is thus a map from the set of pixels to the set of labels. Therefore, every image is a labeling. Thus, the denoising problem is that of finding the “least noisy” labeling.

FIGURE 2.1
A labeling is an assignment of a label to each pixel. A binary image is a labeling with two labels. The image on the left is a labeling, as shown on the right.

More formally, let us denote the set of pixels by P$\mathcal{P}$ and the set of labels by $ℒ$. For example, in the case of the binary image denoising, $\mathcal{P}=\left\{\left(i,j\right)|i=1,\cdots ,n;j=1,\cdots ,m\right\}$ and $ℒ=\left\{0,1\right\}$, assuming that the image has n × m pixels. Then a labeling is a map

$X:\mathcal{P}\to ℒ.$

(2.1)

Since the actual coordinates are not needed in the discussion, in the following we denote the pixels by single letters such as $p,q\in \mathcal{P}$. The label that is assigned to pixel p by a labeling X is denoted by X_p:

$X:\mathcal{P}\ni p\mapsto X_p\in ℒ.$

(2.2)

Figure 2.1 depicts an example of binary image and the labeling representing it.

For a set $\mathcal{P}$ of pixels and a set $ℒ$ of labels, we denote the set of all labelings by ${ℒ}^{\mathcal{P}}$. There are ${\left|ℒ\right|}^{\left|\mathcal{P}\right|}$ possible such labelings; thus, the number of possible solutions to the denoising problem is exponential in terms of the number of pixels. For a labeling $X\in {ℒ}^{\mathcal{P}}$ and any subset $\mathcal{Q}\subset \mathcal{P}$, the labeling on $\mathcal{Q}$ defined by restricting X to $\mathcal{Q}$ is denoted by $X_{\mathcal{Q}}\in {ℒ}^{\mathcal{Q}}$.

FIGURE 2.2
(a) Counting the number of pixels that has different colors for X and Y. (b) Counting neighboring pairs of pixels in X that have different colors.

2.2.1.1    Denoising Problem

In the denoising problem, we are given one labeling, the noisy image, and somehow find another labeling, the denoised image. The input and the output are related as follows:

1.  They are the “same” image.

2.  The output has less noise than the input.

To denoise an image by energy minimization, we need to know what these mean in terms of the labeling. We translate these notions into an energy

$E:{ℒ}^{\mathcal{P}}\to ℝ,$

(2.3)

which is a function on the set ${ℒ}^{\mathcal{P}}$ of labelings that gives a real number to each labeling. The real number E(X) that is given a labeling X is called its energy. The energy evaluates how well the conditions above are met by a labeling. According to the problem at hand, we define the energy so that it gives a smaller value to a labeling when it is better according to some criteria that we consider reasonable or that we have observed to produce good results. Then we use an algorithm, such as graph cuts, to minimize the energy, i.e., the algorithm finds a labeling with as small an energy as possible. With graph cuts, sometimes the global minimum of the energy can be found; that is, we can actually find the labeling that gives the smallest energy among all the exponential number of possible labelings in ${ℒ}^{\mathcal{P}}$, or at least one of such minima.

2.2.1.2    Image Similarity

Suppose we are given a noisy image, or a labeling, Y, and that we would like to find the denoised version X. First, we consider the condition (1) above. That is, the noisy image Y and the denoised image X are supposed to be the same image. Since we cannot take this as meaning they are exactly the same (then we cannot reduce the noise), we quantify the difference between the two images and assume the condition means that the difference is small. How do we quantify the difference between two images? A popular method is to take the square of the L² norm:

${\displaystyle \sum _{p\in \mathcal{P}}{\left(X_p-Y_p\right)}^2.}$

(2.4)

Another oft-used measure of the difference between two images is the sum of absolute difference:

${\displaystyle \sum _{p\in \mathcal{P}}\left|X_p-Y_p\right|},$

(2.5)

In our case, the two measures coincide, since the label is either 0 or 1. They both mean the number of the pixels that have different labels between X and Y, as illustrated in Figure 2.2(a).

2.2.1.3    Denoising Criterion

If we want to find the labeling X that minimize (2.4) or (2.5), it is easy: we take X = Y. This is natural, since we do not have any reason to arrive at anything else so far. To make X the denoised version of Y, we need to have some criterion to say some images are noisier than others. If we have the original image before noise was introduced, we can say that the closer the image is to the original, the less noisier it is. However, if we had the original, we don’t need to denoise it but that is not usually the case. So we need a way to tell the level of noise in an image without comparing it with the original. If it is in the sense above, the closeness to the original, that is clearly impossible, since the original might be very “noisy” to start with. Nevertheless, we have a sense that some images are noisy and others are not, which presumably comes from the statistics of images that we encounter in life. Thus, knowing the statistics of images helps. Also, there are different kinds of noises that are likely to be introduced in practice whose statistics we know. If we know what caused the noise in the image, we can use the information to reduce the noise.

Here, however, we are using the denoising problem only as an example; so we simply assume that the noisier the image is, the rougher it is, that is, there are more changes in color between neighboring pixels.

Accordingly, to evaluate the roughness of image X, we count the number of changes in color between neighboring pixels (see Figure 2.2(b)) as follows:

${\displaystyle \sum _{\left(p,q\right)\in \mathcal{N}}{\left(X_p-X_q\right)}^2}.$

(2.6)

Here, $N\subset \mathcal{P}\times \mathcal{P}$ is the set of neighboring pairs of pixels. We assume that $\mathcal{N}$ is symmetric, i.e., $\left(q,p\right)\in \mathcal{N}$ if $\left(p,q\right)\in \mathcal{N}$. We also assume that $\left(p,p\right)\notin \mathcal{N}$ for any $p\in \mathcal{P}$.

The image that satisfies the “less noise” condition (2) the most, which minimizes the quantity (2.6), is a constant image, either all black or all white. On the other hand, the condition (1) is perfectly satisfied if we set X = Y, as mentioned above. Thus, the two conditions conflict unless Y is a constant image, leading to a need of a tradeoff. The heart of the energy minimization methods is that we attempt to treat such a tradeoff in a principled way by defining it as minimization of an energy. That is, we translate various factors in the tradeoff as terms which are added up to form an energy. The relative importance of each factor can be controlled by multiplying it by a weight.

FIGURE 2.3
Denoising a binary image. Given the noisy image Y on the left, find the image X that is close to Y and has as few change as possible of labels between neighboring pixels. Since the two conditions usually conflict, we need to find a trade off. We encode it as the minimization of the energy (2.7).

In our case, we define the energy as a weighted sum of (2.4) and (2.6):

$E\left(X\right)={\displaystyle \sum _{p\in \mathcal{P}}\lambda {\left(X_p-Y_p\right)}^2+{\displaystyle \sum _{\left(p,q\right)\in \mathcal{N}}\kappa {\left(X_p-X_q\right)}^2}}$

(2.7)

We consider the energy a function of X, supposing Y is fixed. Here, λ and κ are positive weights. Although the two weights are fixed globally in this example, it can be varied from pixel to pixel and pair to pair, depending on the data Y and other factors; for instance, the smoothing factor κ is often changed according to the contrast in Y between the neighboring pixels. Figure 2.3 illustrates the tradeoff represented by the energy.

Assume that X minimizes E(X). For each pixel p, X_p = Y_p makes the first sum smaller. On the other hand, a smoother X without too many changes between neighboring pixels leads to a lesser second sum. Let us assume that λ = κ. If, for instance, there is an “isolated” pixel p such that Y assigns all its neighbors the opposite value from Y_p, the total energy would be smaller when the value X_p at p is the same with the neighbors, rather than choosing X_p = Y_p. Thus, minimizing E(X) represents an effort to make X as close as possible to Y while fulfilling the condition that the values between neighboring pixels do not change too much. The tradeoff between the two conditions are controlled by the relative magnitude of the parameters λ and κ.

2.2.2    Markov Random Field

The energy minimization problem as above can be considered a maximum a posteriori (MAP) estimation problem of a Markov random field (MRF).

A Markov random field is a stochastic model with a number of random variables that are arranged in an undirected graph, so that each node has one variable. Let $\mathcal{P}$ and $\mathcal{N}$ be the sets of pixels and neighbors, as before. We will call the elements of $\mathcal{P}$ “sites”; they represent the notion of location in the problem. Since we are assuming $\mathcal{N}$ is symmetric, we can consider $\left(\mathcal{P},\mathcal{N}\right)$ an undirected graph. The sites most commonly correspond to the pixels in the images, especially in low-level problems such as the denoising example above. However, they sometimes represent other objects such as blocks in the images and segments (so-called superpixels) obtained by a quick oversegmentation of images.

A set of random variables $X={\left(X_p\right)}_{p\in \mathcal{P}}$ is a Markov random field if its probability density function can be written as:

$P\left(X\right)={\displaystyle \prod _{C\in \mathcal{C}}{\phi }_{\mathcal{C}}\left(X_C\right)},$

(2.8)

where $\mathcal{C}$ is the set of cliques of the undirected graph $\left(\mathcal{P},\mathcal{N}\right)$, and each function φ_C depends only on the vector of variables X_C = (X_p)_p∈C.

Assume that the random variables in X all take values in the same set $ℒ$. Then, we can think the set of random variables to be a random variable taking a value in the set ${ℒ}^{\mathcal{P}}$ of labelings. Thus, an MRF can be thought of as a random variable with values in the set of labelings whose probability density function (2.8) satisfies the condition above.

2.2.2.1    Order of an MRF

When the probability density function P(X) in (2.8) can be written as

$P\left(X\right)={\displaystyle \prod _{C\in \mathcal{C},\left|C\le k+1\right|}{\phi }_{\mathcal{C}}\left(X_C\right)},$

(2.9)

with only the functions depending on the variables for cliques with at most k + 1 sites, it is called a k’th order MRF or an MRF of order k. For instance, an MRF of first order can be written as:

$P\left(X\right)={\displaystyle \prod _{p\in \mathcal{P}}{\phi }_p\left(X_p\right)}{\displaystyle \prod _{\left(p,q\right)\in \mathcal{N}}{\phi }_{\left\{p,q\right\}}\left(X_{\left\{p,q\right\}}\right)},$

(2.10)

that depends only on the functions for cliques of size 1 and 2, i.e., sites and neighboring pairs of sites. An MRF of second order can be written as:

$P\left(X\right)={\displaystyle \prod _{p\in \mathcal{P}}{\phi }_p\left(X_p\right)}{\displaystyle \prod _{\left(p,q\right)\in \mathcal{N}}{\phi }_{\left\{p,q\right\}}\left(X_{\left\{p,q\right\}}\right)}{\displaystyle \prod _{\left\{p,q,r\right\}\text{clique}}{\phi }_{\left\{p,q,r\right\}}\left(X_{\left\{p,q,r\right\}}\right)}.$

(2.11)

Remember that the notation X_{{p, q, r}} denotes the vector (X_p, X_q, X_r) of variables.

Note that there is an ambiguity in the factorization of the density function, since lower-order functions can be a part of a higher-order function. We can reduce this ambiguity somewhat by restricting $\mathcal{C}$ to be the set of maximal cliques. However, in practice we define the functions concretely; so there is no problem of ambiguity, and we would like to define them in a natural way. Therefore, we leave $\mathcal{C}$ to mean the set of all cliques.

2.2.2.2    Energy of an MRF

If we define in (2.8)

$f_C\left(X_C\right)=-\log {\phi }_{\mathcal{C}}\left(X_C\right),$

(2.12)

then maximizing P(X) in (2.8) is equivalent to minimizing

$E\left(X\right)={\displaystyle \sum _{C\in \mathcal{C}}{f}_C\left(X_C\right)},$

(2.13)

This function that assigns a real number E(X) to a labeling X is called the energy of the MRF. An MRF is often defined with an energy instead of a density function. Given the energy (2.13), the density function (2.8) is obtained as

$p\left(X\right)=e^{-E\left(X\right)}={\displaystyle \prod _{C\in \mathcal{C}}{e}^{-f_C\left(X_C\right)}}.$

(2.14)

This form of probability density function is called the Gibbs distribution.

The first-order MRF in (2.10) has the energy

$E\left(X\right)={\displaystyle \sum _{p\in \mathcal{P}}{g}_p\left(X_p\right)+}{\displaystyle \sum _{\left(p,q\right)\in \mathcal{N}}{h}_{pq}\left(X_p,X_q\right)},$

(2.15)

where

$g_p\left(X_p\right)=-\log {\phi }_p\left(X_p\right),$

(2.16)

$h_{pq}\left(X_p,X_q\right)=h_{qp}\left(X_q,X_p\right)=-\log {\phi }_{\left\{p,q\right\}}\left(X_{\left\{p,q\right\}}\right).$

(2.17)

Most of the use of graph cuts have been for minimizing the energy of the form (2.15). Each term g_p(X_p) in the first sum in (2.15) depends only on the label assigned to each site. The first sum is called the data term, because the most direct influence of data such as the given image, in deciding the label to assign to each site, often manifests itself through g_p(X_p). For instance, in the case of the denoising problem in the previous section, this term influences the labeling X in the direction of making it closer to Y through the definition:

$g_p\left(X_p\right)=\text{λ}{\left(X_p-Y_p\right)}^2.$

(2.18)

Thus, the first term of (2.15) represents the data influence on the optimization process.

The second sum, on the other hand, reflects the prior assumption on the wanted outcome, such as less noise. In particular, it dictates the desirable property of the labels given to neighboring sites. Because this often means that there is less label change between neighboring sites, this term is called the smoothing term. In the case of the previous section, it is defined by:

$h_{pq}\left(X_p,X_q\right)=\kappa {\left(X_p-X_q\right)}^2.$

(2.19)

Sometimes, it is also called the prior term. The reason is that it often encodes the prior probability distribution, as will be explained next.

2.2.2.3    Bayesian Inference

Assume that we wish to estimate an unobserved parameter X, on the basis of observed data Y. The maximum a posteriori (MAP) estimate of X is its value that maximizes the posterior probability P(X|Y), which is the conditional probability of X given Y. It is often used in the area of statistical inference, where some hidden variable is inferred from an observation. For instance, the denoising problem in the previous section can be thought of as such an inference.

The posterior probability P(X|Y) is often derived from the prior probability P(X) and the likelihood P(Y|X). The prior P(X) is the probability of X when there is no other condition or information. The likelihood P(Y|X) is the conditional probability that gives the data probability under the condition that the unobserved variable in fact has value X. From these, the posterior is obtained by Bayes’ rule:

$P\left(X\text{|}Y\right)=\frac{P\left(Y\text{|}X\right)P\left(X\right)}{P\left(Y\right)}.$

(2.20)

Suppose that we have an undirected graph $\left(\mathcal{P},\mathcal{N}\right)$ and a set $\mathcal{L}$ of labels. Also suppose that the unobserved parameter X takes as value a labeling, and we have a simple probabilistic model given by the following:

$P\left(Y\text{|}X\right)=\frac{1}{Z_1\left(Y\right)}{\displaystyle \prod _{p\in \mathcal{P}}{\phi }_p^Y\left(X_p\right)},$

(2.21)

$P\left(X\right)=\frac{1}{Z_2}{\displaystyle \prod _{\left(p,q\right)\in \mathcal{N}}{\phi }_{pq}\left(X_p,X_q\right)},$

(2.22)

where

$Z_1\left(Y\right)={\displaystyle \sum _{X\in {ℒ}^{\mathcal{P}}}{\displaystyle \prod _{p\in \mathcal{P}}{\phi }_p^Y\left(X_p\right)}},$

(2.23)

$Z_2={\displaystyle \sum _{X\in {ℒ}^{\mathcal{P}}}{\displaystyle \prod _{\left(p,q\right)\in \mathcal{N}}{\phi }_{pq}\left(X_p,X_q\right)}}.$

(2.24)

That is, the likelihood P(Y|X) of the data Y given the parameter X is given in the form of the product of independent local distributions ${\phi }_p^Y\left(X_p\right)$ for each site p that depends only on the label X_p, while the prior probability P(X) is defined as a product of local joint distributions φ_pq(X_p, X_q) depending on the labels X_p and X_q that the neighboring sites p and q are given.

By (2.20), it follows

$P\left(X\text{|}Y\right)=\frac{1}{Z_1\left(Y\right)Z_2}{\displaystyle \prod _{p\in \mathcal{P}}{\phi }_p^Y\left(X_p\right)}{\displaystyle \prod _{\left(p,q\right)\in \mathcal{N}}{\phi }_{pq}\left(X_p,X_q\right)}.$

(2.25)

If we fix the observed data Y, this makes it a first-order MRF. Thus, maximizing the posterior probability P(X|Y) with a fixed Y is equivalent to the energy minimization problem of an MRF. For instance, our example energy minimization formulation of the denoising problem can be considered a MAP estimation problem with the likelihood and the prior:

$P\left(Y\text{|}X\right)=\frac{1}{Z_1\left(Y\right)}{\displaystyle \prod _{p\in \mathcal{P}}{e}^{-\lambda {\left(X_p-Y_p\right)}^2}},$

(2.26)

$P\left(X\right)=\frac{1}{Z_2}{\displaystyle \prod _{\left(p,q\right)\in \mathcal{N}}{e}^{-\kappa {\left(X_p-X_q\right)}^2}},$

(2.27)

which is consistent with a Gaussian noise model.

2.3    Basic Graph Cuts: Binary Labels

In this section, we discuss the basics of graph-cut algorithms, namely the case where the set of labels is binary: $ℒ=\mathbb{B}=\left\{0,1\right\}$. The multiple label graph cuts depend on this basic case. As it is based on the algorithms to solve the s-t minimum cut problem, we start with a discussion on them. For details on the minimum cut and maximum flow algorithms, see textbooks such as [61, 62, 63].

2.3.1    Minimum-Cut Algorithms

Consider a directed graph $\mathcal{G}=\left(\mathcal{V},ℰ\right)$. Each edge e_i→j from υ_i to υ_j has weight w_ij. For the sake of notational simplicity, in the following we assume every pair of nodes ${\upsilon }_i,{\upsilon }_j\in \mathcal{V}$ has weight w_ij but w_ij = 0 if there is no edge e_i→j.

Let us choose two nodes $s,t\in \mathcal{V}$; a cut of $\mathcal{G}$ with respect to the pair (s, t) is a partition of $\mathcal{V}$ into two sets $\mathcal{S}\subset \mathcal{V}$ and $\mathcal{T}=\mathcal{V}\mathcal{S}$ such that $s\in \mathcal{S},t\in \mathcal{T}$ (Figure 2.4). In the following, we denote this cut by $\left(\mathcal{S},\mathcal{T}\right)$. Then, the $costc\left(\mathcal{S},\mathcal{T}\right)$ of cut $\left(\mathcal{S},\mathcal{T}\right)$ is the sum of the weights of the edges that go from $\mathcal{S}$ to $\mathcal{T}$:

FIGURE 2.4
(a) A cut of $\mathcal{G}$ with respect to (s, t) divides the nodes into two sides. The cost of a cut is the total sum of the weights of the directed edges going from the s side $\left(\mathcal{S}\right)$ to the t side $\left(\mathcal{T}\right)$. The cost of the depicted cut is 10, the sum of the weights of the edges in the cut, indicated by thick arrows. (b) Another example: the cost of the cut is 3.

$c\left(\mathcal{S},\mathcal{T}\right)={\displaystyle \sum _{{\upsilon }_i\in \mathcal{S},{\upsilon }_j\in \mathcal{T}}{w}_{ij}}.$

(2.28)

Note that the directed edges going the other direction, from $\mathcal{T}$ to $\mathcal{S}$, do not count. An edge that contributes to the cost is said to be in the cut. A minimum cut is a cut with the minimum cost, and the minimum cut problem seeks to find such a cut for given the triple $\left(\mathcal{G},s,t\right)$.

The minimum cut problem is well known to be equivalent to the maximum flow problem [64, 65]. When all edge weights are nonnegative, these problems are known to be tractable, which is the source of the usefulness of graph cuts. There are three groups of algorithms known: the ‘augmenting path’ algorithms [64, 66], the ‘push-relabel’ algorithms [67, 68, 69], and the ‘network simplex’ algorithms [70]. Although asymptotically the push-relabel algorithms are the fastest, for typical image-related applications, actual performance seems to indicate that the augmenting path algorithms are the fastest. Boykov and Kolmogorov [71] experimentally compared the Dinic algorithm [72], which is a kind of augmenting path algorithm, a push-relabel algorithm, and their own augmenting path algorithm (the BK algorithm) in image restoration, stereo, and image segmentation applications to find the BK algorithm to be the fastest. This is the maximum-flow algorithm most used for graph cuts in image-related applications. There is also a push-relabel algorithm that was specifically developed for large regular grid graphs [73] used in higher-dimensional image processing problems, as well as algorithms to speed up the repeated minimization of an energy with small modifications [74, 75, 76], as commonly happens in movie segmentation.

FIGURE 2.5
(a) The graph for binary MRF minimization. The edges in the cut are depicted as thick arrows. Each node other than υ_s and υ_t corresponds to a site. If a cut $\left(\mathcal{S},\mathcal{T}\right)$ places a node in $\mathcal{S}$, the corresponding site is labeled 0; if it is in $\mathcal{T}$, the site is labeled 1. The 0’s and 1’s at the bottom indicate the label each site is assigned. Here, the sites are arranged in 1D; but according to the neighborhood structure this can be any dimension as shown in (b) and (c).

2.3.2    The Graph Cuts

The graph-cut algorithms utilize the minimum cut (maximum flow) algorithms to minimize MRF energies. We construct a graph with special nodes s and t, as well as a node for each site. Then for a cut $\left(\mathcal{S},\mathcal{T}\right)$ of the graph with respect to the pair (s, t), each node must be either in $\mathcal{S}$ or $\mathcal{T}$; we interpret this as the site being labeled 0 or 1. That is, we define a one to one correspondence between the set of all labeling and that of all cuts.

Consider the first-order MRF energy (2.15), shown here again:

$E\left(X\right)={\displaystyle \sum _{p\in \mathcal{P}}{g}_p\left(X_p\right)}+{\displaystyle \sum _{\left(p,q\right)\in \mathcal{N}}{h}_{pq}\left(X_p,X_q\right)}$

(2.29)

We construct a directed graph $\mathcal{G}=\left(\mathcal{V},ℰ\right)$ corresponding to this energy (Figure 2.5). The node set $\mathcal{V}$ contains the special nodes υ_s and υ_t (for consistency with the notation for graph edges in this book, we denote what we called s and t by υ_s and υ_t, respectively), as well as a node corresponding to each site p in $\mathcal{P}$:

$\mathcal{V}=\left\{{\upsilon }_s,{\upsilon }_t\right\}\cup \left\{{\upsilon }_p\text{|}p\in \mathcal{P}\right\}.$

(2.30)

From and to each node υ_p corresponding to a site $p\in \mathcal{P}$, we add two edges, and also edges between nodes corresponding to neighboring sites:

$ℰ=\left\{e_{s\to p}\text{|}p\in \mathcal{P}\right\}\cup \left\{e_{p\to t}|p\in \mathcal{P}\right\}\cup \left\{e_{p\to q}|\left(p,q\right)\in \mathcal{N}\right\}.$

(2.31)

FIGURE 2.6
Weights for binary MRF minimization for the energy in the example in Section 2.2.1. The numbers at the bottom indicates the labels assigned to the sites above. The thick arrows indicate the edges in the cut. The cut separates the nodes υ_p and υ_t; thus, the site p is assigned the label 0. The weight is exactly g_p(0), which is added to the cost of the cut. Similarly, the site q is assigned 1 and the cost is added g_q(1). When two neighboring sites are assigned different labels, an edge between the two is cut. Here, the labels differ between p and q; thus, the weight h_pq(0, 1) of the edge e_p→q is added to the cost of the cut.

Now, we define a correspondence between a cut $\left(\mathcal{S},\mathcal{T}\right)$ of $\mathcal{G}$ with respect to (υ_s, υ_t) and a labeling $X\in {ℒ}^{\mathcal{P}}$ as follows:

$X_p=\{\begin{array}{ll}0\hfill & \left(\text{if}{\upsilon }_p\in \mathcal{S}\right)\hfill \\ 1\hfill & \left(\text{if}{\upsilon }_p\in \mathcal{T}\right).\hfill \end{array}$

(2.32)

That is X assigns 0 to site p if the node υ_p corresponding to p is on the υ_s side, and 1 if it is on the υ_t side. This way, there is a one-to-one correspondence between cuts of $\mathcal{G}$ with respect to (υ_s, υ_t) and labelings in ${ℒ}^{\mathcal{P}}$.

The minimum-cut algorithm can find a cut with the minimum cost efficiently; thus, in order to find a labeling that minimizes the energy (2.15), we want to define a weight of $\mathcal{G}$ so that the minimum cut corresponds to the minimum energy.

We consider the example in Section 2.2.1, with the energy terms (2.18) and (2.19), and define:

$w_{sp}=g_p\left(1\right),$

(2.33)

$w_{pt}=g_p\left(0\right),$

(2.34)

$w_{pq}=h_{pq}\left(0,1\right).$

(2.35)

Consider the labeling X corresponding to a cut $\left(\mathcal{S},\mathcal{T}\right)$ of $\mathcal{G}$. First, note the data term that depends only on one site. If ${\upsilon }_p\in \mathcal{S}$, then by (2.32) X_p = 0 and, as the edge e_p→t is in the cut, by (2.34) w_pt = g_p(0) = g_p(X_p) is added to the cost of the cut. If ${\upsilon }_p\in \mathcal{T}$, then X_p = 1 and, as the edge e_s→p is in the cut, by (2.33) w_sp = g_p(1) = g_p(X_p) is added to the cost. Either way, g_p(X_p) is added to the cost of the cut.

FIGURE 2.7
Smoothing term and cost.

Next, we consider the smoothing term depending on two neighboring sites. For a neighboring pair of sites p and q, if ${\upsilon }_p\in \mathcal{S},{\upsilon }_q\in \mathcal{T}$, then the edge e_p→q is in the cut. Thus, by (2.35) h_pq(0, 1) = κ is added to the cut cost. By (2.32), it corresponds to (X_p, X_q) = (0, 1) and the added weight to the cost coincides with the smoothing term that should be added to the energy in such combination of assignment. When both υ_p and υ_q belong to either of $\mathcal{S}$ and $\mathcal{T}$, the increase in cost is zero, corresponding to the energy h_pq(0, 0) = h_pq(1, 1) = 0.

This way, the energy for the labeling X precisely coincides with the cost of the corresponding cut. This construction is due to [43].

2.3.3    Submodularity

Thus, by finding the minimum-cut, we can find the global minimum of the energy (2.7) for our image denoising example, as well as the labeling that attains it. Can we generalize this to more general form of energy? The limiting factor is that the edge weights must be nonnegative in order to benefit from the polynomial-time minimum-cut algorithms: with the above construction, g_p(X_p) and h_pq(X_p, X_q) must all be nonnegative in (2.15). Also, it assumes h_pq(0, 0) = h_pq(1, 1) = 0.

However, there is still a little leeway in choosing edge weights. For instance, each υ_p must belong to either $\mathcal{S}$ or $\mathcal{T}$; so one of the edges e_s→p and e_p→t is always in the cut. Therefore, adding the same value to w_sp and w_pt does not affect the choice of which edge to cut. This means that g_p(X_p) can take any number because, if we have negative weight after defining w_sp and w_pt according to (2.33) and (2.34), we can add − min{w_sp, w_pt} to w_sp and w_pt to make both nonnegative. In fact, one of w_sp and w_pt can always be set to zero this way.

So the data term is arbitrary. How about the smoothing term? For a pair p, q of sites, let us define

$\begin{array}{ccc}{w}_{qt}=a,& w_{pq}=b,& w_{sp}=c,\end{array}$

(2.36)

as shown in Figure 2.7. Then the cut costs for the four possible combinations of (X_p, X_q) are:

$\begin{array}{cccc}{h}_{pq}\left(0,0\right)=a,& h_{pq}\left(0,1\right)=b,& h_{pq}\left(1,0\right)=a+c,& h_{pq}\left(1,1\right)=c.\end{array}$

(2.37)

Then we have

$h_{pq}\left(0,1\right)+h_{pq}\left(1,0\right)-h_{pq}\left(0,0\right)-h_{pq}\left(1,1\right)=b.$

(2.38)

Since the right-hand side is an edge weight, it must be nonnegative for the polynomial-time algorithms to be applicable. This is known as the submodularity condition:

$h_{pq}\left(0,1\right)+h_{pq}\left(1,0\right)-h_{pq}\left(0,0\right)-h_{pq}\left(1,1\right)\ge 0.$

(2.39)

Conversely, if this condition is met, we can set

$a=h_{pq}\left(1,0\right)-h_{pq}\left(1,1\right),$

(2.40)

$b=h_{pq}\left(0,1\right)+h_{pq}\left(1,0\right)-h_{pq}\left(0,0\right)-h_{pq}\left(1,1\right),$

(2.41)

$c=h_{pq}\left(1,0\right)-h_{pq}\left(0,0\right).$

(2.42)

Then we have the cut cost for each combination as follows:

$\left(X_p,X_q\right)=\left(0,0\right):h_{pq}\left(1,0\right)-h_{pq}\left(1,1\right),$

(2.43)

$\left(X_p,X_q\right)=\left(0,1\right):h_{pq}\left(0,1\right)+h_{pq}\left(1,0\right)-h_{pq}\left(0,0\right)-h_{pq}\left(1,1\right),$

(2.44)

$\left(X_p,X_q\right)=\left(1,0\right):h_{pq}\left(1,0\right)-h_{pq}\left(1,1\right)+h_{pq}\left(1,0\right)-h_{pq}\left(0,0\right),$

(2.45)

$\left(X_p,X_q\right)=\left(1,1\right):h_{pq}\left(1,0\right)-h_{pq}\left(0,0\right).$

(2.46)

If we add h_pq (0, 0) + h_pq (1, 1) − h_pq (1, 0) to the four cost values, we see each equals h_pq(X_p, X_q). Since we are adding the same value to the four possible outcome of the pair, it does not affect the relative advantage among the alternatives. Thus, the minimum cut still corresponds to the labeling with the minimum energy.

We can do this for each neighboring pair. If all such pair p, q satisfies (2.39), we define:

$w_{sq}=g_q\left(1\right)+{\displaystyle \sum _{\left(p,q\right)\in \mathcal{N}}\left\{h_{pq}\left(1,0\right)-h_{pq}\left(0,0\right)\right\},}$

(2.47)

$w_{qt}=g_q\left(0\right)+{\displaystyle \sum _{\left(p,q\right)\in \mathcal{N}}\left\{h_{pq}\left(1,0\right)-h_{pq}\left(1,1\right)\right\},}$

(2.48)

$w_{pq}=h_{pq}\left(0,1\right)+h_{pq}\left(1,0\right)-h_{pq}\left(0,0\right)-h_{pq}\left(1,1\right).$

(2.49)

After that, if any edge weight w_sq or w_qt is negative, we can make it nonnegative as explained above.

In this way, we can make all the edge weights nonnegative. And from the construction, the minimum cut of this graph corresponds, by (2.32), to a labeling that minimizes the energy (2.15). The basic construction above for submodular first-order case has been known for at least 45 years [41].

2.3.4    Nonsubmodular Case: The BHS Algorithm

When the energy is not submodular, there are also known [53, 50] algorithms that give a partial solution, which were introduced to the image-related community, variously called as the QPBO algorithm [77] or roof duality [78]. Here, we describe the more efficient of the two algorithms, the BHS algorithm [50].

The solution of the algorithms has the following property:

1.  The solution is a partial labeling, i.e., a labeling $X\in {\mathbb{B}}^{\mathcal{Q}}$ on a subset $\mathcal{Q}$ of $\mathcal{P}$.

2.  Given an arbitrary labeling $Y\in {\mathbb{B}}^{\mathcal{P}}$, the output labeling $X\in {\mathbb{B}}^{\mathcal{Q}}$ has the property that, if we “overwrite” Y with X, the energy for the resulting labeling is not higher than that for the original labeling. Let us denote by Y ⊳ X the labeling obtained by overwriting Y by X:

${\left(YᐊX\right)}_p=\{\begin{array}{ll}{X}_p\hfill & \text{if}p\in \mathcal{Q}\hfill \\ Y_p\hfill & \text{otherwise}.\hfill \end{array}$

(2.50)

Then, this autarky property means E(Y ⊳ X) ≥ E(Y). If we take as Y a global minimum, then Y ⊳ X is also a global minimum. Thus, we see that the partial labeling X is always a part of a global minimum labeling, i.e., we can assign 0 or 1 to each site outside of $\mathcal{Q}$ to make it into the global minimum labeling Y ⊳ X. It also means that if $\mathcal{Q}=\mathcal{P}$, X is a global minimum labeling.

3.  If the energy is submodular, all sites are labeled, giving a global minimum solution.

How many of the sites are labeled when the energy is not submodular is up to the individual problem.

Here, we give the graph construction for the BHS algorithm, following [77]. First, we reparametrize the given energy, i.e., modify it without changing the minimization problem, into the normal form. The energy (2.15) is said to be in normal form if

1.  For each site p, min{g_p(0), g_p(1)} = 0,

2.  For each $\left(p,q\right)\in \mathcal{N}$ and x = 0, 1, min{h_pq(0, x), h_pq(1, x)} = 0.

Note that the normal form is not unique. Beginning with any energy, we can reparametrize it into the normal form with the following algorithm:

1.  While there is any combination of $\left(p,q\right)\in \mathcal{N}$ and x ∈ {0, 1} that does not satisfy the second condition, repeatedly redefine

$h_{pq}\left(0,x\right)\leftarrow h_{pq}\left(0,x\right)-\delta ,$

(2.51)

$h_{pq}\left(1,x\right)\leftarrow h_{pq}\left(1,x\right)-\delta ,$

(2.52)

$g_q\left(x\right)\leftarrow g_q\left(x\right)+\delta ,$

(2.53)

where δ = min{h_pq(0, x), h_pq(1, x)}.

FIGURE 2.8
The graph construction for the BHS algorithm. The thick arrows indicate the edges in the cut. The graph has, in addition to υ_s and υ_t, two nodes υ_p and ${\upsilon }_{\overline{p}}$ for each site p. We define a correspondence between the cuts of this graph and the output labeling as in (2.61). The assignment is shown at the bottom.

2.  For each $p\in \mathcal{P}$, redefine

$g_p\left(0\right)\leftarrow g_p\left(0\right)-\delta ,$

(2.54)

$g_p\left(1\right)\leftarrow g_p\left(1\right)-\delta ,$

(2.55)

where δ = min{g_p(0), g_p(1)}.

Next, we build a graph $\mathcal{G}=\left(\mathcal{V},ℰ\right)$ as follows (Figure 2.8). Define two nodes for each site plus the two special nodes:

$\mathcal{V}=\left\{{\upsilon }_s,{\upsilon }_t\right\}\cup \left\{{\upsilon }_p,{\upsilon }_{\overline{p}}|p\in \mathcal{P}\right\}.$

(2.56)

There are four edges for each site, and four edges for each neighboring pair of sites:

$ℰ=\left\{e_{s\to p},e_{s\to \overline{p}},e_{p\to t},e_{\overline{p}\to t}|p\in \mathcal{P}\right\}\cup \left\{e_{p\to q},e_{p\to \overline{q}},e_{\overline{p}\to q},e_{\overline{p}\to \overline{q}}|\left(p,q\right)\in \mathcal{N}\right\}.$

(2.57)

Edge weights are defined as follows:

$\begin{array}{cc}{w}_{sp}=w_{\overline{p}t}=\frac{1}{2}{g}_p\left(1\right),& w_{pt}=w_{s\overline{p}}=\frac{1}{2}{g}_p\left(0\right),\end{array}$

(2.58)

$\begin{array}{cc}{w}_{pq}=w_{\overline{q}\overline{p}}=\frac{1}{2}{h}_{pq}\left(0,1\right),& w_{qp}=w_{\overline{p}\overline{q}}=\frac{1}{2}{h}_{pq}\left(1,0\right),\end{array}$

(2.59)

$\begin{array}{cc}{w}_{p\overline{q}}=w_{q\overline{p}}=\frac{1}{2}{h}_{pq}\left(0,0\right),& w_{\overline{q}p}=w_{\overline{p}q}=\frac{1}{2}{h}_{pq}\left(1,1\right).\end{array}$

(2.60)

For this graph, we find a minimum cut $\left(\mathcal{S},\mathcal{T}\right)$ and interpret it as follows:

$\{\begin{array}{ll}p\in \mathcal{Q}\text{and}{X}_p=0\hfill & \text{if}{\upsilon }_p\in \mathcal{S},{\upsilon }_{\overline{p}}\in \mathcal{T}\hfill \\ p\in \mathcal{Q}\text{and}{X}_p=1\hfill & \text{if}{\upsilon }_p\in \mathcal{T},{\upsilon }_{\overline{p}}\in \mathcal{S},\hfill \\ p\notin \mathcal{Q}\hfill & \text{otherwise}.\hfill \end{array}$

(2.61)

As mentioned above, it depends on the actual problem to what extent this algorithm is effective. However, it is worth trying when dealing with nonsubmodular energies, as the construction is straightforward as above. There are also some techniques dealing with the sites that are unlabeled after the use of the algorithm [78].

2.3.5    Reduction of Higher-Order Energies

So far, the energies we dealt with have been of first order (2.15). Also in the vision literature, until recently most problems have been represented in terms of first-order energies, with a few exceptions that consider second-order ones [79, 48, 80]. Limiting the order to one restricts the representational power of the models, the rich statistics of natural scenes cannot be captured by such limited potentials. Higher-order energies can model more complex interactions and reflect the natural statistics better. There are also other reasons, such as enforcing connectivity [81] or histogram [82] in segmentation, for the need of optimizing higher-order energies. This has long been realized [83, 84, 85], and recent developments [86, 87, 88, 89, 90, 91], including various useful special cases of energies are discussed in the next chapter.

Here, we discuss the general binary case and introduce a method [92, 93] to transform general binary MRF minimization problems to the first-order case, for which the preceding methods can be used, at the cost of increasing the number of the binary variables. It is a generalization of earlier methods [48, 94] that allowed the reduction of second-order energies to first order.

An MRF energy that has labels in $\mathbb{B}=\left\{0,1\right\}$ is a function of binary variables

$f:{\mathbb{B}}^n\to ℝ,$

(2.62)

where $n=\left|\mathcal{P}\right|$ is the number of sites/variables. Such functions are called pseudo-Boolean functions (PBFs.) Any PBF can be uniquely represented as a polynomial of the form

$f\left(x_1,\dots ,x_n\right)={\displaystyle \sum _{\mathcal{S}\subset \mathcal{J}}{c}_{\mathcal{S}}}{\displaystyle \prod _{i\in \mathcal{S}}{x}_i},$

(2.63)

where $\mathcal{J}=\left\{1,\dots ,n\right\}$ and $c_{\mathcal{S}}\in ℝ$. We refer the readers to [95, 96] for proof. Combined with the definition of the order, this implies that any binary-labeled MRF of order d − 1 can be represented as a polynomial of degree d. Thus, the problem of reducing higher-order binary-labeled MRFs to first order is equivalent to that of reducing general pseudo-Boolean functions to quadratic ones.

Consider a cubic PBF of variables x, y, z, with a coefficient $a\in ℝ$:

$f\left(x,y,z\right)=axyz.$

(2.64)

The reduction by [48, 94] is based on the following identity:

$xyz=\underset{w\in \mathbb{B}}{\max }w\left(x+y+z-2\right).$

(2.65)

If a < 0,

$axyz=\underset{w\in \mathbb{B}}{\min }aw\left(x+y+z-2\right).$

(2.66)

Thus, whenever axyz appears in a minimization problem with a < 0, it can be replaced by aw(x + y + z − 2).

If a > 0, we flip the variables (i.e., replace x by 1 − x, y by 1 − y, and z by 1 − z) of (2.65) and consider

$\left(1-x\right)\left(1-y\right)\left(1-z\right)=\underset{w\in \mathbb{B}}{\max }w\left(1-x+1-y+1-z-2\right).$

(2.67)

This is simplified to

$xyz=\underset{w\in \mathbb{B}}{\min }w\left(x+y+z-1\right)+\left(xy+yz+zx\right)-\left(x+y+z\right)+1.$

(2.68)

Therefore, if axyz appears in a minimization problem with a > 0, it can be replaced by

$a\left\{w\left(x+y+z-1\right)+\left(xy+yz+zx\right)-\left(x+y+z\right)+1\right\}.$

(2.69)

Thus, either case, the cubic term can be replaced by quadratic terms. As any binary MRF of second order can be written as a cubic polynomial, each cubic monomial in the expanded polynomial can be converted to a quadratic polynomial using one of the formulae above, making the whole energy quadratic, i.e., of the first order. Of course, it does not come free; as we can see, the number of the variables increases.

This reduction works in the same way for higher order if a < 0:

$a{x}_1\dots x_d=\underset{w\in \mathbb{B}}{\min }aw\left\{x_1+\cdots +x_d-\left(d-1\right)\right\}.$

(2.70)

If a > 0, a different formula can be used [92, 93]:

$a{x}_1\cdots x_d=a\underset{w_1,\dots ,w_{n_d}\in \mathbb{B}}{\min }{\displaystyle \sum _{i=1}^{n_d}{w}_i\left(c_{i,d}\left(-S_1+2i\right)-1\right)+a{S}_2},$

(2.71)

where

$\begin{array}{cc}{S}_1={\displaystyle \sum _{i=1}^d{x}_i,}& S_2={\displaystyle \sum _{i=1}^{d-1}{\displaystyle \sum _{j=i+1}^d{x}_i{x}_j}=\frac{S_1\left(S_1-1\right)}{2}.}\end{array}$

(2.72)

are the elementary symmetric polynomials in these variables and

$\begin{array}{cc}{n}_d=\lfloor \frac{d-1}{2}\rfloor ,& c_{i,d}=\{\begin{array}{ll}1\hfill & \text{if}d\text{is}\text{odd}\text{and}i=n_d,\hfill \\ 2\hfill & \text{otherwise}.\hfill \end{array}\end{array}$

(2.73)

Also, both formulas (2.70) and (2.71) can be modified by “flipping” some of the variables before and after transforming the higher-order term to a minimum or maximum [93]. For instance, another reduction for the quartic term can be obtained using the technique: if we define $\overline{x}=1-x$, we have $xyzt=\left(1-\overline{x}\right)yzt=yzt-\overline{x}yzt$. The right-hand side consists of a cubic term and a quartic term with a negative coefficient, which can be reduced using (2.70). This generalization gives rise to an exponential number (in terms of the occurrences of the variables in the function) of possible reductions.

2.4    Multi-Label Minimization

In this section, we deal with the case where there are more than two labels. First we describe the case when global optimization is possible, after which we introduce the move-making algorithms that can approximately minimize more general class of energies.

2.4.1    Globally Minimizable Case: Energies with Convex Prior

Assume that the labels have a linear order:

$\begin{array}{cc}ℒ=\left\{l_0,\dots ,l_k\right\},& k\ge 2.\end{array}$

(2.74)

Also assume that, in the energy (2.15), the pairwise term h_pq(X_p, X_q) is a convex function in terms of the difference of the indices of the labels, i.e., it can be written

$h_{pq}\left(l_i,l_j\right)={\tilde{h}}_{pq}\left(i-j\right)$

(2.75)

with some function ${\tilde{h}}_{pq}\left(x\right)$ that satisfies

$\begin{array}{cc}{\tilde{h}}_{pq}\left(i+1\right)-2{\tilde{h}}_{pq}\left(i\right)+{\tilde{h}}_{pq}\left(i-1\right)\ge 0,& i=1,\dots ,k-1.\end{array}$

(2.76)

In this case, the energy can be minimized globally using the minimum-cut algorithm by constructing a graph similar to the binary case we described in the preceding section [47].

As before, we construct a graph $\mathcal{G}=\left(\mathcal{V},ℰ\right)$ with special nodes υ_s and υ_t (Figure 2.9). For each site $p\in \mathcal{P}$, we define a series of nodes $\left\{{\upsilon }_p^1,\dots ,{\upsilon }_p^k\right\}$:

$\mathcal{V}=\left\{{\upsilon }_s,{\upsilon }_t\right\}\cup \left\{{\upsilon }_p^i|p\in \mathcal{P},i=1,\cdots ,k\right\}.$

(2.77)

For simplicity of notation, let us mean υ_s by ${\upsilon }_p^0$ and υ_t by ${\upsilon }_p^{k+1}$ for any p.

We denote by e_{(p,i)→(q,j)} the directed edge going from ${\upsilon }_p^i$ to ${\upsilon }_q^j$ and by w_{(p, i)(q, j)} its weight. Now we connect the nodes for the same site as follows. The first kind,

${ℰ}_1=\left\{e_{\left(p,i\right)\to \left(p,i+1\right)}|p\in \mathcal{P},i=0,\cdots ,k\right\}$

(2.78)

starts with ${\upsilon }_s={\upsilon }_p^0$ and goes ${\upsilon }_p^1,{\upsilon }_p^2,\dots$ in turn and ends at ${\upsilon }_t={\upsilon }_p^{k+1}$.

To the opposite direction, the second kind of edges

${ℰ}_2=\left\{e_{\left(p,i+1\right)\to \left(p,i\right)}|p\in \mathcal{P},i=1,\cdots ,k-1\right\}$

(2.79)

have infinite weights. In Figure 2.9, they are depicted as dotted arrows. None of them can be in any cut $\left(\mathcal{S},\mathcal{T}\right)$ with finite cost, as in the case shown in the figure; no dotted arrow goes from the $\mathcal{S}$ side to the $\mathcal{T}$ side. In practice, the weight can be some large-enough value. Because of these edges, among the column of edges

FIGURE 2.9
The graph for multilabel MRF minimization. There is a column of nodes and edges for each site. The thick arrows indicate the edges in the cut. We give an infinite weight to the downward dotted arrows, so that exactly one upward edge is in the cut for each column. The label assigned to each site is determined by which one of the upward edge is in the cut (the number on the left). The numbers at the bottom show the labels assigned to each site (column).

${\upsilon }_s={\upsilon }_p^0\to {\upsilon }_p^1\to \dots \to {\upsilon }_p^k\to {\upsilon }_p^{k+1}={\upsilon }_t$

(2.80)

in ${ℰ}_1$ over each site p, exactly one falls in the cut. This can be seen as follows: (1) the first node ${\upsilon }_s={\upsilon }_p^0$ must be in $\mathcal{S}$; (2) the last node ${\upsilon }_t={\upsilon }_p^{k+1}$ must be in $\mathcal{T}$; (3) so there must be at least one edge in the column going from $\mathcal{S}$ to $\mathcal{T}$; (4) but there cannot be two, since to go from $\mathcal{S}$ to $\mathcal{T}$ twice, there must be an edge in the column going from $\mathcal{T}$ to $\mathcal{S}$, but then the opposite edge with infinite weight would be in the cut.

Because of this, we can make a one-to-one correspondence between the cuts and the labelings as follows:

$X_p=l_i\iff {\upsilon }_p^i\in \mathcal{S},{\upsilon }_p^{i+1}\in \mathcal{T}$

(2.81)

Therefore, we can transfer the data terms into cut cost in the similar way as the binary case by defining the weight as follows:

$\begin{array}{cc}{w}_{\left(p,i\right)\left(p,i+1\right)}=g_p\left(l_i\right),& i=0,\dots ,k.\end{array}$

(2.82)

As in the binary case, g_p can be any function, since we can add the same value to all the edges in the column if there is any with negative weight.

For the pairwise term h_pq(X_p, X_q), we first examine the case shown in Figure 2.9. Here, there are horizontal edges between ${\upsilon }_p^i$ and ${\upsilon }_q^i$, with the same “height” i. With these edges

${ℰ}_3=\left\{e_{\left(p,i\right)\to \left(q,i\right)}|\left(p,q\right)\in \mathcal{N},i=1,\dots ,k\right\},$

(2.83)

we complete the construction of the graph by defining the set of edges $ℰ={ℰ}_1\cup {ℰ}_2\cup {ℰ}_3$.

With this graph, if we give a constant positive number κ as weight to edges in ${ℰ}_3$, we have the smoothing term proportional to the difference between i and j:

$h_{pq}\left(l_i,l_j\right)=\kappa \left|i-j\right|.$

(2.84)

Now, assume that (2.75) and (2.76) are satisfied. For simplicity, we assume that l_i = i, (i = 0, ⋯, k). Then the energy can be rewritten:

$E\left(X\right)={\displaystyle \sum _{p\in \mathcal{P}}{g}_p\left(X_p\right)+}{\displaystyle \sum _{\left(p,q\right)\in \mathcal{N}}{\tilde{h}}_{pq}\left(X_p-X_q\right).}$

(2.85)

To minimize more general energies than (2.84), we need edges that are not horizontal (Figure 2.10). That is, for neighboring sites p and q, ${ℰ}_3$ would in general include edges e_{(p, i)→(q, j)} for all combination of i and j. We give them the weight

$w_{\left(p,i\right)\left(q,j\right)}=\frac{1}{2}\left({\tilde{h}}_{pq}\left(i-j+1\right)-2{\tilde{h}}_{pq}\left(i-j\right)+{\tilde{h}}_{pq}\left(i-j-1\right)\right).$

(2.86)

Because of the convexity condition (2.76), this is nonnegative. Without loss of generality, we can assume ${\tilde{h}}_{pq}\left(x\right)={\tilde{h}}_{qp}\left(-x\right)$, because in the energy (2.85), ${\tilde{h}}_{pq}\left(X_p-X_q\right)$ and ${\tilde{h}}_{qp}\left(X_q-X_p\right)$ appear in pairs and thus we can redefine

${{\tilde{h}}^{\prime }}_{pq}\left(x\right)=\frac{{\tilde{h}}_{pq}\left(x\right)+{\tilde{h}}_{qp}\left(-x\right)}{2}$

(2.87)

if necessary.

Now, suppose edges e_{(p, i)→(p, i+1)} and e_{(q,j)→(q, j+1)} are in the cut $\left(\mathcal{S},\mathcal{T}\right)$, i.e., that ${\upsilon }_p^i,{\upsilon }_q^j\in \mathcal{S}$ and ${\upsilon }_p^{i+1},{\upsilon }_q^{j+1}\in \mathcal{T}$. According to (2.81), this means X_p = l_i = i, X_q = l_j = j. Then we see that exactly the edges

$\left\{e_{\left(p,l\right)\to \left(q,m\right)}|0\le l\le i,j+1\le m\le k+1\right\}$

(2.88)

$\left\{e_{\left(q,l\right)\to \left(p,m\right)}|0\le l\le j,i+1\le m\le k+1\right\}$

(2.89)

are in the cut. We calculate the sum of the weights of these edges. First, summing up the weights of the edges in (2.88) (thick arrows in Figure 2.10) according to (2.86), we see most terms cancel out and

FIGURE 2.10
General smoothing edges for multilabel MRF minimization

$\begin{array}{l}{\displaystyle \sum _{l=0}^i{\displaystyle \sum _{m=j+1}^{k+1}{w}_{\left(p,l\right)\left(q,m\right)}}}\hfill \\ =\frac{1}{2}{\displaystyle \sum _{l=0}^i{\displaystyle \sum _{m=j+1}^{k+1}\left({\tilde{h}}_{pq}\left(l-m+1\right)-2{\tilde{h}}_{pq}\left(l-m\right)+{\tilde{h}}_{pq}\left(l-m-1\right)\right)}}\hfill \\ =\frac{1}{2}{\displaystyle \sum _{l=0}^i{\displaystyle \sum _{n=l-k-1}^{l-j-1}\left({\tilde{h}}_{pq}\left(n+1\right)-2{\tilde{h}}_{pq}\left(n\right)+{\tilde{h}}_{pq}\left(n-1\right)\right)}}\hfill \\ =\frac{1}{2}{\displaystyle \sum _{l=0}^i\left[{\displaystyle \sum _{n=l-k}^{l-j}\left({\tilde{h}}_{pq}\left(n\right)-{\tilde{h}}_{pq}\left(n-1\right)\right)-}{\displaystyle \sum _{n=l-k-1}^{l-j-1}\left({\tilde{h}}_{pq}\left(n\right)-{\tilde{h}}_{pq}\left(n-1\right)\right)}\right]}\hfill \\ =\frac{1}{2}{\displaystyle \sum _{l=0}^i\left({\tilde{h}}_{pq}\left(l-j\right)-{\tilde{h}}_{pq}\left(l-k-1\right)-{\tilde{h}}_{pq}\left(l-j-1\right)+{\tilde{h}}_{pq}\left(l-k-2\right)\right)}\hfill \\ =\frac{1}{2}\left({\tilde{h}}_{pq}\left(i-j\right)-{\tilde{h}}_{pq}\left(-j-1\right)-{\tilde{h}}_{pq}\left(i-k-1\right)+{\tilde{h}}_{pq}\left(-k-2\right)\right).\hfill \end{array}$

(2.90)

Similarly, the edges in (2.89) add up to:

$\frac{1}{2}\left({\tilde{h}}_{qp}\left(j-i\right)-{\tilde{h}}_{qp}\left(-i-1\right)-{\tilde{h}}_{qp}\left(j-k-1\right)+{\tilde{h}}_{qp}\left(-k-2\right)\right).$

(2.91)

Adding the two and using ${\tilde{h}}_{pq}\left(x\right)={\tilde{h}}_{qp}\left(-x\right)$, we have the total sum of

${\tilde{h}}_{pq}\left(i-j\right)+r_{pq}\left(i\right)+r_{qp}\left(j\right),$

(2.92)

where

$r_{pq}\left(i\right)=\frac{{\tilde{h}}_{pq}\left(k+2\right)-{\tilde{h}}_{pq}\left(i-k-1\right)-{\tilde{h}}_{pq}\left(i+1\right)}{2}.$

(2.93)

Since r_pq(i) and r_qp(j) depend only on X_p = i and X_q = j, respectively, we can charge them to the data term. That is, instead of (2.82), we use

$w_{\left(p,i\right)\left(p,i+1\right)}=g_p\left(i\right)-{\displaystyle \sum _{\left(p,q\right)\in \mathcal{N}}{r}_{pq}\left(i\right)}.$

(2.94)

and we have the sum above exactly ${\tilde{h}}_{pq}\left(i-j\right)$ which is h_pq(l_i, l_j). Thus the cost of the cut is exactly the same as the energy of the corresponding labeling up to a constant; and we can use the minimum-cut algorithm to obtain the global minimum labeling.

This construction, since it uses the minimum-cut algorithms, in effect encodes the multi-label energy into a binary one and the convexity condition is the result of the submodularity condition. Generalizations have been made in this respect [97, 98, 99, 100], as well as a spatially continuous formulation [101, 102], which improves metrication error and efficiency. There has also been other improvement in time and memory efficiency [103, 104, 105].

2.4.2    Move-Making Algorithms

The above construction requires that the labels have a linear order, as well as that the energy pairwise term be convex. Since many problems do not satisfy the condition, iterative approximation algorithms are used more often in practice.

Move-making algorithms are iterative algorithms that repeatedly moves in the space of labelings so that the energy decreases. In general, the move can go to anywhere in the space, i.e., each site can change its label to any label; so, the best move would be to a global minimum. Since finding the global minimum in the general multi-label case is known to be NP-hard [106], we must restrict the range of possible moves so that finding the best move among them can be done in a polynomial time. The graph-cut optimization in each iteration of move-making algorithms can be thought of as prohibiting some of the labels at each site [107]. Depending on the restriction, this makes the optimization submodular or at least makes the graph much smaller than the full graph in the exact case.

Below, we introduce some of the approximation methods. There are also other algorithms that generalize move-making algorithms [108, 109].

2.4.2.1    α-β Swap and α-Expansion

Here, we first describe α-β swap and α-expansion moves, the two most popular algorithms in vision literature (Figure 2.11).

FIGURE 2.11
Three moves from the original labeling (a). (b) In the conventional one-pixel move (ICM, annealing), one pixel at a time is changed. (c) In α-β swap, two labels α and β are fixed and the sites currently labeled with one of the two are allowed to swap the current label to the other. (d) In α-expansion, one label α is fixed and each site is allowed to change its label to α.

For $\alpha ,\beta \in ℒ$, an α-β swap from a labeling X is a move that allows only those sites labeled α or β by X to change their labels to α or β. That is, a move X → X′ is an α-β swap if

$\begin{array}{ccc}{X}_p\ne X_p^{\prime }& \Rightarrow & X_p,X_p^{\prime }\in \left\{\alpha ,\beta \right\}\end{array}$

(2.95)

is satisfied. Similarly, an α-expansion is a move that allows each site to either switch to label α or remain unchanged, i.e., a move X → X′ is an α-expansion if

$\begin{array}{ccc}{X}_p\ne X_p^{\prime }& \Rightarrow & X_p^{\prime }=\alpha \end{array}$

(2.96)

is satisfied.

What these two moves have in common is that they both can be parametrized by a binary labeling. To see this, define label functions $ℒ\times \left\{0,1\right\}\to ℒ$ by:

$x^{\alpha \beta }\left(l,b\right)=\{\begin{array}{ll}l\hfill & \text{if}l\notin \left\{\alpha ,\beta \right\}\hfill \\ \alpha \hfill & \text{if}l\in \left\{\alpha ,\beta \right\}\text{and}b=0\hfill \\ \beta \hfill & \text{if}l\in \left\{\alpha ,\beta \right\}\text{and}b=1,\hfill \end{array}$

(2.97)

$x^{\alpha }\left(l,b\right)=\{\begin{array}{ll}l\hfill & \text{if}b=0\hfill \\ \alpha \hfill & \text{if}b=1.\hfill \end{array}$

(2.98)

Then the α-β swap and α-expansion moves are defined by site-wise combination of the current labeling X and a binary labeling Y. Fixing X, we evaluate the energy (2.15) after the move:

$E^{\alpha \beta }\left(Y\right)={\displaystyle \sum _{p\in \mathcal{P}}{g}_p\left(x^{\alpha \beta }\left(X_p,Y_p\right)\right)+{\displaystyle \sum _{\left(p,q\right)\in \mathcal{N}}{h}_{pq}\left(x^{\alpha \beta }\left(X_p,Y_p\right),x^{\alpha \beta }\left(X_q,Y_q\right)\right)}}$

(2.99)

$E^{\alpha }\left(Y\right)={\displaystyle \sum _{p\in \mathcal{P}}{g}_p\left(x^{\alpha }\left(X_p,Y_p\right)\right)+{\displaystyle \sum _{\left(p,q\right)\in \mathcal{N}}{h}_{pq}\left(x^{\alpha }\left(X_p,Y_p\right),x^{\alpha }\left(X_q,Y_q\right)\right)}}$

(2.100)

What makes these moves important is that these energies can be shown to be sub-modular under simple criteria. Let us check the submodularity condition (2.39) for energy (2.99). We only have to check the case both X_p and X_q are in {α, β}, as otherwise there is no real pairwise term depending on both Y_p and Y_q. Assuming X_p, X_q ∈ {α, β}, the condition simply translates to:

$h_{pq}\left(\alpha ,\beta \right)+h_{pq}\left(\beta ,\alpha \right)-h_{pq}\left(\alpha ,\alpha \right)-h_{pq}\left(\beta ,\beta \right)\ge 0.$

(2.101)

As for energy (2.100), let us write β = X_p, γ = X_q; then the condition is:

$h_{pq}\left(\beta ,\alpha \right)+h_{pq}\left(\alpha ,\gamma \right)-h_{pq}\left(\beta ,\gamma \right)-h_{pq}\left(\alpha ,\alpha \right)\ge 0.$

(2.102)

Thus, if the energy satisfies (2.101) for all combination of $\alpha ,\beta \in ℒ$, the optimal α-β swap move can always be found using the basic graph-cut algorithm. The algorithm iterate rotating through combinations of α and β in some order, until the energy stops lowering. Similarly, if the energy satisfies (2.102) for all combinations of $\alpha ,\beta ,\gamma \in ℒ$, the optimal α-expansion move can always be found. The algorithm rotates through α till the energy ceases to improve.

An important special case of both (2.101) and (2.102) is when h_pq is a metric, i.e., when conditions

$h_{pq}\left(\alpha ,\beta \right)\ge 0,$

(2.103)

$\begin{array}{ccc}{h}_{pq}\left(\alpha ,\beta \right)=0& \iff & \alpha =\beta \end{array},$

(2.104)

$h_{pq}\left(\alpha ,\beta \right)+h_{pq}\left(\beta ,\gamma \right)\ge h_{pq}\left(\alpha ,\gamma \right),$

(2.105)

$h_{pq}\left(\alpha ,\beta \right)=h_{pq}\left(\beta ,\alpha \right)$

(2.106)

are satisfied. In fact, only the first two are needed to satisfy (2.101); and only the first three would imply (2.102), when it is called a semimetric.

2.4.2.2    Fusion Moves

The fusion move [110, 111] is the most general form of move-making algorithm using binary MRF optimization. In each iteration, define the binary problem as the pixelwise choice between two arbitrary labelings, instead of between the current label and the fixed label α as in the case of α-expansion.

Let X, P be two multilabel labelings; then, the fusion of the two according to a binary labeling Y is the labeling defined by

$F{\left(X,P;Y\right)}_p=\{\begin{array}{ll}{X}_p\hfill & \text{if}{Y}_p=0\hfill \\ P_p\hfill & \text{if}{Y}_p=1,\hfill \end{array}p\in \mathcal{P}.$

(2.107)

In each iteration, a binary-labeled MRF energy is defined as a function of Y, with X and P fixed:

$\widehat{E}\left(Y\right)=E\left(F\left(X,P;Y\right)\right).$

(2.108)

The Y that minimizes this energy is used to find the optimal fusion. As a move-making algorithm, the resulting fusion is often used as X in the next iteration; thus X is treated as the optimization variable, whereas P, called the proposal, is generated in some problem-specific way in each iteration.

Binary labeling problem defined this way is rarely submodular. So it became really useful only after the BHS (QPBO/roof duality) algorithms (Section 2.3.4), which give a partial labeling $Y\in {\mathbb{B}}^{\mathcal{Q}}\left(\mathcal{Q}\subset \mathcal{P}\right)$ to minimization problems of a nonsubmodular energy, was introduced. For fusion, partial solution must be filled to make a full binary labeling Y. The autarky property guarantees that the energy of the fusion labeling F(X, P; 0 ⊳ Y) is not more than that of X, i.e.,

$E\left(F\left(X,\mathcal{P};0⊳Y\right)\right)=\widehat{E}\left(0⊳Y\right)\le \widehat{E}\left(0\right)=E\left(X\right).$

(2.109)

where $0\in {\mathbb{B}}^{\mathcal{P}}$ is a labeling that assigns 0 to all sites. In other words, if we leave the labels unchanged at the sites where Y does not assign any label, the energy does not increase.

In fusion moves, it is crucial for the success and efficiency of the optimization to provide proposals P that fits the energies being optimized. Presumably, α expansion worked so well with the Potts energy because its proposal is the constant labeling. Using the outputs of other algorithms as proposals allows a principled integration of various existing algorithms [80]. In [112], a simple technique based on the gradient of the energy is proposed for generating proposal labelings that makes the algorithm much more efficient.

It is also worth noting that the set of labels can be very large, or even infinite, in fusion move, since the actual algorithm just chooses between two possible labels for each site.

2.4.2.3    α-β Range Moves

The exact minimization algorithm we described in Section 2.4.1 can be used for a class of move-making algorithms [113, 114], called α-β range move algorithms. When the set of labels has a linear order

$ℒ=\left\{l_0,\dots ,l_k\right\},$

(2.110)

they can efficiently minimize first-order energies of the form (2.15) with truncated-convex priors:

$h_{pq}\left(l_i,l_j\right)=\min \left({\tilde{h}}_{pq}\left(i-j\right),\theta \right),$

(2.111)

where ${\tilde{h}}_{pq}$ is a convex function, which satisfies (2.76), and θ a constant. This kind of prior limits the penalty for very large gaps in labels, thereby encouraging such gaps compared to the convex priors, which is sometimes desirable in segmenting images into objects. Here, we only describe the basic algorithm introduced in [113]; for other variations, see [114].

For two labels α = l_i, β = l_j, i < j, the algorithm use the exact algorithm in Section 2.4.1 to find the optimal move among those that allow changing the labels in the range between the two labels at once. A move X → X′ is called an α-β range move if it satisfies

$\begin{array}{ccc}{X}_p\ne X_p^{\prime }& \Rightarrow & X_p,X_p^{\prime }\in \left\{l_i,\dots ,l_j\right\}\end{array}.$

(2.112)

Let d be the maximum integer that satisfies ${\tilde{h}}_{pq}\left(d\right)\le \theta$. The algorithm iterates α-β range moves with α = l_i, β = l_j, j − i = d. Within this range, the prior (2.111) is convex, allowing the use of the exact algorithm. Let X be the current labeling and define

${\mathcal{P}}_{\alpha \text{-}\beta }=\left\{p\in \mathcal{P}|X_p\in \left\{l_i,\dots ,l_j\right\}\right\}.$

(2.113)

Define a graph ${\mathcal{G}}_{\alpha \text{-}\beta }=\left({\mathcal{V}}_{\alpha \text{-}\beta },{ℰ}_{\alpha \text{-}\beta }\right)$ as follows. The node set ${\mathcal{V}}_{\alpha \text{-}\beta }$ contains two special nodes υ_s, υ_t as well as a series of nodes $\left\{{\upsilon }_p^1,\dots ,{\upsilon }_p^d\right\}$ for each site p in ${\mathcal{P}}_{\alpha \text{-}\beta }$. As in Section 2.4.1, let ${\upsilon }_p^0$ be an alias for υ_s, and ${\upsilon }_p^{d+1}$ for υ_t and denote a directed edge from ${\upsilon }_p^n$ to ${\upsilon }_q^m$ by e_{(p,n)→(q,m)}. The edge set ${ℰ}_{\alpha \text{-}\beta }$ contains a directed edge e_{(p,n)→(p,n+1)} for each pair of $p\in {\mathcal{P}}_{\alpha \text{-}\beta }$ and n = 0, 1, …, d, as well as the opposite edge e_{(p, n+1)→(p, n)} with an infinite weight for n = 1, …, d − 1. This, as before, guarantees that exactly one edge among the series

${\upsilon }_s={\upsilon }_p^0\to {\upsilon }_p^1\to \cdots \to {\upsilon }_p^d\to {\upsilon }_p^{d+1}={\upsilon }_t$

(2.114)

over each site p ∈ P_α-β is in any cut with finite cost, establishing a one-to-one correspondence between the cut $\left(\mathcal{S},\mathcal{T}\right)$ and the new labeling:

$X_p^{\prime }=\{\begin{array}{ll}{l}_{i+n}\hfill & \left(\text{if}p\in {\mathcal{P}}_{\alpha \text{-}\beta },{\upsilon }_p^n\in \mathcal{S},{\upsilon }_p^{n+1}\in \mathcal{T}\right)\hfill \\ X_p\hfill & \left(\text{if}p\notin {\mathcal{P}}_{\alpha \text{-}\beta }\right).\hfill \end{array}$

(2.115)

Thus, by defining the weights by

$w_{\left(p,n\right)\left(p,n+1\right)}=g_p\left(l_{i+n}\right)$

(2.116)

the data term is exactly reflected in the cut cost.

As for the smoothing term, any convex ${\tilde{h}}_{pq}$ can be realized by defining edges as in Section 2.4.1. However, that is only if both p and q belong to ${\mathcal{P}}_{\alpha \text{-}\beta }$. Although it can be ignored if neither belongs to ${\mathcal{P}}_{\alpha \text{-}\beta }$, it cannot be if only one does. This is, however, a unary term, as one of the pair has a fixed label. Thus, adding the effect to (2.116), we redefine

$w_{\left(p,n\right)\left(p,n+1\right)}=g_p\left(l_{i+n}\right)+{\displaystyle \sum _{\begin{array}{c}\left(p,q\right)\in \mathcal{N}\\ q\in \mathcal{P}{\mathcal{P}}_{\alpha \text{-}\beta }\end{array}}\min \left({\tilde{h}}_{pq}\left(l_{i+n}-X_q\right),\theta \right)}.$

(2.117)

This way, the cost of a cut of $\left({\mathcal{G}}_{\alpha \text{-}\beta },{\upsilon }_s,{\upsilon }_t\right)$ is the energy of the corresponding labeling by (2.115) up to a constant. Thus, the minimum cut gives the optimal α-β range move.

2.4.2.4    Higher-Order Graph Cuts

Combining the fusion move and the reduction of general higher-order binary energy explained in Section 2.3.5, multiple-label higher-order energies can be approximately minimized [92, 93].

The energy is of the general form (2.13), shown here again:

$E\left(X\right)={\displaystyle \sum _{C\in \mathcal{C}}{f}_C\left(X_C\right)},$

(2.118)

where $\mathcal{C}$ is a set of cliques (subsets) of the set $\mathcal{P}$ of sites, and X_C is the restriction of X to C.

The algorithm maintains the current labeling $X\in {ℒ}^{\mathcal{P}}$. In each iteration, the algorithm fuses X and a proposed labeling $P\in {ℒ}^{\mathcal{P}}$ by minimizing a binary energy. How P is prepared is problem specific, as is how X is initialized at the beginning of the algorithm.

The result of the merge according to a binary labeling $Y\in {\mathbb{B}}^{\mathcal{P}}$ is defined by (2.107) and its energy by (2.108). For the energy E(X) of the form (2.13), the polynomial expression of $\widehat{E}\left(Y\right)$ is

$\widehat{E}\left(Y\right)={\displaystyle \sum _{C\in \mathcal{C}}{\displaystyle \sum _{\gamma \in {\mathbb{B}}^C}{f}_C\left(F\left(X_C,P_C;\gamma \right)\right)}}{\theta }_C^{\gamma }\left(Y_C\right),$

(2.119)

where $F\left(X_C,P_C;\gamma \right)\in {ℒ}^C$ is the fusion labeling on the clique C determined by a binary vector $\gamma \in {\mathbb{B}}^C$:

$F{\left(X_C,P_C;\gamma \right)}_p=\{\begin{array}{cc}{X}_p& \text{if}{\gamma }_p=0\\ {\mathcal{P}}_p& \text{if}{\gamma }_p=1,\end{array}p\in C,$

(2.120)

and ${\theta }_C^{\gamma }\left(Y_C\right)$ is a polynomial of degree |C| defined by

$\begin{array}{cc}{\theta }_C^{\gamma }\left(Y_C\right)={\displaystyle \prod _{p\in C}{Y}_p^{\left(\gamma \right)}},& Y_p^{\left(\gamma \right)}\end{array}=\{\begin{array}{ll}{Y}_p\hfill & \text{if}{\gamma }_p=1\hfill \\ 1-Y_p\hfill & \text{if}{\gamma }_p=0\hfill \end{array}$

(2.121)

which is 1 if Y_C = γ and 0 otherwise.

The polynomial $\widehat{E}\left(Y\right)$ is then reduced into a quadratic polynomial using the technique described in Section 2.3.5. The result is a quadratic polynomial $\tilde{E}\left(\tilde{Y}\right)$ in terms of the labeling $\tilde{Y}\in {\mathbb{B}}^{{\mathcal{P}}^{\prime }}$, where ${\mathcal{P}}^{\prime }\supset \mathcal{P}$. We use the BHS algorithm to minimize $\tilde{E}\left(\tilde{Y}\right)$ and obtain a partial labeling $Z\in {\mathbb{B}}^{{\mathcal{Q}}^{\prime }}$ on a subset ${\mathcal{Q}}^{\prime }$ of ${\mathcal{P}}^{\prime }$. Overwriting the zero labeling 0 by the restriction $Z_{\mathcal{P}\cap {\mathcal{Q}}^{\prime }}$ of Z to the original sites, we obtain $0ᐊZ_{\mathcal{P}\cap {\mathcal{Q}}^{\prime }}$, which we denote by Y_Z. Then we have

$E\left(F\left(X,P;Y_Z\right)\right)=\widehat{E}\left(Y_Z\right)\le \widehat{E}\left(0\right)=E\left(X\right).$

(2.122)

To see why, let us define

$\begin{array}{cc}{y}_0=\left\{\tilde{Y}\in {\mathbb{B}}^{{\mathcal{P}}^{\prime }}|{\tilde{Y}}_{\mathcal{P}}=0\right\},& {\widehat{Y}}_0^{\min }=\arg \underset{\tilde{Y}\in y_0}{\min }\tilde{E}\left(\tilde{Y}\right),\end{array}$

(2.123)

$\begin{array}{cc}{y}_Z=\left\{\tilde{Y}\in {\mathbb{B}}^{{\mathcal{P}}^{\prime }}|{\tilde{Y}}_{\mathcal{P}}=Y_Z\right\},& {\widehat{Y}}_Z^{\min }=\arg \underset{\tilde{Y}\in y_Z}{\min }\tilde{E}\left(\tilde{Y}\right).\end{array}$

(2.124)

Then, by the property of the reduction, we have $\widehat{E}\left(0\right)=\tilde{E}\left({\tilde{Y}}_0^{\min }\right)$ and $\widehat{E}\left(Y_Z\right)=\tilde{E}\left({\tilde{Y}}_Z^{\min }\right)$. Also, if we define $\tilde{Z}={\tilde{Y}}_0^{\min }ᐊZ$, we have $\tilde{E}\left(\tilde{Z}\right)\le \tilde{E}\left({\tilde{Y}}_0^{\min }\right)$ by the autarky property. Since $\tilde{Z}\in y_Z$, we also have $\tilde{E}\left({\tilde{Y}}_Z^{\min }\right)\le \tilde{E}\left(\tilde{Z}\right)$. Thus, $\widehat{E}\left(Y_Z\right)=\tilde{E}\left({\tilde{Y}}_Z^{\min }\right)\le \tilde{E}\left(\tilde{Z}\right)\le \tilde{E}\left({\tilde{Y}}_0^{\min }\right)=\widehat{E}\left(0\right)$.

Therefore, we update X to F(X, P; Y_Z) and (often) decrease the energy. We iterate the process until some convergence criterion is met.

2.5    Examples

Here, we show denoising examples using the multilabel energy minimization techniques described in the previous section. Figure 2.12 shows the results of denoising an image with graph cuts. The original 8-bit grayscale image (a) was added an i. i. d. Gaussian additive noise with standard deviation σ = 50, resulting in the noisy image Y shown in (b).

The result of denoising it by finding X that globally minimizes the “total variation” energy:

$E\left(X\right)={\displaystyle \sum _{p\in \mathcal{P}}{\left(Y_p-X_p\right)}^2+{\displaystyle \sum _{\left(p,q\right)\in \mathcal{N}}\kappa \left|X_p-X_q\right|}}$

(2.125)

with κ = 8.75, using the technique described in Section 2.4.1 and [47], is shown in (c).

The result of denoising Y with the higher-order graph cuts described in Section 2.4.2.4 is shown in (d). For the higher-order energy, we used the recent image statistical model called the fields of experts (FoE) [85], which represents the prior probability of an image X as the product of several Student’s t-distributions:

$P\left(X\right)\propto {\displaystyle \prod _C{\displaystyle \prod _{i=1}^K{\left(1+\frac{1}{2}{\left(J_i\cdot X_C\right)}^2\right)}^{-{\alpha }_i}}},$

(2.126)

where C runs over the set of all n × n patches in the image, and J_i is an n × n filter. The parameters J_i and α_i are learned from a database of natural images. Here, we used the energy

$E\left(X\right)={\displaystyle \sum _{C\in \mathcal{C}}{f}_C\left(X_C\right)},$

(2.127)

FIGURE 2.12
Denoising example. (a) Original image, (b) noise-added image (σ = 50), (c) denoised using the total variation energy, (d) denoised using the higher-order FoE energy.

where the set $\mathcal{C}$ of cliques consists of those cliques formed by singleton pixels and 2 × 2 patches. For the two kinds of cliques, the function f_C is defined by

$\begin{array}{cc}{f}_C\left(X_C\right)=\frac{{\left(Y_p-X_p\right)}^2}{2{\sigma }^2},& \left(C=\left\{p\right\}\right)\end{array}$

(2.128)

$\begin{array}{cc}{f}_C\left(X_C\right)={\displaystyle \sum _{i=1}^3{\alpha }_i\log \left(1+\frac{1}{2}{\left(J_i\cdot X_C\right)}^2\right).}& \left(C\text{is}\text{a}2\times 2\text{patch}\right)\end{array}$

(2.129)

The FoE parameters J_i and α_i for the experiment were kindly provided by Stefan Roth. The energy was approximately minimized using the higher-order graph cuts. We initialized X by Y and then used the following two proposals in alternating iterations: (i) a uniform random image created each iteration, and (ii) a blurred image, which is made every 30 iterations by blurring the current image X with a Gaussian kernel (σ = 0.5625).

2.6    Conclusion

In this chapter, we have provided an overview of the main ideas behind graph cuts and introduced the basic constructions that are most widely used as well as the ones the author is most familiar with.

Further Reading

The research on graph cuts has become extensive and diverse. There are also algorithms other than graph cuts [115, 116, 117] with similar purpose and sometimes superior performance. The interested reader may also refer to other books [118, 119], as well as other chapters of this book and the original papers in the bibliography.