1 引 言

随着传感器技术与地球空间信息科学的发展,空间数据的采集、建模、融合、更新等正处于快速发展时期。实际应用中常需要对不同设备、不同部门采集的同一地区的多源、多尺度空间数据进行有效集成,以用于信息共享与变化检测。空间数据匹配是实现空间数据变化检测和更新的前提条件,其目的是建立同一区域内两份或多份数据间同名目标的对应关系,通过这种对应关系可以实现两者的属性共享和几何精度改进^{[1, 2]},亦可对无对应关系的目标进行变化检测和数据更新^[3]。众源(crowdsourcing)地理数据,如欧洲的"开放式道路地图"(open street map,OSM)的出现,为空间数据的更新提供新的、免费的数据源。然而,由于其生产过程非标准化,众源数据匹配给传统的空间数据匹配方法带来新的挑战。

文献[4]对空间数据匹配的研究现状进行了系统的总结。对路网匹配而言,部分学者通过计算与候选路段间的几何、拓扑、语义等相似性特征选取最优的匹配路段^{[5, 6, 7, 8, 9]}。多源空间数据之间通常存在非刚性偏差,通过几何、拓扑、语义等相似性可以确定多条可能的候选路段,但很难进一步确定实际的匹配路段,因此,需要考虑在整个路网中与其他匹配对之间的兼容性。一些学者将相似性指标融合成概率或其他综合指标,考虑邻接目标的匹配关系更新自身匹配概率^{[10, 11, 12, 13]}。文献[11, 12]尝试利用概率松弛法解决矢量道路匹配问题,实现了1:1的道路节点对应,但需要进一步建立路段间的对应关系,文献[13]将概率松弛法直接应用于路段,需要设定多种阈值,且匹配概率受路网密度影响较大。文献[11, 12, 13]忽略1:0匹配,即无对应关系的独立路段,这些独立路段是潜在的变化检测目标。另外,由于OSM等众源数据的非标准化表达方式以及内部尺度不一性,以不同数据作为参考得到的结果不一(即存在匹配方向性问题),且1:N、M:N的对应关系很难有效识别。

概率松弛匹配方法在计算机视觉和模式识别领域是一种经典的图匹配方法^[14],该方法首先对两份图结构建立初始匹配矩阵,再结合邻域目标的结构关系启发式地更新初始的匹配矩阵使之达到全局最优。城市道路网是一种复杂的图结构,实现路网匹配需要综合考虑位置、形状、结构等特征,采用概率松弛法能够将多种约束有效结合,实现路网的整体匹配,而不是局部映射。因此,本文在改进文献[13]的概率和兼容函数计算模型基础上提出一种基于概率松弛法的城市路网自动匹配方法,该方法能够建立1:0的匹配关系,减少阈值和路网密度的影响。最后,本文选取不同地区的两份路网数据进行算法验证。

根据文献[11, 12, 13],概率松弛匹配方法包括概率矩阵初始化和迭代更新两个基本过程。本文考虑路网的复杂性增加了匹配结果选取过程,具体算法流程如图 1所示,主要分为3步:①利用缓冲分析检测候选匹配路段,然后根据候选路段间的几何差异指标计算不同匹配方向的概率并综合得到初始概率矩阵;②由于初始概率未考虑邻接路段对其的兼容程度,即兼容系数,本文通过邻接路段间的相对关系计算两邻接匹配对的兼容系数,并基于各邻接匹配对的兼容系数计算所有邻接路段对其的综合影响,即支持系数,然后根据支持系数不断更新原概率矩阵,直到概率矩阵变化量收敛于某一极小值;③计算各候选匹配对的结构相似性,结构相似性反映某一匹配对及其邻接路段间的整体匹配程度,之后基于结构相似性设定一定规则选取稳健匹配集,识别1:1和1:M,并对1:M进行匹配增长,综合得到最后匹配集。

图 1 本文算法流程 Fig. 1 Flow chart of the proposed method

图选项

假设待匹配两份数据data₁={N₁,E₁},data₂={N₂,E₂},其中N代表端点集,E代表路段集。本文首先通过缓冲分析确定data₁与data₂之间的候选匹配路段,再计算候选路段间的差异性指标并综合得到初始的概率矩阵。差异性指标是描述两候选路段间差异的指标,评价线性目标的差异性指标有距离、方向、长度、语义、拓扑等^{[5, 6, 7]},本文采用距离、方向、长度衡量路段间差异特征。对一种差异性指数t (t=dis,dir,len,分别表示距离,方向,长度差异性指标),根据文献[10]按公式(1)计算路段j∈N₂匹配到路段i∈N₁的概率。当j=-1时,表示路段i匹配到空(1:0)的概率

点击浏览公式

点击浏览公式

同理,计算从data₁到data₂的误差因子和路段i匹配到路段j的概率。实际上,匹配概率应为两路段相互匹配的概率,即i匹配到j且j也匹配到i的联合概率。因此,需将不同方向匹配的概率综合为相互匹配概率,公式如下

点击浏览公式

候选匹配对(i→j)的概率定义为不同匹配方向概率的调和平均数^[15]。i没有匹配路段的概率p^t(i,-1)定义为i匹配到空且所有候选路段不匹配到i的概率,同理,j没有匹配路段的概率为p^t(-1,j)。

为综合多种差异指标^[6],本文分别计算3种差异指标的匹配概率,加权平均得到综合的初始概率。距离、方向、长度的权值分别为0.3,0.4,0.3。

初始概率矩阵确定以后,需计算各匹配对的邻接路段对其的兼容系数以不断更新原概率矩阵。兼容系数反映了邻接匹配对间的兼容程度,而通常邻接匹配对不止一个,需要综合这些邻接匹配对的影响,即支持系数来改进初始概率矩阵,使之更准确地反映整个路网的匹配关系。另外,考虑到路段匹配可能存在部分匹配,即1:M,而根据一定的距离或长度比阈值很难有效识别这类型匹配。如图 2(a),路段a₁和b₁的长度,起终点距离皆相同,根据文献[13]将被误识别为1:1匹配,而实际匹配应为(a₁→b₁,b₂)。因此,需要考虑部分匹配对自身的兼容性。

图 2 部分匹配与兼容系数计算 Fig. 2 zrtial matching and calculation of the compatibility coefficient

图选项

基于文献[12],本文考虑邻接路段的相对位置,方向计算兼容系数,一定程度上克服数据本身的旋转和缩放误差。如图 2(b)所示,计算邻接匹配(h→k)对(i→j)的兼容系数C (i,j;h,k),公式为

点击浏览公式

点击浏览公式

而某一候选匹配对的概率受到多个邻接匹配对的影响,需要综合所有邻接匹配对的影响以计算支持系数。如图 3所示,对于候选匹配对(i→j),F₁,F₂和T₁,T₂分别为对应起点和终点,相应的,S_F、Q_F和S_T、Q_T为i和j在起点和终点处的邻接路段集。如表 1所示,不同匹配方向的支持系数皆由起点、终点处支持系数构成,q₁和q₂为(i→j)是完全匹配和部分匹配假设下的支持系数,本文取两者中较大值。

图 3 计算支持系数 Fig. 3 Calculating the support values

图选项

例如，当j匹配到i时，在起点的支持系数q_i,F为

点击浏览公式

点击浏览公式

η_i为i匹配到空的先验值，计算公式为

点击浏览公式

最后根据文献[11]提出的迭代机制重新计算概率，以路段j匹配到i为例，公式为

点击浏览公式

根据不同匹配方向计算的概率按类似公式(3)综合得到新的概率矩阵。如此迭代,直到概率矩阵变化量小于某一给定阈值ε。

为有效克服误匹配和漏匹配,本文设定以下3步用于匹配对的选取。

第1步:计算结构相似性。结构相似性反映某一匹配对及其邻接路段间的整体匹配程度,本文定义候选匹配对(i→j)的结构相似性为

点击浏览公式

第2步:选取稳健匹配对。若(i→j)满足等式(11),则(i→j)为稳健匹配对,添加到队列queue中。

点击浏览公式

之后,需逐一检测queue中每一匹配对与邻接匹配对是否兼容。如图 4所示,当两邻接匹配对M_n,M_p的中间结点(a₂,b₂)不同时是M_n或M_p的对应端点,则认为M_n、M_p相互不兼容。对于不兼容的两邻接匹配对,本文保留结构相似性大的,删除结构相似性小的。

图 4 邻接匹配对之间的兼容性检测 Fig. 4 Detecting the compatibility between two neighbouring matching pairs

图选项

第3步:检测1:M匹配对。对于queue中每一匹配对,判断其对应起点和终点是否皆匹配,如果匹配,则为1:1对应,否则应为1:M匹配。判断匹配对(i→j)在某对应端点处是否匹配,应满足以下条件:①若(i→j)在对应端点处的结构相似性大于i和j的其他匹配对在该对应端点处的结构相似性;②(i→j)在该对应端点处的邻接匹配对中至少存在一匹配对M∈queue。

若(i→j)在某对应端点处满足条件①和②,则认为(i→j)在该对应端点处是匹配的。如果(i→j)的对应起点和终点皆匹配,则该匹配对为1:1匹配,否则为1:M的匹配。逐一检测queue中的每一匹配对是否1:M的匹配对,若是,则添加到临时队列temp。

逐一遍历temp中的每一匹配对,如图 5中(i→j),若起点不匹配,则从短路段i的起点开始,遍历其邻接路段集G={g₀,…,g_k,…,g_n},从中选择与j的结构相似性最大的g_k,添加新的匹配对(g_k→j)到queue,再从g_k的邻接路段中寻找与j的结构相似性最大的路段,组成新的匹配对添加到queue中,如此循环直到找到j的起点的匹配端点。若(i→j)的对应终点也不匹配,则进行同样的匹配增长过程。进行完匹配增长后,对新的queue中每一匹配执行第2步中的兼容性检查,同样保留结构相似性大的,删除结构相似性小的。

图 5 匹配增长过程 Fig. 5 Matching growing from unmatched nodes

图选项

本文选取中国武汉,瑞士苏黎世的两份路网数据进行匹配算法的验证。武汉为四维图新(NavInfo )导航数据与OSM数据匹配,苏黎世为NAVITEQ 导航数据与OSM数据匹配,空间参考为WGS-84,各数据的节点、路段统计如表 2所示。导航数据格式为*.shp,OSM数据格式为*.osm,首先利用FME将OSM数据转换为统一的*.shp,并通过Microsoft Visual Studio 2008(C#)+ArcGIS Engine 9.3实现本文匹配算法,其中武汉、苏黎世的缓冲距离分别设为200 m和40 m,迭代终止阈值设为0.000 5。

试验的部分结果如图 6所示,黑实线为导航数据,灰实线为OSM数据,虚线为匹配路段的中点连线,其中图 6(a)、(b)为武汉地区试验结果,图 6(c)、(d)为苏黎世地区试验结果。由图 6(a)可见,对于武汉地区,OSM数据由于配准精度不高,与专业的导航电子数据的偏差达上百米,而本文方法可以有效地克服这种偏差实现整体匹配最优,图中虚线椭圆中匹配的两条路段位置不是最近的;图 6(b)说明本文方法能够较好地匹配复杂路网结构。图 6(c)中,OSM数据在某些区域要比导航数据详细,将OSM数据匹配到导航数据或反过来,得到的匹配结果不同,本文方法不受匹配方向影响,有效避免独立道路误匹配到另一份数据中最相似道路。图 6(d)表明本文能有效处理众源数据中可能存在结构不完整的路网,虚线椭圆中OSM路段由于用户编辑错误导致连通道路断开。

图 6 试验匹配结果 Fig. 6 The matching results

图选项

为定量评价本文算法的匹配精度,通过与人工匹配对比,计算匹配的准确率P和召回率R公式为

点击浏览公式

如图 7所示,通过缓冲分析确定灰色的路段a₁、a₂的候选路段,分别统计迭代过程中路段a₁、a₂与各候选路段的概率变化,如图 8(a)和(b)所示。由图 8(a)可见,相比a₁的其他候选路段,a₁与c₂的初始概率最高,且在迭代过程中仍保持较高概率,并收敛于某一稳定值;由图 8(b)可见,虽然a₂与d₁、d₂的初始概率最高,但通过不断迭代,a₂与d₄、d₅的概率达到最高并收敛于某一稳定值。结果表明,本文方法结合邻接路段的匹配关系对概率矩阵进行迭代更新,可以帮助寻找正确的匹配路段,并有效降低误匹配率。

图 7 迭代过程举例 Fig. 7 The matching examples for relaxation

图选项

图 8 迭代过程中概率变化 Fig. 8 Matching probability change during iteration

图选项

为分析本文方法对参数的敏感度,本文设定5组缓冲距离(100 m,150 m,200 m,300 m,and 400 m)对武汉地区进行多次试验,试验结果中的正确匹配,错误匹配,模糊匹配数目统计如图 9所示。由图可见,阈值设为150 m至400 m之间时,匹配精度大约为95.4%~97.2%,而当阈值为100 m时,精度降为67.4%,说明本文方法一定程度上不受阈值的影响,可以达到95%以上,但使用较小的阈值导致不能完全检测可能的匹配路段,使匹配精度降低。为取得较高匹配精度,建议使用稍大的阈值,然而,过大的阈值将导致计算时间的增加。

图 9 不同缓冲阈值下的精度比较 Fig. 9 Matching precision of different buffering thresholds

图选项

本文方法考虑自身的几何相似性以及邻接候选匹配路段的兼容性,迭代计算候选路段的匹配概率,最后基于收敛的概率矩阵选取最后的匹配结果。试验结果表明,该方法对偏差较大的路网数据能达到较高的匹配精度,不存在匹配方向性问题,且能够识别1:0和1:M的匹配关系,该方法适用于偏差较大、存在一定尺度差异的路网数据,可用于存在不完整拓扑的众源路网与专业数据的集成,同时为路网更新和变化发现提供了关键技术支撑。未来的研究将侧重于计算效率的改进,基于匹配关系的变化提取和数据更新。