面向道路网VGI数据的匹配与融合方法

王志国，盛业华，黄 毅，黄宝群

(1.南京师范大学 虚拟地理环境教育部重点实验室，江苏 南京 210023;2.江苏省地理信息资源开发与利用协同创新中心，江苏 南京 210023)

自发地理信息(Volunteered Geographic Information，VGI)是Goodchild教授在2007年提出的一种有别于传统测绘的地理数据采集方式[1]。普通非专业用户可以通过在线协作的方式自发进行地理信息的生产、收集和发布，具有数据更新快、细节丰富、覆盖范围广等优势。“人人都是传感器”的自发地理信息在简化地理信息数据采集方式、丰富数据来源的同时，大大降低采集成本，提高了数据的现势性。但是非专业用户采集数据时多使用非专业设备，存在采集方式不规范、对同一地物描述差异较大、轨迹随机性较强等现象，导致VGI数据存在精度较低、可靠性不足等问题[2]，但大量VGI数据对同一地理要素的重复采集与融合处理则可改善VGI数据的质量。道路网作为地理空间数据中变化最快的要素之一，是一种重要的资源，其更新受到人们的广泛关注。随着智能移动设备的普及，VGI成为了一种重要的道路网获取与更新手段，如OpenStreetMap、Google Map Maker等。结合矢量要素的匹配与融合理论，可以有效提高道路网VGI数据的精度，其主要包括匹配与融合两个环节。VGI数据的匹配与融合效果的好坏直接影响到后续更新的正确性。

矢量要素匹配是对不同地图中的同名要素进行互相识别的过程，是地图合并或数据融合的前提与关键。道路网包括点要素和线要素，常用的点匹配算法可从距离、结构、方位等指标进行分类。欧式距离法、双向最近距离法[3]、可信度值匹配法[4]等是常用距离指标匹配法；8角度分区、16角度分区“蜘蛛编码”[5]是常用的结构指标匹配法；星型图描述要素间方位关系[6]是常用的方位指标匹配法。常用的线要素匹配指标有：Hausdorff距离、Fréchet距离等距离指标[7]，线要素方向、形状、拓扑等指标[8-9]。矢量要素融合源于地图合并，即将同一地区两个或两个以上不同来源的地图数据合并生产新的地图过程。常用的道路网点要素融合算法主要包括基于三角网确定同名点间的转换关系融合法[5]、基于同名点拓扑关联的融合算法[10]、利用最小二乘原理融合算法[11]等。常用的线要素融合算法主要包括利用坐标转换关系实现线融合[12]、基于多评价因素实现线状要素融合[13]、基于Delaunay三角网的时空轨迹融合模型[14]等。上述匹配与融合算法多应用于地图合并领域，在道路网VGI数据匹配中应用较少，如何选取合适的匹配与融合算法需要进一步研究。

本文根据道路网VGI数据特点结合矢量要素的匹配与融合理论，利用路段结点和路段距离相似度匹配算法与Delaunay三角剖分融合算法实现道路网VGI数据的匹配与融合，并以某大学校园道路网为例实现多人采集道路网VGI数据的匹配与融合。

1 道路网VGI数据匹配与融合算法

道路网VGI数据匹配与融合算法的目标是根据多人沿道路行走的GNSS轨迹数据建立道路网络。其思路是，首先对每组GNSS轨迹数据分别进行必要的预处理，包括数据筛选、数据格式转换等；然后再生成每组道路网的路段和结点，建立道路网拓扑关系；接着再利用道路网VGI数据匹配与融合算法，首先根据弧段结点相似度匹配对结点进行匹配，其次根据路段距离相似度对路段进行匹配，再次利用Delaunay三角剖分融合算法进行同名路段融合，最后依据融合后的路段生成新的道路网。

1.1 VGI数据预处理及道路网拓扑关系生成

1)VGI数据预处理。针对多人沿道路行走的GNSS轨迹数据，分别对其进行预处理，主要包括数据筛选和数据格式转换，剔除低质量轨迹数据，并将原数据转换为shapefile文件，便于后续处理。

2)单人道路网拓扑关系生成。拓扑关系是空间数据结构化的体现，是对空间数据自动处理的基础，因此必须对道路网VGI数据进行拓扑处理[15]。道路网主要由弧段与结点组成，其拓扑关系包括：结点与结点的关系、结点与弧段的关系、弧段与弧段的关系等，其中结点与弧段间的关系是道路网络主要的拓扑关系。在进行存储时，需要记录每一个结点编号以及相关联弧段等信息。

首先将单人采集并经预处理的GNSS轨迹数据组织在单个图层中，并对轨迹线数据进行结点、弧段的拓扑化处理，形成单人道路网络数据(如图1所示)，并按链状双重独立编码结构记录单人道路网络数据。

图1 单人道路网络图

1.2 道路网VGI数据匹配

为了将多人采集的道路网VGI数据进行融合，其关键在于对经处理的单人道路网络进行匹配。本文首先在路段首尾结点处建立缓冲区，对首尾结点对进行结点匹配；然后再根据路段首尾结点对间的欧式距离相似度进行路段匹配；进而实现整个道路网VGI数据的匹配。

将第一个VGI道路网络作为参考图层，其他VGI道路网络作为待匹配图层(调整图层)，在结点匹配的基础上再以参考图层中各路段为标准，将各待匹配图层中的路段与之匹配。

1)路段结点匹配。路段结点匹配是路段首尾结点处建立缓冲区，缓冲区是某一指定空间物体的一定范围内邻域的集合。对象Oi的缓冲区定义为

Bi={x:d(x,Oi)≤R}.

(1)

即距对象Oi的距离d小于R的全部点的集合，d为欧式距离。

在参考图层的路段首尾两结点处分别建立半径为15 m的缓冲区，由于校园道路间距离相对较远且较为规整，本实验中半径15 m缓冲区可以取得较好的匹配效果。若待匹配图层中存在某一路段的首尾结点分别落在参考图层路段首尾结点的缓冲区内，则待匹配图层该路段首尾结点对与参考图层路段的首尾结点对匹配成功。

2)路段距离相似度匹配。路段距离相似度是参考路段首尾结点间的欧式距离和待匹配路段首尾结点的欧式距离的相似程度。

(2)

式中：Sdis为路段距离相似度；Dis(A,B)为参考弧段首尾结点间的欧式距离；Dis(A′,B′)为待匹配弧段首尾结点间的欧式距离；A,B,A′,B′分别为参考弧段与待匹配弧段的首尾结点。

计算匹配成功的路段结点对之间的距离相似度，若待匹配路段与参考路段的距离相似度大于0.8，则认为这两条路段匹配成功；若无任何待匹配路段与某一参考路段距离相似度大于0.8，则该参考路段匹配失败。

1.3 道路网VGI数据融合

路段融合是在同名路段的基础上进行的，本文依据基于Delaunay三角网的时空轨迹融合模型[14]，通过Delaunay三角剖分融合算法来实现道路网VGI数据的融合。

道路网VGI数据的路段是由GNSS轨迹点连接而成的，如图2所示中a，b为已匹配的同名弧段，利用路段上GNSS轨迹点根据Delaunay三角网的构网原则，在参考路段和调整路段间构建的Delaunay三角网，并将两条路段相交处打断生成新结点A。

图2中三角网中三角形间主要有两种邻接模式。第一种是图2中1、2类三角形间互相有两条邻边三角形，融合后点为两条邻接边的权重比的分割点；第二种是图2中3、4类只有一条邻接边的三角形，融合后点为一条邻接边的权重比分割点及交点。路段融合后新的结点P，根据式(3)计算得出

(3)

式中：W表示权重，参考路段WⅠ=n；调整路段WⅡ=1；融合后路段WP=n+1，其中n表示已参与融合的路段数，即经多次融合后该路段的权重。

最后再将两条路段融合得到的新结点依次相连，即可完成同名路段的融合，如图3所示。

图2 建立Delaunay三角网

图3 同名路段融合

1.4 道路网VGI数据匹配与融合算法过程

①单人采集GNSS轨迹数据筛选、数据格式转换,并将单人采集数据组织在单个图层；

②对图层中轨迹数据进行结点、弧段拓扑化处理，按链状双重独立编码记录单人道路网络数据；

③在参考图层的参考路段的首尾结点处建立缓冲区，遍历出首尾结点均落在缓冲区内的全部待匹配路段；

④根据式(1)计算待匹配路段与参考路段的距离相似度，如果相似度大于0.8则标记已匹配并记录路段编号，否则匹配失败并记为“-1”；

⑤重复③～④步，直至道路网全部路段完成匹配，并输出道路网匹配结果；

⑥根据匹配结果，若匹配结果为“-1”，则该路段无同名路段，保留原路段无需融合；若匹配结果不为“-1”，则继续进行⑦～⑧步；

⑦以参考路段为基准，稀释调整路段点密度，并在同名路段间建立Delaunay三角网；

⑧根据权重比依次计算各分割点，连接各分割点得到融合后路段，并判断融合后路段与参考路段方向是否一致，若不一致则反向存储；

⑨重复⑦～⑧步直至全部路段融合完成并输出道路网VGI数据融合结果。

2 实验及结果分析

基于Visual Studio 2010开发环境，利用C+调用ArcGIS Engine 10.2对本文的算法予以实现，对多人沿道路行走记录的GNSS轨迹数据进行处理，实现VGI道路采集数据的匹配与融合。

2.1 道路网VGI数据获取

本文以某大学校园道路网为例，多人次独立利用带GNSS单点定位功能的智能手机进行校园道路网VGI数据的采集。所采集的GNSS轨迹数据的水平精度为10 m，垂直精度为5 m，经过预处理，本次实验选取4组道路网VGI数据，每组包含77条路段。

四组原始观测数据如图4(a)所示，选取图中圆圈内两组原始观测数据进行对比如图4(b)所示。发现原始观测数据轨迹严重抖动，并且两组数据间差异明显，这是VGI数据的典型问题。

2.2 道路网匹配与融合结果

根据本文算法对以上VGI道路网数据进行匹配与融合处理，融合后的道路网如图5(a)所示，融合后的道路网明显更接近实际情况。对比融合前后道路网，选取图4(a)中圆圈处放大后如图5(b)所示，红色(深色)的表示融合后的道路，其他颜色(浅色)表示采集的原始数据，从中可见，融合后数据精度明显提高。如果融合后点位中误差小于原始观测数据的距离均方根差(DRMS)，则可认为融合成功，数据精度提高。在道路网中随机均匀选取50个特征点进行检查，发现仅有4处点位中误差比距离均方根差大，样本融合成功率为92%。

图4 原始道路网VGI数据

2.3 分析与讨论

1)将融合后的道路网与Google影像图进行叠加对比分析(如图6所示)，可见融合后道路网与实际路网重叠度较高，没有明显偏移，与Google Earth影像地图精度相近。

2)高楼附近的道路数据精度较低。融合前后均存在高楼附近道路VGI数据精度比空旷地区道路VGI数据精度低的现象，主要是由于高楼遮挡手机GNSS信号造成的。

3)VGI道路网融合后弧段的质量与匹配成功参与融合的弧段数成正相关。在样本中共有4处点位中误差比距离均方根差大，主要是误匹配或匹配失败导致参与融合路段数较少。

图5 道路网VGI数据融合结果

图6 融合后道路网与Google Earth地图叠加结果

4)选择高效的匹配算法来提高匹配率和采集多组的道路网VGI数据是提高融合后数据质量的有效方法。参与的人越多，道路网则越平顺，其精度也会明显提高。

3 结束语

本文设计了一种适用于道路网VGI数据的匹配融合的算法，实现了对多人参与的道路网VGI数据的有效匹配与融合处理。通过将处理后的道路网与原始观测道路网数据的对比，以及将融合结果与Google Earth影像地图的叠加显示，可见匹配融合处理后道路网更加平滑，数据精度明显提高，证明了该算法的可靠性。本方法在对结构规整、道路间距离较远的道路网处理时效果较好，但对结构复杂的道路网的复杂结点的匹配；对距离相近道路间如何避免误匹配现象；对首尾结点相同、路径不同的路段匹配等问题的适应性尚需进一步验证。对道路网VGI数据进行匹配与融合，可以改善VGI数据自身的缺点，通过与已有数据的对比可以快速发现变化数据并根据专业知识进行相关分析，同时也可让专业测绘部门在进行地形图测量等相关工作时有的放矢，为专业部门的地理信息更新提供良好的基础，极大地缩短专业数据的更新周期，具有较高的应用价值。

参考文献：

[1] GOODCHILD M F. Citizens as Sensors: The World of Volunteered Geography[J]. GeoJournal, 2007, 69(4):211-221.

[2] 张雪晨.探讨志愿者地理信息数据精度提升所面临的问题——针对移动设备数据的分析[J].信息与电脑,2013(6):144-145.

[3] 田文文.基于自发地理信息的空间数据变化发现与更新方法研究[D].武汉：武汉大学，2013.

[4] BEERI C,KANZA Y,SAFRA E,et al.Object fusion in geographic information systems[C]. Proceedings of the Thirtieth international conference on Very large data bases-Volume 30.VLDB Endowment ,2004:816-827.

[5] SAALFELD A. Automated Map Conflation [D].Washington DC,USA: The University of Maryland,1993.

[6] CUETO K. A feature-based approach to conflation of geospatial sources[J]. International Journal of Geographical Information Science, 2004, 18(5):459-489.

[7] LYU Haiyang, SHENG Yehua, GUO Ningning, et al. Geometric Quality Assessment of Trajectory-generated VGI Road Networks Based on the Symmetric Arc Similarity[J]. Transactions in GIS, 2017. DOI: 10.1111/tgis.12256.

[8] 郭宁宁，盛业华，黄宝群，等.基于人工神经网络的多特征因子路网匹配算法[J].地球信息科学学报, 2016, 18(9):1153-1159.

[9] 刘光孟,刘万增.线目标特征点相似性匹配[J].测绘工程,2014,23(1):35-38.

[10] 张桥平，李德仁，龚健雅.城市地图数据库图形合并技术[J].测绘通报,2003(9):27-29.

[11] 童小华，邓愫愫，史文中.数字地图合并的平差原理与方法[J].武汉大学学报(信息科学版)，2007(7):621-625.

[12] FILIN S, DOYTSHER Y. A Linear Mapping Approach to Map Conflation: Matching of Polylines [J]. Surveying and Land Information Systems,1999,59(2), 107-114.

[13] 唐文静，赵玉新，郝燕玲，等.数字地图点状要素合并变换算法研究[J].系统仿真学报，2009(5):1399-1402.

[14] 唐炉亮，刘章，杨雪，等.符合认知规律的时空轨迹融合与路网生成方法[J].测绘学报, 2015(11): 1271-1284.

[15] 王鹏波,武芳,翟仁健.一种用于道路网综合的拓扑处理方法[J].测绘科学技术学报, 2009, 26(1):64-68.