地球信息科学学报 ›› 2015, Vol. 17 ›› Issue (10): 1143-1151.doi: 10.3724/SP.J.1047.2015.01143

• • 上一篇    下一篇

一种面向海量浮动车数据的地图匹配方法

王晓蒙1,2(), 池天河2,,A;*(), 林晖1,2, 邵静1,2, 姚晓婧1,2, 杨丽娜2   

  1. 1. 中国科学院大学,北京 100049
    2. 中国科学院遥感与数字地球研究所,北京 100101
  • 收稿日期:2015-04-15 修回日期:2015-05-15 出版日期:2015-10-10 发布日期:2015-10-10
  • 通讯作者: 池天河 E-mail:wangxiaomeng1986@163.com;chith@126.com
  • 作者简介:

    作者简介:王晓蒙(1986-),男,博士生,研究方向为地图学与地理信息系统、智慧城市。E-mail: wangxiaomeng1986@163.com

  • 基金资助:
    国家科技支撑计划项目(2015BAJ02B00);国家科技部政策引导类项目(2011FU125Z24)

A Research of Map-Matching Method for Massive Floating Car Data

WANG Xiaomeng1,2(), CHI Tianhe2,*(), LIN Hui1,2, SHAO Jing1,2, YAO Xiaojing1,2, YANG Lina2   

  1. 1. University of Chinese Academy of Sciences, Beijing 100049, China
    2. Institute of Remote Sensing and Digital Earth, CAS, Beijing 100101, China
  • Received:2015-04-15 Revised:2015-05-15 Online:2015-10-10 Published:2015-10-10
  • Contact: CHI Tianhe E-mail:wangxiaomeng1986@163.com;chith@126.com
  • About author:

    *The author: CHEN Nan, E-mail:fjcn99@163.com

摘要:

浮动车数据已广泛应用于交通监管、智能出行、城市规划等领域,地图匹配是浮动车数据关键技术之一,保障匹配算法精度的同时提高匹配效率,是面向海量浮动车数据地图匹配方法的难点。本文提出一种基于HMM(Hidden Markov Model)的地图匹配模型,相对传统模型尝试了多个方面的改进:在发射概率计算中引入航向角变量,并探讨了该变量对模型精度的影响;以格网对路网进行划分,构建哈希索引,实现候选路段快速查找;采用路径无权距离替代路径实际距离,并对路网进行预处理,根据浮动车有限时间内的活动范围构建路段转移矩阵,实现路段转移概率快速计算,以减小路径匹配算法时间复杂度。将模型应用于北京出租车轨迹数据匹配结果表明,对于采样时间间隔在1~120 s的浮动车数据模型切实可行。在满足匹配精度应用需求的前提下,模型效率有了较大幅度提升,能有效应用于海量浮动车数据地图匹配。

关键词: 浮动车, 地图匹配, 隐马尔可夫模型, 网格, 路段转移矩阵

Abstract:

Floating Car Data (FCD) has been widely applied into traffic supervision, smart travelling, urban planning and so forth. Map-matching is one of the key technologies of FCD, for current map-matching algorithms, it is difficult to improve their map-matching efficiency considerably with a guaranteed accuracy. To solve this problem, our research proposes a map-matching model based on Hidden Markov Model (HMM), and makes a variety of improvements compared with the traditional model: (1) in addition to the position information, it introduces the heading angle variable to emission probability calculation, and discusses its influences on model accuracy and how to set a reasonable weight; (2) it divides road network according to a square grid, constructs candidate road segments searching algorithm based on hash index, and then discusses the optimization approach of the candidate road segment collection; (3) the numbers of segments in the path is used as the measurement for transition probability computation instead of the practical length, which simplifies the calculation procedure; (4) by preprocessing the road net, it constructs a road segment transition matrix according to the characteristic that floating cars have a limited scope of space activities in a given time, which realizes the fast calculation of road segment transition probability and reduces the time complexity of road matching calculation to a significant extent. We have applied this map-matching model in analyzing Beijing taxis’ trajectory data, in which the sampling time interval varies from 1 s to 120 s. The result demonstrates that this model is practicable, the required road segment transition matrix can be constructed in affordable space cost, and its efficiency is improved significantly with the condition that the accuracy meets the application requirements, which makes the model more applicable for massive FCD map-matching. As a conclusion, the proposed model has a high application value for multiple cases.

Key words: FCD, map matching, HMM, grid, road segment transition matrix