基于能量最小化原理的地图要素移位算法研究与改进
发布时间：2018-08-18 16:59
【摘要】：随着计算机技术的飞速发展和地理信息系统在地图制图领域中的广泛应用,对数字环境下地图综合自动化的需要越来越紧迫。地图自动综合是地图学与GIS(Geographic information system)领域的一个难题。一些复杂地图综合算子,如移位、典型化等的自动化程度仍然较低。尽管国内外学者对地图综合移位算法进行了长期不懈的探索,但目前仍存在诸多问题没得到有效解决,突出表现为以下几个方面：(a)移位是多种制图综合规则约束下的最优化问题,但现有算法对各类制图综合规则的考虑还不够充分；(b)已有移位算法中的各数学模型、参数条件与地图综合规则约束之间的对应关系还有待进一步研究；(c)地图目标(群)的空间关系与空间结构一致性的保持仍然是移位操作的难点。针对以上问题,本文从地图综合中图形空间冲突解决的实际需求出发,分析了地图目标间邻近冲突产生的机理和移位操作的本质特征,围绕Beams和Snakes能量最小化移位算法,对地图中道路和建筑物等要素的空间冲突识别和移位展开深入研究,通过模型和算法的改进,提高地图自动综合中移位操作的自动化和智能化水平,为数字环境下的地图自动综合提供有效的技术手段。论文主要研究内容如下：(1)从地图综合移位操作的基本概念出发,分析了地图目标之间图形空间冲突的产生机理。在归纳和总结面向移位算子的地图综合约束条件的基础上,给出了一种移位算法概念框架,并阐述了能量最小化移动算法的基本原理和数学模型,奠定了本文研究的理论基础。(2)通过对SDS (Simplicial data structure)地图数据模型的扩展,构建了一种包含点、线和面三类地图要素的CDT (Constrained Delaunay triangulation)地图数据模型。模型中明确定义了地图目标之间的空间邻近关系,并且实现了各类地图目标(群)间空间邻近搜索、骨架线提取、空间邻近冲突识别等算法,从而为移位算法中邻近冲突的识别及其空间上下文的描述、地图目标(群)空间关系与空间结构一致性的保持提供辅助数据模型。(3)提出了一种顾及道路要素等级属性和道路弯曲图形特征的Snakes模型形状参数设置方法。基于Snakes的能量最小化移位算法的移位效果一定程度上受控于模型形状参数(弹性参数a和刚性参数β),但目前仍缺乏定量化的参数设置方法。针对该问题,以道路网的移位为例,分别建立了Snakes模型形状参数与道路等级属性和与道路内部各段弯曲曲率之间的定量化关系,从而更好地顾及了道路的等级属性特征和图形特征,增强了Snakes模型中形状参数设置的适应性和可控性。(4)对Beams能量最小化移位算法提出了三个方面的改进：(a)在降低参数复杂度的情况下,提出了一种Beams模型材料参数自动设置方法,从而提高了算法的自动化水平；(b)通过对移位过大的目标施加吸引力,增强了算法对地图目标位置精度的控制作用；(c)采用了一种新的迭代策略,将每一次迭代的中间结果作为新的输入调用下一次的迭代过程,从而将模型中的“内能”重置为0,提高了算法解决冲突的能力。(5)将改进后Beams移位算法与辅助地图数据模型相结合,针对建筑物群和道路网两类典型地图要素的移位问题,分别设计了两种空间辅助结构支持下的移位算法：(a)邻近图支持下的建筑物群移位算法：(b)增强型道路网支持下的道路要素移位算法。在建筑物群移位算法中,基于CDT骨架线构建了表达建筑物群空间分布特征的邻近图,并利用局部建筑物分组信息对邻近图进行调整,从而能从全局和局部两个层次保持建筑物群的空间关系和空间分布特征；在道路要素移位算法中,进一步拓展了空间辅助结构对移位操作的支持作用,构建了一种增强型道路网,使发生移位的道路路段附近的建筑物以及邻近的其它路段与之建立关联,同时提出了一种以冲突点为中心的移位操作区划分方法,从而保证移位变形能够在比较合适的范围内得到充分传播,更好地保持道路与其邻近地图目标的空间关系与空间分布特征。(6)基于GIS二次开发组件ArcGIS Engine,实现了论文中所提出的模型和算法,并选用多套典型的道路网与建筑物群地图要素数据验证了所实现算法的有效性和优越性。
[Abstract]:With the rapid development of computer technology and the wide application of geographic information system in the field of cartography, the need for map generalization automation in digital environment is becoming more and more urgent. Although scholars at home and abroad have made a long-term and unremitting exploration on the map synthesis shift algorithm, there are still many problems that have not been effectively solved, which are highlighted in the following aspects: (a) Shift is an optimization problem constrained by a variety of cartographic synthesis rules, but the existing algorithms for all kinds of cartography. Consideration of synthesis rules is insufficient; (b) the corresponding relations between mathematical models, parameters and constraints of map synthesis rules in existing shift algorithms need to be further studied; (c) it is still difficult to maintain the consistency between spatial relations and spatial structures of map objects (groups). Starting from the actual demand of graph space conflict resolution in graph synthesis, this paper analyzes the mechanism of adjacent conflict between map objects and the essential characteristics of displacement operation. Focusing on Beams and Snakes energy minimization displacement algorithm, this paper studies the spatial conflict recognition and displacement of road and building elements in map deeply. Through model and algorithm The main contents of this paper are as follows: (1) Based on the basic concepts of map synthesis shift operation, the mechanism of spatial conflict between map objects is analyzed. On the basis of summarizing the constraints of map synthesis oriented to shift operator, a conceptual framework of shift algorithm is given, and the basic principle and mathematical model of energy minimization algorithm are expounded, which lays the theoretical foundation of this paper. (2) By extending the SDS (Simplicial data structure) map data model, a new shift algorithm is constructed. In this model, the spatial proximity between map objects is clearly defined, and the algorithms of spatial proximity search, skeleton line extraction and spatial proximity conflict recognition among various map objects (groups) are implemented, so as to calculate the displacement. (3) A shape parameter setting method for Snakes model is proposed, which takes into account the grade attribute of road elements and the characteristics of road curved graphics. The displacement effect of the method is controlled to a certain extent by the shape parameters of the model (elastic parameter a and rigid parameter beta), but there is still no quantitative parameter setting method at present. Thus, the hierarchical attributes and graphical features of the road are taken into account, and the adaptability and controllability of shape parameter setting in Snakes model are enhanced. (4) Three improvements are proposed to the Beams energy minimization shift algorithm: (a) A Beams model material parameter automation algorithm is proposed to reduce the complexity of the parameters. Setting method improves the automation level of the algorithm; (b) Applying attraction to the object with too large displacement enhances the control effect of the algorithm on the position accuracy of the map object; (c) Adopting a new iterative strategy, calling the intermediate result of each iteration as a new input to the next iteration process, thus making the model (5) Combining the improved Beams shift algorithm with the auxiliary map data model, two kinds of displacement algorithms supported by spatial auxiliary structures are designed for the displacement problem of two typical map elements, building group and road network: (a) the construction supported by adjacent map Building Group Shifting Algorithm: (b) Road Element Shifting Algorithm Supported by Enhanced Road Network. In Building Group Shifting Algorithm, a neighborhood map expressing the spatial distribution characteristics of buildings is constructed based on CDT skeleton line, and the neighborhood map is adjusted by using local building grouping information, so that the construction can be maintained at both global and local levels. In the algorithm of road element displacement, the supporting effect of spatial auxiliary structure on displacement operation is further expanded, and an enhanced road network is constructed to correlate buildings near displaced road sections and other adjacent roads. The method of dividing the shift operation area centered on the conflict points ensures that the displacement deformation can be fully propagated in a suitable range and better maintains the spatial relationship and spatial distribution characteristics between the road and its adjacent map objects. (6) Based on ArcGIS Engine, the model and algorithm proposed in this paper are implemented. The validity and superiority of the algorithm are verified by several typical road network and building group map data.
【学位授予单位】：武汉大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：P208
本文编号：2190108
[Abstract]:With the rapid development of computer technology and the wide application of geographic information system in the field of cartography, the need for map generalization automation in digital environment is becoming more and more urgent. Although scholars at home and abroad have made a long-term and unremitting exploration on the map synthesis shift algorithm, there are still many problems that have not been effectively solved, which are highlighted in the following aspects: (a) Shift is an optimization problem constrained by a variety of cartographic synthesis rules, but the existing algorithms for all kinds of cartography. Consideration of synthesis rules is insufficient; (b) the corresponding relations between mathematical models, parameters and constraints of map synthesis rules in existing shift algorithms need to be further studied; (c) it is still difficult to maintain the consistency between spatial relations and spatial structures of map objects (groups). Starting from the actual demand of graph space conflict resolution in graph synthesis, this paper analyzes the mechanism of adjacent conflict between map objects and the essential characteristics of displacement operation. Focusing on Beams and Snakes energy minimization displacement algorithm, this paper studies the spatial conflict recognition and displacement of road and building elements in map deeply. Through model and algorithm The main contents of this paper are as follows: (1) Based on the basic concepts of map synthesis shift operation, the mechanism of spatial conflict between map objects is analyzed. On the basis of summarizing the constraints of map synthesis oriented to shift operator, a conceptual framework of shift algorithm is given, and the basic principle and mathematical model of energy minimization algorithm are expounded, which lays the theoretical foundation of this paper. (2) By extending the SDS (Simplicial data structure) map data model, a new shift algorithm is constructed. In this model, the spatial proximity between map objects is clearly defined, and the algorithms of spatial proximity search, skeleton line extraction and spatial proximity conflict recognition among various map objects (groups) are implemented, so as to calculate the displacement. (3) A shape parameter setting method for Snakes model is proposed, which takes into account the grade attribute of road elements and the characteristics of road curved graphics. The displacement effect of the method is controlled to a certain extent by the shape parameters of the model (elastic parameter a and rigid parameter beta), but there is still no quantitative parameter setting method at present. Thus, the hierarchical attributes and graphical features of the road are taken into account, and the adaptability and controllability of shape parameter setting in Snakes model are enhanced. (4) Three improvements are proposed to the Beams energy minimization shift algorithm: (a) A Beams model material parameter automation algorithm is proposed to reduce the complexity of the parameters. Setting method improves the automation level of the algorithm; (b) Applying attraction to the object with too large displacement enhances the control effect of the algorithm on the position accuracy of the map object; (c) Adopting a new iterative strategy, calling the intermediate result of each iteration as a new input to the next iteration process, thus making the model (5) Combining the improved Beams shift algorithm with the auxiliary map data model, two kinds of displacement algorithms supported by spatial auxiliary structures are designed for the displacement problem of two typical map elements, building group and road network: (a) the construction supported by adjacent map Building Group Shifting Algorithm: (b) Road Element Shifting Algorithm Supported by Enhanced Road Network. In Building Group Shifting Algorithm, a neighborhood map expressing the spatial distribution characteristics of buildings is constructed based on CDT skeleton line, and the neighborhood map is adjusted by using local building grouping information, so that the construction can be maintained at both global and local levels. In the algorithm of road element displacement, the supporting effect of spatial auxiliary structure on displacement operation is further expanded, and an enhanced road network is constructed to correlate buildings near displaced road sections and other adjacent roads. The method of dividing the shift operation area centered on the conflict points ensures that the displacement deformation can be fully propagated in a suitable range and better maintains the spatial relationship and spatial distribution characteristics between the road and its adjacent map objects. (6) Based on ArcGIS Engine, the model and algorithm proposed in this paper are implemented. The validity and superiority of the algorithm are verified by several typical road network and building group map data.
【学位授予单位】：武汉大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：P208
【相似文献】
相关期刊论文 前10条
1 王晓东;解非线性0-1规划的一个算法及其在结构优化中的应用[J];数值计算与计算机应用;1988年01期
2 张晓;;基于密度聚类算法的异常检测[J];伊犁师范学院学报(自然科学版);2010年04期
3 陈沐天;找周期子字的算法[J];应用数学学报;1991年01期
4 丁才昌;方勃;鲁小平;;分布估计算法及其性能研究[J];武汉大学学报(理学版);2005年S2期
5 石明兰;杨晖;叶东毅;;面向目标的关联规则挖掘的一个FP增长算法[J];集美大学学报(自然科学版);2006年02期
6 张维群;;基于海量数据关联效应测度算法的设计[J];统计与信息论坛;2012年07期
7 罗蕾,徐洪利;构造Dn-最优确切设计的优化方法──离散算法[J];辽宁大学学报(自然科学版);1999年02期
8 贺永恒;王斌;;基于蚁群算法的候选标签子集构造方法研究[J];中国科技信息;2014年06期
9 武小悦,沙基昌;构造网络不交化最小路集的一种新算法[J];系统工程理论与实践;2000年01期
10 姜建国;刘永青;刘梦楠;王国林;李f ;;类电磁机制算法研究与改进[J];计算力学学报;2014年01期
相关会议论文 前2条
1 潘志明;郑骏;钱卫宁;周傲英;;构造XML相似相关结构库的一种有效方法[A];第二十届全国数据库学术会议论文集（技术报告篇）[C];2003年
2 林景亮;董槐林;姜青山;吴书;;一种基于新增阈值的频繁模式挖掘算法[A];第二十三届中国数据库学术会议论文集（研究报告篇）[C];2006年
相关博士学位论文 前9条
1 张磊;基于概念格的角色工程相关算法研究[D];哈尔滨工业大学;2015年
2 孟静;新型Krylov子空间算法及其应用研究[D];电子科技大学;2015年
3 胡芳;复杂网络节点中心性多元评估与社团探测新算法研究[D];华中师范大学;2015年
4 肖建元;保几何结构算法在等离子体物理中的应用[D];中国科学技术大学;2017年
5 刘远刚;基于能量最小化原理的地图要素移位算法研究与改进[D];武汉大学;2015年
6 唐益明;（1，，2，2）型异蕴涵泛三I算法及其应用研究[D];合肥工业大学;2011年
7 牛云云;求解计算困难问题的膜计算模型与算法研究[D];华中科技大学;2012年
8 李冬冬;基因组序列标注的算法与理论研究[D];国防科学技术大学;2004年
9 周琨;航空公司航班运行调度模型与算法研究[D];南京航空航天大学;2012年
相关硕士学位论文 前10条
1 闫铭;基于度量学习的不完整数据聚类方法研究[D];哈尔滨工业大学;2015年
2 张小琼;基于改进萤火虫群优化算法的BP神经网络研究[D];广西大学;2015年
3 李俊杰;基于蚁群算法的聚类区分器设计研究[D];电子科技大学;2014年
4 艾慧;天波雷达电离层污染校正与测高算法研究[D];电子科技大学;2015年
5 陈红强;大规模并行排序学习算法研究[D];西安电子科技大学;2014年
6 郭艳茹;k-中心平面聚类模型与算法研究[D];浙江工业大学;2015年
7 彭辉辉;基于压缩感知的心电信号压缩算法研究[D];东南大学;2015年
8 葛娜;高效用项集动态挖掘算法的研究[D];中北大学;2016年
9 叶馨;闭项集挖掘算法在医保目录制定问题上的研究与应用[D];中国科学技术大学;2016年
10 张靓云;面向微博的事件摘要生成算法研究与实现[D];西南交通大学;2016年
本文编号：2190108
本文链接：https://www.wllwen.com/kejilunwen/dizhicehuilunwen/2190108.html
