数字地图注记自动定位方法的智能优化
|
摘要
近年来,随着经济建设的快速发展,人们对地图的应用越来越广泛,要求也越来越高,地图更新的速度越来越快,从而使地图注记自动配置就显得尤为重要。除此以外,计算机、网络和信息技术的发展,促使世界各国加快了测绘技术信息化进程。如何利用计算机进行地图注记自动配置,提高地图生产效率,已经成为影响和制约GIS应用和发展的一个迫切需要解决的问题。本论文目的在于提高地图自动注记系统的自动化程度和注记质量,降低人工干预和人工编辑的作业量,力求解决实际生产中的问题,促使地图注记自动配置研究成果实用化。
本文首先深入了解了当前国内外地图自动注记的研究动态,在详细阐述了地图注记配置的理论、方法、规则的基础上,对现有的方法进行分析研究,重点讨论了在地形图中的占主要比例的点状要素,道路、河流、等高线等线状要素,以及居民地、湖泊等面状要素的注记自动配置的推理方法,并给出了相应的实现算法。
对应用在注记自动配置中的人工智能算法进行了讨论,简单介绍了禁忌搜索算法,重点论述了人工神经网络和遗传算法。并分析了各算法的优缺点。
在研究过程中,为了实际需要把网格划分,遗传算法,拓扑等方法运用到算法设计和实现的过程中,对算法本身进行了优化,提高了计算效率。对算法的优化和完善是本文所研究的核心重点。
最后,对研究内容进行了实践检测,将所采用或设计的方法用C#和VC++结合编程实现并应用到NewMap DMP制图软件中,完成其注记的自动配置系统。
In recent years, with the rapid development of economic construction, it is widely applied on the map, thus, requiring much more high-quality and efficiency of map contents updates, which has made automatical configuration of the map notes become particularly important. In addition, computer, network and information technology have led many countries to accelerate the process of information-based of surveying and mapping technology. How to use computers process the Automated Placement of map notes and improve the efficiency of map production has already become a key factor and issue needed to solved imminently, which has also influenced and restricted the application and development of Geographic Information System (GIS). The purpose of this paper is to improve the quality of map notes and the degree of the automatic map notes system, reduce the amount of work of human intervention and manual editing, strive to solve practical problems in the production and also prompt the practicality of the production of map auto-configuration research.
Firstly, in-depth understanding of the current domestic and international research dynamics on map automated placement, elaborated on the map in the configuration note the theory, methods, rules, based on existing methods of analysis and research focused on the topographic map accounted for the major proportion of the point feature, roads, rivers, contour lines and other linear elements, as well as residential areas, lakes and other area feature automatic configuration Note reasoning, and the corresponding algorithm.
Notes on the application of the automatic configuration of the artificial intelligence algorithms were discussed, a brief introduction of the tabu search algorithm, with emphasis on artificial neural networks and genetic algorithms. And analyzes the advantages and disadvantages of each method. In the course of the study, to the actual needs of the mesh, genetic algorithms, topology and other methods applied to algorithm design and implementation process of the algorithm itself has been optimized to improve the computational efficiency. Optimization and improvement of the algorithm is the core focus of this paper.
Finally, the practice test was carried out on the research contents of this paper by programming with VC++, methods and algorithms of the results of research work was applied to the NewMap DMP mapping software, accomplishing its auto-configuration system on map notes.
本文首先深入了解了当前国内外地图自动注记的研究动态,在详细阐述了地图注记配置的理论、方法、规则的基础上,对现有的方法进行分析研究,重点讨论了在地形图中的占主要比例的点状要素,道路、河流、等高线等线状要素,以及居民地、湖泊等面状要素的注记自动配置的推理方法,并给出了相应的实现算法。
对应用在注记自动配置中的人工智能算法进行了讨论,简单介绍了禁忌搜索算法,重点论述了人工神经网络和遗传算法。并分析了各算法的优缺点。
在研究过程中,为了实际需要把网格划分,遗传算法,拓扑等方法运用到算法设计和实现的过程中,对算法本身进行了优化,提高了计算效率。对算法的优化和完善是本文所研究的核心重点。
最后,对研究内容进行了实践检测,将所采用或设计的方法用C#和VC++结合编程实现并应用到NewMap DMP制图软件中,完成其注记的自动配置系统。
In recent years, with the rapid development of economic construction, it is widely applied on the map, thus, requiring much more high-quality and efficiency of map contents updates, which has made automatical configuration of the map notes become particularly important. In addition, computer, network and information technology have led many countries to accelerate the process of information-based of surveying and mapping technology. How to use computers process the Automated Placement of map notes and improve the efficiency of map production has already become a key factor and issue needed to solved imminently, which has also influenced and restricted the application and development of Geographic Information System (GIS). The purpose of this paper is to improve the quality of map notes and the degree of the automatic map notes system, reduce the amount of work of human intervention and manual editing, strive to solve practical problems in the production and also prompt the practicality of the production of map auto-configuration research.
Firstly, in-depth understanding of the current domestic and international research dynamics on map automated placement, elaborated on the map in the configuration note the theory, methods, rules, based on existing methods of analysis and research focused on the topographic map accounted for the major proportion of the point feature, roads, rivers, contour lines and other linear elements, as well as residential areas, lakes and other area feature automatic configuration Note reasoning, and the corresponding algorithm.
Notes on the application of the automatic configuration of the artificial intelligence algorithms were discussed, a brief introduction of the tabu search algorithm, with emphasis on artificial neural networks and genetic algorithms. And analyzes the advantages and disadvantages of each method. In the course of the study, to the actual needs of the mesh, genetic algorithms, topology and other methods applied to algorithm design and implementation process of the algorithm itself has been optimized to improve the computational efficiency. Optimization and improvement of the algorithm is the core focus of this paper.
Finally, the practice test was carried out on the research contents of this paper by programming with VC++, methods and algorithms of the results of research work was applied to the NewMap DMP mapping software, accomplishing its auto-configuration system on map notes.
引文
[1]周继成,周青山,韩飘扬.人工神经网络——第六代计算机的实现[M].北京:科学普及出版社,1993.
[2]张立明.人工神经网络的模型及其应用[M].上海:复旦大学出版社,1993.
[3] Hopfield J J. Neurons with graded response have collective compuatation properties like those of two state neurons. Proc. Natl. Acad. Sci. U. S. A., 1984, 81(5):3088-3092.
[4]张青贵.人工神经网络导论[M].北京:中国水利水电出版社,2004.
[5]陈允平.人工神经网络原理及其应用[M].北京:中国电力出版社,2002.
[6]马锐.人工神经网络原理[M].北京:机械工业出版社,2010.
[7]丁士圻,郭丽华.人工神经网络基础[M].哈尔滨:哈尔滨工程大学,2008.
[8]梁学斌,吴立德.Hopfield型神经网络的全局指数稳定性及应用.中国科学(A),1995,25(2):523-532.
[9]廖晓昕.论Hopfield神经网络的数学内蕴.中国科学(E),2003,32(2):127-136.
[10] Miller W T.Real-time application of neural networks for sensor-based control of robots with vision[J].IEEE Trans.System,Man,Cybern.,1989,(19):825-831.
[11]焦李成.神经网络计算[M].西安:西安电子科技大学出版社,1993.
[12]魏海坤.神经网络结构设计的理论与方法[M].北京:国防工业出版社,2005.
[13]米凯利维茨Z[美].演化程序——遗传算法和数据编码的结合[M].北京:科学出版社,2000.
[14]邢文训,谢金星.现代优化计算方法[M].北京:清华大学出版社,2003.
[15] Gen M,Cheng R W.Genetic algorithms and engineering design[M].New York:John Wiley and Sons,1997.
[16] Grefenstette J J.Optimization of Control Parameters for Genetic Algorithms[M]. IEEE Trans. on AMC,1986,16(1),122-128.
[17]张文修,梁怡.遗传算法的数学基础[M].西安:西安交通大学出版社,2000.
[18]王小平,曹立明.遗传算法——理论、应用与软件实现[M].西安:西安交通大学出版社,2002.
[19]王凌.智能优化算法及其应用[M].北京:清华大学出版社,2001.
[20]周明,孙树栋.遗传算法原理及应用[M].北京:国防工业出版社,2002.
[21]蔡自兴,徐光佑.人工智能及其应用[M].北京:清华大学出版社,2003.
[22]普雷帕拉塔F P,沙莫斯M I.计算几何[M].北京:科学出版社,1992.
[23] AH罗宾逊等.地图学原理[M].北京:测绘出版社,1989.
[24]黄杏元,马劲松,汤勤.地理信息系统概论[M].北京:高等教育出版社,1990.
[25]郭达志,盛业华,余兆平.地理信息系统基础与应用[M].北京:煤炭工业出版社.
[26]樊红,刘开军,张祖勋.基于遗传算法的点状要素注记的整体最优配置[M].武汉大学学报,2002,27(6):560-565.
[27]贾伟凤,曾囡莉,廖晓昕.关于Hopfield型神经网络稳定性的注记[J].华中科技大学学报,2003,31(8),74-76.
[28]樊红,张祖勋,杜道生等.基于神经网络模型求取注记配置最优解[J].武汉测绘科技大学学报,1998,23(1):32-35.
[29]刘树安,吕帅.地图文本注记问题的遗传算法求解[J].控制工程,2007,14(2),129-131.
[30]张红武,张友纯,谢忠等.用遗传算法解决点状要素的自动注记问题[J].计算机工程与应用,2003,7,68-77.
[31]韩炜,廖振鹏.关于遗传算法收敛性的注记[J].地震工程与工程振动,1999,19(4),13-16.
[32]杨勇,邓淑丹,李霖等.基于禁忌搜索的点状注记研究[J].测绘科学,2007,32(6),46-48.
[33]郑春燕,郭庆胜,刘小利。基于禁忌搜索算法的点状要素注记的自动配置[J].武汉大学学报,2006,31(5),428-431.
[34]樊红,杜道生,张祖勋.地图注记自动配置规则及其实现策略[J].武汉测绘科技大学学报,1998,24(2),154-157.
[35]贾新宇,陆志一. Polyline线的抽稀与圆滑[J].信息技术,2006,2006,7,145-146.
[36]樊红,张祖勋,杜道生.地图注记质量评价模型的研究[J].测绘学报,2004,33(4),362-366.
[37]贺彪,李霖,朱海红.数字制图中面状注记自动配置的研究[J].测绘信息与工程,2007,32(6),12-14.
[38]刘小利.城市地形图注记自动配置子系统的设计与实现[D].武汉大学硕士学位论文,2005.
[39]雷明军.地图线状要素注记自动配置的研究[D].武汉大学硕士学位论文,2005.
[40]耿留勇.地图注记自动配置研究及其在AutoCAD地图制图中的应用[D].成都理工大学硕士学位论文,2007.
[41]娄倩.电子地图动态注记的设计与实现[D].解放军信息工程大学硕士学位论文,2007.
[42]杨凌云.电子地图动态注记的研究和实现[D].中国地质大学硕士学位论文,2007.
[43]樊红.地图注记自动配置研究[M].北京:测绘出版社,2004
[44]邓红艳,武芳,李铭等.遗传算法在点注记自动配置中的应用[J].测绘学院学报,2003,20(1),69-72.
[45]吴信才.地理信息系统的基本技术与发展动态[J].地球科学,1998,23(4),329-333.
[46] HumPhreys P,Freedman D.The grand leap[J].British Journal for the Philosophy of science,1999,47,113-118.
[47] Hnas Pual Schwefel,Frank Kusrwae.Solving Map Labeling Problems by Means of Evolution Strategies[J].Diplomarbeit Fachbeerieh Informatik der Universitat Dortmumd.1998,2(19),1-73.
[48] James E M.Automated Feature and Name Placement On Parallel Computers[J]. Cartography and Geographic Information Systems,1993,20(2),69-82.
[49] YOeli P.The Logic of Auotmated Map Lettering[J].The Cartogrphical Journal,1972,9(2),99-108.
[50] Cook A C,Jones C B.A Prolog Rule2Based System for Cartographic Name Placement[J]. Computer Graphics Forum,1990,9(2),109-126.
[51] Steven Zoraster.Integer Programming Applied To The Map Label Placement Problem[J].Cartographic a,1986,23(3),16-27.
[2]张立明.人工神经网络的模型及其应用[M].上海:复旦大学出版社,1993.
[3] Hopfield J J. Neurons with graded response have collective compuatation properties like those of two state neurons. Proc. Natl. Acad. Sci. U. S. A., 1984, 81(5):3088-3092.
[4]张青贵.人工神经网络导论[M].北京:中国水利水电出版社,2004.
[5]陈允平.人工神经网络原理及其应用[M].北京:中国电力出版社,2002.
[6]马锐.人工神经网络原理[M].北京:机械工业出版社,2010.
[7]丁士圻,郭丽华.人工神经网络基础[M].哈尔滨:哈尔滨工程大学,2008.
[8]梁学斌,吴立德.Hopfield型神经网络的全局指数稳定性及应用.中国科学(A),1995,25(2):523-532.
[9]廖晓昕.论Hopfield神经网络的数学内蕴.中国科学(E),2003,32(2):127-136.
[10] Miller W T.Real-time application of neural networks for sensor-based control of robots with vision[J].IEEE Trans.System,Man,Cybern.,1989,(19):825-831.
[11]焦李成.神经网络计算[M].西安:西安电子科技大学出版社,1993.
[12]魏海坤.神经网络结构设计的理论与方法[M].北京:国防工业出版社,2005.
[13]米凯利维茨Z[美].演化程序——遗传算法和数据编码的结合[M].北京:科学出版社,2000.
[14]邢文训,谢金星.现代优化计算方法[M].北京:清华大学出版社,2003.
[15] Gen M,Cheng R W.Genetic algorithms and engineering design[M].New York:John Wiley and Sons,1997.
[16] Grefenstette J J.Optimization of Control Parameters for Genetic Algorithms[M]. IEEE Trans. on AMC,1986,16(1),122-128.
[17]张文修,梁怡.遗传算法的数学基础[M].西安:西安交通大学出版社,2000.
[18]王小平,曹立明.遗传算法——理论、应用与软件实现[M].西安:西安交通大学出版社,2002.
[19]王凌.智能优化算法及其应用[M].北京:清华大学出版社,2001.
[20]周明,孙树栋.遗传算法原理及应用[M].北京:国防工业出版社,2002.
[21]蔡自兴,徐光佑.人工智能及其应用[M].北京:清华大学出版社,2003.
[22]普雷帕拉塔F P,沙莫斯M I.计算几何[M].北京:科学出版社,1992.
[23] AH罗宾逊等.地图学原理[M].北京:测绘出版社,1989.
[24]黄杏元,马劲松,汤勤.地理信息系统概论[M].北京:高等教育出版社,1990.
[25]郭达志,盛业华,余兆平.地理信息系统基础与应用[M].北京:煤炭工业出版社.
[26]樊红,刘开军,张祖勋.基于遗传算法的点状要素注记的整体最优配置[M].武汉大学学报,2002,27(6):560-565.
[27]贾伟凤,曾囡莉,廖晓昕.关于Hopfield型神经网络稳定性的注记[J].华中科技大学学报,2003,31(8),74-76.
[28]樊红,张祖勋,杜道生等.基于神经网络模型求取注记配置最优解[J].武汉测绘科技大学学报,1998,23(1):32-35.
[29]刘树安,吕帅.地图文本注记问题的遗传算法求解[J].控制工程,2007,14(2),129-131.
[30]张红武,张友纯,谢忠等.用遗传算法解决点状要素的自动注记问题[J].计算机工程与应用,2003,7,68-77.
[31]韩炜,廖振鹏.关于遗传算法收敛性的注记[J].地震工程与工程振动,1999,19(4),13-16.
[32]杨勇,邓淑丹,李霖等.基于禁忌搜索的点状注记研究[J].测绘科学,2007,32(6),46-48.
[33]郑春燕,郭庆胜,刘小利。基于禁忌搜索算法的点状要素注记的自动配置[J].武汉大学学报,2006,31(5),428-431.
[34]樊红,杜道生,张祖勋.地图注记自动配置规则及其实现策略[J].武汉测绘科技大学学报,1998,24(2),154-157.
[35]贾新宇,陆志一. Polyline线的抽稀与圆滑[J].信息技术,2006,2006,7,145-146.
[36]樊红,张祖勋,杜道生.地图注记质量评价模型的研究[J].测绘学报,2004,33(4),362-366.
[37]贺彪,李霖,朱海红.数字制图中面状注记自动配置的研究[J].测绘信息与工程,2007,32(6),12-14.
[38]刘小利.城市地形图注记自动配置子系统的设计与实现[D].武汉大学硕士学位论文,2005.
[39]雷明军.地图线状要素注记自动配置的研究[D].武汉大学硕士学位论文,2005.
[40]耿留勇.地图注记自动配置研究及其在AutoCAD地图制图中的应用[D].成都理工大学硕士学位论文,2007.
[41]娄倩.电子地图动态注记的设计与实现[D].解放军信息工程大学硕士学位论文,2007.
[42]杨凌云.电子地图动态注记的研究和实现[D].中国地质大学硕士学位论文,2007.
[43]樊红.地图注记自动配置研究[M].北京:测绘出版社,2004
[44]邓红艳,武芳,李铭等.遗传算法在点注记自动配置中的应用[J].测绘学院学报,2003,20(1),69-72.
[45]吴信才.地理信息系统的基本技术与发展动态[J].地球科学,1998,23(4),329-333.
[46] HumPhreys P,Freedman D.The grand leap[J].British Journal for the Philosophy of science,1999,47,113-118.
[47] Hnas Pual Schwefel,Frank Kusrwae.Solving Map Labeling Problems by Means of Evolution Strategies[J].Diplomarbeit Fachbeerieh Informatik der Universitat Dortmumd.1998,2(19),1-73.
[48] James E M.Automated Feature and Name Placement On Parallel Computers[J]. Cartography and Geographic Information Systems,1993,20(2),69-82.
[49] YOeli P.The Logic of Auotmated Map Lettering[J].The Cartogrphical Journal,1972,9(2),99-108.
[50] Cook A C,Jones C B.A Prolog Rule2Based System for Cartographic Name Placement[J]. Computer Graphics Forum,1990,9(2),109-126.
[51] Steven Zoraster.Integer Programming Applied To The Map Label Placement Problem[J].Cartographic a,1986,23(3),16-27.