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

摘要

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

主权项

一种基于低采样率浮动车数据的全局投票地图匹配方法，其特征在于：所述匹配方法包括以下步骤：步骤一：构建有向道路网络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点p的记录包括经度、纬度、时间，所有的GPS点的集合定义为GPS记录L，浮动车GPS轨迹数据T定义为一组采样间隔为Δt的GPS点的序列；一个路段s为一条道路被两个相邻交叉口分隔出的一段路，每个路段包含起始点、结束点、路段长度；步骤二：针对浮动车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；对每个候选点进行匹配函数计算，得出静态分析矩阵；根据步骤二得到的候选节点集合，定义候选节点的近距概率MP为候选点是正确的匹配结果的概率，1≤k≤n，即：$MP\left(c_i^k\right)=\frac{1}{\sqrt{2\pi }}{e}^{-\frac{{(x_i^k-\mu )}^2}{2{\delta }^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=\left[\begin{array}{cccc}{M}_2& 0& \mathrm{...}& 0\\ 0& M_3& \mathrm{...}& 0\\ .& .& .& .\\ .& .& .& .\\ .& .& .& .\\ 0& 0& \mathrm{...}& M_n\end{array}\right]$其中M_i为路径经过匹配函数计算得到的矩阵，i≥2：$M_i=\left[\begin{array}{cccc}{F}_{(c_{i-1}^1\to c_i^1)}& F_{(c_{i-1}^1\to c_i^2)}& \mathrm{...}& 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)}& \mathrm{...}& F_{(c_{i-1}^2\to c_i^n)}\\ .& .& .& .\\ .& .& .& .\\ .& .& .& .\\ F_{(c_{i-1}^m\to c_i^1)}& F_{(c_{i-1}^m\to c_i^2)}& \mathrm{...}& F_{(c_{i-1}^m\to c_i^n)}\end{array}\right]$其中，1≤j≤m,1≤k≤n,m,n分别为c_i‑1,c_i的候选节点总个数；步骤四：加权得分过程，定义与两个轨迹点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，定义一个n‑1维距离影响矩阵W_i:$W_i=\left[\begin{array}{ccccccc}{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{array}\right]$其中，距离加权函数W_i^j采用其中δ为阈值，接下来，加权分析矩阵G_i，1≤i≤n：$G_i=\left[\begin{array}{ccccccc}{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{array}\right]$其中步骤五：全局投票，对每个轨迹点p_i，在其对应的加权分析矩阵G_i中，寻找一条最优的通过每个轨迹点的候选节点的路径，定义为单点投票过程；某个候选节点被选取，对这个候选节点进行记录加一操作，表示一次投票选中过程，针对全部候选节点集合，依次重复上述一次投票选中过程，会得到全部候选节点的得票情况；最后，对每个轨迹点p_i，在其候选节点集合中选择得票数最多的候选点作为全局候选节点结果，即得到了全局匹配结果。