5.1算法模型
弧段中(离交叉路口有一定距离)的地图道路匹配过程，就是基于已知的信息及当前GPS位置g(k)求得地图匹配修正量e(k)，参见图5.1。
图5.1弧段上的地图道路匹配过程示意图
设当前为时刻k , 历史数据包括车辆GPS轨迹点g(k -1) 、地图道路匹配点p(k -1) 、匹配修正量e(k-1)都是已知的。当前数据包括GPS轨迹点g(k)以及g(k)的道路弧段横向偏差eh(k) 也是已知或可以立即计算出的确定量。根据论文第三章中关于GPS主要误差相对稳定的结论，引入预测校正点
定义为
(5.1)
在没有更多信息的时候，取预测校正点的弧段Si 最近点q.(k)作为k时刻的车辆位置g(k)的地图道路匹配点p(k)是很自然合理的选择。所产生的预测补偿记为
(5.2)
e (k)补偿.. GPS误差的慢漂移和地图道路误差的微变，严格来说.. e (k)主要校正的是.. GPS误差漂移和道路误差变化在垂直于道路方向的分量ev(k) ，进而可以保证其对于后续轨迹的垂直道路方向上的修正量ev(k) 的准确性。匹配修正量.. e(k)的实时校正公式如下：..
e(k) = e(k -1) + e (k) = p(k) -g(k) (5.3)
匹配修正量e(k)的实时校正。考虑到车辆运行过程中有一些偶然误差.. (多路径原因或者信号干扰)对.. GPS轨迹产生脉冲扰动，单独用公式 (5.3)可能会使道路匹配的预测偏差修正量e(k)产生比较大的扰动。为了平滑这种扰动，我们采用前.. 3个GPS轨迹点和匹配点距离的平均值来修正e(k)：..
(5.4)
5.2初始阶段匹配道路的选取与利用
e(k)的车辆轨迹实时匹配导航系统刚开始工作时，道路匹配的匹配修正量.. e(k)还没有被赋以有效值。初始阶段的主要目标是确定车辆实际运行的道路弧段Si 。由于在后续轨迹点的匹配过程中会用到历史轨迹匹配结果，所以如果初始阶段的匹配道路弧段.. Si 判定错误会严重影响后续轨迹的匹配准确性。在这一阶段，我们综合考虑轨迹到匹配弧段Si的距离最短和.. GPS测定的车辆速度与弧段Si延伸的方向一致性(方向夹角在.. 30o内定义为方向一致)，特别是后一条件来判定车辆当前行驶的弧段.. Si 。由于单个初始轨迹点用这种方式也可能出现误判，特别是接近交叉路口处，实际的计算中采用连续匹配在同一条弧段Si 上的轨迹点数大于或等于某个阈值，则确认该弧段是当前轨迹的匹配弧段。匹配弧段阈值记为.. Ceff ，测试程序取.. Ceff = 6 。这里的连续匹配以车辆速度与某些弧段例如Si ，Sj 延伸的方向一致性为标准，满足这一条件后 选择弧段横向修正量ev (k)[Si ]最小的那条弧段.. Si。
在车辆行驶过程中，我们获得了虚拟差分向量.. ediff后，可以对车辆实时.. GPS轨迹点进行地图匹配。首先我们利用.. ediff对当前轨迹点g(k) 进行校正。根据公式 （5.1）用.. ediff作为差分量对.. g(k) 校正获得点。这时的点已经被消除了沿道路方向和垂直于道路方向的主要误差。因为.. GPS误差漂移的存在以及可能的地图道路误差变化，..并不一定落在地图道路上，这时我们利用从车载.. GPS获得的
车辆速度、方向信息以及地图拓扑结构信息和历史匹配数据来将.. p.(k)匹配到对应道路的对应位置上。
由于车辆位置在远离交叉路口处的匹配道路选择简单，而在交叉路口附近由于道路情况的复杂非常容易误判，从算法效率和匹配准确率两方面考虑，我们对于在远离交叉路口处和交叉路口附近的校正轨迹点p.(k)采取不同的匹配方法。首先我们确定前一时刻选择的匹配道路弧Si 的两个端点
和
。计算预校正后的轨迹点位置
xpk , y pk ) 分别到.. 
和
的距离.. dik和djk 。..
设置临近交叉口的判断阈值为deffect ，deffect 越大，误识别率越低，实时性越差（我们在测试程序中取值为.. 50m）。如果.. dik >=djk ，并且.. d jk <deffect ，则判断临近节点.. nj。如果.. d jk >=dik ，并且.. dik <deffect ，则判断
临近节点
。
当与两个端点都不临近时，说明车辆在远离交叉口的道路上行驶，这时根据车辆行驶道路的连续性，判断的匹配路段为Si，将垂直映射到Si上获得匹配点。
当临近节点ni时，说明此时车辆位置在交叉口附近，我们就要根据导航系统的各种输入信息以及地图信息来准确判断车辆所处的道路，保证匹配路段的选择是最重要的，因为会关系到后续路段上的路段匹配的准确性。我们用来判断匹配路段主要根据车辆的方向信息h(k)，经过预校正的.. GPS轨迹位置以及地图的拓扑关联。但是由于当车辆速度.. v(k)低于一定程度.. veffect时（经过实验证明是10.8km/h也就是.. 3m/s），车辆方向误差比较大，可信度低，所以我们在利用车辆的方向信息h(k)时要先判断车辆速度v(k)是否大于有效阈值veffect（测试程序中取值为.. 11km）。具体过程描述如下：
如果v(k) >veffect，计算到与ni相连接的各条弧的距离，确定距离最小弧.Sl（l可以等于 i），如果此时 h(k)方向与Sl方向（为方向起始点）的夹角
小于预先设定的阈值beffect (测试程序中我们设定为30度)，则判断的匹配路段是Sl ，将垂直映射到Sl 上，获得。如果此时大于或者等于beffect ，就说明用最短距离和方向判定法选取的匹配路段不一致，则此时的匹配点位于节点（临近节点，也就是将车辆位置显示在道路交叉口处）。如果v(k) <=veffect，说明此时的方向信息h(k)无效，将的匹配点p(k )位置确定在上一时刻匹配位置p(k -1) 上。
5.3转弯过程后的地图匹配修正量的自动更新
地图匹配修正量定时更新指的是在一定条件下避免使用实时校正公式(8-10)而获得新弧段Sj 上全新的准确的e(k)[ Sj ] 。当车辆经过交叉路口时，车辆在地图上的准确匹配点是一个确定的交叉路口位置
。在这种情况下，有可能实现匹配修正量从上一弧段.. e(k)[Si ] 到当前弧段e(k)[ Sj ] 的一次更新。
为了提高e(k)更新的准确性与可靠性，我们只对符合一定条件的转弯进行利用。先设定几个变量，设定车辆轨迹匹配到当前路段上的轨迹点个数为Ccurrent，车辆轨迹匹配到前一路段上的轨迹点个数为Clast。当轨迹点匹配到一个新的路段上时，.. Clast=Ccurrent并对Ccurrent置.. 0，即Ccurrent=0。之后每获得一个匹配在当前路段上的轨迹点并且匹配点不在道路端点上（避免交叉路口处长时间等待带来的误差），对Ccurrent加1。用符号a来表示当前路段与上一路段的夹角（锐角）。我们设定.Ceff表示一个预先设定的匹配在某路段上点的个数的阈值，Ceff越大，获得的ediff稳定性越高，但是实时性越差（在我们的测试程序中设置为6）。用a eff表示一个预先设定的当前路段与运行的上一路段夹角的阈值，同Ceff 一样，aeff越大，获得的.ediff稳定性越高，但是实时性越差（在我们的测试程序中设置为30度）。
为了减少短时间连续转弯的不稳定性和计算误差，我们选取用来计算获得虚拟差分向量的转弯有以下条件：
1）Ccurrent=Ceff并且Clast>=Ceff（5.5）
2）a >aeff (5.6)
当条件1）2）得到满足时，由于弧段纵向修正量ev (k)[Sj ]总是已知 (方程5)，所以匹配修正量e(k)[Sj ] 的初始更新转化成为弧段纵向修正量eh (k)[Sj ] 的初始更新。图5给出了直观的求解过程示意图，分析如下。
如果在道路转弯前和转弯后各选取一个点g(k1) 和g(k2) ，根据.. GPS误差的慢漂移特性，如果地图准确，应该有
(5.7)
事实上在转弯处，也就是前一弧段Si 上的终端同时又是当前道路弧段Sj 上的始段处(图.. 5.2中对应标注Ccurrent = 0 的大节点
)的g(k)有严格的..
(5.8)
参考图.5.2左上部的两个几何分析示意图易知，将矢量e(k1) 在ev(k2) 与eh(k2)方向上作正交分解，可得各分量值为..
(5.9)
(5.10)
同样的将矢量e(k2) 在ev(k1) 与eh(k1) 方向上作正交分解，可得各分量值为
将方程(5.11)与(5.12)两边分别同乘以
与
再相加，整理得出e(k2) 在新的道路弧段上的纵向偏差分量eh(k2) 的幅值为
(5.13)
注意到ev (k1)[Si ] 与ev (k2 )[Sj ] 均是已知确定性变量，选用公式(5.13)计算eh (k)[Sj ]可以完全消除上一弧段上纵向积累偏差eh (k1)[Si ] 的影响，获得准确的纵向偏差更新eh (k2 )[Sj ]。
图5.2 更新偏差修正量e(k)的过程示意图
上述推导过程，假设地图较为准确，其时实际上的eh (k1)[Si ]也较为准确，所以利于图5的分析。必须指出，当地图不够准确，不能保证e(k2)[Sj ] .e(k1)[Si ] 。原因是eh (k1)[Si ]误差积累较大，会出现如图5.2所示的车辆运行及匹配过程。同样的推导过程表明，弧段纵向修正量的更新值eh (k2 )[Sj ] 的计算公式仍然如(5.13)所示。
如图5.3所示，对应标注Ccurrent = 0 的时刻，弧段纵向修正量已经从eh (k )[Si ]自动更新为eh (k)[Sj ] ，相应地，地图匹配修正量也从e(k)[Si ] 自动更新为e(k)[Sj ] 。事实上前一弧段.. Si上的地图匹配修正量e(k)[Si ]预侧的道路转弯路口为节点
，由于矢量地图的误差，矢量道路转弯路口为节点(1) nj。可见e(k )[S ] 实际hi上已经积累的误差eerror (k)[Si ] =
-
。地图匹配修正量自动更新正好完全补偿了这一误差，即：
(5.14)
方程(5.14)说明匹配修正量自动更新同时获得了交叉路口道路弧段的零误差匹配。
图5.3地图误差较大时的匹配修正量e(k)更新示意图
地图匹配修正量的自动平滑更新：在实际应用中，单次选取g(k1) 和g(k2) 计算使用式(20)可能受到随机干扰影响计算结果，所以采用多点匹配方法平滑更新数值计算。在前一弧段的最后Ceff 个轨迹点的弧段横向修正量的平均值
来代替ev(k1) ，用当前弧段前Ceff个轨迹点到当前弧段的弧段横向修正量的平均值
来代替| ev(k2)| ，即
由方程(5.(0) 15)获得e(k2)
异常轨迹点的排除问题：在车载GPS接收仪确定车辆轨迹的时候，某些误差因素的漂移是可以接受的，但是某些时刻，GPS信息由于某些特殊原因或者信号受损，或者接收设备出现暂时异常，会得到明显错误的信息，这些信息不能用来确定车辆当时的位置，而且也不应该用来更新算法中的参数信息，否则会极大的影响后续匹配的准确性和整个算法的稳定性。这样的异常轨迹点需要进行舍弃，对轨迹点g(k)是否异常的判定主要依据正常校正过程中匹配修正量e(k)[Si ] 不会发生突变。异常轨迹点e(k)[Si ] 的判据为
式中
为g(k) GPS定位信号误差可信阈值,程序设定为= 30m 。
判断该轨迹点异常，则不使用该次匹配修正量e(k)[Si ] 进行校正点p(k)的记录与显示。
5.4算法程序流程概要描述
启动预置初值： k= 0 ； e(0) = (0, 0) 。
Step 1: k= k + 1，接收g(k)，由方程(5.1-5.4)计算得出
)，e (k)与e(k)。检查g(k)是否异常轨迹点(方程
5.20)如是转到Step 1。
Step 2：如果匹配弧段Si 已确定转到Step 5。
Step 3：匹配弧段Si 的判定，5.2中方法。转到Step 1。
Step 4：临近交叉路口判定。如属于临近交叉路口，开始交叉路口新弧段的判定，转到Step5。
Step 5：垂直映射确定匹配点p(k )，如果满足预测修正量的更新条件则转到Step6，否则转到Step1。
Step 6：利用转弯前后的历史轨迹更新预测修正量（论文5.3部分的方法），转到Step1.
5.5算法效果
经过交叉路口实现零匹配误差的匹配修正量自动更新的地图匹配算法应用于实际车辆导航系统来检验算法效果。采用了大量实际数据进行测试。
表5.1 是用实际车辆导航系统检测新算法的测试数据，用来检查新算法利用自动更新的匹配修正量对匹配点的实时校正作用表现在对道路横向偏差和纵向偏差两方面的校正效果。在测试过程中对比了加进匹配修正量自动更新功能前后的地图匹配算法的效果。这种算法除了没有对轨迹点用修正量进行校正的步骤，其
他都与新算法一致。由于不能解决沿道路方向上存在的GPS误差和地图误差，在交叉路口处的匹配误差明显高于采用新算法。
表5.1加进匹配修正量自动更新功能前后的匹配效果比较
图5.4新算法对道路纵向偏差的修正效果
测试过程利用轨迹与道路网的匹配并对其位置调整获得轨迹点的准确位置。计算原始GPS轨迹点和经过匹配修正量自动更新实时校正后的点到这些准确位置的距离并做出相应的曲线图如图5.4所示。曲线Raw GPS Points（上）显示的是GPS原始轨迹与其在匹配道路上对应位置的距离，曲线Pre-corrected Points(下)是经过差分修正量校正后的点到对应位置的距离。两个曲线的横坐标是轨迹采集时间，单位s；纵坐标是与准确位置的偏差距离，单位km。从图中可以看出新算法校正后的轨迹点，到对应位置的距离97%都在 10m以内，少量点超过10m，在20m范围左右，而且明显误差要比GPS原始轨迹小。
为了检验新算法对于地图误差的修正效果，我们手动将道路移动到不准确位置，形成平移误差和旋转误差进行测试如图5.5所示。实验过程中，对于地图平移误差，新算法有很好的校正匹配效果；对于地图局部旋转误差也有着明显的校正效果，但是当旋转误差比较大时，还是会在交叉路口附近出现误识别。
map-matchingresultwithtranslationmaperror map-matchingresultwithrotationmaperror
图5.5新算法对于平移地图误差和旋转误差的校正结果
图5.6，5.7，5.8展示我们应用新算法于实际导航系统中的地图匹配效果。图8 是原始GPS轨迹，图9是经过预校正后的轨迹，我们可以发现轨迹点已经在沿道路方向和垂直道路方向发生移动，更靠近匹配弧段。图10是最终地图匹配效果。我们的实验是在中等城市合肥进行的，根据图8可以看出，GPS轨迹误差的慢漂移特性还是比较明显的。
图5.6车辆在合肥市市区道路上运行的原始GPS 轨迹
图5.7仅使用匹配修正量实时校正的地图匹配效果
图5.8加入匹配修正量更新功能的实时校正结果
5.6算法评论与总结
新算法利用了GPS信号误差的慢漂移特性以及交通矢量地图误差的连续变化特性，利用前面时刻获得的
GPS轨迹与道路上对应位置之间的匹配偏差量获得当前时刻的预测偏差，使用最近点方法完成当前匹配偏差量的实时校正，获得较为准确的车辆轨迹匹配点。由于在地图匹配过程在经过交叉路口时实现了对轨迹修正量的更新，保证了对GPS误差变化的跟踪。通过将仿真实验证明了算法的有效性。新算法应用于实际车辆导航系统和也证明了新算法对于提高地图匹配的准确性与可靠性的作用。与现有算法相比，在保证实时性和道路选择可靠性的同时，不仅对于垂直道路方向上的误差有比较好的校正效果，而且对于沿道路方向上的匹配误差有显著效果，这是新算法明显优于其他算法的地方。
实际上，新算法的核心功能——用从历史轨迹中获得的修正量校正轨迹点的功能模块可以被应用于大量的已有算法程序中，对这些算法进行改进，取得功能互补的最优效果。因为根据介绍可以看出差分修正量修正原始轨迹过程相对独立。完全可以在已有算法中加入差分修正量自动更新过程，以实现原算法在已有优势的情况下增加沿道路方向的误差校正功能。
新算法对于平移地图误差和较小的旋转地图误差有着比较好的校正效果，但是对于比较严重的旋转误差还是无能为力，这种误差本质上改变了相关道路的长度比例，如何能够有效解决这一问题将是我们研究的一个方向。
