Markov Random Field Models
175
can take many different values. However, since we used the proposal matrix
G to propose a new configuration at a given site, there is a possibility that
some configurations may not be reachable after completion of a sweep (complete update of all pixels.). This causes the transition matrix to have zero
elements which may jeopardize the positivity conditions required for convergence of the induced Markov chain. As a result, the sufficient conditions for
the Metropolis algorithm must be modified to make the positivity condition
valid. The following definition provides this sufficient condition for a proposal matrix that will guarantee the positivity conditions for the transition
matrix.
Definition: A Markov kernel G on A -8 is called irreducible if for all x, yEA -8
there exists a chain x = uQ, Ul, ••• , Ua(x,y) = Y in A -8 such that G (Uj-l, Uj) > 0 for
1 ::: j ::: a (x,y) < 00. The corresponding homogeneous Markov chain is also
called irreducible as well. Next, we shall call YEA -8 a neighbor of x E A -8 if
G (x,y) > 0, i. e.,
N(x) = {y E A -8 : x # y, G (x,y) > o}
(6.24)
The cooling schedule for the Metropolis algorithm is different from the SA
algorithm due to the fact that, in the SA algorithm, any possible configurations
can be reached after one sweep of an entire image while several sweeps may
be required in the Metropolis algorithm. The optimum cooling schedule is
given by
ul
In(n) ,
where T = max { a (x, y) : x, yEA -8 }.
6.4.3
Iterated Conditional Modes Algorithm
For many remote sensing applications, we often deal with images of very large
size (e.g. data from hyperspectral sensors or high resolution images). These
data are too large for a global optimization algorithm to handle in an efficient
manner, even with highly efficient algorithms such as the SA and Metropolis algorithms. In such cases, it is preferable to deal with a simpler and less
computationally intensive optimization algorithm that may only guarantee
local optima rather than a more accurate and complex global optimization
algorithm (such as the SA and Metropolis algorithms). Among suboptimum
algorithms, the iterated conditional modes (ICM) algorithm, proposed by Begas (1986), has received a great deal of attention because of its simplicity and
fast convergence rate. In this algorithm, the MAP equation is still the objective
function to be optimized. However, unlike the previous two algorithms where
175
can take many different values. However, since we used the proposal matrix
G to propose a new configuration at a given site, there is a possibility that
some configurations may not be reachable after completion of a sweep (complete update of all pixels.). This causes the transition matrix to have zero
elements which may jeopardize the positivity conditions required for convergence of the induced Markov chain. As a result, the sufficient conditions for
the Metropolis algorithm must be modified to make the positivity condition
valid. The following definition provides this sufficient condition for a proposal matrix that will guarantee the positivity conditions for the transition
matrix.
Definition: A Markov kernel G on A -8 is called irreducible if for all x, yEA -8
there exists a chain x = uQ, Ul, ••• , Ua(x,y) = Y in A -8 such that G (Uj-l, Uj) > 0 for
1 ::: j ::: a (x,y) < 00. The corresponding homogeneous Markov chain is also
called irreducible as well. Next, we shall call YEA -8 a neighbor of x E A -8 if
G (x,y) > 0, i. e.,
N(x) = {y E A -8 : x # y, G (x,y) > o}
(6.24)
The cooling schedule for the Metropolis algorithm is different from the SA
algorithm due to the fact that, in the SA algorithm, any possible configurations
can be reached after one sweep of an entire image while several sweeps may
be required in the Metropolis algorithm. The optimum cooling schedule is
given by
ul
In(n) ,
where T = max { a (x, y) : x, yEA -8 }.
6.4.3
Iterated Conditional Modes Algorithm
For many remote sensing applications, we often deal with images of very large
size (e.g. data from hyperspectral sensors or high resolution images). These
data are too large for a global optimization algorithm to handle in an efficient
manner, even with highly efficient algorithms such as the SA and Metropolis algorithms. In such cases, it is preferable to deal with a simpler and less
computationally intensive optimization algorithm that may only guarantee
local optima rather than a more accurate and complex global optimization
algorithm (such as the SA and Metropolis algorithms). Among suboptimum
algorithms, the iterated conditional modes (ICM) algorithm, proposed by Begas (1986), has received a great deal of attention because of its simplicity and
fast convergence rate. In this algorithm, the MAP equation is still the objective
function to be optimized. However, unlike the previous two algorithms where