International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B4. Istanbul 2004
3. Forbid and avoid overlap: Point label should not overlap the
important linear feature of the same color such as railways and
major roads etc, While overlap is unavoidable, efforts should be
made to decrease it.
a
B 4H 5 d
Sol] € =,
7^ n 3 8
(c)
Figure 1 the candidate labeling position of point feature
This paper studies the labeling problem of the following two
kinds of point features mainly. The algorithm of solving four-
candidate-position is easy to expand to apply in the situations of
5, 8 and n candidate-position.
Problem I: consider the point feature in map, if adopting four-
candidate-position labeling mode, namely choosing the right, top,
left and bottom four candidate positions of point feature
respectively (as indicated in figure 1(a), the distance between
label and point residence is Imm), try designing and
implementing labeling algorithm to make globally conflict least.
In the actual labeling problem, besides considering eliminating
label conflict, also need to consider dodging important map
features and choosing the candidate point with higher-priority,
thus the above problem becomes more complicated problem as
follow.
Problem II: consider the point feature in map, if adopting four-
candidate-position labeling mode, namely choose the right, top,
left and bottom four candidate positions of point feature
respectively (as indicated in figure 1(a), the distance between
label and point residence is 1mm), try designing and
implementing labeling algorithm, make globally conflict least,
the overlap to other features minimum and the labeling position
optimal.
IV. GENETIC ALGORITHM OF SOLVING POINT
FEATURE LABELING
Genetic Algorithm was developed by Professor J.H.Holland, his
fellows and his students in Michican University of U.S.A, in the
sixties of the twentieth century. At present it has been applied to
solve various optimal problems, such as layout scheme, self-
adaptive control, game rules, pattern cognition, transportation
problem, travelling salesman problem, optimal control and
database query optimal, etc, most of them are famous NP-
complete problems[Zhou Ming, 1999 ].
The biology has been always evolving according to the rule of
"survival of the fittest" and natural genetics course, genetic
algorithm is exactly the randomized calculating model originated
from simulating the biological evolution course. In the solving
course, genetic algorithm always keeps a population of potential
solution. Begin from one initial population, through selection,
crossover and mutating to produce the next generation
population, in this way seek the optimal solution generation after
generation until meeting the terminating condition. In order to
solve one given problem, genetic algorithm must go through the
following five steps generally [Zbigniew Michalewicz, 2000]:
(1) Determine the encoding framework;
(2) Generate initial population;
(3) Determine the fitness function;
(4) Design genetic operator, including selection, crossover and
mutate operators;
(5) Determine the important parameters of genetic algorithm.
Because genetic algorithm is an all-purpose algorithm with
extensive applicability, in design often need combine itself with
the special rule of problem domain. In application course, we
have put forward some optimization strategies according to the
characteristics of labeling problem and has improved the
performance of the algorithm greatly. The remains of this paper
will in detail introduce our genetic algorithm and some crucial
design theories and optimization strategies adopted by our
genetic algorithm.
4.1 Determine encoding framework
The map label is the optimization target of genetic algorithm.
One of the map placements can be expressed with a integer
vector. Each component represents the localization of one label.
Assumed there are m candidate positions, which can be
expressed with codes of 0—m-1, for instance when considering
four-position label, the four candidate positions can be expressed
with the codes of 0-3.
Encode the map label placement with integer vector, and a piece
of chromosome is a integer vector representing an instance of a
map label placement. The length of chromosome is n (the
number of point features label), and every component (gene)
represents one point feature label, the domain of gene is [0, m-1],
where m is the number of candidate positions, the gene code set
of four-candidate-point labeling problem is.(0,. 1, 2, 31. Now
figure 2 give an example, it shows a map with twenty point
features, one placements of this map and the corresponding
chromosome encoding.
ets” di
[-
FE 15 ,
Cia 17 «CU
«CT 19 CU
6 se 10
LX Burr.
S 4017 HE sm
n*L7—]
r= ye
CT] 3 Seu 1]
LA)
chromosome codes:
00231020100030132010
Figure2 Point feature labeling placement and its encoding
4.2 Generate initial population
According to the characteristic of labeling problem, the
following strategies to generate initial population was adopted.
(1) Randomly generate an initial population with certain size,
and randomly select every gene for the chromosome.
(2) According to the characteristic of labeling problem, for all
free labels (when selecting optimal position for them, overlap
and conflict never appear), in initial population select the optimal
positions for the corresponding genes of all chromosomes.
618
Intei
The
posi
solv
redu
evol
4.3 I
The
the |
the |
first
cons
prior
the c
calci
of st
thus
the :
cons
fitne:
thou;
diffe
functi
targe
LE
First
optin
defin
fit(
Eco
Whe
defin
label
and {|
This
whicl
fitnes
better
2. Th
Now
optim
confli
functi
E(L;
I
+
fit(L
Where
The m
