曲线拟合与网络拓扑论文范文

1基于网络拓扑的地图匹配算法

使用路段连通性或路段的几何形状的地图匹配算法是基于网络拓扑的地图匹配算法。它通过对前1次匹配结果和车辆前进方向的分析，利用道路层的空间网络拓扑关系，确定当前GPS定位点的候选路段的范围，并计算出当前GPS定位点的匹配点。该算法的依据是：车速有限，在一定时间范围内，车辆只能行驶在与上一匹配路段相连的道路上，不可能在其他路段。

2综合地图匹配算法的实现

基于曲线拟合的地图匹配算法充分利用了GPS历史数据，使得该算法在匹配路段的选择方面具有较强的稳定性，但是它只考虑了拟合直线与候选路段的斜率，以及定位点与候选路段的距离关系，对于相互靠近的平行路段则无法准确辨别，所以对于这类路段，仅仅依靠曲线拟合算法会造成匹配错误。网络拓扑反映的是道路之间的连通关系，在一定时间范围内，车辆只能行驶在与上一匹配路段相连的道路上，而平行路段中只可能有1条（即匹配路段）是与上一匹配路段相连的，因此，利用网络拓扑关系可以排除平行路段的干扰。本文的地图匹配算法基于曲线拟合并结合路网拓扑关系，不但能弥补基于曲线拟合的地图匹配算法在距离较近的平行路段匹配率不佳的缺点，还能有效缩小候选路段的搜索范围，减小算法复杂度。

2．1数据预处理城市道路路况复杂，隧道、立交桥和密集的高大建筑物的存在导致GPS信号盲区的产生，在传输过程中，因通信或建筑物、树木、桥梁阻隔等原因导致数据缺失，经纬度或速度突变，导致错误数据和数据丢失［11］。为了提高地图匹配的精度，有必要对GPS数据进行预处理，剔除经纬度或速度突变的数据并插值补全缺失的数据［12］。

2．2候选路段的确定误差区域是指包含车辆真实位置的区域，确定候选路段之前首先要确定误差区域。圆概率误差（R95＝2DRMS／1．2。其中：2DRMS为GPS接收机的双倍距离均方根差）是在以GPS接收机天线真实位置为圆心的圆内、偏离圆心概率为95％的二维点位精度分布度量。也即是说，GPS接收机接收到的测量值以95％的概率落在以GPS接收机天线真实位置为圆心、R95为半径的圆内。因此以GPS定位点为圆心，圆概率误差为半径的圆形区域可以确定1个误差圆区域，并从电子地图数据库中提取出与该误差圆相交的路段集L＝｛l1，l2，…，ln｝。考虑路网拓扑关系，从路段集L中取出与上1个匹配道路有邻接关系的路段作为候选路段。如图2，点O是待匹配的GPS定位点，圆O是误差圆，则与该误差圆相交的路段集为L＝｛1，2，…，7｝，当前时刻车辆行驶在道路1上，则下一时刻车辆只能出现在与道路1相连的道路2，道路3，道路4上，故候选路段为道路2，道路3，道路4。电子地图中的路段是用直线段或折线来近似的，由于车辆在道路上行驶的这个前提，在一定的行驶距离内，可以用直线拟合车辆的行驶轨迹。根据道路本身的最短长度，本文选取4个观测点，作1次曲线拟合，即直线拟合。由上述的曲线拟合的原理求得轨迹拟合的直线斜率。

3综合算法的实验验证

图4为终端号为22的北京市物流电动出租车的部分行驶轨迹，行驶方向为万红路→酒仙桥东路→酒仙桥北路。由于GPS定位误差的存在，使得部分定位点之间间隔过大且定位点与道路偏离。采用本文提出的综合算法解决这些问题，主要完成3个任务。1）预处理GPS数据，使其符合车辆行驶规律。2）匹配车辆定位点到正确的路段上。3）确定车辆在路段上的位置。GPS接收机每5s接收1次数据，因此以5s为间隔插值补全GPS数据，由物流电动车内的GPS接收机的双倍距离均方根差得到误差圆半径为66．7m，然后按综合算法流程进行候选路段、匹配路段和匹配点的确定。图5显示利用本文算法的匹配结果。图6是基于曲线拟合算法得到的匹配结果，由于图中上下2条平行路段距离比较近且部分定位点偏离路段的距离相对较大，所以这2条路段都被包含在误差圆内，基于曲线拟合的地图匹配算法又有其自身的局限性，故出现了图6所示的错误匹配。将综合算法应用到多个样本进行实验验证，匹配率都在95％以上，单点匹配时间均在5ms以内。由于综合算法显著地缩小了候选路段的范围，而影响地图匹配算法实时性的主要因素就是候选路段的确定，故其减少了匹配时间。表1所示为综合算法与基于曲线拟合的算法之间匹配率和单点匹配时间的对比。实验结果表明：本文提出的综合算法能比较精确的把定位点匹配到道路上，能解决基于曲线拟合匹配算法对比较靠近的平行路段进行匹配时容易出错的问题，因此，综合算法能应用到地图匹配的实践中。

4结束语

笔者提出1种基于曲线拟合和网络拓扑的综合地图匹配算法，详细描述了匹配的4个步骤：数据预处理、候选路段的确定、匹配路段的确定和匹配点的确定。最后将该算法应用到实际的匹配工作中，运行结果表明：该算法精度高、效率好，能解决基于曲线拟合算法在靠近的平行路段匹配率不佳的问题，具有很好的实用价值。笔者所指的算法没有考虑立交桥区域内的地图匹配，可在此方面做进一步的研究。

作者：毕军朱颖程勇单位：北京交通大学城市交通复杂系统理论与技术教育部重点实验室北京交通大学北京城市交通协同创新中心山东济宁市鸿翔公路勘察设计研究院