Markov Random Field Models
161
the equivalence property between MRFs and Gibbs fields. Next, some possible
approaches to employ MRF modeling are examined in Sect. 6.3. Here, we also
construct the posterior energy function under the MAP criterion, which is
used as an objective function for optimization problems. Then, several widely
used optimization methods including simulated annealing are introduced and
discussed in Sect. 6.4. Some theoretical results are also presented in this section
to make this chapter self-contained.
6.2
MRF and Gibbs Distribution
6.2.1
Random Field and Neighborhood
Consider a stochastic sequence, {xn}n>O. It is said to have the Markov property
if for n ::: 1, Xn is statistically independent of {Xb k = 0, 1, ... , n - 2} given Xn-1.
This suggests a local dependency among adjacent time slots. In more general
cases, we can extend the notion of dependency to multiple dimensions. But,
before defining the MRF in multidimensional systems, we need to first define
some terms (Winkler 1995).
6.2.1.1
Random Field
Let -8 = {SI' S2, ... ,SM} be a finite set. An element denoted by S E -8 is called
a site. Let il be a finite set called a phase or configuration space. A random field
on -8 with phase il is defined as a collection X = {X{s)} SEJ of random variables
X{s) taking values in the phase space il.
A random field can be viewed as a random variable or a random vector
taking values in the configuration space il J . A configuration x E il J is of the
form x = (x{s),s E -8), where x{s) E il for all s E -8. We note that, in image
processing applications, -8 is normally a subset ofZ2 andil represents different
intensity values of the image where Z is the set of all integers. Our particular
interest in this chapter is on a Markov random field, which is characterized by
local interactions. As a result, we need to introduce a neighborhood system on
the sites.
6.2.1.2
Neighborhood
A neighborhood system on -8 is a family N = {NS}SEJ of subsets of -8 such that
for all s E -8,
i) s t. Ns
ii) tENs ::::} SENt
161
the equivalence property between MRFs and Gibbs fields. Next, some possible
approaches to employ MRF modeling are examined in Sect. 6.3. Here, we also
construct the posterior energy function under the MAP criterion, which is
used as an objective function for optimization problems. Then, several widely
used optimization methods including simulated annealing are introduced and
discussed in Sect. 6.4. Some theoretical results are also presented in this section
to make this chapter self-contained.
6.2
MRF and Gibbs Distribution
6.2.1
Random Field and Neighborhood
Consider a stochastic sequence, {xn}n>O. It is said to have the Markov property
if for n ::: 1, Xn is statistically independent of {Xb k = 0, 1, ... , n - 2} given Xn-1.
This suggests a local dependency among adjacent time slots. In more general
cases, we can extend the notion of dependency to multiple dimensions. But,
before defining the MRF in multidimensional systems, we need to first define
some terms (Winkler 1995).
6.2.1.1
Random Field
Let -8 = {SI' S2, ... ,SM} be a finite set. An element denoted by S E -8 is called
a site. Let il be a finite set called a phase or configuration space. A random field
on -8 with phase il is defined as a collection X = {X{s)} SEJ of random variables
X{s) taking values in the phase space il.
A random field can be viewed as a random variable or a random vector
taking values in the configuration space il J . A configuration x E il J is of the
form x = (x{s),s E -8), where x{s) E il for all s E -8. We note that, in image
processing applications, -8 is normally a subset ofZ2 andil represents different
intensity values of the image where Z is the set of all integers. Our particular
interest in this chapter is on a Markov random field, which is characterized by
local interactions. As a result, we need to introduce a neighborhood system on
the sites.
6.2.1.2
Neighborhood
A neighborhood system on -8 is a family N = {NS}SEJ of subsets of -8 such that
for all s E -8,
i) s t. Ns
ii) tENs ::::} SENt