一种面向海量浮动车数据的地图匹配方法_王晓蒙.pdf

第17卷 第10期 Vol. 17, No.10 2015 年10月 Oct., 2015 一种面向海量浮动车数据的地图匹配方法 1,2 2* 1,2 1,2 1,2 2 王晓蒙 ，池天河 ，林 晖 ，邵 静 ，姚晓婧 ，杨丽娜 （1. 中国科学院大学，北京 100049；2. 中国科学院遥感与数字地球研究所，北京 100101） 摘要：浮动车数据已广泛应用于交通监管、智能出行、城市规划等领域，地图匹配是浮动车数据关键技术之一，保障 匹配算法精度的同时提高匹配效率，是面向海量浮动车数据地图匹配方法的难点。本文提出一种基于HMM （Hid- den Markov Model ）的地图匹配模型，相对传统模型尝试了多个方面的改进：在发射概率计算中引入航向角变量， 并探讨了该变量对模型精度的影响；以格网对路网进行划分，构建哈希索引，实现候选路段快速查找；采用路径无 权距离替代路径实际距离，并对路网进行预处理，根据浮动车有限时间内的活动范围构建路段转移矩阵，实现路段 转移概率快速计算，以减小路径匹配算法时间复杂度。将模型应用于北京出租车轨迹数据匹配结果表明，对于采 样时间间隔在1~ 120 s 的浮动车数据模型切实可行。在满足匹配精度应用需求的前提下，模型效率有了较大幅度 提升，能有效应用于海量浮动车数据地图匹配。 关键词：浮动车；地图匹配；隐马尔可夫模型；网格；路段转移矩阵 DOI:10.3724/SP.J. 1047.2015.01143 1 引言 贝叶斯定理的最优路径匹配算法，然而，由于匹配 过程中候选路径数量以几何倍数增长，算法效率较 交通信息采集是智能交通系统的基础，传统的 低。此后，学者主要从候选路段筛选和路径匹配2 信息采集技术包括感应线圈、摄像头、地磁等，随着 个关键步骤，对地图匹配算法进行改进提升匹配效 移动传感器技术的发展，浮动车（Floating Car Data ， 率。为提高候选路段查找效率，Raymond[8] 以道路 FCD ）技术逐渐成为国内外研究的热点。浮动车数 交点替代候选路段，将点与线的邻域分析转换为点 据具备实时性强、采集成本低、覆盖范围广等优点， 与点，降低了几何分析复杂度，缺点是道路交点难 主要基于大规模实时运行的交通工具（如公交车、 以反映浮动车的真实位置；章威和李宇光分别基于 [9] [10] 出租车等），通过GPS、加速度器、陀螺仪等车载传 格网划分 和路网栅格化技术 构建索引，通过折 感器收集交通信息。目前，浮动车技术已应用于多 半算法实现了候选路段快速查找，时间复杂度为 [1] [2] O lnm ，m 为索引规模。为提高路径匹配算法效 个领域，包括交通监管 、路径推荐 、行程时间估计 ( ) [3] [4] 率，一方面需控制匹配过程中候选路径数量的增长 与预测 、城市规划 等。 由于数据采集、地图数据处理等过程存在误 速度，另一方面需提高路径分析效率。基于隐马尔 差，浮动车数据应用前需进行地图匹配（Map-Match- 可夫模型（Hidden Markov Model, HMM ）的地图匹