基于图文法的城市道路匹配方法

作 者 信 息

包永钢

( 太原市测绘研究院,山西 太原 030001)

【摘要】提取多源城市路网交叉口节点,每个节点都有唯一的结构模式信息,将城市道路网的节点匹配转化为图匹配中的最大公共子图问题,采用最小图编辑距离衡量两份道路网数据中道路节点的匹配程度,并且加入距离和方向统计,寻找结构形态最为相似的道路节点。实验表明,相对于传统的点线匹配方法,当两份数据存在不均匀偏移时,基于图论的匹配方法可以更完全地利用拓扑信息,使用上下文相关的拓扑分析方法帮助提高几何和语义的匹配结果,该方法不依赖于任何非空间语义信息,原则上可以应用于各种数据源,有效提高匹配准确度。

【关键词】图文法;城市路网;结构模式;节点匹配

【中图分类号】P208 【文献标识码】A 【文章编号】1672-1586(2020)05-0102-06

引文格式:包永钢. 基于图文法的城市道路匹配方法[J].地理信息世界,2020,27(5):102-107.

正文

0 引 言

城市道路是城市的基础骨架之一,随着城市管理越来越精细化、智能化,城市路网数据来源也越来越广泛。不同来源的数据在精度、尺度、空间关系、语义表达、数据存储等方面存在不一致性,将多源路网数据进行匹配对于实现数据融合、快速更新、提高数据共享价值、节省采集资源等方面具有重要意义。近年来,随着移动互联网的发展,路网匹配是基于位置服务中的关键步骤, 它将全球定位系统(Global Positioning System,GPS)轨迹点匹配到实际路网上。以此为基础对数据进行分析和挖掘, 能够辅助解决城市计算中相关问题。

国内外的学者在地理空间数据匹配和融合方面做了大量的研究,并取得了许多优秀的成果。总体来说,这些匹配方法基本原理是根据待匹配数据的特点,选择几何、拓扑和语义这3种属性作为数据匹配的主要方法。几何匹配通过提取、比较不同数据集的几何特征,在另一份数据集中寻找具有相同或相似几何特征的对象来实现相应地物的匹配,一般来说,几何匹配需要两份数据的相应对象在距离、位置、方向、形状等方面具有很高的相似性。拓扑匹配利用两份数据各自的拓扑关系进行匹配,这种方法能够应用于整个路网的匹配,但是它对数据的拓扑关系要求较高,也需要匹配数据之间有很高的拓扑相似性,相对几何匹配来说,这种方法比较灵活、高效,一旦道路节点相互匹配,就可以根据节点和弧段的关系推断出弧段和弧段的匹配。语义匹配又称为属性匹配,语义是数据在某个领域上的解释和逻辑表示,当两份数据具有某一相同或相近的语义信息时,该方法非常有效。但目前关于语义的智能化匹配方法还不成熟,多数情况是把语义匹配作为一种辅助方法来提高数据的匹配程度。

常用的城市路网匹配方法是基于缓冲区增长、迭代最邻近点方法或这些方法的组合和改进,这些方法属于几何匹配范畴,在一定的实验区域里可以得到较高的匹配率,但对于复杂路网存在匹配不确定的问题。此外,这些匹配方法局限性较大,很难适应不同数据源道路的整体匹配问题,适于同一数据提供者提供的数据。城市路网数据虽然来源广泛,但不同来源的数据其结构具有相似性,如果能够提取并分析路网中蕴含的结构特征,作为匹配的基础依据,将会得到更好的匹配效果。因此,本文选取拓扑关系进行匹配,首先利用图文法描述路网中路段和交叉口结构模式,使道路节点之间能够相互区分,然后通过寻找两个结构间的最大公共子网,选取相似度最高的道路节点作为最佳匹配节点,以获得多源道路网数据之间更可靠的匹配度。本文编写了程序进行匹配实验,结果表明,该方法使用上下文相关的拓扑信息进行匹配可提高匹配程度,而不必依赖于空间几何信息,这种方法具有一定的灵活性、普遍性,比较适合不同区域、不同来源路网数据之间的匹配。

1 基于图文法的城市路网数据匹配原理

1.1 图文法道路结构模式描述

图文法最早是为了解决图像处理问题,此后学者们在理论和应用方面进行了大量探索,在图文形式化定义和方法实现方面取得了许多成果。近年来,图文法在模式识别领域中得到较好的发展。本文利用图文法实现两个道路网结构模式描述,进而进行路网的匹配。

使用图文法结构,能直观准确地表达道路中的连续要素,而且能突出要素的整体结构和局部结构。如道路结构的图文法表示如图1所示,其中图1a和图1c表示三角形交叉口和三环交叉口,图1b为他们的图论表达,集合n表示节点,集合a表示节点之间的连线。图2为图文法关系表,V为节点标识符的集合,E表示有向弧段,集合Rv表示节点的编号,集合RE表示边的编号,集合G表示节点连线与有向弧段的对应关系。

图1 三角形交叉口、三叉环交叉口示意图及其图论表达

Fig.1 Diagrams of triangle intersections and trigeminal intersection by graphics theory

图2 图文法关系表

Fig.2 Representations of graph grammar

所有的道路节点可按上述方法进行结构化描述,当对所有的道路节点进行结构化描述之后发现,某些道路节点在图论结构上是一致的,如图1c所示的三环交叉口,其图论表达和图1a的表达是一致的。但在道路网上弧段的角度和连接长度均存在差异,即在图中边的属性不同,因此还应结合道路节点间的形状信息描述道路的结构模式特征。可采用方向、长度和节点类型来描述道路节点的形状上下文特征。如图3所示,道路间的方向差异ρdθ和长度差异dρ可以由向量

表示。

图3 图方向差异和长度差异

Fig.3 The difffferences of graphics directions and length

1.2 基于结构模式的多源路网数据匹配原理

分别用图文法描述两份道路数据交叉口的结构特征后,道路匹配可以转换为两个图结构模式之间的匹配,其主要方式是通过构建连通图在另一份数据中寻找最优的匹配连通图,连通图之间的匹配程度可通过计算最大公共子图获得。两个图结构越相似,那么它们的公共部分就越多,即存在一个公共子图,可以用最大公共子图来度量两个图结构的相似度。下面给出一组图形来更好地说明最大公共子图,如图4所示。

图4 无向连通图

Fig.4 An example of undirected connected graph

图4a~图4d中给出了4个已经确定节点对应关系的无向连通图,其中图4a是图4b~图4d之间的最大公共部分。图4b与图4d相比,多了DE和EC边;图4c与4a相比,多了边EC;图4b与4a相比,多了DE和EF边。可以看出,图4b~图4d均可由4a通过删除或添加线条,或平移等途径相互转换,两个图结构的相似程度即最大公共子图可以通过修改图结构的形式实现,其修改步数定义为图编辑距离,而最小编辑距离即反映两个图之间的最大公共部分。最小编辑距离计算常使用KM算法(Kuhn-Munkras Algorithm),即二分图最佳匹配算法实现。

道路中每个节点的连通图不同于图论中抽象的连通图,城市道路数据中的节点具有明确的位置,边是一种实体连接,具有明确的意义[3]。因此,在寻找2个三阶连通图的最大公共子图时,应综合道路节点和路段的长度、方向、形态等几何特征,距离接近、方向相似,并且长度差异较小的道路连接更接近构成公共子图中的公共边。

2 基于图文法多源路网数据匹配流程

图5为本文实现基于图文法的多源路网数据匹配的主要流程。其中,数据预处理、建立节点连通图、图文匹配是匹配流程的关键步骤,本文进行详细说明。

图5 基于图文法的多源路网数据匹配流程

Fig.5 Matching process of multi-source road networks >

2.1 数据预处理

数据预处理包括数据分析、节点和路段生成、对节点数据的几何信息表达和存储三部分。

1)数据分析。获取数据后,需要详细分析两份数据的特点,主要包括数据内容、现势性、精度、拓扑质量等,为了提高匹配效率和正确性,两份数据的尺度、坐标系应一致,同时依据数据情况将明显不能匹配的区域剔除,对于拓扑比较差的数据应进行处理。

2)节点、路段生成。首先利用原始数据生成节点和路段,对原始数据进行拓扑关系提取;然后计算节点的度信息,节点的度是指连接该点的线条数;最后删除度为2的节点,并合并度为2的路段线,消除伪节点。

3)节点数据几何信息表达。道路数据的数据量比较大,加之数据在不同工具软件间进行交互时会延长数据处理的时间,降低数据处理的效率。为了从整体上加快数据处理的速度,在数据处理的环节即将整个算法实现中所用到的点的编号、坐标信息,线的编号、长度及线与线之间的角度、距离、拓扑位置关系等信息都提取出来,以提高后续匹配过程中结构形态的计算速度。点数据形式主要存储节点ID、节点坐标、节点连接路段名等信息;路段数据主要存储路段ID、起止、相连路段的公共点、夹角信息。

2.2 节点连通图的建立及存储

这一步从匹配的有效性、准确性等方面出发,构建节点的图结构存储形式。具体操作方法是各自从两份数据中找到一个点,沿着连接线向外扩散,找到与它相连的点,将这种连接信息通过矩阵存储起来,方便进行匹配。以一个例子详述节点连通性的图存储方法。

图6 道路网节点存储示意图

Fig.6 Storing sketch of road networks nodes

图6a所示的道路节点,两节点之间相连记为1,不相连的记为0,可建立一个5×5的数组来存储该图节点数据的图结构,如图6b所示。对直线的两夹角进行判断,将夹角接近180°的数据提取出来,图6a中的AC和CE两条直线夹角接近180°,可以认为A点和E点是直接相连的,将数组进行修改,如图6c所示。图6a中,A、B、D和E这4个点到原点C点都只有一条连线,记为以C为原点的图结构的一阶连通图。当点与C点之间的弧段有n条时,则为图结构的n阶连通图,n越大,道路结构越复杂,故而它的存储越复杂。考虑到数据匹配的高效性和正确性,本文对节点的三阶图结构进行存储。

2.3 图文法匹配

在数据匹配的过程中,对给定的目标数据,在另一份数据中遍历所有的数据,但有很多的数据是明显不能和目标数据匹配的,那么遍历这些数据效率比较低。通过建立缓冲区的形式,找出与给定目标节点一定范围内可能匹配的候选节点,计算两份数据中相邻各点三阶邻近节点所构成的图结构之间的最小编辑距离,由此可得最佳的道路节点匹配。

1)点缓冲区的建立

对数据中每个节点建立缓冲区,落入缓冲区中的点即为待匹配节点,计算节点之间的欧式距离,并将计算结果存入到名为点缓冲区的属性表中。

2)最小编辑距离计算

最小编辑距离的定义公式如式(1):

式中,Del_point (network1)为删除图结构a中的点;Del_edge(network1) 为删除图结构a中的边;Add_point (network2)为增加图结构b中的点;Add _edge(network2)为连接图结构b中的点,删除与添加一次的值都为1;MoveDis为相应点间距离小于100 m时的距离编辑值,当对应点的距离大于100 m时,认为是匹配节点,MoveDis为节点之间的距离/100。

最小编辑距离的求解常采用KM算法,通过该算法能够找到两个图结构的最佳匹配。在求解过程中还应当考虑多源道路网数据表达内容与表达尺度上的差异性。一份数据中的道路交叉口在另一份数据中可能存储为一个环路或更加复杂的结构,一条道路也可表示为道路的中心线或者两条平行线车道。因此,在寻找最大公共子图时,如果存在多个形状相似的道路节点或者道路段与另一份数据中的单个节点或单条道路对应,则应当对多个节点和道路进行合并,以反映表达尺度的差异性。

2.4 数据后处理

这个过程主要是对匹配结果进行检验,得出匹配的正确性评价,同时对于不能匹配的数据或者匹配错误的数据进行详细分析,然后进行路段数据的融合处理,最终获取满足需求的新数据。

3 城市路网数据匹配实验

本文采用山西省太原市基础地理数据和道路导航数据进行匹配实验,图7为两份原始数据及局部放大图(图中蓝线表示基础地理数据,红线表示导航数据)。基础地理信息数据来自于测绘部门,导航数据来自于交通部门,由于二者的采集方式、用途、更新频率等均有不同,数据内容丰富程度也不一样,具有较好的实验价值。

图7 待匹配的原始数据及其局部放大图

Fig.7 The representations of the whole and a part of raw >

从图7的放大图可以看出,两份原始数据坐标有偏移,而且由于数据用途不同,道路分段规则也不一致,通过建立缓冲区,采用距离、角度等设定阈值的方法进行数据的匹配,当两份数据偏移量很小的时候,这些方法有很大的优势性,但是对于本文所采用的两份原数据具有偏移量的情况下,这些方法的匹配效果都不理想。本文采用图文法的验证多源路网数据匹配的可行性,匹配程序利用AE10.1和VS2010实现。为了保证匹配算法的正确性和效率,本文选取两块典型区域进行检验,并对匹配结果进行详细分析。

实验区域1如图8所示,这块区域位于主城区,待匹配的两份数据发生偏移但偏移距离不均匀,两份数据的道路线形态相近,如按照传统的参照距离、方向、形状等因素,设定阈值建立缓冲区进行匹配是行不通的,传统的方法在给定的缓冲区内可能会出现在另一份数据中不能找到或者找到错误的点,导致实验结果的不准确性,并且由于数据的不规则,所以很难整体设定缓冲区、方向、形状等匹配标准的阈值。基于图结构的道路匹配方法,充分考虑了节点的图形结构,很好地克服了上述问题,更直观地看到匹配的效果,将部分运行结果显示在图上。

图8 实验区域1匹配结果

Fig.8 The matching results of the fifirst experiment area

值得注意的是点2143和点2244在数据中是属于双行道的交叉口,并且二者都与点2339相匹配,如图9所示,说明这种方法不仅可以解决形态相似的节点匹配,还可用于双行道交叉口的识别。

图9 双行道的匹配

Fig.9 The matching results of two-way street

实验区域2如图10所示,这块区域位于城区边缘,基础地理信息数据道路现势性较差,两份数据结构比较简单但偏移较大。在此区域中,点5863和点5815用最小编辑距离的最小值就能实现正确匹配,如图10中所标示。但是对于点5846和点5820仅仅用最小编辑距离的方法并不能正确匹配,因此可以借助距离和方向两个值进行匹配再识别,具体做法是可以统计出正确匹配点的距离和方向的分布最多的值,对于不能匹配的点,找出距离和方向最接近的候选节点,在这些点中找出编辑距离最小的道路节点,从而确定点的最佳匹配。

图10 实验区域2匹配结果

Fig.10 The matching results of the second experiment area

为了验证加入距离和方向辅助匹配方法对匹配结果的影响程度,随机选取300个节点,分别采用仅使用最小编辑距离匹配和加入距离方向辅助最小编辑距离的匹配方法,两种方法的匹配正确率统计结果见表1。

表1 匹配准确度统计

Tab.1 Statistics of matching accuracy

从表1可以看出,加入距离方向后能够显着提高匹配准确度,但对于未匹配的节点由于找不到最优的最小编辑距离,此方法并不能减少未匹配点的数量。在匹配过程中发现越远离边界,图结构信息越丰富,匹配精度越高。部分道路节点匹配错误,主要原因是数据图结构信息不足,或两个图结构差异大,故而会产生匹配错误情况,但这种情况可以作为数据更新的基础。

4 结束语

本文将道路的局部节点匹配转化为寻找两个图结构的最大公共子图问题,采用最小图编辑距离衡量两份道路数据中节点匹配程度,确定最相似的道路节点。相比传统的点线匹配方法,可以减少可能的候选匹配点,提高匹配准确性,并且在两份路网数据存在不均匀偏移时甚至坐标系不同、尺度不一,仍能比较有效地寻找出互相匹配的道路同名点,克服了传统方法的不足,提高了全局路网数据匹配效率。

以图结构中的最小编辑距离作为匹配效果的衡量指标,将路网数据整体匹配转化为寻找最优解的这一过程对于数据包含的结构信息较少的情况时,会出现匹配错误。因此,本文加入距离和方向两个数值,采用统计学的方法,对一定区域正确匹配点对的距离和方向进行统计,选出不能正确匹配的点对中落入距离和方向区域中的数值,这些点对中的编辑距离最小的点可认为是最优匹配的点对。

基于图文法的道路结构匹配不依赖于建立缓冲区、属性等任何非空间信息,对于城市道路的多源数据融合、快速更新、数据建库等具有重要的意义。但本文重点道路节点的结构特性,要求待匹配的数据中交叉口和路段应具有较好的拓扑关系,否则可能匹配准确度较低。而在实际中,非专业部门生产的数据往往并不具有比较好的拓扑特性,在匹配前要花费大量时间进行数据预处理,甚至远超过匹配过程本身所用的时间。因此,如何根据原始数据合理快速地选取有限拓扑性好的节点来实现道路的整体匹配,充分考虑数据属性信息以提高匹配方法的适用性和准确性,以及匹配后的数据自动融合将是本文进一步研究的重点。

作者简介:包永钢(1988-),男,宁夏盐池人,工程师,硕士,主要从事空间数据处理、分析研究和管理工作。

E-mail:yg.B@163.com

本期回顾

文化遗产数字化与虚拟修复

· 典型矿物颜料混合像元几何单形体端元提取算法研究

· 基于众源数据的广武月亮门虚拟修复

· 大型石窟遗产海量点云快速可视化

理论研究

· 改进的基于累加投影图匹配的点云配准算法

· 北京市城市形态与热岛强度关系的日夜对比研究

· 基于多源数据的特大城市空间结构识别及空间形态研究

· 北京市城区城市居住环境条件评价及其空间格局特征

· 基于福州市交通违法数据的时空关联规则挖掘研究

· 耦合功能连接性的TOD发展模式“节点—场所”测度模型构建

· 基于卷积神经网络的遥感影像地表覆盖分类

· 聊城市就医可达性研究

· 基于多源数据的惠州商品住宅房价分布及影响因素研究

创新应用

· 面向移动位置数据的移动性指标计算工具:设计实现与实践应用

· 基于犯罪大数据的城市基层警务设施评价与选址研究

· 一种基于网格系统的地图集版式设计方法

邮箱变更声

·《地理信息世界》邮箱变更声明

网站开通公告

·关于开通《地理信息世界》网站的公告

诚聘特约审稿专家

·诚聘|《地理信息世界》诚聘特约审稿专家

专题组稿

·约稿函|《地理信息世界》关于开辟“博士综述论坛”专栏的约稿函

·《地理信息世界》“地理信息科学一流本科专业建设” 专题征稿启事

免责声明:本文仅代表文章作者的个人观点,与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺,请读者仅作参考,并自行核实相关内容。

http://image99.pinlue.com/thumb/img_jpg/jVibtZ1LjYAXspxS6br9tpXjpV4Ud9FDyqiaKkGczI3mFxiaTQwyXummY78OvpRksO9zaTAu8hz8tFqtjqV0SvaQw/0.jpeg
分享
评论
首页