地图匹配算法综述

文献综述--地图匹配算法----周成研究背景地图匹配算法的必要性1.各大城市道路日益更新，中小城市也不断修建新的道路，导致路网复杂。2.为了能够提高出行效率，导航系统成为车载必备工具。3.对于车辆导航系统，定位的准确性是至关重要的因素，定位准确才能为用户提供准确的车辆位置，以便提供准确的路线。研究背景全球定位系统导航系统主要由GPS（GlobalPositionSystem）和地理信息系统GIS（GeographicInformationSystem）两个部分组成。GPS系统负责与卫星以及地面基站的往返通讯，向基站或卫星发送请求，并从其接收GPS数据。GIS系统主要负责电子地图的存储和管理，显示车辆位置、方向等信息，并结合道路进行空间分析，选择出最佳行车路线。定位系统的准确性也是车辆导航系统的重点和难点。GPS系统总会存在难以避免的误差，误差大致可分为三部分：1.卫星及其传播途径本身所产生的误差，如卫星钟误差、星历误差以及电离层误差等；2.无法测量或不能用校正模型计算的传播延迟误差；3.是用户接收机固有误差，如内部噪声、通道延迟等。解决办法：从软件方面提高车辆行驶路线的精度。这就需要利用地图匹配将车辆的GPS点数据匹配到车载系统的电子地图的道路网络中，从而准确地提供车辆信息。研究背景地图匹配概念地图匹配是应用软件的方法，对导航定位误差进行修正的技术。该技术以模式识别理论为依据，基于车辆始终行驶在道路上的假设，其基本思想是结合车辆定位的轨迹与数字地图中的道路网络，将GPS定位方法所测得的车辆位置信息与导航系统的电子地图数据比较和匹配，找到车辆所在的路段，计算出车辆在路段上的确切位置，将车辆点投影到路段上，从而校正了定位误差。定位技术结合地图匹配算法，极大地提高了车辆定位精度，地图匹配技术是决定导航系统最终性能的关键技术[2][3]。可见，地图匹配技术的应用必须具备两个前提：（1）用于匹配的数字化地图中的道路位置信息具有较高的精确性；（2）被定位的车辆需在地图中的道路网上行驶。因此，地图匹配算法可以分为两个相对独立的步骤：一是找到车辆当前正在行驶的道路；二是将车辆当前的定位点投影到道路上[4]。当前的地图匹配绝大多数都是面对动态实时GPS数据的处理，匹配算法按照空间区域关系的算法总的分为两类：1.确定性地图匹配算法2.不确定性算法确定性地图匹配算法投影算法为查找距离车辆位置最近的路段，然后将表示车辆位置的定位数据点投影到查找到的路段所对应的点上，将投影点作为车辆匹配后的位置。2003年，帝国理工的M.A.Quddus等人提出了要素加权法来优化传统的直接投影算法[5]，将轨迹方向和点到路段的距离分别进行加权计算：路段方向与轨迹方向一致性越高，权重就越大；距离越小，权重也越大；空间相关性越大，权重越大。将方向、距离和相关性的权重相结合计算出该路段的总权重，然后根据权重选择路段。2008年，国内的张雷元等人改进了这种加权算法[6]，扩大了道路选择范围，并将原有算法的人工赋予权重系数改进为多属性决策计算权重，从而增进了地图匹配的可靠性。2012年，王敏等人在该算法中加入了速度权重[7]，并在轨迹的转弯点对适量地图交叉路口节点的偏移量做平行四边形，将转弯点附近前后车辆位置点以该平移量的方向平移到路段上，构成平行四边形，这种添加速度权重和动态平行四边形算法的结合完善了计算权重的投影的算法。投影匹配算法相对简单，易于实现，可以在一定程度上提高车辆定位的精度，但是效率较低，稳定性相对较差，通常只适用于精度要求不是很高的条件下使用。确定性地图匹配算法总结不确定性地图匹配算法4.1概率统计算法概率统计地图匹配算法也是一种基础的匹配方法。2001年彭飞等人提出并实现了利用概率统计算法的地图匹配技术。概率计算法的基本思想是依据GPS接收到的数据信息设置一个置信区域，即利用概率准则来设定搜索道路的距离阈值，并从中选出用以匹配的道路位置信息，按照统计理论，定位误差椭圆可推导如下[9]：2003年，许志海等人对概率统计算法做了改进[10]，在利用概率统计确定阈值的同时还参考了道路宽度，并在道路匹配操作时，对车辆所处于的不同状态赋予不同的权值。概率统计算法的优点在于不要求车辆总是在道路上。如果接收的数据不在已知的道路网络中，概率统计算法就会反复地比较接收的坐标和偏离道路路段的坐标，并识别车辆匹配的路段[11]。4.2模糊逻辑算法地图匹配设计模糊度的定性决策过程，利用模糊逻辑方法可以解决这一问题。模糊逻辑推论过程包括模糊化、推理机和去模糊化三个部分，利用隶属函数描述与候选道路来定义误差模型。国内，2001年苏洁等人首先提出了模糊逻辑算法[14]，基本思想是在将地图每条道路分段线性化成直线段的前提下，对每条描述路段进行模式v识别，并将前面多条路段的识别结果作为后一路段的相似性大量函数识别权值。1.2006年M.A.Quddus等人[15]提出了有关模糊逻辑地图匹配算法的改进，在算法中输入车辆速度、道路连通性、定位点相对于道路位置等信息，利用这些输入的信息和模糊逻辑规则来提高算法性能。2.2008年宋洁等人提出了相对完善的模糊逻辑算法[18]，分别定义方向、距离和速度的隶属函数，分别对函数值进行单因素评价，构造模糊矩阵，计算出模糊向量，确定权向量，权向量的每个维度的值分别表示各个因素的重要程度，最后做模糊变换得到向量作为每个评判因子的权重值。模糊逻辑算法的优点在于其匹配效率高、计算简单、实时性好，并且对不同的路段状况都适用。缺点在于权重系数分配缺乏理论依据，基本上以经验为主要选择标准[12]。4.3相关性分析算法2004年常菲等人提出了地图匹配的相关性分析算法。相关性算法的基本原理是利用拐角和交叉口或曲线路段的形状特性对定位系统测出的数据进行校正[16]。假设车辆在t=1,2k,k=N的时刻内，定位系统测出的车辆行驶轨迹分别是S1，S2，Sk，对应电子地图有i条可能性是路线，并设地图上与导航传感器测出的数据对应轨迹分别为Li1，Li2，Lik，是i组序列。相关性算法是计算出轨迹与i组地图数据的相关性系数：4.4基于D-S证据推理算法D-S证据理论有比较强的理论基础，既能处理随机性所导致的不确定性，又能处理模糊性所导致的不确定性，依靠证据的积累，不断缩小假设集，将“不知道”和“不确定”区分开来。在样本空间中定义命题的信任函数（对命题A为真的支持度）与似然函数（不反对命题A点程度）。然后考虑不同证据的mass函数，根据D-S合成规则，可以得到一个复合函数，此函数反映了证据对命题A的联合支持程度。2008年谷正气等人对该算法进行了改进[17]，分别在两方面进行了改进：（1）证据权值改进：通过高斯概率密度函数求出证据之间距离以及其支持矩阵，反应对同一物体测量结果的不一致，求得支持矩阵的每个证据的可信度，求得每个证据的权值；（2）决策规则改进：基于Pignistic概率的决策规则，而非传统的单层决策，以扩大信度差异。总结：该算法的优点在于通过推理可以得到唯一正确的判断结果。缺点在于算法证据推理过程只考虑了GPS采样点的两种信息：GPS点的位置，和方向。但地图匹配过程中，还需要考虑三种及以上信息的融合，并且该算法实现复杂、计算的开销较大[13]。5.存在问题与发展方向上述方法均存在一定的优势和尚待解决的问题。1.直接投影法虽然计算相对简单，但是效率不高，而且稳定性不好。缺点：它的一些改进算法只是提高了其稳定性，并没有对效率进行改进。2.不确定性算法大多存在着算法复杂，实现困难的问题，它涉及一系列的公式推导，不仅实践起来繁琐，不容易让人理解，而且这两种算法计算开销比较大，匹配效率低下，这样就影响了GPS数据显示的实时性，难以满足大众对GPS系统的要求。总结：虽然模糊逻辑算法相对简单，但算法本身不够严谨，缺乏理论依据。总的说来，地图匹配算法中，算法相对简单的准确性较差；准确性高的算法计算复杂，计算效率不高。未来研究方向：卫星测量精度的提高，获得的GPS数据量也是海量的。所以目前海量GPS数据的地图匹配成为亟待解决的问题，海量数据地图匹配的研究也相对较少。海量GPS数据处理的核心在于保留相对较高匹配精度的同时，很大程度上提高计算效率，从而满足海量数据的实时性匹配。在今后的研究中，对地图匹配的准确性以及针对海量数据的快速处理都是需要进一步研究的方面。参考文献[1]李沛.车辆导航系统中地图匹配的研究[D].北京交通大学.2008.[2]夏州.GPS车辆导航中的数据处理与地图匹配研究[D].北京交通大学.2009.[3]胡建超,王忠,张维.改进的地图匹配算法研究[J].通信技术,2009(42):166-170.[4]方伟骏.GPS与数字地图匹配的组合导航研究[D].南京航天航空大学.2009.[5]MohammedA.Quddus,WashingtonYottoOchieng,LinZhao,RobertB.Noland.Ageneralmapmatchingalgorithmfortransporttelematicsapplications[J].GPSSolutions,2003(7):157-167.[6]张雷元,徐棱,刘晓明.一种改进的基于要素加权的浮动车地图匹配算法[J].交通与计算机,2008(2):8-10.[7]王敏,魏衡华,鲍远.GPS导航系统中的地图匹配算法[J].计算机工程,2012(14):259-261.[8]彭飞,柳重堪,张其善.基丁模糊逻辑的GPS/DR组合导航系统地图匹配算法[J].遥测遥控,2001:32-36.[9]彭飞,等.基于代价函数的组合导航系统地图匹配算法[J].北京航空航天大学学报,2002(6):261-264.[10]许志海,张昭云,陈应东.车辆导航系统中定位数据处理和地图匹配技术[J].测绘学院报,2003,20(4):247-250.[11]张振辉,崔铁军,姚慧敏.车辆导航系统中地图匹配新算法[J].海洋测绘,2006(26):55-58.[12]周培德,付梦印.地图匹配的新算法[J].北京理工大学学报,2004,24(3):38-47.[13]ChenZ,SunY.DevelopmentofAnAlgorithmforCarNavigationsystemBasedonDempster-ShaferEvidenceReasoning[C].Proc.ofIEEEIntelligentTransportationSystems,2002:534-537.[14]苏洁,周东方,岳春生.GPS车辆导航中的实时地图匹配算法[J].测绘学报,2001,20(3):252-256.[15]M.A.Quddus.HighIntegrityMapMatchingAlgorithmsforAdvancedTransportTelematicsApplications[D].2006.[16]常菲,等.综合地图匹配定位技术研究[J].计算机工程与应用,2004,19:200-202.[17]谷正气,胡林,黄晶,等.基于改进D-S证据理论的车辆导航地图匹配[J].汽车工程，2008,30(2):141-145.[18]宋洁,李国燕,李娜娜.基于模糊逻辑的GPS/DR地图匹配算法[J].计算机工程与科学，2008,30(10).