04 
and 
vith 
vith 
we 
the 
the 
per 
cial 
our 
hm. 
>ger 
bel. 
be 
ring 
ssed 
iece 
of a 
(the 
ene) 
1-1], 
set 
Now 
oint 
ding 
the 
sd. 
size, 
or all 
'erlap 
timal 
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXX V, Part B4. Istanbul 2004 
The above initial population strategy has selected the optimal 
positions for free labels. That means free label's position can be 
solved without through optimal process. It also means the 
reduction of the scale of problem and the acceleration of the 
evolvement of genetic algorithm. 
4.3 Determine the fitness function 
The target of labeling problem is to find the label placement with 
the highest quality. Therefore the fitness function is defined as 
the labeling quality evaluation function. Here adopt such a way: 
first define a labeling quality evaluation function which 
considers these factors including conflict, overlap, position 
priority and so on, now adopt the way of marking, namely mark 
the conflict, overlap and position priority of each label, and then 
calculate the total score of each label through weighted average 
of summation, finally, calculate the summation of all the labels, 
thus obtain the score of the whole labeling placement. The higher 
the score is, the higher the labeling quality is, this is exactly 
consistent with the meaning of the fitness function (the larger the 
fitness value is, the better the individual is). According to this 
thought, by referring to the demands of optimization target of 
different labeling problems, define the corresponding fitness 
function. Now introduce it with two examples of optimization 
targets. 
|. The least conflict target 
First consider the point labeling problem I; it only considers the 
optimization target of least conflict. Under this kind of situation, 
define of the fitness function see equation (1). 
N 
füu(L) = x Econfliet (Li) (D) 
i=) 
V/f(ViO« j «n, j &i,dj(Li, L;) » 0) 
Eontidii- DIN i (2) 
otherwise 
Where E 
conflict (L) is 0-1 conflict evaluation function whose 
definition is shown in expression (2), in which L, represents the 
label of i-th point feature, when there is no conflict between L, 
and the other labels the function equals 1, otherwise it equals 0. 
This kind of fitness function is defined as the sum of the labels 
which don't overlap with other labels. By using this kind of 
fitness function, genetic algorithm can solve the global conflict 
better. 
2. The target of the least conflict, overlap and optimal position 
Now consider the point labeling problem II, it has three 
optimization targets, and the fitness function needs to consider 
conflict, overlap and position priority, therefore define the fitness 
function as equation (3): 
E(L;) = E(Lj j) 
WoverlapEoverlap Li, j,BF)  if(L; ,j-don't.Conflict) 
7 | *positionE position ^4, j) 
0 otherwise 
  
J 
fI) S X EQ) (3) 
j=] 
Where we let W, = 100: We ET. 
The meaning of every symbol is as follows: 
ver | ay sition 
E L. .. BFE represents the overlap evaluation value when 
overldy i.j? 
L is on the candidate position J, if adopting simple overlap 
evaluation function, it is defined as the highest importance 
weight of the features overlapped with the label, when there is no 
overlap, BL L BFE €99, the higher the importance of 
overlaid feature is, the severer the overlap is, accordingly the 
lower the overlap score is. BF ; represents the j-th background 
feature overlaid by the label; the predicate overlap 0 0.) 
indicates the two objects O, ; O, overlap with each other. Now 
define E eni L. .BFE as 
ij? 
Ep verlap(Li,BF) = 
Í 99 
|99 — max (W (BF;) | overlap(L;, BF;) ^ BF; e BF] with..overlap 
(4) 
In equation (4), W (BF j ) represents the importance evaluation 
no...overlap 
function defined by background feature (it value called 
importance grade or weight). Similarly adopting the mark system 
0~99, the score of the feature which can’t be overlaid is 99, the 
lower the importance, the lower the score is, the score of the 
feature with the lowest importance is 0. Now define W (BF, ) 
as equation (5): 
0 the minimal | importance 
W(BFj)-41—98 the median importance (5) 
99 the maximal importance 
i L Erepresents the position evaluation value when L. 
1, 
is on the candidate position / , adopt sorted position evaluation 
function, and is calculated according to equation (6). When the 
candidate positions are finite and can be enumerated (such as 
four-position labeling or eight-position labeling). We sort them 
Pos ,(L;) 
in the descending order of their priority, let 
position of rr. 
represents the j-th labeling j 
Order(Pos , (L, ) represents the order number of candidate 
position after sorting, we can define the position evaluation 
function as the difference of 99 and Order(P Os A LY : 
Namely the score of the position with the highest priority is 99, 
the scores of the other positions decrease in order. The definition 
of F £ LE see equation (6): 
posi t i 
E position (Li) = 99 — Order(Pos j(Lj 6) 
By adopting this kind of fitness function, genetic algorithm not 
only solves conflict but also solve the optimization of the overlap 
and position priority. 
In addition, if only consider the target of least conflict and most 
optimal position, let Ww, 0 in equation (3), then 
ver | ay = 
We can have equation (7): 
619