9.3.1
Here we describe a special GNC algorithm, called annealing labeling [Li et al. 1994], which may be used to improve the optimization of the posterior energy (5.18) formulated for the MAP matching.
We first do an energy-gain conversion ( cf. Section 8.2.2). Substituting (5.11), (5.12), (5.16) and (5.17) into (5.18), we have
where 
is the number of NULL
labels
in f, and 
is the number of label pairs at least one of which is NULL
.
The constants 
and 
control the number of sites assigned
the NULL
label. The smaller they are, the more sites will be assigned
the NULL
. The corresponding gain function is
In the above, 
, 
, and
and 
are related to 
and 
by (8.26) and
(8.27). These determines the compatibilities in RL. The gain is
to be maximized.
The parameters 
and 
not only affect the NULL
labels
but also the local behavior of the maximization algorithm. When both are
zero, there will be no NULL
labels. The larger their values. the more
sites will be assigned the NULL
and the more serious the problem of
local maxima becomes. In other words, we found that a labeling f, in
which 
for some i, is likely a local optimum and that the
labeling f, in which 
for all i, is a deep local optimum.
This has motivated us to incorporate a heuristic annealing procedure
into the labeling process, in a way similar to the graduated
non-convexity (GNC) algorithm [Blake and Zisserman 1987], to overcome the
local optimum problem.
Introduce a temperature parameter into the gain
with 
. T is initially set to a very
high value 
and gradually lowered towards
. The maximum 
obtained at 
is used as
the initial value for the next new phase of maximization at 
.
In this way, the 
are tracked from high T to low T. Because
and 
are weighted by 
, the optimum 
obtained at high T is less affected by the local optimum problem; when
it is tracked down, a better quality solution may be obtained than one
found by a non-annealing algorithm. The improvement of annealing
labeling ICM, a procedure incorporating annealing labeling into ICM,
over the simple ICM will be shown shortly.
Note that the T in the annealing labeling acts on only the prior part whereas in SA, T acts on both the prior and likelihood parts. So the present annealing procedure is more like GNC [Blake and Zisserman 1987] than SA [Geman and Geman 1984].
