下载:
-
文献[1~2]利用Snake模型对道路移位进行了研究，并总结了Snake移位模型中参数α和β的改变对移位效果的影响。随后，有学者对该移位模型进行了一些改进。文献[3]通过道路交叉点的权重属性控制来保证移位后各交叉点的连通性。文献[4]研究了道路Snake移位模型实现的数据模型、逻辑结构和基本流程。文献[5]为了保证线要素的瓶颈特征在移位中不被破坏，研究了参数α、β与曲线瓶颈特征之间存在的关系。另外，文献[6]分析了用Beam模型参数A、I、E的设置控制线目标变形与移位的规律。文献[7~8]以改进的Beam移位模型为基础研究了有效控制和疏导多类型空间目标群移位的传播规律。文献[9~11]研究了有关道路(街道)与建筑物之间冲突的解决方法，很好地顾及了相关的地图制图规则。类似的研究成果还包括基于三角网[12]、场论[13]、有限元分析[14]等的地图要素移位方法。也有学者比较系统地研究了地图要素移位的规则[15]，或者把最优化方法应用于地图要素移位处理中，例如用最小二乘法、模拟退火法、遗传算法等解决移位问题[16]。对这些相关研究成果的分析表明，智能化解决地图要素移位问题是非常必要的。文献[17]强调在地图综合中充分利用制图知识是解决地图综合自动化问题的关键。因此，本文在研究道路移位的制图规律的基础上，通过设置移位传播障碍点、移位传播障碍线、移位模型参数自动修正等措施改进Snake移位模型，提高其智能化程度。
-
在地图综合中空间冲突的解决应该遵循4条基本规则：(1)清晰性，即综合后的地图要素应更容易区分; (2)地图目标移位后，所有的空间冲突得到解决，且不能产生新的空间冲突; (3)局部空间关系与图形特征应尽量保持; (4)在解决空间冲突的同时，地图目标的移位量尽量少[15]。从几何特征来看，有地图清晰性规则、形状维护规则和几何精度规则。语义特征是指道路等级，用于控制道路移位的优先级。从空间关系来看，则主要表现为交叉处道路之间的夹角尽量保持不变。
为了方便描述这些规则，设一条道路在移位前为{(x00, y00) …(xj0, j0)…(xm0, ym0)}, 移位后为{(x0, y0)…(xj, yj)…(xm, ym)}，其中，(xj0, yj0)和(xj, yj)为道路上顶点的坐标。
1) 清晰性规则C1：保证道路符号化后相互之间无压盖现象，且相互之间有最小可分辨距离。
2) 形状规则C2：一条道路移位后，往往希望道路的形状基本保持不变，因此需要设定相应的阈值。设移位前在顶点(xi0, yi0)处的道路走向为向量U=[xi0-xi-10 yi0-yi-10]到向量V=[xi+10-xi0 yi+10-yi0]的方向变化。同样，该点被移位后的顶点(xi, yi)处的走向也可用这种方法计算：
$$ \theta {\rm{ = }}\arcsin \left( {\frac{{\left\| {\mathit{\boldsymbol{U}} \otimes \mathit{\boldsymbol{V}}} \right\|}}{{\left\| \mathit{\boldsymbol{U}} \right\| \cdot \left\| \mathit{\boldsymbol{V}} \right\|}}} \right) $$ (1) 其中，$\otimes $为向量积；||·||为向量模。
移位前顶点(xi0, yi0)处的曲率C为：
$$ C = \frac{{\left\| \mathit{\boldsymbol{U}} \right\| + \left\| \mathit{\boldsymbol{V}} \right\|}}{{\left\| \mathit{\boldsymbol{W}} \right\|}} $$ (2) 其中，W=[xi+10-xi-10 yi+10-yi-10]。该点移位后，对应的顶点(xi, yi)的曲率计算方法类似。设移位前后的θ和C的变化值为Δθ和ΔC。那么道路移位的形状规则可表示为：
$$ \Delta \theta /\theta \le {G_1}, \Delta C/C \le {G_2} $$ (3) 其中，G1和G2为设定的变化阈值，是一个百分比数。
3) 精度规则C3：在保证没有空间冲突的前提下道路移位量尽量小，可以表示为：
$$ \min \left( {\sum\nolimits_{i = 1}^{m-1} {\sqrt {\left( {\Delta x_i^2 + \Delta y_i^2} \right)} } } \right) $$ (4) 当道路的一个顶点不能被移位时，则规则为Δxi=Δyi=0。在道路端点处的规则为Δx0=Δy0=Δxm=Δym=0。这就是强调的制图规则：在道路网符号化过程中交叉点和端点不移动。
4) 优先级规则C4：不同等级道路的重要程度不同，其移位优先级也不同，可以用三元组表示：(Code, Weight, Move)。其中，Code为分类代码；Weight为道路的重要程度，是一个相对值，位于[0, 1]之间；Move描述是否可以移动，值为0或1，0表示不可移位，1表示可移位。
5) 道路交叉处规则C5：在道路移位过程中, 往往强调交叉处道路之间的夹角尽量不变。设交叉处某一个夹角移位前后的变化为Δt，那么该制图规则为Δt≤G3，其中G3为设定的阈值。
-
在Snake移位模型中，总能量计算公式为：
$$ E\left( d \right) = \int_l {\left( {{E_{{\mathop{\rm int}} }} + {E_{{\rm{ext}}}}} \right){\rm{d}}s} $$ (5) 其中，l表示线的长度；E(d)是总能量；Eext是外部能量，在本文代表两条线之间空间冲突所产生的外力F，为了解决这个空间冲突，需要一个外力把两条线分开，外部能量F促使线移动；Eint是内部能量：
$$ {E_{{\mathop{\rm int}} }} = \frac{1}{2}\left( {\alpha \left( s \right){{\left| {d'\left( s \right)} \right|}^2} + \beta \left( s \right){{\left| {d''\left( s \right)} \right|}^2}} \right) $$ (6) 式中，d(s)是移位量的参数表达；d′(s)和d″(s)分别是移位量d(s)关于s的一阶导数和二阶导数，反映了移位产生的形状变化的大小；α(s)和β(s)参数决定Snake移位模型的弹性和刚性，通常将二者统称为形状参数。外力F和形状参数α和β在经典Snake移位模型中需要人工设置，但是本文试图通过自动调整的方法来找到合适的参数。
但是，经典的Snake移位模型设置线的首末点位置不变，作为强加的边界条件，并把整条线作为移位的传播带。
-
Snake移位模型的移位效果一定程度上受控于模型形状参数的设置，目前主要通过人工设置适合的参数来控制线移位传播。Snake移位模型的参数α和β决定了线的弹性和刚性[1-2]。
为了能对参数进行自动调整，本文提出了一种依据制图规则调整参数的方法，每条规则的作用如下。
1) 若没有满足规则C1，则说明移位的作用力过小。道路移位后，必须重新判断原有空间冲突是否还存在，若还有空间冲突，就说明Snake移位模型在此处的作用力F过小，需要添加外力。
2) 若没有满足规则C2，则说明Snake移位模型的形状参数设置有问题，因为Snake移位模型的优点就是“能很好地保证线的形状特征”，需要依据规则调整参数α和β。
3) 若没有满足规则C3，则说明道路的移位量太大，移位模型中设置的作用力太大，需要减少外力。
4) 若没有满足规则C4，则说明不该移位的道路被移动了，不符合制图规范，也即Snake移位模型的应用对象错了。
5) 若没有满足规则C5，则说明Snake移位模型引起的端点附近的道路图形变形太大，虽然形状特征得到了较好保持，但是在端点处附近的走向变化太大，需要依据规则调整参数α和β。
用于评价移位效果的这5条规则会在道路移位过程的不同阶段起作用。
外力F的大小受规则C1和C3的影响，若空间冲突还存在，则说明F需要增大，设F增加值为ΔF，计算方法为：
$$ \Delta F = F\left( {1-{D_0}/{D_1}} \right) $$ (7) 其中，F为当前的作用力；D0和D1分别为道路上某一个顶点应该移位的已知距离和当前被移动的距离。
图 1(a)说明了移位前顶点P1处前后两条直线段的走向变化。顺时针θ移位后，可能出现图 1(b)和图 1(c)两种情况，当θ′从顺时针变为逆时针，或从逆时针变为顺时针时，就认为θ′为负方向。因此，顶点P1处的形状参数变化值Δθ可表示为：
$$ \Delta \theta = \left| {\theta '-\theta } \right| $$ (8) 
图 1 道路的方向变化
Figure 1. Change of Road Direction
顶点P1处的曲率可用式(2)计算。Δθ和ΔC的值越大，越应增大参数α和β的值。道路移位后，从所有移位的顶点中找到Δθ和ΔC的最大值，判断该最大值是否大于阈值，若成立，则调整参数。
道路交叉处在移位时有时会发生很大的空间方向关系变化，如图 2所示。设当前移位的道路是L1，在交叉点O处，L1在移位后与其他道路之间的空间方向关系就有可能发生变化，如图 2(b)、图 2(c)所示，图 2(b)就在允许的变化范围内，而图 2(c)就超出了允许的变化范围。当遇到这种情况时，需要调整参数α和β的值，调整方法与C3的情况类似。
图 2 空间方向关系变化
Figure 2. Change of Spatial Direction Relationship
-
依据Snake移位模型的特点需要设计沿线传播的范围，本文提出了一种移位传播范围的计算方法，见式(9)，以免把整条道路作为经典Snake移位模型的移位对象。
$$ {F_L} = {\rm{MaxDis/sin}}\theta ' $$ (9) 其中，MaxDis是在冲突处O的最大移位量$\left| {\overrightarrow {OO'} } \right| $。设θ是最大冲突处的道路移位前走向变化角度，那么由设置的走向变化阈值G1可以计算出θ′=θ×(1-G1)，如图 3所示，A点是冲突区边缘上离O最远的点，AO的长度是O点到A点的曲线长度，也就是说，A点最多移位到A′才符合规则，FL是A′到O′的曲线长度，AO是移位前的直线段。
图 3 移位传播长度的计算
Figure 3. Computation of Displacement Propagation Length
设道路的空间冲突区域为{ (xi, yi)…(xj, yj)}，那么可能移位传播范围分别需要从第i个点到第1个点和从第j个点到第m个点进行计算。例如，从第i个点到第1个点的传播范围的计算过程如下：
1) 设当前障碍点点的位置K=i，当前传播范围的曲线长度FD=0, 设置走向变化阈值A1。
2) 计算冲突处的最大移位量MaxDis。
3) θ′=θ·(1-G1)；FL=MaxDis/sinθ′。
4) ${F_D} = \sqrt {{{\left( {{x_k}-{x_{k-1}}} \right)}^2} + {{\left( {{y_k}-{y_{k - 1}}} \right)}^2}} + {F_D} $。
5) 如果K=1，则移位传播障碍点的位置FP=1。
6) 如果FD≥FL，移位传播障碍点的位置FP=K-1。
7) K=K-1，转第4步。
类似地，另一个方向上的传播范围计算方法也是这样。
-
为了验证本文所提出的改进方法，利用VS2010C#设计并实现了该方法，并用有代表性的实验数据进行了验证。图 4是道路移位的数据处理流程。另外, 笔者开发的实验软件中调用了文献[4~5]提供的经典Snake移位算法程序和文献[7~8]提供的基于约束性Delaunay三角网进行空间冲突识别的程序。
图 4 数据处理流程
Figure 4. Diagram of Data Handling
-
道路符号化后，有时会产生自身的空间冲突，例如山区的迂回盘山公路。但是经典Snake移位模型的求解方法只针对有一处空间冲突的单条线进行运算，线的端点就是边界条件。因此，需要计算出移位传播障碍点，将这种道路断开，满足经典Snake移位模型的计算条件。可以通过设置移位传播障碍点，将一条线变成多条线，阻断移位传播，起到限制移位传播范围的作用。这种障碍点就是经典Snake移位模型中的边界条件。
当“之”字形道路内部有空间冲突时, 先需要利用约束性Delaunay三角网识别空间冲突区，然后判断冲突区所关联的两条道路线段是否直接冲突，并且这两条道路线段之间无冲突区，若条件满足，则找到了设置移位传播障碍点的道路线段。设这两条道路线段之间冲突区的内侧顶点是(xi, yi)和(xj, yj)，那么可以简单地把障碍点定义为这两个顶点的中间点，即第int((i+j)/2)个顶点。搜索道路上所有满足条件的空间冲突区，就可以计算出所有的障碍点。另外，若道路上有重要点不可移位，则也应人为设置为移位传播障碍点。
从开放街道地图(OpenStreetMap，OSM)中下载了一条“之”字型道路的数据进行实验，如图 5(a)所示，该图符号化输出的地图比例尺为1:25 000，图 5(b)的灰色区域为计算出的空间冲突区域，红色的线是冲突区域内的三角网的边，说明此道路存在多处空间冲突，换算后的道路符号宽度数值为13.82，红色的点子是计算出的移位传播障碍点。图 5(c)是最终得到的移位结果和原始道路的比较，此时，α=800，β=1 000。
图 5 线内空间冲突的解决
Figure 5. Solution of Spatial Conflicts Within a Line
若参数设置不恰当，则会出现移位效果不好的结果。例如，图 5(d)是在作用力发生变化时的移位结果；当α=1，β=1，作用力正常时，出现了非常混乱的移位结果，见图 5(e)；图 5(f)是冲突快完全解决时的移位结果，α=1 000，β=1 200，图 5(f)中的缓冲区半径刚好为冲突距离的一半，若按照实验中定义的规则(道路符号之间不能相接)，那么图 5(f)中还是存在冲突区域。这些图说明了参数调节的几个典型情况，也体现了参数自动调节的重要性。
实验图中线的顶点数是189，有9个移位传播障碍点。当α=800，β=1 000时，运算时间接近1 s。当设置的初始参数不合适时，运算时间与参数调整的次数有关。
-
本文从OSM中下载了一个道路网络实验数据，如图 6所示。依据道路类型或等级的移位优先级规则C4建立三元组，以便在空间冲突区中确定移位哪条道路。但是，为了重点实验参数自动调整, 本文直接把道路网的交叉点作为经典Snake移位模型的边界条件，使交叉点保持不动，保证道路交叉点的定位精度。图 6是道路网移位前后的效果图。
图 6 道路网的移位
Figure 6. Displacement of Road Networks
-
本文针对经典Snake移位模型的缺点，分析了道路移位的制图规则，通过设置移位传播障碍点，计算移位传播范围，自动调整模型参数，提高了移位模型的自适应能力。从实验效果来看，该方法适用于解决道路符号拓宽所产生的空间冲突，克服了经典Snake移位模型的人工干预难题，提高了道路移位的自动化程度。从实验结果来看，该算法应该和几何移位算法结合。另外，初始参数设置应该可以依据道路的几何特征和空间冲突程度进行简单计算，减少参数自动调整的次数。在进一步的研究中需要解决这些问题，并同时考虑与其他地图要素移位的协同。
-
摘要: 在地图综合中，一条道路的不同路段之间，或者两条道路之间，都有可能存在空间冲突，需要进行道路移位。目前，道路的移位方法主要以能量最小化方法为代表，但是模型参数的控制和移位传播的距离仍有待深入研究。为了有效控制道路移位，基于道路移位制图规则，利用移位传播障碍点设置、移位传播距离计算和模型参数自动调整等措施，优化道路移位的能量最小化模型。实验结果验证了所提方法的可行性和有效性。Abstract: In map generalization, spatial conflicts may occur either between different sections of one single road or between two different roads. Displacement is required when such conflicts emerge. At present, the energy minimization approach is the dominant method for understanding road displacement; but model parameter control and displacement propagation need to be studied further in order to control road displacement effectively. The energy minimization model is improved by setting up obstacle points, calculating distance of displacement propagation, and adjusting model parameters automatically. These improvement measures are all guided by cartographic rules. The effectiveness and availability of this proposed method are verified by experiments.
-
Key words:
- map generalization /
- displacement /
- roads /
- energy minimization /
- parameters
-
[1] Burghardt D, Meier S. Cartographic Displacement Using the Snakes Concept[C].Semantic Modeling for the Acquisition of Topographic Information from Images and Maps, Germany, 1997 [2] Bader M. Energy Minimization Methods for Feature Displacement in Map Generalization[D].Zurich:University of Zurich, 2001 http://www.geo.uzh.ch/dam/jcr:2c2e14d7-7754-41fe-81b6-fbd6c75b2aed/thesis_MatsBader_2001.pdf [3] 吴小芳, 杜清运, 胡月明, 等.基于改进Snake模型的道路网空间冲突处理[J].测绘学报, 2008, 37(2):223-229 http://d.wanfangdata.com.cn/Periodical/chxb200802017 Wu Xiaofang, Du Qingyun, Hu Yueming, et al. Disposal of Spatial Conflict Between the Roads Networks Based on Improved Snake Model[J].Acta Geodaetica et Cartographica Sinica, 2008, 37(2):223-229 http://d.wanfangdata.com.cn/Periodical/chxb200802017 [4] 刘远刚, 郭庆胜, 孙雅庚, 等.基于Snakes算法的道路要素移位软件模块[J].测绘通报, 2014(4):56-60 http://d.wanfangdata.com.cn/Periodical/chtb201404015 Liu Yuangang, Guo Qingsheng, Sun Yageng, et al. A Road Feature Displacement Software Module Based on Snakes Algorithm[J].Bulletin of Surveying and Mapping, 2014(4):56-60 http://d.wanfangdata.com.cn/Periodical/chtb201404015 [5] 孙雅庚, 郭庆胜, 刘远刚, 等.一种道路网图形冲突移位改进研究[J].测绘科学, 2015, 40(3):101-106 http://d.wanfangdata.com.cn/Periodical/chkx201503021 Sun Yageng, Guo Qingsheng, Liu Yuangang, et al. Improved Research for the Road Network Graphic Conflict Displacement Based on Snake Algorithm[J].Science of Surveying and Mapping, 2015, 40(3):101-106 http://d.wanfangdata.com.cn/Periodical/chkx201503021 [6] 武芳, 侯璇, 钱海忠, 等.自动制图综合中的线目标位移模型[J].测绘学报, 2005, 34(3):262-268 http://d.wanfangdata.com.cn/Periodical/chxb200503014 Wu Fang, Hou Xuan, Qian Haizhong, et al. A Model for Road Network Displacement in Automated Map Generalization[J].Acta Geodaetica et Cartographic Sinica, 2005, 34(3):262-268 http://d.wanfangdata.com.cn/Periodical/chxb200503014 [7] Liu Y, Guo Q, Sun Y. A Complete Solution of Cartographic Displacement Based on Elastic Beams Model and Delaunay Triangulation[C].ISPRS Technical Commission IV Symposium, Suzhou, China, 2014 [8] 刘远刚, 郭庆胜, 孙雅庚, 等.地图自动综合中Beams移位算法的实现与改进[J].武汉大学学报·信息科学版, 2016, 41(4):450-454 http://d.wanfangdata.com.cn/Periodical/whchkjdxxb201604004 Liu Yuangang, Guo Qingsheng, Sun Yageng, et al. Implementation and Improvement of Beams Displacement Algorithm in Automated Cartographic Generalization[J].Geomatics and Information Science of Wuhan University, 2016, 41(4):450-454 http://d.wanfangdata.com.cn/Periodical/whchkjdxxb201604004 [9] Fei Lifan.A Method of Automated Cartographic Displacement:On the Relationship Between Streets and Buildings[D].Germany:University of Hannover, 2002 [10] 何津, 费立凡.解决图形冲突的受限变形所涉及的数学原则:以道路和建筑物的关系为例[J].武汉大学学报·信息科学版, 2007, 32(4):326-330 http://ch.whu.edu.cn/CN/abstract/abstract1867.shtml He Jin, Fei Lifan. Mathematical Methods Involved in Constrained Reshaping for Solving Graphic Conflicts Between Streets and Buildings[J].Geomatics and Information Science of Wuhan University, 2007, 32(4):326-330 http://ch.whu.edu.cn/CN/abstract/abstract1867.shtml [11] 费立凡, 何津.解决街道与建筑物图形冲突的移位模型研究[J].武汉大学学报·信息科学版, 2007, 32(6):540-543 http://ch.whu.edu.cn/CN/abstract/abstract1911.shtml Fei Lifan, He Jin.Displacement Models for Solving Graphic Conflicts Between Streets and Buildings[J].Geomatics and Information Science of Wuhan University, 2007, 32(6):540-543 http://ch.whu.edu.cn/CN/abstract/abstract1911.shtml [12] Ruas A.A Method for Building Displacement in Automated Map Generalization[J].International Journal of Geographical Information Science, 1998, 12(8):789-803 doi: 10.1080/136588198241509 [13] Ai T, Zhang X, Zhou Q, et al. A Vector Field Model to Handle the Displacement of Multiple Conflicts in Building Generalization[J].International Journal of Geographical Information Science, 2015, 29(8):1-22 [14] Højholt P.Solving Space Conflicts in Map Generalization:Using a Finite Element Method[J].Cartography and Geographic Information Science, 2000, 27(1):65-74 doi: 10.1559/152304000783548028 [15] Beard K.Constraints on Rule Formation[M]//Buttenfield B P, Mcmaster R B. Map Generalization:Making Rules for Knowledge Representation. London:Longman Press, 1991 [16] 孙雅庚, 郭庆胜, 刘远刚, 等.顾及格式塔原则的建筑物群移位实数编码遗传算法[J].武汉大学学报·信息科学版, 2015, 40(2):269-273 http://ch.whu.edu.cn/CN/abstract/abstract3197.shtml Sun Yageng, Guo Qingsheng, Liu Yuangang, et al.A Real-Coded Genetic Algorithm Considering Gestalt Principles to Building Displacement[J].Geomatics and Information Science of Wuhan University, 2015, 40(2):269-273 http://ch.whu.edu.cn/CN/abstract/abstract3197.shtml [17] 王家耀, 钱海忠.制图综合知识及其应用[J].武汉大学学报·信息科学版, 2006, 31(5):382-386 http://ch.whu.edu.cn/CN/abstract/abstract2452.shtml Wang Jiayao, Qian Haizhong. Cartographic Generalization Knowledge and its Application[J].Geomatics and Information Science of Wuhan University, 2006, 31(5):382-386 http://ch.whu.edu.cn/CN/abstract/abstract2452.shtml -
点击查看大图
图(6)
计量
- 文章访问数: 1314
- HTML全文浏览量: 89
- PDF下载量: 351
- 被引次数: 0
