留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

利用道路分类进行道路网层次迭代匹配

王骁 钱海忠 刘海龙 何海威 陈竞男

王骁, 钱海忠, 刘海龙, 何海威, 陈竞男. 利用道路分类进行道路网层次迭代匹配[J]. 武汉大学学报 ● 信息科学版, 2016, 41(8): 1072-1078. doi: 10.13203/j.whugis20140441
引用本文: 王骁, 钱海忠, 刘海龙, 何海威, 陈竞男. 利用道路分类进行道路网层次迭代匹配[J]. 武汉大学学报 ● 信息科学版, 2016, 41(8): 1072-1078. doi: 10.13203/j.whugis20140441
WANG Xiao, QIAN Haizhong, LIU Hailong, HE Haiwei, CHEN Jingnan. A Hierarchical and Iterative Road Network Matching Method by Using Road Classification[J]. Geomatics and Information Science of Wuhan University, 2016, 41(8): 1072-1078. doi: 10.13203/j.whugis20140441
Citation: WANG Xiao, QIAN Haizhong, LIU Hailong, HE Haiwei, CHEN Jingnan. A Hierarchical and Iterative Road Network Matching Method by Using Road Classification[J]. Geomatics and Information Science of Wuhan University, 2016, 41(8): 1072-1078. doi: 10.13203/j.whugis20140441

利用道路分类进行道路网层次迭代匹配

doi: 10.13203/j.whugis20140441
基金项目: 

国家自然科学基金 41171305

国家自然科学基金 41171354

国家自然科学基金 40701157

详细信息
    作者简介:

    王骁, 博士生, 研究方向为空间数据匹配与更新等。758300176@qq.com

    通讯作者: 钱海忠, 博士, 副教授。haizhongqian@163.com
  • 中图分类号: P208

A Hierarchical and Iterative Road Network Matching Method by Using Road Classification

Funds: 

The National Natural Science Foundation of China 41171305

The National Natural Science Foundation of China 41171354

The National Natural Science Foundation of China 40701157

More Information
    Author Bio:

    WANG Xiao, PhD candidate, majors in map generalization and spatial data matching.758300176 @qq.com

    Corresponding author: QIAN Haizhong, PhD, associate professor. E-mail:haizhongqian@163.com
图(10) / 表(7)
计量
  • 文章访问数:  1165
  • HTML全文浏览量:  36
  • PDF下载量:  319
  • 被引次数: 0
出版历程
  • 收稿日期:  2014-12-25
  • 刊出日期:  2016-08-05

利用道路分类进行道路网层次迭代匹配

doi: 10.13203/j.whugis20140441
    基金项目:

    国家自然科学基金 41171305

    国家自然科学基金 41171354

    国家自然科学基金 40701157

    作者简介:

    王骁, 博士生, 研究方向为空间数据匹配与更新等。758300176@qq.com

    通讯作者: 钱海忠, 博士, 副教授。haizhongqian@163.com
  • 中图分类号: P208

摘要: 道路网匹配过程往往采用全局遍历的搜索模式,这种模式会影响匹配效率。针对这一问题,提出一种利用道路分类的层次迭代匹配新方法。首先,依据拓扑关系对道路进行分类,并按道路类型将其划分为匹配层和非匹配层,其中划分至匹配层的道路类型数量较少;其次,对匹配层匹配,并只在同种类型道路集中搜索匹配对象,从而避免全局遍历;然后,将非匹配层中剩余未匹配的道路视为新道路网,重新依据拓扑关系分类,划分出新的匹配层和非匹配层,仍按相同方法进行匹配,如此迭代直至匹配结束;最后,对少量无匹配对象道路进行全局遍历检查,作为提高匹配正确率的有效补充。实验结果及对比分析表明,该方法避免了全局遍历匹配,减少了不同层次间道路的干扰,有效提高了匹配的效率和正确率。

English Abstract

王骁, 钱海忠, 刘海龙, 何海威, 陈竞男. 利用道路分类进行道路网层次迭代匹配[J]. 武汉大学学报 ● 信息科学版, 2016, 41(8): 1072-1078. doi: 10.13203/j.whugis20140441
引用本文: 王骁, 钱海忠, 刘海龙, 何海威, 陈竞男. 利用道路分类进行道路网层次迭代匹配[J]. 武汉大学学报 ● 信息科学版, 2016, 41(8): 1072-1078. doi: 10.13203/j.whugis20140441
WANG Xiao, QIAN Haizhong, LIU Hailong, HE Haiwei, CHEN Jingnan. A Hierarchical and Iterative Road Network Matching Method by Using Road Classification[J]. Geomatics and Information Science of Wuhan University, 2016, 41(8): 1072-1078. doi: 10.13203/j.whugis20140441
Citation: WANG Xiao, QIAN Haizhong, LIU Hailong, HE Haiwei, CHEN Jingnan. A Hierarchical and Iterative Road Network Matching Method by Using Road Classification[J]. Geomatics and Information Science of Wuhan University, 2016, 41(8): 1072-1078. doi: 10.13203/j.whugis20140441
  • 随着我国经济的快速发展,城市中道路要素的变化周期越来越短。为满足数据现势性的要求,需要不断进行道路数据更新,因此各个部门需要完成大量的空间数据采集和生产任务[1]。但是由于应用目的、制图综合等方面的差异,不同单位对同一比例尺同一区域采集的数据结果往往不尽相同,这就造成了空间数据的多语义性、多时空性、多尺度性等问题,从而严重影响了多源道路数据的集成、共享与融合。

    同名实体匹配是通过分析空间实体的差异和相似性识别出不同来源数据中表达现实世界同一地物或地物集的过程,是解决多源数据集成融合的核心技术之一。针对道路匹配,国内外已有不少学者进行了研究[2-8],如Walter和Fritsch利用缓冲区增长法进行道路匹配;Zhang提出可动态调整缓冲区半径的非对称性缓冲区增长法;胡云岗将道路目标分为三个匹配层次,利用缓冲区分析和拓扑关系开发了系列算法完成匹配;赵东保改局部寻优为全局寻优,综合利用道路结点与弧段的特征信息,通过概率松弛法获得匹配关系等。这些方法都有力地推动了道路网匹配技术的发展,为解决道路数据的集成与融合提供了技术支持。但这些方法通常更为关注匹配的正确率,对匹配效率方面的研究相对较少。在匹配过程中,一般对道路网进行全局遍历来确定匹配对象,一旦数据量过大,这种全局遍历匹配模式会影响匹配效率。构建外接矩形或缓冲区来获取候选匹配集[9]以及建立规则格网索引进行渐进式搜索等匹配方法[10]虽然能够在一定程度上提高匹配效率,但仍无法避免全局遍历。为此,本文提出一种利用道路分类的层次迭代匹配方法,从而避免了全局遍历,提高了匹配效率。

    • 首先,根据拓扑关系对道路进行分类,将数量较少的道路类型划入匹配层中,剩余数量较多的道路类型则划为非匹配层;其次,对匹配层中的道路类型进行匹配,匹配时只需在另一数据源相同道路类型中搜索匹配对象,从而在避免了全局遍历的同时减少了不同类型道路间的相互干扰,可同时提高匹配效率和正确率;然后,将非匹配层中剩余较多的道路视为新的道路网重新分类,仍按数量多少划分为匹配层和非匹配层,按照相同方法匹配,如此迭代直至匹配结束;最后,对少量无匹配对象道路进行全局遍历检查,作为提高匹配正确率的有效补充。该方法不仅能够避免全局遍历的匹配搜索方式,提高匹配效率,还能在一定程度上提高匹配正确率。

    • 本文主要依据拓扑关系对道路网进行分类。道路网拓扑关系构建步骤为:①断链,即将道路相交处断开;②接链,即将距离满足阈值的两个结点合并为一个结点;③构面,即对道路网中的封闭区域构建道路网眼面,道路网眼面是指道路网纵横交错形成的最小闭合区块[11]图 1为拓扑关系构建前后的道路网对比示意图。

      图  1  道路网拓扑关系构建

      Figure 1.  Constructing Topology of Road Network

      根据拓扑关系对道路进行分类,记NStart(Li)为与道路Li首结点相连的其他道路数量;NEnd(Li)为与道路Li末结点相连的其他道路数量;A(Li)为道路Li参与构成的道路网眼面数量,则按照表 1中的分类依据[12]可将道路划分为图 2所示的Ⅰ、Ⅱ、Ⅲ、Ⅳ、Ⅴ共5种类型。

      图  2  5种不同类型道路示意图

      Figure 2.  Sketch Map of Five Different Road Types

      表 1  道路分类依据

      Table 1.  Rules of Road Classification

      道路类型 分类依据
      Ⅰ类 NStart(Li) > 1且NEnd(Li)=0,或者NStart(Li)=0且NEnd(Li) > 1
      Ⅱ类 NStart(Li) > 1且NEnd(Li) > 1且A(Li)=0
      Ⅲ类 NStart(Li) > 1且NEnd(Li) > 1且A(Li)=1
      Ⅳ类 NStart(Li) > 1且NEnd(Li) > 1且A(Li)=2
      Ⅴ类 NStart(Li)=0且NEnd(Li)=0

      图 3为道路网分类实例,其中不同类型道路用不同线型和线宽表示。表 2为不同类型道路的数量统计结果。由此可得5种类型道路的数量特点, 即Ⅰ、Ⅱ、Ⅲ、Ⅴ类道路数量占道路总数量的比重很小,Ⅳ类道路数量所占比重很大。

      图  3  道路网分类实例

      Figure 3.  Classification Example of Road Network

      表 2  不同类型道路数量统计

      Table 2.  Quantity of Different Road Types

      道路类型 数量 占道路总数比率/%
      Ⅰ类 153 8.4
      Ⅱ类 10 0.5
      Ⅲ类 182 10.0
      Ⅳ类 1 480 81.0
      Ⅴ类 2 0.1
    • 匹配层划分之前需明确两个概念, 一是匹配判断次数,即一条待匹配道路在另一数据源中搜索到匹配对象所需的判断次数; 二是匹配判断总次数,即道路网中所有道路的匹配判断次数总和。

      从理论上分析,道路分类后,两数据源中互相匹配的两条道路类型应相同。对某一条道路,其匹配对象必然存在于另一数据源和其类型相同的道路集合中。所以只需在与其类型相同的道路集合中进行搜索,即可得到匹配对象。道路分类结果中,Ⅰ、Ⅱ、Ⅲ、Ⅴ类型的道路数量较少,按照上述搜索模式能够避免对其他类型道路的搜索,从而大幅减少匹配判断次数;但Ⅳ类道路数量很多,若对其仍按上述方法匹配,则其匹配判断次数减少并不明显。所以道路分类后将直接进行匹配的Ⅰ、Ⅱ、Ⅲ、Ⅴ类道路划分至匹配层(图 4(a)~4(d)),将暂时不匹配的Ⅳ类道路划分至非匹配层(图 4(e))。

      图  4  匹配层、非匹配层道路类型

      Figure 4.  Road Types in Matching and Un-matching Hierarchy

    • 将非匹配层中未匹配的大量Ⅳ类道路视为未分类的新道路网(图 5(a)),对其重新构建拓扑关系(图 5(b))并分类,得到新的Ⅰ、Ⅱ、Ⅲ、Ⅳ、Ⅴ类道路(图 5(c)5(d)5(e))。其中,新Ⅰ、Ⅱ、Ⅲ、Ⅴ类道路数量仍然很少,新Ⅳ类道路数量仍然很多,所以仍将Ⅰ、Ⅱ、Ⅲ、Ⅴ类道路划分至匹配层,将Ⅳ类道路划分至非匹配层。重复上述过程直至所有道路完成匹配,即为迭代过程。迭代过程是本方法的核心,有效避免了对分类后数量最多的Ⅳ类道路直接进行匹配,确保每次匹配只在少量道路集合中搜索匹配对象。

      图  5  新道路网及重新分类

      Figure 5.  New Road Network and Reclassification

    • 由于道路数据具有不确定性,互相匹配的两条道路可能会被分为不同类型。由于只在相同类型道路集合中搜索匹配对象,这可能造成原本存在匹配对象的道路被错误地判断为无匹配对象。本文采用对无匹配对象道路进行全局遍历检查的方法解决这一问题,即匹配结束后,对所有无匹配对象道路,重新在另一数据源中进行全局遍历,以判断其是否确实不存在匹配对象。全局遍历结束后,若存在道路与之匹配,则把其纳入匹配结果中来;若仍无匹配对象,此时可确定该道路确实不存在匹配对象,为新增或消失道路。

      无匹配对象道路全局遍历检查是对分类过程可能造成错误的有效补充,确保匹配结果的正确性,虽然在一定程度上会增加匹配判断总次数,但是这种情况相对很少,因此不会产生较大影响。

    • 本方法的实验流程如图 6所示。

      图  6  方法流程图

      Figure 6.  Flowchart of Proposed Method

      1)对不同来源的道路网构建拓扑关系,并将其分为Ⅰ、Ⅱ、Ⅲ、Ⅳ、Ⅴ5种类型;

      2)将Ⅰ、Ⅱ、Ⅲ、Ⅴ类道路划为匹配层并匹配,将Ⅳ类道路划为非匹配层;

      3)判断匹配后双方Ⅳ类道路数量NⅣ1NⅣ2是否同时为0。若NⅣ1≠0且NⅣ2≠0,则匹配双方同时转至步骤1);若NⅣ1≠0且NⅣ2=0,或者NⅣ1=0且NⅣ2≠0,则不等于0的一方转至步骤1);若NⅣ1=0且NⅣ2=0,则转至步骤4)。

      4)最后一次层次匹配;

      5)无匹配对象道路全局遍历检查。

    • 为验证本方法的有效性和适用性,选择方格网式、环形放射式、自由式和混合式4种不同形式的城市道路网数据进行实验。分别选择西安、成都、重庆、北京4市(图 7)不同来源的相同比例尺道路数据作为上述4种路网形式的代表进行实验,其目的是探索路网形式的不同是否会影响拓扑关系的构建,继而影响后续的匹配过程,以检验本文方法对不同形式道路网的适用性。表 3的统计结果显示出4种形式道路网的数量呈增大趋势,可以此探索匹配效率与数据量之间的关系。

      图  7  四种典型路网形式实验数据

      Figure 7.  Experiment Data of Four Typical Road Networks

      表 3  4种不同形式道路网统计结果(数据源1/数据源2)

      Table 3.  Statistical Results of Four Different Road Networks Forms (data 1 / data 2)

      路网形式 道路总数 道路结点总数
      自由式 133/141 923/804
      方格网式 522/513 1 340/1 273
      环形放射式 577/585 1 872/1 755
      混合式 1 092/1 101 3 710/2 935
    • 以混合式路网为例对道路网匹配实验结果进行显示,如图 8所示,虚线连接的是两数据源中互相匹配的道路(为清晰起见,仅显示局部匹配结果)。通常使用匹配率(matching rate)MR和匹配正确率(matching correctness)MC这两个指标对匹配结果进行评价。Cobb等对匹配结果进行了详细的分类,匹配结果可分为匹配和未匹配两种情况;其中,匹配可进一步划分为正确匹配、错误匹配及假匹配;未匹配也可进一步划分为正确未匹配和假未匹配[13]

      图  8  混合式路网匹配结果(局部)

      Figure 8.  Matching Results of Hybrid Road Network(Part)

      记匹配结果中正确匹配数为Nrm,错误匹配数为Nwm,假匹配数为Nfm,正确未匹配数为Nrum,假未匹配数为Nfum,由此可得匹配率MR和匹配正确率MC的计算公式为:

      (1)
      (2)

      表 4为本文方法匹配结果统计,4种不同形式的道路网匹配率和匹配正确率均达到90%以上,表明本文方法不会受道路网形式的影响和约束,对各种形式的道路网普遍适用。

      表 4  本文方法对4种不同形式道路网的匹配结果

      Table 4.  Matching Results of Four Different Road Networks Using Proposed Method

      路网形式 Nrm Nwm Nfm Nrum Nfum 匹配率/% 匹配正确率/%
      自由式 109 0 1 0 2 98.2 99.1
      方格网式 412 15 1 12 21 95.3 96.3
      环形放射式 489 18 2 1 5 99.0 96.1
      混合式 841 74 11 2 13 98.6 90.8
    • 对§2中4组数据按照全局遍历式的匹配方法进行对比实验,并从匹配判断总次数、匹配效率、匹配质量这三个方面进行对比分析。为了确保匹配效率不受匹配方法的影响,同样采用缓冲区增长算法进行对比实验。

    • 设道路数据源1中的道路总数为N1,道路数据源2中的道路总数为N2,将数据源1中道路作为待匹配道路,用数据源2中道路进行匹配。对全局遍历式匹配方法,设其匹配判断总次数为NO,由于数据源1中每条道路在搜索匹配对象时需完成N2次判断,则:

      (3)

      对本文的层次迭代匹配方法而言,匹配判断总次数由层次迭代匹配判断次数和无匹配对象道路全局遍历检查判断次数两部分组成。设完成整个道路网匹配需要进行的判断次数为NH,则:

      (4)

      式中, n1in2in3in5i(i=1, 2, …, m)分别为Ⅰ、Ⅱ、Ⅲ、Ⅴ类道路的匹配判断次数;m为迭代次数;ncheck为无匹配对象道路全局遍历检查判断次数。设需进行全局遍历检查的无匹配对象道路数量为Ncheck,则:

      (5)

      表 5的匹配判断总次数统计结果看出,本文方法的匹配判断总次数约为全局遍历式匹配方法的1/5。匹配判段总次数的大幅减少,证明了本文方法在搜索待匹配道路的匹配对象时有效避免了全局遍历。

      表 5  匹配判断总次数统计

      Table 5.  Statistic of Total Matching Numbers

      路网形式 层次迭代
      判断次数
      遍历检查
      判断次数
      本文方法
      总次数
      全局遍历
      法总次数
      自由式 3 190 564 3 754 18 753
      方格网式 24 281 42 579 66 860 267 786
      环形放射式 28 962 12 285 41 247 337 545
      混合式 74 453 205 887 280 340 1 202 292
    • 本文主要利用匹配时间指标来衡量匹配效率。定义时间压缩比率tw(式(6)),设全局遍历式匹配方法完成道路网匹配的时间为TO,本文方法完成匹配的时间为TN,则有:

      (6)

      表 6为全局遍历匹配方法和本文方法的时间与时间压缩比率的统计结果。从表 6中可以看出,在匹配时间方面,本文方法明显少于全局遍历式匹配方法,时间压缩比率超过50%;并且时间压缩比率随着数据量的增大而增大,表明在处理数据量较大的道路网时,本文方法更具优势,能够更大幅度地减少匹配时间,从而提高匹配效率。

      表 6  匹配时间对比

      Table 6.  Comparison of Matching

      路网形式 数据量/KB 全局遍历法
      耗时/s
      本文方法
      耗时/s
      时间压缩
      比率/%
      自由式 114 4.866 2.184 55.1
      方格网式 233 22.292 9.532 57.2
      环形放射式 296 37.736 15.349 59.3
      混合式 548 112.663 41.667 63.0
    • 表 7为本文方法与全局遍历方法的匹配率和匹配正确率的统计结果。本文方法的匹配正确率高于全局遍历方法,这是由于, 除了在层次迭代匹配后进行无匹配对象道路全局遍历检查这一对匹配正确率的补充外,本文方法只在匹配层中同种类型的道路集内搜索匹配对象的匹配策略减少了周围相邻道路的干扰,增大了匹配正确的概率,具体分析如下。

      表 7  匹配率、匹配正确率对比

      Table 7.  Comparison of Matching Recall Rate and Matching Correctness

      路网形式 匹配率/% 匹配正确率/%
      全局遍历法 本文方法 全局遍历法 本文方法
      自由式 99.2 98.2 96.9 99.1
      方格网式 96.6 95.3 95.7 96.3
      环形放射式 98.7 99.0 94.3 96.1
      混合式 98.6 98.6 83.1 90.8

      全局遍历式匹配方法通过在整个道路网中进行遍历来搜索匹配对象,一旦道路网分布密集,待匹配道路对应同名实体周围的相邻道路极易对其匹配产生干扰,从而增大匹配错误的概率。如图 9所示,在待匹配道路A的周围不仅存在其对应的同名要素,而且存在干扰道路,一旦匹配方法选择不当或者匹配阈值设定不合理,就可能造成错误匹配。

      图  9  相邻道路干扰示意

      Figure 9.  Diagram of Interference Roads

      相反,本文方法则能够有效减少同名要素周围相邻道路的干扰。如图 10所示,匹配层中的Ⅰ、Ⅱ、Ⅴ类道路均呈零散稀疏分布状态,道路之间距离较大,其周边相邻道路对同名实体产生干扰较小;Ⅲ类道路则呈首尾相连状分布,这种分布也可减小相邻道路的干扰,这两种分布特点均能减小错误匹配概率。因此,本文方法中的分层匹配模式不仅能够有效提高匹配效率,还能够提高匹配正确率。

      图  10  匹配层道路分布特点

      Figure 10.  Distribution Characteristic of Roads in Matching Hierarchy

    • 通过上述的实验对比及分析可发现,首先, 本文方法在匹配时能够避免全局遍历,从而大幅减少匹配判断次数,压缩匹配时间,提高匹配效率。其次, 本文方法能够减小周围相邻道路的干扰,从而提高匹配的正确率;无匹配道路的遍历检查是对匹配正确率的有效补充。因此本方法并不以“牺牲”匹配质量来换取匹配效率的提高。最后, 本文方法不受道路形式的影响,适用于多种形态的道路网匹配,特别适用于数据量大、道路分布密集的道路网之间的匹配。

    • 本文提出一种利用道路分类进行道路网层次迭代匹配的方法,通过避免匹配过程中全局遍历的搜索方式,有效提高了匹配效率;减少相邻道路间干扰的同时, 提高匹配正确率。4种不同形式道路网的匹配实验验证了本方法的有效性和适用性,与全局遍历式匹配方法的对比实验验证了本方法在效率和正确率方面的优势,从而为多源道路数据的集成与融合提供了新的技术途径。

      但是,本方法目前只适用于相同或相近比例尺道路网。对于跨尺度较大的不同比例尺的道路网,由于制图综合的影响,匹配双方之间的原有精度损失较大,如采用与同尺度道路网层次迭代匹配相同的模式,则可能会产生新的问题。因此,如何将本方法应用于跨尺度道路匹配将是后续研究的重点。

参考文献 (13)

目录

    /

    返回文章
    返回