王 鹏，郑贵省，王 元

(1.军事交通学院 研究生管理大队，天津 300161；2.军事交通学院 基础部，天津 300161)

基于多相似度量指标的路网匹配算法研究

王 鹏1，郑贵省2，王 元1

(1.军事交通学院 研究生管理大队，天津 300161；2.军事交通学院 基础部，天津 300161)

路网数据融合是路网数据更新以及提升数据质量的重要方法之一。而路网数据融合的关键技术在于路网匹配。结合路网数据源的特点，提出了一种顾及路段和结点拓扑关系，基于语义、几何和拓扑多种相似度量指标的路网匹配算法。通过实验表明，该算法能在不同尺度的路网数据中准确识别出互相匹配的路段,具备可操作性和实用性。

路网匹配；拓扑关系；相似度量指标

0 引言

随着计算机技术的不断发展，地理信息系统(Geographic Information System, GIS)的运用已经涵盖各行各业。在道路交通领域，已经将GIS用于车辆导航、路政设施管理、交通规划、路面管理等各个方面。目前，我国路网建设发展迅猛，道路空间位置和属性变化周期大大缩短。及时准确地掌握道路空间数据，维护数据的现势性，关系到基于路网空间信息各种服务的准确性和有效性。由于空间数据采集周期长，花费代价大，特别是路网数据其变化周期短，因此很难及时有效地进行更新。在目前的GIS应用中，已经采用匹配技术将不同来源和不同尺度的数据源进行融合和集成，用以提高数据的质量，解决数据不一致等问题[1]。在路网匹配研究中，研究人员已经提出了许多路网匹配算法[2-7]，但主要是针对特定的数据源，而且算法主要依靠路段自身的相似性进行度量，并没有顾及路网整体结构的影响和制约。因此，本文根据数据源的特点，提出一种顾及路段和结点的拓扑关联关系并基于语义、几何和拓扑多种相似度量指标的路网匹配算法，并利用ArcGIS平台和Python脚本语言来开发了相应的路网匹配脚本工具。

1 路网匹配相似度量指标确立

路网匹配主要是根据不同数据源中对同名道路实体的识别和数据交换，主要识别路网中的同名路段和同名结点。根据路网空间的数据特点对同名实体之间的相似性进行判断，以此来判断是否相互匹配。本文根据数据源的特点，建立如下几种相似度量指标。

1.1 语义

空间数据具备丰富的属性信息，即语义信息。如描述道路的名称、宽度、长度等属性。由于数据的多来源和多尺度特点，往往存在属性缺失。或由于各自领域和专业的使用习惯、命名方式和专业术语的不同，导致属性项的不同。因此语义相似度的计算对数据模型和属性数据模型的依赖很大[1]，往往不同的数据需要采用不同的计算方式。但是在局部区域中，不同来源的路网空间数据，如果存在对道路实体唯一和非歧义的描述(例如道路名称)，即可认为是同名路段。使用道路名称进行相似度量的前提是数据源对道路名称描述的字段必须非空。

1.2 几何

在GIS数据库中，路网数据一般以ployline和point的形式进行存储。路段由ployline构成，point是路段的端点和路段之间的交点。ployline由一系列的点按顺序构成，因此道路实体的相似可以采用距离和方向等几何特征来度量。在道路空间数据中，距离主要用来描述实体之间的位置关系。这里使用欧式距离来进行表示，其计算公式为：

(1)

其中D表示点(xs,ys)和点(xt,yt)之间的距离。其主要用于点和点之间、点和线之间匹配的距离度量。由于道路实体由ployline的形式进行存储，一条ployline一般由若干个具有坐标的隐藏折点组成的多条线段构成，如图1所示。

图1 ployline的组成形式

两条路段的空间距离可以通过计算一条路段上的折点P1、P2,…,Pn到另一道路段的最短欧式距离di(i=1,2,…,n)，如图2所示。然后统计最短距离小于距离阈值d的个数，记为m。m/n的值越接近1，则两条路段互为同名路段的可能性越大。

图2 隐藏折点到路段的距离

方向主要用来判断道路实体的“走向”，是相似性度量的一个重要参数。方向主要用路段首尾结点形成的角度来表示，如图3所示。

图3 道路弧段的方向

弧段的首尾结点坐标分别为P0(x0,y0)和Pn(xn,yn)，路段的方向角度可以用计算公式表示为：

(2)

1.3 拓扑

拓扑相似是指不同数据源路段与结点构成的拓扑关系相同的程度。其主要由连接结点的路段数量(即结点的度)以及与结点关联路段的方向来进行比较和判断[8]。道路结点的度类型如表1所示。

表1 道路结点的度类型

当数据尺度差异较大时，依靠结点度无法进行拓扑相似度的判断。如图4所示，结点A1和B1在空间距离上非常相近，而且具有相同的度，但其不是相互匹配的结点。因此，采用与结点关联路段的方向来对结点的类型进行进一步的判别。以结点作为原点，建立平面直角坐标系，计算路段的方向，根据其与X轴正方向形成的角度，进一步确定结点是否匹配。

图4 依据结点的度进行判断产生的错误匹配

1.4 路段匹配判定标准

由于道路网是一个整体的空间结构，如果单独采用上述特性进行相似判断，必然会产生较大的错误。因此，本文根据道路网路段和结点的拓扑关系，建立参考路网数据R和目标路网数据T路段之间多个度量指标约束的匹配判定标准。如下式所示：

(3)

2 匹配算法过程

一般来说，在路网拓扑中，两条对应的匹配路段，其对应的结点是匹配的。而两条路段的结点匹配，不一定能保证路段之间匹配，但是可以作为路段匹配的约束。根据上述原则建立的匹配标准，本文从语义、拓扑和几何三个层次进行路网匹配，通过结点和路段之间的依赖关系，来确定匹配路段和结点。如图5所示。

图5 匹配中路段和结点的依赖关系

匹配算法的基本思路如下：

(4)不断重复步骤(2)和(3)，直至参考数据中路段和结点全部遍历。

完成上述步骤后，能将大部分的同名道路实体识别出来，主要是进行路段1：1的匹配。但由于路网数据的采集来自不同的部门，因此对道路实体的空间描述和表达存在较大的差异，使得同名道路实体具备多种匹配关系，如图6所示，实线表示小比例尺的参考数据R，虚线表示大比例尺目标数据T。

图6 同名道路实体存在的匹配对应关系

在未匹配的路段中，可能存在n:1、1:n和m:n三种匹配关系。通过对参考数据集中路段建立一定距离阈值的缓冲区[5]，根据缓冲区与目标数据集中路段的位置关系确定候选匹配路段，最后根据相似度量指标确定候选匹配路段是否与参考路段匹配。其原理如下：

(1)对于1:n匹配类型，以参考数据中的路段r1，建立半径为ΔD的缓冲区，如图7(a)所示。对落在缓冲区中的一系列目标弧段{t1,t2,…,tn}，根据拓扑关联关系进行连接，将连接后的弧段与参考弧段r1根据式(3)进行相似度量，判断其是否匹配。

(2)对于n:1和m:n的匹配类型，参考路段建立缓冲区后，可能没有完全落在缓冲区内的目标路段，若缓冲区内没有目标路段，说明该参考路段无匹配路段。若缓冲区内只存在目标路段的一部分，如图7(b)所示，r2建立缓冲区后并没有将t1完全包含进去，这时选择与r2关联的一条路段。这里假设选取r3，将r2和r3合并成一条路段，再创建缓冲区，缓冲区将包含目标路段t1和t2。然后根据式(3)判断r2、r3和t1、t2构成的整体路段是否匹配。若r2、r3构成的整体路段形成的缓冲区还未完全包含参考路段，则继续连接其关联路段创建缓冲区，直到缓冲区存在完整的目标路段。

图7 缓冲区增长匹配

在缓冲区增长法匹配中，可能会出现如图8所示的情况。t3、t4构成的路段与t1、t2、t3构成的路段均可作为参考路段r1的候选匹配路段。在这种情况下，选取各指标值更加接近的一组作为匹配路段，即选择t1、t2、t3与r1匹配。

图8 缓冲区增长后出现多候选匹配路段

综上所述，匹配策略主要流程为：先根据道路名称进行初始路段匹配；由初始匹配路段确定初始匹配结点；由匹配判断标准判断与初始结点关联路段的是否匹配，完成路段的1∶1匹配；在未匹配的路段中，对非1∶1匹配采用缓冲区增长匹配进行匹配判定。其具体流程如图9所示。

3 算例分析

根据上述匹配算法，本文利用ArcGIS平台，结合Python脚本语言开发了路网匹配工具。在Python中通过导入ArcPy站点包来访问ArcGIS的地理处理功能，通过OGR包来读取道路空间数据，并获取数据的属性信息和几何信息。利用Python中的函数来进行匹配指标计算。

选取面积约为38平方公里的某地区内的不同尺度的路段数据，对本文提出的匹配算法进行验证。以小比例尺的作为参考数据，大比例尺的作为目标数据，如图10所示。

对提取的路网数据进行拓扑处理和提取结点，生成参考路段507条，目标路段1 203条；参考结点324个，目标结点805个。再对路网数据进行校准和叠加，如图11所示。从图中可以看出，尽管路网数据的吻合度较高，但是在局部地区仍然存在着一定的差异。

利用路网匹配工具箱对路网进行匹配，根据数据的精度和质量，设置比例系数为80%，距离阈值为30 m，方向角度差阈值为15度，缓冲区半径为40 m。匹配结果如图12所示。对匹配结果进行统计，路段的匹配率为94%。对不能进行匹配的路段进行分析发现，由于数据受到采集以及绘制等各类因素影响，其质量无法得到完全保证。在局部区域，存在着数据差异过大的情况，因此导致匹配失败。但是匹配结果能与人工检查结果保持一致，能将匹配和未匹配的数据进行分离，方便对未匹配的路段进行人工检查，具备可操作性和实用性。

图9 路网匹配流程图

图10 参与匹配的路网数据

图11 路网叠加

图12 路网匹配结果

4 结论

本文针对不同尺度下路网匹配的问题，提出一种顾及路段和结点的拓扑关联关系并基于语义、几何和拓扑多种指标的路网匹配算法。其充分利用了路网中结点和路段的拓扑关系，顾及了路网的整体性，而且不需要进行复杂的计算及对路网数据进行过多的分段处理，使得匹配工作更容易实现。实验表明，该算法具有实用性和可操作性。

[1] 唐文静.多源地理空间矢量数据融合[M].北京：清华大学出版社，2014.

[2] 胡天硕,毛政元.线实体候选匹配集的优化方法研究[J].测绘科学,2011,36(2):132-135.

[3] 田文文,朱欣焰,呙维. 一种VGI矢量数据增量变化发现的多层次蔓延匹配算法[J]. 武汉大学学报(信息科学版),2014,39(8):963-966.

[4] WEISS R, WEIBEL R. Road network selection for small-scale maps using an improved centrality-based algorithm[J]. Journal of Spatial Information Science, 2014(9): 71-99.

[5] WALTER V, FRITSH D. Matching spatial data sets: a statical approach[J]. International Journal of Geographical Information Systems,1999,13(5):445-473.

[6] WILL J. Development of an automated matching algorithm to assess the quality of the OpenStreetMap road network-A case study in Goteborg, Sweden[D]. Lund(Sweden): Lund University ,2014.

[7] 胡云岗,赵仁亮,李志林,等.地图数据缩编更新中道路数据匹配方法[J].武汉大学学报(信息科学版),2010,35(4):451-456.

[8] ZHANG M. Methods and implementations of road-network matching[D]. Munich(Germany): Technical University of Munich, 2009.

Research on road network matching algorithm based on multi similarity measure criteria

Wang Peng1，Zheng guixing2，Wang Yuan1

(1.Postgraduate Training Brigade，Military Transportation University，Tianjin 300161，China；2.General Courses Department，Military Transportation University，Tianjin 300161，China)

Road network data fusion is one of the important methods, which can be used to improve data quality and update data. And the key technology of road network data fusion is the road network matching. According to the characteristics of network data sources, a road network matching algorithm based on geometry, topology and semantics multi similarity measure criteria is proposed, which takes into the consideration of topological relations between the road arcs and the nodes. Experiments show that the algorithm can accurately identify the matching road arcs in different scales, and it is operable and practical.

road network matching; topological relations; similarity measure criteria

P208

A

1674-7720(2016)01-0019-04

王鹏,郑贵省,王元.基于多相似度量指标的路网匹配算法研究[J].微型机与应用,2016，35(1)：19-22，26

2015-09-09)

王鹏(1990—)，通信作者，男，硕士，主要研究方向：交通信息工程及控制。E-mail:1741760653@qq.com