论文部分内容阅读
摘要：本文讨论了车辆导航系统中GPS实时信息在数字地图上的匹配问题。分析了由于GPS精度误差以及道路网复杂等因素而可能造成直接定位不准确问题，提出了基于GPS实时信息的地图匹配算法，一方面考虑了GPS点的轨迹与道路网的相似性，另一方面也充分利用了GPS数据中有关车辆的实时信息，如航向等，提高了定位的准确性。
关键词：全球定位系统；地理信息系统；车辆导航；地图匹配
中图法分类号：TP368 文献标识码：A文章编号：1009-3044(2007)04-11021-03
1 引言
在车辆监控系统中，GPS卫星可以为全球绝大多数地方提供全天候、连续的实时定位导航测量。但是GPS定位，由于受卫星数据误差、数据传输误差、接收机钟差、接收机的测量误差等的影响，定位精度会产生较大的偏差。另外，在城市路段复杂的情况下，往往会出现高楼或高架桥阻挡，使接收机对部分卫星失去锁定，GPS数据产生漂移。这时就会有较大的偏差甚至失去信号，使得GPS数据的连续性受到一定的影响。航位推算是一种完全自主的导航系统，利用车速传感器来实现车辆定位，这种传感器在低速时并不可靠，使得用该传感器作为定位模块输入时，难于进行精确车辆定位。航位推算受方向探测仪及车速脉冲设备精度的限制，测量是一个累积的过程，因为不同时刻的测量误差都会累积起来，所以随着时间的推移，如果不补偿或不适当地补偿累积误差，车辆位置计算会变得越来越不精确，因此，单独的航位推算系统不能用来进行长时间的独立定位。由于GPS和航位推算都无法提供足够高的定位精度。因此，在实际系统中通常采用地图匹配（MapMatching-MM）[1]-[3]方法来提高GPS和DR定位的精度。在地图精度有保证的前提下，地图匹配算法可以大大改善GPS自主导航系统的定位精度。
2 地图匹配算法
本文地图匹配算法是在Bernstein D., White[4]-[7]等人的研究基础上，一方面充分考虑了GPS轨迹与道路网路段的相似性，另一方面也充分利用了GPS数据中有关车辆的实时信息（如航向等）。算法中利用GPS定位数据作为输入数据，其中包括位置、速度、时间等，有助于提高定位的准确性。
2.1 道路网定义
道路网G由一组曲线组成，每条曲线也可以称为弧段，假定每条弧段是线性的，弧段E∈G可以用一个有限点序列（P0，P1，…，Pn）表示，也就是说E由线段的端点组成，其中线段E的端点P0，Pn称为结点，P1，…，Pn-1称为形状点。结点是一条弧段的起点或终点，而P1，…，Pn-1用来表示弧段的几何信息。结点可能是一个终点，对应于道路网G中的道路的尽头，也可能是一条弧段到另一条弧段的过渡点，对应于道路网G中的交叉点。
2.2 地图匹配过程
本算法中把弧段数据、结点数据以及GPS定位数据作为输入数据。首先进行初始化处理，用结点匹配的方法来确定一条正确的弧段，该弧段是从与GPS点距离最近的结点相连接的所有弧段中找到，然后确定GPS点在弧段上的具体位置。下一步分析下一个GPS点是否还在该弧段上，然后确定它所在弧段的具体位置。在这里，第一步是至关重要的，因为候选弧段可能会有很多，而且后续匹配过程也是在第一步的基础上进行的。下面详细描述地图匹配的过程。
2.2.1 在候选弧段中找出正确的弧段
地图匹配算法最难的一项工作就是在候选弧段中找出正确的弧段，一般可通过计算权值的方法来选择正确的弧段。根据连续的两个GPS点所组成的线段与道路网弧段之间的相似度，点到道路弧段的接近度，GPS轨迹线与道路弧段夹角的大小，计算出候选弧段的权值。
（1）计算车辆航向与道路方向的权值
图1 车辆航向与道路方向的相似性
假设已经确定GPS点P1，P2，P3匹配到弧段1上面，下面的问题是确定P4所在的弧段，由于车辆当前位置是在弧段1上，点P4的候选弧段是2，3，4。运用权值公式来选择正确的弧段，图1中的β角表示车辆在点P4的航向（用车辆在该点的航向与正北之间的夹角表示），用车辆航向与候选弧段之间的夹角Δβ来计算权值。
WSH=AHCOS（Δβ′） （1）
其中：
AH（>0）是加权参数，它的值可以从式（7）获取。需要注意的是，Δβ′值越小的候选弧段成为正确弧段的可能性就越大。
（2）计算点和弧段接近度的权值
接近度测试可选用两种类型的权值，第一种是基于GPS点到弧段的垂直距离，见图2。
图2 GPS点到路段的垂直距离
假设P（X3,Y3）是GPS点，AB是弧段，因此点P到弧段AB的垂直距离是
用递减函数计算垂直距离的权值
其中：WSPD是点到弧段的接近度权值
D是GPS点到弧段的垂直距离
AP（>0）是加权参数，从式（3）可以看出，垂直距离越小，权值就越高，也就是说，如果点Pi越靠近弧段i，那么该弧段越有可能是正确的弧段。
另一种计算接近度的方法是测试两个连续GPS点，P(xi-1,yi-1)和P(xi,yi)组成的线是否与弧段i物理相交，这两条线的接近程度用它们之间的夹角θ表示，θ是锐角。夹角θ越小说明接近度越好。如果两条线不相交，则权值为0。
计算接近度的权值公式为：
其中：WSPI是夹角的权值，如果夹角存在的话
AP与上面定义的一样
（3）点相对于弧段位置的权值
图3 GPS点到与最近结点相邻的路段的相对位置
图3中P(xi,yi)是GPS点，变量α1，α2，α3，α4分别表示该点到弧段1，2，3，4的相对位置，由于该点映射到弧段2或弧段3的可能性比较大，那么到弧段2和弧段3的权值必须大于到其它弧段的权值，也就是说，角度越大，那么匹配到该弧段的可能性就越小。下面是计算权值的公式：
其中：WSRP是GPS点相对于弧段的权值
α（≤180°）是候选弧段与最近结点和该点之间连线的夹角
ARP（>0）是加权参数，控制WSRP的大小，它的值可以从式（7）中得到
（4）计算总权值
总的权值可以通过累计所有的权值得到，因此权值总和计算如下：
通过选择加权参数的不同值，就能得到总权值，由经验表明，航向权值（WSH）应该比相对位置WSRP更重要，另外，相对位置WSRP也应该比接近度权值（WSPD+WSPI）更为重要，下面的公式计算加权参数：
其中：a和b是加权因子，并且a>b>1，在确定a和b后，总权值是AP的倍数，在理论上，AP可以取任一正值，AP的取值不会影响最终的结果。
然后计算所有候选弧段的的TWS值，把权值最大的弧段作为GPS点的匹配弧段。
2.2.2 确定车辆在选定弧段的位置
在确定车辆所在的正确弧段后，下一步就是确定车辆在该弧段的具体位置，见图4。
图4 估算GPS点在路段的位置
GPS定位点在点PS以ES和NS表示，在路段上的投影如下式（8）：
其中点CP(PES,PNS)为GPS点PS(ES,NS)在路段上的投影点。
2.2.3 检测车辆是否仍然在当前弧段上
前一个GPS点在正确弧段上确定车辆位置后，需要检测车辆是否仍然在该弧段上，下面引入两个测试条件：
（1）两个连续GPS点航向之间的角度之差小于45°
（2）当前GPS点与当前选中弧段的夹角小于90°
如果上面任意一个条件不成立，则假定车辆开始接近交叉点并且初始化地图匹配过程，否则，车辆仍然在前面的弧段上并计算新的位置。
3 算法测试
为了验证本章地图匹配算法的有效性，在图5中给出了利用该算法对实际车辆行驶数据的处理结果。这里使用的原始数据是在镇江市中心地区获取的车辆行驶轨迹，行车路线是梦溪广场－环城路－中山东路－中山西路。其中黑色点形成的轨迹为原始GPS定位轨迹，红色点形成的轨迹是经过地图匹配算法校正后的轨迹。从图5可以看出，在市区道路网比较复杂的情况下，运用本文的算法，可以保证GPS点在电子地图的准确定位。
图5 镇江市区道路图
参考文献：
[1]Jong-Sun Pyo. Development of a map matching method using the multiple hypothesis technique [C]. IEEE Intelligent Transportation Systems Conference Proceedings, 2001.
[2]Rajashri R. Joshi. A New Approach to Map Matching for In-Vehicle Navigation Systems: The Rotational Variation Metric [C]. IEEE Intelligent Transportation Systems Conference Proceedings, 2001.
[3]Valentin Enescu, Hichem Sahli. Multiple model estimation scheme for map-matching [C]. The IEEE 5th International Conference on Intelligent Transportation Systems 3-6 September 2002.
[4]Sinn Kim, Jong-Hwan Kim. Adaptive Fuzzy-Network-Based C-Measure Map-Matching Algorithm for Car Navigation System [J]. IEEE Transactions On Industrial Electronics, Vol. 48, No. 2, April 2001.
[5]Sinn Kim, Jong-Hwan Kim. Q-factor Map Matching Method Using Adaptive Fuzzy Network [C].IEEE International Fuzzy Systems Conference Proceedings. August 22-25, 1999.
[6]Sotiris Brakatsoulas. On Map-Matching Vehicle Tracking Data [C]. Proceeding of the 31st VLDB Conference. 2005
[7]White, C.E., Bernstein, D., Kornhauser, A.L.. Some map matching algorithms for personal navigation assistants [J]. Transportation Research Part C 8, 91-108. 2000
本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。
关键词：全球定位系统；地理信息系统；车辆导航；地图匹配
中图法分类号：TP368 文献标识码：A文章编号：1009-3044(2007)04-11021-03
1 引言
在车辆监控系统中，GPS卫星可以为全球绝大多数地方提供全天候、连续的实时定位导航测量。但是GPS定位，由于受卫星数据误差、数据传输误差、接收机钟差、接收机的测量误差等的影响，定位精度会产生较大的偏差。另外，在城市路段复杂的情况下，往往会出现高楼或高架桥阻挡，使接收机对部分卫星失去锁定，GPS数据产生漂移。这时就会有较大的偏差甚至失去信号，使得GPS数据的连续性受到一定的影响。航位推算是一种完全自主的导航系统，利用车速传感器来实现车辆定位，这种传感器在低速时并不可靠，使得用该传感器作为定位模块输入时，难于进行精确车辆定位。航位推算受方向探测仪及车速脉冲设备精度的限制，测量是一个累积的过程，因为不同时刻的测量误差都会累积起来，所以随着时间的推移，如果不补偿或不适当地补偿累积误差，车辆位置计算会变得越来越不精确，因此，单独的航位推算系统不能用来进行长时间的独立定位。由于GPS和航位推算都无法提供足够高的定位精度。因此，在实际系统中通常采用地图匹配（MapMatching-MM）[1]-[3]方法来提高GPS和DR定位的精度。在地图精度有保证的前提下，地图匹配算法可以大大改善GPS自主导航系统的定位精度。
2 地图匹配算法
本文地图匹配算法是在Bernstein D., White[4]-[7]等人的研究基础上，一方面充分考虑了GPS轨迹与道路网路段的相似性，另一方面也充分利用了GPS数据中有关车辆的实时信息（如航向等）。算法中利用GPS定位数据作为输入数据，其中包括位置、速度、时间等，有助于提高定位的准确性。
2.1 道路网定义
道路网G由一组曲线组成，每条曲线也可以称为弧段，假定每条弧段是线性的，弧段E∈G可以用一个有限点序列（P0，P1，…，Pn）表示，也就是说E由线段的端点组成，其中线段E的端点P0，Pn称为结点，P1，…，Pn-1称为形状点。结点是一条弧段的起点或终点，而P1，…，Pn-1用来表示弧段的几何信息。结点可能是一个终点，对应于道路网G中的道路的尽头，也可能是一条弧段到另一条弧段的过渡点，对应于道路网G中的交叉点。
2.2 地图匹配过程
本算法中把弧段数据、结点数据以及GPS定位数据作为输入数据。首先进行初始化处理，用结点匹配的方法来确定一条正确的弧段，该弧段是从与GPS点距离最近的结点相连接的所有弧段中找到，然后确定GPS点在弧段上的具体位置。下一步分析下一个GPS点是否还在该弧段上，然后确定它所在弧段的具体位置。在这里，第一步是至关重要的，因为候选弧段可能会有很多，而且后续匹配过程也是在第一步的基础上进行的。下面详细描述地图匹配的过程。
2.2.1 在候选弧段中找出正确的弧段
地图匹配算法最难的一项工作就是在候选弧段中找出正确的弧段，一般可通过计算权值的方法来选择正确的弧段。根据连续的两个GPS点所组成的线段与道路网弧段之间的相似度，点到道路弧段的接近度，GPS轨迹线与道路弧段夹角的大小，计算出候选弧段的权值。
（1）计算车辆航向与道路方向的权值
图1 车辆航向与道路方向的相似性
假设已经确定GPS点P1，P2，P3匹配到弧段1上面，下面的问题是确定P4所在的弧段，由于车辆当前位置是在弧段1上，点P4的候选弧段是2，3，4。运用权值公式来选择正确的弧段，图1中的β角表示车辆在点P4的航向（用车辆在该点的航向与正北之间的夹角表示），用车辆航向与候选弧段之间的夹角Δβ来计算权值。
WSH=AHCOS（Δβ′） （1）
其中：
AH（>0）是加权参数，它的值可以从式（7）获取。需要注意的是，Δβ′值越小的候选弧段成为正确弧段的可能性就越大。
（2）计算点和弧段接近度的权值
接近度测试可选用两种类型的权值，第一种是基于GPS点到弧段的垂直距离，见图2。
图2 GPS点到路段的垂直距离
假设P（X3,Y3）是GPS点，AB是弧段，因此点P到弧段AB的垂直距离是
用递减函数计算垂直距离的权值
其中：WSPD是点到弧段的接近度权值
D是GPS点到弧段的垂直距离
AP（>0）是加权参数，从式（3）可以看出，垂直距离越小，权值就越高，也就是说，如果点Pi越靠近弧段i，那么该弧段越有可能是正确的弧段。
另一种计算接近度的方法是测试两个连续GPS点，P(xi-1,yi-1)和P(xi,yi)组成的线是否与弧段i物理相交，这两条线的接近程度用它们之间的夹角θ表示，θ是锐角。夹角θ越小说明接近度越好。如果两条线不相交，则权值为0。
计算接近度的权值公式为：
其中：WSPI是夹角的权值，如果夹角存在的话
AP与上面定义的一样
（3）点相对于弧段位置的权值
图3 GPS点到与最近结点相邻的路段的相对位置
图3中P(xi,yi)是GPS点，变量α1，α2，α3，α4分别表示该点到弧段1，2，3，4的相对位置，由于该点映射到弧段2或弧段3的可能性比较大，那么到弧段2和弧段3的权值必须大于到其它弧段的权值，也就是说，角度越大，那么匹配到该弧段的可能性就越小。下面是计算权值的公式：
其中：WSRP是GPS点相对于弧段的权值
α（≤180°）是候选弧段与最近结点和该点之间连线的夹角
ARP（>0）是加权参数，控制WSRP的大小，它的值可以从式（7）中得到
（4）计算总权值
总的权值可以通过累计所有的权值得到，因此权值总和计算如下：
通过选择加权参数的不同值，就能得到总权值，由经验表明，航向权值（WSH）应该比相对位置WSRP更重要，另外，相对位置WSRP也应该比接近度权值（WSPD+WSPI）更为重要，下面的公式计算加权参数：
其中：a和b是加权因子，并且a>b>1，在确定a和b后，总权值是AP的倍数，在理论上，AP可以取任一正值，AP的取值不会影响最终的结果。
然后计算所有候选弧段的的TWS值，把权值最大的弧段作为GPS点的匹配弧段。
2.2.2 确定车辆在选定弧段的位置
在确定车辆所在的正确弧段后，下一步就是确定车辆在该弧段的具体位置，见图4。
图4 估算GPS点在路段的位置
GPS定位点在点PS以ES和NS表示，在路段上的投影如下式（8）：
其中点CP(PES,PNS)为GPS点PS(ES,NS)在路段上的投影点。
2.2.3 检测车辆是否仍然在当前弧段上
前一个GPS点在正确弧段上确定车辆位置后，需要检测车辆是否仍然在该弧段上，下面引入两个测试条件：
（1）两个连续GPS点航向之间的角度之差小于45°
（2）当前GPS点与当前选中弧段的夹角小于90°
如果上面任意一个条件不成立，则假定车辆开始接近交叉点并且初始化地图匹配过程，否则，车辆仍然在前面的弧段上并计算新的位置。
3 算法测试
为了验证本章地图匹配算法的有效性，在图5中给出了利用该算法对实际车辆行驶数据的处理结果。这里使用的原始数据是在镇江市中心地区获取的车辆行驶轨迹，行车路线是梦溪广场－环城路－中山东路－中山西路。其中黑色点形成的轨迹为原始GPS定位轨迹，红色点形成的轨迹是经过地图匹配算法校正后的轨迹。从图5可以看出，在市区道路网比较复杂的情况下，运用本文的算法，可以保证GPS点在电子地图的准确定位。
图5 镇江市区道路图
参考文献：
[1]Jong-Sun Pyo. Development of a map matching method using the multiple hypothesis technique [C]. IEEE Intelligent Transportation Systems Conference Proceedings, 2001.
[2]Rajashri R. Joshi. A New Approach to Map Matching for In-Vehicle Navigation Systems: The Rotational Variation Metric [C]. IEEE Intelligent Transportation Systems Conference Proceedings, 2001.
[3]Valentin Enescu, Hichem Sahli. Multiple model estimation scheme for map-matching [C]. The IEEE 5th International Conference on Intelligent Transportation Systems 3-6 September 2002.
[4]Sinn Kim, Jong-Hwan Kim. Adaptive Fuzzy-Network-Based C-Measure Map-Matching Algorithm for Car Navigation System [J]. IEEE Transactions On Industrial Electronics, Vol. 48, No. 2, April 2001.
[5]Sinn Kim, Jong-Hwan Kim. Q-factor Map Matching Method Using Adaptive Fuzzy Network [C].IEEE International Fuzzy Systems Conference Proceedings. August 22-25, 1999.
[6]Sotiris Brakatsoulas. On Map-Matching Vehicle Tracking Data [C]. Proceeding of the 31st VLDB Conference. 2005
[7]White, C.E., Bernstein, D., Kornhauser, A.L.. Some map matching algorithms for personal navigation assistants [J]. Transportation Research Part C 8, 91-108. 2000
本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。