CN111307164A - 一种低采样率轨迹地图匹配方法 - Google Patents

Abstract

本发明公开一种低采样率轨迹地图匹配方法，包括以下步骤：首先对GPS轨迹进行噪音处理并建立路径索引；其次，搜索轨迹对应的候选路径，并使用候选路径的相似性对轨迹进行聚类；最后通过重采样提取聚类中心线，并将和聚类中心线LCSS距离最小的候选路径作为匹配结果。本发明的方法解决了极低采样率GPS轨迹地图匹配方法精度低的问题，同时也提高了地图匹配的效率。

Description

一种低采样率轨迹地图匹配方法

技术领域

本发明属于数据挖掘技术领域，涉及一种基于聚类的低采样率轨迹地图匹配方法。

背景技术

GPS轨迹数据是由一系列的GPS点数据组成，每个GPS点数据由必要的三元素<时间戳、精度、维度>和非必要元素<瞬时速度、瞬时角度>等组成，可以有效地记录移动物体的空间轨迹。随着定位设备Global Positioning System GPS的广泛使用，由定位设备所产生的轨迹数据被应用于各个领域。为了节省GPS信号接收器的能耗，会将GPS信号的接收间隔时间设置大于1分钟，因此产生的低采样率轨迹存在较大的不确定性，如果将这些低采样轨迹直接应用各领域会造成较大的偏差，最终导致人力、物力、财力的浪费。因此在轨迹预处理时需要将GPS低采样率轨迹匹配到道路网络上，以用于许多应用，例如城市移动计算，电子路网更新，运输分析和管理等。因此，高效且精准的低采样率地图匹配是急切需要的。

一直以来，轨迹的地图匹配是一个重要的研究领域。但是现有的地图匹配方法大多都是针对高采样率轨迹的，尽管有一些针对低采样率轨迹的地图匹配方法，但是这些方法在采样率较低时(时间间隔大于3分钟)匹配精度不高，或者需要第三方的高采样率轨迹。例如，通过时空分析每条低采样率轨迹对应的候选路径，然后从中求出最优的路径，或利用第三方高采样率的历史轨迹统计出每条道路上的历史车辆通行的频繁模式，然后根据频繁模式对每条待匹配的低采样率轨迹进行匹配。通过时空分析对单条轨迹依次匹配的方法通常具有两个不足。首先，该方法在采样率较低时匹配精度较低，其次该方法效率较低。

综上所述，低采样率地图匹配在如下两个方面有待深入研究：1.采样率较低时精度不高；2.匹配效率低的问题。

发明内容

针对上述问题，本发明的目的在于提供一种基于聚类的低采样率轨迹地图匹配方法，解决了基于时空分析轨迹地图匹配方法精度不高，效率低的问题。

为了实现上述任务，本发明采用以下技术方案：

一种低采样率轨迹地图匹配方法，本方法中用带权有向图G表示路网，本方法是为G中任意两点之间的低采样率GPS轨迹集合匹配最佳的路网路径，该低采样率GPS轨迹集合中包含多条低采样率GPS轨迹；具体包括如下步骤：

步骤一，对G建立R-tree空间索引，采用最短路径搜索法搜索G中A和B之间的多条最短路径，通过R-tree空间索引和最短路径搜索每条低采样率GPS轨迹中相邻GPS轨迹点之间的多条候选路径，组成每条低采样率GPS轨迹的候选路径集合；

步骤二，计算任意两条低采样率GPS轨迹trj_i和trj_j之间的非相似度值d_n(trj_i,trj_j),若d_n(trj_i,trj_j)小于阈值ε_s，则trj_i和trj_j组成互相邻近轨迹对；

其中，path_i和path_j分别表示低采样率GPS轨迹trj_i的候选路径集合和低采样率GPS轨迹trj_j的候选路径集合；path_i,φ为低采样率GPS轨迹trj_i的候选路径集合path_i中的第φ个候选路径；

为低采样率GPS轨迹trj_j的候选路径集合path_j中的第

个候选路径；path_i.count和path_j.coun分别表示path_i和path_j中的候选路径的数量；i、j均为自然数且i≠j；φ和

均为自然数；

表示path_i,φ与

之间的非相似性值；

其中，

代表通过LCSS算法计算出的path_i,φ和

之间的最长公共子序列中元素的个数；

步骤三、采用基于DBSCAN的聚类方法对所有互相邻近轨迹对进行聚类，得到多组轨迹类；

步骤四，提取每个轨迹类的中心线；

步骤41，标记该轨迹类中所有GPS轨迹点为未访问状态，并对该该轨迹类中所有低采样率GPS轨迹建立R-tree空间索引；

步骤42，在该轨迹类中所有轨迹的第一个GPS轨迹点p₁中随机选择一个作为种子轨迹点并将其设置为已访问状态；

步骤43，以种子轨迹点为圆心做两个半径分别为r和2r的同心圆C₁和C₂，然后利用步骤41中的R-tree空间索引搜索圆C₁中与种子轨迹点具有相似航向的处于未访问状态的GPS轨迹点，并标记为已访问状态，然后计算这些处在已访问状态的GPS轨迹点的质心，将该质心作为新生成的轨迹点p_new；

所述相似航向是指该GPS轨迹点与种子轨迹点之间的航向差小于阈值β；

步骤44，搜索同心圆C₁和C₂之间的处于未访问状态的GPS轨迹点，在同心圆C₁和C₂之间的处于未访问状态的GPS轨迹点中随机选择一个作为新的种子轨迹点p_seed；如果在同心圆C₁和C₂之间没有搜索到GPS轨迹点，则扩大同心圆的半径直到能搜索到GPS轨迹点为止；

步骤45，重复步骤43-44，直至遍历所有的GPS轨迹点，将所有的p_new和p_seed有序排列即可得到一条高采样率的GPS轨迹，将该条GPS轨迹作为该轨迹类的中心线；

步骤五，计算每个轨迹类的中心线与该轨迹类中所有候选路径之间的距离值，最小的距离值对应的候选路径即为该轨迹类匹配的最佳的路网路径。

步骤一中，得到每条低采样率GPS轨迹的候选路径集合后，对于每个候选路径集合，将该候选路径集合中每条候选路径的最短通行时间大于该候选路径集合对应的相邻GPS轨迹点之间的时间间隔的候选路径剔除。

具体的，步骤二中，0<ε_s<1。、

进一步，步骤四中，阈值β的取值范围界于0°和60°之间。

与现有技术相比，本发明具有以下效果：

本发明首先将计算出任意两条低采样率GPS轨迹之间的非相似度值进而得到互相邻近轨迹对；在此基础上，对将低采样率轨迹进行聚类，解决了基于时空分析轨迹地图匹配效率低和精度低的问题。

附图说明

图1是基于聚类的低采样率轨迹地图匹配整体框架图；

图2是轨迹聚类示意图；

图3是聚类中心线提取示意图；

图4是不同采样率下平均匹配精度对比图；

图5是不同采样率下平均匹配时间对比图。

具体实施方式

以下结合附图和实施例对本发明作进一步的说明。

以下本发明对涉及的相关概念做如下定义：

定义1路网。G＝(V,E)是带权有向图，其中V表示道路中节点的集合，E表示道路段的有向边集合，即有向路段集合。节点v_i∈V是路段的一个端点。一条边e_j∈E表示具有一个起始点e_j.start∈V和一个终点e_j.end∈V的一条路段。

定义2路段序列。路段序列由邻接的路段组成的序列，表示为path＝{e₁,e₂,…,e_m}，e_k代表一条路段并且e_k.end＝e_k+1.start(1≤k≤m)。路段序列path的起始端点和末尾端点表示为path.first，path.last并且path.first＝e₁.start，path.last＝e_m.end。

定义3GPS记录。一条GPS记录p是一个四元组，表示为p＝(t,lng,lat,dir)，t是GPS记录的时间戳，lng,lat,dir是GPS记录p在时刻t的经度、纬度、行驶角度。

定义4GPS轨迹。GPS轨迹是GPS记录组成的序列表示为trj＝{p₁,p₂,…,p_m}且p_i.t-p_i-1.t>0,1≤i≤m。

本发明的步骤4中所述的第一个GPS轨迹点p₁，即一条轨迹中以时间先后进行排序后的第一个轨迹点。

实施例1：

本实施例提供一种基于聚类的低采样率轨迹地图匹配方法，本方法是为低采样率GPS轨迹trj匹配最佳的路网路径，用带权有向图G＝(V,E)表示路网，E表示路网中有向路段集合，V表示有向路段的端点集合，多个有向路段邻接即组成路径，具体包括如下步骤：

步骤一、对G建立R-tree空间索引，采用最短路径搜索法搜索G中A和B之间的多条最短路径，通过R-tree空间索引和最短路径搜索每条低采样率GPS轨迹中相邻GPS轨迹点之间的多条候选路径，组成每条低采样率GPS轨迹的候选路径集合。

具体的，建立R-tree空间索引前，使用基于距离及速度的方法对低采样率集合中的轨迹进行除燥处理，之对路网中的路段建立R-tree空间索引；采用最短路径搜索算法搜索路网中两个路口之间的多条最短路径，然后使用hashtable数据结构对路网建立路径索引Path-Index。在路径索引Path-Index中搜索低采样率的GPS轨迹集合中每条轨迹的相邻GPS轨迹点之间的候选路径集合；

除噪处理具体方法为：采用公式(1)计算每条路径的最短通行时间σ，同时采用公式(2)计算相邻GPS点之间的时间间隔，并将最短通行时间大于相邻GPS点时间间隔的路径剔除；

t_k-1→k＝p_k.t-p_k-1.t(2)

其中，一条轨迹trj＝{p₁,p₂,…,p_k,…,p_n}，1≤k≤n，一条路径path＝{e₁,e₂,…,e_k,…,e_m}，1≤k≤m，k,m,n均为自然数，p_k表示轨迹trj中第k个GPS轨迹点，p_k.t表示轨迹trj中第k个GPS轨迹点的时间戳，e_k表示路径path中第k个路段，e_k.speedlimit表示一条路径path中第k个路段的最大限速，e_k.length表示一条路径path中第k个路段的长度，t_k-1→k表示轨迹点p_k-1和轨迹点p_k之前的时间差。

步骤二，计算任意两条低采样率GPS轨迹trj_i和trj_j之间的非相似度值d_n(trj_i,trj_j),若d_n(trj_i,trj_j)小于阈值ε_s，则trj_i和trj_j组成互相邻近轨迹对；

采用公式(3)计算候选路径path_i,φ和

之间的非相似性值d_s，并将d_s用于公式(4)计算轨迹trj_i和trj_j之间的非相似度值d_n,最后将d_n小于ε_s(0<ε_s<1)的轨迹设置为互相邻近轨迹对；

其中，path_i和path_j分别代表轨迹trj_i，trj_j的候选路径集合。path_i,φ，

分别表示轨迹trj_i的第φ个候选路径和轨迹trj_j的第

个候选路径。

代表通过LCSS算法计算出的路径path_i,φ和

之间的最长公共子序列中元素的个数，path_i.count和path_j.count分别代表路径集合path_i和path_j中路段的个数，

代表路径path_i,φ和

的d_s值小于ε_s的路径对的个数，其中LCSS为常规的最长公共子序列算法。

步骤三、使用基于DBSCAN的聚类算法对所有低采样率轨迹进行聚类，并得到多组轨迹类；

该聚类算法所需参数为最小邻近轨迹数MinTrjs,轨迹端点之间的距离阈值ε_l,轨迹之间非相似性阈值ε_s，通过步骤二得到每条低采样率轨迹的非相似度值小于ε_s的邻近轨迹，如果某条低采样率轨迹的邻近轨迹数量大于参MinTrjs,则该条轨迹被视为一个核心轨迹对象。

步骤四、对每个轨迹类提取类别的中心线；

具体步骤如下：

步骤41，标记一个类别中的所有轨迹中的所有轨迹点为未访问状态，并对该类别中的所有低采样率轨迹建立R-tree索引。

步骤42，在该类别中所有轨迹的第一个轨迹点p₁中随机选择一个未访问的轨迹点作为种子轨迹点p_seed，并将其种子轨迹点设置为已访问。

步骤43，以种子轨迹点p_seed为圆心做两个半径分别为r_s和2*r_s的同心圆C₁和C₂，然后借助R-tree搜索圆C₁中与种子轨迹点具有相似航行的未访问的轨迹点(搜索到的轨迹点与种子轨迹点之间的航向差小于阈值β)，并标记搜索到的轨迹点为已访问状态，然后计算这些轨迹点的中心点，将该质心作为新生成的轨迹点p_new。

步骤44，搜索同心圆C₁和C₂之间的未被访问的轨迹点，然后在这些轨迹点钟随机选择一个轨迹点作为新的种子轨迹点p_seed。如果在同心圆C₁和C₂之间没有搜索到轨迹点，则扩大圆的半径指导能搜索到轨迹点为止。

步骤45，重复步骤43-44，将新生成的多个轨迹点p_new有序排列即可得到一条重采样后的高采样率的轨迹，将该条轨迹作为类别的中心线。

步骤五、使用LCSS算法计算每条类别中心线和类别对应的候选路径之间的距离，并将距离最小的候选路径作为该类别中所有轨迹的最佳匹配路径。

优选的，在步骤一中，对GPS轨迹聚类前，先对GPS轨迹进行剔除噪声数据的预处理和路网R-tree索引的建立以及路网中节点之间多条路径的搜索并将这些路径以起始和结束节点的编号作为键,将路径作为值存储在hash table中作为路径索引Path-Index。

实施例2：

本实施例提供一种基于聚类的低采样率轨迹地图匹配方法，整体框架如图1，主要分为三层：数据预处理层、候选路径搜索及轨迹聚类层、轨迹匹配层，本方法的具体实施步骤如下：

第一部分，数据预处理：

本方法此处使用的剔除噪声数据的两种方法，均为常规方法，仅做简单说明：为避免轨迹数据中的噪声对最后匹配性能的影响，对低采样率的GPS原始轨迹数据进行预处理，将噪声数据进行剔除。搜索从路段节点v_i到v_j之间长度小于sp.length*1.2(sp.length代表从节点v_i到v_j的最短路径的长度)的k(k＝5)条路径并将这些路径以起始和结束节点的编号作为键，将路径作为值存储在hash table中作为路径索引Path-Index。

第二部分，对每条低采样率轨迹在路径索引中搜索轨迹候选路径并对不合理的路径进行过滤：在根据路网所建立的R-tree中及路网索引快速搜索轨迹的候选路径：对于轨迹trj＝{p₁,p₂,…,p_m},依次以每个GPS点p为圆心，以r(40m)为半径在路网的R-tree中搜索路段，同时在搜索过程中以角度β(60°)作为阈值，当道路的角度和轨迹的角度差大于阈值时，则剔除该路段；然后使用路段的编号在路径索引Path-Index中获取相邻GPS点之间的多条路径，最后利用路网的拓扑关系将上述得到的路段连接起来得到最终的候选路径，然后选取距离最短的k(k＝5)条完整的候选路径。

具体的，步骤21，对于轨迹trj_i＝{p₁,p₂,…,p_m}，如在图2中，有一条轨迹Trj₁＝{p₁,p₂,p₃}，以GPS点p1为圆心，以r为半径在路网的R-tree中搜索路段，如p1点在r半径内得到角度差值小于阈值β的边e₁，同样的方法可以得到p2对应的路段e₁₁；

步骤22，以e₁,e₁₁为键在路径索引Path-Index可以获取多条路径path＝{e₁e₂e₄e₈e₁₁,e₁e₃e₅e₈e₁₁,e₁e₃e₇e₁₀e₁₁,e₁e₂e₄e₅e₇e₁₀e₁₁}，使用速度限制可以剔除路径e₁e₂e₄e₅e₇e₁₀e₁₁，最终得到路径path＝{e₁e₂e₄e₈e₁₁,e₁e₃e₅e₈e₁₁,e₁e₃e₇e₁₀e₁₁}；

步骤23，重复步骤21-22，可以得到轨迹Trj₁中GPS点p2到p3之间的路径path₁＝{e₁₁e₁₄e₁₇}，最后将候选路径进行拼接，得到轨迹Trj₁的完整候选路径path₁＝{e₁e₂e₄e₈e₁₁e₁₄e₁₇,e₁e₃e₅e₈e₁₁e₁₄e₁₇,e₁e₃e₇e₁₀e₁₁e₁₄e₁₇}；

步骤24，重复步骤21-23，可以得到轨迹Trj₂，Trj₃对应的候选路径path₂＝{e₁e₂e₄e₈e₁₁e₁₄e₁₇,e₁e₃e₅e₈e₁₁e₁₄e₁₇}，path₃＝{e₁e₂e₄e₈e₁₁e₁₄e₁₇}。

第三部分，使用每条轨迹的候选路径对低采样轨迹聚类；

步骤31，对于步骤2中三条轨迹及其对应的候选路径，使用公式(4)计算这三条轨迹之间的非相似性；

其中阈值ε_s＝0.4，MinTrj＝2,将三条轨迹和参数代入DBSCAN聚类算法中，最终可以将这三条轨迹聚类为一个类别。

计算结果如下：

表1轨迹之间非相似度参数值对应表

d<sub>n</sub>	Trj<sub>1</sub>	Trj<sub>2</sub>	Trj<sub>3</sub>
				Trj<sub>1</sub>	X	0	0.33
Trj<sub>2</sub>	X	X	0
				Trj<sub>3</sub>	X	X	X

第四部分，对每个轨迹类使用滑动窗的方法提取每个类别的中心线；

步骤41，标记图2中三条轨迹的所有GPS轨迹点为未访问状态，并对这三条轨迹建立R-tree空间索引；

步骤42，在这三条轨迹的第一个GPS轨迹点p₁中随机选择一个轨迹点(此处选取Trj₂.P₁)作为种子轨迹点p_seed并将其设置为已访问状态；

步骤43，以种子轨迹点Trj₂.P₁为圆心做两个半径分别为r和2r(r＝50米)的同心圆C₁和C₂，然后利用步骤41中的R-tree空间索引搜索圆C₁中与种子轨迹点具有相似航向的处于未访问状态的GPS轨迹点(此处可以得到轨迹点Trj₁.P₁，Trj₂.P₁，Trj₃.P₁)，并标记为已访问状态，然后计算这些处在已访问状态的GPS轨迹点的质心P₁’，将该质心作为新生成的轨迹点p_new。

步骤44，搜索同心圆C₁和C₂之间的处于未访问状态的GPS轨迹点，在同心圆C₁和C₂之间的处于未访问状态的GPS轨迹点中随机选择一个作为新的种子轨迹点p_seed，假设此时在同心圆C₁和C₂之间没有搜索到GPS轨迹点，则扩大同心圆C₂的半径为5r时才搜索到轨迹点Trj₃.P₂，将轨迹点Trj₃.P₂作为新的种子轨迹点p_seed。

步骤45，重复步骤43-44，最后将所有的p_new和p_seed有序排列即可以得到最终的三条轨迹的中心线Trj’＝{P₁’,Trj₃.P₂,Trj₂.P₂,Trj₁.P₂,Trj₃.P₃,Trj₂.P₂,P₂’}

第五部分，使用LCSS算法计算轨迹Trj’和候选路径之间的距离，并将距离最小的候选路径作为该类别中所有轨迹的最佳匹配路径。

计算结果如下：

表2 轨迹段和候选路径之间的参数值对应表

候选路径	Trj’和候选路径之间LCSS距离
		e<sub>1</sub>e<sub>2</sub>e<sub>4</sub>e<sub>8</sub>e<sub>11</sub>e<sub>14</sub>e<sub>17</sub>	0.285
e<sub>1</sub>e<sub>3</sub>e<sub>5</sub>e<sub>8</sub>e<sub>11</sub>e<sub>14</sub>e<sub>17</sub>	0.428
		e<sub>1</sub>e<sub>3</sub>e<sub>7</sub>e<sub>10</sub>e<sub>11</sub>e<sub>14</sub>e<sub>17</sub>	0.487

和轨迹之间LCSS距离最小候选路径为{e₁e₂e₄e₈e₁₁e₁₄e₁₇}，即是三条GPS轨迹的匹配结果；

为了验证本文方法的有效性，实验在深圳市选取的小区域内通过仿真1980条GPS轨迹，其中采样间隔时间分别为2-10分钟，此外，道路网络包含7,007个道路顶点和7,949个路段。该GPS轨迹数据集由一系列带有时间戳标记的点构成，每点包含经度、纬度、实时方向信息。在度量实验性能时本文使用如下指标，

本文使用1980条轨迹进行匹配后的精度如图4所示，本文统计了GPS点不同采样间隔下算法的性能，对不同的采样率(2min，3min，4min，5min，6min，7min，8min，9min，10min)，使用GSMM方法将具有不同采样率的轨迹匹配到道路网络上。结果如图4所示。可以观察到，随着采样率的增加，准确度缓慢下降。本文的GSMM方法的匹配精度从92％降到79％，而STD-Matching方法的精度从91％降到68％，本文的匹配精确度高于传统的STD-Matching方法。随着采样率的增加，两个相邻GPS点之间的距离增大，导致GPS子轨迹的不确定性增加，从而影响匹配的结果。因为本文的方法使用相似轨迹之间进行互补，在时空分析方法的基础上提高了匹配的精度。

为了评估GSMM的效率，本文计算了每个GPS点的平均匹配时间。如图5显示随着采样率的增加，GSMM方法每个点的匹配时间从5.5毫秒增加到10.5毫秒，而STD-Matching的平均匹配时间从8.5毫秒增加到24.5毫秒。本文通过聚类可以批量匹配多条轨迹，因此，GSMM平均比STD-Matching更有效。

Claims (5)

1.一种低采样率轨迹地图匹配方法，本方法中用带权有向图G表示路网，本方法是为G中任意两点之间的低采样率GPS轨迹集合匹配最佳的路网路径，该低采样率GPS轨迹集合中包含多条低采样率GPS轨迹；其特征在于，具体包括如下步骤：

步骤一，采用最短路径搜索法搜索G中任意两点之间的多条最短路径，对G建立R-tree空间索引，通过R-tree空间索引和最短路径搜索每条低采样率GPS轨迹的多条候选路径，组成每条低采样率GPS轨迹的候选路径集合；

步骤二，计算任意两条低采样率GPS轨迹trj_i和trj_j之间的非相似度值d_n(trj_i,trj_j),若d_n(trj_i,trj_j)小于阈值ε_s，则trj_i和trj_j组成互相邻近轨迹对；

其中，path_i和path_j分别表示低采样率GPS轨迹trj_i的候选路径集合和低采样率GPS轨迹trj_j的候选路径集合；path_i,φ为低采样率GPS轨迹trj_i的候选路径集合path_i中的第φ个候选路径；

为低采样率GPS轨迹trj_j的候选路径集合path_j中的第

个候选路径；path_i.count和path_j.coun分别表示path_i和path_j中的候选路径的数量；i、j均为自然数且i≠j；φ和

均为自然数；

表示path_i,φ与

之间的非相似性值；

其中，

代表通过LCSS算法计算出的path_i,φ和

之间的最长公共子序列中元素的个数；

步骤三、采用基于DBSCAN的聚类方法对所有互相邻近轨迹对进行聚类，得到多组轨迹类；

步骤四，提取每个轨迹类的中心线；

步骤41，标记该轨迹类中所有GPS轨迹点为未访问状态，并对该轨迹类中所有低采样率GPS轨迹建立R-tree空间索引；

步骤42，在该轨迹类中所有轨迹的第一个GPS轨迹点p₁中随机选择一个作为种子轨迹点并将其设置为已访问状态；

步骤43，以种子轨迹点为圆心做两个半径分别为r和2r的同心圆C₁和C₂，然后利用步骤41中的R-tree空间索引搜索圆C₁中与种子轨迹点具有相似航向的处于未访问状态的GPS轨迹点，并标记为已访问状态，然后计算这些处在已访问状态的GPS轨迹点的质心，将该质心作为新生成的轨迹点p_new；所述相似航向是指该GPS轨迹点与种子轨迹点之间的航向差小于阈值β；

步骤44，搜索同心圆C₁和C₂之间的处于未访问状态的GPS轨迹点，在同心圆C₁和C₂之间的处于未访问状态的GPS轨迹点中随机选择一个作为新的种子轨迹点p_seed；

步骤45，重复步骤43-44，直至遍历所有的GPS轨迹点，每一次遍历都会产生一个新的p_new和p_seed，最后将所有的p_new和p_seed有序排列即可得到一条高采样率的GPS轨迹，将该条GPS轨迹作为该轨迹类的中心线；

步骤五，计算每个轨迹类的中心线与该轨迹类中所有候选路径之间的距离值，最小的距离值对应的候选路径即为该轨迹类匹配的最佳的路网路径。

2.如权利要求1所述低采样率轨迹地图匹配方法，其特征在于，步骤一中，得到每条低采样率GPS轨迹的候选路径集合后，对于每个候选路径集合，将该候选路径集合中每条候选路径的最短通行时间大于该候选路径集合对应的相邻GPS轨迹点之间的时间间隔的候选路径剔除。

3.如权利要求1所述低采样率轨迹地图匹配方法，其特征在于，步骤二中，0<ε_s<1。、

4.如权利要求1所述低采样率轨迹地图匹配方法，其特征在于，步骤四中，阈值β的取值范围界于0°和60°之间。

5.如权利要求1所述低采样率轨迹地图匹配方法，其特征在于，步骤44中，如果在同心圆C₁和C₂之间没有搜索到GPS轨迹点，则扩大同心圆的半径直到能搜索到GPS轨迹点为止。

Images