3. Classification Algorithm
Once the cluster centers have been estimated, the whole image set is classified by assigning
labels to every pixel. The label, l=1, . . . m, is an integer value and represents classes. If the
classification is carried out according to only the condition that the Euclidean distance between
the data vector and the cluster center reaches a minimum, some regions appear somewhat
mottled, with isolated pixels of one class embedded within larger regions of another class, i.e.,
mixed-up classes. Generally, one expects neighboring pixels to belong to the same class unless
there is a true border between regions. Thus, we assume the field of labels is a Markov Random
Field (MRF): the probability of a pixel to be labeled k knowing the labels of all other pixels in
the image is equal to the probability of a pixel to be labeled k knowing the labels of its neighbors.
The classification is realized by minimizing an energy function. It consists of its own energy U1
and energy U2 related to its neighborhood N. For each pixel, i, U1 and U2 are defined as
where ß is a weighting factor ( ß
³0) and
d is the Kroeneker symbol:
and N represents the neighborhood structure. Usually, the number of pixels within a
neighborhood structure is predefined. The shape, in contrast, is not fixed, but is adapted to data.
Here, the neighborhood structure is a 5*1 window with different orientations (shown in Fig. 1).
One of the neighborhood structures is selected on which the variance of the data has the
minimum value. Thus, by using the adaptive windows we take into account the local
homogeneity and improve the detail preservation.
A classification is optimal if the global energy E over the whole image
is minimum. Global minimization is achieved by a simulated annealing approach.
Fig. 1 Neighborhood structures for classification algorithm
4. Simulated Annealing Algorithm
The concept of simulated annealing (SA) is based on an analogy between the thermodynamic
behavior of solids and large combinatorial optimization. The basic procedure involves a cooling
procedure, in which a þ temperature þ parameter starts out high and is gradually lowered until
the system is þ frozen þ (in a state of minimal energy). In the simulated annealing algorithm, not
only are state changes accepted which decrease energy, but also some state changes are accepted
which increase energy with a defined probability. However, the lower the temperature, the less
likely is any significant energy increase.
Simulated Annealing algorithm is implemented as follows
1) Choose initial temperature T
0, assign the class label to every pixels randomly
2) Repeat
For each pixel, change randomly its label from class i to class j,
Compute
DU
ij=E
i-E
j and accept the change,
when
DU
ij 0, or, with a probability exp
(-
DU
ij/T),
when
DU
ij>0,
T
new=u*Told (0 <u <1),
Until T
new <Tend where T
end is the freezing temperature.
