Page 181 -

160 3 Image processing

f (i, j+1)

d (i, j) f (i+1, j+1)

w(i, j) s y(i, j)

f (i, j) s x(i, j) f (i+1, j)

Figure 3.56 Graphical model for an N 4 neighborhood Markov random field. (The blue edges are added for an
N 8 neighborhood.) The white circles are the unknowns f(i, j), while the dark circles are the input data d(i, j).
The s x (i, j) and s y (i, j) black boxes denote arbitrary interaction potentials between adjacent nodes in the random
field, and the w(i, j) denote the data penalty functions. The same graphical model can be used to depict a discrete
version of a first-order regularization problem (Figure 3.55).

where N(i, j) denotes the neighbors of pixel (i, j). In fact, the general version of the theorem
says that the energy may have to be evaluated over a larger set of cliques, which depend on
the order of the Markov random field (Kindermann and Snell 1980; Geman and Geman 1984;
Bishop 2006; Kohli, Ladick´ y, and Torr 2009; Kohli, Kumar, and Torr 2009).
The most commonly used neighborhood in Markov random field modeling is the N 4
neighborhood, where each pixel in the field f(i, j) interacts only with its immediate neigh-
bors. The model in Figure 3.56, which we previously used in Figure 3.55 to illustrate the
discrete version of first-order regularization, shows an N 4 MRF. The s x (i, j) and s y (i, j)
black boxes denote arbitrary interaction potentials between adjacent nodes in the random
field and the w(i, j) denote the data penalty functions. These square nodes can also be inter-
preted as factors in a factor graph version of the (undirected) graphical model (Bishop 2006),
which is another name for interaction potentials. (Strictly speaking, the factors are (improper)
probability functions whose product is the (un-normalized) posterior distribution.)
As we will see in (3.112–3.113), there is a close relationship between these interaction
potentials and the discretized versions of regularized image restoration problems. Thus, to
a first approximation, we can view energy minimization being performed when solving a
regularized problem and the maximum a posteriori inference being performed in an MRF as
equivalent.
While N 4 neighborhoods are most commonly used, in some applications N 8 (or even
higher order) neighborhoods perform better at tasks such as image segmentation because
they can better model discontinuities at different orientations (Boykov and Kolmogorov 2003;
Rother, Kohli, Feng et al. 2009; Kohli, Ladick´ y, and Torr 2009; Kohli, Kumar, and Torr 2009).

Binary MRFs

The simplest possible example of a Markov random field is a binary field. Examples of such
fields include 1-bit (black and white) scanned document images as well as images segmented
into foreground and background regions.
To denoise a scanned image, we set the data penalty to reflect the agreement between the