路网匹配是基于位置服务中的关键预处理步骤,它将GPS轨迹点匹配到实际路网上.以此为基础对数据进行分析和挖掘,能够辅助解决城市计算中相关问题,例如建立智能交通系统、协助用户规划出行.对国内外学者在该研究领域取得的成果进行了分类总结,发现这些匹配算法可以较好地解决高采样率的路网匹配问题.但是,随着城市交通的快速发展,获取和处理车辆位置信息的成本不断提高,低频采样点越来越多,现有算法匹配精确度大幅度下降.于是,近年来出现了基于隐马尔可夫模型(hidden Markov model,简称HMM)的路网匹配算法.隐马尔可夫模型可以较为平滑地将噪声数据和路径约束进行整合,从有许多可能状态的路径中选择一条最大似然路径.重点总结了基于隐马尔可夫模型的路网匹配算法,主要是从特点与实验结果的角度对其进行对比总结,有些实验结果的正确率在一定条件下最高可达90%,这说明了基于隐马尔可夫模型的路网匹配算法在低采样率下的有效性.最后,对未来的研究可能采取的方法进行了展望.
Map matching is a key preprocessing step in the location-based service to match GPS points into a digital road network. Data analysis on the map matched trajectory data can be used to facilitate many real city computing applications such as intelligent transportation system and trip planning. This survey provides a systematic summary of existing research achievements of map matching. With the rapid development of urban traffic, the cost of acquiring and processing vehicle location information is increasing, low-sampling-rate GPS tracking data is growing, and the accuracy of existing algorithms is not adequate. In recent years, map matching algorithm based on hidden Markov model (HMM) has been widely studies. HMM can smoothly assimilate noisy data with path constraints by choosing a maximum likelihood path. The accuracy of HMM-based algorithms can reach 90% under certain conditions, which confirms the validity of map matching algorithm based on HMM at low sampling rate. A perspective of future work in this research area is also discussed.
http://www.aiweibang.com/yuedu/100330112.html).]]>
这些出行车辆装配的GPS(global positioning system, 全球定位系统)设备每天能够收集到大量的移动位置序列和车载状态信息, 这些数据蕴含着丰富的交通信息和用户行为, 可以实时地了解路网上乘客需求的时空变化以及乘客出行的有关信息.通过使用大数据处理技术, 分析车辆轨迹数据和乘客需求数据, 挖掘出对乘客打车和司机载客有帮助的价值信息, 能够对乘客的出行提供有效的指导.同时, 从一定程度上反映出城市交通状况和人群流动情况, 便于了解交通流量规律, 发现人群行为特征, 协助改善交通状况等, 具有极大的科研和应用价值.
另外, 随着基于位置服务(location-based service)和移动社交网络(mobile social network)的发展和普及, 越来越多的应用, 如热路线查找[
GPS设备定位示例
GPS device positioning illustration
在
将所观察到的用户或者交通工具的GPS位置关联到给定电子地图的道路网络上的过程称为路网匹配.路网匹配对于许多基于位置的应用程序是一个基本的数据预处理步骤(如
轨迹数据挖掘示意图
Paradigm of trajectory data mining
路网匹配是一个将原始的经纬度坐标转换成一个序列的处理过程, 其涉及到的概念和定义如下.
GPS日志和轨迹的示意图
Illustration of GPS log and GPS trajectory
路网中的一条路径示意图
Illustration of a path in a road network
路网匹配问题可以描述为, 给定未加工的GPS轨迹
路网匹配的流程图
Paradigm of map matching
直观来讲, 解决路网匹配最简单的方法就是将GPS点关联到最近的路段上, 但有些时候效果会非常差, 如
GPS点关联到最近的路段
GPS point matched to the nearest road segment
根据算法的不同特性, 现有的路网匹配算法可以有下列分类标准.
根据输入数据所涉及的信息, 现有的路网匹配算法可被分成4类, 见
以数据涉及信息进行算法分类
Algorithm classification by data involved in the information
算法 | 代表性工作 | 算法描述 | 优缺点分析 |
几何匹配算法 | 点到点匹配方法[ |
首先计算GPS点与道路网络上每个节点的距离, 然后将GPS点匹配到距离最近的节点上 | 算法简单, 容易实现, 计算速度快, 但受道路网络上节点密度及分布影响, 容易造成错误匹配, 实用性不强 |
点到线匹配方法[ |
将道路网络中的所有路段都看作候选路段, 首先计算GPS点到每个候选路段的投影距离, 然后选择距GPS点最近的路段为匹配路段, 相应的投影点就是匹配节点 | 准确性提高, 但由于没有考虑道路的拓扑结构和车辆的历史信息, 所以稳定性不好, 在复杂路况下容易发生错误匹配 | |
线到线匹配方法[ |
首先获得车辆的历史轨迹曲线, 然后与候选路段进行相似性比较, 最终选择相似度最高的路段 | 考虑车辆的历史信息, 提高了匹配效率, 但计算量大, 受异常值影响较大, 并且某个GPS点的匹配错误可能会引起一系列的错误匹配 | |
拓扑关系算法 | 简单拓扑关系匹配方法[ |
运用车辆历史数据、轨迹之间关系和道路拓扑特征等信息来限制采样点的候选匹配 | 利用历史采集点和空间道路网的数据, 提高匹配效率, 但容易受到采集噪声和数据稀疏性的影响, 在复杂路况下容易发生错误匹配 |
加权拓扑匹配方法[ |
首先对轨迹方向、GPS点到道路的距离以及相关性等进行加权计算得到该路段的总权重, 然后选择权重最大的路段为匹配路段 | 根据GPS信息和道路几何形状, 使用较少的输入, 引入额外的参数和准则来提高匹配效率, 但易受采集噪声和数据稀疏性的影响, 在复杂路况下容易发生错误匹配 | |
概率统计算法 | 置信区间匹配方法[ |
基于多假设思想, 首先在置信区域内选出多条路段加入到候选路段集中, 然后对每条候选路段都计算出一个得分, 最终选择得分最高的路段作为匹配路段 | 即使某个GPS点匹配错误也不会对后续匹配产生太大影响, 但同时也降低了路网匹配程序的执行速度 |
新型概率匹配方法[ |
在道路交叉口处设置一个椭圆或矩形的置信区域, 通过一些基于经验性研究准则来检测车辆在道路交叉口的转弯动作 | 计算速度较快, 稳定性较好, 对识别车辆转弯很有效, 即使车辆低速运行时也能正确匹配 | |
先进匹配算法 | 模糊逻辑方法[ |
采用模糊逻辑的方法解决路网匹配问题, 通过隶属函数描述以及候选道路来定义误差模型 | 实时性好, 鲁棒性较好, 匹配效率较高, 但计算开销较大, 缺乏理论依据, 对输入要素的利用率较低, 实用性较差 |
证据推理方法[ |
基于D-S证据理论, 首先利用车辆位置与方向信息为证据分别构造基本概率分配函数, 再将其融合为一个联合支持度函数, 然后比较融合后的各候选路段支持度大小, 最终选定支持度最高的路段作为匹配路段 | 通过证据推理可以得到唯一正确的判断结果.但是只考虑GPS点的两种信息:位置和方向, 准确度不高.而且算法实现复杂、计算开销大 | |
卡尔曼滤波方法[ |
考虑GPS系统误差特点, 基于卡尔曼滤波中的白噪声假设, 通过分析卡尔曼滤波后的模型误差特性是否满足高斯白噪声分布来完成地图匹配 | 稳定性较高, 特别是在交叉路口.但是由于没有充分考虑车辆信息和路网信息, 匹配最初阶段效果并不理想 | |
贝叶斯推理[ |
使用多假设技术(multiple hypothesis technique, 简称MHT), 为置信区域内所有路段产生伪测量值, 路网拓扑分析(连接、方向和道路设计参数)与伪测量值一起被用来为每个车辆推导出一组假设及概率值 | 缺少初始匹配方法, 在很大程度上影响了随后匹配的性能, 因此存在错匹配可能性 |
基于几何信息的匹配算法是由Bemstein等人在20世纪90年代提出来的.它仅利用时空道路网络的几何信息进行匹配, 如距离、角度、形状等, 而不考虑路段间的连通性[
基于几何信息的匹配算法相对简单, 易于实现, 在定位系统没有较大误差的情况下匹配度较高, 但是它们没有使用GPS采集点之间的联系、交通规则信息和道路的拓扑信息等, 导致准确率下降; 而且一旦出现错误匹配无法及时修正, 稳定性较差.虽然它们可以为密集的GPS轨迹提供良好的匹配, 但如果是针对有噪声且稀疏的数据就不再适用.
拓扑信息是指实体(点、线、多边形)之间的相连(线)、邻接(多边形)、包围(多边形与点)等关系.基于拓扑信息的匹配算法[
基于拓扑信息的路网匹配算法不仅要考虑GPS采集点与道路的距离, 而且要考虑路网的拓扑连通性以及历史采集点, 从而使匹配效率和准确性在一定程度上有所提高.但它们仍然容易受到采集噪声和数据稀疏性的影响, 还不能完全解决复杂的城市道路问题.
Honey等人在1989年首先将概率统计方法运用在路网匹配算法中[
基于概率信息算法不要求车辆总是在道路上.如果车辆接收到的GPS数据偏离了已知的路网, 算法将会不断地比较接收到的GPS坐标与偏离路段的坐标, 并识别与车辆匹配的路段[
高级路网匹配算法往往综合考虑全面信息, 包括最近出现的道路网络的拓扑结构和轨迹数据中的噪音; 使用更精致的概念, 如卡尔曼滤波[
根据匹配轨迹时考虑采样点的范围, 路网匹配算法可以分为两类:局部/增量和全局方法.具体见
以考虑采样点的范围进行算法分类
Algorithm classification by range of sampling points
算法 | 代表性工作 | 算法描述 | 复杂度 | 优缺点分析 |
局部/增量方法 | 文献[ |
使用距离相似度和方向相似度组合来评价候选边 | 除了位置样本外, 该方法假设预期行驶路线没有任何进一步知识, 而且也不使用任何速度信息 | |
文献[ |
“自适应裁剪”, 将轨迹分段, 采用Dijkstra算法在两个采样点之间构建最短路径 | 增量算法快, 质量低; 全局算法慢, 质量好.达到二者的平衡, 提高计算速度 | ||
文献[ |
使用一个恒定深度的基于局部匹配的几何形状的递归前瞻策略 | 文章提出2类3种算法:局部/增量1种; 全局算法2种.实验结果表明, 全局算法的匹配效果更好 | ||
文献[ |
引入基于分段的匹配算法, 给不同采样点分配置信度值.先匹配高置信度分段, 然后使用之前匹配的边来匹配低置信度分段 | 采样率很高时, 执行速度快且效果好.如果是低采样率的话, 两个采样点之间断了联系则很难匹配, 精度显著下降 | ||
文献[ |
追求一小部分轨迹的局部匹配.当匹配一个新GPS点时, 要考虑其前一个位置和最后匹配的边 | - | 对于只考虑当前位置的方法, 结果受到测量误差影响很大.因此, 局部/增量算法的准确性普遍较低, 因为相邻点的相关性被完全忽略 | |
全局算法 | 文献[ |
该算法在概念上从左到右(沿着轨迹的方向)在所有自由空间上扫描一条线, 同时保持在扫描线上的点通过左下角开始的自由空间中的一些单调路径可达.然后在扫描线推进的同时更新该Dijkstra风格的可达性信息 | 该算法对所有临界值应用参数搜索.然后它通过在从左下角到右上角的自由空间中找到单调路径来解决决策问题 | |
文献[ |
提出两种全局算法:一种使用弗雷歇距离来衡量GPS轨迹和候选路段序列的匹配度, 旨在最小化弗雷歇距离; 另一种扩展上述算法, 用弱弗雷歇距离(weak-Fréchet-distance)来减少异常值的影响 | 采用一种前瞻技术来减少遗漏路段的情况, 进一步提高准确率.然而, 当前方法没有尝试使用真实路径来评估实际匹配精度.同时, 它忽略了轨迹中的时间/速度信息 | ||
文献[ |
采用离线捕捉方法, 提出了一种基于道路网络的加权图表示的算法, 其中, 每个边的权重表示轨迹到地图上的弧序列的距离.通过用于加权图的Dijkstra最短路径算法来找到道路网络中的匹配轨迹, 即与初始轨迹具有最小距离的路线 | - | 基于类似于平均弗雷歇距离(average-Fréchet-distance, 简称AFD)的测量, 然而在匹配曲线上没有给出整体质量保证.同时, 数据集上的一些细节, 如类型和大小缺失 | |
文献[ |
通过将相邻时刻轨迹点的候选匹配路段构建成候选匹配图, 并从该图中求解并搜寻一条最佳匹配路径, 该路径即对应着最终的匹配结果 | 文献[ |
||
文献[ |
采用最优化模型来求解匹配结果 | 其最可能行驶路径是通过对历史轨迹数据的查询来获得的 |
局部/增量算法利用当前GPS轨迹点的局部特征来进行路网匹配.算法使用贪心策略, 从已经匹配好的解决方案中依次延伸得到最终的全局解.文献[
局部/增量算法计算速度快、实时性强, 所以经常用于有在线需求的应用.当采样速率较高时(比如2s~5s), 能够获得良好的匹配效果.但随着采样率的降低, 局部/增量算法将呈现“弧跳”现象[
全局算法考虑整个采样轨迹, 从路网中找到一条与其最接近的匹配路径.大多数全局路网匹配算法[
与局部/增量算法相比, 全局算法更准确, 对采样率降低表现出更大的健壮性, 能够较好地处理长采样间隔情况下的路网匹配问题, 但计算成本较高.由于缺乏真实的车辆和道路实验, 使得它难以评估实际的匹配精度.此外, 目前的全局匹配算法只采用空间分析, 而忽略了轨迹的时间/速度约束, 这使它们也容易受到采样率下降的影响.由于全局算法需要整个行驶轨迹的信息, 所以通常适用于离线任务(例如在所有轨迹产生后, 挖掘频繁的轨迹模式).
如
以采样的频率进行算法分类
Algorithm classification by sampling rate
算法 | 采样设备 | 采样频率 | 代表 |
高频采样算法 | 浮动车GPS+航位推算罗盘/高度计 | 1s~10s | 所有局部算法、部分全局算法 |
低频采样算法 | 浮动车GPS+航位推算罗盘/高度计 | 30s以上 | HMMM[ |
更低频率采样算法 | 手机GPS/手机基站+WIFI/惯性传感器/蜂窝指纹 | 2min以上 | VTrack[ |
GPS样本点的采样频率影响着算法的匹配精确度, 当GPS采样频率较高时(一般是1s~10s), 即使仅将轨迹点匹配至最近的道路片段, 也可得到较高的正确率.高采样率轨迹的路网匹配技术已经被商业化为个人导航设备.几乎上述所有的路网匹配算法都是基于高样本率数据集的.
然而, 高采样率的数据集的采集和存储需要消耗更多的存储空间、GPS模块的操作和计算时间.基于节约能源以及浮动车本身特性等原因, 在实际应用中, 返回给调度中心的数据往往是低采样率的(1min~2min采样一次, 甚至更低).
在实际中, 存在大量的低采样率GPS跟踪数据(采样间隔超过1min).例如, 为了节省通信和能源成本, 出租车通常以较低的频率向调度中心报告GPS位置.文献[
采样间隔的分布[
Distribution of the sampling interval [
在这种情况下, 基于高样本率的路网匹配算法无法适用于低样本率的数据集.针对此问题, 研究人员已经提出了一些基于低采样率的数据集的路网匹配算法, 如ST-Matching[
上述的路网匹配技术主要用于GPS定位数据, GPS具有全球可用性和较高的精度.然而在许多形况下, 基于粗粒度网络的定位信息是唯一可行的解决方案, 例如从蜂窝提供商处定位, 在需要高效节能定位的情况下[
因此, 一些新的路网匹配技术开始出现, 利用手机上的其他传感器(如WiFi[
现在, 手机使用率非常高, 运营网络也是现成的.如果能够发动手机用户积极参与交通流预测, 则会极大地提高预测的实时性、准确性和覆盖率, 而且投入和维护的成本都比较低.因此, 这种方法非常易于推广普及.但在这种情况下, 传统路网匹配算法的典型假设不成立.手机位置不再接近实际路段, 位置误差是以km计, 改变手机塔关联会有来回转换现象, 且输入位置样本高度稀疏.所以, 亟需一些能够处理更低采样率和定位精度的路网匹配算法.
路网匹配算法可以分为实时和离线算法:实时算法将记录过程中的位置与道路网络联系起来; 离线算法在数据被记录后使用, 将数据匹配到道路网络.
在实时应用中, 如交通感知, 希望进行路网匹配, 而未来的数据尚不可知, 这就要求算法必须在线.实时应用程序只能基于给定时间前的点计算(而不是一个完整的旅程), 意在现实生活环境中使用.上文介绍的增量算法[
而离线应用可以考虑所有的点, 所以可以容忍较慢的性能而有利于提高精度.上文介绍的全局算法[
目前, 因为要节省能源成本和通信成本以及车辆本身的特性, 输入GPS数据的采样率普遍较低, 两个采样点之间的许多细节很容易被丢失.例如,当采样间隔为2min时, 即使车速为30km/h, 两个采样点之间的距离也可达到1km.特别是在复杂的城市道路网络中, 车速较高、街区较短、误差较大的情况下, 大部分GPS点之间的关联信息将会丢失[
在近几年的研究中出现了一些基于低采样率的数据集的路网匹配算法, 可以较好地处理这个问题, 比较著名的方法就是基于隐马尔可夫模型(hidden Markov model, 简称HMM)的路网匹配算法, 其结果的正确率在一定条件下最高可以达到90%.下一节将重点介绍基于HMM的路网匹配算法.
20世纪60年代, Baum等人和其他作者在一系列的统计学论文[
http://baike.baidu.com/).]]>
● 隐含状态
● 可观测状态
● 状态转移概率矩阵
● 观测状态概率矩阵
● 初始状态概率矩阵
隐马尔可夫模型通过对道路的连通性进行明确建模, 并同时考虑许多不同的路径假设来解决路网匹配问题.最早利用HMM来进行路网匹配的应用来自Lamb等人[
隐马尔可夫模型可以解决3类问题.
● 评价:将最可能的系统与观测序列匹配, 使用前向算法(forward algorithm)求解.
● 解码:确定最可能产生观察序列的隐藏序列, 使用维特比算法(Viterbi algorithm)求解.
● 学习:确定模型参数最可能产生的一系列观察, 使用前向-后向算法(forward-backward algorithm)求解.
路网匹配问题实际上是一个解码问题.假设移动对象在路网的交叉点间移动, 且移动的过程符合马尔可夫模型.虽然无法直接观察到移动对象所经过的道路轨迹(可以把这些轨迹看作隐含状态), 但是可以获得隐含状态的输出, 即GPS样本点(假设观测值仅与移动对象的隐含状态相关).于是, 基于HMM的路网匹配算法就变成在给定一系列观察的前提下, 寻找最有可能产生这个观察序列的隐含状态序列, 也就是实际的移动轨迹.这里有两个状态集合.
● 可观测状态集合:从GPS设备中得到的位置信息(经度、纬度).
● 隐含状态集合:拥有GPS设备的物体(车、人等)实际所在的位置.
这样, 就可以把路网匹配问题与隐马尔可夫模型结合起来.然后, 用一定的规则去拟合历史的真实数据得到状态转移概率矩阵
● 观测状态概率.观测的GPS样本点离候选路段越近, 这个样本点在这个路段上的概率就越大.
● 状态转移概率.这里有两种解决思路:
➢ 一是前后两个GPS样本点的距离越近, 状态转移的概率就越大;
➢ 二是真实路段上的前后两个点之间距离与GPS观测的前后两个样本点之间距离越接近, 状态转移概率就越大.
● 初始状态概率.代表移动对象初始时位于某个路段上的概率, 使用相应GPS样本点的观测状态概率来表示.
在基于HMM的路网匹配算法中, 对于每一个GPS轨迹点, 首先确定一组候选路段.每个候选路段被表示为马尔可夫链中的隐藏状态(顶点), 并具有观测状态概率, 这是观察GPS点是否与候选路段匹配的可能性.如果发现GPS点非常接近某个路段, 就给这个路段指定一个较高的概率值.然后, 为马尔可夫链中连接每一对相邻顶点的边计算权重, 即状态转移概率.最终, 在马尔可夫链上找到具有最高观测状态概率和状态转移概率的最大似然路径.一般使用维特比算法(Viterbi algorithm)进行求解, 实际上是用一个动态规划(dynamic programming, 简称DP)算法解隐马尔可夫模型预测问题, 即用动态规划在道路网络中快速找到使观测概率和转移概率的乘积最大化的最优路径.这个过程如
基于隐马尔可夫模型的路网匹配过程
HMM-Based map matching process
基于隐马尔可夫模型的路网匹配过程示例
An example of HMM-based map matching process
从
基于隐马尔可夫模型的路网匹配算法计算过程
Calculation process of HMM-based map matching algorithm
ST-Matching算法结合时间和空间特征, 包括几何拓扑结构和速度约束.文献[
● 观测概率矩阵
一般来说, GPS观测点的测量误差可以被合理地描述为一个GPS观测点和实际路段之间距离的高斯分布. 这里采用的是一个均值
● 状态转移矩阵
算法根据路段投影过程为每个GPS采样点检索一组候选路段和候选点.然后构造一个候选图, 图中的节点是每个GPS观测的候选点集合, 而边是任意两个相邻的候选点之间的最短路径集.节点和边都基于空间/时间分析结果分配了权重值.结合观测和转移概率, 匹配算法在候选图中寻找一条具有最高得分的路径, 最大限度地提高全局匹配概率.
ST-Matching在匹配路网时, 会把GPS点对应到距离较近的路段上, 并不考虑其相邻点的关系, 所以会出现锯齿形的线路.IVMM的提出, 就是为了“拉直”不匹配的路段, 使其更适合地面真实路径.它在ST-Matching的基础上加入了“互动投票”, 就是说, 每个候选点会对在同一条单点最优的轨迹上的其他候选点进行加强, 即投票, 最后打分最高的点连起来形成匹配路径.
观测概率矩阵(同公式(1))和状态转移矩阵(同公式(2))的计算方法和ST-Matching相同, 只是公式(1)中的取值不同, 这里
IVMM算法从全局角度考虑观测点之间的相关性.所有观测点之间进行相互投票, 完全并行, 这样就不需要进行大量的计算得到可能的匹配结果, 而只需从候选集合中投票产生正确匹配结果, 算法复杂度较小.
与ST-Matching算法相近, 但没有考虑速率信息.它是用前后两个相邻GPS观测点的距离与两个候选点的距离之差的绝对值来表示这两段距离的接近程度, 越接近, 概率就越大, 且最后的概率是用指数函数来拟合.具体公式如下.
● 状态转移矩阵
其中,
● 观测概率矩阵
与ST-Matching算法相同(见公式(1)), 都是使用均值
其中, ||
● 初始状态概率
状态转移概率依赖于当前状态以及上一个观察状态, 所以不能严格满足维特比算法中对状态转移概率的要求, 从而产生两个问题:一是利用公式(1)得到的近似概率并不一定是其最大似然结果; 二是公式(1)将观测点在道路上的投影作为隐性状态的一部分, 但这个投影并不唯一, 从而增大了最大似然解的寻找难度.文献[
上述论文中使用的模型并不是完美的原始的HMM, 因为在计算状态转移概率时, 既要考虑候选点的信息, 也要考虑观测点的信息, 可以说是HMM的一个变种.本文将之前的HMM模型简化, 在计算状态转移概率时不考虑观测点之间的信息, 所以可以看作简化的HMM方法.
HMM模型对比
Comparison of HMMs
隐性马尔可夫模型包含的3种概率如下.
● 观测概率矩阵
和之前的算法一样(见公式(1)), 用高斯分布模拟(本文是
● 状态转移矩阵
车辆从一个道路交叉点转移到另一个交叉点的概率, 对应于
其中,
● 初始状态概率
代表车辆在初始时刻处于某个道路交叉点的概率, 文献[
之前的算法的状态转移概率公式中都有||
算法使用在线的维特比算法来实现实时的路网匹配.计算观测概率矩阵时考虑了路段的宽度信息和速度信息.在计算状态转移矩阵时使用了机器学习的方法.
● 观测概率矩阵
● 状态转移矩阵
使用支持向量机(support vector machine, 简称SVM)来探悉状态转移概率, 而不是像之前的算法一样先验地选择模型, 然后估计其参数.这种方法的主要优点是提供了一个数据驱动的框架, 用于集成多个转移评分函数.文献[
距离差异函数测量传感器推导的行驶距离和最短路径长度之间的差异.
动量变化函数测量车辆在
这两个公式计算出来的都只是一个特征, 然后使用被标记为正确或不正确转换的实例训练支持向量机分类器, 其中, 特征向量由上述两个评分函数给出的分数组成.使用这种分类方法,
为了利用增量方法实现在线的全局路网匹配算法, 需要在不知道未来输入的情况下沿着马尔可夫链进行不可逆的在线决策, 同时确保部分解在组合时产生全局最优解.
文献[
QMM是第1个强调运行时间的路网匹配算法.算法设计在多核CPU上运行, 因为路段的处理可以在建立索引时彼此分离, 并且每个样本轨迹点在匹配时相互独立.算法应用多线程技术极大地减少了运行时间, 同时在HMMM算法基础上作了一些改进.
● 观测概率矩阵
由于存在不可避免的GPS测量误差, 在主路上行驶的车辆记录的GPS采样点位置可能更接近侧路, 原始算法可能会错把这些点与侧路匹配.
此外, 算法也考虑了类似于HMMM算法[
上述基于隐马尔可夫模型的路网匹配算法的对比见
基于隐马尔可夫模型的路网算法设置比较
Comparison of HMM-based map matching algorithm setup
算法 | 观测概率矩阵 | 状态转移矩阵 | 初始状态概率 |
ST-Matching | 均值 |
空间分析函数和时间分析函数的乘积.考虑了道路网络的拓扑结构和前后两个时间点之间的速率信息 | - |
IVMM | 空间分析函数和时间分析函数的乘积.考虑了道路网络的拓扑结构和前后两个时间点之间的速率信息 | - | |
HMMM | 用指数函数来拟合前后两个相邻GPS观测点的距离与两个候选点的距离之差的绝对值 | 在初始时刻时的观测概率矩阵 | |
Simplified HMM | 假设状态转移概率与两个交叉点间的距离正相关, 也考虑行驶时间、成本等距离之外的其他因素 | 使用相应交叉点的观测概率来表示移动 | |
OHMM | 使用支持向量机来探悉状态转移概率.两个特征为距离差异函数和动量变化函数 | - | |
QMM | 用指数函数来拟合前后两个相邻GPS观测点的距离与两个候选点的距离之差的绝对值 | - |
基于隐马尔可夫模型的路网算法性质比较
Comparison of HMM-based map matching algorithm characteristic
算法 | 数据信息 | 考虑范围 | 采样频率 | 计算实时性 | 特点 |
ST-Matching | 几何信息+拓扑信息 | 全局 | 低采样率 | 线下计算 | 较早的算法, 结合时间和空间特征.与增量算法和基于AFD的全局匹配算法相比, 具有更高的匹配精度 |
IVMM | 拓扑信息 | 全局 | 低采样率 | 线下计算 | 在ST-Matching的基础上加入了“互动投票”环节, 比ST-Matching有更高的匹配精度和更好的鲁棒性 |
HMMM | 几何信息+拓扑信息 | 全局 | 低采样率 | 线下计算 | 首次提出基于隐马尔可夫模型路网匹配的概念, 并公开实验数据, 是之后许多研究的基础 |
Simplified HMM | 几何信息 | 全局 | 低采样率 | 线下计算 | 简化的隐马尔可夫模型, 实现虽然简单, 但仍有较好的性能.而且匹配速度快 |
OHMM | 拓扑信息 | 局部/增量 | 低采样率 | 在线计算 | 在线的路网匹配算法.以较低的输出延迟实现了较优的匹配结果 |
QMM | 几何信息 | 全局 | 低采样率 | 线下计算 | 第1种强调运行时间的路网匹配算法.采用多线程技术极大地减少了运行时间 |
随着手机的普及, 移动大数据成为重要的资源, 提供了丰富的信息, 而且几乎没有成本.近几年新出现的一个研究方向和热点是将HMM用在采样周期低、噪声误差大的手机定位.高频率采样的智能手机定位精确但无法实时定位, 因为它消耗过多的智能手机的带宽和电池电源.因此, 手机数据一般非常稀疏且噪声较大.有必要在确保精确和及时的情况下, 为手机轨迹路网匹配开发鲁棒算法.
SnapNet系统[
隐马尔可夫模型对于低采样率路网匹配问题的适用性, 使得它在手机数据匹配方面也得到较好的应用.由于数据的来源不同, 接下来的实验比较中没有加入手机轨迹路网算法.
上述基于HMM的算法的实验环境与评价标准各有千秋(见
基于隐马尔可夫模型的路网算法实验结果对比
Experiment results comparison of HMM-based map matching algorithm
算法 | 评价标准 | 测试环境 | 比较对象 | 实验结果 |
ST-Matching | 匹配质量, 运行时间 | 合成数据 | 增量算法, 基于AFD的全局匹配算法 | 当采样间隔为2.91min时, |
城市:北京, Geolife中28条轨迹 | 增量算法, 基于AFD的全局匹配算法 | 当采样间隔为30s时, |
||
IVMM | 匹配质量, 运行时间 | 城市:北京, Geolife中28条轨迹 | ST-Matching算法 | 当采样间隔为1.5min~6.5min时, IVMM的精度维持在70%左右, 比ST-Matching算法有10%的改进.当采样间隔超过6.5min时, IVMM和ST-Matching算法的性能变得接近, 但仍具有5%的优势 |
HMMM | 匹配质量, | 城市:西雅图, 7 531个采样点 | - | 当采样间隔为30s时, RMF为0.11%.随着采样率间隔不断增加, RMF上升, 采样间隔2min的RMF为0.1, 当到达5min以上时, RMF超过0.5 |
Simplified HMM | 匹配质量, 运行时间 | 城市:西雅图, 7 531个采样点 | HMMM算法 | 当采样间隔为90s时, RMF为0.2.采样间隔为5min时, RMF为0.6.随着采样间隔的增加, RMF逐渐上升.当采样增加至8min时, RMF为1.1, 之后出现少许下降.与HMMM算法相比, RMF略大, 但效率较高, 约为前者的2倍 |
OHMM | 匹配质量, 运行时间 | 城市、郊区:新加坡, 4条公共线路 | 城市路线和农村路线比较 | 除了大于4min的采样间隔外, 农村路线的准确性比城市路线的准确度高出大约5%.在小于1min的采样间隔, 两条路线的精度都高于0.9.在这两种情况下, 精度都随着采样间隔的增加而下降 |
QMM | 匹配质量, 运行时间 | ACM SIGSPATIAL Cup 2012竞赛数据 | 不同线程下的比较 | 当采样间隔为1s~30s时, 不匹配率保持在2%以内, 波动不大 |
算法测试实验使用的数据源有3种类型:合成数据、真实数据和竞赛数据.
● 合成数据
ST-Matching算法测试使用的合成数据是由模拟器随机生成的轨迹.它首先随机选择两个顶点的道路网络, 并计算它们之间最短的
● 真实数据
ST-Matching算法和IVVM算法实验中, 以人们标记的真实路径数据作为地面实况.路网数据采用北京的城市道路网络图, 包含58 624个顶点和130 714个路段.GPS轨迹数据都是从Geolife系统[
http://research.microsoft.com/en-us/um/people/jckrumm/MapMatchingData/data.htm), 行驶距离为80km, 包含7 531个GPS采样点, 采样间隔为1s.为了体现采样点的稀疏性, 还模拟了90s, 120s, 180s, 240s, 300s, 360s, 420s, 480s, 540s和600s等的采样周期.所有测试数据、地面实况数据和道路网络都已公开, 供其他研究人员开发、测试和比较自己的路网匹配算法]]>.
OHMM算法使用在新加坡的4条公交线路上收集的地面真实数据来评估算法的性能.为了比较不同环境下的表现, 选择了4条涵盖新加坡农村和城市地区的路线.农村路线的转弯次数较少, 主要由直通高速公路等直线路线组成.城市路线除了大量分岔路外, 还覆盖着高层建筑密集的城市街区.长度分别为36.3km, 11.3km, 27.3km, 32.5km.此外, 为了模拟不同采样频率的轨迹, 以10s~5min的采样间隔对原始数据(每1s~3s记录1次)进行二次采样.
● 竞赛数据
http://depts.washington.edu/giscup/home)的训练数据, 这是由ACM SIGSPATIAL主办的全球范围内的关于地图匹配算法的科技竞赛, 这也是此国际会议举办的第1次竞赛.这次科技竞赛影响力吸引了来自全球31支专业级的参赛队伍.所有算法当中匹配准确率最高的两个都是基于HMM的匹配算法.SIGSPATIAL GIS编写的数据集可以帮助各研究所的研究人员掌握地面真实数据.比赛是美国华盛顿州路网信息的简化版本, 原始地图数据从Open Street Map(OSM)(OpenStreetMap. Available from: http://www.openstreetmap.org/)获得, 采样间隔为1s~30s.]]>
ST-Matching算法在运行时间和匹配质量上进行了广泛的评价.实验中使用实际的程序执行时间来衡量运行时间.通过两个精度指标“准确的数量
IVMM算法在匹配质量和效率方面与ST-Matching算法进行比较.为了评估算法的效率, 实验比较了运行时间.为了评估匹配质量, 使用下式计算的正确匹配百分比(correct matching percentage, 简称CMP).
HMMM算法、ST-Matching算法、Simplified HMM算法评价标准都采用道路错误匹配指数(route mismatch fraction, 简称RMF), 是对从正确路径错误添加和错误减去的不正确道路的长度求和, 然后除以正确路径的长度来计算不正确路径所占比例, 也就是结果记录的误差值, 如
评价指标
Evaluation norm
OHMM算法评估使用两个性能指标:匹配精度和输出延迟.精度定义为地面真实路径中正确匹配的轨迹点的比例CMP, 某个轨迹点映射到地面真实路径中的任何道路段就是一个正确的匹配; 输出延迟是对于每个轨迹点算法所产生的平均输出延迟, 它通过在获得匹配结果之前经过的秒数来量化.
QMM算法使用不匹配率(mismatching percentage, 简称MP)作为评价标准, 采样间隔为1s~30s, 不匹配率保持在2%以内.
● ST-Matching算法
算法比较对象为基于点的先前匹配结果执行匹配的增量算法和旨在最小化平均弗雷歇距离(average Fréchet distance, 简称AFD)的全局匹配算法.合成数据的测试结果表示ST-Matching算法显著优于增量式和基于AFD的算法.同时我们注意到, 当采样率降低时, 增量算法的性能急剧退化, 而全局算法对采样率的变化更为鲁棒.当采样间隔为2.91min时, ST-Matching算法匹配质量最好,
ST-Matching算法在GeoLife收集的实际数据上的测试结果也要优于增量式和基于AFD的算法.随着采样率的降低, 增量算法的精度急剧下降, 而两种全局算法再次表现出更一致的性能.当采样间隔为30s时, ST-Matching算法的
为了评估算法的效率, 将算法的运行时间与基于AFD的全局方法进行比较.当采样点数目较少时, 两种方法表现出相似的运行时间; 然而随着采样点的增加, 基于ADF的方法的运行时间急剧增加.
实验结果表明:ST-Matching算法在低采样轨迹的匹配精度方面显著优于增量算法; 而且, 与基于AFD的全局匹配算法相比, ST-Matching还提高了匹配精度和运行时间.
● IVVM算法
IVMM算法在匹配质量和效率方面与ST-Matching算法进行比较.为了评估算法的效率, 实验比较了运行时间, 结果表明:对于低采样率和高采样率数据, IVMM算法与ST-Matching算法一样快, IVMM甚至更好一些; 而且随着采样间隔的增加, 要匹配的采样点数量相应地减少, 使得两种算法的时间成本都快速降低.
匹配结果显示, IVMM算法在所有采样间隔中都显著优于ST-Matching算法.回顾北京实际出租车GPS数据的统计结果(如
● HMMM算法
实验结果表明:当采样间隔在10s以内时, 几乎不会产生错误; 当采样间隔增长到30s时, 误差只有0.11%.随着采样率间隔的不断增加, 错误率上升, 采样间隔2min的误差为10%;当采样间隔达5min以上时, 误差超过50%.
● Simplified HMM算法
从实验结果可以看出, Simplified HMM算法与HMMM性能相似.当采样间隔为90s时, RMF为0.2;当采样间隔上升至180s时, RMF为0.6;当采样增加至480s时, RMF为1.1, 然后出现少许下降.采样间隔增加, 采样点的数量也随之降低, 算法的正确率逐渐下降, RMF逐渐上升.与HMMM算法相比, RMF略大, 但效率较高, 约为前者的2倍.
Simplified HMM算法在采样率较低的情况下, 准确率较高, 实现较为简单, 而且匹配速度较快.这是因为Simplified HMM算法中没有搜索候选路段的过程, 所以不需要计算GPS点到道路上的投影, 而且状态转移概率公式较为简单.
● OHMM算法
除了大于4min的采样间隔外, 农村路线的准确性比城市路线的准确度高出大约5%.采样间隔不超过1min时, 农村路线和城市路线的精度均在0.9之上.在这两种情况下, 精度都随着采样间隔的增加而下降.研究结果表明:当操作实时输入流时, OHMM算法以较低的输出延迟实现了最优或接近最优的匹配结果.
● QMM算法
应用ACM SIGSPATIAL Cup竞赛数据测试, 不匹配率保持在2%以内, 波动不大.利用美国华盛顿州道路网的1 283 539个路段来测试多线程技术的应用.假设把使用一个线程进行匹配需要的时间设置为100%, 则2个线程匹配时间为65%, 4个线程匹配时间为43%.而当使用4个线程时, 程序仅需要0.37s来构建网格索引.结果表明:对原始隐马尔可夫模型映射匹配算法的修改, 纠正了一些特殊的不匹配情况.当多核CPU的资源被充分利用时, 索引构建时间和路网匹配时间都大为减少.
大多数现有的增量/在线算法、轨迹具有太多点的全局算法, 往往使用滑动窗口策略.滑动窗口方法简单地将轨迹划分为固定大小的输入序列, 并且独立地处理它们.
文献[
文献[
基于隐马尔可夫模型路网匹配算法在实际应用中可能会出现中断的情况, 从一个时间点到下一个时间点的所有转移概率为0.导致中断的原因如下.
● 路线本地化.在选择某个GPS点的候选路段时, 为了避免不合理的计算量, 一般会忽略距离GPS点超过一定距离的路段, 而不将它们添加到HMM里面, 这可能会导致在特定时间中没有匹配候选.当车辆在未标记在地图上的道路上行驶时, 或者经历特别高的噪声时(比如当车辆进入隧道或城市峡谷时), 可能出现这种情况.
● 低概率路线.当路线变得迂回时, 对于该路线上的任何两个采样点之间的最短路径距离可能远大于它们之间的欧式距离.在这种情况下, 对应于该路线的转移概率将变得非常小, 这将触发HMM中断.
● GPS离群值.作为HMM状态之间转换计算的任何路线都要做合理性测试:如果计算出的路线需要车辆以超过50m/s的速度, 或者以超过3倍限制的速度行驶, 就认为路线是不合理的, 并将其概率设置为0.
由于上述的简化限制了将被考虑的匹配候选路线的数量, 可能会找不到通过HMM的完整路径, 这就是HMM中断.HMM中断发生的频率越高, 匹配算法的效率就越低.
文献[
GPS轨迹进行路网匹配是轨迹挖掘的基础, 而GPS数据规模和数据质量都对路网匹配算法提出了挑战.下一步考虑在这两个方面进行的研究工作.
配有GPS设备的车辆会产生海量数据.比如北京市具有约6万余辆出租车, 一天的时间就能产生上亿条GPS数据, 更不用提产生更多数据的车牌识别、交通视频监控等.当前, 与交通有关的数据跃升到PB级别.这种情况下, 再使用传统交通流方法来对数据进行处理与分析, 效果不甚理想.
另外, 交通轨迹数据在空间和时间上呈现某种特性, 如果能够充分利用时空特点, 可以关联更多的异构数据, 从而实现更加准确的分析, 但是相应地也增大了数据分析的维度, 对数据查询和处理提出了更高的要求.尤其在轨迹数据规模较大的情况下, 计算效率变得更加重要.
日趋成熟的Hadoop, Spark等分布式计算平台能够高效地支持大规模数据的分析与建模问题.合理的分布式策略可以线性地提高交通计算的速度.如, Map-Reduce就是一个性能很高的批处理分布式计算框架.它能够并行处理海量轨迹数据, 可以利用集群的计算能力来提高轨迹数据处理的效率.应海量数据处理需求发展起来的云计算等新兴综合应用, 可以帮助路网匹配算法降低海量数据处理的难度、节约成本、提高处理效率.
此外, 对时空数据做索引, 支持快速存取, 可以缩小定位范围, 减少候选路段数量, 从而极大地缩短了GPS数据匹配时间, 可以更高效、更精确地确定候选匹配路段, 提高路网匹配的实时性和准确性.时空数据索引依赖于空间数据库索引技术, 如网格索引、R-tree、K-D Tree、Quadtree等.
GPS设备精度和测量误差会严重影响路网匹配的准确率.可以考虑使用GPS信息对车辆所处的道路情况进行预判, 从而根据不同的道路场景选择相应的路网匹配算法来提高路网匹配的实时性和准确性.
● 首先, 可以使用机器学习和计算机视觉的方法来提取路边的街道、街景、交通标志等细节信息, 从而建立GPS信息之外的新数据层, 这样能够在很大程度上帮助路网匹配算法提高准确率.比如, 路牌信息可以更好地起到指针作用, 如果驾驶者在听到导航指示的时候能够匹配所看到的街景, 比如车辆所在街道旁边的企业、单位或是商铺的招牌等信息也可以帮助车辆更快、更准地定位; 路边的停止标记、地上的车道或者转弯限制等交通标志信息虽然很难捕捉, 但是可以帮助提高匹配的效率和质量.
● 其次, 智能手机传感器能感受到不同的道路特性[
● 最后, 普通用户也可以参与到标记道路语义信息的工作中来, 比如获取公园、步行道以及其他街景车无法进入的地方的信息, 完善更多精确路线.随着信息不断被开发、路网匹配精度不断提高, 最终呈现出来的将是更为丰富、灵活的交通生活地图.
本文详细调研了国内外轨迹路网匹配技术, 包括全局算法和局部算法.很多算法只适合于高采样率的轨迹, 不适合于低采样率的轨迹, 而基于隐马尔可夫的算法成为主流, 因此, 本文详细综述了基于隐马尔可夫模型的路网匹配算法, 分析了各种不同算法的优势和不足, 最后给出了研究挑战和趋势.
10.1007/978-3-540-73540-3_25]]]>
Yuan YF, Van LH, Van WF, Hoogendoorn S. Network-Wide traffic state estimation using loop detector and floating car data. Journal of Intelligent Transportation Systems, 2014, 18(1):41-50.[doi:10.1080/15472450.2013.773225]
Yuan NJ, Zheng Y, Xie X, Wang YZ, Zheng K, Xiong H. Discovering urban functional zones using latent activity trajectories. IEEE Trans. on Knowledge and Data, 2015, 27(3):712-725.[doi:10.1109/TKDE.2014.2345405]
10.1109/MDM.2008.20]]]>
Pfoser D, Jensen CS. Capturing the uncertainty of moving-object representations. Lecture Notes in Computer Science, 1999, 1651:111-131.[doi:10.1007/3-540-48482-5_9]
10.1109/ITSC.2001.948625]]]>
10.1109/VNIS.1993.585667]]]>
10.1007/978-3-319-18032-8_27]]]>
Alvarez-Garcia JA, Ortega JA, Gonzalez-Abril L, Velasco F. Trip destination prediction based on past GPS log using a hidden Markov model. Expert Systems with Applications, 2010, 37(12):8166-8171.[doi:10.1016/j.eswa.2010.05.070]
Mori U, Mendiburu A, Álvarez M, Lozano JA. A review of travel time estimation and forecasting for advanced traveler information systems. Transportmetrica A:Transport Science, 2015, 11(2):119-157.[doi:10.1080/23249935.2014.932469]
Krumm J. A Markov model for driver turn prediction. SAE World Congress, 2008, 22(1):1-25.
Kuehne RRP, Scbiifert J, Mikat KV, Tbiessenbusent V, Lorkowski BS. New approaches for traffic management in metropolitan areas. In: Proc. of the 10th IFAC Symp. on Control in Transportation Systems. 2003. 209-214.
Lü L, Chen M, Liu Y, Yu XH. A plane moving average algorithm for short-term traffic flow prediction. In: Proc. of the Advances in Knowledge Discovery and Data Mining. 2015. 357-369.
Pang LX, Chawla S, Liu W, Zheng Y. On detection of emerging anomalous traffic patterns using GPS data. Data and Knowledge Engineering, 2013, 87(9):357-373.[doi:10.1016/j.datak.2013.05.002]
10.1145/2370216.2370423]]]>
10.1145/2487575.2487576]]]>
Gonzalez H, Han J, Li X, Myslinska M, Sondag JP. Adaptive fastest path computation on a road network: A traffic mining approach. In: Proc. of the VLDB. 2007. 794-805.
Wei LY, Zheng Y, Peng WC. Constructing popular routes from uncertain trajectories. In: Proc. of the SIGKDD. 2012. 195-203.
Yuan J, Zheng Y, Xie X, Sun GZ. T-Drive:Enhancing driving directions with taxi drivers' intelligence. IEEE Trans. on Knowledge and Data Engineering, 2013, 26(1):220-232.[doi:10.1109/TKDE.2011.200]
10.1007/978-3-540-39653-6_6]]]>
10.1145/585147.585172]]]>
10.1109/ITSC.2009.5309869]]]>
Mohammed AQ, Robert BN, Washington YO. A high accuracy fuzzy logic based map matching algorithm for road transport. Journal of Intelligent Transportation Systems, 2006, 10(3):103-115.[doi:10.1080/15472450600793560]
Yuan NJ, Zheng Y, Xie X, Wang YZ, Zheng K, Xiong H. Discovering urban functional zones using latent activity trajectories. IEEE Trans. on Knowledge and Data Engineering, 2015, 27(3):712-725.[doi:10.1109/TKDE.2014.2345405]
10.1145/2623330.2623653]]]>
Bernstein D, Kornhauser A. An introduction to map matching for personal navigation assistants. Geometric Distributions, 1996, 122(7):1082-1083.
White CE, Bemstein D, Komhauser AL. Some map matching algorithrns for personal navigation assistants. Transportation Research Part C:Emerging Technologies, 2000, 8(1):91-108.[doi:10.1016/S0968-090X(00)00026-7]
Taylor G, Blewitt G, Steup D, Corbett S, Car A. Road reduction filtering for GPS-GIS navigation. Trans. in GIS, 2001, 5(3):193-207.[doi:10.1111/1467-9671.00077]
Alt H, Efrat A, Rote G, Wenk C. Matching planar maps. Journal of Algorithms, 2003, 49(2):262-283.[doi:10.1016/S0196-6774(03)00085-3]
Quddus MA, Ochieng WY, Zhao L, Noland RB. A general map matching algorithm for transport telematics applications. GPS Solutions, 2003, 7(3):157-167.[doi:10.1007/s10291-003-0069-z]
Abbour M, Bonnifait P, Cherfaoui V. Map matching integrity using multi-sensor fusion and multi-hypothesis road tracking. Joumal of Intelligent Transportation Systems Technology Planllingand Operations, 2008, 6(4):189-201.
Nadine S, Kay WA. Map matching of GPS traces on high-resolution navigation networks using the multiple hypothesis techniique (MHT). Woking Paper Transport and Spatial Planning, 2009, (10):568-588.
Ochieng WY, Quddus M, Noland RB. Map-Matching in complex urban road networks. Revista Brasileira De Cartografia, 2003, 55(2):1-14.
Quddus MA, Noland RB, Ochieng WY. Validation of map matching algorithm using high precision positioning with GPS. Journal of Navigation, 2004, 58(2):257-271.[doi:10.1017/S0373463305003231]
Kim S, Kim J. Adaptive fuzzy-network based C-measure map-matching algorithm for car navigation system. IEEE Trans. on Industrial Electronics, 2001, 48(2):432-440.[doi:10.1109/41.915423]
Syed S, Cannon ME. Fuzzy logic-based map-matching algorithm for vehicle navigation system in urban canyons. In: Proc. of the Ion National Technical Meeting. 2004. 982-993.
10.1109/WCICA.2008.4593639]]]>
10.1109/ICCIAS.2006.294272]]]>
Zhang L, Liu JW, Wang RC, Wang HY. Trust evaluation model based on improved D-S evidence theory. Journal on Communications, 2013, 34(7):167-173(in Chinese with English abstract).
张琳, 刘婧文, 王汝传, 王海艳.基于改进D-S证据理论的信任评估模型.通信学报, 2013, 34(7):167-173.
El Najjar ME, Bonnifait P. A road-matching method for precise vehicle localization using belief theory and kalman filtering. Autonomous Robots, 2005, 19(2):173-191.[doi:10.1007/s10514-005-0609-1]
Nassreddine G, Abdallah F, Denoeux T. Map matching algorithm using belief function theory. In: Proc. of the IF. 2008. 1-8.
Yang D, Cai B, Yuan Y. An improved map-matching algorithm used in vehicle navigation system. Intelligent Transportation Systems, 2003, 11(2):1246-1250.[doi:10.1109/ITSC.2003.1252683]
Obradovic D, Lenz H, Schupfner M. Fusion of map and sensor data in a modern car navigation system. Journal of Signal Processing Systems, 2006, 45(1):111-122.[doi:10.1007/s11265-006-9775-4]
Xu H, Liu HC, Tan CW, Bao Y. Development and application of an enhanced kalman filter and global positioning system error-correction approach for improved map matching. Journal of Intelligent Transportation Systems:Technology, Planning and 0perations, 20l0, 14(1):27-36.[doi:10.1080/15472450903386013]
10.1109/PLANS.2000.838299]]]>
10.1109/ITSC.2005.1520086]]]>
10.1109/ITSC.2001.948623]]]>
Cherif S, El-Najjar ME, François C. A road matching method for precise vehicle localization using hybrid Bayesian network. Intelligent Transportation Systems, 2008, 12(4):176-188.[doi:10.1080/15472450802448153]
10.1109/SSDM.2004.1311248]]]>
Blazquez C, Vonderohe A. Simple map-matching algorithm applied to intelligent winter maintenance vehicle data. Journal of the Transportation Research Board, 2005, 1935(1):68-76.[doi:10.3141/1935-08]
Brakatsoulas S, Pfoser D, Salas R, Wenk C. On map-matching vehicle tracking data. In: Proc. of the VLDB. 2005. 853-864.
Honey SK, Zavoli WB, Milnes KA, Phillips AC, Jr White MS, Jr Loughmiller GE. Vehicle navigational system and method: US. US4796191, 1989.
10.1109/ITSC.2008.4732697]]]>
Bierlaire M, Chen J, Newman J. A probabilistic map matching method for smartphone GPS data. Transportation Research Part C:Emerging Technologies, 2013, 26(1):78-98.[doi:10.1016/j.trc.2012.08.001]
Zhang ZH, Cui TJ, Yao HM. New map matching calculation method in vehicle navigation system. Hydrog-raphic Surveying and Charting, 2006, 26(2):55-58(in Chinese with English abstract).
张振辉, 崔铁军, 姚慧敏.车辆导航系统中地图匹配新算法.海洋测绘, 2006, 26(2):55-58.
10.1145/1653771.1653818]]]>
https://trid.trb.org/Results?q=&serial=%22Transportation%20Research%20Board%2081st%20Annual%20Meeting%22]]>
10.1109/SSDBM.2006.11]]]>
10.1109/IVS.2007.4290280]]]>
Lou Y, Zhang C, Zheng Y, Wang W, Huang Y. Map-Matching for low-sampling-rate GPS trajectories. In: Proc. of the ACM-GIS. 2009. 352-361.
10.1109/MDM.2010.14]]]>
Giovannini L. A novel map-matching procedure for low-sampling GPS data with applications to traffic flow analysis[Ph. D. Thesis]. Universita Di Bologna, 2011.
Zheng K, Zheng Y, Xie X, Zhou XF. Reducing uncertainty of low sampling rate trajectories. In: Proc. of the ICDE. 2012. 1144-1155.
Civilis A, Jensen CS, Pakalnis S. Techniques for efficient road-network based tracking of moving objects. IEEE Trans. on Knowledge and Date Engineering, 2005, 17(5):698-712.[doi:10.1109/TKDE.2005.80]
Thiagarajan A, Ravindranath L, Lacurts K, Madden S, Balakrishnanet H, Toledo S, Eriksson J. VTrack: Accurate, energy-aware road traffic delay estimation using mobile phones. In: Proc. of the Sensys. 2009. 85-98.
Thiagarajan A, Ravindranath L, Balakrishnan H, Madden S, Girod L. Accurate, low-energy trajectory mapping for mobile devices. In: Proc. of the USENIX. 2011. 267-280.
10.1109/INFCOM.2013.6567082]]]>
10.1145/1869983.1869988]]]>
10.1145/2820783.2820824]]]>
10.1145/2666310.2666429]]]>
Mohamed R, Aly H, Youssef M. Accurate real-time map matching for challenging environments. IEEE Trans. on Intelligent Transportation Systems, 2017, 18(4):847-857.[doi:10.1109/TITS.2016.2591958]
10.1145/2525314.2525338]]]>
10.1109/WCNC.2012.6214359]]]>
10.1109/GLOCOM.2010.5683779]]]>
Ibrahim M, Youssef M. A hidden Markov model for localization using low-end GSM cell phones. Proc. of the ICC, 2011, 47(10):1-5.[doi:10.1109/icc.2011.5962993]
Ibrahim M, Youssef M. CellSense:An accurate energy-efficient GSM positioning system. IEEE Trans. on Vehicular Technology, 2011, 61(1):286-296.[doi:10.1109/TVT.2011.2173771]
10.1109/SAHCN.2014.6990394]]]>
10.1109/ITSC.2012.6338627]]]>
Rohani M, Gingras D, Gruyer D. A novel approach for improved vehicular positioning using cooperative map matching and dynamic base station DGPS concept. IEEE Trans. on Intelligent Transportation Systems, 2015, 17(1):1-10.[doi:10.1109/TITS. 2015.2465141]
Pereira FC, Costa H, Pereira NM. An off-line map-matching algorithm for incomplete map databases. European Transport Research Review, 2009, 1(3):107-124.[doi:10.1007/s12544-009-0013-6]
Miwa T, Kiuchi D, Yamamoto T, Morikawaet T. Development of map matching algorithm for low frequency probe data. Transportation Research Part C:Emerging Technologies, 2012, 22(5):132-145.[doi:10.1016/j.trc.2012.01.005]
Raymond R, Morimura T, Osogami T, Hirosue N. Map matching with hidden Markov model on sampled road network. In: Proc. of the ICPR. 2012. 2242-2245.
Baum LE. Statistical inference for probabilistic functions of finite state Markov chains. Annals of Mathematical Statistics, 1966, 37(6):1554-1563.[doi:10.1214/aoms/1177699147]
Baum LE, Eagon JA. An inequality with applications to statistical estimation for probabilistic functions of Markov processes and to a model for ecology. Bulletin of the American Mathematical Society, 1967, 73(3):360-363.[doi:10.1090/S0002-9904-1967-11751-8]
Baum LE, Sell GR. Growth transformation for functions on manifolds. Pacific Journal of Mathematics, 1968, 27(2):211-227.[doi:10.2140/pjm.1968.27.211]
Lamb P, Thiebaux S. Avoiding explicit map-matching in vehicle location. In: Proc. of the ITS. 1999. 8-12.
Hummel B. Map matching for vehicle guidance. In: Dynamic and Mobile GIS: Investigating Changes in Space and Time. Boca Raton: Taylor & Francis, 2006.
10.4271/2007-01-1102]]]>
Gather U, Schultze V. Robust estimation of scale of an exponential distribution. Statistica Neerlandica, 1999, 53(53):327-341.[doi:10.1111/1467-9574.00115]
Wang Y, Zhu Y, He Z, Yue Y, Li Q. Challenges and opportunities in exploiting large-scale GPS probe dat. HP Laboratories, Technical Report, HPL-2011-109, 2011.
10.1109/ICASSP.2008.4518061]]]>
Šrámek R, Brejová B, Vinař T. On-Line viterbi algorithm and its relationship to random walks. arXiv: 0704. 0062v1, 2007.
10.1145/2424321.2424428]]]>
Wu G, Qiu YJ, Wang GR. Map matching algorithm based on hidden Markov model and genetic algorithm. Journal of Northeastern University (Natural Science), 2017, 38(4):472-475(in Chinese with English abstract).
吴刚, 邱煜晶, 王国仁.基于隐马尔可夫模型和遗传算法的地图匹配算法.东北大学学报(自然科学版), 2017, 38(4):472-475.
George RJ, Thambipillai S. Online map-matching of noisy and sparse location data with hidden Markov and route choice models. IEEE Trans. on Intelligent Transportation Systems, 2017, 18(9):2423-2434.[doi:10.1109/TITS.2017.2647967]
Essam A, Tetsuji O, Ahmed E. Real-Time large-scale map matching using mobile phone data. ACM Trans. on Knowledge Discovery from Data, 2017, 11(4):1-38.[doi:10.1145/3046945]
Zheng Y, Chen Y, Xie X, Ma W. GeoLife2. 0: A location-based social networking service. In: Proc. of the MDM. 2009. 357-358.
Zheng Y, Liu L, Wang L, Xie X. Learning transportation mode from raw GPS data for geographic applications on the Web. In: Proc. of the WWW. 2008. 247-256.
10.1145/1378600.1378605]]]>
10.1109/DCOSS.2011.5982206]]]>
10.1145/1460412.1460444]]]>