Markov Random Field Models
171
After determining a visiting scheme and a cooling schedule, the algorithm
sets the temperature to the initial value, say To, and either randomly or deterministically picks an initial configuration (image X). Then, a sweep of an
entire image is performed. During a sweep, the algorithm visits a site at a time
until all sites are visited. Without loss of generality, we assume that a site 51
is being visited. Here, the algorithm computes the energy Bpost for all possible configurations at 51 while keeping the configurations at all the other sites
fixed. As a result, a set of posterior probabilities associated with all the possible
configurations at 51 is obtained. Next, a new configuration at 51 is generated
based on the computed posterior probabilities (e.g. if Ppost (x (51) = 0) = 0.7
and P post (x (51) = 1) = 0.3, then there are 70% and 30% chances that the new
configuration at 51 is 0 or 1, respectively). After the update at 51> the algorithm moves to the next site in the visiting scheme, increases the counter, and
decreases the temperature parameter. The above procedure is repeated until
the counter exceeds a predetermined value at which point the algorithm is
terminated.
In general, the cooling schedule given in (6.19) is computationally not feasible. For instance, when L1 = 1 and M = 64 x 64, it will take more than
e 4000 sweeps before the temperature reduces to 1 from the lower bound given
by (6.19). Therefore, in practice, we usually start with a much lower temperature (e. g. between 1 and 5) so that the steady state is reached sooner. Of course,
this violates the condition given in (6.19) and, therefore, convergence is not
guaranteed. But in most cases, we are able to start from initial images that are
fairly close to one of the minima of E such that the SA procedure converges in
a reasonable amount of time.
Example
We present a simple example to illustrate the implementation of the SA algorithm. In this example, we consider a Gibbs field that consists of two sites {I, 2}
whose configurations can be either -lor 1. The Gibbs distribution associated
with this system is given by
where
{
-I
I(a,b)= 1
if a = b
if a i b
(6.20)
(6.21)
and Z = L
L exp (-I (XI, X2)) = 6.17. The prior probabilities assox2={-1,1} xl={-I,I}
ciated with each configuration can be computed from (6.20) and are given in
Table 6.1.
Furthermore, let us assume that the realization of the configuration is {I, I},
but because of identical, independent Gaussian noise with zero mean and
unit variance, we actually obtain the real number {YI>Y2} = {0.5,-0.15}. The
171
After determining a visiting scheme and a cooling schedule, the algorithm
sets the temperature to the initial value, say To, and either randomly or deterministically picks an initial configuration (image X). Then, a sweep of an
entire image is performed. During a sweep, the algorithm visits a site at a time
until all sites are visited. Without loss of generality, we assume that a site 51
is being visited. Here, the algorithm computes the energy Bpost for all possible configurations at 51 while keeping the configurations at all the other sites
fixed. As a result, a set of posterior probabilities associated with all the possible
configurations at 51 is obtained. Next, a new configuration at 51 is generated
based on the computed posterior probabilities (e.g. if Ppost (x (51) = 0) = 0.7
and P post (x (51) = 1) = 0.3, then there are 70% and 30% chances that the new
configuration at 51 is 0 or 1, respectively). After the update at 51> the algorithm moves to the next site in the visiting scheme, increases the counter, and
decreases the temperature parameter. The above procedure is repeated until
the counter exceeds a predetermined value at which point the algorithm is
terminated.
In general, the cooling schedule given in (6.19) is computationally not feasible. For instance, when L1 = 1 and M = 64 x 64, it will take more than
e 4000 sweeps before the temperature reduces to 1 from the lower bound given
by (6.19). Therefore, in practice, we usually start with a much lower temperature (e. g. between 1 and 5) so that the steady state is reached sooner. Of course,
this violates the condition given in (6.19) and, therefore, convergence is not
guaranteed. But in most cases, we are able to start from initial images that are
fairly close to one of the minima of E such that the SA procedure converges in
a reasonable amount of time.
Example
We present a simple example to illustrate the implementation of the SA algorithm. In this example, we consider a Gibbs field that consists of two sites {I, 2}
whose configurations can be either -lor 1. The Gibbs distribution associated
with this system is given by
where
{
-I
I(a,b)= 1
if a = b
if a i b
(6.20)
(6.21)
and Z = L
L exp (-I (XI, X2)) = 6.17. The prior probabilities assox2={-1,1} xl={-I,I}
ciated with each configuration can be computed from (6.20) and are given in
Table 6.1.
Furthermore, let us assume that the realization of the configuration is {I, I},
but because of identical, independent Gaussian noise with zero mean and
unit variance, we actually obtain the real number {YI>Y2} = {0.5,-0.15}. The