交通数据的地图匹配算法研究
摘要:城市智能交通引导系统为用户提供最准确的道路交通信息。

在分析地图匹配问题产生原因的基础上,阐述了地图匹配算法解决车辆在地图上位置定位的基本思想和判断依据,设计了交通引导系统中便于实现的地图匹配算法,通过引入行驶方向和驾车轨迹,地图匹配算法改进后提高了车辆定位的准确性。

系统实验证明,改进后的地图匹配算法能够很好的完成交通引导系统中车辆位置在地图显示中的定位匹配任务。

关键词:地图匹配行驶方向驾车轨迹定位匹配
智能交通引导系统是一个融合了车辆GPS定位技术和计算机技术,结合MapInfo电子地图,为用户提供优化、准确的道路交通信息服务平台。

系统通过导航生成GPS数据,获取车辆行驶信息,通过对交通数据的处理实现在客户端地图中显示车辆位置、方向和目的地等,并在地图上显示出满足要求的行驶路线。

路网中行驶的车辆位置坐标定位在电子地图上不可避免的存在误差,因为:(1)车辆GPS数据和电子地图数据所采用的坐标系可能不同,车辆的坐标位置显示在电子地图上会发生偏移;(2)电子地图坐标数据存在误差。

交通引导系统采用基于的电子地图,生成电子地图的基础数据来源于高精度卫星地形图。

地形卫星图片要经过扫描和栅格化等多重处理,每个处理环节不可避免的产生误差;(3)GPS定位误差。

车辆通过GPS定位时,车辆位置坐标数据会受到地形因素等的影响。

通常,车辆GPS定位精度误差范围一般在15～30 m之间。

因此,车辆行车数据在地图上显示时会出现偏差。

因此,通过地图匹配算法将车辆的行车数据与电子地图中的道路数据联系起来,从而判断车辆在地图上显示时相对准确的位置坐标。

1 地图匹配算法分析
地图匹配算法通过坐标转换将车辆位置坐标精确定位在路段或交叉口上。

1.1 地图匹配算法的原理
地图匹配算法借助电子地图提供的高精度道路交通数据来提高车辆的定位精度,利用已经确定的地理坐标如交叉口,路段分段的结点坐标,通过一定的算法,确定车辆的地图位置。

同时它需要满足:(1)所需匹配地图位置坐标的车辆总是行驶在道路上;(2)采用的电子地图道路数据的精度不低于车辆GPS定位的精度;(3)具备适用于地图匹配的具有拓扑结构的道路交通网络模型。

地图匹配算法的基本思想是:通过采集车辆在路段中行驶的坐标位置,判断车辆通行轨迹与电子地图路段的相关性。

以待匹配车辆在地图上的位置坐标或该车辆行驶历史路线为样本,获取到车辆周围的路段和路段间的交叉点,再将分段道路的数据作为模板,将样本与模板
按照一定条件进行匹配,从而确定车辆当前行驶路段,并将车辆投影到该路段的相应位置上。

根据车辆历史位置定位时为了保证有效性,地图匹配应该满足两个要求:(1)车辆初始位置确定;(2)每隔一段时间对地图中车辆位置进行重新匹配修正,以降低位置偏差[1-3]。

1.2 地图匹配算法的实现过程
地图匹配算法的处理流程包括:
(1)设定误差匹配范围:以车辆在地图上的待匹配点为中心选取一定范围的区域,在区域范围内的路段都有可能是与车辆轨迹相匹配的路段。

(2)确定待匹配路段:在区域范围内选取与车辆行驶轨迹最相似的车辆行驶路段。

如选取距离匹配点最近的路段作为最佳匹配路段。

(3)计算匹配位置:确定最佳匹配路段后,根据算法选取匹配点在该路段的投影作为匹配位置点。

2 地图匹配问题的解决方案
如图1所示,地图匹配算法就是为了寻找车辆待匹配点最近的路段,从而计算出车辆在地图上的最佳位置坐标P＇。

根据地图匹配算法的匹配准则和实现过程,以图1简化的道路模型为例,详细介绍地图匹
配问题的解决方案。

2.1 误差匹配范围的确定
系统获取车辆GPS位置后,设定一定范围,从地图数据中选取范围内的路段作为候选路段,减少地图匹配算法在后续过程中为了确定最佳路段时对路段的判断次数。

以图1为例,为车辆在地图上显示的位置,R为搜索半径(可变化),P＇为在带匹配路段上的投影。

如图所示,L1、L2、L3、L4为点周围的路段,其中L1、L2、L3在误差范围内,所以只去该三条路段进行车辆位置的匹配。

2.2 确定待匹配路段
确定待匹配路段的具体方法是:以搜索半径R为限制,将获取的待匹配路段分别求出与待匹配点的最短距离,选取距离最近的路段作为车辆在地图上的行驶道路。

按图1中信息进行抽取,得到如图2所示的坐标系。

其中,车辆位置坐标,为提取出的其中一条待匹配路段,为在该路段上的投影点。

、分别为该路段的两端点坐标,即为我们所需求取的与路段的距离。

利用矢量算法,求得距离的大小。

其中:向量, 。

点、的坐标可由地图数据库直接提供。

所求出的即为指定路段的最短距离。

按照图2所描述的情况求取距离最近的路段,必须具备定位点所到路段的投影必须在该路段上,垂线段即为最短距离。

但当如图3所示,点到路段投影在路段之外,我们这时候需要考虑的方向。

由空间几何运算,可知,当时,投影坐标满足图3情况;当时,投影坐标满足(a);当,投影坐标满足(b)。

如式3所示,当投影点在路段外时,我们认定点到路段的最短距离d为点到路段端点的距离。

2.3 计算道路匹配位置
定位误差范围内的所有路段到点的最短距离d作为车辆在地图上的行驶路段。

车辆行驶坐标点在该路段上的投影点即为车辆在地图上所显示的匹配位置。

当投影点在路段外时,选定路段的端点坐标为匹配坐标。

3 改进后的地图匹配算法
车辆的地图匹配工作是一个连续的不间断的过程,而不是某个时间点单一的车辆定位。

为了提升地图匹配的精确度,关键在于地图匹
配算法辨认出定位轨迹与车辆实际行驶路线间的相似度高的行驶路段,但是这种相似程度容易受到某些因素的影响。

如定位误差范围内的车辆匹配导致车辆的定位轨迹可能落在真实行驶路段相之外。

另外,当道路分布非常密集时,相互的间距相对较小,道路基本机构相同,采用匹配方法会给车辆位置的地图匹配带来了很大的不确定性。

车辆地图匹配的不确定性集中在复杂路段或道路的交叉口,误差范围内各路段的最短距离相差不大,容易产生错误的匹配结果。

为提高地图匹配算法的准确性,引入两个因素对算法进行改进,一是车辆的行驶方向(式5),一是车辆的行车轨迹。

当车辆行驶到路段交叉口时,引入行车方向的度量,如式(5):
其中:为车辆在定位点的行驶方向与第个待匹配路段所构成的夹角;为第个路段上的投影距离;、分别为最短距离d与间的比重[4]。

在交叉口处,车辆定位获取的参数越小,说明路段越接近车辆真实行驶路段。

地图匹配算法工作流程如图4所示。

4 结语
讨论了城市智能交通引导系统的地图匹配问题解决方案。

首先对地图匹配问题产生的原因进行了分析,阐述了地图匹配算法解决车辆
在地图上位置定位的基本思想和判断依据;然后在满足地图匹配的前提条件下,设计了在交通引导系统中便于实现的地图匹配算法;最后为了进一步提高车辆定位的准确性,引入了行驶方向和驾车轨迹等因素,对地图匹配算法进行进一步的改进。

实验证明,改进后的地图匹配算法能够很好的完成交通引导系统中车辆位置在地图显示中定位匹配的任务。

参考文献
[1] 常菲．综合地图匹配定位技术研究[J]．计算机工程与应用,2004,19:200-202．
[2] 刘志德．地图误差对地图匹配质量的影响[J]．测绘科学技术学报,2008,25(5):340-343．
[3] 荆涛．车辆导航系统中地图匹配的研究[J]．铁路计算机应用,2008,17(7):1-5．。