2018, Vol. 29
2. 清华大学 计算机科学与技术系, 北京 100084;
3. 中国人民大学 新闻学院, 北京 100872
2. Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China;
3. School of Journalism and Communication, Renmin University of China, Beijing 100872, China
近几年来, 中国在线出行服务行业发展迅速, 服务模式从“线下重资产+线上服务”转为“互联网+共享经济/轻资产重服务”, 服务场景从电脑端转向移动端.自2012年起, 移动端出行服务模式大量涌现, 包括出租车、拼车、专车(快车)、租车、代驾、定制巴士等.截止到2015年年底, 移动端出行服务用户数量接近4亿, 其中, 出租车用户达到2.5亿, 拼车用户达到1.6亿, 专车(快车)用户达到1.9亿.2016年, 滴滴出行全平台订单数量达到14.3亿, 这相当于美国2015全年订单量的近2倍(http://www.aiweibang.com/yuedu/100330112.html).
这些出行车辆装配的GPS(global positioning system, 全球定位系统)设备每天能够收集到大量的移动位置序列和车载状态信息, 这些数据蕴含着丰富的交通信息和用户行为, 可以实时地了解路网上乘客需求的时空变化以及乘客出行的有关信息.通过使用大数据处理技术, 分析车辆轨迹数据和乘客需求数据, 挖掘出对乘客打车和司机载客有帮助的价值信息, 能够对乘客的出行提供有效的指导.同时, 从一定程度上反映出城市交通状况和人群流动情况, 便于了解交通流量规律, 发现人群行为特征, 协助改善交通状况等, 具有极大的科研和应用价值.
另外, 随着基于位置服务(location-based service)和移动社交网络(mobile social network)的发展和普及, 越来越多的应用, 如热路线查找[1]、交通监管[2]、城市规划[3]、地理社会网络[4], 已经开始使用来自GPS的数据信息, 以实现更好的服务质量.但是, 由于GPS传感器的读数有定位误差和采样误差[5], GPS跟踪数据与实际轨迹之间的偏差是不可避免的.如果不进行路网匹配, 那么交通工具可能不会正确显示到道路上, 如图 1所示.
|
Fig. 1 GPS device positioning illustration 图 1 GPS设备定位示例 |
在图 1中, 实心点是GPS设备定位到的位置信息, 可以看出, GPS点离最近的路有一段距离, 如果不做处理, 这个点就直接定位到建筑、湖泊中, 而不显示到路网上.最终得到的车辆行驶路线将不沿着正常道路, 而会直接穿越地铁、房屋、草坪等, 显然, 这是不合理的.所以需要对由GPS设备获得的定位信息进行一定的处理, 使它能够较为精确地匹配到路网上.
将所观察到的用户或者交通工具的GPS位置关联到给定电子地图的道路网络上的过程称为路网匹配.路网匹配对于许多基于位置的应用程序是一个基本的数据预处理步骤(如图 2所示), 只有处理好这一步, 以后的研究才能有效地进行.其主要目的是识别用户(或车辆)正在/曾经行驶的真实路段, 进行车辆导航[6, 7]、位置预测[8, 9]、路线或行程预测[10, 11]、交通状况预测与管理[12-14]、轨迹深度理解[15, 16]、路径规划与推荐[17-19]、活动识别[20]和许多其他基于位置的服务[21-23], 同时, 可以加入其他数据(如气象数据、环境数据等)来进行城市计算[24, 25], 向社会提供广泛的服务.由于大多数的民用GPS设备和智能手机中的GPS模块价格便宜但精度不高, 这就需要一种可靠且健壮的基于位置信息的路网匹配算法来提高GPS数据的准确性.
|
Fig. 2 Paradigm of trajectory data mining 图 2 轨迹数据挖掘示意图 |
1 轨迹路网匹配问题描述
路网匹配是一个将原始的经纬度坐标转换成一个序列的处理过程, 其涉及到的概念和定义如下.
定义1(GPS日志). 一个GPS日志是一系列GPS点的集合L={p1, p2, …, pn}.每个GPS点包含纬度、经度和时间戳信息, 如图 3(a)所示.
|
Fig. 3 Illustration of GPS log and GPS trajectory 图 3 GPS日志和轨迹的示意图 |
定义2(GPS轨迹). 一条GPS轨迹T是一个GPS点的序列, 任意连续的GPS点之间不超过一定的阈值ΔT, T:p1→p2→…→pn, 其中, pi∈L, 0 < pi+1.t-pi.t < ΔT(1≤i < n), ΔT是采样间隔.如图 3(b)所示.
定义3(路段). 一个路段e是一条有向边, 具有编号e.id、行驶速度e.v、长度e.l、开始点e.start、结束点e.end和中间点列表.一条道路可以包含多个路段, 如图 4所示.
|
Fig. 4 Illustration of a path in a road network 图 4 路网中的一条路径示意图 |
定义4(路网). 路网是一个有向图G(V, E), 其中, V是顶点集合, 代表路口或道路中的转折点; E是一系列有向边, 代表路网中的路段.
定义5(路径). 给定路网G中的两个顶点vi, vj, 一条路径P是始于vi止于vj的一组连接的路段.P:e1→ e2→…→en, 其中, e1.start=vi, en.end=vj, ek.end=ek+1.start, 1≤k < n.
路网匹配问题可以描述为, 给定未加工的GPS轨迹T和路网G(V, E), 从G中寻找路径P, 其实际路径匹配轨迹T.路网匹配的一般流程如图 5所示.
|
Fig. 5 Paradigm of map matching 图 5 路网匹配的流程图 |
直观来讲, 解决路网匹配最简单的方法就是将GPS点关联到最近的路段上, 但有些时候效果会非常差, 如图 6所示:假如有3个连续的点, 第1个点和第3个点都在一条路上, 而第2个点由于误差, 会被定位到另外一条无关的路上, 但却是最近的.尤其是在采样频率较低、定位误差较大、信号易丢失的实际情况下, 如何保持较高的路网匹配准确率, 仍是当前研究的重点问题.目前, 国内外学者提出了很多路网匹配算法来处理这个问题.
|
Fig. 6 GPS point matched to the nearest road segment 图 6 GPS点关联到最近的路段 |
2 轨迹路网匹配算法分类
根据算法的不同特性, 现有的路网匹配算法可以有下列分类标准.
2.1 以数据涉及的信息来划分根据输入数据所涉及的信息, 现有的路网匹配算法可被分成4类, 见表 1.
|
Table 1 Algorithm classification by data involved in the information 表 1 以数据涉及信息进行算法分类 |
2.1.1 基于几何信息的匹配算法
基于几何信息的匹配算法是由Bemstein等人在20世纪90年代提出来的.它仅利用时空道路网络的几何信息进行匹配, 如距离、角度、形状等, 而不考虑路段间的连通性[26].
基于几何信息的匹配算法相对简单, 易于实现, 在定位系统没有较大误差的情况下匹配度较高, 但是它们没有使用GPS采集点之间的联系、交通规则信息和道路的拓扑信息等, 导致准确率下降; 而且一旦出现错误匹配无法及时修正, 稳定性较差.虽然它们可以为密集的GPS轨迹提供良好的匹配, 但如果是针对有噪声且稀疏的数据就不再适用.
2.1.2 基于拓扑信息的匹配算法拓扑信息是指实体(点、线、多边形)之间的相连(线)、邻接(多边形)、包围(多边形与点)等关系.基于拓扑信息的匹配算法[49, 50]关注路网的连通性, 运用历史数据、车辆速度和道路拓扑特征等额外信息来限制采样点的候选匹配.代表性的算法[51]使用弗雷歇距离(Fréchet distance)来衡量GPS序列和候选路段序列的匹配度, 处理具有噪声和低采样率的轨迹.算法[30]使用道路网络的几何形状和GPS导航数据之间的各种相似性标准(如车辆速度、封闭性)将用户轨迹映射到道路网络上.
基于拓扑信息的路网匹配算法不仅要考虑GPS采集点与道路的距离, 而且要考虑路网的拓扑连通性以及历史采集点, 从而使匹配效率和准确性在一定程度上有所提高.但它们仍然容易受到采集噪声和数据稀疏性的影响, 还不能完全解决复杂的城市道路问题.
2.1.3 基于概率信息的匹配算法Honey等人在1989年首先将概率统计方法运用在路网匹配算法中[52].该算法在汽车动态运动过程中, 利用计算机来估计车辆的行驶方向以及位置距离, 然后使用航位推测法来推测汽车所在的路段.基于概率信息的匹配算法[23, 33, 53, 54]给每个GPS样本点设定一个椭圆或矩形的置信区域, 并根据GPS的点和在置信区域内的位置之间的距离获得概率值, 根据概率值的大小来决定最佳匹配路径.
基于概率信息算法不要求车辆总是在道路上.如果车辆接收到的GPS数据偏离了已知的路网, 算法将会不断地比较接收到的GPS坐标与偏离路段的坐标, 并识别与车辆匹配的路段[55].但是大多数基于概率信息算法都涉及公式推导, 不容易理解, 实现起来比较困难; 而且算法计算开销较大, 匹配准确性很低, 满足不了实时性和大众对GPS系统的要求.
2.1.4 高级路网匹配算法高级路网匹配算法往往综合考虑全面信息, 包括最近出现的道路网络的拓扑结构和轨迹数据中的噪音; 使用更精致的概念, 如卡尔曼滤波[43]、模糊逻辑模型[23]、隐式马尔可夫模型[53, 56]等.由于采用了先进的技术手段, 这些高级路网匹配算法的准确率普遍较高.尤其是在空旷的道路, 比如郊区、农村等.在城市道路上效果也不错, 但受复杂路网、采样率等因素影响较大.当采样率较低时, 这些算法仍然表现不佳, 当采样间隔超过5min时, 错误率超过50%[56].
2.2 以考虑采样点的范围来划分根据匹配轨迹时考虑采样点的范围, 路网匹配算法可以分为两类:局部/增量和全局方法.具体见表 2.
|
|
Table 2 Algorithm classification by range of sampling points 表 2 以考虑采样点的范围进行算法分类 |
2.2.1 局部/增量路网匹配算法
局部/增量算法利用当前GPS轨迹点的局部特征来进行路网匹配.算法使用贪心策略, 从已经匹配好的解决方案中依次延伸得到最终的全局解.文献[57]根据GPS轨迹点与路段的几何距离、行车方向以及前后时刻路径可达性等因素来综合判断匹配结果.文献[53, 64]则进一步考虑了在拓扑规则约束和交通规则约束下的路段连通性, 匹配结果更为可靠.
局部/增量算法计算速度快、实时性强, 所以经常用于有在线需求的应用.当采样速率较高时(比如2s~5s), 能够获得良好的匹配效果.但随着采样率的降低, 局部/增量算法将呈现“弧跳”现象[57], 造成精度的显著降低.由于只考虑当前位置, 相邻点的相关性被完全忽略, 结果受到测量误差影响很大.因此, 局部/增量算法的准确性普遍较低.
2.2.2 全局路网匹配算法全局算法考虑整个采样轨迹, 从路网中找到一条与其最接近的匹配路径.大多数全局路网匹配算法[49, 51]使用“弗雷歇距离”或其变体来测量采样轨迹和匹配路径的相似度.“弗雷歇距离”考虑了曲线的连续性, 因此适用于比较轨迹.两曲线之间的“弗雷歇距离”由文献[59]提出, 文献[29]给出了一种计算方法.文献[56, 60, 62, 63]则同时考虑多个相邻时刻GPS轨迹点的位置信息, 将路网匹配问题转化为给定目标函数的优化求解问题, 其最优解即对应路网匹配的结果.
与局部/增量算法相比, 全局算法更准确, 对采样率降低表现出更大的健壮性, 能够较好地处理长采样间隔情况下的路网匹配问题, 但计算成本较高.由于缺乏真实的车辆和道路实验, 使得它难以评估实际的匹配精度.此外, 目前的全局匹配算法只采用空间分析, 而忽略了轨迹的时间/速度约束, 这使它们也容易受到采样率下降的影响.由于全局算法需要整个行驶轨迹的信息, 所以通常适用于离线任务(例如在所有轨迹产生后, 挖掘频繁的轨迹模式).
2.3 以采样的频率来划分如表 3所示, 现有的路网匹配算法根据GPS数据的采样密度可分为高频采样算法、低频采样算法和更低频率采样算法.
|
|
Table 3 Algorithm classification by sampling rate 表 3 以采样的频率进行算法分类 |
2.3.1 高频采样算法
GPS样本点的采样频率影响着算法的匹配精确度, 当GPS采样频率较高时(一般是1s~10s), 即使仅将轨迹点匹配至最近的道路片段, 也可得到较高的正确率.高采样率轨迹的路网匹配技术已经被商业化为个人导航设备.几乎上述所有的路网匹配算法都是基于高样本率数据集的.
然而, 高采样率的数据集的采集和存储需要消耗更多的存储空间、GPS模块的操作和计算时间.基于节约能源以及浮动车本身特性等原因, 在实际应用中, 返回给调度中心的数据往往是低采样率的(1min~2min采样一次, 甚至更低).
2.3.2 低频采样算法在实际中, 存在大量的低采样率GPS跟踪数据(采样间隔超过1min).例如, 为了节省通信和能源成本, 出租车通常以较低的频率向调度中心报告GPS位置.文献[61]给出了10000+北京出租车1周产生的GPS轨迹的采样间隔的统计分布, 如图 7所示.可以指出, 只有34%的数据是高采样率(采样间隔小于1min)的数据, 超过60%的数据是低采样率数据.数据集的平均时间间隔为3.27min.
在这种情况下, 基于高样本率的路网匹配算法无法适用于低样本率的数据集.针对此问题, 研究人员已经提出了一些基于低采样率的数据集的路网匹配算法, 如ST-Matching[60], IVVM[61]等, 但仍存在着一些误计算.由IVVM[61]的实验结果可见:给定一个轨迹的采样速率约为2min, 路网匹配算法的最高精度约为70%.低采样率的轨迹处理技术仍然非常具有挑战性.
2.3.3 更低频采样算法上述的路网匹配技术主要用于GPS定位数据, GPS具有全球可用性和较高的精度.然而在许多形况下, 基于粗粒度网络的定位信息是唯一可行的解决方案, 例如从蜂窝提供商处定位, 在需要高效节能定位的情况下[72-76], 应用涉及低端手机没有GPS或其他传感器, 以及人群的遥感应用中GPS通常关闭[77].
因此, 一些新的路网匹配技术开始出现, 利用手机上的其他传感器(如WiFi[65], 具有周围手机信号塔信息的蜂窝指纹[66]和惯性传感器[67, 68])来提高手机定位精度, 加入一些基于道路语义的判断[69], 从而提供更好的路网匹配精度.然而, 它们所使用的传感器仍然具有噪声, 并且功率消耗较高, 导致定位不准确.
现在, 手机使用率非常高, 运营网络也是现成的.如果能够发动手机用户积极参与交通流预测, 则会极大地提高预测的实时性、准确性和覆盖率, 而且投入和维护的成本都比较低.因此, 这种方法非常易于推广普及.但在这种情况下, 传统路网匹配算法的典型假设不成立.手机位置不再接近实际路段, 位置误差是以km计, 改变手机塔关联会有来回转换现象, 且输入位置样本高度稀疏.所以, 亟需一些能够处理更低采样率和定位精度的路网匹配算法.
2.4 以计算的实时性来划分路网匹配算法可以分为实时和离线算法:实时算法将记录过程中的位置与道路网络联系起来; 离线算法在数据被记录后使用, 将数据匹配到道路网络.
在实时应用中, 如交通感知, 希望进行路网匹配, 而未来的数据尚不可知, 这就要求算法必须在线.实时应用程序只能基于给定时间前的点计算(而不是一个完整的旅程), 意在现实生活环境中使用.上文介绍的增量算法[30, 78, 79]采用本地化的战略, 将输入轨迹划分成较小的部分按顺序处理, 适合在线匹配, 但是有时会导致一个次优的解决方案.这就需要在性能和精度之间取得平衡.一个可靠的在线路网匹配算法要充分考虑到这些问题, 并保证输出的准确性和及时性.
而离线应用可以考虑所有的点, 所以可以容忍较慢的性能而有利于提高精度.上文介绍的全局算法[49, 80]批量输入轨迹从而生成整个解决方案, 需要整个行驶轨迹的信息, 所以通常适用于离线任务.
目前, 因为要节省能源成本和通信成本以及车辆本身的特性, 输入GPS数据的采样率普遍较低, 两个采样点之间的许多细节很容易被丢失.例如，当采样间隔为2min时, 即使车速为30km/h, 两个采样点之间的距离也可达到1km.特别是在复杂的城市道路网络中, 车速较高、街区较短、误差较大的情况下, 大部分GPS点之间的关联信息将会丢失[81], 从而导致上述绝大多数传统路网匹配方法失效.因为它们只能处理高采样率的GPS数据, 对低采样率的点有效性下降严重.如文献[82]中所述, 当GPS采样间隔大于120s时, 大多数全局算法表现不佳, 平均正确率小于60%.
在近几年的研究中出现了一些基于低采样率的数据集的路网匹配算法, 可以较好地处理这个问题, 比较著名的方法就是基于隐马尔可夫模型(hidden Markov model, 简称HMM)的路网匹配算法, 其结果的正确率在一定条件下最高可以达到90%.下一节将重点介绍基于HMM的路网匹配算法.
3 基于HMM的路网匹配算法 3.1 隐马尔可夫模型20世纪60年代, Baum等人和其他作者在一系列的统计学论文[83-85]中描述了隐马尔可夫模型.它最初的应用之一是语音识别, 80年代成为信号处理的研究重点, 现已成功地用于故障诊断、行为识别、文字识别、自然语言处理以及生物信息等领域.
隐马尔可夫模型主要包含5个要素——2个状态集合和3个概率矩阵(http://baike.baidu.com/).
● 隐含状态S:马尔可夫模型中实际所隐含的状态, 通常无法通过直接观测得到.这些状态之间满足马尔可夫性质.令N代表隐含状态数目.
● 可观测状态O:可以通过直接观测而得到的状态, 在隐马尔可夫模型中与隐含状态相关联.令M代表可观测状态数目.
● 状态转移概率矩阵A:描述隐马尔可夫模型中各个状态之间的转移概率.A=[aij]N×N, 其中, aij=P(qt+1=Sj| qt=Si), 1≤i, j≤N.表示在t时刻状态是Si的条件下, 在t+1时刻状态为Sj的概率.
● 观测状态概率矩阵B:B=[bj(k)]N×M, 其中, bj(k)=P(ot=Ok|qt=Sj), 1≤j≤N, 1≤k≤M.表示在t时刻隐含状态是Sj条件下, 其可观测状态为Ok的概率.
● 初始状态概率矩阵π:π=(πi), πi=P(q1=s1), 1≤i≤N.表示隐含状态在初始时刻t=1的概率矩阵.
3.2 基于隐马尔可夫模型的路网匹配隐马尔可夫模型通过对道路的连通性进行明确建模, 并同时考虑许多不同的路径假设来解决路网匹配问题.最早利用HMM来进行路网匹配的应用来自Lamb等人[86]的工作.他们使用的是卡尔曼滤波器和HMM的组合.几个卡尔曼滤波器沿着不同的假设路径跟踪车辆, HMM在这中间进行选择.来自Hummel[87]和Krumm[88]的著作使用隐马尔可夫模型来平衡测量噪声和路径概率.
隐马尔可夫模型可以解决3类问题.
● 评价:将最可能的系统与观测序列匹配, 使用前向算法(forward algorithm)求解.
● 解码:确定最可能产生观察序列的隐藏序列, 使用维特比算法(Viterbi algorithm)求解.
● 学习:确定模型参数最可能产生的一系列观察, 使用前向-后向算法(forward-backward algorithm)求解.
路网匹配问题实际上是一个解码问题.假设移动对象在路网的交叉点间移动, 且移动的过程符合马尔可夫模型.虽然无法直接观察到移动对象所经过的道路轨迹(可以把这些轨迹看作隐含状态), 但是可以获得隐含状态的输出, 即GPS样本点(假设观测值仅与移动对象的隐含状态相关).于是, 基于HMM的路网匹配算法就变成在给定一系列观察的前提下, 寻找最有可能产生这个观察序列的隐含状态序列, 也就是实际的移动轨迹.这里有两个状态集合.
● 可观测状态集合:从GPS设备中得到的位置信息(经度、纬度).
● 隐含状态集合:拥有GPS设备的物体(车、人等)实际所在的位置.
这样, 就可以把路网匹配问题与隐马尔可夫模型结合起来.然后, 用一定的规则去拟合历史的真实数据得到状态转移概率矩阵A、观测状态转移概率矩阵B以及初始状态概率矩阵π.接下来将详细介绍基于HMM的几种算法, 其中, 定义的规则要满足人的先验知识, 主要有以下3种.
● 观测状态概率.观测的GPS样本点离候选路段越近, 这个样本点在这个路段上的概率就越大.
● 状态转移概率.这里有两种解决思路:
➢ 一是前后两个GPS样本点的距离越近, 状态转移的概率就越大;
➢ 二是真实路段上的前后两个点之间距离与GPS观测的前后两个样本点之间距离越接近, 状态转移概率就越大.
● 初始状态概率.代表移动对象初始时位于某个路段上的概率, 使用相应GPS样本点的观测状态概率来表示.
在基于HMM的路网匹配算法中, 对于每一个GPS轨迹点, 首先确定一组候选路段.每个候选路段被表示为马尔可夫链中的隐藏状态(顶点), 并具有观测状态概率, 这是观察GPS点是否与候选路段匹配的可能性.如果发现GPS点非常接近某个路段, 就给这个路段指定一个较高的概率值.然后, 为马尔可夫链中连接每一对相邻顶点的边计算权重, 即状态转移概率.最终, 在马尔可夫链上找到具有最高观测状态概率和状态转移概率的最大似然路径.一般使用维特比算法(Viterbi algorithm)进行求解, 实际上是用一个动态规划(dynamic programming, 简称DP)算法解隐马尔可夫模型预测问题, 即用动态规划在道路网络中快速找到使观测概率和转移概率的乘积最大化的最优路径.这个过程如图 8所示.
|
Fig. 8 HMM-Based map matching process 图 8 基于隐马尔可夫模型的路网匹配过程 |
图 9用一个简单的例子来说明基于隐马尔可夫模型的路网匹配过程, 观测状态概率和状态转移概率都在图中列出.
|
Fig. 9 An example of HMM-based map matching process 图 9 基于隐马尔可夫模型的路网匹配过程示例 |
从Co点出发, 有3个候选点
|
Fig. 10 Calculation process of HMM-based map matching algorithm 图 10 基于隐马尔可夫模型的路网匹配算法计算过程 |
3.3 基于隐马尔可夫模型的路网匹配算法 3.3.1 ST-Matching算法(spatial temporal matching algorithm)[60]
ST-Matching算法结合时间和空间特征, 包括几何拓扑结构和速度约束.文献[60]使用高斯分布来模拟观测概率转移, 而状态转移概率则是综合了速率信息、GPS观测点和真实点的信息计算出来, 具体公式如下.
● 观测概率矩阵B
| $ {b_j}(k) = P({o_t} = {o_k}|{q_t} = {r_j}) = \frac{1}{{\sqrt {2{\rm{ \mathsf{ π} }}} \sigma }}{{\rm{e}}^{-\frac{{||{o_t}-{r_j}|{|^2}}}{{2{\sigma ^2}}}}} $ | (1) |
一般来说, GPS观测点的测量误差可以被合理地描述为一个GPS观测点和实际路段之间距离的高斯分布. 这里采用的是一个均值μ=0, 标准差σ=20米的高斯分布.
● 状态转移矩阵A
| $ \left. \begin{array}{c} {a_{ij}} = P({q_{t + 1}} = {r_j}|{q_t} = {r_i}) = {F_t}({r_i} \to {r_j}) \cdot V({r_i} \to {r_j})\\ {F_t}({r_i} \to {r_j}) = \frac{{{d_{t \to t + 1}}}}{{{w_{t \to t + 1}}}} = \frac{{||{o_t}-{o_{t + 1}}|{|_{Euclidean\_Distance}}}}{{||{r_i}-{r_j}|{|_{route}}}}\\ V({r_i} \to {r_j}) = \frac{{\sum\nolimits_{u-1}^k {({{e'}_u} \cdot {v_r} \times {{\bar v}_{ij}})} }}{{\sqrt {\sum\nolimits_{u - 1}^k {{{({{e'}_u} \cdot {v_r})}^2}} } \times \sqrt {\sum\nolimits_{u - 1}^k {\bar v_{ij}^2} } }} \end{array} \right\} $ | (2) |
Ft(ri→rj)是空间分析函数, 考虑了道路网络的拓扑结构.根据前后两个时间点t和t+1之间的观测点pi-1, pi及其候选点
V(ri→rj)是时间分析函数, 考虑前后两个时间点之间的速率信息.用余弦距离(cosine distance)来衡量从
算法根据路段投影过程为每个GPS采样点检索一组候选路段和候选点.然后构造一个候选图, 图中的节点是每个GPS观测的候选点集合, 而边是任意两个相邻的候选点之间的最短路径集.节点和边都基于空间/时间分析结果分配了权重值.结合观测和转移概率, 匹配算法在候选图中寻找一条具有最高得分的路径, 最大限度地提高全局匹配概率.
3.3.2 IVMM算法(interactive-voting based map matching algorithm)[61]ST-Matching在匹配路网时, 会把GPS点对应到距离较近的路段上, 并不考虑其相邻点的关系, 所以会出现锯齿形的线路.IVMM的提出, 就是为了“拉直”不匹配的路段, 使其更适合地面真实路径.它在ST-Matching的基础上加入了“互动投票”, 就是说, 每个候选点会对在同一条单点最优的轨迹上的其他候选点进行加强, 即投票, 最后打分最高的点连起来形成匹配路径.
观测概率矩阵(同公式(1))和状态转移矩阵(同公式(2))的计算方法和ST-Matching相同, 只是公式(1)中的取值不同, 这里μ=5m, σ=10m.先选取相邻观测点pi-1, pi和相应的候选节点
IVMM算法从全局角度考虑观测点之间的相关性.所有观测点之间进行相互投票, 完全并行, 这样就不需要进行大量的计算得到可能的匹配结果, 而只需从候选集合中投票产生正确匹配结果, 算法复杂度较小.
3.3.3 HMMM(hidden markov model map matching through noise and sparseness)算法[56]与ST-Matching算法相近, 但没有考虑速率信息.它是用前后两个相邻GPS观测点的距离与两个候选点的距离之差的绝对值来表示这两段距离的接近程度, 越接近, 概率就越大, 且最后的概率是用指数函数来拟合.具体公式如下.
● 状态转移矩阵A
| $ \left. \begin{array}{c} {a_{ij}} = P({q_{t + 1}} = {r_j}|{q_t} = {r_i}) = \frac{1}{\beta }{{\rm{e}}^{\frac{{-{d_t}}}{\beta }}}\\ {d_t} = |||{o_t}-{o_{t + 1}}|{|_{great\_circle}}-||{r_i} - {r_j}|{|_{route}}| \end{array} \right\} $ | (3) |
其中, β选用Gather等人[89]建议的鲁棒性较强的估计值, 见公式(4).
| $ \beta = \frac{1}{{\ln (2)}}media{n_t}(|||{o_t}-{o_{t + 1}}|{|_{great\_circle}}-||{r_i}-{r_j}|{|_{route}}|) $ | (4) |
β较大、大圆距离和候选点之间最短距离越大, 说明对非直线路径越容忍.
● 观测概率矩阵B
与ST-Matching算法相同(见公式(1)), 都是使用均值μ=0高斯分布.但标准差σ是使用绝对中位差(median absolute deviation, 简称MAD)进行鲁棒估计, 见公式(5).
| $ \sigma = 1.4826media{n_t}(||{o_t} - {r_j}|{|_{great\_circle}}) $ | (5) |
其中, ||ot-rj||使用的是观测点和其候选点之间的地球表面上的大圆距离.对于使用的测试数据, 该值为σ=4.07m, 这是GPS噪声的合理值.σ值越大, 噪声就越大, 表示位置测量越不可信.σ和β两个参数需要确定合适值才能使算法性能最高.
● 初始状态概率π
πi=P(p1|ri), 1≤i≤N, 在初始时刻t=1时的观测概率矩阵, 有πi=P(p1|ri), 即使用第1个GPS观测点p1得到ri是所有道路中第1条匹配道路的概率.
状态转移概率依赖于当前状态以及上一个观察状态, 所以不能严格满足维特比算法中对状态转移概率的要求, 从而产生两个问题:一是利用公式(1)得到的近似概率并不一定是其最大似然结果; 二是公式(1)将观测点在道路上的投影作为隐性状态的一部分, 但这个投影并不唯一, 从而增大了最大似然解的寻找难度.文献[81]中的算法简化状态转换概率以适应理想的HMM框架, 避免了这些缺点.
3.3.4 Simplified HMM算法(simplification of the more-complex HMM-based method)[81]上述论文中使用的模型并不是完美的原始的HMM, 因为在计算状态转移概率时, 既要考虑候选点的信息, 也要考虑观测点的信息, 可以说是HMM的一个变种.本文将之前的HMM模型简化, 在计算状态转移概率时不考虑观测点之间的信息, 所以可以看作简化的HMM方法.图 11给出了Simplified HMM算法所采用的模型与HMMM算法模型的对比示意图.
|
Fig. 11 Comparison of HMMs 图 11 HMM模型对比 |
隐性马尔可夫模型包含的3种概率如下.
● 观测概率矩阵B
和之前的算法一样(见公式(1)), 用高斯分布模拟(本文是μ=0, σ=1.0的高斯分布).
● 状态转移矩阵A
车辆从一个道路交叉点转移到另一个交叉点的概率, 对应于图 9中的理想隐性马尔可夫模型中的状态转移.文献[81]中假设状态转移概率跟两个交叉点间的距离成正比, 即
| $ {a_{ij}} = P({q_{t + 1}} = {r_j}|{q_t} = {r_i}) \propto {{\rm{e}}^{-\beta {d_{ij}}}} $ | (6) |
其中, β用于调节两个交叉点间最短距离dij对结果的影响.距离dij可以考虑行驶时间、成本等距离之外的其他因素.
● 初始状态概率π
代表车辆在初始时刻处于某个道路交叉点的概率, 文献[81]中使用相应交叉点的观测概率来表示车辆的初始状态概率.
之前的算法的状态转移概率公式中都有||Ot-Ot+1||, 说明状态转移概率依赖于当前及上一次观察状态, 不能严格满足Viterbi算法中对状态转移概率的要求.Simplified HMM算法按照理想模型设定了状态转移概率公式, 错误率比HMMM算法略大, 说明变种HMM更接近现实路网匹配.但Simplified HMM算法的匹配效率提高了很多, 约为前者的2倍.该算法实现更为简单, 且在处理低频采样的GPS轨迹时仍有较好的性能.
3.3.5 OHMM(online map-matching based on hidden Markov model)算法[71]算法使用在线的维特比算法来实现实时的路网匹配.计算观测概率矩阵时考虑了路段的宽度信息和速度信息.在计算状态转移矩阵时使用了机器学习的方法.
● 观测概率矩阵B
| $ {b_j}\left( k \right) = P\left( {{o_t} = {o_k}|{q_t} = {r_j}} \right) = S\left( {{v_t}, {v_r}} \right)P\left( {observation} \right) $ | (7) |
| $ P(observation) = \frac{1}{{2w}}\int_{{\kern 1pt}-w}^{{\kern 1pt} w} {\frac{1}{{\sqrt {2{\rm{ \mathsf{ π} }}} \sigma }}{{\rm{e}}^{-\frac{{{{(l-d)}^2}}}{{2{\sigma ^2}}}}}{\rm{d}}l} $ | (8) |
P(observation)与之前的算法相似, 也是使用μ=0的高斯分布拟合.但这里也考虑了路段的宽度信息, 为了能够更好地区分路段, 特别是在路口.其中, 2w是路段宽度, d是GPS样本点t和道路路段r之间点到曲线的大圆距离.GPS误差的估计标准偏差σ是通过分析地面真实数据的扰动来估计的.对于每个轨迹点, 计算该点到离其最近路段中心的大圆距离.然后, 用与文献[56, 90]相同的基于距离的绝对中位差计算标准偏差.基于整个数据集最终获得σ=6.86m.
| $ S({v_t}, {v_r}) = \frac{{{v_r}}}{{\max (0, {v_t}-{v_r}) + {v_r}}} $ | (9) |
S(vt, vr)是引入的一个超速处罚因子, 它是基于这样的假设:驾驶员不太可能在很大程度上超过速度限制.目的是帮助区分从同一路口分叉出的可能具有不同速度限制的紧密间隔的平行道路.因为在这种情况下, 单独的位置测量不足以区分路段, 因为记录的轨迹点可能落在它们之间.其中, vt是t的记录速度, vr是路段r的速度限制.如果遵守了速度限制, 那么max(0, vt-vr)=0, 不会产生代价.S(vt, vr)的作用和算法[60]中的速率变化功能是一样的.
● 状态转移矩阵A
使用支持向量机(support vector machine, 简称SVM)来探悉状态转移概率, 而不是像之前的算法一样先验地选择模型, 然后估计其参数.这种方法的主要优点是提供了一个数据驱动的框架, 用于集成多个转移评分函数.文献[71]中设计了两个评分函数.
| $ 距离差异函数:T({d_{i \to j}}, {D_{i \to j}}) = \frac{{|{d_{i \to j}}-{D_{i \to j}}|}}{{{D_{i \to j}}}} $ | (10) |
| $ 动量变化函数:M({\vec v_0}, {\vec v_1}, {l_1}, ..., {\vec v_k}, {l_k}) = \frac{{\sum\nolimits_i^K {{l_i}|{{\vec v}_i}-{{\vec v}_{i-1}}|} }}{{{{\bar v}_{i \to j}}\sum\nolimits_i^K {{l_i}} }} $ | (11) |
距离差异函数测量传感器推导的行驶距离和最短路径长度之间的差异.Pi→j定义为从i行驶到j时车辆最大可能采取的最短路径.di→j表示前后两个时刻之间以平均速率
动量变化函数测量车辆在Pi→j中采取每个路段上所引起的平均动量变化.这里,
这两个公式计算出来的都只是一个特征, 然后使用被标记为正确或不正确转换的实例训练支持向量机分类器, 其中, 特征向量由上述两个评分函数给出的分数组成.使用这种分类方法, p(i→j)就是输入的分数组合属于“正确转换”类的概率, 也就是从i到j的转移概率.
为了利用增量方法实现在线的全局路网匹配算法, 需要在不知道未来输入的情况下沿着马尔可夫链进行不可逆的在线决策, 同时确保部分解在组合时产生全局最优解.
文献[71]使用在线维特比算法来解决Vn=bj(k)max{aijVn-1}中的递推关系.当前幸存路径在马尔可夫链中的某点收敛时, 所有未来的幸存路径将包含直到收敛点的相同子路径[91, 92].
3.3.6 QMM(quick map matching using multi-core CPUs)算法[93]QMM是第1个强调运行时间的路网匹配算法.算法设计在多核CPU上运行, 因为路段的处理可以在建立索引时彼此分离, 并且每个样本轨迹点在匹配时相互独立.算法应用多线程技术极大地减少了运行时间, 同时在HMMM算法基础上作了一些改进.
● 观测概率矩阵B:算法考虑了侧路问题, 基于车辆更可能在具有较高速度约束的主要道路上行驶而不是侧路行驶的假设, 在计算观测概率时加入路段的速度限制Vr:
| $ {b_j}\left( k \right) = P\left( {{o_t} = {o_k}|{q_t} = {r_j}} \right) \cdot {V_r} $ | (12) |
由于存在不可避免的GPS测量误差, 在主路上行驶的车辆记录的GPS采样点位置可能更接近侧路, 原始算法可能会错把这些点与侧路匹配.
此外, 算法也考虑了类似于HMMM算法[56]的HMM中断问题(详细说明见第3.5.2节), 提出适当地放大参数β , 可以有效地减少中断情况, 对匹配精度具有不可估量的影响.并通过实验, 给出不同采样周期内β的最优值.
上述基于隐马尔可夫模型的路网匹配算法的对比见表 4和表 5.隐马尔可夫模型被理论和实践证明适用于低采样率的路网匹配问题, 为了进一步提高匹配精度, 在研究中引入了一些优化算法、启发式算法等.如吴刚等人[94]提出的一种将HMM和遗传算法相结合的新型地图匹配算法.在使用传统的HMM地图匹配算法预测出一组概率较大的路径序列, 然后把这组路段序列作为种群, 通过遗传算法寻找最优的路段序列, 提高了HMM算法的匹配精确度.
|
|
Table 4 Comparison of HMM-based map matching algorithm setup 表 4 基于隐马尔可夫模型的路网算法设置比较 |
|
|
Table 5 Comparison of HMM-based map matching algorithm characteristic 表 5 基于隐马尔可夫模型的路网算法性质比较 |
3.3.7 基于HMM的手机轨迹路网匹配算法
随着手机的普及, 移动大数据成为重要的资源, 提供了丰富的信息, 而且几乎没有成本.近几年新出现的一个研究方向和热点是将HMM用在采样周期低、噪声误差大的手机定位.高频率采样的智能手机定位精确但无法实时定位, 因为它消耗过多的智能手机的带宽和电池电源.因此, 手机数据一般非常稀疏且噪声较大.有必要在确保精确和及时的情况下, 为手机轨迹路网匹配开发鲁棒算法.
SnapNet系统[70, 71]使用增量HMM算法为具有噪声和稀疏性特征的粗粒度蜂窝数据提供实时地图匹配, 运用一系列的过滤器和一些启发式方法来减少噪声, 利用插补解决数据稀疏问题.George等人[95]结合了HMM的方法和驾驶员路线选择的概念, 使用HMM以在线方式为噪声和稀疏数据生成部分地图匹配路径, 然后利用一个路线选择模型, 从真实驾驶数据估计, 重新评估每个HMM生成的部分路径以及一组可行的替代路径.Essam等人[96]总结并比较了一些利用手机数据进行路网匹配的方法, 并提出了一种基于自适应HMM的模型, 使用大量移动数据来学习模型参数, 并利用数据的稀疏性来提供实时快速维特比处理, 将各个手机轨迹映射到道路段.该模型首次单独使用手机大数据进行细粒度路网匹配.
隐马尔可夫模型对于低采样率路网匹配问题的适用性, 使得它在手机数据匹配方面也得到较好的应用.由于数据的来源不同, 接下来的实验比较中没有加入手机轨迹路网算法.
3.4 实验设置与测试上述基于HMM的算法的实验环境与评价标准各有千秋(见表 6), 详细分析如下.
|
|
Table 6 Experiment results comparison of HMM-based map matching algorithm 表 6 基于隐马尔可夫模型的路网算法实验结果对比 |
3.4.1 数据集
算法测试实验使用的数据源有3种类型:合成数据、真实数据和竞赛数据.
● 合成数据
ST-Matching算法测试使用的合成数据是由模拟器随机生成的轨迹.它首先随机选择两个顶点的道路网络, 并计算它们之间最短的k条路径.然后, 随机从k条路径中选择一个轨迹作为地面实况, 记为G:e1, e2, e3, …, en.其背后的动机是移动物体通常遵循从源到目的地的方向, 但不一定严格遵循最短路径.注意到任何两个相邻点之间的时间间隔不均匀.为了检索具有所需采样间隔的轨迹, 模拟器从G中每个k'段选择一个路段, 比如选择e1, e1+k', …, e1+mk', 其中,
● 真实数据
ST-Matching算法和IVVM算法实验中, 以人们标记的真实路径数据作为地面实况.路网数据采用北京的城市道路网络图, 包含58 624个顶点和130 714个路段.GPS轨迹数据都是从Geolife系统[97, 98]收集的真实数据. ST-Matching算法从中选择了28条轨迹.它们在空间范围、长度、时间间隔和道路段数上有所不同, 采样间隔范围为30s~5min.IVVM算法数据集包含26个具有不同采样点和平均速度的轨迹.30多个小时的轨迹覆盖约643km, 采样间隔范围为30s~10.5min.
HMMM和Simplified HMM算法也是在真实数据集上进行测试.使用的是美国华盛顿西雅图的GPS数据(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次)进行二次采样.
● 竞赛数据
QMM算法采用2012年ACM SIGSPATIAL Cup(ACM SIGSPATIAL Cup 2012. Available from: 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.
3.4.2 评价标准ST-Matching算法在运行时间和匹配质量上进行了广泛的评价.实验中使用实际的程序执行时间来衡量运行时间.通过两个精度指标“准确的数量AN”和“准确的长度AL”来评估匹配质量, 其中,
| $ \begin{array}{c} {A_N} = \frac{{\# 正确匹配的路段数}}{{\# 轨迹中所有的路段数}}, \\ {A_L} = \frac{{\sum {轨迹的总长度} }}{{AAA}}. \end{array} $ |
IVMM算法在匹配质量和效率方面与ST-Matching算法进行比较.为了评估算法的效率, 实验比较了运行时间.为了评估匹配质量, 使用下式计算的正确匹配百分比(correct matching percentage, 简称CMP).
| $ CMP = \frac{{\# 正确匹配的样本点数}}{{\# 需要匹配的样本点数}} \times 100\% . $ |
HMMM算法、ST-Matching算法、Simplified HMM算法评价标准都采用道路错误匹配指数(route mismatch fraction, 简称RMF), 是对从正确路径错误添加和错误减去的不正确道路的长度求和, 然后除以正确路径的长度来计算不正确路径所占比例, 也就是结果记录的误差值, 如图 12所示.RMF指标由匹配正确和匹配错误的点数量共同决定.
|
Fig. 12 Evaluation norm 图 12 评价指标 |
OHMM算法评估使用两个性能指标:匹配精度和输出延迟.精度定义为地面真实路径中正确匹配的轨迹点的比例CMP, 某个轨迹点映射到地面真实路径中的任何道路段就是一个正确的匹配; 输出延迟是对于每个轨迹点算法所产生的平均输出延迟, 它通过在获得匹配结果之前经过的秒数来量化.
QMM算法使用不匹配率(mismatching percentage, 简称MP)作为评价标准, 采样间隔为1s~30s, 不匹配率保持在2%以内.
| $ MP = \frac{{\# 不匹配样本点数}}{{\# 所有样本点数}} \times 100\% . $ |
● ST-Matching算法
算法比较对象为基于点的先前匹配结果执行匹配的增量算法和旨在最小化平均弗雷歇距离(average Fréchet distance, 简称AFD)的全局匹配算法.合成数据的测试结果表示ST-Matching算法显著优于增量式和基于AFD的算法.同时我们注意到, 当采样率降低时, 增量算法的性能急剧退化, 而全局算法对采样率的变化更为鲁棒.当采样间隔为2.91min时, ST-Matching算法匹配质量最好, AL达到95%, AN约为92%;当采样间隔降低到5.77min时, AL仍有86%, AN为80%.
ST-Matching算法在GeoLife收集的实际数据上的测试结果也要优于增量式和基于AFD的算法.随着采样率的降低, 增量算法的精度急剧下降, 而两种全局算法再次表现出更一致的性能.当采样间隔为30s时, ST-Matching算法的AL约为87%, AN为86%;当采样间隔下降到5min时, AL约为70%, AN为68%;当采样间隔为2min时, 可以维持在80%的准确率.
为了评估算法的效率, 将算法的运行时间与基于AFD的全局方法进行比较.当采样点数目较少时, 两种方法表现出相似的运行时间; 然而随着采样点的增加, 基于ADF的方法的运行时间急剧增加.
实验结果表明:ST-Matching算法在低采样轨迹的匹配精度方面显著优于增量算法; 而且, 与基于AFD的全局匹配算法相比, ST-Matching还提高了匹配精度和运行时间.
● IVVM算法
IVMM算法在匹配质量和效率方面与ST-Matching算法进行比较.为了评估算法的效率, 实验比较了运行时间, 结果表明:对于低采样率和高采样率数据, IVMM算法与ST-Matching算法一样快, IVMM甚至更好一些; 而且随着采样间隔的增加, 要匹配的采样点数量相应地减少, 使得两种算法的时间成本都快速降低.
匹配结果显示, IVMM算法在所有采样间隔中都显著优于ST-Matching算法.回顾北京实际出租车GPS数据的统计结果(如图 6所示), 大多数低采样率GSP轨迹的采样间隔为2min~6min(在所有低采样率数据中约为86%).当采样间隔为1.5min~6.5min时, IVMM的精度维持在70%左右, 比ST-Matching算法有10%的改进.当采样间隔超过6.5min时, IVMM和ST-Matching算法的性能变得接近, 但仍具有5%的优势.验证了IVMM算法代表采样点之间的有效交互影响, 比ST-Matching算法具有更好的鲁棒性, 在低采样率的情况下匹配效果好.
● 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的资源被充分利用时, 索引构建时间和路网匹配时间都大为减少.
3.5 算法参数设置 3.5.1 窗口大多数现有的增量/在线算法、轨迹具有太多点的全局算法, 往往使用滑动窗口策略.滑动窗口方法简单地将轨迹划分为固定大小的输入序列, 并且独立地处理它们.
文献[63]中的算法使用固定滑动窗口(fixed sliding window, 简称FSW), 通过在轨迹的滑动窗上构造局部候选图来实现全局路网匹配.每个局部候选图由轨迹的子集构成, 找到这个子集的最佳匹配路径序列, 然后滑动窗口, 重复该过程.将轨迹分割为窗口可以减少平均延迟并节省在线处理的存储空间, 但不一定加快总体处理时间, 因为算法中花费最大的部分是最短路径计算.为了降低计算复杂度, 算法试探性地保留具有顶部l个分数的候选点, 从而减少下一个采样点需要计算的最短路径数量.当l=1时, 算法退化成增量算法.从真实轨迹上的实验结果可以看出:只要选择适当的窗口大小, 基于滑动窗口的全局匹配算法就可以实际使用.随着窗口尺寸的增大, 算法可以得到更好的匹配, 但输出延迟增加.而且保留顶部节点可以显著降低匹配准确度, 特别是当窗口较大时.滑动窗口方法虽然易于实现, 但可能导致次优解决方案和较长的输出延迟.
文献[71]中的算法使用可变滑动窗口(variable sliding window, 简称VSW)将输入分成更小的子问题, 并证明算法得到的是全局最优解.可以针对实时输入流很快产生输出.当在由窗口覆盖的马尔可夫链中的任何地方发现收敛点时, 窗口随着新的轨迹点被处理而从后面收缩, 向前扩展.注意, 滑动窗口的大小可以根据状态空间的结构而变化.在概念上类似于在线维特比算法[91, 92].然而, VSW的一个缺点是不能保证最坏情况的窗口大小, 因此在极端情况下, 输出延迟可以是任意大的.通过设置窗口大小的上限来修改VSW, 使得当达到阈值时, 算法将输出, 直到当前阶段的最大似然解, 即有界滑动窗(bounded variable sliding window, 简称BVSW)方法.但不同于VSW, 这种方法可能导致次优解决方案.
3.5.2 HMM中断基于隐马尔可夫模型路网匹配算法在实际应用中可能会出现中断的情况, 从一个时间点到下一个时间点的所有转移概率为0.导致中断的原因如下.
● 路线本地化.在选择某个GPS点的候选路段时, 为了避免不合理的计算量, 一般会忽略距离GPS点超过一定距离的路段, 而不将它们添加到HMM里面, 这可能会导致在特定时间中没有匹配候选.当车辆在未标记在地图上的道路上行驶时, 或者经历特别高的噪声时(比如当车辆进入隧道或城市峡谷时), 可能出现这种情况.
● 低概率路线.当路线变得迂回时, 对于该路线上的任何两个采样点之间的最短路径距离可能远大于它们之间的欧式距离.在这种情况下, 对应于该路线的转移概率将变得非常小, 这将触发HMM中断.
● GPS离群值.作为HMM状态之间转换计算的任何路线都要做合理性测试:如果计算出的路线需要车辆以超过50m/s的速度, 或者以超过3倍限制的速度行驶, 就认为路线是不合理的, 并将其概率设置为0.
由于上述的简化限制了将被考虑的匹配候选路线的数量, 可能会找不到通过HMM的完整路径, 这就是HMM中断.HMM中断发生的频率越高, 匹配算法的效率就越低.
文献[56]中的算法通过以下方式处理HMM中断:当在时间t和t+1之间检测到中断时, 从模型中移除测量点zt和zt+1, 并检查中断是否已经愈合.如果t-1和t+2的测量点在HMM中重新连接, 则中断愈合; 否则, 继续去除中断任一侧上的点, 直到中断愈合或中断超过180s.如果中断超过180s, 就将数据拆分为前后两个单独的行程, 并分别对每个行程进行路网匹配.文献[92]中的算法使用的方法是适当地扩大参数β, 可以有效地减少中断情况, 对匹配精度具有不可估量的影响.同时, 通过实验, 给出不同采样周期内β的最优值.
4 研究挑战与趋势GPS轨迹进行路网匹配是轨迹挖掘的基础, 而GPS数据规模和数据质量都对路网匹配算法提出了挑战.下一步考虑在这两个方面进行的研究工作.
4.1 使用大数据技术提高算法性能配有GPS设备的车辆会产生海量数据.比如北京市具有约6万余辆出租车, 一天的时间就能产生上亿条GPS数据, 更不用提产生更多数据的车牌识别、交通视频监控等.当前, 与交通有关的数据跃升到PB级别.这种情况下, 再使用传统交通流方法来对数据进行处理与分析, 效果不甚理想.
另外, 交通轨迹数据在空间和时间上呈现某种特性, 如果能够充分利用时空特点, 可以关联更多的异构数据, 从而实现更加准确的分析, 但是相应地也增大了数据分析的维度, 对数据查询和处理提出了更高的要求.尤其在轨迹数据规模较大的情况下, 计算效率变得更加重要.
日趋成熟的Hadoop, Spark等分布式计算平台能够高效地支持大规模数据的分析与建模问题.合理的分布式策略可以线性地提高交通计算的速度.如, Map-Reduce就是一个性能很高的批处理分布式计算框架.它能够并行处理海量轨迹数据, 可以利用集群的计算能力来提高轨迹数据处理的效率.应海量数据处理需求发展起来的云计算等新兴综合应用, 可以帮助路网匹配算法降低海量数据处理的难度、节约成本、提高处理效率.
此外, 对时空数据做索引, 支持快速存取, 可以缩小定位范围, 减少候选路段数量, 从而极大地缩短了GPS数据匹配时间, 可以更高效、更精确地确定候选匹配路段, 提高路网匹配的实时性和准确性.时空数据索引依赖于空间数据库索引技术, 如网格索引、R-tree、K-D Tree、Quadtree等.
4.2 利用道路语义提高匹配准确性GPS设备精度和测量误差会严重影响路网匹配的准确率.可以考虑使用GPS信息对车辆所处的道路情况进行预判, 从而根据不同的道路场景选择相应的路网匹配算法来提高路网匹配的实时性和准确性.
● 首先, 可以使用机器学习和计算机视觉的方法来提取路边的街道、街景、交通标志等细节信息, 从而建立GPS信息之外的新数据层, 这样能够在很大程度上帮助路网匹配算法提高准确率.比如, 路牌信息可以更好地起到指针作用, 如果驾驶者在听到导航指示的时候能够匹配所看到的街景, 比如车辆所在街道旁边的企业、单位或是商铺的招牌等信息也可以帮助车辆更快、更准地定位; 路边的停止标记、地上的车道或者转弯限制等交通标志信息虽然很难捕捉, 但是可以帮助提高匹配的效率和质量.
● 其次, 智能手机传感器能感受到不同的道路特性[77], 如减速道或隧道.例如, 驶过减速带的车辆将会小范围地上下移动, 这将引起手机测量的重力加速度发生变化; U形转弯的车辆将产生大约180°的方向转变.因此, 可以利用手机传感器的这种效应来监测道路条件的变化.文献[99-101]使用加速度计来检测坑洞和交通条件.使用智能手机的传感器实时识别大范围的道路语义, 可以自动丰富当前的数字地图, 使基于这些道路语义丰富的数字地图上的路网匹配变得更加精确.
● 最后, 普通用户也可以参与到标记道路语义信息的工作中来, 比如获取公园、步行道以及其他街景车无法进入的地方的信息, 完善更多精确路线.随着信息不断被开发、路网匹配精度不断提高, 最终呈现出来的将是更为丰富、灵活的交通生活地图.
5 结论本文详细调研了国内外轨迹路网匹配技术, 包括全局算法和局部算法.很多算法只适合于高采样率的轨迹, 不适合于低采样率的轨迹, 而基于隐马尔可夫的算法成为主流, 因此, 本文详细综述了基于隐马尔可夫模型的路网匹配算法, 分析了各种不同算法的优势和不足, 最后给出了研究挑战和趋势.
| [1] |
Li X, Han J, Lee J, Gonzalez H. Traffic densitybased discovery of hot routes in road networks. In: Proc. of the 10th Int'l Symp. on Spatial and Temporal Databases, Vol. 4605. 2007. 441-459. [doi: 10.1007/978-3-540-73540-3_25] |
| [2] |
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] |
| [3] |
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] |
| [4] |
Zheng, Y, Wang L, Xie X, Ma W. GeoLife: Managing and understanding your past life over maps. In: Proc. of the 9th Int'l Conf. on Mobile Data Management. 2008. 211-212. [doi: 10.1109/MDM.2008.20] |
| [5] |
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] |
| [6] |
Joshi RR. A new approach to map matching for in-vehicle navigation systems: The rotational variation metric. In: Proc. of the ITS. 2001. 33-38. [doi: 10.1109/ITSC.2001.948625] |
| [7] |
Feijoo C, Ramos J, Perez F. A system for fleet management using differential GPS and VHF data transmission mobile networks. In: Proc. of the VNIS. 1993. 445-448. [doi: 10.1109/VNIS.1993.585667] |
| [8] |
Chen M, Liu Y, Yu X. Predicting next locations with object clustering and trajectory clustering. In: Proc. of the PAKDD. 2015. 344-356. [doi: 10.1007/978-3-319-18032-8_27] |
| [9] |
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] |
| [10] |
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] |
| [11] |
Krumm J. A Markov model for driver turn prediction. SAE World Congress, 2008, 22(1): 1–25.
http://www.doc88.com/p-7478079637398.html |
| [12] |
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.https://www.researchgate.net/publication/224793556_New_Approaches_for_Traffic_Management_in_Metropolitan_Areas |
| [13] |
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.http://link.springer.com/10.1007/978-3-319-18032-8_28 |
| [14] |
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] |
| [15] |
Long X, Jin L, Joshi J. Exploring trajectory-driven local geographic topics in foursquare. In: Proc. of the Int'l Workshop on Location-based Social Networks. 2012. 927-934. [doi: 10.1145/2370216.2370423]http://dl.acm.org/citation.cfm?id=2370423 |
| [16] |
Yuan Q, Cong G, Ma Z, Sun A, Magnenat-Thalmann N. Who, where, when and what: Discover spatio-temporal topics for Twitter users. In: Proc. of the SIGKDD. 2013. 605-613. [doi: 10.1145/2487575.2487576] |
| [17] |
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.http://dl.acm.org/citation.cfm?id=1325851.1325942&preflayout=flat |
| [18] |
Wei LY, Zheng Y, Peng WC. Constructing popular routes from uncertain trajectories. In: Proc. of the SIGKDD. 2012. 195-203.http://dl.acm.org/citation.cfm?id=2339562 |
| [19] |
Yuan J, Zheng Y, Xie X, Sun GZ. T-Drive:Enhancing driving directions with taxi drivers' intelligence. IEEE Trans. on Knowledge and Data Engineering, 201, 26(1): 220–232.
[doi:10.1109/TKDE.2011.200] |
| [20] |
Patterson DJ, Liao L, Fox D, Kautzy H. Inferring high-level behavior from low-level sensors. In: Proc. of the UbiComp. Springer-Verlag, 2003. 73-89. [doi: 10.1007/978-3-540-39653-6_6]http://www.springerlink.com/content/k3x004g773qj80kg |
| [21] |
Rauschert I, Agrawal P, Sharma R, Fuhrmann S, Brewer I, MacEachren A, Wang HM, Cai G. Designing a human-centered, multimodal GIS interface to support emergency management. In: Proc. of the Int'l Symp. on Advances in Geographic Information Systems. 2003. 119-124. [doi: 10.1145/585147.585172] |
| [22] |
Li M, Zhang Y, Wang W. Analysis of congestion points based on probe car data. In: Proc. of the ITS. 2009. 1-5. [doi: 10.1109/ITSC.2009.5309869] |
| [23] |
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] |
| [24] |
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] |
| [25] |
Shang J, Zheng Y, Tong W, Chang E, Yu Y. Inferring GAS consumption and pollution emission of vehicles throughout a city. In: Proc. of the SIGKDD. 2014. 1027-1036. [doi: 10.1145/2623330.2623653] |
| [26] |
Bernstein D, Kornhauser A. An introduction to map matching for personal navigation assistants. Geometric Distributions, 1996, 122(7): 1082–1083.
https://users.cs.jmu.edu/bernstdh/web/tide/reports/mapmatchintro.pdf |
| [27] |
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] |
| [28] |
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] |
| [29] |
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] |
| [30] |
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] |
| [31] |
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.
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.386.5400 |
| [32] |
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.
https://link.springer.com/content/pdf/10.1007/978-3-319-49466-1_2.pdf |
| [33] |
Ochieng WY, Quddus M, Noland RB. Map-Matching in complex urban road networks. Revista Brasileira De Cartografia, 2003, 55(2): 1–14.
http://www.doaj.org/doaj?func=abstract&id=216880&recNo=55&toc=2&uiLanguage=en |
| [34] |
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] |
| [35] |
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] |
| [36] |
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.http://www.researchgate.net/publication/237430219_Fuzzy_Logic_Based-Map_Matching_Algorithm_for_Vehicle_Navigation_System_in_Urban_Canyons |
| [37] |
Su H, Chen J, Xu J. A adaptive map matching algorithm based on fuzzy-neural-network for vehicle navigation system. In: Proc. of the WCICA. 2008. 4448-4452. [doi: 10.1109/WCICA.2008.4593639] |
| [38] |
Haibin S, Jiansheng T, Chaozhen H. A integrated map matching algorithm based on fuzzy theory for vehicle navigation system. In: Proc. of the ICCIAS. 2006. 916-919. [doi: 10.1109/ICCIAS.2006.294272] |
| [39] |
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).
https://www.cnki.com.cn/qikan-JSJY201508053.html |
| [40] |
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] |
| [41] |
Nassreddine G, Abdallah F, Denoeux T. Map matching algorithm using belief function theory. In: Proc. of the IF. 2008. 1-8.http://ieeexplore.ieee.org/document/4632319/ |
| [42] |
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] |
| [43] |
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] |
| [44] |
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, 2010, 14(1): 27–36.
[doi:10.1080/15472450903386013] |
| [45] |
Kim W, Jee GI, Lee JG. Efficient use of digital road map in various positioning for ITS. In: Proc. of the Position Location and Navigation Symp. 2000. 170-176. [doi: 10.1109/PLANS.2000.838299] |
| [46] |
Li Z, Chen W. A new approach to map-matching and parameter correcting for vehicle navigation system in the area of shadow of GPS signal. In: Proc. of the ITSC, Vol. 5. 2005. 425-430. [doi: 10.1109/ITSC.2005.1520086] |
| [47] |
Pyo JS, Shin DH, Sung TK. Development of a map matching method using the multiple hypothesis technique. In: Proc. of the Intelligent Transportation Systems. 2001. 23-27. [doi: 10.1109/ITSC.2001.948623] |
| [48] |
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] |
| [49] |
Yin H, Wolfson O. A weight-based map matching method in moving objects databases. In: Proc. of the SSDBM, Vol. 16. 2004. 437-438. [doi: 10.1109/SSDM.2004.1311248] |
| [50] |
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] |
| [51] |
Brakatsoulas S, Pfoser D, Salas R, Wenk C. On map-matching vehicle tracking data. In: Proc. of the VLDB. 2005. 853-864.http://dl.acm.org/citation.cfm?id=1083691 |
| [52] |
Honey SK, Zavoli WB, Milnes KA, Phillips AC, Jr White MS, Jr Loughmiller GE. Vehicle navigational system and method: US. US4796191, 1989. |
| [53] |
Pink O, Hummel B. A statistical approach to map matching using road network geometry, topology and vehicular motion constraints. In: Proc. of the ITS. 2008. 862-867. [doi: 10.1109/ITSC.2008.4732697] |
| [54] |
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] |
| [55] |
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).
http://www.cnki.com.cn/Article/CJFDTotal-SHJT201308028.htm |
| [56] |
Newson P, Krumm J. Hidden Markov map matching through noise and sparseness. In: Proc. of the ACM-GIS. 2009. 336-343. [doi: 10.1145/1653771.1653818] |
| [57] |
Greenfeld JS. Matching GPS observations to locations on a digital map. In: Proc. of the TRB. 2002. https://trid.trb.org/Results?q=&serial=%22Transportation%20Research%20Board%2081st%20Annual%20Meeting%22 |
| [58] |
Wenk C, Salas R, Pfoser D. Addressing the need for map-matching speed: Localizing global curve-matching algorithms. In: Proc. of the SSDBM. 2006. 379-388. [doi: 10.1109/SSDBM.2006.11] |
| [59] |
Chawathe SS. Segment-Based map matching. In: Proc. of the Intelligent Vehicles Symp. 2007. 1190-1197. [doi: 10.1109/IVS.2007.4290280] |
| [60] |
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.http://dl.acm.org/citation.cfm?id=1653820 |
| [61] |
Yuan J, Zheng Y, Zhang C, Xie X, Sun JZ. An interactive-voting based map matching algorithm. In: Proc. of the MDM. 2010. 43-52. [doi: 10.1109/MDM.2010.14] |
| [62] |
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. |
| [63] |
Zheng K, Zheng Y, Xie X, Zhou XF. Reducing uncertainty of low sampling rate trajectories. In: Proc. of the ICDE. 2012. 1144-1155.http://dl.acm.org/citation.cfm?id=2310317 |
| [64] |
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] |
| [65] |
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.http://dl.acm.org/citation.cfm?id=1644048 |
| [66] |
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.http://dl.acm.org/citation.cfm?id=1972485 |
| [67] |
Wang H, Wang Z, Shen G, Li F, Han S, Zhao F. WheelLoc: Enabling continuous location service on mobile phone for outdoor scenarios. In: Proc. of the INFOCOM. 2013. 2733-2741. [doi: 10.1109/INFCOM.2013.6567082] |
| [68] |
Guha S, Plarre K, Lissner D, Mitra S, Krishna B, Dutta P, Kumar S. AutoWitness: Locating and tracking stolen property while tolerating GPS and radio outages. In: Proc. of the TOSN. 2010. 29-42. [doi: 10.1145/1869983.1869988] |
| [69] |
Aly H, Youssef M. semMatch: Road semantics-based accurate map matching for challenging positioning data. In: Proc. of the 23rd SIGSPATIAL Int'l Conf. on Advances in Geographic Information Systems. 2015. Article No. 5. [doi: 10.1145/2820783.2820824] |
| [70] |
Mohamed R, Aly H, Youssef M. Accurate and efficient map matching for challenging environments. In: Proc. of the SIGSPATIAL. 2014. 401-404. [doi: 10.1145/2666310.2666429] |
| [71] |
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] |
| [72] |
Aly H, Youssef M. Dejavu: An accurate energy-efficient outdoor localization system. In: Proc. of the ACM-GIS. 2013. 154-163. [doi: 10.1145/2525314.2525338] |
| [73] |
Alzantot M, Youssef M. UPTIME: Ubiquitous pedestrian tracking using mobile phones. In: Proc. of the WCNC. 2012. 3204-3209. [doi: 10.1109/WCNC.2012.6214359] |
| [74] |
Ibrahim M, Youssef M. CellSense: A probabilistic RSSI-based GSM positioning system. In: Proc. of the GLOBECOM. 2010. 1-5. [doi: 10.1109/GLOCOM.2010.5683779] |
| [75] |
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] |
| [76] |
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] |
| [77] |
Aly H, Basalamah A, Youssef M. Map++: A crowd-sensing system for automatic map semantics identification. In: Proc. of the SECON. 2014. 546-554. [doi: 10.1109/SAHCN.2014.6990394] |
| [78] |
Goh CY, Dauwels J, Mitrovic N, Asif MT, Oran A, Jailletet P. Online map-matching based on hidden Markov model for real-time traffic sensing applications. In: Proc. of the ITSC. 2012. 776-781. [doi: 10.1109/ITSC.2012.6338627] |
| [79] |
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] |
| [80] |
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] |
| [81] |
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] |
| [82] |
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.http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6460610 |
| [83] |
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] |
| [84] |
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] |
| [85] |
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] |
| [86] |
Lamb P, Thiebaux S. Avoiding explicit map-matching in vehicle location. In: Proc. of the ITS. 1999. 8-12.http://www.mendeley.com/research/avoiding-explicit-mapmatching-vehicle-location/ |
| [87] |
Hummel B. Map matching for vehicle guidance. In: Dynamic and Mobile GIS: Investigating Changes in Space and Time. Boca Raton: Taylor & Francis, 2006. |
| [88] |
Krumm J, Letchner J, Horvitz E. Map matching with travel time constraints. SAE Technical Paper, 2007-01-1102, 2007. [doi: 10.4271/2007-01-1102] |
| [89] |
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] |
| [90] |
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.https://www.researchgate.net/publication/290092893_Challenges_and_opportunities_in_exploiting_large-scale_GPS_probe_data |
| [91] |
Bloit J, Rodet X. Short-Time viterbi for online HMM decoding: Evaluation on a real-time phone recognition task. In: Proc. of the ICASSP. 2008. 2121-2124. [doi: 10.1109/ICASSP.2008.4518061] |
| [92] |
Šrámek R, Brejová B, Vinař T. On-Line viterbi algorithm and its relationship to random walks. arXiv: 0704. 0062v1, 2007.http://arxiv.org/abs/0704.0062 |
| [93] |
Song R, Lu W, Sun W, Huang W, Chen C. Quick map matching using multi-core CPUs. In: Proc. of the ACM-GIS. 2012. 605-608. [doi: 10.1145/2424321.2424428] |
| [94] |
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).
http://d.wanfangdata.com.cn/Thesis/Y311415 |
| [95] |
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] |
| [96] |
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] |
| [97] |
Zheng Y, Chen Y, Xie X, Ma W. GeoLife2. 0: A location-based social networking service. In: Proc. of the MDM. 2009. 357-358. |
| [98] |
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.http://dl.acm.org/citation.cfm?id=1367532 |
| [99] |
Eriksson J, Girod L, Hull B, Newton Y, Madden S, Balakrishnan H. The pothole patrol: Using a mobile sensor network for road surface monitoring. In: Proc. of the MobiSys. 2008. 29-39. [doi: 10.1145/1378600.1378605]http://dl.acm.org/citation.cfm?id=1378605 |
| [100] |
Mednis A, Strazdins G, Zviedris R, Kanonirs G, Selavo L. Real time pothole detection using Android smartphones with accelerometers. In: Proc. of the DCOSS. 2011. 1-6. [doi: 10.1109/DCOSS.2011.5982206] |
| [101] |
Mohan P, Padmanabhan VN, Ramjee R. Nericell: Rich monitoring of road and traffic conditions using mobile smartphones. In: Proc. of the SenSys. 2008. 323-336. [doi: 10.1145/1460412.1460444] |
| [39] |
张琳, 刘婧文, 王汝传, 王海艳. 基于改进D-S证据理论的信任评估模型. 通信学报, 2013, 34(7): 167–173.
https://www.cnki.com.cn/qikan-JSJY201508053.html
|
| [55] |
张振辉, 崔铁军, 姚慧敏. 车辆导航系统中地图匹配新算法. 海洋测绘, 2006, 26(2): 55–58.
http://www.cnki.com.cn/Article/CJFDTotal-SHJT201308028.htm
|
| [94] |
吴刚, 邱煜晶, 王国仁. 基于隐马尔可夫模型和遗传算法的地图匹配算法. 东北大学学报(自然科学版), 2017, 38(4): 472–475.
http://d.wanfangdata.com.cn/Thesis/Y311415
|