168
Initial Image
Find visiting scheme
{S"S2, ... }' set T~ To
and h ~ 1.
For sj,tind
ElmJx(s)) for all
possible x(s)
Select a new x based
on the above
probabilities.
h~h+1.
Reduce Tby a
predetermined schedule.
Move to a new site
NO
Is h > hmax ?
If yes, stop
Fig. 6.2. Block diagram of the simulated annealing algorithm
6.4.1
Simulated Annealing
6: Teerasit Kasetkasem
The SA algorithm, shown in Fig. 6.2, is a computationally efficient mathematical tool for the implementation of the MAP detector/estimator because
a direct search in the configuration space is computationally expensive for
large images. The idea of the SA algorithm is to generate a random sequence
of configurations (images) that eventually converges to solutions of the MAP
problem. This method involves an inhomogeneous Markov chain and its timedependent Markov kernel. The inhomogeneity is introduced via the temperature parameter. Here, the temperature decreases as the number of updates
increases. In the limit, it eventually reaches zero when the number of times
a site is visited approaches infinity. Before going into the details of the SA
algorithm, we shall investigate the statistical behavior of the Gibbs field for
arbitrarily low temperatures.
Proposition 6.1 Let TTT(r) = 1 exp (- +E(x)) be a Gibbs distribution. Then
.)
lim TTT(X) = { Ilxmll If X E ~m ,
(6.15)
1
T -+0
0
otherwIse
where Xm denotes the set of all minima of E, and lIall denotes the cardinality of a set a.