首页> 中国专利> 一种基于低采样率浮动车数据的全局投票地图匹配方法

一种基于低采样率浮动车数据的全局投票地图匹配方法

页面导航

摘要
著录项
法律信息
说明书
相似文献

摘要

一种基于低采样率浮动车数据的全局投票地图匹配方法，该方法在浮动车GPS轨迹数据的基础上，考虑道路网络的拓扑结构和不同距离的空间位置相邻的GPS轨迹数据对地图匹配过程的影响。定义了新的地图匹配函数指标，综合考虑道路网络的几何学特性和拓扑结构对匹配的影响，得出作为初始地图匹配结果的静态匹配矩阵(SMM)；在此基础上，定义反映节点之间距离影响的距离加权函数对SMM进行修正，得到动态匹配矩阵(DMM)，最后，对DMM采用全局投票的方法，找出最优轨迹作为地图匹配的结果。本发明能在低采样率的情况下，以较低的计算时间复杂度实现较好的地图匹配效果。

著录项

公开/公告号CN104197945A

专利类型发明专利
公开/公告日2014-12-10

原文格式PDF
申请/专利权人浙江工业大学;
展开▼

申请/专利号CN201410427108.9
发明设计人杨旭华;赵久强;汪向飞;
展开▼

申请日2014-08-27
分类号G01C21/30(20060101);
代理机构33241 杭州斯可睿专利事务所有限公司;
代理人王利强
地址 310014 浙江省杭州市下城区朝晖六区潮王路18号
入库时间 2023-12-17 02:55:12

法律信息

法律状态公告日

法律状态信息

法律状态
2017-04-12

授权

授权
2015-01-07

实质审查的生效 IPC(主分类):G01C21/30 申请日:20140827

实质审查的生效
2014-12-10

公开

公开

说明书

技术领域

本发明涉及交通领域，特别是指一种基于低采样率浮动车数据的全局投票地图匹配方法。

背景技术

浮动车一般是指安装了车载GPS定位装置并行驶在城市主干道上的公交汽车或出租车。浮动车技术是近年来兴起的一种动态交通信息检测的技术，是近年来智能交通系统中所采用的获取道路交通信息的先进技术手段之一。浮动车可以定期将车辆编号、时刻、方向、经纬度坐标等数据传送到调度中心,经过信息处理，可以方便地获得整个城市路网的实时交通信息。地图匹配方法是浮动车数据处理的关键技术之一，它可以最大程度地校正GPS卫星定位所产生的误差，从而矫正车辆轨迹偏离道路的现象，并进一步将GPS数据转化为道路的交通信息。

传统的地图匹配方法，GPS采样率往往都很高，匹配的正确率才得以保证。但实际在浮动车技术中，为了节约能源以及浮动车本身特性，返回给调度中心的数据往往都是低采样率的。在低采样率的情况下(比如2分钟)，在车辆的速度仅为30km/h，两个采样点之间的距离就达到了1000米，两个GPS点之间的关联信息会大部分丢失。因此，传统的地图匹配方法不能很好运用在基于低采样率的浮动车数据的匹配过程。以此为背景，为了提高匹配方法在低采样率GPS数据输入情况下的正确匹配率，本文提出的全局投票方法考虑道路网络的拓扑结构以及 GPS点之间的相互影响。

考虑几何学特性的地图匹配方法，根据匹配过程，这类方法又可以分为点对点的匹配，点对曲线的匹配，曲线对曲线的匹配。由于缺乏对整体道路网络拓扑结构的考虑，在复杂的道路环境和低采样率的浮动车数据情况下，这些方法很容易出现匹配误差。同时这些匹配方法不考虑全局GPS点之间的相互影响，在某个 GPS点的匹配过程中，只利用该点本身的信息，或者仅仅考虑其相邻节点对其匹配过程的影响，但针对节点间关联信息大量丢失的低采样率浮动车数据时，很难得到正确的匹配结果。

发明内容

为了克服现有的全区投票地图匹配方法的正确率较低的不足，本发明提供一种一种基于低采样率浮动车数据的全局投票地图匹配方法，在道路网络的模型基础上，首先计算当前GPS轨迹点可能匹配的候选集合，考虑集合中候选点的近距概率和连通概率，得出静态分析矩阵。再考虑节点之间距离的不同导致影响程度的不同，得出加权匹配矩阵，在此基础上，各个GPS轨迹点之间相互投票，完成匹配方法。

为了解决上述技术问题采用的技术方案如下：

一种基于低采样率浮动车数据的全局投票地图匹配方法，所述匹配方法包括以下步骤：

步骤一：构建有向道路网络G(V,E)，其中V为道路的交叉点、起点或终点， E为被两个相邻交叉口分隔出的路段，定义一条路径为：在道路网络中，选取两个节点V_i,V_j，找到一条互相连接的路段集合s₁→s₂→s₃...→s_n，并且 s₁.start＝V_i,s_n.end＝V_j,即路段s₁的起点为V_i，路段s_n的终点为V_j；在道路网络的基础上，处理浮动车GPS数据，得到浮动车GPS轨迹数据T；

步骤二：针对浮动车GPS轨迹数据T：p₁→p₂→p₃...→p_n中的轨迹点p_i， 1≤i≤n，选取在半径r范围内的所有路段为候选路段k表示点p_i的第k个候选路段；通过投影得到对应的候选节点：如果轨迹点p_i在路段的范围内存在垂点，则选取该垂点作为轨迹点p_i的候选节点，记为并且选取垂线的长度为该轨迹点与该路段的距离；否则，选取该路段离轨迹点较近的起点或者终点为候选节点，选取轨迹点与该路段起点或者终点的连线长度为该轨迹点与该路段的距离；根据路段投影过程，得出每个GPS轨迹点的候选点集合；

步骤三：静态分析过程，定义匹配函数指标其中为点p_i-1的第j个候选节点，为点p_i的第k个候选节点，i≥2；对每个候选点进行匹配函数计算，得出静态分析矩阵；

步骤四：加权得分过程，定义与两个轨迹点p_i,p_j之间的距离有关的函数的距离加权函数W_i^j＝f(dist(p_i,p_j))，dist(p_i,p_j)为轨迹点p_i,p_j之间的欧式距离， 1≤i≤n，1≤j≤n，i≠j，距离加权函数代表节点之间距离越远，节点之间影响越弱，对每一个GPS点，经过全局计算，得出加权分析矩阵；

步骤五：全局投票，对每个轨迹点p_i，在其对应的加权分析矩阵G_i中，寻找一条最优的通过每个轨迹点的候选节点的路径，定义为单点投票过程；某个候选节点被选取，对这个候选节点进行记录加一操作，表示一次投票选中过程，针对全部候选节点集合，依次重复上述操作，会得到全部候选节点的得票情况；最后，对每个轨迹点p_i，在其候选节点集合中选择得票数最多的候选点作为全局候选节点结果，即得到了全局匹配结果。

进一步，所述步骤一中，一个GPS点p的记录包括经度、纬度、时间，所有的GPS点的集合定义为GPS记录L，GPS轨迹T定义为一组采样间隔为Δt的 GPS点的序列；一个路段s为一条道路被两个相邻交叉口分隔出的一段路，每个路段包含起始点、结束点、路段长度。

再进一步，所述步骤三中，根据步骤二得到的候选节点集合，定义候选节点的近距概率MP为候选点是正确的匹配结果的概率，1≤k≤n，即：

$MP (c_{i}^{k}) = \frac{1}{\sqrt{2 π}} e^{- \frac{{(x_{i}^{k} - μ)}^{2}}{{2 δ}^{2}}}$

其中为该候选点与轨迹点p_i的欧式距离；

考虑道路网络的拓扑结构，定义两个候选节点之间的连通概率CP为：

$CP (c_{i - 1}^{j} \to c_{i}^{k}) = \frac{l_{i - 1 \to i}}{s_{(i - 1, j) \to (i, k)}}$

其中，l_i-1→i为两个相邻轨迹点p_i-1和轨迹点p_i之间的欧氏距离，s_{(i-1,j)→(i,k)}为通过候选节点和的最短路径长度；

选取相邻轨迹点p_i-1和p_i相应的候选节点和经过匹配函数计算，得出静态分析矩阵M，针对每条路径n≥i≥2，计算出匹配函数的值，得出静态分析矩阵M：

$M = (\begin{matrix} M_{2} & 0 & \cdot \cdot \cdot & 0 \\ 0 & M_{3} & \cdot \cdot \cdot & 0 \\ \cdot & \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot & \cdot \\ 0 & 0 & \cdot \cdot \cdot & M_{n} \end{matrix})$

其中M_i为路径经过匹配函数计算，得到的矩阵：

$M_{i} = (\begin{matrix} F_{(c_{i - 1}^{1} \to c_{i}^{1})} & F_{(c_{i - 1}^{1} \to c_{i}^{2})} & \cdot \cdot \cdot & F_{(c_{i - 1}^{1} \to c_{i}^{n})} \\ F_{(c_{i - 1}^{2} \to c_{i}^{1})} & F_{(c_{i - 1}^{2} \to c_{i}^{2})} & \cdot \cdot \cdot & F_{(c_{i - 1}^{2} \to c_{i}^{n})} \\ \cdot & \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot & \cdot \\ F_{(c_{i - 1}^{m} \to c_{i}^{1})} & F_{(c_{i - 1}^{m} \to c_{i}^{2})} & \cdot \cdot \cdot & F_{(c_{i - 1}^{m} \to c_{i}^{n})} \end{matrix})$

其中，1≤j≤m,1≤k≤n,m,n分别为c_i-1,c_i的候选节点总个数。

更进一步，所述步骤四中，针对每个轨迹点p_i，定义一个n-1维距离影响矩阵W_i:

$W_{i} = (\begin{matrix} W_{i}^{1} & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & W_{i}^{2} & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & . . . & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & W_{i}^{i - 1} & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & W_{i}^{i + 1} & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & . . . & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & W_{i}^{n} \end{matrix})$

其中，距离加权函数采用 $f (dist (p_{i}, p_{j})) = \exp (- \frac{dist {(p_{i}, p_{j})}^{2}}{δ^{2}}),$ 其中δ为阈值，接下来，加权分析矩阵G_i，1≤i≤n：

$G_{i} = (\begin{matrix} G_{i}^{1} & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & G_{i}^{2} & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & . . . & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & G_{i}^{i - 1} & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & G_{i}^{i + 1} & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & . . . & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & G_{i}^{n} \end{matrix})$

其中 $G_{i}^{1} = M_{2} W_{i}^{1}, G_{i}^{2} = M_{3} W_{i}^{2}, G_{i}^{i - 1} = M_{i - 1} W_{i}^{i - 1}, G_{i}^{i + 1} = M_{i + 1} W_{i}^{i + 1}, G_{i}^{n} = M_{n} W_{i}^{n} .$

本发明的技术构思为：浮动车数据不仅仅反映了车辆的位置信息，在某种程度上也反映了道路的拓扑结构信息以及GPS轨迹点之间的时间序列信息。因此本文所提出的这种针对低采样率GPS数据的全局投票地图匹配方法，在采样率低的情况下，充分考虑道路网络的拓扑结构，以及全局GPS点之间的关联信息，且根据GPS点之间的距离，对它们之间的影响程度进行加权处理，从而提高匹配的正确率。

本发明的有益效果为：能在低采样率的情况下，以较低的计算时间复杂度实现较好的地图匹配效果。

附图说明

图1是本发明的主流程图。

图2是选取候选节点示意图。

具体实施方式

下面结合附图对本发明做进一步说明。

参考图1和图2，一种一种基于低采样率浮动车数据的全局投票地图匹配方法，包括以下步骤：

步骤一：构建有向道路网络G(V,E)，其中V为道路的交叉点、起点或终点， E为被两个相邻交叉口分隔出的路段。定义一条路径为：在道路网络中，选取两个节点V_i,V_j，找到一条互相连接的路段集合s₁→s₂→s₃...→s_n，并且 s₁.start＝V_i,s_n.end＝V_j。在道路网络的基础上，处理浮动车GPS数据，得到浮动车GPS轨迹数据T；

步骤二：参考图2，针对轨迹T:p₁→p₂→p₃...→p_n中的轨迹点p_i，1≤i≤n，选取在半径r范围内的所有路段为候选路段k表示点p_i的第k个候选路段。通过投影得到对应的候选节点：如果轨迹点p_i在路段的范围内(而不是在路段延长线上)存在垂点，则选取该垂点作为轨迹点p_i的候选节点，记为并且选取垂线的长度为该轨迹点与该路段的距离。否则，选取该路段离轨迹点较近的起点或者终点为候选节点，选取轨迹点与该路段起点或者终点的连线长度为该轨迹点与该路段的距离。根据路段投影过程，得出每个GPS轨迹点的候选点集合。

步骤三：静态分析过程，定义匹配函数指标其中为点p_i-1的第j个候选节点，为点p_i的第k个候选节点；又因为针对起始节点c₁不需要计算连通概率CP，因此选取i≥2。对每个候选点进行匹配函数计算，得出静态分析矩阵；

步骤四：加权得分过程，定义表示与p_i,p_j之间的距离有关的函数的距离加权函数dist(p_i,p_j)为轨迹点p_i,p_j之间的欧式距离，1≤i≤n， 1≤j≤n，i≠j，距离加权函数代表代表节点之间距离越远，节点之间影响越弱；对每一个GPS点，经过全局计算，得出加权分析矩阵；

步骤五：全局投票，对每个轨迹点p_i，在其对应的加权分析矩阵G_i中，寻找一条最优的通过每个轨迹点的候选节点的路径，我们定义为单点投票过程。某个候选节点被选取，我们对这个候选节点进行记录加一操作，表示一次投票选中过程。针对全部候选节点集合，依次重复上述操作，会得到全部候选节点的得票情况。最后，对每个轨迹点p_i，在其候选节点集合中选择得票数最多的候选点作为全局候选节点结果，也就同时得到了全局匹配结果。

进一步，所述步骤一中，一个GPS点p的记录包括经度、纬度、时间，所有的GPS点的集合定义为GPS记录L。GPS轨迹T定义为一组采样间隔为Δt的 GPS点的序列。本发明研究Δt≥2min的情况。一个路段s为一条道路被两个相邻交叉口分隔出的一段路，每个路段包含起始点、结束点、路段长度。

再进一步，所述步骤三中，根据步骤二得到的候选节点集合，定义候选节点的近距概率MP为候选点是正确的匹配结果的概率，1≤k≤n，即：

$MP (c_{i}^{k}) = \frac{1}{\sqrt{2 π}} e^{- \frac{{(x_{i}^{k} - μ)}^{2}}{{2 δ}^{2}}}$

其中为该候选点与轨迹点p_i的欧式距离；

考虑道路网络的拓扑结构，定义两个候选节点之间的连通概率CP为：

$CP (c_{i - 1}^{j} \to c_{i}^{k}) = \frac{l_{i - 1 \to i}}{s_{(i - 1, j) \to (i, k)}}$

其中，l_i-1→i为两个相邻轨迹点p_i-1和轨迹点p_i之间的欧氏距离，s_{(i-1,j)→(i,k)}为通过候选节点和的最短路径长度。

MP和CP为作为方法评测指标，分别表示在考虑道路网络的几何学特性和拓扑结构特性下的匹配概率。概率越大，越有可能是最终的匹配结果。

选取相邻轨迹点p_i-1和p_i相应的候选节点和经过匹配函数计算，得出静态分析矩阵M。针对每条路径n≥i≥2，计算出匹配函数的值。得出静态分析矩阵M：

其中M_i为路径经过匹配函数计算，得到的矩阵：

其中，1≤j≤m,1≤k≤n,m,n分别为c_i-1,c_i的候选节点总个数。

更进一步，所述步骤四中，在步骤三得到的静态分析矩阵的基础上，考虑节点之间的距离越远，它们之间互相的影响越弱。因此，针对每个轨迹点p_i，我们定义一个n-1维距离影响矩阵W_i：

其中，距离加权函数W_i^j采用 $f (dist (p_{i}, p_{j})) = \exp (- \frac{dist {(p_{i}, p_{j})}^{2}}{δ^{2}}),$ 其中δ为阈值，接下来，加权分析矩阵G_i，1≤i≤n：

其中 $G_{i}^{1} = M_{1} W_{i}^{1}, G_{i}^{2} = M_{1} W_{i}^{2}, G_{i}^{i - 1} = M_{i - 1} W_{i}^{i - 1}, G_{i}^{i + 1} = M_{i} W_{i}^{i + 1}, G_{i}^{n} = M_{n - 1} W_{i}^{n} .$

如上所述，本实施的具体实现步骤使本发明更加清晰。在本发明的精神和权利要求的保护范围内，对本发明作出的任何修改和改变，都落入本发明的保护范围。

去获取专利，查看全文>

相似文献

专利
中文文献
外文文献

1. 一种基于低采样率浮动车数据的全局投票地图匹配方法 [P] . 中国专利： CN104197945B . 2017.04.12
2. 一种基于低采样率浮动车数据的全局投票地图匹配方法 [P] . 中国专利： CN104197945A . 2014-12-10
3. Feature extraction from 3D submap and global map system and method for centimeter precision localization using camera-based submap and lidar-based global map [P] . 美国专利： US10223807B1 . 2019-03-05

机译：从3D子地图和全局地图系统中提取特征以及使用基于相机的子地图和基于激光雷达的全局地图进行厘米精度定位的方法
4. Map-matching for low-sampling-rate GPS trajectories [P] . 美国专利： US10288433B2 . 2019-05-14

机译：低采样率GPS轨迹的地图匹配
5. MAP-MATCHING FOR LOW-SAMPLING-RATE GPS TRAJECTORIES [P] . 美国专利： US2019265047A1 . 2019-08-29

机译：低采样率GPS轨迹的地图匹配