Markov Random Field Models
167
The term in (6.14) is called the posterior energy function. Like in the case of
EMLE, higher and lower values of Epost correspond to lower and higher values
of posterior probabilities. By choosing the configurations X( -8) that minimize
Epost> we actually maximize the posterior probability. In other words, the maximum a posteriori (MAP) criterion is used. Under this criterion, the probability
of error, i. e., that of choosing incorrect classified maps is minimized. We note
that there are other optimization criteria such as the MPM (maximization
of the posterior marginals) developed in Marroguin et al. (1987) that can be
employed. However, the MAP criterion is designed to optimize a statistical
quantity, namely the probability of error. Hence, the MAP criterion is chosen
as the optimization criterion for all the MRF-based image analysis problems
in this book.
Although the MAP criterion is meaningful and powerful in solving various
image analysis problems, it does not provide any systematic method to find
its solutions. If Epost is differentiable and convex (i. e. it has only one saddle
point), any gradient-based optimization algorithm can be used to search for
the MAP solutions. Unfortunately, this is not the case in general. Hence, other
optimization techniques that are capable of handling non-convex functions
must be employed. In the next section, we introduce several optimization
algorithms for finding the MAP solutions.
6.4
Optimization Algorithms
In the previous two sections, we have established the statistical models of the
MRF and its equivalent form, Gibbs field. This model is used to describe spatial
properties of an image. Depending upon the problem at hand, these images can
be classified images (Solberg et al. 1996), noiseless images (Geman and Geman
1984), or change images (Bruzzone and Preito 2000; Kasetkasem and Varshney
2002). Then, based on MAP criterion, the best (optimum) image is chosen. If
the image model is simple, the optimum solution can be determined by using
simple exhaustive search or gradient search approaches. However, since the
MRF model is complex, (i. e. its marginal distribution is non-concave), the
optimum solution under the MAP criterion can no longer be obtained by just
a gradient search approach. Furthermore, for most cases, the image space is
too large for exhaustive search methods to handle in an efficient manner. For
example, there are more than 2 4000 possible binary images (i. e. the intensity
value of a pixel can either be 0 or 1) of size 64 x 64. Hence, the need for more
efficient optimization algorithms is obvious. In this section, we discuss several
optimization algorithms that are widely used for solving MRF model based
image analysis optimization problems. These include the simulated annealing
(SA), Metropolis, and iterated conditional modes (IeM) algorithms.
167
The term in (6.14) is called the posterior energy function. Like in the case of
EMLE, higher and lower values of Epost correspond to lower and higher values
of posterior probabilities. By choosing the configurations X( -8) that minimize
Epost> we actually maximize the posterior probability. In other words, the maximum a posteriori (MAP) criterion is used. Under this criterion, the probability
of error, i. e., that of choosing incorrect classified maps is minimized. We note
that there are other optimization criteria such as the MPM (maximization
of the posterior marginals) developed in Marroguin et al. (1987) that can be
employed. However, the MAP criterion is designed to optimize a statistical
quantity, namely the probability of error. Hence, the MAP criterion is chosen
as the optimization criterion for all the MRF-based image analysis problems
in this book.
Although the MAP criterion is meaningful and powerful in solving various
image analysis problems, it does not provide any systematic method to find
its solutions. If Epost is differentiable and convex (i. e. it has only one saddle
point), any gradient-based optimization algorithm can be used to search for
the MAP solutions. Unfortunately, this is not the case in general. Hence, other
optimization techniques that are capable of handling non-convex functions
must be employed. In the next section, we introduce several optimization
algorithms for finding the MAP solutions.
6.4
Optimization Algorithms
In the previous two sections, we have established the statistical models of the
MRF and its equivalent form, Gibbs field. This model is used to describe spatial
properties of an image. Depending upon the problem at hand, these images can
be classified images (Solberg et al. 1996), noiseless images (Geman and Geman
1984), or change images (Bruzzone and Preito 2000; Kasetkasem and Varshney
2002). Then, based on MAP criterion, the best (optimum) image is chosen. If
the image model is simple, the optimum solution can be determined by using
simple exhaustive search or gradient search approaches. However, since the
MRF model is complex, (i. e. its marginal distribution is non-concave), the
optimum solution under the MAP criterion can no longer be obtained by just
a gradient search approach. Furthermore, for most cases, the image space is
too large for exhaustive search methods to handle in an efficient manner. For
example, there are more than 2 4000 possible binary images (i. e. the intensity
value of a pixel can either be 0 or 1) of size 64 x 64. Hence, the need for more
efficient optimization algorithms is obvious. In this section, we discuss several
optimization algorithms that are widely used for solving MRF model based
image analysis optimization problems. These include the simulated annealing
(SA), Metropolis, and iterated conditional modes (IeM) algorithms.