论文部分内容阅读
[摘要]首先给出地图匹配算法的基本原理，对基于投影的地图匹配算法的两种情况，即车辆正常行驶的过程和车辆转弯过程，给出匹配的基本算法。在此基础上提出地图匹配算法的详细匹配过程。实际的验证结果表明基于投影的地图匹配算法对GPS接收器接收到的原始定位信息的校正是有效的。
[关键词]地图匹配 投影距离 方向夹角
中图分类号：TP2文献标识码：A 文章编号：1671－7597（2008）1220023－02
一、引言
随着科学技术的飞速发展，GPS技术已广泛地应用于地面移动目标的跟踪定位。车辆导航跟踪监控系统就是其中众多应用之一。由于车辆GPS的定位数据与电子地图数据都不可避免地存在各种误差，往往会带来车辆行驶轨迹偏离实际道路的问题。为了解决这个问题，目前主要有两种处理方法，一种是采取提高GPS定位精度及电子地图精度的方法，但这种方法成本高，也不可能完全消除定位点与地图之间的这种显示误差；另一种是采用地图匹配方法，即用软件的方法来协调不准确的定位数据和电子地图所造成的显示误差，也就是把定位点依照某种规则强制与实际道路配准，从而保证车辆总在行驶的道路上。目前主要研究的地图匹配算法有基于代价函数的地图匹配、基于模糊逻辑的地图匹配、基于D-S证据推理的地图匹配、基于神经网络的地图匹配以及基于预测的地图匹配方法等[1]。这些算法原理较为复杂，实现难度较大，大多数没有考虑如何消除GPS定位误差对地图匹配的影响。该文设计了一个基于投影的地图匹配算法，将GPS定位点投影到附近的道路上，然后每个定位点的权重值大小来确定车辆当前行驶的道路，该算法充分利用了定位点的当前信息和历史信息，能够有效地降低定位误差对地图匹配效果的影响。
二、地图匹配算法的思想
地图匹配的基本思想[2]是通过车辆的航迹与电子地图上矢量化的路段相近匹配，寻找当前行驶的道路，并将车辆当前的定位点投影到道路上，它的应用基于两个前提：第一，用于匹配的高精度数字地图；第二，车辆行驶在道路上，这样就保证了不会因为定位误差使车辆定位点偏离车辆当前行驶的道路，而且通过投影使车辆定位数据仅保留定位误差在车辆前进方向上的径向分量，从而提高车辆的定位精度。
地图匹配算法是曲线匹配原理和地理空间接近性分析方法的融合，曲线匹配算法的基本思想[3]是：如果对一条曲线做任意数量、任意比例的分割，分割点都落在另一条曲线上，则两条曲线严格匹配。实际应用中，就是计算一条曲线上相对均匀的某一数量分割点到参考曲线的距离的平均值，将其作为到参考曲线的平均距离，并将此平均值的倒数作为匹配优劣的度量；空间接近性分析方法就是在已知可能正确的地理数据集中，按照空间最接近的方法匹配当前定位数据网。
地图匹配算法可分为两个相对独立的过程[4]：一是寻找车辆当前行驶的道路；二是将当前定位点投影到车辆行驶的道路上。其基本方法是按照曲线匹配的思想在车辆航迹的邻近区内搜索所有道路路段及其组合，把这些组合路段分别与车辆航迹求取匹配度量值，将其得到的最佳匹配度量值的组合路线作为车辆的当前行驶路线。
三、基于投影的地图匹配算法的原理
基于投影的地图匹配算法如图1所示，图中P点为待匹配的GPS定位点，L1、L2表示GPS点附近的道路的中心线。在投影匹配算法中，把待匹配的GPS定位点向附近所有道路做投影，计算GPS点与各道路间的投影距离r1，及车辆行驶方向与道路间的夹角，选出r1、值小于给定阙值得所有道路，并根据公式（1）计算各候选道路的距离度量值R1[5] 。
（1）
式中、 分别是投影距离和方向夹角的权值。
在所有候选道路中，选择距离度量值最小的作为匹配道路，即认为车辆正在该道路上行驶。算法最后将车辆在匹配道路上的投影点作为车辆的当前位置加以显示。在图1中，经过以上计算，选择道路L1作为匹配道路，并以P点在L1上的投影点P1作为车辆当前位置。
在处理道路交叉点附近车辆转弯时，根据道路的连通性和车辆的转角，在所有接续道路中，选择角度变化最为接近的道路，作为匹配结果。如图2所示，当车辆在交叉点S处转弯时，车辆行进角度的变化值为 ，原行进道路L0的三条接续道路L1、L2 、L3，与L0之间的夹角分别为。算法将 与 、、进行比较，并综合考虑GPS点与三条道路间的距离，最后选定道路L2作为匹配道路。这个方法的实质是在道路的节点处将投影距离的权值 的减小，而主要考虑行进角度[6]。
四、具体的匹配算法过程
投影地图匹配的具体算法如图3所示，其步骤为：
1．接收GPS定位数据。
当GPS接收器接收到GPS定位信号的时候，将这些信息暂时存储到缓冲区中，如时间、经纬度、高度、速度、方向和几何衰减因子等。
2．判断定位数据是否无效。若无效，则根据历史定位数据进行推测匹配，然后转第8步。
这里判断GPS定位数据是否无效主要是判断GPS接收器传过来的DOP[7]（Dilution of Precision精度衰减因子）是否大于一个数值。一般来说，如果DOP>5，表明GPS接收的数据不正常，转而依据车辆行驶的历史轨迹推测车辆当前可能的位置。要说明的是，这种推测匹配方法是建立在当前车辆正常行驶的前提下，因此，它只能在短时间内起作用。
3．判断车辆当前是否处于停止或滑行状态。若是，对其作相应处理，然后转第8步。
如果在车辆停止或低速滑行接近于停止时，理论上车辆定位点应该保持不动或基本不动。然而，由于GPS定位误差的随机漂移，使得系统定位模块给出的车辆位置信息在以车辆当前实际所处位置为圆心的一个圆形区域内随机抖动[8]。判断发生这种异常的方法是计算当前定位点与其前几个定位点（设计中取为3）的距离，若它们持续小于GPS正常定位时的误差上限，则说明车辆当前基本处于停止或低速滑行状态，此时，可将与当前定位点对应的匹配点作为车辆当前的真实位置而不对后续定位点进行匹配，直到前面的三个距离值开始大于GPS正常定位时的误差上限为止[9]。
4．如果在一定阙值内搜索到的道路数<1，表明车辆不在道路上，退出匹配过程，以当前GPS数据作为车辆的当前位置。
5. 如果在一定阙值内搜索到的道路数=1，表明车辆在道路上，直接投影，把此道路作为车辆行驶的当前道路。
6. 如果在一定阙值内搜索到的道路数>1，并且道路的节点号码相同，表明车辆在节点附近，利用类似图2的方法处理。
7．如果在一定阙值内搜索到的道路数>1，并且道路的节点号码不同，表明车辆在几条相近的道路中的某条上行驶，利用类似图1的方法处理。
8．结束本次匹配。
五、试验分析
图3是GPS接收器接收到的原始定位信息。从这张图上可以看出来，很多定位点都偏离了道路，使得定位信息不准确。
从图4可以看出，经过了MM算法校正后的GPS定位信息相比未校正的定位信息，精确度大大提高。定位点大部分都校正了道路的中心线上，使得整个系统的可用性提高了不少。
六、结论
地图匹配算法在车辆导航跟踪系统起着至关重要的作用。该文设计了一种基于投影的地图匹配算法，该算法原理较为简单，计算方便，有效地利用了定位点的当前信息和历史信息，能够在很大程度上降低定位误差对地图匹配效果的影响，从而大大地降低地图匹配的误配率，对提高导航跟踪系统的性能起着积极的作用。
参考文献：
[1]钟海丽、童瑞华、李军、陈宏盛，GPS定位于地图匹配方法研究，小型微型计算机系统，2003.1.第24卷第1期.
[2]陈佳瑜、肖桂荣，基于权重的地图匹配算法，计算机工程与应用，2005.11.
[3]马建军、唐进君、曹凯，一种新的智能地图匹配算法，计算机应用，2007.12月.第27卷第12期.
[4]Christopher E. White， David Bernstein， Alain L. Kornhauser. Some map matching algorithms for personal navigation assistants. Transportation Research C，2008，8：91-108.
[5]李鑫、徐勇、邓涛，电子地图匹配算法在GPS和DR组合车载导航系统中的作用，国外电子测量技术，2006.5.第25卷第5期.
[6]张小平、王保保、范克利，GPS与数字地图的匹配研究，计算机仿真，2005，22（6）：148-151.
[7]Sinn Kim， Jong-Hwan Kim， Adaptive fuzzy-network-based c-measure map-matching algorithm for car navigation system， IEEE Transaction on Industrial Electronics， 2001，48 （2）：432-441.
[8]常菲、李明禄、李治洪，基于道路分级的地图匹配综合定位技术，微型电脑应用，2004，20（2）：46-48.
[9]陈勇刚、王更生、陈斌，车载地图匹配技术中GPS定位数据的研究，工业控制计算机，2006，19（1）：61-62.
注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”
[关键词]地图匹配 投影距离 方向夹角
中图分类号：TP2文献标识码：A 文章编号：1671－7597（2008）1220023－02
一、引言
随着科学技术的飞速发展，GPS技术已广泛地应用于地面移动目标的跟踪定位。车辆导航跟踪监控系统就是其中众多应用之一。由于车辆GPS的定位数据与电子地图数据都不可避免地存在各种误差，往往会带来车辆行驶轨迹偏离实际道路的问题。为了解决这个问题，目前主要有两种处理方法，一种是采取提高GPS定位精度及电子地图精度的方法，但这种方法成本高，也不可能完全消除定位点与地图之间的这种显示误差；另一种是采用地图匹配方法，即用软件的方法来协调不准确的定位数据和电子地图所造成的显示误差，也就是把定位点依照某种规则强制与实际道路配准，从而保证车辆总在行驶的道路上。目前主要研究的地图匹配算法有基于代价函数的地图匹配、基于模糊逻辑的地图匹配、基于D-S证据推理的地图匹配、基于神经网络的地图匹配以及基于预测的地图匹配方法等[1]。这些算法原理较为复杂，实现难度较大，大多数没有考虑如何消除GPS定位误差对地图匹配的影响。该文设计了一个基于投影的地图匹配算法，将GPS定位点投影到附近的道路上，然后每个定位点的权重值大小来确定车辆当前行驶的道路，该算法充分利用了定位点的当前信息和历史信息，能够有效地降低定位误差对地图匹配效果的影响。
二、地图匹配算法的思想
地图匹配的基本思想[2]是通过车辆的航迹与电子地图上矢量化的路段相近匹配，寻找当前行驶的道路，并将车辆当前的定位点投影到道路上，它的应用基于两个前提：第一，用于匹配的高精度数字地图；第二，车辆行驶在道路上，这样就保证了不会因为定位误差使车辆定位点偏离车辆当前行驶的道路，而且通过投影使车辆定位数据仅保留定位误差在车辆前进方向上的径向分量，从而提高车辆的定位精度。
地图匹配算法是曲线匹配原理和地理空间接近性分析方法的融合，曲线匹配算法的基本思想[3]是：如果对一条曲线做任意数量、任意比例的分割，分割点都落在另一条曲线上，则两条曲线严格匹配。实际应用中，就是计算一条曲线上相对均匀的某一数量分割点到参考曲线的距离的平均值，将其作为到参考曲线的平均距离，并将此平均值的倒数作为匹配优劣的度量；空间接近性分析方法就是在已知可能正确的地理数据集中，按照空间最接近的方法匹配当前定位数据网。
地图匹配算法可分为两个相对独立的过程[4]：一是寻找车辆当前行驶的道路；二是将当前定位点投影到车辆行驶的道路上。其基本方法是按照曲线匹配的思想在车辆航迹的邻近区内搜索所有道路路段及其组合，把这些组合路段分别与车辆航迹求取匹配度量值，将其得到的最佳匹配度量值的组合路线作为车辆的当前行驶路线。
三、基于投影的地图匹配算法的原理
基于投影的地图匹配算法如图1所示，图中P点为待匹配的GPS定位点，L1、L2表示GPS点附近的道路的中心线。在投影匹配算法中，把待匹配的GPS定位点向附近所有道路做投影，计算GPS点与各道路间的投影距离r1，及车辆行驶方向与道路间的夹角，选出r1、值小于给定阙值得所有道路，并根据公式（1）计算各候选道路的距离度量值R1[5] 。
（1）
式中、 分别是投影距离和方向夹角的权值。
在所有候选道路中，选择距离度量值最小的作为匹配道路，即认为车辆正在该道路上行驶。算法最后将车辆在匹配道路上的投影点作为车辆的当前位置加以显示。在图1中，经过以上计算，选择道路L1作为匹配道路，并以P点在L1上的投影点P1作为车辆当前位置。
在处理道路交叉点附近车辆转弯时，根据道路的连通性和车辆的转角，在所有接续道路中，选择角度变化最为接近的道路，作为匹配结果。如图2所示，当车辆在交叉点S处转弯时，车辆行进角度的变化值为 ，原行进道路L0的三条接续道路L1、L2 、L3，与L0之间的夹角分别为。算法将 与 、、进行比较，并综合考虑GPS点与三条道路间的距离，最后选定道路L2作为匹配道路。这个方法的实质是在道路的节点处将投影距离的权值 的减小，而主要考虑行进角度[6]。
四、具体的匹配算法过程
投影地图匹配的具体算法如图3所示，其步骤为：
1．接收GPS定位数据。
当GPS接收器接收到GPS定位信号的时候，将这些信息暂时存储到缓冲区中，如时间、经纬度、高度、速度、方向和几何衰减因子等。
2．判断定位数据是否无效。若无效，则根据历史定位数据进行推测匹配，然后转第8步。
这里判断GPS定位数据是否无效主要是判断GPS接收器传过来的DOP[7]（Dilution of Precision精度衰减因子）是否大于一个数值。一般来说，如果DOP>5，表明GPS接收的数据不正常，转而依据车辆行驶的历史轨迹推测车辆当前可能的位置。要说明的是，这种推测匹配方法是建立在当前车辆正常行驶的前提下，因此，它只能在短时间内起作用。
3．判断车辆当前是否处于停止或滑行状态。若是，对其作相应处理，然后转第8步。
如果在车辆停止或低速滑行接近于停止时，理论上车辆定位点应该保持不动或基本不动。然而，由于GPS定位误差的随机漂移，使得系统定位模块给出的车辆位置信息在以车辆当前实际所处位置为圆心的一个圆形区域内随机抖动[8]。判断发生这种异常的方法是计算当前定位点与其前几个定位点（设计中取为3）的距离，若它们持续小于GPS正常定位时的误差上限，则说明车辆当前基本处于停止或低速滑行状态，此时，可将与当前定位点对应的匹配点作为车辆当前的真实位置而不对后续定位点进行匹配，直到前面的三个距离值开始大于GPS正常定位时的误差上限为止[9]。
4．如果在一定阙值内搜索到的道路数<1，表明车辆不在道路上，退出匹配过程，以当前GPS数据作为车辆的当前位置。
5. 如果在一定阙值内搜索到的道路数=1，表明车辆在道路上，直接投影，把此道路作为车辆行驶的当前道路。
6. 如果在一定阙值内搜索到的道路数>1，并且道路的节点号码相同，表明车辆在节点附近，利用类似图2的方法处理。
7．如果在一定阙值内搜索到的道路数>1，并且道路的节点号码不同，表明车辆在几条相近的道路中的某条上行驶，利用类似图1的方法处理。
8．结束本次匹配。
五、试验分析
图3是GPS接收器接收到的原始定位信息。从这张图上可以看出来，很多定位点都偏离了道路，使得定位信息不准确。
从图4可以看出，经过了MM算法校正后的GPS定位信息相比未校正的定位信息，精确度大大提高。定位点大部分都校正了道路的中心线上，使得整个系统的可用性提高了不少。
六、结论
地图匹配算法在车辆导航跟踪系统起着至关重要的作用。该文设计了一种基于投影的地图匹配算法，该算法原理较为简单，计算方便，有效地利用了定位点的当前信息和历史信息，能够在很大程度上降低定位误差对地图匹配效果的影响，从而大大地降低地图匹配的误配率，对提高导航跟踪系统的性能起着积极的作用。
参考文献：
[1]钟海丽、童瑞华、李军、陈宏盛，GPS定位于地图匹配方法研究，小型微型计算机系统，2003.1.第24卷第1期.
[2]陈佳瑜、肖桂荣，基于权重的地图匹配算法，计算机工程与应用，2005.11.
[3]马建军、唐进君、曹凯，一种新的智能地图匹配算法，计算机应用，2007.12月.第27卷第12期.
[4]Christopher E. White， David Bernstein， Alain L. Kornhauser. Some map matching algorithms for personal navigation assistants. Transportation Research C，2008，8：91-108.
[5]李鑫、徐勇、邓涛，电子地图匹配算法在GPS和DR组合车载导航系统中的作用，国外电子测量技术，2006.5.第25卷第5期.
[6]张小平、王保保、范克利，GPS与数字地图的匹配研究，计算机仿真，2005，22（6）：148-151.
[7]Sinn Kim， Jong-Hwan Kim， Adaptive fuzzy-network-based c-measure map-matching algorithm for car navigation system， IEEE Transaction on Industrial Electronics， 2001，48 （2）：432-441.
[8]常菲、李明禄、李治洪，基于道路分级的地图匹配综合定位技术，微型电脑应用，2004，20（2）：46-48.
[9]陈勇刚、王更生、陈斌，车载地图匹配技术中GPS定位数据的研究，工业控制计算机，2006，19（1）：61-62.
注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”