留言板

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

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

全局与局部寻优相结合的道路网匹配方法

张建辰 王艳慧 赵文吉

张建辰, 王艳慧, 赵文吉. 全局与局部寻优相结合的道路网匹配方法[J]. 武汉大学学报 ● 信息科学版, 2018, 43(8): 1166-1171. doi: 10.13203/j.whugis20160157
引用本文: 张建辰, 王艳慧, 赵文吉. 全局与局部寻优相结合的道路网匹配方法[J]. 武汉大学学报 ● 信息科学版, 2018, 43(8): 1166-1171. doi: 10.13203/j.whugis20160157
ZHANG Jianchen, WANG Yanhui, ZHAO Wenji. Matching Road Networks Based on Combination of Global and Local Optimization[J]. Geomatics and Information Science of Wuhan University, 2018, 43(8): 1166-1171. doi: 10.13203/j.whugis20160157
Citation: ZHANG Jianchen, WANG Yanhui, ZHAO Wenji. Matching Road Networks Based on Combination of Global and Local Optimization[J]. Geomatics and Information Science of Wuhan University, 2018, 43(8): 1166-1171. doi: 10.13203/j.whugis20160157

全局与局部寻优相结合的道路网匹配方法

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

国家自然科学基金 41371375

北京市自然科学基金 8132018

详细信息

Matching Road Networks Based on Combination of Global and Local Optimization

Funds: 

The National Natural Science Foundation of China 41371375

the Natural Science Foundation of Beijing 8132018

More Information
  • 摘要: 针对面向道路网匹配的概率松弛法约束性指标单一且无法识别MN匹配模式的不足,从兼顾全局和局部匹配最优的角度出发,提出了从局部角度顾及几何约束和拓扑约束,从全局角度完善MN匹配模式的改进算法,设计并实现了不同匹配模式下的匹配策略。测试结果表明,该方法的整体匹配精度和召回率提高了7%~14%,均达到90%以上;空间与属性匹配度评价指标提高了3%~7%;可将待匹配路网中最邻近结点平均距离的两倍值作为缓冲区阈值设定的参考依据,从而验证了该方法的可行性与可靠性。
  • 图  1  节点的连通度及其关联的弧段

    Figure  1.  Node's Connectivity Degree and Its Associated Road Segments

    图  2  方向一致性路段连接

    Figure  2.  Road Connecting with Regard to Direction Consistency

    图  3  M:N的匹配模式

    Figure  3.  M:N Matching Pattern

    图  4  2:3的匹配模式

    Figure  4.  2:3 Matching Pattern

    图  5  结构相似性计算

    Figure  5.  Illustration of Calculating Structural Similarity

    图  6  路网数据

    Figure  6.  Road Datasets

    图  7  局部匹配结果

    Figure  7.  Illustration of Local Matching Results

    图  8  不同缓冲区阈值下各评价指标结果

    Figure  8.  Evaluation Results at Different Buffering Thresholds

    表  1  不同匹配各评价指标统计结果

    Table  1.   Statistics Results from Different Matching Patterns

    匹配模式 Cn Mn An Pn/% Rn/% Pl/% Rl/%
    1:0 127 133 129 95.5 97.7 97.5 98.9
    1:1 218 224 229 97.3 95.1 97.7 96.5
    1:M 183 194 198 94.3 92.4 92.9 91.8
    M:N 31 33 34 94.0 91.2 92.7 90.2
    总计 559 585 590 95.6 94.7 95.2 92.1
    下载: 导出CSV

    表  2  不同匹配方法的匹配精度/%

    Table  2.   Precision Comparison Among Different Matching Methods/%

    匹配方法 Pn Rn Pl Rl
    不考虑M:N 87.9 87.1 83.2 82.8
    仅考虑几何约束 88.9 90.9 89.5 87.8
    改进的概率松弛法 95.6 94.7 95.2 92.1
    下载: 导出CSV

    表  3  概率松弛法计算效率比较

    Table  3.   Computing Efficiency Comparison Between Two Probabilistic Relaxation Methods

    方法 单次迭代耗费时间/ms 迭代次数 匹配路段数 耗时/s 匹配速度/(条·s-1)
    一般概率松弛法 1 150 24 552 30 18.4
    改进的概率松弛法 1 500 16 585 32 18.3
    下载: 导出CSV

    表  4  不同权重组合下的匹配结果

    Table  4.   Matching Results at Different Weights

    方法 权重组合 Pn/% Rn/% Pl/% Rl/%
    等权重法 (0.25, 0.25, 0.25, 0.25) 95.6 94.7 95.2 92.1
    专家打分法 (0.17, 0.25, 0.25, 0.33) 95.8 94.1 94.3 92.7
    CRITIC法 (0.29, 0.28, 0.21, 0.22) 94.7 92.5 93.1 91.2
    组合权重法 (0.21, 0.26, 0.24, 0.29) 95.4 93.6 93.8 92.5
    下载: 导出CSV

    表  5  多个样本的匹配结果对比

    Table  5.   Matching Results from Multiple Samples

    序号 Pn/% Rn/% Pl/% Rl/% 加入M:N后各评价指标变化范围/% 加入拓扑后各指标变化范围/% 节点平均距离/m 缓冲区半径/m
    1 95.6 94.7 95.2 92.1 7.3~13.6 3.8~6.7 42 80
    2 95.3 94.2 94.5 93.2 6.9~12.7 4.3~7.2 53 100
    3 94.2 93.3 94.1 91.7 7.5~13.2 3.2~6.4 34 70
    4 95.7 95.8 95.4 91.5 7.0~12.8 4.1~6.9 63 120
    下载: 导出CSV
  • [1] 郭黎, 李宏伟, 张泽建, 等.道路网信息投影匹配方法研究[J].武汉大学学报·信息科学版, 2013, 38(9):1113-1117 http://ch.whu.edu.cn/CN/abstract/abstract2756.shtml

    Guo Li, Li Hongwei, Zhang Zejian, et al. Geometry Matching Method for Transportation Road Network Data Based on Projection[J]. Geomatics and Information Science of Wuhan University, 2013, 38(9):1113-1117 http://ch.whu.edu.cn/CN/abstract/abstract2756.shtml
    [2] Safra E, Kanza Y, Sagiv Y, et al. Ad Hoc Matching of Vectorial Road Networks[J]. International Journal of Geographical Information Science, 2013, 27(1):114-153 doi:  10.1080/13658816.2012.667104
    [3] Zhang M, Meng L Q. Delimited Stroke Oriented Algorithm-Working Principle and Implementation for Matching of Road Networks[J]. Annals of GIS, 2008, 14(1):44-53 doi:  10.1080/10824000809480638
    [4] 胡云岗, 陈军, 赵仁亮, 等.地图数据缩编更新中道路数据匹配方法[J].武汉大学学报·信息科学版, 2010, 35(4):451-456 http://ch.whu.edu.cn/CN/abstract/abstract912.shtml

    Hu Yungang, Chen Jun, Zhao Renliang, et al. Digital Map Confliction:A Review of the Process and a Proposal for Classification[J]. Geomatics and Information Science of Wuhan University, 2010, 35(4):451-456 http://ch.whu.edu.cn/CN/abstract/abstract912.shtml
    [5] 应申, 李霖, 刘万增, 等.版本数据库中基于目标匹配的变化信息提取与数据更新[J].武汉大学学报·信息科学版, 2009, 34(6):725-755 http://ch.whu.edu.cn/CN/abstract/abstract1361.shtml

    Ying Shen, Li Lin, Liu Wanzeng, et al. Change-only Updating Based on Object Matching in Version Databases[J]. Geomatics and Information Science of Wuhan University, 2009, 34(6):725-755 http://ch.whu.edu.cn/CN/abstract/abstract1361.shtml
    [6] Safra E, Kanza Y, Sagiv Y, et al. Location-Based Algorithms for Finding Sets of Corresponding Objects over Several Geo-spatial Data Sets[J]. International Journal of Geographical Information Science, 2010, 24(1):69-106 doi:  10.1080/13658810802275560
    [7] Volz S. An Iterative Approach for Matching Multiple Representations of Street Data[C]. ISPRS Workshop on Multiple Representations and Interoperability of Spatial Data, Hanover, 2006
    [8] Mustièr S, Devogele T. Matching Networks with Different Levels of Detail[J]. GeoInformatica, 2008, 12:435-453 doi:  10.1007/s10707-007-0040-1
    [9] 邓敏, 徐凯, 赵彬彬, 等.基于结构化空间信息的节点层次匹配方法[J].武汉大学学报·信息科学版, 2010, 35(8):913-916 http://ch.whu.edu.cn/CN/abstract/abstract1031.shtml

    Deng Min, Xu Kai, Zhao Binbin, et al. A Hierarchical Approach for Nodes Matching Based on Structural Spatial Relaxations[J]. Geomatics and Information Science of Wuhan University, 2010, 35(8):913-916 http://ch.whu.edu.cn/CN/abstract/abstract1031.shtml
    [10] Christamas W J, Kittler J, Petrou M. Structural Matching in Computer Vision Using Probabilistic Relaxation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1995, 17(8):749-764 doi:  10.1109/34.400565
    [11] Song W, Keller J M, Haithcoat T M, et al. Relaxation-Based Point Feature Matching for Vector Map Conflation[J]. Transactions in GIS, 2011, 15(1):43-60 doi:  10.1111/tgis.2011.15.issue-1
    [12] Yang B S, Zhang Y F, Luan X C. A Probabilistic Relaxation Approach for Matching Road Networks[J]. International Journal of Geographical Information Science, 2013, 27(2):319-338 doi:  10.1080/13658816.2012.683486
    [13] 翟仁建. 基于全局一致性评价的多尺度矢量空间数据匹配方法研究[D]. 郑州: 信息工程大学, 2011

    Zhai Renjian. Research on Automated Matching Method for Multi-scale Vector Spatial Data Based on Global Consistency Evaluation[D]. Zhengzhou: Information Engineering University, 2011
  • [1] 张云菲, 黄金彩, 邓敏, 房晓亮, 胡继萍.  基于邻近模式的多比例尺居民地松弛迭代匹配 . 武汉大学学报 ● 信息科学版, 2018, 43(7): 1098-1105. doi: 10.13203/j.whugis20160243
    [2] 张丁文, 陈占龙, 谢忠.  利用松弛标记法进行空间场景匹配 . 武汉大学学报 ● 信息科学版, 2018, 43(5): 752-758. doi: 10.13203/j.whugis20150719
    [3] 朱递, 刘瑜.  一种路网拓扑约束下的增量型地图匹配算法 . 武汉大学学报 ● 信息科学版, 2017, 42(1): 77-83. doi: 10.13203/j.whugis20150016
    [4] 王骁, 钱海忠, 刘海龙, 何海威, 陈竞男.  利用道路分类进行道路网层次迭代匹配 . 武汉大学学报 ● 信息科学版, 2016, 41(8): 1072-1078. doi: 10.13203/j.whugis20140441
    [5] 付仲良, 杨元维, 高贤君, 赵星源, 逯跃锋, 陈少勤.  利用多元Logistic回归进行道路网匹配 . 武汉大学学报 ● 信息科学版, 2016, 41(2): 171-177. doi: 10.13203/j.whugis20150112
    [6] 张凯, 赵建虎, 张红梅.  一种基于M估计的水下地形抗差匹配算法 . 武汉大学学报 ● 信息科学版, 2015, 40(4): 558-562. doi: 10.13203/j.whugis20130011
    [7] 杨林, 万波, 王润, 左泽均, 安晓亚.  一种基于层次路划结构关系约束的矢量道路网自动匹配方法 . 武汉大学学报 ● 信息科学版, 2015, 40(12): 1661-1668. doi: 10.13203/j.whugis20140295
    [8] 刘海龙, 钱海忠, 王骁, 何海威.  采用层次分析法的道路网整体匹配方法 . 武汉大学学报 ● 信息科学版, 2015, 40(5): 644-651. doi: 10.13203/j.whugis20130350
    [9] 巩现勇, 武芳, 姬存伟, 翟仁健.  道路网匹配的蚁群算法求解模型 . 武汉大学学报 ● 信息科学版, 2014, 39(2): 191-195. doi: 10.13203/j.whugis20120649
    [10] 尹川, 王艳慧.  路网增量更新中基于OSTU的目标几何匹配阈值计算 . 武汉大学学报 ● 信息科学版, 2014, 39(9): 1061-1067. doi: 10.13203/j.whugis20130575
    [11] 甄艳, 刘学军, 王美珍.  匹配点分布密度约束下的基础矩阵估计 . 武汉大学学报 ● 信息科学版, 2013, 38(10): 1167-1171.
    [12] 郭黎, 李宏伟, 张泽建, 张斌.  道路网信息投影匹配方法研究 . 武汉大学学报 ● 信息科学版, 2013, 38(9): 1113-1117.
    [13] 李清泉, 胡波, 乐阳.  一种基于约束的最短路径低频浮动车数据地图匹配算法 . 武汉大学学报 ● 信息科学版, 2013, 38(7): 805-808.
    [14] 江万寿, 郑顺义, 张祖勋, 张剑清.  航空影像特征匹配研究 . 武汉大学学报 ● 信息科学版, 2003, 28(5): 510-513.
    [15] 张力, 沈未名, 张祖勋, 张剑清.  基于空间约束的神经网络影像匹配 . 武汉大学学报 ● 信息科学版, 2000, 25(1): 55-59.
    [16] 张力, 沈未名, 张祖勋, 张剑清.  基于约束满足神经网络的整体影像匹配 . 武汉大学学报 ● 信息科学版, 1999, 24(3): 216-219.
    [17] 仇彤.  基于小波变换的松弛法影像匹配 . 武汉大学学报 ● 信息科学版, 1998, 23(2): 145-148.
    [18] 潘励, 张剑清.  道路断线自动连接的概率松弛方法 . 武汉大学学报 ● 信息科学版, 1997, 22(4): 318-321.
    [19] 沈未名, 张祖勋, 张剑清.  基于神经网络的影像匹配概率松弛算法 . 武汉大学学报 ● 信息科学版, 1996, 21(3): 247-251.
    [20] 张剑清.  基于特征的最小二乘匹配理论精度 . 武汉大学学报 ● 信息科学版, 1988, 13(4): 82-90.
  • 加载中
图(8) / 表(5)
计量
  • 文章访问数:  1097
  • HTML全文浏览量:  51
  • PDF下载量:  337
  • 被引次数: 0
出版历程
  • 收稿日期:  2016-07-25
  • 刊出日期:  2018-08-05

全局与局部寻优相结合的道路网匹配方法

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

    国家自然科学基金 41371375

    北京市自然科学基金 8132018

    作者简介:

    张建辰, 博士, 主要从事地理信息系统方法与应用研究。openbuildstar@126.com

    通讯作者: 王艳慧, 博士, 教授。huiwangyan@sohu.com
  • 中图分类号: P208

摘要: 针对面向道路网匹配的概率松弛法约束性指标单一且无法识别MN匹配模式的不足,从兼顾全局和局部匹配最优的角度出发,提出了从局部角度顾及几何约束和拓扑约束,从全局角度完善MN匹配模式的改进算法,设计并实现了不同匹配模式下的匹配策略。测试结果表明,该方法的整体匹配精度和召回率提高了7%~14%,均达到90%以上;空间与属性匹配度评价指标提高了3%~7%;可将待匹配路网中最邻近结点平均距离的两倍值作为缓冲区阈值设定的参考依据,从而验证了该方法的可行性与可靠性。

English Abstract

张建辰, 王艳慧, 赵文吉. 全局与局部寻优相结合的道路网匹配方法[J]. 武汉大学学报 ● 信息科学版, 2018, 43(8): 1166-1171. doi: 10.13203/j.whugis20160157
引用本文: 张建辰, 王艳慧, 赵文吉. 全局与局部寻优相结合的道路网匹配方法[J]. 武汉大学学报 ● 信息科学版, 2018, 43(8): 1166-1171. doi: 10.13203/j.whugis20160157
ZHANG Jianchen, WANG Yanhui, ZHAO Wenji. Matching Road Networks Based on Combination of Global and Local Optimization[J]. Geomatics and Information Science of Wuhan University, 2018, 43(8): 1166-1171. doi: 10.13203/j.whugis20160157
Citation: ZHANG Jianchen, WANG Yanhui, ZHAO Wenji. Matching Road Networks Based on Combination of Global and Local Optimization[J]. Geomatics and Information Science of Wuhan University, 2018, 43(8): 1166-1171. doi: 10.13203/j.whugis20160157
  • 依靠数据更新驱动的导航电子地图中,路网数据的现势性是基于位置服务的重要保障。导航电子地图更新中,路网变化信息的识别和提取很大程度上取决于新旧版本数据库中对应的目标匹配,其匹配精度会直接影响数据更新的准确率。因此,路网数据匹配技术一直是国内外空间数据库更新领域的热点之一[1-3]。从局部最优角度,算法可以分为缓冲区算法[4-5]、迭代最邻近点算法[6-7]、结构拓扑法[8-9]等,这些匹配算法虽然可以融合多个匹配条件,但匹配结果可能仅在其局部阈值范围内合理。实际上,路网匹配往往更需要考虑整体的匹配效果,需要在局部最优的前提下,使路网匹配达到整体最优。很多研究试图引入计算机视觉和模式识别领域常用的图匹配算法——概率松弛匹配方法[10],结合路网要素的位置、形状等指标,通过迭代匹配概率矩阵的方法使路网匹配达到整体最优[11-12]。这类方法存在一些问题。一是已有研究对初始概率计算时,仅从局部考虑了路段的长度、方向和距离等几何约束指标,未顾及具有空间关联的不同路网要素之间的相互影响。而导航电子地图系统必须具备的路径规划与引导功能更加关注的是路网要素的拓扑连通性,对拓扑约束指标的忽略很可能无法实现局部最优的匹配效果,对整体匹配精度和后续实际应用也会造成影响。二是已有研究仅考虑了1:0、1:1和1:M匹配模式的设计与实现,对由道路拓宽、新建交叉道路、立交桥交叉路口匹配等路网物理变化引发的较复杂的M:N匹配模式判定的研究较少, 阻碍了该方法的实用性。

    在此背景下,本文兼顾全局和局部,设计从局部角度顾及几何约束和拓扑约束,从全局角度完善M:N匹配模式的改进概率松弛法,并用实验验证本算法的可行性与可靠性。

    • 在几何约束的基础上,本文引入节点连通度与弧段方向角作为拓扑约束算子, 对初始化匹配概率矩阵中的差异性指标选取进行改进。具体算法如下。

      1) 为区分节点关联的弧段的相对位置关系,以节点为原点建立坐标系,以X轴为起始方向,逆时针记录各个弧段与X轴形成的方向角。如图 1所示,道路节点P0连接3条路段,其节点连通度为3。P0关联的3条路段L1L2L3X轴形成的方向角分别为∠1、∠2和∠3。

      图  1  节点的连通度及其关联的弧段

      Figure 1.  Node's Connectivity Degree and Its Associated Road Segments

      2) 由于节点连通度与弧段方向角量纲不同,采用式(1)计算节点的拓扑差异[13]

      $$ {\rm{tp}}({S_i}, {T_i}) = \frac{m}{n}\left( {1-\frac{{\left\{ {{\rm{min}}\sum\limits_{i = 1}^m {\left| {a({S_i}, {T_i})} \right|} } \right\}}}{{180m}}} \right) $$ (1)

      式中,mn分别表示节点(Si, Ti)的最小和最大连通度; a(Si, Ti)为节点SiTi所关联道路弧段的方向角差。对于待匹配路段(ij),tp(ij)为起始两个节点的tp(Si, Ti)之和。

      3) 对于每个差异性指标,均可得到一个匹配概率矩阵。文献[12]详细描述了距离、方向和长度等几何约束性指标计算方法。本文引入的拓扑指标也转化为一个概率矩阵参与到最终概率矩阵的计算,因此,本文采用加权的方法对最终概率矩阵进行赋值:

      $$ \begin{array}{l} \mathit{\boldsymbol{P}} = {m_1} \times {\mathit{\boldsymbol{P}}_{{\rm{dis}}}} + {m_2} \times {\mathit{\boldsymbol{P}}_{{\rm{len}}}} + {m_3} \times {\mathit{\boldsymbol{P}}_{{\rm{alg}}}} + \\ \;\;\;\;\;\;\;\;\;\;\;\;\;{m_4} \times {\rm{ }}{\mathit{\boldsymbol{P}}_{{\rm{tp}}}} \end{array} $$ (2)

      式中,m1m2m3m4为权重参数; PdisPlenPalgPtp分别为距离、长度、方向和拓扑的概率。此处采用等权重法对各权重参数进行赋值。

    • 针对不满足1:0、1:1和1:M匹配条件的未匹配数据集,需要先把未匹配的路段按照一定规则连接成路径才能进行M:N匹配判断。本文基于方向一致性原则对m条未匹配且具有连通性的路段进行虚拟路径连接。此处的方向一致性原则是指当节点存在两条以上未匹配的路段时,把路段方向偏差值较小的两条路段进行连接。如果节点只有两条未匹配的路段,则直接进行连接。

      图 2所示,S1S2S3为3条未匹配的路段,选择S1的候选连接路径时,采用方向一致性原则,应选择S1S2进行连接,舍弃S1S3的路径连接。

      图  2  方向一致性路段连接

      Figure 2.  Road Connecting with Regard to Direction Consistency

    • 虚拟节点的插入是为了把M:N匹配模式转化为多个1:1或者1:M匹配模式进行处理。如图 3所示,M是由m条未匹配的路段联结的一条路径, N是其候选匹配集中的一条路径。在路径N上插入m-1个虚拟节点Vi (i=1, 2…m-1)。虚拟节点Vi应满足以下假设条件:①ViRi+1N 的正投影,即由Ri+1向路段Tj+kTj+k+1作垂线,垂线与Tj+kTj+k+1的交点为虚拟节点Vi;②Vi虚拟节点处的拓扑差异值与Ri+1相同。

      图  3  M:N的匹配模式

      Figure 3.  M:N Matching Pattern

      为方便说明,现以图 4M1N1路段的2:3的匹配模式为例,进行虚拟节点的插入与结构相似性的计算。在顾及方向一致性的路段连接后,M1是由R1R2R2R3连接成的路径。N1M1候选路段的一条路径。在N1路径上插入一个虚拟节点V1,使2:3的匹配模式转化成两个1:2的匹配模式。

      图  4  2:3的匹配模式

      Figure 4.  2:3 Matching Pattern

    • 基于§1.2.2节中的两个假设条件,以图 4所示的2:3匹配模式为例,路径M1的匹配可以转化成R1R2T1-T2-V1匹配和R2R3V1-T3-T4匹配。下面讨论路径M1与路径N1结构相似性的计算方法。M1由2条路段组成,M1的候选路段N1在计算结构相似性时插入一个虚拟节点。由于虚拟节点的数目是固定的,且要求M1中两条路段的权重保持不变,因此,可以定义M1N1的结构相似性为:

      $$ {S_{{M_1}{N_1}}} = \frac{{\left\| {{R_1}{R_2}} \right\|}}{{\left\| {{M_1}} \right\|}} \times {S_{{R_1}{R_2}}} + \frac{{\left\| {{R_2}{R_3}} \right\|}}{{\left\| {{M_1}} \right\|}} \times {S_{{R_2}{R_3}}} $$ (3)

      式中,‖·‖表示路段的长度;SR1R2SR2R3分别表示路段R1R2以及R2R3的结构相似性。

      在一般情况下,由于待匹配的一条路段对应的路段集数目可能不固定,如果仅采用简单的线性相加,会产生节点越多、相似性越大的问题,这与实际情况不相符。鉴于此,本文借鉴联合概率的思想,计算一条路段与多条路段匹配时的联合概率来表示对应路段的结构相似性,从而兼顾算法匹配精度全局最优的准则。即SR1R2可以定义为ST1T2ST2V1的乘积:

      $$ {S_{{R_1}{R_2}}} = {S_{{T_1}{T_2}}} \times {S_{{T_2}{V_1}}} $$ (4)

      同理,

      $$ {S_{{R_2}{R_3}}} = {S_{{V_1}{T_3}}} \times {S_{{T_3}{T_4}}} $$ (5)

      推广到M >2,N >3时,则MN的结构相似性为:

      $$ {S_{MN}} = \sum\limits_{i = 1}^{M + 1} {\frac{{\left\| {{R_i}{R_{i + 1}}} \right\|}}{{\left\| {{R_1}} \right\|}}} \times {S_{{R_i}{R_{i + 1}}}} $$ (6)

      假设路段RiRi+1对应k个路段,如图 5所示,则路段RiRi+1的结构相似性定义为:

      $$ {S_{{R_i}{R_{i + 1}}}} = \prod\limits_{i = 1}^k {{S_{{O_i}{O_{i + 1}}}}} $$ (7)

      图  5  结构相似性计算

      Figure 5.  Illustration of Calculating Structural Similarity

    • 1:0、1:1和1:M的匹配策略可参考文献[12]。本文重点论述M:N匹配模式的匹配策略。为了对M:N匹配模式进行判断,需对其结构相似性进行计算。若路径MN均为连接后形成的虚拟路径,且NM的缓冲区范围内,可判定M:N结构相似。若满足结构相似性判定条件,且NM候选路段集中与M结构相似性最大的路径,以及NM的结构相似性值大于结构相似性阈值,则可判定为M:N匹配模式。由此可知,结构相似性判定条件是M:N匹配条件的必要条件,满足结构相似性判定条件的路段,若同时也满足M:N匹配模式的其他条件,后期将作为M:N匹配模式处理,否则将作为未匹配路段处理。对于不满足结构相似性条件的路段,后期也被看作未匹配的路段处理。具体匹配策略如下。

      假设M是一条由m条路段组成的虚拟路径,通过设定缓冲区分析,可获得M的候选路段集N ={N1N2Ni},其中N为未匹配路段连接的虚拟路径。在虚拟路径Nj (j=1, 2…i)插入m-1个虚拟节点,采用式(6)和式(7)对Nj进行结构相似性计算,得到虚拟路径MN j的结构相似性SMNj(j=1, 2…i)。若SMNi=max{SMNj},则Ni可能为M的匹配虚拟路径。分别统计已匹配的1:1和1:M路段的结构相似性的平均值Savg。若SMNi>Savg,则判定NiM的匹配路径。否则,NiM将作为未匹配路段处理。

    • 本实验数据分别来自于北京市房山区某处的2009年和2015年路网数据。图 6(a)表示2015年数据,共732条路段,534个节点,总长度268 km。图 6(b)表示2009年数据,共507条路段,383个节点,总长度241 km。

      图  6  路网数据

      Figure 6.  Road Datasets

      本文在Windows 7操作系统下集成ArcEngine 10.1和C#环境,编程验证实验效果。计算机配置CPU为Inter(R) Core(TM)2 Dou E7200, 3.53 GHz, 内存为2 GB。本文实验以2015年路网作为匹配路网,2009年路网作为参考路网。

      从路段数目匹配和路段长度匹配的角度综合考虑,本文构建精度(Pn)、召回率(Rn)、长度匹配精度(Pl)、长度召回率(Rl)4个空间与属性一体化指标来综合检验匹配效果。计算公式如下:

      $$ \left\{ \begin{array}{l} {P_n} = \frac{{{C_n}}}{{{M_n}}} \times 100\%, {R_n} = \frac{{{C_n}}}{{{A_n}}} \times 100\% \\ {P_l} = \frac{{{C_l}}}{{{M_l}}} \times 100\%, {R_l} = \frac{{{C_l}}}{{{A_l}}} \times 100\% \end{array} \right. $$ (8)

      式中,Cn表示匹配结果中的正确数;Mn表示由匹配算法得出的匹配对数,其中包括正确的匹配对数和错误的匹配对数;An表示由人工识别出的正确匹配对数,它包括算法识别出的正确的匹配数和遗漏的匹配数;ClMlAl分别对应于CnMnAn匹配道路的总长度。

    • 表 1可知,整体匹配和不同的匹配模式下,各评价指标的结果均在90%以上,表明改进的概率松弛匹配算法具有较好的匹配结果。

      表 1  不同匹配各评价指标统计结果

      Table 1.  Statistics Results from Different Matching Patterns

      匹配模式 Cn Mn An Pn/% Rn/% Pl/% Rl/%
      1:0 127 133 129 95.5 97.7 97.5 98.9
      1:1 218 224 229 97.3 95.1 97.7 96.5
      1:M 183 194 198 94.3 92.4 92.9 91.8
      M:N 31 33 34 94.0 91.2 92.7 90.2
      总计 559 585 590 95.6 94.7 95.2 92.1

      图 7中,道路路段abcdef分别来自于2009年和2015年路网数据,在未考虑M:N匹配模式的情况下,这些路段是属于遗漏的未匹配路段。基于本文对M:N匹配模式的判定,首先对路段abcd连接成a-b-c-d路径,ef路段连接成e-f路径,插入虚拟节点v,最终判定其为2:4的匹配模式。

      图  7  局部匹配结果

      Figure 7.  Illustration of Local Matching Results

    • 表 2可知,加入M:N匹配模式后,整体匹配结果提高了7.3%~13.6%,表明考虑顾及全局最优的M:N匹配模式后,匹配精度有了明显提升。利用顾及局部最优的几何+拓扑的改进概率松弛法,与仅采用几何约束的方法进行比较,各评价指标的结果增加了3.8%~6.7%。表明增加拓扑约束后,匹配精度和召回率进一步提升。

      表 2  不同匹配方法的匹配精度/%

      Table 2.  Precision Comparison Among Different Matching Methods/%

      匹配方法 Pn Rn Pl Rl
      不考虑M:N 87.9 87.1 83.2 82.8
      仅考虑几何约束 88.9 90.9 89.5 87.8
      改进的概率松弛法 95.6 94.7 95.2 92.1

      为了探索改进概率松弛法中合理的缓冲区阈值,本文分别以10~120 m为不同缓冲区半径,并以10 m为等间隔步长统计各评价指标结果。由图 8可知,在0~80 m缓冲区半径内,随着缓冲距的增加,PnRn都增加。在80 m以后,匹配结果的PnRn基本保持平稳。实际上,节点平均距离反映的是两个数据集中对应节点匹配时的缓冲距。

      图  8  不同缓冲区阈值下各评价指标结果

      Figure 8.  Evaluation Results at Different Buffering Thresholds

    • 根据算法语句的频度,采用频度估计算法可知,一般概率松弛法和改进的概率松弛法算法的时间复杂度均为T=O(n2)。由表 3可知,与现有的概率松弛方法相比,改进后的概率松弛方法的匹配速度仅降低了0.54%,降低幅度远远小于匹配精度7%~14%的增幅。改进后算法与原算法相比,时间复杂度相似;匹配速度虽然有所降低,但其降幅远小于匹配精度的增幅。因此,改进后的算法仍具有相应的优势。

      表 3  概率松弛法计算效率比较

      Table 3.  Computing Efficiency Comparison Between Two Probabilistic Relaxation Methods

      方法 单次迭代耗费时间/ms 迭代次数 匹配路段数 耗时/s 匹配速度/(条·s-1)
      一般概率松弛法 1 150 24 552 30 18.4
      改进的概率松弛法 1 500 16 585 32 18.3

      为了比较不同权重对匹配结果的敏感性,本文利用不同的权重组合(等权重法、专家打分法、CRITIC(criteria importance though intercrieria correlation)法及组合权重法)计算相对应的匹配结果。由表 4可知,4种赋权方法得到的匹配结果相差不大,说明不同的权重组合对实验结果敏感性不大。

      表 4  不同权重组合下的匹配结果

      Table 4.  Matching Results at Different Weights

      方法 权重组合 Pn/% Rn/% Pl/% Rl/%
      等权重法 (0.25, 0.25, 0.25, 0.25) 95.6 94.7 95.2 92.1
      专家打分法 (0.17, 0.25, 0.25, 0.33) 95.8 94.1 94.3 92.7
      CRITIC法 (0.29, 0.28, 0.21, 0.22) 94.7 92.5 93.1 91.2
      组合权重法 (0.21, 0.26, 0.24, 0.29) 95.4 93.6 93.8 92.5

      为了验证该方法的可靠性,本文另选取3个研究区(序号为2、3、4),分别与上述实验得到的结论(序号为1)进行比照。由表 5可知,不同的验证区得到的结果虽然具有一定的波动,但基本一致。综上可知,本实验的方法具有一定的稳定性和可靠性。

      表 5  多个样本的匹配结果对比

      Table 5.  Matching Results from Multiple Samples

      序号 Pn/% Rn/% Pl/% Rl/% 加入M:N后各评价指标变化范围/% 加入拓扑后各指标变化范围/% 节点平均距离/m 缓冲区半径/m
      1 95.6 94.7 95.2 92.1 7.3~13.6 3.8~6.7 42 80
      2 95.3 94.2 94.5 93.2 6.9~12.7 4.3~7.2 53 100
      3 94.2 93.3 94.1 91.7 7.5~13.2 3.2~6.4 34 70
      4 95.7 95.8 95.4 91.5 7.0~12.8 4.1~6.9 63 120
    • 本文同时顾及几何约束和拓扑约束,提出一种兼顾全局与局部效果的改进概率松弛方法,完善传统概率松弛法初始矩阵中差异性指标的选取与计算准则,并设计插入虚拟节点的方法实现对M:N匹配模式的补充与完善,详细剖析了该算法的实现流程。实验结果表明,该算法能进一步提高路网匹配的精度。对比多个实验区域,验证了本算法的稳定性与可靠性。但是本文在引入拓扑约束算子后,算法耗时增加,且在各约束性指标赋权时,采用了等权重法,后续应通过相关方法获取最佳的权重组合,并围绕这些问题展开进一步研究。

参考文献 (13)

目录

    /

    返回文章
    返回