一种基于R树和轨迹分段的HMM高效地图匹配方法

摘要

本发明公开了一种基于R树和轨迹分段的HMM高效地图匹配方法。首先采用R树空间索引方法为路网建立空间索引，然后基于轨迹点位置变化率对GPS轨迹数据进行分段，并利用R树索引快速确定子轨迹所属的候选路段，在子轨迹中挑选关键点代替整段子轨迹判断所属路段，根据结果完成各子轨迹的地图匹配。本发明的优点是：可以同时减少道路搜索和轨迹点遍历的工作量，大幅提高算法效率。

权利要求

1.一种基于R树和轨迹分段的HMM高效地图匹配方法，其特征在于，包括如下步骤：S1：对于路网数据建立R树；

S2：对GPS轨迹数据进行子轨迹的划分，根据轨迹数据的位置实时变化率对GPS数据进行逐点处理，通过点间位置变化率与平均变化率的大小关系判断该点是否处于当前子轨迹；两点间的位置变化率分为经度平均变化率和纬度平均变化率；经度平均变化率和纬度平均变化率的计算方法均为该点的经度或纬度值减去上一点的经度或纬度值的绝对值，再除以上一点的经度或纬度，用公式表示为：具体流程如下：

S21：创建一个子轨迹并作为当前子轨迹，从第一个点或当前点开始将前两个轨迹点加入，第三个轨迹点设为当前点；

S22：从当前点i开始遍历GPS轨迹点；

S23：计算当前点的位置变化率和当前子轨迹的平均位置变化率；平均位置变化率公式为：S24：判断当前点的位置变化率和当前子轨迹的平均位置变化率的大小关系，当i点满足r(i)lon≤1.5R(n)lon且r(i)lat≤1.5R(n)lat时，说明位置变化率与当前子轨迹的平均值相差不大，认为其属于当前子轨迹，转到S25；否则，结束当前子轨迹，返回S21；

S25：将当前点加入当前轨迹，下一点作为当前点，返回S22；

S3：遍历所有子轨迹，对于每个子轨迹，将所有轨迹点等分为四部分，第一部分和第四部分保留所有点，而在中间两部分每两个点取样一个点，按顺序排列，生成整个轨迹的样本；

S4：使用维特比算法计算轨迹样本的最优匹配道路，具体步骤如下：S41：从样本起点出发，利用R树索引寻找候选路段；综合考虑轨迹点与各路段距离、前进方向的差异性，通过公式计算选择各个路段的概率P(X1j)，公式如下：其中，dj为与第j个路段间的距离，取轨迹点到道路的垂线长度；θj为轨迹点与第j个路段间的前进方向夹角，取正值；

S42：从第二个样本点开始，通过公式P(Xij)＝P(Xi‑1)*P(Xi|Xi‑1)*P(Xij|Xi)  (4)，计算各个候选路段的观测概率P(Xij)，直至最后一个样本点；

P(Xij)为选择当前路段的概率；P(Xi‑1)为上一路段的概率；P(Xi|Xi‑1)为两状态间的转移概率；P(Xij|Xi)为当前状态中选择当前路段的概率；

S43：找到最后一个状态中具有最大观测概率的候选路段，并由此进行回溯，得到各个状态的相应候选路段，直到样本起点；

S5：将回溯得到的整条路径作为该子轨迹的匹配路径，并将子轨迹内的各个点匹配到该路径的距离最小点上，完成匹配。

说明书

一种基于R树和轨迹分段的HMM高效地图匹配方法

技术领域

[0001] 本发明涉及地图匹配技术领域，特别涉及一种基于R树和轨迹分段的HMM高效地图匹配方法。

背景技术

[0002] GPS轨迹数据是带有时间和空间信息的序列数据，数据获取成本低，覆盖范围广，且拥有时态特性。通过GPS轨迹数据既可以进行微观个体活动模式的研究，也可以进行宏观[1‑4]活动系统的城市空间结构研究，已经成为城市地理大数据研究重要的数据源 。由于GPS数据的误差，未校准的轨迹数据往往会偏离实际道路，在实际应用时，首先要将GPS数据进[5]
行地图匹配，获得结合路网的轨迹描述 。GPS轨迹数据的地图匹配是学者对其进行深一步[6‑9]
挖掘分析的基础工作之一 。

[0003] 传统的地图匹配算法仅根据几何与拓扑关系将轨迹点匹配到路网上[10‑11]，这种方法仅考虑GPS点与道路的空间位置，而未考虑道路的连通性、双向性等信息，因此会导致[12]结果产生较大的误差。Newson和Krumm 于2009年提出了基于隐马尔科夫模型(Hidden‑Markov Model，简称HMM)的地图匹配算法，该算法考虑到了车辆行驶的历史信息，从概率论的角度引入了观测概率和隐藏概率，很好的解决了单纯几何匹配精度不够的问题，已经成为GPS轨迹地图匹配的主要方法，目前众多地图匹配算法的工作是在HMM地图匹配算法的基础上对其精度和效率进行改进。

[0004] 对HMM地图匹配算法进行精度改进的方法有多种形式，主要是通过优化维特比算[13]法中的概率计算实现准确率的提高，如：陈浩 使用动态规划的方法，将计算单个轨迹点的发射概率和转移概率改进为计算路段联合概率；传统的HMM地图匹配算法并未考虑行驶[14] [15]
方向对模型的影响，而刘旻 、王晓蒙 都提出了将行驶方向(航向角)引入转移概率计算[16]
的方法。另有学者对匹配前或匹配后的轨迹数据进行一定处理，如：Zhou 考虑到实际交通状况较为复杂，提出在匹配前选出匹配易错点并进行人工注释，其余点正常进行HMM地图[17]
匹配；吴刚 使用遗传算法对HMM地图匹配的结果进处理，进一步提高了匹配路段的准确性。

[0005] 实际应用场景中，尤其是在线地图应用中，对轨迹数据地图匹配的时效性要求很[18]高，因此，许多学者更加侧重于研究如何提高HMM地图匹配的效率，如：Huang 提出了从历[14] [19]
史轨迹数据中识别出频繁模式的方法；刘旻 、Xie 都选择对轨迹数据进行分割处理以[15]
减少转移概率的计算次数。也有学者对道路搜索的速率来进行优化，如王晓蒙 对路网数据建立了哈希索引，可以在一定程度上提高地图匹配的效率。另一种解决办法是对轨迹点进行抽稀处理，即对轨迹点进行抽样，比如每隔50m保留一个轨迹点，只对抽稀后的样本点进行匹配。这种方法可以明显提高匹配速度，但缺点是没有考虑到轨迹点的各个属性(速度、方向等)与所在路段的相关性。

[0006] 如上所述，众多学者针对地图匹配算法的高效率要求对HMM地图匹配算法进行了改进，已有的方法或对GPS轨迹数据的遍历进行简化处理以减少对轨迹点的循环次数，或对路网数据建立索引以加快搜索速率。实际上，地图匹配算法的时间复杂度主要源于对路网数据的搜索和对轨迹数据的逐点判断两个方面，若从这两个方面综合起来进行改进，可以极大地提高算法效率。因此，本发明提供一种基于采用R树和轨迹分段的HMM高效地图匹配方法，对路网数据建立R树索引的同时，也对GPS轨迹数据进行了轨迹分割处理，实现从两个方面同时提高算法的效率。

[0007] 参考文献

[0008] [1]Xi Liu,Gong Li,Gong Yongxi,et al.Revealing travel patterns and city structure with taxi trip data[J].Journal of Transport Geography,2015,4378‑90.ISSN:0966‑6923；

[0009] [2]Yang Zhou,Fang Zhixiang,Thill Jean‑Claude,et al.Functionally critical locations in an urban transportation network:Identification and space–time analysis using taxi trajectories[J].Computers,Environment and Urban Systems,2015,5234‑47.ISSN:0198‑9715；

[0010] [3]朱递,刘瑜.一种路网拓扑约束下的增量型地图匹配算法[J].武汉大学学报(信息科学版),2017,42(01):77‑83.[Zhu D,Liu Y.An Incremental Map‑Matching Method Based on Road Network Topology[J].Geomatics and Information Science of Wuhan University,2017,42(01):77‑83.]；

[0011] [4]吴涛,向隆刚,龚健雅.路网更新的轨迹‑地图匹配方法[J].测绘学报,2017,46(04):507‑515.[Wu T,Xiang L G,Gong J Y.Renewal of Roads Networks Using Map‑matching Technique of Trajectories[J].Acta Geodaetica et Cartographica Sinica,2017,46(04):507‑515.]；

[0012] [5]W.C,J.Z,W.M,et al.Map Matching Algorithm According to Pseudo‑Zernike Moments[C].2010Second World Congress on Software Engineering,Hubei,China,2010；

[0013] [6]Yu Zheng.Trajectory  Data  Mining:An  Overview[J].ACM Trans.Intell.Syst.Technol.,2015,6(4):29.ISSN:2157‑6904；

[0014] [7]卢家品,罗月童,黄兆嵩,等.基于排名学习和多源信息的地图匹配方法[J].浙江大学学报(理学版),2020,47(01):27‑35.[Lu J P,Luo Y T,Huang Z S,et al.An information fusion map matching method based on ranking learning[J].Journal of Zhejiang University(Science Edition),2020,47(01):27‑35.]；

[0015] [8]Ming Ren,Karimi Hassan‑A.A fuzzy logic map matching for wheelchair navigation[J].GPS Solutions,2012,16(4):273‑282.ISSN:1521‑1886；

[0016] [9]Hu G.,J.Shao,F.Liu,et al.IF‑Matching:Towards Accurate Map‑Matching with Information Fusion[J].IEEE Transactions on Knowledge and  Data Engineering,2017,29(1):114‑127.ISSN:2375‑026X；

[0017] [10]Yoonsik Bang,Kim Jiyoung,Yu Kiyun.An Improved Map‑Matching Technique Based on the Fréchet Distance Approach for Pedestrian Navigation Services.2016；

[0018] [11]Ling Yuan,Li Dan,Hu Song.A map‑matching algorithm with low‑frequency floating car data based on matching path[J].EURASIP Journal on Wireless Communications and Networking,2018,2018(1):146.ISSN:1687‑1499；

[0019] [12]Paul Newson,Krumm John.Hidden Markov map matching through noise and sparseness[A]//Seattle,Washington:Association for Computing Machinery,2009:336‑343；

[0020] [13]陈浩,许长辉,张晓平,等.基于隐马尔科夫模型和动态规划的手机数据移动轨迹匹配[J].地理与地理信息科学,2019,35(03):1‑8.[Chen H,Xu C H,Zhang X P,et al.Hidden Markov Model and Dynamic Programming Based Map Matching Method for Mobile Trajectories Using Mobile Phone Data[J].Geography and Geo‑Information Science,2019,35(03):1‑8.]；

[0021] [14]刘旻,李梅,徐晓宇,等.一种基于HMM模型改进的地图匹配算法[J].北京大学学报(自然科学版),2018,54(06):1235‑1241.[Liu W,Li M,Xu X Y,et al.An Improved Map Matching Algorithm Based on HMM Model[J].Acta Scientiarum Naturalium Universitatis Pekinensis,2018,54(06):1235‑1241.]；

[0022] [15]王晓蒙,池天河,林晖,等.一种面向海量浮动车数据的地图匹配方法[J].地球信息科学学报,2015,17(10):1143‑1151.[Wang X M,Chi T H,Lin H,et al.A Research of Map‑Matching Method for Massive Floating Car Data[J].Journal of Geo‑Information Science,2015,17(10):1143‑1151.]；

[0023] [16]Xibo Zhou,Ding Ye,Tan Haoyu,et al.HIMM:An HMM‑Based Interactive Map‑Matching System[A]//Candan S,Chen L,Pedersen TB,et al.Cham:Springer International Publishing,2017:3‑18；

[0024] [17]吴刚,邱煜晶,王国仁.基于隐马尔可夫模型和遗传算法的地图匹配算法[J].东北大学学报(自然科学版),2017,38(04):472‑475.[Wu G,Qiu Y J,Wang G R.Map Matching Algorithm Based On Hidden Markov Model and Genetic Algorithm[J].Journal of Northeastern University(Natural Science),2017,38(04):472‑475.]；

[0025] [18]Huang Y.,W.Rao,Z.Zhang,et al.Frequent Pattern‑Based Map‑Matching on Low Sampling Rate Trajectories[A]//2018:266‑273.ISSN:2375‑0324；

[0026] [19]Yan Xie,Zhou Kai,Miao Fang,et al.High‑Accuracy Off‑Line Map‑Matching of Trajectory Network Division Based on Weight Adaptation HMM[J].IEEE Access,2020,87256‑7266.ISSN:2169‑3536；

[0027] [20]吴军.数学之美[M].北京：人民邮电出版社，2012：49‑58；

[0028] [21]Antonin Guttman.R‑Trees:A Dynamic Index Structure for Spatial Searching[J].SIGMOD Rec.,1984,14(2):47‑57。

发明内容

[0029] 本发明针对传统HMM地图匹配算法无法高效处理大量轨迹数据的问题，提供了一种基于采用R树和轨迹分段的HMM高效地图匹配方法，对路网数据建立R树索引的同时，也对GPS轨迹数据进行了轨迹分割处理，实现从两个方面同时提高效率。

[0030] 为了实现以上发明目的，本发明采取的技术方案如下：

[0031] 一种基于R树和轨迹分段的HMM高效地图匹配方法，包括如下步骤：

[0032] S1：对于路网数据建立R树；

[0033] S2：对GPS轨迹数据进行子轨迹的划分；

[0034] S3：遍历所有子轨迹，对于每个子轨迹，将所有轨迹点等分为四部分，第一部分和第四部分保留所有点，而在中间两部分每两个点取样一个点，按顺序排列，生成整个轨迹的样本；

[0035] S4：使用维特比算法计算该样本的最优匹配道路：

[0036] S5：将回溯得到的整条路径作为该子轨迹的匹配路径，并将子轨迹内的各个点匹配到该路径的距离最小点上，完成匹配。

[0037] 进一步地，S2根据轨迹数据的位置实时变化率对GPS数据进行逐点处理，通过点间位置变化率与平均变化率的大小关系判断该点是否处于当前子轨迹。两点间的位置变化率分为经度平均变化率和纬度平均变化率。经度平均变化率和纬度平均变化率的计算方法均为该点的经度或纬度值减去上一点的经度或纬度值的绝对值，再除以上一点的经度或纬度，用公式表示为：

[0038]

[0039] 具体流程如下：

[0040] S21：创建一个子轨迹并作为当前子轨迹，从第一个点或当前点开始将前两个轨迹点加入，第三个轨迹点设为当前点；

[0041] S22：从当前点i开始遍历GPS轨迹点；

[0042] S23：计算当前点的位置变化率和当前子轨迹的平均位置变化率。平均位置变化率公式为：

[0043]

[0044] S24：判断当前点的位置变化率和当前子轨迹的平均位置变化率的大小关系，当i点满足r(i)lon≤1.5R(n)lon且r(i)lat≤1.5R(n)lat时，说明位置变化率与当前子轨迹的平均值相差不大，认为其属于当前子轨迹，转到S25；否则，结束当前子轨迹，返回S21；

[0045] S25：将当前点加入当前轨迹，下一点作为当前点，返回S22。

[0046] 进一步地，S4的具体步骤如下：

[0047] S41：从样本起点出发，利用R树索引寻找候选路段；综合考虑轨迹点与各路段距离、前进方向的差异性，通过公式计算选择各个路段的概率P(X1j)，公式如下：

[0048]

[0049] 其中，dj为与第j个路段间的距离，取轨迹点到道路的垂线长度；θj为轨迹点与第j个路段间的前进方向夹角，取正值。

[0050] S42：从第二个样本点开始，通过公式P(Xij)＝P(Xi‑1)*P(Xi|Xi‑1)*P(Xij|Xi)  (4)，计算各个候选路段的观测概率P(Xij)，直至最后一个样本点；

[0051] P(Xij)为选择当前路段的概率；P(Xi‑1)为上一路段的概率；P(Xi|Xi‑1)为两状态间的转移概率；P(Xij|Xi)为当前状态中选择当前路段的概率。

[0052] S43：找到最后一个状态中具有最大观测概率的候选路段，并由此进行回溯，得到各个状态的相应候选路段，直到样本起点。

[0053] 与现有技术相比，本发明的优点在于：

[0054] 进行了效率优化，使在时效性上更具优势。效率在GPS轨迹数据量较大的情况下有明显提高，适用于轨迹数据量极大的应用场景。

附图说明

[0055] 图1是本发明实施例针对路网的空间分割示意图；

[0056] 图2是本发明实施例建立的R树示意图；

[0057] 图3是本发明实施例位置变化率分区示意图；

[0058] 图4是本发明实施例GPS轨迹数据分段匹配示意图；

[0059] 图5是本发明实施例候选路段示意图；

[0060] 图6是本发明实施例部分轨迹点的匹配效果示意图；

[0061] 图7是本发明实施例三种匹配算法的效率分析示意图。

具体实施方式

[0062] 为使本发明的目的、技术方案及优点更加清楚明白，以下根据附图并列举实施例，对本发明做进一步详细说明。

[0063] 一种基于R树和轨迹分段的HMM高效地图匹配方法，包括如下步骤：

[0064] S1：对于路网数据建立R树；

[0065] R树(R‑trees)是一种采用空间分割概念的平衡树，通过最小包围矩形(MBR)将多维空间分割为多个层次，可以大幅减少空间搜索中的结点访问量。在构建一棵R树时，每个叶子结点保存指向空间中各地物MBR的指针；倒数第二层同样保存指向MBR的指针，这类MBR包含一个或多个各地物的MBR；以此类推，最终在整个空间建立索引。在基于HMM的地图匹配算法中，每个状态都可能有大量的观测结果，即可能的匹配路段。匹配过程中，遍历每个GPS轨迹点时，首先要做的就是筛选出候选匹配路段，即当前状态的所有节点。通常情况下，路网复杂、路段繁多，因而此搜索步骤会耗费大量时间。若在匹配前以各个路段为最小地物单元建立R树索引，则可大大缩短候选路段的搜索时间，提高算法效率。

[0066] 图1所示为针对示例路网的分割方法。其中最上层空间被分为R1，R2；R3到R6为第二层空间；其余为第三层，即各个路段的MBR。该R树的数据结构如图2所示；

[0067] 在地图匹配过程中，可以通过GPS轨迹点的地理坐标快速找到其所在的大矩形(即处于非叶子结点的MBR)，继而根据R树存储的指针找到该矩形内所有路段，将它们作为候选路段。图1中，A，B，C为待匹配的三个数据点，体现了搜索待匹配路段时的三种情况。容易看出，A点位于R8矩形即叶子结点的MBR内，则可根据R树寻找上一层的矩形即R3，继而将R3内的两个路段列为当前状态的候选路段；B点位于R3内，则直接把R7、R8的对应路段列为候选；C点处于R1中，则将其中的R7、R8、R11、R12对应的路段都列为候选路段。

[0068] S2：对GPS轨迹数据进行子轨迹的划分；

[0069] 轨迹点的数据来源为GPS接收器的连续采集，在同一路段上，相邻轨迹点在行驶方向、行驶速度等方面都具有较强的相似性；在不同路段上，相邻轨迹点的各个属性则会有较明显的变化。如果将出行轨迹中性质相似的相邻轨迹点组成子轨迹，在各个子轨迹内部进行抽稀处理，此样本便可以极大程度地代替子轨迹。对抽稀产生的样本进行候选路段的搜索，并将其作为整个子轨迹的候选路段，便可以大幅提高搜索效率。同时，相比于简单的抽稀处理，能更准确地代表整个轨迹。

[0070] 子轨迹的划分通常由比较相邻点轨迹点的相似性实现，相似性超过规定阈值的点视为子轨迹点。相似性的计算很大程度上会受到轨迹点定位误差的影响，因而子轨迹的划分也应具有数据清洗功能。根据轨迹数据的位置实时变化率对GPS数据进行逐点处理，通过点间位置变化率与平均变化率的大小关系判断该点是否处于当前子轨迹。两点间的位置变化率又可分为经度平均变化率和纬度平均变化率。二者计算方法均为该点的经(纬)度值减去上一点的经(纬)度值的绝对值，再除以上一点的经(纬)度值，用公式表示为：

[0071]

[0072] 具体流程如下所示：

[0073] S21：创建一个子轨迹并作为当前子轨迹，从第一个点或当前点开始将前两个轨迹点加入，第三个轨迹点设为当前点；

[0074] S22：从当前点i开始遍历GPS轨迹点；

[0075] S23：计算当前点的位置变化率和当前子轨迹的平均位置变化率。平均位置变化率公式为：

[0076]

[0077] S24：判断当前点的位置变化率和当前子轨迹的平均位置变化率的大小关系，如图3所示。当i点满足r(i)lon≤1.5R(n)lon且r(i)lat≤1.5R(n)lat时，说明i点位于“1区”，位置变化率与当前子轨迹的平均值相差不大，认为其属于当前子轨迹，转到S25；否则，结束当前子轨迹，返回S21；

[0078] S25：将当前点加入当前轨迹，下一点作为当前点，返回S22。

[0079] S3：遍历所有子轨迹，对于每个子轨迹，将所有轨迹点等分为四部分，第一部分和第四部分保留所有点(即保留子轨迹的首尾)，而在中间两部分每两个点取样一个点，按顺序排列，生成整个轨迹的样本；

[0080] S4：使用维特比算法计算该样本的最优匹配道路：

[0081] S41：从样本起点出发，利用R树索引寻找候选路段；综合考虑轨迹点与各路段距离、前进方向的差异性，通过公式计算选择各个路段的概率P(X1j)，公式如下：

[0082]

[0083] 其中，dj为与第j个路段间的距离，取轨迹点到道路的垂线长度；θj为轨迹点与第j个路段间的前进方向夹角，取正值。

[0084] S42：从第二个样本点开始，通过公式P(Xij)＝P(Xi‑1)*P(Xi|Xi‑1)*P(Xij|Xi)  (4)，计算各个候选路段的观测概率P(Xij)，直至最后一个样本点；

[0085] P(Xij)为选择当前路段的概率；P(Xi‑1)为上一路段的概率；P(Xi|Xi‑1)为两状态间的转移概率，用来度量从上一个点到这一个点的前进过程中，从上一个点对应的某个路段到这个点对应的某个路段的代价，可由两轨迹点之间距离和两个路段上对应点之间距离之差度量；P(Xij|Xi)为当前状态中选择当前路段的概率，轨迹点离路段越远、前进方向与路段方向相差越小，该概率越大。

[0086] S43：找到最后一个状态中具有最大观测概率的候选路段，并由此进行回溯，得到各个状态的相应候选路段，直到样本起点；

[0087] S5：将回溯得到的整条路径作为该子轨迹的匹配路径，并将子轨迹内的各个点匹配到该路径的距离最小点上，完成匹配。

[0088] 图4为上述地图匹配算法的示意图。a‑b‑c‑d为一段连续轨迹(为方便展示，此处只绘出少数轨迹点)，R13、R14中分别有两个路段，共同被R6包围。根据本发明的子轨迹划分规则，得到a、b、c、d四段子轨迹。对于a、b、d，可以按照上述的方法，寻找非叶子结点矩形即R6，将其中的路段列为候选；对于c，由于其不在任一叶子结点内，直接将R6中的矩形列为候选；之后利用维特比算法计算各个候选概率，找到最大概率的路段，回溯得到整个路段；最后将轨迹内各个点匹配到相应路段的距离最小点上。

[0089] 仿真实验与结果分析

[0090] 数据源：本实施例使用的路网数据为北京市的OpenStreetMap数据；轨迹数据为微软2012年发布的北京市GPS轨迹数据集。

[0091] 软硬件环境：为了验证本方法的适用性，本次仿真选择普通配置的计算机进行实验，硬件环境方面，电脑型号为Legion Y7000P 2019，CPU为Intel(R)Core(TM)i7‑9750H CPU@2.60GHz 2.59GHz，内存为16.0GB。软件环境方面，编程语言Python的版本为3.8，电子地图采用ArcGIS软件显示。

[0092] 仿真实验

[0093] 建立R树：对OpenStreetMap数据建立R树索引。经过统计，共有1827个路段，因而创建的R树有1827个叶子结点。

[0094] 划分子轨迹：以一条由932个GPS点组成的轨迹为例，按照公式(1)进行经纬度变化率的求解，部分结果如表1所示。经纬度变化率从第二个轨迹点开始计算，故轨迹首点(表格第一行)经纬度变化率为空。

[0095] 表1经纬度变化率

[0096]

[0097] 按照公式(2)求解该轨迹的经纬度平均变化率，纬度平均变化率为1.59561E‑06，经度平均变化率为6.78495E‑07。比较经纬度变化率与经纬度平均变化率的大小，便可判断各个点是否为子轨迹起点。分析结果如表2所示，其中“<”表示轨迹点经纬度变化率小于平均变化率，“>”表示轨迹点经纬度变化率大于平均变化率。轨迹首点无经纬度变化率，故表格第一行的经纬度判断为空值，并将轨迹首点作为非起点处理。

[0098] 表2子轨迹起点的判断

[0099]

[0100] 处理后，整个轨迹的932个点被划分为26个子轨迹，最长子轨迹涵盖106个轨迹点，最短子轨迹只有3个轨迹点。

[0101] 候选路段搜索：用其中1个子轨迹进行仿真实验，其轨迹点坐标和行驶方向如表3所示，其中行驶方向的角度从正东按逆时针方向度量，90°为正北。首先按照算法步骤对该子轨迹进行抽样处理，得到表4所示的样本。后续实验通过该样本进行展示。

[0102] 表3某一子轨迹

[0103]

[0104] 表4子轨迹的样本

[0105]

[0106] 图5展示了一段轨迹，其中矩形为子轨迹的外包矩形，包围的10个点为该子轨迹，矩形中的点为表4所示的抽样结果。矩形为R树叶子结点和叶子结点上一级的父结点。使用R树搜索该子轨迹的候选路段，发现子轨迹外包矩形与路段1、4、5的外包矩形相交；进一步搜索它们的父结点，发现父结点的矩形也包括了路段2、3、6的外包矩形。因此将路段1、2、3、4、5、6作为该子轨迹的候选道路。如此确定整个子轨迹的候选路段，后续便无需逐子轨迹点搜索候选路段，大幅提高了算法效率。

[0107] 候选路段概率计算：通过路段数据点可计算出路段方向，如表5所示。首先使用公式(3)计算样本首点的6个状态概率，如选择候选路段1时，θj为2°，dj为1.8米，计算得到该节点概率为0.8312；之后计算第二个状态的概率，根据公式(4)得到共36个节点的概率；后续点同理，直到最后一点，最后一个状态的节点概率如表6所示，由于节点过多，只做部分展示。表中路径一列记录了到达该节点所经过的各个节点，概率一列则为通过该路径到达末尾状态的概率。从其中选择最大值，并进行回溯，发现各个状态选择的候选路段都为路段1。连接各个状态的候选路径得到的仍为路段1，最后子轨迹就匹配到路段1上。

[0108] 表5候选路段方向

[0109]

[0110] 表6末尾状态概率计算

[0111]

[0112] 仿真结果与分析

[0113] 图6展示了改进算法于北京两处取样路段的匹配效果，其中小点为匹配后的轨迹点。

[0114] 由图6可见，即使在比较复杂的路网，比如校园内，轨迹点也基本全部匹配到了道路上，说明改进算法的精度可以满足实际应用的要求。本发明提出的改进方法致力于提高地图匹配效率，下面进行效率分析。

[0115] 为验证算法效率，从实际GPS轨迹数据中截取1000、5000、10000、50000、100000、500000、1000000个连续轨迹点进行实验，分别使用传统的HMM地图匹配算法、使用R树改进的HMM地图匹配算法与使用R树和轨迹分段的HMM地图匹配算法进行仿真实验，分析结果如图7所示，其中柱形图代表不同数据量的整体匹配效率，折线图代表单点匹配效率。

[0116] 由图7可知，随着数据量增大单点匹配率逐渐减小，其主要原因是程序的编译时间在数据量小时占总运行时间的比重很大，而这种影响在数据量极大时会平均到各个点，几乎可以忽略不计。数据量较小时三种算法效率相差不大，但当数据量超过10000，仅使用R树对算法效率有一定的提高，而使用R树和轨迹分段的HMM地图匹配算法具有十分明显的优势：在数据量为50000、100000、500000、1000000时，使用两种改进的算法运行时间比传统HMM地图匹配算法分别减少了34％、46％、61％和69％。由此可以看出，本发明针对HMM的两种改进都能显著提高地图匹配效率，并且随着数据量的增大，这种效率的优势越来明显。当下用于智能交通领域的数据具有百万、千万甚至更高的数量级，而本发明提出的改进的HMM地图匹配算法在这种大量轨迹数据的应用场景下更加高效实用。

[0117] 结论：GPS轨迹数据是智能交通领域的重要数据源，而地图匹配是应用轨迹数据的关键一环。面对海量轨迹数据，提高地图匹配算法的效率至关重要。本发明在传统HMM地图匹配算法的基础上，结合R树空间索引和轨迹匹配方法，提出了一种快速地图匹配方法，同时在路网数据处理和轨迹数据处理两方面进行了效率优化，使算法在时效性上更具优势。通过验证，改进算法的效率在GPS轨迹数据量较大的情况下有明显提高，适用于轨迹数据量极大的应用场景。

[0118] 本领域的普通技术人员将会意识到，这里所述的实施例是为了帮助读者理解本发明的实施方法，应被理解为本发明的保护范围并不局限于这样的特别陈述和实施例。本领域的普通技术人员可以根据本发明公开的这些技术启示做出各种不脱离本发明实质的其它各种具体变形和组合，这些变形和组合仍然在本发明的保护范围内。