留言板

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

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

顾及速度与航向信息的轨迹匹配方法

殷吉崇 武芳 李安平 杜佳威 刘呈熠

殷吉崇, 武芳, 李安平, 杜佳威, 刘呈熠. 顾及速度与航向信息的轨迹匹配方法[J]. 武汉大学学报 ● 信息科学版, 2021, 46(11): 1774-1781. doi: 10.13203/j.whugis20210058
引用本文: 殷吉崇, 武芳, 李安平, 杜佳威, 刘呈熠. 顾及速度与航向信息的轨迹匹配方法[J]. 武汉大学学报 ● 信息科学版, 2021, 46(11): 1774-1781. doi: 10.13203/j.whugis20210058
YIN Jichong, WU Fang, LI Anping, DU Jiawei, LIU Chengyi. Trajectory Matching Considering Speed and Heading Information[J]. Geomatics and Information Science of Wuhan University, 2021, 46(11): 1774-1781. doi: 10.13203/j.whugis20210058
Citation: YIN Jichong, WU Fang, LI Anping, DU Jiawei, LIU Chengyi. Trajectory Matching Considering Speed and Heading Information[J]. Geomatics and Information Science of Wuhan University, 2021, 46(11): 1774-1781. doi: 10.13203/j.whugis20210058

顾及速度与航向信息的轨迹匹配方法

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

国家自然科学基金 41101362

详细信息
    作者简介:

    殷吉崇, 博士生, 主要从事遥感影像矢量化提取与地图自动综合研究。jichongy@whu.edu.cn

    通讯作者: 武芳, 博士, 教授。wufang_630@126.com
  • 中图分类号: P283; P237

Trajectory Matching Considering Speed and Heading Information

Funds: 

The National Natural Science Foundation of China 41101362

More Information
    Author Bio:

    YIN Jichong, PhD candidate, specializes in remote sensing image vectorization extraction and automatic map generalization. E-mail: jichongy@whu.edu.cn

    Corresponding author: WU Fang, PhD, professor. E-mail: wufang_630@126.com
  • 摘要: 现有轨迹匹配方法具有一定局限性,其匹配精度无法满足车辆导航定位的需求。针对拓扑匹配方法对于起始匹配位置的依赖性,提出了顾及速度与航向信息的轨迹匹配方法。该方法综合利用速度、距离和航向约束改进起始匹配路段和起始位置的判定,并通过后续时刻车辆的正确匹配位置修正起始位置,避免了传统拓扑匹配方法中起始位置匹配错误导致的误差传递累积,提高匹配路段的准确性。同时以起始位置为基础,速度与时间信息为约束确定匹配点。为验证所提方法的有效性,选取多条复杂程度各异的路线进行实验,并与现有的几何匹配方法和拓扑匹配方法进行比较。实验结果表明,该方法在不同复杂程度的城市路网下具有良好的匹配效果,准确率可达93.53%。在匹配准确率方面优于现有的两种方法,在匹配效率方面能满足定位导航的需求。
  • 图  1  本文方法的流程图

    Figure  1.  Flowchart of Our Proposed Method

    图  2  匹配路段判定准则

    Figure  2.  Determination Criteria of Matching Section

    图  3  起始位置判定准则

    Figure  3.  Determination Criterion of Initial Position

    图  4  匹配误差传递

    Figure  4.  Transmission of Matching Error

    图  5  测试路线

    Figure  5.  Test Routes

    图  6  匹配结果

    Figure  6.  Matching Results

    表  1  路段结点关系

    Table  1.   Relationship of Link-Node

    路段ID 起始结点ID 终止结点ID 通行方向
    L1 N1 N2 双向
    L2 N2 N3 单向
    L3 N3 N4 双向
    L4 N2 N5 双向
    L5 N2 N6 双向
    L6 N4 N6 单向
    下载: 导出CSV

    表  2  结点路段关系

    Table  2.   Relationship of Node-Link

    结点ID 是否路口 与结点关联的路段数量 与结点关联的路段ID
    N1 1 L1
    N2 4 L1, L2, L4, L5
    N3 2 L2, L3
    N4 2 L3, L6
    N5 1 L4
    N6 2 L5, L6
    下载: 导出CSV

    表  3  测试路线基本信息

    Table  3.   Basic Information of Test Routes

    路线 起始位置 终点位置 路线长度/km
    1 139.545 748 4°E,35.544 231 7°N 139.352 959 4°E,35.418 647°N 26.3
    2 139.483 113 9°E,35.506 643 1°N 139.377 809 7°E,35.440 759 1°N 16.9
    3 139.326 290 5°E,35.428 644 4°N 139.294 092 9°E,35.405 629 4°N 10.8
    4 139.361 955 7°E,35.416 893 1°N 139.366 901 3°E,35.423 461 5°N 2.0
    5 139.330 056 4°E,35.431 432 2°N 139.338 216 9°E,35.427 276 6°N 1.8
    6 139.328 489 9°E,35.427 437 4°N 139.330 095°E,35.427 483°N 2.1
    下载: 导出CSV

    表  4  匹配结果比较

    Table  4.   Comparison of Matching Results

    匹配方法 nall nright r/%
    本文方法 340 318 93.53
    文献[9]方法 340 275 80.88
    文献[12]方法 340 311 91.47
    下载: 导出CSV

    表  5  匹配时间统计

    Table  5.   Statistics of Matching Time

    测试路线 轨迹点数量/个 匹配时间/s 单个轨迹点平均匹配时间/s
    1 120 22.46 0.19
    2 49 3.00 0.06
    3 82 20.25 0.25
    4 23 0.20 0.01
    5 23 2.06 0.09
    6 49 15.89 0.33
    下载: 导出CSV
  • [1] 郭仁忠, 林浩嘉, 贺彪, 等. 面向智慧城市的GIS框架[J]. 武汉大学学报·信息科学版, 2020, 45(12): 1 829-1 835 doi:  10.13203/j.whugis20200536

    Guo Renzhong, Lin Haojia, He Biao, et al. GIS Framework for Smart Cities[J]. Geomatics and Information Science of Wuhan University, 2020, 45 (12): 1 829-1 835 doi:  10.13203/j.whugis20200536
    [2] 唐炉亮, 靳晨, 杨雪, 等. 基于GPS时空轨迹的路网拓扑自动变化检测[J]. 武汉大学学报·信息科学版, 2017, 42(10): 1 381-1 386 doi:  10.13203/j.whugis20150662

    Tang Luliang, Jin Chen, Yang Xue, et al. Road Network Topology Automatic Change Detection Based on GPS Spatio-Temporal Trajectories[J]. Geomatics and Information Science of Wuhan University, 2017, 42(10): 1 381-1 386 doi:  10.13203/j.whugis20150662
    [3] Tan C P, Liu L, Wu H, et al. Fuzing License Plate Recognition Data and Vehicle Trajectory Data for Lane-Based Queue Length Estimation at Signalized Intersections[J]. Journal of Intelligent Transportation Systems, 2020, 24(5): 449-466 doi:  10.1080/15472450.2020.1732217
    [4] Kim H, Nam D, Suh W, et al. Origin-Destination Trip Table Estimation Based on Subarea Network OD Flow and Vehicle Trajectory Data[J]. Transportation Planning and Technology, 2018, 41(3): 265-285 doi:  10.1080/03081060.2018.1435437
    [5] Wu L, Hu S, Yin L, et al. Optimizing Cruising Routes for Taxi Drivers Using a Spatio-Temporal Trajectory Model[J]. ISPRS International Journal of Geo-Information, 2017, 6(11): 373-384 doi:  10.3390/ijgi6110373
    [6] 李翔, 马爽, 杨辉, 等. 矢量道路拓扑追踪匹配算法[J]. 中国图象图形学报, 2017, 22 (5): 596-609 https://www.cnki.com.cn/Article/CJFDTOTAL-ZGTB201705004.htm

    Li Xiang, Ma Shuang, Yang Hui, et al. Vector Road Matching Algorithm Based on a Topological Path[J]. Journal of Image and Graphics, 2017, 22 (5): 596-609 https://www.cnki.com.cn/Article/CJFDTOTAL-ZGTB201705004.htm
    [7] Hashemi M, Karimi H A. A Critical Review of Real-Time Map-Matching Algorithms: Current Issues and Future Directions[J]. Computers, Environment and Urban Systems, 2014, 48: 153-165 doi:  10.1016/j.compenvurbsys.2014.07.009
    [8] Quddus M A, Ochieng W Y, Noland R B. Current Map-Matching Algorithms for Transport Applications: State-of-the Art and Future Research Directions[J]. Transportation Research Part C: Emerging Technologies, 2007, 15(5): 312-328 doi:  10.1016/j.trc.2007.05.002
    [9] Bernstein D, Kornhauser A. An Introduction to Map Matching for Personal Navigation Assistants [J]. Geometric Distributions, 1998, 122(7): 1 082- 1 083
    [10] White C E, Bernstein D, Kornhauser A L. Some Map Matching Algorithms for Personal Navigation Assistants[J]. Transportation Research Part C: Emerging Technologies, 2000, 8(2): 91-108 http://www.sciencedirect.com/science/article/pii/s0968090x00000267
    [11] 曾喆, 李清泉, 邹海翔, 等. 曲率积分约束的GPS浮动车地图匹配方法[J]. 测绘学报, 2015, 44 (10): 1 167-1 176 https://www.cnki.com.cn/Article/CJFDTOTAL-CHXB201510016.htm

    Zeng Zhe, Li Qingquan, Zou Haixiang, et al. Curvature Integration Constrained Map Matching Method for GPS Floating Car Data[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(10): 1 167-1 176 https://www.cnki.com.cn/Article/CJFDTOTAL-CHXB201510016.htm
    [12] 朱递, 刘瑜. 一种路网拓扑约束下的增量型地图匹配算法[J]. 武汉大学学报·信息科学版, 2017, 42(1): 77-83 doi:  10.13203/j.whugis20150016

    Zhu Di, Liu Yu. An Incremental Map-Matching Method Based on Road Network Topology[J]. Geomatics and Information Science of Wuhan University, 2017, 42(1): 77-83 doi:  10.13203/j.whugis20150016
    [13] 李清泉, 胡波, 乐阳. 一种基于约束的最短路径低频浮动车数据地图匹配算法[J]. 武汉大学学报·信息科学版, 2013, 38(7): 805-808 http://ch.whu.edu.cn/article/id/2697

    Li Qingquan, Hu Bo, Yue Yang. Flowing Car Data Map-Matching Based on Constrained Shortest Path Algorithm[J]. Geomatics and Information Science of Wuhan University, 2013, 38(7): 805-808 http://ch.whu.edu.cn/article/id/2697
    [14] 李清泉, 黄练. 基于GPS轨迹数据的地图匹配算法[J]. 测绘学报, 2010, 39(2): 207-212 https://www.cnki.com.cn/Article/CJFDTOTAL-CHXB201002022.htm

    Li Qingquan, Huang Lian. A Map Matching Algorithm for GPS Tracking Data[J]. Acta Geodaetica et Cartographica Sinica, 2010, 39(2): 207-212 https://www.cnki.com.cn/Article/CJFDTOTAL-CHXB201002022.htm
    [15] Obradovic D, Lenz H, Schupfner M. Fusion of Map and Sensor Data in a Modern Car Navigation System[J]. Journal of VLSI Signal Processing Systems for Signal, Image and Video Technology, 2006, 45(1): 111-122 http://www.onacademic.com/detail/journal_1000034531230810_1427.html
    [16] 周洋, 方志祥, 李清泉, 等. 利用经验约束规则和证据理论进行出租车异常轨迹检测[J]. 武汉大学学报·信息科学版, 2016, 41(6): 797-802 doi:  10.13203/j.whugis20140221

    Zhou Yang, Fang Zhixiang, Li Qingquan, et al. Anomalous Taxi Trajectory Detection Based on Experiential Constraint Rules and Evidence Theory [J]. Geomatics and Information Science of Wuhan University, 2016, 41(6): 797-802 doi:  10.13203/j.whugis20140221
    [17] Yang C, Gidófalvi G. Fast Map Matching, an Algorithm Integrating Hidden Markov Model with Precomputation[J]. International Journal of Geographical Information Science, 2018, 32(3): 547-570 doi:  10.1080/13658816.2017.1400548
    [18] 郑诗晨, 盛业华, 吕海洋. 基于粒子滤波的行车轨迹路网匹配方法[J]. 地球信息科学学报, 2020, 22(11): 2 109-2 117 https://www.cnki.com.cn/Article/CJFDTOTAL-DQXX202011002.htm

    Zheng Shichen, Sheng Yehua, Lü Haiyang. Vehicle Trajectory-Map Matching Based on Particle Filter [J]. Journal of Geo-Information Science, 2020, 22 (11): 2 109-2 117 https://www.cnki.com.cn/Article/CJFDTOTAL-DQXX202011002.htm
    [19] 孙文彬, 熊婷. 历史数据和强化学习相结合的低频轨迹数据匹配算法[J]. 测绘学报, 2016, 45(11): 1 328-1 334 https://www.cnki.com.cn/Article/CJFDTOTAL-CHXB201611013.htm

    Sun Wenbin, Xiong Ting. A Low-Sampling-Rate Trajectory Matching Algorithm in Combination of History Trajectory and Reinforcement Learning[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45 (11): 1 328-1 334 https://www.cnki.com.cn/Article/CJFDTOTAL-CHXB201611013.htm
    [20] Chen B Y, Yuan H, Li Q Q, et al. Map-Matching Algorithm for Large-Scale Low-Frequency Floating Car Data[J]. International Journal of Geographical Information Science, 2014, 28(1): 22-38 doi:  10.1080/13658816.2013.816427
    [21] Zeng Z, Zhang T, Li Q Q, et al. Curvedness Feature Constrained Map Matching for Low-Frequency Probe Vehicle Data[J]. International Journal of Geographical Information Science, 2016, 30(4): 660-690 doi:  10.1080/13658816.2015.1086922
    [22] 严盛隆, 于娟, 周后盘. ⅡVMM: 针对低频GPS轨迹的改进交互式投票匹配算法[J]. 计算机科学, 2019, 46(9): 325-332 https://www.cnki.com.cn/Article/CJFDTOTAL-JSJA201909052.htm

    Yan Shenglong, Yu Juan, Zhou Houpan. ⅡVMM: An Improved Interactive Voting-Based Map Matching Algorithm for Low-Sampling-Rate GPS Trajectories[J]. Computer Science, 2019, 46(9): 325-332 https://www.cnki.com.cn/Article/CJFDTOTAL-JSJA201909052.htm
    [23] 谢金运, 涂伟, 李清泉, 等. 大规模浮动车流数据并行地图匹配方法[J]. 武汉大学学报·信息科学版, 2017, 42(5): 697-703 doi:  10.13203/j.whugis20140847

    Xie Jinyun, Tu Wei, Li Qingquan, et al. A Parallel Map-Matching Approach for Large Volume Floating Car Stream Data[J]. Geomatics and Information Science of Wuhan University, 2017, 42(5): 697- 703 doi:  10.13203/j.whugis20140847
    [24] 王骁, 钱海忠, 刘海龙, 等. 利用道路分类进行道路网层次迭代匹配[J]. 武汉大学学报·信息科学版, 2016, 41(8): 1 072-1 078 doi:  10.13203/j.whugis20140441

    Wang Xiao, Qian Haizhong, Liu Hailong, et al. A Hierarchical and Iterative Road Network Matching Method by Using Road Classification[J]. Geomatics and Information Science of Wuhan University, 2016, 41(8): 1 072-1 078 doi:  10.13203/j.whugis20140441
  • [1] 王占刚, 吴自兴, 王想红.  语义尺度影响的相离区域合并与拓扑关系计算 . 武汉大学学报 ● 信息科学版, 2018, 43(11): 1712-1718. doi: 10.13203/j.whugis20170009
    [2] 牛继强, 徐丰, 姚高伟, 樊勇, 林昊.  基于粗集的多尺度空间拓扑关系不确定性定量评价模型 . 武汉大学学报 ● 信息科学版, 2017, 42(6): 756-761, 781. doi: 10.13203/j.whugis20140904
    [3] 王行风, 汪云甲.  一种顾及拓扑关系的室内三维模型组织和调度方法 . 武汉大学学报 ● 信息科学版, 2017, 42(1): 35-42. doi: 10.13203/j.whugis20140798
    [4] 向隆刚, 王星星, 吴涛, 陶强强.  面向关键点的轨迹-有向线移动过程建模 . 武汉大学学报 ● 信息科学版, 2016, 41(10): 1292-1298. doi: 10.13203/j.whugis20140731
    [5] 王珂, 张周威.  矢栅一体化拓扑关系的度量描述研究 . 武汉大学学报 ● 信息科学版, 2015, 40(5): 638-643. doi: 10.13203/j.whugis20130357
    [6] 郭继发, 刘玉洁, 毛健, 崔铁军.  高阶模糊区域的交叉拓扑关系形式化研究 . 武汉大学学报 ● 信息科学版, 2014, 39(2): 196-200. doi: 10.13203/j.whugis20120691
    [7] 吴华意, 刘波, 李大军, 凌南燕.  空间对象拓扑关系研究综述 . 武汉大学学报 ● 信息科学版, 2014, 39(11): 1269-1276.
    [8] 向隆刚, 龚健雅, 吴涛, 李文海.  一种面向Stop/Move抽象的轨迹时空关系 . 武汉大学学报 ● 信息科学版, 2014, 39(8): 956-962. doi: 10.13203/j.whugis20130061
    [9] 沈敬伟, 闾国年, 温永宁, 吴明光.  拓扑和方向空间关系组合描述及其相互约束 . 武汉大学学报 ● 信息科学版, 2011, 36(11): 1305-1308.
    [10] 刘新, 刘文宝, 李成名.  三维体目标间拓扑关系与方向关系的混合推理 . 武汉大学学报 ● 信息科学版, 2010, 35(1): 74-78.
    [11] 杜世宏, 郭泺.  基于拓扑关系的不确定区域方向关系推理 . 武汉大学学报 ● 信息科学版, 2010, 35(4): 388-393.
    [12] 刘波, 李大军, 阮见, 夏元平.  带空洞面对象间拓扑关系形式化描述 . 武汉大学学报 ● 信息科学版, 2009, 34(1): 68-71.
    [13] 郭庆胜, 吕秀琴, 蔡永香.  图形简化过程中空间拓扑关系抽象的规律 . 武汉大学学报 ● 信息科学版, 2008, 33(5): 520-523.
    [14] 郭庆胜, 刘小利, 陈宇箭.  线与线之间的空间拓扑关系组合推理 . 武汉大学学报 ● 信息科学版, 2006, 31(1): 39-42.
    [15] 邓敏, 李志林, 李永礼, 张雪松.  GIS线目标间拓扑关系描述的4交差模型 . 武汉大学学报 ● 信息科学版, 2006, 31(11): 945-948.
    [16] 郭庆胜, 陈宇箭, 刘浩.  线与面的空间拓扑关系组合推理 . 武汉大学学报 ● 信息科学版, 2005, 30(6): 529-532.
    [17] 郭庆胜, 丁虹, 刘浩, 刘小利.  面状目标之间空间拓扑关系的组合式分类 . 武汉大学学报 ● 信息科学版, 2005, 30(8): 728-731.
    [18] 邓敏, 张雪松, 林宗坚.  拓扑关系形式化描述的Euler示性数模型 . 武汉大学学报 ● 信息科学版, 2004, 29(10): 872-876.
    [19] 罗芳, 艾廷华, 王洪.  闭合坐标链多边形数据的拓扑关系快速构建 . 武汉大学学报 ● 信息科学版, 2004, 29(6): 558-561.
    [20] 王涛, 毋河海.  等高线拓扑关系的构建以及应用 . 武汉大学学报 ● 信息科学版, 2004, 29(5): 438-442. doi: 10.13203/j.whugis2004.05.014
  • 加载中
图(6) / 表(5)
计量
  • 文章访问数:  119
  • HTML全文浏览量:  77
  • PDF下载量:  20
  • 被引次数: 0
出版历程
  • 收稿日期:  2021-01-30
  • 刊出日期:  2021-11-05

顾及速度与航向信息的轨迹匹配方法

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

    国家自然科学基金 41101362

    作者简介:

    殷吉崇, 博士生, 主要从事遥感影像矢量化提取与地图自动综合研究。jichongy@whu.edu.cn

    通讯作者: 武芳, 博士, 教授。wufang_630@126.com
  • 中图分类号: P283; P237

摘要: 现有轨迹匹配方法具有一定局限性,其匹配精度无法满足车辆导航定位的需求。针对拓扑匹配方法对于起始匹配位置的依赖性,提出了顾及速度与航向信息的轨迹匹配方法。该方法综合利用速度、距离和航向约束改进起始匹配路段和起始位置的判定,并通过后续时刻车辆的正确匹配位置修正起始位置,避免了传统拓扑匹配方法中起始位置匹配错误导致的误差传递累积,提高匹配路段的准确性。同时以起始位置为基础,速度与时间信息为约束确定匹配点。为验证所提方法的有效性,选取多条复杂程度各异的路线进行实验,并与现有的几何匹配方法和拓扑匹配方法进行比较。实验结果表明,该方法在不同复杂程度的城市路网下具有良好的匹配效果,准确率可达93.53%。在匹配准确率方面优于现有的两种方法,在匹配效率方面能满足定位导航的需求。

English Abstract

殷吉崇, 武芳, 李安平, 杜佳威, 刘呈熠. 顾及速度与航向信息的轨迹匹配方法[J]. 武汉大学学报 ● 信息科学版, 2021, 46(11): 1774-1781. doi: 10.13203/j.whugis20210058
引用本文: 殷吉崇, 武芳, 李安平, 杜佳威, 刘呈熠. 顾及速度与航向信息的轨迹匹配方法[J]. 武汉大学学报 ● 信息科学版, 2021, 46(11): 1774-1781. doi: 10.13203/j.whugis20210058
YIN Jichong, WU Fang, LI Anping, DU Jiawei, LIU Chengyi. Trajectory Matching Considering Speed and Heading Information[J]. Geomatics and Information Science of Wuhan University, 2021, 46(11): 1774-1781. doi: 10.13203/j.whugis20210058
Citation: YIN Jichong, WU Fang, LI Anping, DU Jiawei, LIU Chengyi. Trajectory Matching Considering Speed and Heading Information[J]. Geomatics and Information Science of Wuhan University, 2021, 46(11): 1774-1781. doi: 10.13203/j.whugis20210058
  • 城市车辆轨迹数据蕴含着丰富的位置信息,为城市空间数据的更新与挖掘提供了信息支撑[1]。真实道路是面状地物,行车轨迹在该面状地物内,但当道路抽象为线状地物时,轨迹与道路就会出现不完全匹配的情况。由于存在全球导航卫星系统(global navigation satellite system,GNSS)误差,车辆轨迹难以准确反映位置信息,轨迹数据无法直接应用于路网更新[2]、交通状态分析[3]、出行规律发现[4]和动态路径规划[5]等研究中。因此,研究提高轨迹定位精度的数据处理方法具有重要意义。车辆轨迹与行驶道路的匹配能够纠正轨迹位置,且避免了外界干扰引发的不确定性,是提高导航定位准确性的重要方法之一[6]

    轨迹与地图匹配方法是将定位数据匹配到道路网数据中,以识别车辆正在行驶的正确路段并确定路段上车辆的位置[7]。文献[8]综述了轨迹与地图匹配的研究发展,并将匹配方法分为几何匹配方法、拓扑匹配方法、概率匹配方法和其他匹配方法。不同的算法具有不同的优缺点和适用范围,文献[9-11]提出的几何匹配方法易于实施且匹配速度快,但未考虑道路间的连接方式,在城市密集路段容易出现误匹配;文献[612-13]提出的拓扑匹配方法顾及道路的连通性和延续性,在密集路段依然保持很好的匹配效果,但该方法比较依赖初始位置的匹配,匹配误差会随着道路的延续而传递累积;概率匹配方法通过构建椭圆或矩形缓冲区快速获取与轨迹相交的路段,该方法常用于匹配路段的初步筛选,作为匹配方法的预处理步骤,文献[14]按照定位点精度构建缓冲区进行候选匹配路段的筛选;其他匹配方法包括卡尔曼滤波器[15]、D-S证据理论[16]、隐式马尔可夫模型[17]、粒子滤波器[18]和模糊逻辑模型[19]等,尽管先进的匹配技术具有较高的准确性,但效率较低。为平衡匹配算法的准确性与效率,文献[17]通过预存道路网中所有路口最短路径的方式解决先进匹配技术的性能瓶颈,但最短路径并不总能代表最真实的路径。

    几何、拓扑及其他信息相结合的匹配方法[20-22]能够进一步提高匹配质量与性能,是近些年研究的热点。文献[14]综合利用曲线相似性、路网拓扑关系和交通规则约束提出一种轨迹数据的全局地图匹配方法,该方法在轨迹与地图匹配的后处理过程中效果很好,但无法为车辆导航定位提供实时匹配服务。文献[23]提出的并行地图匹配方法在计算效率上满足大规模浮动车流数据实时处理的需求,但在复杂路口匹配正确率低。文献[12]采用路网拓扑约束匹配算法,消除了密集路段的误匹配,但针对低频采样数据在复杂路口的匹配未作处理,容易匹配到错误路段,且拓扑匹配方法对起始匹配路段和起始位置的准确度要求很高,该方法并不能提升起始匹配路段和起始位置的准确性。因此,本文在优化起始匹配路段和起始匹配位置判定的基础上,针对车辆在复杂路口的匹配问题,附加速度信息约束,提出了一种顾及速度与航向信息的轨迹匹配方法。

    • 本文方法可分为确定匹配路段和确定匹配位置两个阶段,技术流程如图 1所示。首先在初始匹配路段及匹配位置确定的前提下,按照GNSS定位误差和轨迹延续性分别生成轨迹点GNSS误差圆和轨迹段矩形缓冲区,筛选出候选匹配路段集;然后依据矢量道路网高精度的定位坐标和高准确度的拓扑结构获取路段间的接续关系,构建最优匹配路段;最后利用车辆速度和行驶时间,实时修正车辆当前位置。

      图  1  本文方法的流程图

      Figure 1.  Flowchart of Our Proposed Method

    • 针对车辆在立交桥、路口和平行路段等特殊路段上匹配准确率低的问题,本文利用路网中道路的拓扑关系、限速信息,以及轨迹数据中的位置信息、时间信息和航向信息设计了基于多约束的匹配路段判定准则,如图 2所示。

      图  2  匹配路段判定准则

      Figure 2.  Determination Criteria of Matching Section

    • 距离约束主要通过构建缓冲区的方式实现,本文针对轨迹点和轨迹段分别构建离散缓冲区和连续缓冲区,如图 2(a)所示,TiTi-1分别为i时刻及其前一时刻轨迹点,Bp为轨迹点Ti的离散缓冲区,Bl为轨迹段Ti-1Ti的连续缓冲区,L1,L2L7均为候选路段。

      以轨迹点的定位误差圆大小为范围构建离散缓冲区Bp,并以轨迹段长度为矩形一边、该误差圆直径为矩形另一边,沿行车方向构建连续缓冲区Bl,落在缓冲区内以及与缓冲区相交的路段作为候选路段ML。因此,轨迹点距离约束准则为:

      ML=(BpL)(BpL) ]]>

      式中,L表示路网中的路段。

      轨迹段距离约束准则为:

      ML=[(BpBl)L][(BpBL)L] ]]>
    • 高精度矢量道路网中包含了路段的限速信息,主要分为高速公路、城市主干道和普通道路。如图 2(b)所示,记高速公路路段为LH,城市主干道路段为LM,普通道路路段为LG。高速公路限速100 km/h,城市主干道限速50 km/h,普通道路限速40 km/h(该限速信息由矢量道路网属性信息获得),当轨迹点速度为80 km/h时,依据路段限速信息,匹配路段为LH。在假设车辆遵守交通规则、不超速行驶的前提下,将i时刻轨迹点对应的车辆行驶速度vi与路段限速信息相结合,进一步筛选候选路段ML。速度约束准则如下:

      MLLG,0<vi40LM,40<vi50LH,50<vi100 ]]>
    • 分别计算行车方向、候选路段方向与真北方向间的夹角αTαL,则行车方向与候选路段方向的夹角θ为:

      θ=αT-αL,0αT-αL180°360°-αT-αL,180°<αT-αL360° ]]>

      θ越小,则行车方向与候选路段方向偏离越小,故选取偏离最小的候选路段作为匹配路段,航向约束准则可表示为:

      ML=min{ML|key=sort(θ)} ]]>

      式中,sort(θ)表示对θ中元素进行排序;min{ }表示返回最小值函数;key=sort(θ)表示依据排序后的θ返回最小值。

      由于行车方向与路段L3方向偏差较小,故排除其他候选路段,将路段L3作为匹配路段,如图 2(c)所示。

    • 矢量道路网中每一路段均由起始结点和终止结点构成,道路属性文件和道路结点文件中记录了各路段的结点信息和该结点关联的路段。据此构建路段拓扑关系,以某路口为例,建立路段拓扑结构如图 2(d)所示,其路段结点关系如表 1所示,结点路段关系如表 2所示。

      表 1  路段结点关系

      Table 1.  Relationship of Link-Node

      路段ID 起始结点ID 终止结点ID 通行方向
      L1 N1 N2 双向
      L2 N2 N3 单向
      L3 N3 N4 双向
      L4 N2 N5 双向
      L5 N2 N6 双向
      L6 N4 N6 单向

      表 2  结点路段关系

      Table 2.  Relationship of Node-Link

      结点ID 是否路口 与结点关联的路段数量 与结点关联的路段ID
      N1 1 L1
      N2 4 L1, L2, L4, L5
      N3 2 L2, L3
      N4 2 L3, L6
      N5 1 L4
      N6 2 L5, L6

      表 1中通行方向为双向的路段,其起始结点ID与终止结点ID可以互换。当上一匹配路段的终止结点ID与当前匹配路段的终止结点ID相同,且当前匹配路段为双向通行路段时,转换当前匹配路段的结点ID。依据表12,可以获得路段接续关系。图 2(d)中,当i时刻轨迹点匹配到路段L3上且前一时刻轨迹点在路段L1上时,考虑到路段L6为单向通行路段,故匹配路段为L1-L2-L3

    • 前后轨迹点的车辆速度与行驶时间已知,可以计算车辆前后轨迹点间所经过的真实里程Strue,再与多条路径对应的道路距离Si(i=1, 2n)进行比较,距离更接近真实里程的为车辆真实行驶路径。记前后轨迹点间可达的多条路径分别为R1,R2Rn,匹配路段ML判定准则如下:

      ML=min{Ri|key=sort(Strue-Si)} ]]>

      式中,key=sort(Strue-Si),表示依据排序后的Strue-Si返回最小值。

      图 2(e)所示,车辆从Mi-1Mi的里程为90 m,两轨迹点间存在多条路径,经由L1-L2-L5的路径距离为70 m,而经由L1-L3-L4-L5的路径距离为95 m,故车辆真实行驶路段为L1-L3-L4-L5

    • 起始匹配路段判定是保证本文轨迹匹配方法有效性的重要基础。依据本文设计的距离、速度和航向约束准则可以优化起始匹配路段的判定,本文起始匹配路段判定过程如下:(1)利用起始轨迹点构建离散缓冲区,采用轨迹点距离约束准则选取候选路段集ML,若ML为空,则进入步骤(2);若ML数量为1,则判定结束,ML即为起始匹配路段;若ML数量大于1,则进入步骤(3)。(2)跳过该轨迹点,进入下一轨迹点,为前后时刻轨迹段构建连续缓冲区,采用轨迹段距离约束准则选取候选路段集ML,若ML为空,则重复步骤(2),直至ML不为空;若ML数量为1,则判定结束,ML即为起始匹配路段;若ML数量大于1,则进入步骤(3)。(3)运用速度约束准则判定候选路段集ML中各路段所属道路类型,车辆速度符合某道路类型限速条件,则该路段为起始匹配路段;若车速为0或多条路段属于同一道路类型,则进入步骤(4)。(4)利用航向约束准则选取行车方向与候选路段方向夹角θ最小的作为起始匹配路段。

    • 在起始匹配路段确定基础上,考虑到轨迹的延续性和矢量道路网高准确度的拓扑结构,利用拓扑和里程约束准则确定匹配路段,匹配路段确定步骤如下:(1)利用轨迹段距离约束准则获取起始匹配路段下一时刻轨迹段的候选匹配路段ML;(2)在车辆进入道路交叉口前,利用拓扑约束准则从候选匹配路段ML中选取唯一连通且可行的路段作为匹配路段;(3)当车辆进入复杂路口时,按照起始匹配路段判定过程中的步骤优选出匹配路段ML,若ML唯一,则得到最佳匹配路段,若ML不唯一,则进入步骤(4);(4)利用里程约束准则终选出最佳匹配路段。

    • 起始匹配路段确定后,计算起始轨迹点到该路段的距离d以确定起始位置SP。起始匹配路段记为SL,其结点记为NsNe,起始轨迹点T1到起始匹配路段SL垂直映射的垂足记为V。则起始位置判定准则如下:(1)若垂足V在起始匹配路段SL上,则垂足V即为起始位置SP;(2)若垂足V不在起始匹配路段SL上,则分别计算起始轨迹点T1到起始匹配路段结点NsNe的距离,取距离小的结点作为起始位置。

      图 3为起始位置判定示意图,L1L2为起始候选路段,M1M2为起始候选位置。经过距离、速度、航向约束的筛选,若L1为起始匹配路段,则M1为起始匹配位置;若L2为起始匹配路段,则M2为起始匹配位置。

      图  3  起始位置判定准则

      Figure 3.  Determination Criterion of Initial Position

    • 在确定车辆真实起始位置和匹配路段后,利用车辆速度与行驶时间确定车辆在匹配路段上的真实位置。依据前一时刻与当下时刻的平均速度v¯和时长t,得到车辆在匹配路段上行驶距离Strue。在起始位置的基础上,沿匹配路段加上行驶距离,得到车辆在当下时刻的匹配位置MP,计算如下:

      MP=SP+Strue ]]>
    • 为避免因起始位置匹配错误而导致的误差传递累积,本文利用车辆后续时刻在匹配路段上的匹配位置反馈修正车辆的起始位置。

      当起始位置匹配错误时,拓扑匹配方法的匹配误差会传递累积,影响后续轨迹点的匹配。如图 4所示,当起始轨迹点错误地匹配到路段L1上时,拓扑匹配方法便会错误地以Mi*为车辆真实起始位置进行追踪,从而在某时刻得到错误的车辆位置Mi*,而Mi才是车辆在该时刻的真实位置。错误匹配点Mi*与该时刻轨迹点Ti距离相差过大,故可设定轨迹点与匹配位置间距离的容差,以此约束匹配过程,修正匹配位置。误差修正的过程如下:(1)设置轨迹点与匹配位置间距离容差ρ,每个轨迹点匹配结束后,计算检核匹配位置与对应轨迹点间的距离D;(2)比较距离D与容差ρ数值大小,若D<ρ,则继续下一时刻轨迹点的匹配;若Dρ,则以当前轨迹点为起始点重新判定起始匹配路段和起始位置。

      图  4  匹配误差传递

      Figure 4.  Transmission of Matching Error

    • 为验证本文匹配方法的有效性,采用武汉光庭公司生产的高精度矢量道路数据和车辆行驶测试数据进行了轨迹与地图匹配实验。测试环境为Intel(R)Core(TM)i7-9750H CPU @2.60 GHz 2.59 GHz、RAM 16.0 GB、Windows10 X64、PyCharm 2018、Python 3.6。实验选取了不同长度、不同级别道路实地跑车采集轨迹数据,包含平行路段、复杂路口和立交桥等特殊路段,测试路线如图 5所示,路线基本信息如表 3所示。

      图  5  测试路线

      Figure 5.  Test Routes

      表 3  测试路线基本信息

      Table 3.  Basic Information of Test Routes

      路线 起始位置 终点位置 路线长度/km
      1 139.545 748 4°E,35.544 231 7°N 139.352 959 4°E,35.418 647°N 26.3
      2 139.483 113 9°E,35.506 643 1°N 139.377 809 7°E,35.440 759 1°N 16.9
      3 139.326 290 5°E,35.428 644 4°N 139.294 092 9°E,35.405 629 4°N 10.8
      4 139.361 955 7°E,35.416 893 1°N 139.366 901 3°E,35.423 461 5°N 2.0
      5 139.330 056 4°E,35.431 432 2°N 139.338 216 9°E,35.427 276 6°N 1.8
      6 139.328 489 9°E,35.427 437 4°N 139.330 095°E,35.427 483°N 2.1

      实验前需要剔除轨迹数据中重复的坐标点和未显示经纬度坐标的点,并对道路数据和轨迹数据进行坐标转换。

    • 考虑到GNSS定位误差和道路宽度,距离约束的阈值设置为15 m,匹配位置误差修正容差设置为50 m。为了更好地验证本文方法效果,将本文方法和文献[9]提出的几何匹配方法以及文献[12]提出的路网拓扑约束匹配方法进行对比,结果如图 6所示。

      图  6  匹配结果

      Figure 6.  Matching Results

    • 本文对3种方法在立交桥、路口和平行路段等特殊路段的匹配结果进行了对比。由图 6可知,在立交桥处,文献[9]方法出现误匹配;文献[12]方法和本文方法利用拓扑约束准则匹配到正确路段。在路口处,文献[9]方法容易出现误匹配;文献[12]方法能够处理一般路口的匹配问题,但在多路径通行路段仅仅以最短路径作为车辆真实行驶道路并非可靠的解决方法;本文方法利用拓扑、航向和里程约束准则在复杂路口和多路径通行路段能成功匹配。文献[9]方法无法应对平行路段的匹配问题;在起始路段匹配正确的情况下,文献[12]方法利用路网拓扑约束可以处理后续路段的匹配,但当车辆在平行路段起步时,该方法容易出现误匹配;本文方法利用距离、速度和航向约束准则可以优化起始路段的匹配。在没有平行路段和复杂路口的干扰下,3种方法均表现良好,只有文献[9]方法在前后轨迹点间距较大时出现误匹配。可见,本文方法在特殊路段能够进行准确匹配,基本上解决了车辆所在行驶路段的匹配问题。

      此外,本文以r=(nright/nall)×100%衡量匹配方法的准确度[24],对车辆轨迹匹配结果进行了统计,结果如表 4所示,其中r为匹配正确率,nright为正确匹配的路段数量,nall为轨迹对应的全部路段数量。由表 4可知,本文方法平均匹配准确率达到93.53%,相比较于文献[9]和文献[12]匹配方法,其准确率有了较大提高,能满足定位导航的需求。

      表 4  匹配结果比较

      Table 4.  Comparison of Matching Results

      匹配方法 nall nright r/%
      本文方法 340 318 93.53
      文献[9]方法 340 275 80.88
      文献[12]方法 340 311 91.47

      本文匹配位置的确定过于依赖起始位置和行驶距离,尽管依靠误差修正的方式可以实时调整匹配位置,但对低频GNSS轨迹数据的匹配结果并不可靠。低频GNSS轨迹数据采样间隔大、轨迹点稀疏,一旦起始位置匹配错误,由于前后轨迹点间距过大,因距离传递累积的误差难以消除。

    • 为进一步探究本文算法的匹配效率,本文对不同测试路线匹配的时间进行了统计,结果如表 5所示。可以看出,本文对测试路线1的匹配用时为22.46 s,由于测试路线1含有120个轨迹点,每一个轨迹点及相邻轨迹点间匹配路段的确定需要耗时0.19 s,对于采样频率为0.1 s的车载GNSS基本满足车辆实时定位导航的需求。但与文献[12]方法相比,实时性仍有待于进一步提升。由于文献[12]方法以增量化方式选取最短路径作为匹配路段,降低了匹配复杂度,其匹配时间仅需0.147 s。

      表 5  匹配时间统计

      Table 5.  Statistics of Matching Time

      测试路线 轨迹点数量/个 匹配时间/s 单个轨迹点平均匹配时间/s
      1 120 22.46 0.19
      2 49 3.00 0.06
      3 82 20.25 0.25
      4 23 0.20 0.01
      5 23 2.06 0.09
      6 49 15.89 0.33

      表 5可知,匹配时间不仅与轨迹点数量有关,还与车辆行驶路段的复杂程度密切相关。当车辆行驶道路交叉口较多时,算法匹配耗时多。测试路线2与测试路线6所含轨迹点数量一样多,尽管测试路线2距离更长,但由于测试路线6匹配时需要进行更多路口的判定,故耗时多。

      综上所述,本文方法总体上匹配效果良好,在保持较高匹配准确率的同时能够基本满足车载定位导航实时性的需求。但本文方法不适用于低频GNSS轨迹数据车辆位置的精确匹配,且实时性可以进一步提升。

    • 本文提出了一种顾及速度与航向信息的轨迹匹配方法,实现了不同复杂程度城市路段的GNSS轨迹数据地图匹配。该方法在建立路网拓扑关系的基础上,考虑车辆行驶速度与航向信息,优化了匹配路段的选取过程,同时改进了起始匹配路段与匹配位置的判定准则,并利用匹配位置修正起始位置的判定,避免了传统拓扑匹配方法因起始位置匹配错误导致的误差传递累积;在候选道路集构建中考虑轨迹的延续性,增加矩形缓冲区,避免漏匹配;利用速度与时间信息在匹配路段上确定匹配位置,可以较为真实地反映车辆行驶状态。实验结果验证了本文方法的有效性。

参考文献 (24)

目录

    /

    返回文章
    返回