EN中文

Journal of Geo-information Science >

2024 , Vol. 26 >Issue 1: 135 - 143

DOI: https://doi.org/10.12082/dqxxkx.2024.220569

Application of the Decomposition Importance in the Road Network Auto-Selection of Volunteered Geographic Information for Map Generalization

  • XIONG Shun , 1, 2, * ,
  • DU Qingyun 3 ,
  • MA Chao 1, 2 ,
  • LIU Pingzhi 1, 2 ,
  • JIANG Danni 2
Expand
  • 1. Survevying and Mapping Institute, Xi'an 710054, China
  • 2. State Key Laboratory of Geo-information Engineering, Xi'an 710054,China
  • 3. WuHan University, Wuhan 430072, China
* XIONG Shun, E-mail:

Received date: 2022-08-03

  Revised date: 2022-11-16

  Online published: 2024-03-26

Supported by

National Natural Science Foundation of China(62101395)

Fold

Abstract

Volunteered geographic information has the characteristics of real time, wide coverage, rich information, and convenient access. It can be used as a good data input for the production and updating of worldwide geospatial data. However, due to the scale-free characteristics of this data, the details of volunteered geographic information road data are usually too complex, which is far beyond the needs for spatial vector data production and is thus difficult to be directly applied to geospatial data production. When calculating the road importance, the existing road network automatic selection algorithm sorts the importance of all roads to be selected and selects them from the largest to the smallest according to the importance. These methods usually ignore the influence of road network structure changes which could affect the road importance in the selection process. Therefore, this paper proposes an automatic selection algorithm of road network based on hierarchical decomposition of importance. Aiming at the characteristics of rich details and free scale of volunteered geographic information road network, this paper proposes a road network selection algorithm based on hierarchical decomposition. Compared with the previous algorithms based on the ranking and selection of road importance, the essence of this algorithm is that it considers the impact of the ranking of road importance caused by the changes in road network structure after deleting some roads in the process of gradual downsizing. It adopts the strategy of gradual decomposition and multiple calculations to reduce this impact by repeatedly calculating the road importance. The selection process of this algorithm is shown as follows. Firstly, we calculate the importance of all nodes and remove some road nodes with the least importance. Secondly, whether the selection results meet the requirements are judged. If the requirements are not met, we will recalculate the importance of all new nodes and repeat the judgement steps until all road nodes are sorted, so as to obtain the importance ranking of all roads and complete the selection of road network. The experimental results show that the algorithm selected in this paper is better than the network centric method, which means that the decomposition selection strategy is more consistent with the reference data. In addition, the algorithm in this paper is beneficial to the infinite selection of road network. However, this algorithm needs to manually set the selection step size, and the step size setting has a certain impact on the selection results. In the next step of research, more extensive and in-depth experiments are needed to explore more reasonable step size settings and further study the quantitative evaluation mechanism of road selection results.

Key words： volunteered geographic information; road network selection; importance degree; K-shell algorithm; hierarchical decomposition; complex network

Cite this article

XIONG Shun , DU Qingyun , MA Chao , LIU Pingzhi , JIANG Danni . Application of the Decomposition Importance in the Road Network Auto-Selection of Volunteered Geographic Information for Map Generalization[J]. Journal of Geo-information Science, 2024 , 26(1) : 135 -143 . DOI: 10.12082/dqxxkx.2024.220569

1 引言

地理信息数据资料是地理信息数据生产与应用的基础，随着地理信息数据应用范围不断扩大、应用层次不断深入，用户对全球范围的高质量地理信息数据提出了迫切需求。但是目前境外区域的地理信息数据生产与更新只能依靠从网络上收集到的公开资料进行，收集难度大，收集来的资料凌乱繁杂、现势性差、存在诸多不一致性等问题，严重影响了数据生产的质量和效率。自发地理信息（Volunteered Geographic Information，VGI）是近年来新兴的开放式地理信息数据，具有高覆盖性、高现势性和易于获取等特点，使其能够成为全球范围内地理信息数据生产与更新的良好数据资料[1]。由于VGI数据的无尺度特性，VGI道路数据细节过于繁杂，远远超出了全球矢量空间数据生产的需要，严重影响了制图人员的处理效率[2]。为此，需要研究VGI中道路的自动选取方法，选择相对重要的、需要保留的道路，删去细小的道路。
目前关于道路网选取方法的研究从传统的基于语义信息的选取，逐渐转向依据道路的几何特征上来[3-4]。其中，基于图模型的道路网选取方法，凭借其选取后道路连通性优势，近年来得到了广大学者的重视。该方法的主要思路是将道路连接成stroke，并抽象成图模型，并根据图节点的中心性特征构建模型，计算图节点的重要度，进而完成道路选取[5⇓-7]。这类方法通过对道路的重要度进行量化，进而可以实现道路网的连续尺度变换，但是各个节点中心性之间的权重设置，往往通过人工经验设置，算法的实用程度不高。此外，还有一些学者引入机器学习的算法，将道路节点的中心性特征作为神经网络的输入，通过监督学习的方法训练神经网络，将道路节点的选取问题作为节点的二类分类问题进行学习[8-9]。此类方法可以避免不同特征的权重设置问题，但是其将道路网选取作为二类分类问题，只能应用于固定比例尺之间的道路网选取，不能够实现连续的道路网选取。
上述算法，均是直接对待选取道路网建模、计算，从而一次完成道路重要性排序和道路选取。但是在实际进行道路网选取或缩编时，往往是采取逐级选取的策略，如1:5万的道路网要缩编到1:100万，首先要缩编至1:25万，然后再由1:25万缩编至1:50万，最后由1:50万缩编至1:100万。考虑到在逐级缩编的过程中，由于舍去了一些低等级道路，从而会引起道路网结构发生变化，这种结构变化会影响道路的中心性指标，如道路的度、中介中心性等都会发生变化，进而会引起道路重要度排序发生变化。与直接从待选取比例尺计算并完成选取的方式相比，最终的选取结果会产生差异。为此，本文提出了一种基于道路重要度层次分解的道路网选取方法，借鉴了K-shell算法的逐层分解计算的思想，在进行道路网选取时，通过分批、逐步删除低重要度道路、并重新计算道路网重要度的方式，完成道路网的重要度评价与选取，最后利用实际路网数据对上述算法进行试验验证。

2 研究方法

根据研究目标，本将具体的研究方法分为2个部分：① 道路重要度计算。基于文献[10]提出的增加加权PageRank算法，在其基础上进行了部分适应性改进和优化，使其能够适用于本文所提出的逐层分解选取的思路。② 道路层次分解选取方法。基于经典的K-shell算法原理，提出了道路重要度 K-shell分解方法，使其能够应用到道路网的选取中，技术路线如图1所示。
图1 研究技术路线

Fig. 1 Work flow of this research

2.1 道路重要度计算

借鉴PageRank算法计算网页的重要性的思路，文献[10]提出了加权PageRank的道路重要度算法，取得了较好的效果。PageRank算法基本思路为：网页的重要性是由入链的数量和质量决定的，同时每个页面又将自己的重要度通过出链平均分配给其指向的节点。由于PageRank值的排序与初始值无关，因此开始时每个页面设置相同的PageRank值，通过迭代递归计算来更新每个页面的得分，随着每一轮的计算进行，网页当前的PageRank值会不断得到更新。通过若干轮的计算，各个网页的PageRank值会进入一个稳定的状态，得到每个页面最终的PageRank值，该值越大表明该网页越重要，迭代公式如式（1）所示：
P a g e R a n k ( p i ) = ∑ P j ∈ I n p u t P i P a g e R a n k ( p j ) p j O u t p u t
式中： p i（i=1,2,3，…，N）表示网页节点； I n p u t P i表示节点 p i的所有入链集合； p j O u t p u t表示 p i的出链数量； p a g e r a n k ( p i )表示网页节点 p i的PageRank值。为了消除链接陷阱对结果的影响，增加一个阻尼系数d，基本PageRank迭代公式如式（2）所示。
P a g e R a n k ( p i ) = 1 - d N + d * ∑ P j ∈ I n p u t P i P a g e R a n k ( p j ) p j O u t p u t
本文在其基础上进行了一定的改进：① 重要度分配权重方法，文献[10]是将道路的长度作为权重，道路越长，则其权重越大，对于获得的重要度也越大。这样的设计是默认为道路长度是道路重要度的重要衡量指标，考虑稍显不足。本文将道路长度作为道路重要度初始值，将道路当前重要度作为重要度分配权重，这样能够使得重要的道路能够获得更多的权重，并且权重也由静态变为动态，更加能够体现“重要的道路可以获得更多的重要度”这一设计初衷，也可以加快算法的收敛速度；② 去掉了利用SpamRank进行重要度修正的部分，因为本文采用层次分解的选取方法，在逐层分解选取的过程中，逐步去掉了路网密集区域微小道路的影响，可以不用额外考虑。
上述道路重要度计算过程及方法如下：道路网构建道路对偶图，将每个道路节点长度设置为其初始重要度，然后统计各节点的邻居节点情况，并根据当前重要度占比进行邻居节点的重要度分配，通过不断迭代反复，最终达到每条道路重要度不再发生变化，达到稳定状态，此时道路重要度即为所求重要度。
设 p i（i=1,2,3，…，N）为道路网中的节点， I n p u t P i表示节点 p i的所有邻居节点集合， O u t p u t p j表示节点 p j的邻居节点集合， L e n g t h ( p i )表示节点 p i的stroke长度，则节点 p i的初始重要度 p a g e r a n k ( p i ) 0为：
p a g e r a n k ( p i ) 0 = L e n g t h ( p i )
第k次重要度分配时，节点 p i获取来自节点 p j（ p j ∈ I n p u t p i）重要度时的权重 w e i g h t ( p i , j ) k为：
w e i g h t ( p i , j ) k = p a g e r a n k ( p i ) k - 1 ∑ p j ∈ O u t p u t p j p a g e r a n k ( p j ) k - 1
根据上述算法描述，此时节点 p i重要度 p a g e r a n k ( p i ) k为：
p a g e r a n k ( p i ) k = 1 - d N + d ×                             ∑ P j ∈ I n p u t P i ( p a g e r a n k ( p j ) k - 1 × w e i g h t ( p i , j ) k )

2.2 道路层次分解选取方法

2.2.1 经典K-shell算法

Kitsak等[11]于2010年首次提出了节点重要性依赖于其在整个网络中的位置的思想，并且利用 K-shell分解获得了节点重要性排序指标，该指标时间复杂度低，适用于大型网络而且比度、介数更能准确识别在疾病传播中最有影响力的节点。K-shell分解方法通过递归地移去网络中所有度值小于或等于k的节点，是一个层层推进的过程[12]（图2）。
图2 K-shell算法逐层分解示例

Fig. 2 The example of K-shell method

首先计算图中所有节点的度，然后标记度小于等于1的节点，得到k=1的所有节点，并将其从图中剔除；然后重新计算新图中所有节点的度，继续标记并剔除度小于等于1的节点，得到k=2所有节点；重复上述步骤，直到所有节点分配完毕。这样就获得了一系列不同k核的集合，从而可以将节点进行粗排序。

2.2.2 道路网重要度的K-shell分解

考虑到道路网的逐级缩编过程，即由大比例尺数据首先缩编至较小比例尺，然后再继续缩编，直至到目标比例尺。上述K-shell算法的逐层分解原理，恰好与道路网的逐级缩编相呼应：以大比例尺道路网作为待选取数据，首先根据道路节点重要度评价算法，计算所有节点的重要度，然后舍去一部分重要度最小的道路，得到较小比例尺的道路网，此时的道路网图结构与之前已有所不同，重新计算剩下道路节点的重要度，重复上述选取步骤，直至缩编至目标比例尺停止，即可完成从待选比例尺到目标比例尺的道路网选取。与现有算法直接根据待选比例尺数据计算道路的重要度并完成最终选取的方法相比，采用逐级选取的方法考虑了逐级选取过程中，道路网结构变化对最终道路重要度的影响，可以使选取结果更加科学、合理[13]。以图3所示的道路图为例，来分析说明两种选取方法的差异。
图3 示例道路网及其道路对偶图模型

Fig. 3 The example road network and its dual graph model

图3道路网有11个道路节点，以选取5条道路为目标，设每次分解删去重要度最小的2个道路节点，进行3次分解即可完成选取。选取过程为：首先，计算所有道路节点的重要度，如表1（左侧）所示；然后，舍去重要度最小的节点8和节点10，重新计算剩下节点的重要度，如表1（右侧）和图4所示。
表1 第一次分解道路节点的重要度及其变化

Tab. 1 The result of first road select and the changes of road importance

首次道路节点重要度 第一次分解后重新计算道路节点重要度 排序变化
重要度排序 重要度 道路ID 重要度排序 重要度 道路ID
1 1.561 9 0 1 1.489 2 0 不变
2 1.500 4 5 2 1.348 8 4 上升
3 1.488 1 1 3 1.240 8 5 下降
4 1.438 9 4 4 1.197 6 1 下降
5 0.787 0 7 5 0.765 6 2 上升
6 0.725 5 2 6 0.708 4 3 上升
7 0.700 9 6 7 0.657 6 7 不变
8 0.577 9 3 8 0.638 8 6 下降
9 0.430 3 9 9 0.528 0 9 不变
10 0.418 0 10
11 0.331 9 8
图4 直接选取方法道路选取结果示例

注:基于Pagerank方法计算道路重要度。数字为道路ID号

Fig. 4 The road select result of Pagerank method

表1左侧是根据原始道路网计算的所有节点重要度，相当于现有直接计算选取的方法，可直接获得最终选取的道路为节点0、节点1、节点4、节点5和节点7，如图4所示。
表1右侧是删除2条重要度最小的道路节点后，重新计算的重要度，相当于进行了第1次分解选取。对比表1可以看出，节点5、节点1和节点7的重要度排序出现了下降，而节点2、节点3和节点4的重要度排序则上升，其他节点重要度排序保持不变，即有60%的道路节点重要度排序发生不同程度的变化。继续删除2条重要度最小的道路节点6和节点9，剩下的再次重新计算重要度，进行第2次分解选取，并删除2条重要度最小的道路节点3和节点7，剩下的再次重新计算重要度，进行第3次分解选取，结果分别如表2左侧和表2右侧所示。
表2 第二次分解及第三次分解道路节点的重要度及其变化

Table 2 The results of senond and third road select and the changes of road importance

采用逐层分解的选取方法，最终选取道路为节点0、节点1、节点2、节点4和节点5，选取结果如图5所示。对比图4和图5可以发现，2种方法的结果略有不同，直接计算选取的方法选中了道路节点7，但逐层分解的选取方法则保留了节点2，删除了节点7。观察图3原始道路网可以发现，节点7连接了节点1和节点4，但是没有像节点0那样连接节点2，实质为一条次要道路，节点2为横贯城市的主要道路。
图5 道路网重要度逐层分解选取结果示例

注:数字为道路ID号。

Fig. 5 The road select result of decomposition importance method

从上述选取过程可以看出，道路网结构在逐级选取的过程中不断发生变化，道路节点的重要度也随之改变，会影响道路节点的排序，从而影响最终的选取结果。与现有算法直接根据待选比例尺数据计算道路的重要度相比，采用逐层分解的方法，结果会更加科学、合理。
在道路网选取的应用中，由于道路的重要度值是一个连续的值，如果每次只剔除道路重要度值最小的道路，会大大增加算法的复杂性和计算冗余程度。因此，本文在进行逐层分解选取时，通过设置分解步长r来进行分解。设某道路网共用N条道路，设置分解步长r，即每次分解剔除r×N条道路节点。r取值可根据待选取道路网数量进行调整。

3 道路网选取实验与结果分析

3.1 实验数据

为了验证本文算法原理正确、结果有效，采用西安市城区2021年度OpenStreetMap道路网数据进行实验。在该比例尺下，城区的部分道路网具有多线、圈型立交等微观结构，对于连接stroke影响较大，需在试验前进行处理，处理完成后的试验区域内共有4 998条路段，构造stroke单元1 126条。为了保证算法选取效果，将短小、悬挂等路段删除，如图6所示。
图6 道路网实验数据范围

Fig. 6 The range of road experimental data

3.2 实验结果与分析

3.2.1 实验结果

在实验中，将分解步长设置为0.1，共进行12次分解，结果如图7所示。从图7来看，开始选取时，会舍去一些短小道路，随着选取次数的增多，舍去的道路逐渐变长、位置也逐渐变得重要。
图7 实验结果

Fig. 7 Shows the experimental results

3.2.2 实验分析

为了验证本文算法思路，与基于网络中心性方法（节点重要度指标为stroke长度、节点度、接近中心性、中介中心性）的选取结果进行对比。为了保证结果可信度，每次选取都设置相同的选取比例，并统计道路重要度排序结果、相同道路ID的重要度排序情况，以及2种算法结果的一致性情况，结果分别如图8所示。
图8 实验结果统计

Fig. 8 Statistics of experimental results

图8中，蓝色虚线表示2种算法结果道路重要度不一致的比例，即将2种算法计算结果按照重要度大小进行排序，并统计相同排序位置上道路是否相同；绿色虚线表示2种算法道路选取结果不一致的比例，即在最终的选取结果中，2种算法道路ID的不一致数量的占比。从图8中可以看出，道路的重要度排序不一致比例达到了97%以上，这说明按照本文算法的得到的道路网排序，与对比算法相比，基本所有道路的重要度排序均发生了不同程度的变化，即本文算法确实是影响了道路网的重要度的度量。从选取结果不一致性曲线来看，2种算法的选取结果从最开始约2%左右不一致，达到了最终的25%左右的不一致，说明本文算法不仅影响了道路网的重要度排序结果，并且这种影响还导致了一定程度上选取结果的差异。图7的2个方面的统计结果结合起来可以说明通过分层、分步骤进行道路网重要性度量，道路网的重要度发生了变化，并且这种变化会随着选取次数的增加而不断变大，最终会对选取结果造成较大的影响。
为进一步说明算法结果有效，将实验区域1:25万道路网数据作为参照物，计算本文算法最终选取结果与参照物的一致性程度，作为算法结果有效性的评价指标，并以网络中心性算法作为对比。经统计，实验区域1:25万道路数据有214条stroke单元，将上述2种算法选取结果设置成为该数字后，再将上述2种算法的选取结果与1:25万道路数据进行匹配，并计算其一致性程度，具体实验结果如图9所示。
图9 2种选取算法选取结果与参考数据对比

Fig. 9 Comparison between the selection results of two selection algorithms and reference data

经统计计算，本文算法一致性为86.2%，184条道路与1:25万数据一致，网络中心性算法的一致性为77%，165条道路与1:25万数据一致。这说明本文算法与参考数据一致性更好。

4 结论

针对自发地理信息道路网数据细节丰富、数据无尺度的特点，本文提出了基于层次分解的道路网选取算法。该算法与以往的基于道路重要度排序选取的算法相比，其本质在于考虑了逐级缩编过程中，删除部分道路后，道路网结构变化引起道路重要度的排序的影响，采取逐次分解、多次计算的策略，通过反复计算道路重要度来降低这种影响。从上述实验结果对比来看，采用逐级分解的选取策略的选取结果，与参考数据的一致性更高。此外，本文算法对于道路网的无极选取具有一定的裨益。但是，本文算法需要人工设置选取步长，且步长的设置对于选取结果有一定的影响。在下一步的研究中，需要进行更广泛、深入的实验，探索利用深度学习等智能算法实现步长的自动设置或者智能推荐，并进一步研究道路选取结果的量化评价机制。值得注意的是，制图区域特点、制图目的等因素对选取结果也具有较大影响，如何将这些因素量化加入到数学选取模型中，使得模型的鲁棒性更好、适用性更广，也是后续需要深度研究的问题。

References

Publishing order | Descend order by publishing year | Descend order by cited within
[1]
马超, 孙群, 徐青, 等. 自发地理信息可信度及其评价[J]. 地球信息科学学报, 2016, 18(10):1305-1311.

DOI

[Ma C, Sun Q, Xu Q, et al. The credibility and evaluation of volunteered geographic information[J]. Journal of Geo-Information Science, 2016, 18(10):1305-1311.] DOI:10.3724/SP.J.1047.2016.01305

[2]
寇培颖, 牛铮, 刘正佳, 等. 基于自发地理信息的“一带一路”区域陆路交通状况分析[J]. 地球信息科学学报, 2018, 20(8):1074-1082.

DOI

[Kou P Y, Niu Z, Liu Z J, et al. Analyzing the land transportation conditions in the Belt and Road area based on volunteered geographic information[J]. Journal of Geo-Information Science, 2018, 20(8):1074-1082.] DOI:CNKI:SUN:DQXX.0.2018-08-006

[3]
Jasim O. Digital geomatics trends for production and updating topographic map by using digital generalization procedures[J]. World Academy of Science, Engineering and Technology, International Journal of Environmental, Chemical, Ecological, Geological and Geophysical Engineering, 2017,11:644-652.

[4]
Balboa J L G, López F J A. Generalization-oriented Road line classification by means of an artificial neural network[J]. GeoInformatica, 2008, 12(3):289-312. DOI:10.1007/s10707-007-0026-z

[5]
郭漩, 钱海忠, 王骁, 等. 多源道路智能选取的本体知识推理方法[J]. 测绘学报, 2022, 51(2):279-289.

DOI

[Guo X, Qian H Z, Wang X, et al. Ontology knowledge reasoning method for multi-source intelligent road selection[J]. Acta Geodaetica et Cartographica Sinica, 2022, 51(2):279-289.] DOI:10.11947/j.AGCS.2021.20200360

[6]
马京振, 孙群, 温伯威, 等. 结合轨迹数据的混合多特征道路网选取方法[J]. 武汉大学学报·信息科学版, 2022, 47(7):1009-1016.

[Sun Q, Wen B W, et al. A hybrid multi-feature road network selection method based on trajectory data[J]. Geomatics and Information Science of Wuhan University, 2022, 47(7):1009-1016.] DOI:10.13203/j.whugis20190480

[7]
邓敏, 陈雪莹, 唐建波, 等. 一种顾及道路交通流量语义信息的路网选取方法[J]. 武汉大学学报·信息科学版, 2020, 45(9):1438-1447.

[Deng M, Chen X Y, Tang J B, et al. A method for road network selection considering the traffic flow semantic information[J]. Geomatics and Information Science of Wuhan University, 2020, 45(9):1438-1447.] DOI:10.13203/j.whugis20180053

[8]
刘佩, 袁林辉, 张康, 等. 基于RBF神经网络的OSM道路网智能选取[J]. 地理信息世界, 2019, 26(3):8-13.

[Liu P, Yuan L H, Zhang K, et al. Intelligent selection of OSM road network based on RBF neural network[J]. Geomatics World, 2019, 26(3):8-13.] DOI:CNKI:SUN:CHRK.0.2019-03-003

[9]
袁林辉, 刘凯, 刘佩, 等. 径向基函数神经网络用于小比例尺道路网选取[J]. 测绘科学, 2019, 44(3):8-14,20.

[Yuan L H, Liu K, Liu P, et al. Small scale road network selection using radial basis function neural network[J]. Science of Surveying and Mapping, 2019, 44(3):8-14,20.] DOI:10.16251/j.cnki.1009-2307.2019.03.002

[10]
马超, 孙群, 陈换新, 等. 加权网页排序算法在道路网自动选取中的应用[J]. 武汉大学学报·信息科学版, 2018, 43(8):1159-1165.

[Sun Q, Chen H X, et al. Application of weighted PageRank algorithm in road network auto-selection[J]. Geomatics and Information Science of Wuhan University, 2018, 43(8):1159-1165.] DOI:10.132 03/j.whugis20160127

[11]
Kitsak M, Gallos L K, Havlin S, et al. Identification of influential spreaders in complex networks[J]. Nature Physics, 2010, 6(11):888-893. DOI:10.1038/nphys1746

[12]
Wei B, Liu J, Wei D J, et al. Weighted k-shell decomposition for complex networks based on potential edge weights[J]. Physica A: Statistical Mechanics and Its Applications, 2015, 420:277-283. DOI:10.1016/j.physa.2014.11.012

[13]
李木梓, 徐柱, 李志林, 等. 基于层次随机图的道路选取方法[J]. 地球信息科学学报, 2012, 14(6):719-727.

DOI

[Li M Z, Xu Z, Li Z L, et al. A hierarchical random graph based selection method for road network generalization[J]. Journal of Geo-Information Science, 2012, 14(6):719-727.] DOI:10.3724/SP.J.1047.2012.00719

Options
Outlines

/

〈 〉