International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B4. Istanbul 2004
consider conflict optimization; (2) consider conflict and position
optimization, but not consider overlap.
Under the situation of only considering conflict, we expressed
the labeling quality with the ratio of non-conflict labels to the
total of labels. We randomly generate 8*5 map sheets of point
feature with 200, 400, 600, 800, 1000, 1200, 1400, 1600 point
features respectively, figure 6 shows the comparison result of
these algorithms. The result in figure 6 is the average of the
labeling results on five maps.
1 &—— 4 i =F :
7 zm T. +.
A *
= 05 ms res
o à
c ~
2 s 4.
B Os!
E
a
a
Et
m. X.
$ 07. |
E Genetic Algonthm
aq
+ et "
= 06} >
= Cibo 4 Nemal Netrork
Lt E
a fy Sinmlated Annealing “Try
E usi AURL
. « Hill Chimbling 5
&———& — Random Algonthm
0.4 i ; A
0 200 400 800 200 1000 1200 1400 1800
Labeling Point Numbers
Figure 6 performance comparison among 5 kinds of algorithms
From the above comparison experiment we can draw two
conclusions.
(1) From figure 6 we find that the solution of genetic algorithm
has the highest quality to the map with the same complexity, the
next is neural network algorithm, the next again is simulated
annealing algorithm and hill climbing algorithm, and the quality
of random algorithm is the lowest, whose labeling quality is the
lowest limit of available solution quality. From the angle of
labeling quality, genetic algorithm> neural network algorithm >
simulated annealing > hill climbing algorithm. Genetic algorithm
has the highest comprehensive performance.
(2) Genetic algorithm introduced in this paper is a kind of robust
and expansible automated labeling algorithm with well-
performance. It possesses the following merits: easy to add the
consideration of other optimization factors, well expansibility.
The encoding form can be determined by problem, and easy to
expand according to problem. In addition genetic algorithm is
very robust, it will not generate invalid solution. The parameters
of genetic algorithm are easy to modulate. Its primary parameters
have been determined by system, the workload of parameter
modulating is very little.
ACKNOWLEDGEMENTS
Thanks for the supporting from Natural Science Fund of
P.R.China (No. 40001019).
References:
Zbigniew Michalewicz, 2000, evolutionary programming, the
press of science.
PanZhengjun, KangLishang, ChenYuping,1998,evolutionary
calculation, the press of tsinghua Univ.
Zhou Ming, Sun Shudong, the principle and application of
Genetic Algorithm, the press of National defense industry.
Herbert Freeman and John Ahn. On the problem of placing
names in a geographic map. Int. J. of Pattern Recog. and Art.
Intell., 1(1):121-140, 1987.
Hiersch,S.A.,'An Algorithm for Automatic Name Placement
Around Point Data.”, 1982, The American Cartographer, vol 9(1)
Imhof, E., 1975, “Positioning Names on Maps”,The American
Cartographer, vol 2(2), pp 128-144
James E. Mower, 1993 “Automated Feature and Name
Placement On Parallel Computers”, Cartography and Geographic
Information Systems, Vol.20(2), pp. 69-82
Jefrey S. Doerschler and H. Freeman. A rule-based system for
dense-map name placement. Comm.of the ACM, 35:68-79, 1992.
Anthony C. Cook and Christopher B. Jones. A Prolog rule-based
system for cartographic name placement. Computer Graphics
Forum, 9(2):109-126, 1990.
Jon Christensen, Joe Marks, and Stuart Shieber. An empirical
study of algorithms for point-feature label placement. ACM
Transactions on Graphics, 14(3):203-232, 1995.
Lee R.Ebinger and M. Goulette,1990,“Noninteractive Automated
Names Placement for the 1990 Decennial Census.”, Cartography
and Geographic Information Systems, Vol. 17(1) , pp. 69-78
Yoeli,P.,1972, “The logic of Automated Map Lettering”, The
cartographical Journal, vol. 9(2),pp.99-108
Christopher B. Jones and Anthony C. Cook. Rule-based name
placement with Prolog. In Proc. Auto-Carto 9, pp 231-240, 1989.
David S. Johnson, Umit Basoglu.,1989,“The Use of Artificial
Intelligence in The Automated Placementof Cartogrphic Names”,
Proceedings of Auto-Carto 9
Doerschler,J.,and H. Freeman,1989,”An Expert System for
Dense-Map Name Placement.” Proceedings of Auto-Carto 9,pp.
215-224
Freeman,H.,J.Ahn.,1984,“AUTOMAP:An Expert System for
Automatic Map Name Placement” Proceedings of the First
International Symposium on Spatial data Handling, pp 544-571
David S. Johnson, Umit Basoglu.,1989,“The Use of Artificial
Intelligence in The Automated Placementof Cartogrphic Names”,
Proceedings of Auto-Carto 9
Doerschler,J.,and H. Freeman,1989,”An Expert System for
Dense-Map Name Placement." Proceedings of Auto-Carto 9,pp.
215-224
John Ahn and Herbert Freeman. AUTONAP - an expert system
for automatic map name placement. In Proceedings International
Symposium on Spatial Data Handling. pages 544-569, 1984
622
OR
KEY
ABS]
SPOT
cover
capab
image
Topo;
The a
a sim
points
image
GCPs
taken.
adjust
when
the m
reduc:
In this
accur:
Remo
Earth,
than a
cost-e
applic
moniti
develc
the v:
obviot
Earth
feature
Up-to-
need
image
to pro
chang
proble
to-date
rapid
orthoii
to mee
