一种面向立体城市交通网的道路最优匹配方法

1.本发明属于数据分析、智慧交通等交叉技术领域，具体的说是一种面向立体城市交通网的道路最优匹配方法。

背景技术：

2.近些年随着gps技术的发展，支持gps技术的设备越来越多，车辆、智能手机、智能穿戴设备等都可以记录完整的轨迹路线，丰富的gps轨迹数据为智慧交通以及相关技术提供了数据基础，尤其是近几年网约车的兴起，网约车中配备的gps设备产生了大量轨迹数据，这些数据能够极大反应道路的状况，将这些数据聚合分析能够实现实时监控道路状态，为交通安全和交通效率方面提供数据基础。地图匹配(mm)技术是通过将惯性导航轨迹与现有的地图数据库中的道路特征进行比较来校正位置误差的技术，是智能交通系统(its)的重要组成部分。地图匹配技术不需要增加外部传感器，具有成本低、自主性强、可靠性高的优势，是进一步提高地面设备自主定位能力的有效途径，也是加快智慧交通建设最重要的基础。
3.理想情况下，车辆的gps点应位于道路连接线上，然而gps设备的信号易受到电磁干扰或功率限制的影响，产生大量噪声数据，且目前搭载在车辆上的gps设备大部分为低采样率设备(采样间隔大于30秒)，低采样率设备产生的数据中连续采样点之间的联系较低，且存在噪声数据的影响。地图匹配算法不仅是交通数据的可视化工具，更重要的是能够减少gps设备精度问题对匹配结果的影响，能够将尽可能多的采样点匹配到正确的道路上。目前国内外车辆导航系统中应用的现有方法已被证明是有效的，利用航位推算技术、差分gps、无线电信标或高精度载波相位接收机等提高gps定位精度。然而，由于这些方法依赖外部辅助装置，通常成本很高，相关技术也有点复杂，这些方法限制了它们在实际应用中的推广。为了降低地图匹配的成本，st-matching算法考虑了gps轨迹的空间和时间信息，并对gps点之间的加权相互影响建模，但算法的过程复杂，数据必须重复映射进行匹配，这限制了该算法的效率。

技术实现要素：

4.为了上述技术问题，本发明提供了一种面向立体城市交通网的道路最优匹配方法，解决了gps轨迹与路网的匹配准确率与效率的问题。
5.为了达到上述目的，本发明是通过以下技术方案实现的：
6.本发明是一种面向立体城市交通网的道路最优匹配方法，提高地图匹配准确率与效率，具体的包括如下步骤：
7.步骤1)候选点匹配，首先进行候选路段匹配，本发明为提高候选点匹配的准确率与效率，将原始路网数据与gps轨迹数据进行数据预处理，降低路网数据复杂度以及过滤gps轨迹噪声，利用简化后的路网数据构建三维kd树并利用该树进行空间域搜索，得到每个采样点的若干候选路段，然后使用web墨卡托投影进行候选点的计算。
8.步骤2)位置上下文分析，gps采样点与候选点之间以及相邻候选点之间都存在相关性，通过空间分析、时间分析以及道路分析对所有路径进行权重计算，并提出三个约束条件，当某些路径不满足所提出的约束条件时会被过滤，不参与后续计算，只有满足约束条件的路径才会被保留，参与下一步计算。
9.步骤3)相互影响建模，连续的gps采样点之间会相互影响，某一点越靠近一点，对该点的影响就越大。首先，根据筛选出的候选点创建候选图其中表示各个采样点的候选点集合，ε表示前一个采样点的候选点到当前采样点的候选点之间的路径集合。图中包含各个相邻采样点的候选点构成的路径，再以时间分析、空间分析以及道路分析为基础，构建静态评分矩阵m，根据矩阵m，相互影响建模为n-1维距离权重矩阵w。
10.步骤4)交互式投票，首先通过遍历上述步骤生成的候选图，计算所有候选点的局部最优路径，局部最优路径可以反映最终匹配路径所经过的路径的可能性。如果路径(用p表示)被更多的路径所包含，则路径p称为最终路径一部分的概率就越大；如果路径p没有被任何局部最优路径所包含，则最终匹配路径不包括该路径p；再根据每个候选点的局部最优路径，对每条路径进行投票，每两个相邻采样点之间的候选点形成的路径只选出一个票数最大的，最终选出的所有子路径拼接为最终路径。
11.其中所述步骤1)具体如下：
12.步骤11)首先对原始gps轨迹数据进行预处理，gps轨迹数据一般为出租车生成的轨迹数据，在原始gps轨迹数据中包含部分车辆静止时采集到的gps点，需要删除这些点，因为车辆在静止时gps设备采集的数据集中在某一个区域呈现不规则形状。在这种情况下，采样点之间的位置信息为概率性波动，这会干扰采样点间的相互影响，导致后续的计算中产生大量噪声且增加计算时长；然后对原始路网数据进行简化，现有的路网数据均为未优化的数据，在路口的表示上，通常有多少个道路交叉点就有多少个路口，如果某个交通岗道路很多，就会产生大量交叉点，进而增加路网中路口的数量，增加路网复杂度。应该将属于同一交通岗的所有道路交叉点合并为一个路口，这样可以简化路网数据，加快有关路网的计算，如查最短路径以及其相关计算。
13.步骤12)首先匹配候选路段，pi，i＝0,1,
…
,n-1，都有候选点其中n为采样点个数，m为候选点个数，本发明使用基于kd树的k近邻算法knn来获取候选路段，将静态路网数据建模为三维kd树，然后通过kd树出距离采样点最近的候选路段。为了将球面坐标系中的gps数据应用到knn算法，我们采用以下公式将采样点以及路网使用的球面坐标系转换为三维笛卡尔坐标系后，构建三维kd树。
14.x:r
×
cosφ
×
cosθ
15.y:r
×
cosφ
×
sinθ
16.z:r
×
sinφ
17.其中，r为地球半径，θ、φ分别为经度、纬度对应的弧度，在构建完三维kd树后，knn算法使用采样点与候选路段之间的欧几里得距离以及车辆方向与候选路段方向之间的夹角来确定候选路段，其公式为：
18.q(t)＝αd(t)+βa(t)
19.其中，t为时间表，α与β表示权重，d(t)表示车辆采样点与候选路段之间的垂直距
离的贡献度：
[0020][0021]
其中pc为车辆位置，pr为车辆在候选路段上的投影位置，σ
′
为位置误差的标准差。车辆行驶方向与候选路段间的方向夹角贡献度：
[0022][0023]
其中表示车辆的行驶方向，表示候选路段的方向，θ表示车辆方向与候选路段方向的夹角。车辆位置与候选路段之间的垂直距离使用海伦公式计算，其中p,a,b,c分别为三角形的半周长以及3条边长。
[0024]
步骤13)根据候选路段的匹配结果，使用web墨卡托投影来确定候选路段上的候选点。考虑把地球椭球体假设为正球体，取地球半径r＝6378137m，有a＝b＝r，第一偏心率e＝0。web墨卡托投影公式为：
[0025][0026]
车辆采样点与候选路段之间存在两种关系：一是过采样点且垂直于路段的线段与该路段相交，这种关系候选点为垂线与路段的交点；另一种关系是过采样点且垂直于路段的线段与该路段不相交，这种情况候选点只能选择距离采样点最近的候选路段的端点。将采样点以及与其对应的候选路段通过web墨卡托投影到平面坐标系后，根据上述车辆采样点与候选路段之间的关系，选出对应候选路段的候选点。
[0027]
所述步骤2)具体如下：
[0028]
步骤21)gps点的测量误差满足高斯分布n(μ,σ2)，其观测概率为：
[0029][0030]
其中是采样点pi的候选点，是从候选到采样点pi的欧几里得距离，μ是正态分布的方差，σ为正态分布的标准差。
[0031]
从候选点到候选点的空间分析函数定义为：
[0032][0033]
其中是过渡概率，t为采样点p
i-1
的候选点索引，s为采样点pi的候选点索引，n为概率，n是采样点个数，i是采样点的索引，目的是测量两个连续候选点之间的最短路径和直路径的相似性，定义为：
[0034][0035]
其中d
i-1
→i是采样点p
i-1
到采样点pi的欧几里得距离，ω
(i-1,t)
→
(i,s)
是从候选到
的最短路径的长度。
[0036]
步骤22)在没有交通事故的情况下，车速一般接近道路限速。因此，适当的时间分析函数应在道路限速附近获得最大值。时间分析函数定义为：
[0037][0038]
其中v
(i-1,t)
→
(i,s)
是从候选点到的最短路径的加权速度限制，是沿着候选点至之间最短路径行驶的车辆的平均速度。
[0039]
步骤23)在地图中，道路通常被分为几个级别，每个级别都有不同的道路限速。高架路的水平高于地面道路，即高架路的限速大于地面道路。因此，我们使用道路水平系数来模拟车辆在高限速道路上停留的趋势。的道路水平系数(rlf)定义为：
[0040][0041]
其中vs和vd表示和所在道路的速度限制。综上，路径的综合权重函数为：
[0042][0043]
步骤24)首先，在真实的路网结构中，两个连续采样点的候选点之间可能没有可达道路；其次，根据大量实验结论，错误匹配路径权重值总是小于1.0
×
10-5
，而正确匹配路径的权重值总是大于1.0
×
10-5
；最后，路网结构不是平面的，可能有立交桥或城市环岛等立体结构，而投影的结果是在平面坐标系中，因此，可能会将真正属于被遮挡道路的候选点投影到了其上面的道路上。结合以上三点分析，为了过滤错误数据减少后续计算负担，我们提出了以下三个约束：
[0044]
约束1：
[0045]
相邻采样点p
i-1
的各个候选点之间的连通性需符合真实路网结构，在路网结构中查询到最短路径，即匹配路径在路网结构中真实存在且能够在合理时间内可到达；
[0046]
约束2：
[0047]
设两个相邻匹配点的候选点之间的权重的阈值θ＝1.0
×
10-5
，当路径的权重小于θ时则被视为错误匹配路径，此路径不参与后续计算；
[0048]
约束3：
[0049]
根据不同道路拥有不同的限速这一特性，通过车辆的行驶速度与道路限速的关系进行判断，设为车辆沿着候选点到候选点之间最短路径行驶的平均速度，为所经过的所有道路的加权平均限速，当所经过的所有道路的加权平均限速，当时，其中1≤α≤2，路径被视为错误的匹配路径。
[0050]
所述步骤3)具体如下：
[0051]
步骤31)我们以上一节提出的位置上下文分析为建模基础，采用空间分析以及时
间分析两个方面来衡量两个连续候选点之间的影响。在计算各个采样点对应的各个候选点之间相互影响的权重之前，我们构建了一个静态评分矩阵：
[0052]
m＝diag{m
(1)
,m
(2)
,
…
,m
(n-1)
}
[0053]
其中q
i-1
与qi分别为采样点p
i-1
与pi的候选点个数。此静态评分矩阵中的每个项目仅考虑两个连续点的信息，表示候选点的权重。并不反映它们之间的相互影响。因此，我们可以将其构建为静态矩阵，以减少计算相互影响的权重时的计算负担。
[0054]
步骤3-2将采样点间的相互影响建模为(n-1)维距离权重矩阵，定义如下：
[0055][0056]
其中，dist(pi,pj)是采样点pi和pj之间的欧几里得距离，β是相对于道路网的参数，e为自然常数，距离权重矩阵给出了所有其他点到pi的距离影响的权重，对于i＝1,2,
…
,n-1受距离影响的权重计算为：
[0057][0058]
其中：ω为距离权重矩阵，m为静态评分矩阵，i和j是采样点的索引，q
i-1
与qi分别为采样点p
i-1
与pi的候选点个数。
[0059]
步骤33)在得到每个采样点的权重矩阵后，根据筛选出的候选点创建候候选图步骤33)在得到每个采样点的权重矩阵后，根据筛选出的候选点创建候候选图其中表示各个采样点的候选点集合，表示前一个采样点的候选点到当前采样点的候选点之间的路径集合，通过分析可知，路径到必须同时满足三个约束条件时才会存在边每个节点都拥有观测概率属性，即表示该候选点与其采样点的观测概率，每条边都拥有累积权重与投票数属性，用于后续投票计数。
[0060]
所述步骤4)具体如下：
[0061]
步骤41)：局部最优路径反映最终匹配路径所经过的路径的可能性，如果路径被更多的路径所包含，则路径称为最终路径一部分的概率就越大；如果路径路径没有被任何局部最优路径所包含，则最终匹配路径不包括该路径对于采样点pi的每个候选点其中n为采样点个数，m为设置的候选点个数，遍历每个候选点当一个候选点被遍历时，假设该候选点就是最终匹配阶级过中正确的匹配点，到一条通过点的概率最大的路径作为局部最优路径，累计权重计权重计权重是的权重，受pi和pj的距离影响，当i＝0时，计算所有点的累计权重后，即可得到每个候选点的局部最优路径；
[0062]
步骤42)：在到每个候选点的局部最优路径后，得到了一组局部最优路径，通过对每一个点的局部最优路径进行投票，选出投票数最多的一条路径作为最终匹配的路
径，具体为：遍历第四阶段生成的候选图对图的所有边进行投票，最后筛选出每两个相邻采样点中投票最多的子路径作为最终匹配子路径，最后，所有子路径拼接成最终的最优匹配路径。
[0063]
本发明的有益效果是：
[0064]
(1)简化了原始路网数据，将同一交通岗的多个交叉点视为同一路口，减少了大量有关路网的计算，提高算法效率。
[0065]
(2)考虑路网数据为三维结构，将大地坐标系转换为三维笛卡尔坐标系，得益于kd树优秀的性能，取消knn查邻近边的范围阈值，采用全局搜索，增加候选路段匹配的准确率。
[0066]
(3)本发明在已选出侯选路段的基础上使用web墨卡托投影确定候选点，并分两种情况讨论候选点的选取，提高了算法准确率。
[0067]
(4)本发明考虑采样点与候选点之间以及采样点与采样点、候选点与候选点之间的关系对其进行相互影响建模，在存在较多噪声的数据集中也能拥有较高的准确率。
附图说明
[0068]
图1是本发明的整体流程。
[0069]
图2是本发明查局部最优路径算法。
[0070]
图3是本发明候选边投票算法。
[0071]
图4是本发明匹配方法的流程图。
具体实施方式
[0072]
以下将以图式揭露本发明的实施方式，为明确说明起见，许多实务上的细节将在以下叙述中一并说明。然而，应了解到，这些实务上的细节不应用以限制本发明。也就是说，在本发明的部分实施方式中，这些实务上的细节是非必要的。
[0073]
本发明采用较经济的方案，在以下方面进行改进：路径上权重的计算不是简单的求和计算，避免了如果错误候选路径的累积权重远大于前几个候选点中的真正匹配路径，即使错误路径在其后续候选中的权重相对较小，错误路径的最终累积权重也将大于正确路径的问题；现有的路网数据均为未优化的数据，在路口的表示上，通常有多少个道路交叉点就有多少个路口，如果某个交通岗道路很多，就会产生大量交叉点，进而增加路网中路口的数量，增加路网复杂度。应该将属于同一交通岗的所有道路交叉点合并为一个路口，这样可以简化路网数据，加快有关路网的计算，如查最短路径以及其相关计算；考虑城市道路是立体结构，因为在地图投影计算中虽然是二维投影，但现实道路存在三维形式，且大部分三维形式的道路上层道路与下层道路拥有不同的属性，如高架桥及其下方的道路，在匹配过程中不应将其视为同一条道路。本发明简化了路网结构，将路网构建为三维kd树，应用knn算法选出候选路段，使用web墨卡托投影匹配候选点，通过位置上下文分析、三个约束条件以及相互影响建模来考虑采样点之间以及候选点之间的相互影响，通过计算的权重构建候选图，计算每个候选点的局部最优路径，最后根据候选图与局部最优路径进行交互式投票，最终选出一条概率最大的路径作为最终的匹配路径。
[0074]
具体的，本发明的面向立体城市交通网的道路最优匹配方法包括如下步骤：
[0075]
步骤1)候选点匹配，首先进行候选路段匹配，本发明为提高候选点匹配的准确率与效率，将原始路网数据与gps轨迹数据进行数据预处理，降低路网数据复杂度以及过滤gps轨迹噪声，利用简化后的路网数据构建三维kd树并利用该树进行空间域搜索，得到每个采样点的若干候选路段，然后使用web墨卡托投影进行候选点的计算。
[0076]
其中所述步骤1)具体如下：
[0077]
步骤11)首先对原始gps轨迹数据进行预处理，gps轨迹数据一般为出租车生成的轨迹数据，在原始gps轨迹数据中包含部分车辆静止时采集到的gps点，需要删除这些点，因为车辆在静止时gps设备采集的数据集中在某一个区域呈现不规则形状。在这种情况下，采样点之间的位置信息为概率性波动，这会干扰采样点间的相互影响，导致后续的计算中产生大量噪声且增加计算时长；然后对原始路网数据进行简化，现有的路网数据均为未优化的数据，在路口的表示上，通常有多少个道路交叉点就有多少个路口，如果某个交通岗道路很多，就会产生大量交叉点，进而增加路网中路口的数量，增加路网复杂度。应该将属于同一交通岗的所有道路交叉点合并为一个路口，这样可以简化路网数据，加快有关路网的计算，如查最短路径以及其相关计算。
[0078]
步骤12)首先匹配候选路段，pi，i＝0,1,
…
,n-1，都有候选点其中n为采样点个数，m为候选点个数，本发明使用基于kd树的k近邻算法knn来获取候选路段，将静态路网数据建模为三维kd树，然后通过kd树出距离采样点最近的候选路段。为了将球面坐标系中的gps数据应用到knn算法，我们采用以下公式将采样点以及路网使用的球面坐标系转换为三维笛卡尔坐标系后，构建三维kd树。
[0079]
x:r
×
cosφ
×
cosθ
[0080]
y:r
×
cosφ
×
sinθ
[0081]
z:r
×
sinφ
[0082]
其中，r为地球半径，θ、φ分别为经度、纬度对应的弧度，在构建完三维kd树后，knn算法使用采样点与候选路段之间的欧几里得距离以及车辆方向与候选路段方向之间的夹角来确定候选路段，其公式为：
[0083]
q(t)＝αd(t)+βa(t)
[0084]
其中，t为时间表，α与β表示权重，d(t)表示车辆采样点与候选路段之间的垂直距离的贡献度：
[0085][0086]
其中pc为车辆位置，pr为车辆在候选路段上的投影位置，σ
′
为位置误差的标准差。车辆行驶方向与候选路段间的方向夹角贡献度：
[0087][0088]
其中表示车辆的行驶方向，表示候选路段的方向，θ表示车辆方向与候选路段方向的夹角。车辆位置与候选路段之间的垂直距离使用海伦公式
计算，其中p,a,b,c分别为三角形的半周长以及3条边长。
[0089]
步骤13)根据候选路段的匹配结果，使用web墨卡托投影来确定候选路段上的候选点。考虑把地球椭球体假设为正球体，取地球半径r＝6378137m，有a＝b＝r，第一偏心率e＝0。web墨卡托投影公式为：
[0090][0091]
其中：θ为经度、a为地球长轴，b为地球短轴，为纬度，x和y为web墨卡托投影到二维平面的两个轴。
[0092]
车辆采样点与候选路段之间存在两种关系：一是过采样点且垂直于路段的线段与该路段相交，这种关系候选点为垂线与路段的交点；另一种关系是过采样点且垂直于路段的线段与该路段不相交，这种情况候选点只能选择距离采样点最近的候选路段的端点。将采样点以及与其对应的候选路段通过web墨卡托投影到平面坐标系后，根据上述车辆采样点与候选路段之间的关系，选出对应候选路段的候选点。
[0093]
步骤2)位置上下文分析，gps采样点与候选点之间以及相邻候选点之间都存在相关性，通过空间分析、时间分析以及道路分析对所有路径进行权重计算，并提出三个约束条件，当某些路径不满足所提出的约束条件时会被过滤，不参与后续计算，只有满足约束条件的路径才会被保留，参与下一步计算。
[0094]
所述步骤2)具体如下：
[0095]
步骤21)gps点的测量误差满足高斯分布n(μ,σ2)，其观测概率为：
[0096][0097]
其中是采样点pi的候选点，是从候选到采样点pi的欧几里德距离，μ是正态分布的方差，σ为正态分布的标准差。从候选点到候选点的空间分析函数定义为：
[0098][0099]
其中是过渡概率。目的是测量两个连续候选点之间的最短路径和直路径的相似性。定义为：
[0100][0101]
其中d
i-1
→i是采样点p
i-1
到采样点pi的欧几里得距离，ω
(i-1,t)
→
(i,s)
是从候选到的最短路径的长度。
[0102]
步骤22)在没有交通事故的情况下，车速一般接近道路限速。因此，适当的时间分析函数应在道路限速附近获得最大值。时间分析函数定义为：
[0103][0104]
其中v
(i-1,t)
→
(i,s)
是从候选点到的最短路径的加权速度限制，是
沿着候选点至之间最短路径行驶的车辆的平均速度。
[0105]
步骤23)在地图中，道路通常被分为几个级别，每个级别都有不同的道路限速。高架路的水平高于地面道路，即高架路的限速大于地面道路。因此，我们使用道路水平系数来模拟车辆在高限速道路上停留的趋势。的道路水平系数(rlf)定义为：
[0106][0107]
其中vs和vd表示和所在道路的速度限制。综上，综上，路径的综合权重函数为：
[0108][0109]
步骤24)首先，在真实的路网结构中，两个连续采样点的候选点之间可能没有可达道路；其次，根据大量实验结论，错误匹配路径权重值总是小于1.0
×
10-5
，而正确匹配路径的权重值总是大于1.0
×
10-5
；最后，路网结构不是平面的，可能有立交桥或城市环岛等立体结构，而投影的结果是在平面坐标系中，因此，可能会将真正属于被遮挡道路的候选点投影到了其上面的道路上。结合以上三点分析，为了过滤错误数据减少后续计算负担，我们提出了以下三个约束：
[0110]
约束1：
[0111]
相邻采样点的各个候选点之间的连通性需符合真实路网结构，可在路网结构中查询到最短路径，即匹配路径在路网结构中真实存在且能够在合理时间内可到达。
[0112]
约束2：
[0113]
设两个相邻匹配点的候选点之间的权重的阈值θ＝1.0
×
10-5
。当路径的权重小于θ时则被视为错误匹配路径，此路径不参与后续计算。
[0114]
约束3：
[0115]
可以根据不同道路拥有不同的限速这一特性，通过车辆的行驶速度与道路限速的关系进行判断。设为车辆沿着候选点到候选点之间最短路径行驶的平均速度，为所经过的所有道路的加权平均限速。当所经过的所有道路的加权平均限速。当时，其中1≤α≤2，路径被视为错误的匹配路径。
[0116]
步骤3)相互影响建模，连续的gps采样点之间会相互影响，某一点越靠近一点，对该点的影响就越大。首先，根据筛选出的候选点创建候选图其中表示各个采样点的候选点集合，表示前一个采样点的候选点到当前采样点的候选点之间的路径集合。图中包含各个相邻采样点的候选点构成的路径，再以时间分析、空间分析以及道路分析为基础，构建静态评分矩阵m，根据矩阵m，相互影响建模为n-1维距离权重矩阵w。
[0117]
所述步骤3)具体如下：
[0118]
步骤31)我们以上一节提出的位置上下文分析为建模基础，采用空间分析以及时间分析两个方面来衡量两个连续候选点之间的影响。在计算各个采样点对应的各个候选点之间相互影响的权重之前，我们构建了一个静态评分矩阵：
[0119]
m＝diag{m
(1)
,m
(2)
,
…
,m
(n-1)
}
[0120]
其中q
i-1
与qi分别为采样点p
i-1
与pi的候选点个数。此静态评分矩阵中的每个项目仅考虑两个连续点的信息，表示候选点的权重。并不反映它们之间的相互影响。因此，我们可以将其构建为静态矩阵，以减少计算相互影响的权重时的计算负担。
[0121]
步骤32)我们将采样点间的相互影响建模为(n-1)维距离权重矩阵，定义如下：
[0122][0123]
其中，dist(pi,pj)是采样点pi和pj之间的欧几里得距离，β是相对于道路网的参数。此矩阵给出了所有其他点到pi的距离影响的权重。对于i＝1,2,
…
,n-1受距离影响的权重可计算为：
[0124][0125]
其中：ω为距离权重矩阵，m为静态评分矩阵，i和j是采样点的索引，q
i-1
与qi分别为采样点p
i-1
与pi的候选点个数。
[0126]
步骤33)在得到每个采样点的权重矩阵后，我们根据上一节筛选出的候选点创建候候选图其中表示各个采样点的候选点集合，表示前一个采样点的候选点到当前采样点的候选点之间的路径集合，通过上一节的分析可知，路径到必须同时满足三个约束条件时才会存在边每个节点都拥有观测概率属性，即表示该候选点与其采样点的观测概率，每条边都拥有累积权重与投票数属性，用于后续投票计数。
[0127]
步骤4)交互式投票，首先通过遍历上述步骤生成的候选图，计算所有候选点的局部最优路径，局部最优路径可以反映最终匹配路径所经过的路径的可能性。如果路径(用p表示)被更多的路径所包含，则路径p称为最终路径一部分的概率就越大；如果路径p没有被任何局部最优路径所包含，则最终匹配路径不包括该路径p；再根据每个候选点的局部最优路径，对每条路径进行投票，每两个相邻采样点之间的候选点形成的路径只选出一个票数最大的，最终选出票数最大的路径作为最终路径。
[0128]
所述步骤4)具体如下：
[0129]
步骤41)局部最优路径可以反映最终匹配路径所经过的路径的可能性。如果路径(用p表示)被更多的路径所包含，则路径p称为最终路径一部分的概率就越大；如果路径p没有被任何局部最优路径所包含，则最终匹配路径不包括该路径p。对于采样点pi的每个候选点其中n为采样点个数，m为设置的候选点个数，遍历每个候选点当一个候选点被遍历时，我们假设该候选点就是最终匹配阶级过中正确的匹配点，到一条通过点的概率最大的路径作为局部最优路径。累计权重的概率最大的路径作为局部最优路径。累计权重是的权重，受pi和pj的距离影响。计算所有点的累计权重后，即可得到每个候选点的局部最优路径。
[0130]
步骤42)在到每个候选点的局部最优路径后，我们得到了一组局部最优路径。通过对每一个点的局部最优路径进行投票，选出投票数最多的一条路径作为最终匹配的路径。具体的：遍历第四阶段生成的候选图对图的所有边进行投票，最后筛选出每两个相邻采样点中投票最多的子路径作为最终匹配路径的子路径，最后，所有子路径拼接成最终的最优匹配路径。
[0131]
在具体实施中，选取的gps轨迹数据坐标系为wgs84坐标系，路网数据为openstreetmap提供的osm格式的路网数据。首先对以上数据进行预处理，gps轨迹点需删除车辆未移动或移动距离很短的点，因为这种情况下gps设备采集的数据集中在某一个区域呈现不规则形状，采样点之间的位置信息为概率性波动，这会干扰采样点间的相互影响，导致后续的计算中产生大量噪声且增加计算时长；路网数据需简化结构，合并同一十字路口的所有交叉点视为同一交叉点，降低路网中交点个数。在数据处理完成后，将路网数据与gps轨迹数据通过转换公式转换为三维笛卡尔坐标，然后将转换后的路网数据构建三维kd树，通过knn算法在该树中查每个gps轨迹点的候选路段，根据每个采样点的若干候选路段，将gps轨迹点与其对应的若干候选路段通过web墨卡托投影计算出对应的候选点。此时得到了每个gps轨迹点对应的若干候选点，通过位置上下文分析中时间分析、空间分析以及道路分析，计算出相邻候选点的权重，在计算过程中，舍弃不满足三个约束条件的路径，约束1保证了后续参与运算的数据都符合实际路网结构，不会出现不存在的路径；约束2保证了不会出现下述情况：如果错误的候选路径的累积权重大于前几个正确候选路径的权重，即便在后续候选中权值逐渐减小，但最终累积权重有概率大于正确路径的权重，导致生成错误的结果；约束3由于考虑了路网的三维结构，通过限速与车辆行驶速度的关系提高了匹配候选路径的准确性。以上三点约束能够在参与后续计算之前过滤掉大部分的错误路径，减少运算时间。连续的gps采样点之间会相互影响，通过对采样点之间进行相互影响建模，得到距离权重矩阵φ，然后再创建候选图每条边都拥有累积权重与投票数属性。根据生成的候选图，通过公式计算累计权重，是的权重，受pi和pj的距离影响，通过计算累计权重得到了每个候选点的局部最优路径。最后遍历每个候选点的局部最优路径对每条路径进行投票，票数最多的路径为最优匹配路径。

技术特征：

1.一种面向立体城市交通网的道路最优匹配方法，其特征在于：所述道路最优匹配方法包括以下步骤：步骤1、候选点匹配，首先进行候选路段匹配，将原始路网数据与gps轨迹数据进行数据预处理，降低路网数据复杂度以及过滤gps轨迹噪声，得到简化的路网数据，利用简化后的路网数据构建三维kd树并利用所述三维kd树进行空间域搜索，得到每个采样点的若干候选路段，再根据候选路段进行候选点的计算；步骤2、位置上下文分析，gps采样点与候选点之间以及相邻候选点之间都存在相关性，通过空间分析、时间分析以及道路分析对所有路径进行权重计算，并提出三个约束条件，当某些路径不满足所提出的约束条件时会被过滤，不参与后续计算，只有满足约束条件的路径才会被保留，参与下一步计算；步骤3、相互影响建模：首先，根据筛选出的候选点创建候选图其中表示各个采样点的候选点集合，ε表示前一个采样点的候选点到当前采样点的候选点之间的路径集合，图中包含各个相邻采样点的候选点构成的路径，再以时间分析、空间分析以及道路分析为基础，构建静态评分矩阵m，根据静态评分矩阵m，相互影响建模为n-1维距离权重矩阵w；步骤4、交互式投票，首先通过遍历步骤3生成的候选图，计算所有候选点的局部最优路径，局部最优路径反映最终匹配路径所经过的路径的可能性，如果路径被更多的路径所包含，则路径成为最终路径一部分的概率就越大；如果路径没有被任何局部最优路径所包含，则最终匹配路径不包括该路径再根据每个候选点的局部最优路径，对每条路径进行投票，每两个相邻采样点之间的候选点形成的路径只选出一个票数最大的，最终选出的所有子路径拼接为最终路径。2.根据权利要求1所述的一种面向立体城市交通网的道路最优匹配方法，其特征在于：所述步骤1具体包括如下步骤：步骤1-1：对原始gps轨迹数据进行预处理，gps轨迹数据为出租车生成的轨迹数据，在原始gps轨迹数据中包含部分车辆静止时采集到的gps点，删除这些gps点；然后将属于同一交通岗的所有道路交叉点合并为一个路口，简化路网数据，加快有关路网的计算；步骤1-2：匹配候选路段，采样点p
i
，i＝0,1,
…
,n-1，其中n为采样点个数，i是采样点的索引，采样点p
i
的候选点为其中m为候选点个数，j是每个采样点的候选点索引，使用基于三维kd树的k近邻算法knn来获取候选路段，将静态路网数据建模为三维kd树，然后通过kd树出距离采样点最近的候选路段；步骤1-3：根据候选路段的匹配结果，使用web墨卡托投影来确定候选路段上的候选点，把地球椭球体假设为正球体，取地球半径r＝6378137m，有a＝b＝r，第一偏心率e＝0，web墨卡托投影公式为：其中：θ为经度、a为地球长轴，b为地球短轴，为纬度，x和y为web墨卡托投影到二维平面的两个轴。
3.根据权利要求2所述的一种面向立体城市交通网的道路最优匹配方法，其特征在于：步骤1-2中，为了将球面坐标系中的gps数据应用到knn算法，采用以下公式将采样点以及路网使用的球面坐标系转换为三维笛卡尔坐标系后，构建三维kd树：x:r
×
coscp
×
cosθy:r
×
coscp
×
sinθz:r
×
sinφ其中，r为地球半径，θ、φ分别为经度、纬度对应的弧度。在构建完三维kd树后，knn算法使用采样点与候选路段之间的欧几里得距离以及车辆方向与候选路段方向之间的夹角来确定候选路段，其公式为：q(t)＝αd(t)+pa(t)其中，t为时间表，α与β表示权重，d(t)表示车辆采样点与候选路段之间的垂直距离的贡献度：其中p
c
为车辆位置，p
r
为车辆在候选路段上的投影位置，σ
′
为位置误差的标准差，车辆行驶方向与候选路段间的方向夹角贡献度：其中表示车辆的行驶方向，表示候选路段的方向，θ表示车辆方向与候选路段方向的夹角，车辆位置与候选路段之间的垂直距离使用海伦公式计算，其中p,a,b,c分别为三角形的半周长以及3条边长。4.根据权利要求3所述的一种面向立体城市交通网的道路最优匹配方法，其特征在于：所述步骤2具体包括如下步骤：步骤2-1：gps点的测量误差满足高斯分布n(μ,σ2)，其观测概率为：其中是采样点p
i
的候选点，是从候选点到采样点p
i
的欧几里得距离，μ是正态分布的方差，σ为正态分布的标准差；从候选点到候选点的空间分析函数定义为：其中是过渡概率，t为采样点p
i-1
的候选点索引，s为采样点p
i
的候选点索引，n为概率，n是采样点个数，i是采样点的索引，目的是测量两个连续候选点之间的最短路径和直路径的相似性，定义为：
其中d
i-1
→
i
是采样点p
i-1
到采样点p
i
的欧几里得距离，ω
(i-1,t)
→
(i,s)
是从候选到的最短路径的长度；步骤2-2：在没有交通事故的情况下，车速接近道路限速，利用时间分析函数在道路限速附近获得最大值，时间分析函数定义为：其中v
(i-1,t)
→
(i,s)
是从候选点到的最短路径的加权速度限制，是沿着候选点至之间最短路径行驶的车辆的平均速度；步骤2-3：使用道路水平因子来模拟车辆在高限速道路上停留的趋势，的道路水平系数(rlf)定义为：其中v
s
和v
d
表示和所在道路的速度限制，路径的综合权重函数为：步骤2-4：在真实的路网结构中，两个连续采样点的候选点之间可能没有可达道路；其次，根据大量实验结论，错误匹配路径权重值总是小于1.0
×
10-5
，而正确匹配路径的权重值总是大于1.0
×
10-5
；最后，路网结构不是平面的，有立体结构，而投影的结果是在平面坐标系中，因此，会将真正属于被遮挡道路的候选点投影到了其上面的道路上，使用三个约束过滤数据，减少后续计算负担。5.根据权利要求4所述的一种面向立体城市交通网的道路最优匹配方法，其特征在于：在所述步骤2-4中，三个约束分别为：约束1：相邻采样点的各个候选点之间的连通性需符合真实路网结构，可在路网结构中查询到最短路径，即匹配路径在路网结构中真实存在且能够在合理时间内可到达；约束2：设两个相邻匹配点的候选点之间的权重的阈值θ＝1.0
×
10-5
，当路径的权重小于θ时则被视为错误匹配路径，此路径不参与后续计算；约束3：根据不同道路拥有不同的限速这一特性，通过车辆的行驶速度与道路限速的关系进行判断，设为车辆沿着候选点到候选点之间最短路径行驶的平均速度，为所经过的所有道路的加权平均限速，当所经过的所有道路的加权平均限速，当时，其中1≤α≤2，路径被视为错误的匹配路径。6.根据权利要求1所述的一种面向立体城市交通网的道路最优匹配方法，其特征在于：
所述步骤3具体包括如下步骤：步骤3-1：:以步骤2提出的位置上下文分析为建模基础，采用空间分析以及时间分析两个方面来衡量两个连续候选点之间的影响，在计算各个采样点对应的各个候选点之间相互影响的权重之前，构建一个静态评分矩阵：m＝diag{m
(1)
,m
(2)
,
…
,m
(n-1)
}其中q
i-1
与q
i
分别为采样点p
i-1
与p
i
的候选点个数，静态评分矩阵中的每个项目仅考虑两个连续点的信息，表示候选点的权重，并不反映它们之间的相互影响，因此，将其构建为静态矩阵，以减少计算相互影响的权重时的计算负担；步骤3-2将采样点间的相互影响建模为(n-1)维距离权重矩阵，定义如下：其中，dist(p
i
,p
j
)是采样点p
i
和p
j
之间的欧几里得距离，β是相对于道路网的参数，e为自然常数，距离权重矩阵给出了所有其他点到p
i
的距离影响的权重，对于i＝1,2,
…
,n-1受距离影响的权重计算为：其中：ω为距离权重矩阵，m为静态评分矩阵，i和j是采样点的索引，q
i-1
与q
i
分别为采样点p
i-1
与p
i
的候选点个数；步骤3-3：在得到每个采样点的权重矩阵后，根据筛选出的候选点创建候候选图3：在得到每个采样点的权重矩阵后，根据筛选出的候选点创建候候选图其中表示各个采样点的候选点集合，ε表示前一个采样点的候选点到当前采样点的候选点之间的路径集合，通过分析可知，路径到必须同时满足三个约束条件时才会存在边每个节点都拥有观测概率属性，即表示该候选点与其采样点的观测概率，每条边都拥有累积权重与投票数属性，用于后续投票计数。7.根据权利要求1所述的一种面向立体城市交通网的道路最优匹配方法，其特征在于：所述步骤4具体包括如下步骤：步骤4-1：步骤4-1：局部最优路径反映最终匹配路径所经过的路径的可能性，如果路径被更多的路径所包含，则路径成为最终路径一部分的概率就越大；如果路径没有被任何局部最优路径所包含，则最终匹配路径不包括该路径对于采样点p
i
的每个候选点其中n为采样点个数，m为设置的候选点个数，遍历每个候选点当一个候选点被遍历时，假设该候选点就是最终匹配阶级过中正确的匹配点，到一条通过点的概率最大的路径作为局部最优路径，累计权重计权重是的权重，受p
i
和p
j
的距离影响，当i＝0时，计算所有点的累计权重后，即可得到
每个候选点的局部最优路径；步骤4-2：在到每个候选点的局部最优路径后，得到了一组局部最优路径，通过对每一个点的局部最优路径进行投票，选出投票数最多的一条路径作为最终匹配的路径，具体为：遍历第四阶段生成的候选图对图的所有边进行投票，最后筛选出每两个相邻采样点中投票最多的子路径作为最终匹配子路径，最后，所有子路径拼接成最终的最优匹配路径。

技术总结

本发明属于数据分析、智慧交通等交叉技术领域，具体的是一种面向立体城市交通网的道路最优匹配方法，该道路最优匹配方法首先利用路网数据构建三维KD树，将整个路网划分为多个域，再通过GPS轨迹数据在KD树中进行查，确定若干候选点；其次，其次通过路网与GPS轨迹及其之间的关系进行位置上下文分析与相互影响建模，确定每个采样点对应的候选点的局部最优路径以及候选图；最后，通过每个候选点的局部最优路径以及候选图进行交互式边投票，计算出最终的匹配结果。本发明解决了GPS轨迹与路网的匹配准确率与效率的问题。匹配准确率与效率的问题。