一种基于条件随机场和低采样频率浮动车数据的地图匹配方法

摘要

一种基于条件随机场和低采样频率浮动车数据的地图匹配方法，针对低采样率的浮动车数据，在道路网络的模型基础上，首先计算GPS观测点可能匹配的候选投影点集合以及集合中每一个候选投影点的观测概率，然后计算相邻GPS观测点的候选路径集合以及每两个相邻候选投影点之间的传递概率；根据这些候选投影点和候选路径，在滑动窗口内，基于条件随机场模型，应用前后向递归算法，选择观测点的最佳匹配投影点。本发明在低采样频率的情况下，既考虑道路网络的拓扑结构，也考虑GPS观测点之间的关联信息，以较低计算复杂度，提高了地图匹配的精度。

说明书

技术领域

本发明涉及交通领域，特别是指一种基于条件随机场和低采样频率浮动车数 据的地图匹配方法。

背景技术

在交通出行中，车载GPS设备具有记录车辆轨迹以及路由、导航等功能，使 用较为普遍。车载GPS设备可以定期、实时地把车辆位置信息(主要包括车辆标 识符、偏移的经纬度以及时间戳等)通过无线通讯系统传输到信息处理中心。浮 动车一般是指安装了这种车载GPS设备并行驶在城市主干道上的公交汽车和出 租车。另外，GPS设备容易受到环境噪声干扰，GPS设备本身的可靠性及定位技 术自身局限性，这些都会影响GPS设备的定位经度。因此，在处理浮动车GPS 轨迹数据时，通常存在的一个问题就是把这些浮动车GPS观测位置数据尽可能正 确的匹配到路网上。

当浮动车的采样频率较高时，一些准确率较高的地图匹配算法已经比较成熟。 目前，为了降低功耗和数据的传输成本以及浮动车本身特性，浮动车的采样频率 普遍较低(1至2分钟，甚至更低)。在采样频率较低时，由于车速较高、街区较 短以及GPS定位误差等，浮动车的精确位置信息以及路径信息的重建、恢复较难。 因此，近年来，低采样频率浮动车数据地图匹配问题引起了很大关注。

地图匹配的问题可以追溯到1980年。20世纪90年代，GPS系统普及到民用， 研究人员开始对GPS设备进行系统的研究。早期的地图匹配方法，从几何分析的 角度，把每一个GPS观测数据投影到路网道路的一些点上。后来，这种投影算法 利用了路网及车辆的其他信息进行地图匹配，如车辆行进方向和路网道路曲率等。 然而，因为只考虑单个GPS观测点，这类匹配算法的准确率并不高。基于路网拓 扑和弗雷歇距离，新的确定性算法涌现出来，这类算法把部分轨迹直接匹配到路 网上。当GPS观测点偏差较大时，这类确定性算法并不能很好的处理，然后这类 算法思想很快延伸到概率框架，例如粒子滤波器，卡尔曼滤波器，隐马尔可夫模 型(HMMs)，及一些其他基于信任函数理论和模糊逻辑的非主流算法。但这类算 法主要是针对高采样频率浮动车数据，并不能很好运用在低采样频率浮动车数据 的匹配过程。

发明内容

为了克服现有的地图匹配方法的计算复杂度较高、匹配精度较低的不足，本 发明提供一种计算复杂度较低、匹配精度较高的基于条件随机场和低采样频率浮 动车数据的地图匹配方法。

为了解决上述技术问题本发明提出如下技术方案：

一种基于条件随机场和低采样频率浮动车数据的地图匹配方法，包括以下步 骤：

步骤一：构建有向道路网络G(V,E)，其中V为道路的交叉路口，E为两个相 邻交叉路口中间的路段，每一路段e的属性包括路段的起始经纬度点 e.Longitude1、e.Latitude1，结束经纬度点e.Longitude2、e.Latitude2和路段的类型 e.Type；

步骤二：对于一个t时刻的GPS观测点g(t)，选取以g(t)为圆心在半径r范 围内的所有路段，通过投影得到相应的候选投影点：如果观测点g(t)在路段e的 范围内存在垂点，则选取该垂点作为观测点g(t)在该路段上的候选投影点x_i(t)， 并且选取垂线的长度为该观测点与该路段的距离；否则，选取该路段离轨迹点较 近的起点或者终点为观测点g(t)在该路段上的候选投影点x_i(t)，选取观测点与该 路段起点或者终点的连线长度为该观测点与该路段的距离，根据路段投影过程， 获取GPS观测点g(t)的候选投影点集合Χ(t)＝(x_i(t)),i＝1,2,…,I^t，其中I^t为候 选投影点的个数；

步骤三：每隔Δt时间，同一辆浮动车会发送到信息处理中心一个观测点g， 然后，把g(t)投影到路网上I^t个不同的候选投影点，获取候选投影点集合，即 Χ(t)＝(x_i(t)),i＝1,2,…,I^t；t时刻处于候选投影点x_i(t)∈Χ(t)处的车辆，经过Δt 时间，转移到候选投影点x_i′(t+1)∈Χ(t+1)处，把所经过的最短路径作为候选路 径，标记观测点g(t)和下一个观测点g(t+1)之间的候选路径集合为 Ρ(t)＝(p_m,n(t))，p_m,n(t)表示观测点g(t)的一个候选投影点x_m(t)到观测点g(t) 的一个候选投影点x_n(t+1)的一条候选路径，J^t表示候选路径的个数；

步骤四：对于同一辆浮动车的GPS观测点序列g(1:T)＝g(1)→g(2)→…→g(T)， 获得每一个GPS观测点的候选投影点集合以及每两个相邻观测点的候选路径集 合；然后，把候选投影点的观测概率ω(g(t)|x_i(t))和相邻候选投影点之间的传递 概率η(p_m,n(t))结合起来，基于条件随机场模型，应用前后向递归算法，计算滑 动窗口中部分GPS轨迹数据中GPS观测点g(t)的候选投影点x_i(t)的概率权重值 q_i(t)，选取概率权重值最大的候选投影点为GPS观测点的最佳匹配点。

进一步，所述步骤二中，一个GPS观测点g(t)包括车牌编号、经度、纬度和 时间。

再进一步，所述步骤四中，获得一GPS观测点的候选投影点集合，对每个候 选投影点，采用高斯分布N(μ,δ²)，定义其观测概率ω(g(t)|x_i(t))，t时刻处于候 选投影点x_i(t)处的车辆产生观测点g(t)的观测概率，即：

$\omega \left(g\right(t\left)\right|x_i\left(t\right))=\frac{1}{\sqrt{2\pi }\sigma }\exp \left(-\frac{{\left(d\left(g\left(t\right),x_i\left(t\right)\right)-\mu \right)}^2}{2{\sigma }^2}\right),$

其中d(g(t),x_i(t))为观测点和投影点之间的欧氏距离，然后，把每一候选投影点 的观测概率组成一个行向量，即$C\left(t\right)=\left(\omega \left(g\left(t\right)|x_1\left(t\right)\right),...,\omega \left(g\left(t\right)|x_{I^t}\left(t\right)\right)\right);$

结合道路网络的拓扑结构，对于相邻的两个候选投影点，定义其传递概率 p_m,n(t)，即：

$\eta \left(p_{m,n}\left(t\right)\right)=\frac{d\left(g\left(t\right),g\left(t+1\right)\right)}{l\left(p_{m,n}\left(t\right)\right)}$

其中d(g(t),g(t+1))为两个观测点之间的欧式距离，l(p_m,n(t))为两个候选投影 点x_m(t)与x_n(t+1)之间的最短路径p_m,n(t)长度，然后，把每两个相邻的候选点 之间传递概率组成一个矩阵，记为：

其中，α_i(t)表示观测点g(t)的所有候选投影点到观测点g(t+1)的候选投影 点x_i(t+1)的传递概率列向量，β_i(t)表示观测点g(t)的候选投影x_i(t)到观测点 g(t+1)的所有候选投影点的传递概率行向量。

更进一步，所述步骤四中，所述条件随机场是一个无向图模型或马尔可夫随 机场，采用条件随机场模型来处理浮动车GPS观测点序列的地图匹配问题，通过 观测点、候选投影点以及传递概率矩阵，进行地图匹配。

所述步骤四中，q_i(t)为t时刻的观测点g(t)的候选投影点x_i(t)相对于其他的 候选投影点x_i′(t)的概率权重，即已知观测点序列g(1:T′)＝g(1)→…→g(T′)，t时 刻车辆处于状态x_i(t)的概率，标记Normalize(C(t))表示对候选投影点观测概率向 量进行归一化计算，计算q_i(t)的前后向递归过程如下：

q_i(t)＝π(x_i(t)|g(1:T′))＝π(x_i(t)|g(1:t))π(x_i(t)|g(t:T′))

其中计算的过程如下，是一个前向递归过程：

ⅰ：${\overrightarrow{f}}_i\left(1\right)=\omega \left(g\left(1\right)|x_i\left(1\right)\right)$

ⅱ：${\overrightarrow{f}}_i\left(t\right)=\omega \left(g\left(t\right)|x_i\left(t\right)\right)*\left(Normalize\left(\left({\overrightarrow{f}}_1\left(t-1\right),...,{\overrightarrow{f}}_{I^{t-1}}\left(t-1\right)\right)\right){\alpha }_i\left(t-1\right)\right)$

其中计算的过程如下，是一个后向递归过程：

①：${\overleftarrow{b}}_i\left(T^{\prime }\right)=\omega \left(g\left(T^{\prime }\right)|x_i\left(T^{\prime }\right)\right)$

②：${\overleftarrow{b}}_i\left(t\right)=\omega \left(g\left(t\right)|x_i\left(t\right)\right)*\left(Normalize\left(\left({\overleftarrow{b}}_1\left(t+1\right),...,{\overleftarrow{b}}_{I^{t-1}}\left(t+1\right)\right)\right){\left({\beta }_i\left(t-1\right)\right)}^T\right)$

在t时刻，选取q_i(t)值最大的候选投影点作为最佳匹配投影点。

所述步骤四中，滑动窗口机制为：给定一个正数k＞0，对于一GPS观测点 序列，把其中的观测点一个接一个的放到滑动窗口链表里，如果t＝k，计算滑动 窗口链表中第一个至第(k/2+1)个GPS观测点的每个候选投影点的选择观测 点对应的值最大的候选投影点作为此观测点的最佳匹配投影点，如果t＞k，计 算滑动窗口链表中第(k/2+1)个GPS观测点的每个候选投影点的选择值最 大的候选投影点作为此观测点的最佳匹配投影点，弹出滑动窗口链表的第一个观 测点，持续把观测点插入到滑动窗口链表，重复上述计算过程。

所述步骤三中，所述最短路径通过Dijkstra算法或Floyd算法获得。

本发明的技术构思为：针对相邻GPS观测点之间时间差为Δt≥1min情况， 为了提高低采样频率浮动车数据地图匹配的正确率，本发明结合路网拓扑信息及 局部GPS观测点之间的关联信息，基于条件随机场模型，应用前后向递归算法， 提出一种正确率较高的地图匹配方法。

首先计算GPS观测点可能匹配的候选投影点集合以及集合中每一个候选投影 点的观测概率，然后计算相邻GPS观测点的候选路径集合以及每两个相邻候选投 影点之间的传递概率。根据这些候选投影点和候选路径，基于条件随机场模型， 应用前后向递归算法，选择观测点的最佳匹配投影点。

本发明的有益效果为：在低采样频率的情况下，既考虑道路网络的拓扑结构， 也考虑GPS观测点之间的关联信息，以较低计算复杂度，提高了地图匹配的精度。

附图说明

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

图2是条件随机场示意图。

具体实施方式

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

参照图1和图2，一种基于条件随机场和低采样频率浮动车数据的地图匹配 方法，包括以下步骤：

步骤一：构建有向道路网络G(V,E)，其中V为道路的交叉路口，E为两个相 邻交叉路口中间的路段，每一路段e的属性包括路段的起始经纬度点 e.Longitude1、e.Latitude1，结束经纬度点e.Longitude2、e.Latitude2和路段的类型 e.Type；

步骤二：参考图1，对于一个t时刻的GPS观测点g(t)，选取以g(t)为圆心 在半径r范围内的所有路段，通过投影得到相应的候选投影点：如果观测点g(t)在 路段e的范围内存在垂点，则选取该垂点作为观测点g(t)在该路段上的候选投影 点x_i(t)，并且选取垂线的长度为该观测点与该路段的距离；否则，选取该路段离 轨迹点较近的起点或者终点为观测点g(t)在该路段上的候选投影点x_i(t)，选取观 测点与该路段起点或者终点的连线长度为该观测点与该路段的距离，根据路段投 影过程，获取GPS观测点g(t)的候选投影点集合Χ(t)＝(x_i(t)),i＝1,2,…,I^t，其 中I^t为候选投影点的个数；

步骤三：每隔Δt时间，同一辆浮动车会发送到信息处理中心一个观测点g。 然后，把g(t)投影到路网上I^t个不同的候选投影点，获取候选投影点集合，即 Χ(t)＝(x_i(t)),i＝1,2,…,I^t，t时刻处于候选投影点x_i(t)∈Χ(t)处的车辆，经过Δt 时间，转移到候选投影点x_i′(t+1)∈Χ(t+1)处，把所经过的最短路径作为候选路 径，可以通过Dijkstra算法或Floyd算法获得，标记观测点g(t)和下一个观测点 g(t+1)之间的候选路径集合为Ρ(t)＝(p_m,n(t))，p_m,n(t)表示观测点g(t)的一个 候选投影点x_m(t)到观测点g(t)的一个候选投影点x_n(t+1)的一条候选路径，J^t表示候选路径的个数；

步骤四：对于同一辆浮动车的GPS观测点序列g(1:T)＝g(1)→g(2)→…→g(T)， 获得每一个GPS观测点的候选投影点集合以及每两个相邻观测点的候选路径集 合。然后，把候选投影点的观测概率ω(g(t)|x_i(t))和相邻候选投影点之间的传递 概率η(p_m,n(t))结合起来，基于条件随机场模型(如图2)，应用前后向递归算法， 计算滑动窗口中部分GPS轨迹数据中GPS观测点g(t)的候选投影点x_i(t)的概率 权重值q_i(t)，选取概率权重值最大的候选投影点为GPS观测点的最佳匹配点。

进一步，所述步骤二中，一个GPS观测点g(t)包括车牌编号、经度、纬度和 时间。

再进一步，所述步骤四中，获得一GPS观测点的候选投影点集合，对每个候 选投影点，采用高斯分布N(μ,δ²)，定义其观测概率ω(g(t)|x_i(t))，t时刻处于候 选投影点x_i(t)处的车辆产生观测点g(t)的观测概率，即：

$\omega \left(g\right(t\left)\right|x_i\left(t\right))=\frac{1}{\sqrt{2\pi }\sigma }\exp \left(-\frac{{\left(d\left(g\left(t\right),x_i\left(t\right)\right)-\mu \right)}^2}{2{\sigma }^2}\right),$

其中d(g(t),x_i(t))为观测点和投影点之间的欧氏距离。然后，把每一候选投影点 的观测概率组成一个行向量，即$C\left(t\right)=\left(\omega \left(g\left(t\right)|x_1\left(t\right)\right),...,\omega \left(g\left(t\right)|x_{I^t}\left(t\right)\right)\right).$

结合道路网络的拓扑结构，对于相邻的两个候选投影点，定义其传递概率 p_m,n(t)，即：

$\eta \left(p_{m,n}\left(t\right)\right)=\frac{d\left(g\left(t\right),g\left(t+1\right)\right)}{l\left(p_{m,n}\left(t\right)\right)}$

其中d(g(t),g(t+1))为两个观测点之间的欧式距离，l(p_m,n(t))为两个候选投影 点x_m(t)与x_n(t+1)之间的最短路径p_m,n(t)长度。然后，把每两个相邻的候选点 之间传递概率组成一个矩阵，记为：

其中α_i(t)表示观测点g(t)的所有候选投影点到观测点g(t+1)的候选投影点 x_i(t+1)的传递概率列向量，β_i(t)表示观测点g(t)的候选投影x_i(t)到观测点 g(t+1)的所有候选投影点的传递概率行向量。

更进一步，所述步骤四中，条件随机场是一个无向图模型或马尔可夫随机场， 也是一种处理序列化数据的统计模型。这里用此模型来处理浮动车GPS观测点序 列的地图匹配问题，通过观测点、候选投影点以及传递概率矩阵，进行地图匹配。

更进一步，所述步骤四中，q_i(t)为t时刻的观测点g(t)的候选投影点x_i(t)相 对于其他的候选投影点x_i′(t)的概率权重，即已知观测点序列 g(1:T′)＝g(1)→…→g(T′)，t时刻车辆处于状态x_i(t)的概率。标记Normalize(C(t)) 表示对候选投影点观测概率向量进行归一化计算。计算q_i(t)的前后向递归过程如 下：

q_i(t)＝π(x_i(t)|g(1:T′))＝π(x_i(t)|g(1:t))π(x_i(t)|g(t:T′))

其中计算的过程如下，是一个前向递归过程：

ⅰ：${\overrightarrow{f}}_i\left(1\right)=\omega \left(g\left(1\right)|x_i\left(1\right)\right)$

ⅱ：${\overrightarrow{f}}_i\left(t\right)=\omega \left(g\left(t\right)|x_i\left(t\right)\right)*\left(Normalize\left(\left({\overrightarrow{f}}_1\left(t-1\right),...,{\overrightarrow{f}}_{I^{t-1}}\left(t-1\right)\right)\right){\alpha }_i\left(t-1\right)\right)$

其中计算的过程如下，是一个后向递归过程：

①：${\overleftarrow{b}}_i\left(T^{\prime }\right)=\omega \left(g\left(T^{\prime }\right)|x_i\left(T^{\prime }\right)\right)$

②：${\overleftarrow{b}}_i\left(t\right)=\omega \left(g\left(t\right)|x_i\left(t\right)\right)*\left(Normalize\left(\left({\overleftarrow{b}}_1\left(t+1\right),...,{\overleftarrow{b}}_{I^{t-1}}\left(t+1\right)\right)\right){\left({\beta }_i\left(t-1\right)\right)}^T\right)$ 在t时刻，选取q_i(t)值最大的候选投影点作为最佳匹配投影点。

更进一步，所述步骤四中，滑动窗口机制为：给定一个正数k＞0，对于一 GPS观测点序列，把其中的观测点一个接一个的放到滑动窗口链表里，如果t＝k， 计算滑动窗口链表中第一个至第(k/2+1)个GPS观测点的每个候选投影点的选择观测点对应的值最大的候选投影点作为此观测点的最佳匹配投影点，如果 t＞k，计算滑动窗口链表中第(k/2+1)个GPS观测点的每个候选投影点的选 择值最大的候选投影点作为此观测点的最佳匹配投影点，弹出滑动窗口链表的 第一个观测点，持续把观测点插入到滑动窗口链表，重复上述计算过程。

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