动态距离权重因子的隐马尔可夫模型地图匹配算法

滕志军，李昊天，张 宇，何义昌

(1.东北电力大学 a.现代电力系统仿真控制与绿色电能新技术教育部重点实验室；b.电气工程学院,吉林 吉林 132012；2.中国联合网络通信有限公司 菏泽市分公司,山东 菏泽 274000)

0 引言

定位数据和电子地图均存在难以避免的误差[1]，导致车辆的定位结果显示错误。地图匹配算法可以解决误差干扰的问题，将定位点匹配到正确的路段上。现有的地图匹配算法可分为4种类型：基于几何信息的算法，基于拓扑关系的算法，基于概率统计的算法以及复合匹配算法。基于几何信息的算法未考虑道路拓扑结构，易造成错误匹配[2-5]。基于拓扑关系的算法易受噪声、数据稀疏性等因素的影响，难以解决复杂路网匹配的问题[6-7]。基于概率统计的算法涉及复杂的公式证明与推导，算法稳定性不佳[8-9]。卡尔曼滤波、D-S证据理论等复合匹配算法虽然准确率很高，但低频采样时错误率较高[10-15]。基于隐马尔可夫模型的地图匹配算法，可以很好地解决低频采样错误率较高的问题，但是随着城市道路拓扑结构越来越复杂，导致该算法准确率不稳定，单点匹配耗时长[16-17]。

综上所述，单一算法很难较好地权衡准确率和时效性，因此，本文结合了几何匹配算法和基于隐马尔可夫匹配算法两种思想，重新定义匹配程度的概念。对传统点到线的匹配算法进行改进，提出了一种融入动态距离权重因子的隐马尔可夫模型(hidden Markov model，HMM)地图匹配算法。借助仿真实验，验证了本文HMM地图匹配算法的单点匹配时间更少且准确率更高。

1 确定路段检索区域

经典算法选择以车辆定位位置为区域中心的方形或圆形区域作为路段检索区域。为了提高算法的运行效率，本文通过两次筛选确定路段检索区域，第1次筛选利用网格索引对电子地图进行划分，合理选择以车辆当前定位位置为中心的九宫格区域，尽可能减少候选道路数量；第2次筛选以行车方向为长轴作椭圆形，剔除没有经过椭圆形区域的候选路段，进一步减少计算量，确定最终的路段检索区域。

建立网格索引，以l(依据工程经验一般选取200 m)为边长划分网格，以G(gx，gy)为分块网格索引号。若定位点为P(i，j)，则定位点的网格索引号为：

(1)

图1 路段检索区域示意图

图1为路段检索区域示意图。如图1所示，以定位点P(i，j)为中心的3×3的网格区域为经过第1次筛选后的路段检索区域，此时候选路段为A、C；接着以行车方向为长轴作椭圆形，则可以排除路段C，区域内的路段A为经过第2次筛选后的候选路段，确定路段A作为车辆定位点P的最佳匹配路段。

图1中，a为路段检索区域长轴的1/2，b为短轴的1/2，Ψ为a与正北方向之间的角度，且Ψ≤π。a、b和Ψ由以下公式确定[18]：

(2)

(3)

(4)

2 匹配程度

点到线的匹配算法把全部路段都视为候选路段，计算定位点到所有路段之间的垂直距离，由最小距离确定最佳匹配路段。如果点到几条路段的距离都相等，那么会造成无法执行匹配的情况，从而发生错误。与点到点的匹配算法相比较，点到线的匹配算法的准确率有所提升，但是未考虑道路拓扑结构和车辆行驶轨迹曲线等因素，因此稳定性相对较差，容易产生错误匹配。

本文在传统算法的基础上，引入车辆行驶速度和历史匹配程度两个因素，采用多个因素重新定义匹配程度的概念，并将距离权重因子改为动态，应用到基于HMM的地图匹配算法中，可在一定程度上改善本文算法的时效性和准确率。定位点与候选匹配路段的匹配程度为：

(5)

其中：α为距离权重因子；D为待匹配点与候选路段间距离的特征值参数；dlp为定位点P到候选路段l的投影距离；β为角度权重因子；θ为车辆此时行进方向与候选路段之间夹角的特征值参数；ω为车辆行驶方向与路段方向的夹角；γ为速度权重因子；v为车辆此时速度的特征值参数；τ和lτ分别为行驶时间和距离；λ为历史匹配程度权重因子；M′为历史匹配程度；Mik为第k个定位点到第i条候选路段的匹配程度；j为当前定位点数。

3 基于HMM的改进算法

本文提出的改进算法主要包括两部分：数据预处理以及改进地图匹配算法。匹配算法流程图如图2所示。数据预处理是除去全部无效的、异常的以及冗余的定位数据；改进地图匹配算法包含标准差σ的估计、4个特征值参数的权重因子计算等。

图2 匹配算法流程图

3.1 数据预处理

定位数据会受到多种因素的影响，比如对流层、电离层传播延时，从而产生不可避免的定位误差，使定位点远离候选路段，产生大幅度漂移，这些有误差的定位数据会给地图匹配算法的准确率和时效性带来严重的影响，可能会增加计算量和工作难度。所以，在执行地图匹配算法之前要先将获取的定位数据进行分类、汇总，然后除去全部无效的、异常的以及冗余的定位数据。具体筛选规则如下：

(Ⅰ)如果定位数据远离候选路段，根据定位点构建的路段检索区域内没有候选路段，则这些定位数据为漂移点，视为无效的数据并删除。

(Ⅱ)如果定位数据记录中，在连续时间段内车辆的经纬度坐标出现多次重复，则判定该条数据记录为异常数据并剔除。

(Ⅲ)如果定位数据记录中，同一车辆出现采集时间多次重复的若干条记录，则判定此数据记录为冗余数据，经过处理后只需保留一条格式正确的、不再重复的数据记录，将冗余数据全部删除。

3.2 改进地图匹配算法

为了权衡地图匹配算法的准确率和时效性，本文首先使用多模态鲁棒回归估计，对观测概率矩阵B中的标准差σ进行估计，选取概率最大的两条候选路段；然后引入动态的距离权重因子α，通过多个因素构建的函数分别计算两条候选路段的匹配程度M，其数值较大的候选路段所对应的为最终确定的候选路段。

文献[19]结合时空特性，包括几何、拓扑以及速度等约束条件，采用均值μ=0、标准差σ=20 m的高斯分布表示在隐含状态下得到的观测概率矩阵B：

(6)

可以用一个定位点和候选路段之间距离的高斯分布来表示定位点的误差。文献[20]仍然使用均值μ=0的高斯分布，而标准差σ是采用绝对中位差来进行鲁棒估计，得到了噪声的合理值，σ的计算公式为：

(7)

(8)

本文采用多个因素构造的函数确定匹配程度，并引入动态的距离权重因子，使匹配准确率在一定程度上更优。在路段检索区域内，对于定位点P及其候选路段，若路段检索区域内只有一条候选路段，则该路段为最佳匹配路段；若候选路段不只一条，此时需要对候选路段进行筛选，对候选路段的观测概率进行排序，通过上述方法得到观测概率排名前两位的候选路段la和lb,计算两条候选路段的匹配程度M，其数值较大的候选路段所对应的为最终确定的候选路段。

一些匹配算法的权重因子大多是由主观经验确定的，使得匹配算法的结果差异很大，准确率不稳定[22-24]，针对这个问题，引入动态距离权重因子，使其不再由主观经验确定，可在一定程度上提高本文算法的稳定性。文中提出的匹配程度由4种参数确定，历史匹配程度M′与之前匹配的轨迹数据有关联，可以将其权重因子λ设置为：

(9)

(Ⅰ)确定α值

引入动态的距离权重因子，通过对20 000个定位点的分析得出，距离D小于Dmax=50 m的定位点所占比例接近99%，距离D小于Dmin=0.5 m的定位点所占比例不足1%。综上所述，定义动态的距离因子α为：

(10)

(Ⅱ)确定β值

根据上文分析，路段检索区域内有两条候选路段，得到观测概率排名前两位的候选路段la和lb，定义ρ1和ρ2为两条候选路段的观测概率，相应的评价Rz和β分别为：

(11)

(12)

(Ⅲ)确定γ值

车辆当前的行驶速度与道路网的信息、驾驶人员的行为都有着密不可分的关系，在500 s的时间内对车辆的速度误差进行仿真实验分析，结果如图3所示。

(a) 东向速度误差

(b) 北向速度误差

(c) 天向速度误差

图3 车辆的速度误差

图3a为东向速度误差，经过多次仿真发现速度误差最大值在0.5 m/s以内，并通过计算500 s内的速度误差得出标准差约为0.27 m/s。图3b为北向速度误差，其最大值约为0.8 m/s，取平均值经计算得出标准差约为0.35 m/s。图3c为天向速度误差，其速度误差最大值约为0.5 m/s，取平均值经计算得出标准差约为0.18 m/s。由以上数据可以看出：3个方向速度误差的标准差最大值为0.35 m/s，该值在可接受的误差范围之内，低频采样条件下，完全可以适应各种道路拓扑结构。因此，根据速度误差的仿真结果，当车辆在一定区间内行驶的平均速度小于路网的限制速度时，将其权重因子γ置为1；否则，认为车辆不具备在该路段上行驶的条件，将其权重因子γ置为0。

4 仿真实验

首先通过仿真实验验证本文算法的运行效率，分别从4种不同的路段中随机选取240个定位点，对其单点匹配时间进行统计分析。图4为本文算法与其他3种对比算法的单点匹配时间的仿真结果比较。从图4中可以看出：本文算法的单点匹配时间在5 ms上下浮动，约为5.20 ms；点到线匹配算法的单点匹配时间大部分集中在20～25 ms，约为22.73 ms；固定权重匹配算法的单点匹配时间和传统HMM算法的单点匹配时间大致相同，约为13.81 ms。本文提出的改进算法的单点匹配时间相对较少，在时效性上更加具有优势。

在单一路段、平行路段、交叉路段以及复杂路段4种路段拓扑结构下，对本文算法与其他3种地图匹配算法的准确率进行比较，结果如图5所示。

图4 单点匹配时间仿真结果比较

图5 匹配准确率比较

由图5可知：当车辆在简单路段行驶时，4种匹配算法的准确率都比较高，本文改进算法的匹配准确率和其他3种算法的准确率相近。当车辆驶入平行、交叉甚至更为复杂的路段时，本文改进算法的匹配准确率依然能达到90%以上。随着路况复杂程度的增加，本文算法的准确性明显优于其他3种对比算法的准确性。

当车辆驶入复杂路段时，对4种地图匹配算法位置误差的标准差进行统计，结果见表1。从表1中可以看出：本文算法东向位置误差的标准差为4.30 m，北向为4.36 m，天向为4.26 m，本文算法3个方向的误差比其他3种对比算法的误差都要小，并且位置误差波动的幅度均在可以接受的范围之内。

表1 不同地图匹配算法位置误差的标准差对比 m

5 结束语

本文以基于HMM的匹配算法为基础，采用多个因素定义匹配度，引入动态的距离权重因子，结合几何匹配算法和基于HMM匹配算法的思想，提出一种改进的地图匹配算法，以降低定位点的单点匹配时间，提高算法整体的运行效率，使算法在时效性上更加具有优势。通过仿真验证，改进后的匹配算法准确率有所提高，即使在低频采样条件下，复杂路况的准确率依然可以达到90%以上，与3种传统的匹配算法进行比较，本文算法在时效性和准确性上均有所改善。下一阶段将重点研究高频采样时的算法优化，在保证时效性的前提下获得更高的准确率。