基于Android移动终端的车辆导航地图匹配算法研究

曾锡山 ，范冰冰

(华南师范大学计算机学院，广州510631)

车辆导航地图匹配指运用一定的匹配算法将车辆GPS 定位数据与电子地图中的道路网络进行比对，首先找到车辆当前的行驶路段，然后确定车辆在路段上的位置(匹配位置)［1］.受各种干扰因素影响，GPS 定位往往存在较大误差.地图匹配从带误差的定位数据中识别出当前行驶道路，用匹配位置来代替原始定位位置用于导航，能改善屏幕显示效果，提高定位精度，是车辆导航的关键技术之一.

近年来移动终端技术发展迅速，智能手机、平板电脑等移动终端都配备了GPS 定位模块，可以运行复杂的车辆导航应用. 对传统车辆导航系统产生了巨大的冲击.相对于专业的车辆导航系统，基于移动终端的车辆导航系统要适应定位精度较低、处理能力参差不齐的多种终端，对地图匹配有着更高要求.因此，研究匹配效果较好、计算量较小的地图匹配算法对基于移动终端车辆导航具有重要意义.

常见的地图匹配算法分为几何匹配、拓扑匹配、概率统计法和高级匹配算法［2］，其中拓扑匹配算法利用了道路网络中路段间的连接性、连通性等拓扑信息，消耗的计算资源较少且易于实现，同时又具有较好的匹配效果，主要用于车辆导航等实时应用［3］.本文基于Android 移动终端设计了一种基于路网拓扑结构的地图匹配算法，该算法计算简单、具有较高的路段识别率，匹配后的位置精度有较大提高.

1 算法思想

基本思想是将地图匹配分成4个相对独立过程:(1)定位数据预处理;(2)确定车辆所在路段;(3)确定车辆匹配位置;(4)出错检测.

1.1 定位数据预处理

预处理的作用是过滤掉异常定位数据，然后对缺失的数据进行补偿，以保证地图匹配的正常进行.当满足以下条件之一时，算法认为定位异常:

1)当可见卫星不足4 颗(GPS 定位至少需要4颗卫星才能获得比较精确的位置);

2)从GPS 得到的车辆速度达到一个正常行驶不可能达到的阈值vTH，算法取vTH=200 km/h.

检测并过滤掉异常定位数据后，使用航位推算进行补偿［4］:

用推算出来的坐标(xn，yn)进行匹配，(x0，y0)为最近的有效定位点坐标，vn－1、θn－1为上一点处的车速和行驶方向，Δt 为定位时间间隔. 补偿过程一直持续到GPS 定位恢复正常.

1.2 确定车辆所在路段

首先根据定位误差模型建立候选路段集，然后使用匹配评估模型计算定位信息与各候选路段的匹配度，挑选出匹配度最高的路段作为车辆所在路段.

1.2.1 建立候选路段集 得到定位点后，车辆真实位置可能位于定位误差区内的任何一条路段(候选路段)上，建立候选路段集就是将所有候选路段信息从地图数据库中提取出来. 误差椭圆［5］是最常用的定位误差模型，即真实位置以一定置信度位于以定位坐标为中心的椭圆区域内，该区域可以由定位坐标的统计方差计算得到.对于专业的GPS 导航设备，可以从输出的电文中获取计算椭圆方程所需的各种统计方差. 而对于一般的Android 移动终端来说，通过给定的SDK 无法得到这些参数. 算法采用圆形误差区域［6］，半径R 取移动终端最大定位精度的3 倍(R=60 m).当得到定位坐标后，分情况建立候选路段集:

式中：0和c分别代表基态和故障状态；C表示预想故障集合；x和u分别表示由状态变量和控制变量构成的向量；指故障c发生后控制变量调节范围的最大值。

1)不存在历史匹配路段，则将误差圆内所有路段作为候选路段;

2)存在历史匹配路段，则利用道路网络的拓扑关系，只选择误差区内与历史匹配路段相连通的路段为候选路段.

利用历史匹配信息和路网拓扑信息过滤掉不可能的路段，一方面减小了候选路段集从而减少算法计算量，另一方面也可以提高匹配准确率.

1.2.2 确定匹配路段 采用一种考虑距离和方向两种要素的加权评估模型来评估定位信息与候选路段的相似度，首先计算出定位点到候选路段的距离相似度，再计算得到车辆行驶方向与路段走向的相似度，然后取2 种相似度的加权和作为总体相似度.距离相似度定义为:

其中d 为定位点到候选路段的距离，dTH是一个预先设定的距离阈值，取dTH=60 m 为误差区域的半径.方向相似度定义为:

其中Δθ 为车辆航向与路段走向的角度之差，大于90 度时方向相似度直接为0，小于90 度则使用余弦函数计算相似度.

总体匹配评估模型定义为:

其中wd、wθ为距离、方向相似度的权重因子，权重的大小代表相应要素的重要程度. 算法取wd+wθ=100，则SimTotal(d，Δθ)的取值范围为［0，100］. 用该模型对每条候选路段进行评估时，首先应计算方向相似度:若为0 则总相似度直接为0;否则计算加权和.这样可以滤除方向相差太大的候选路段，减少不必要的计算.

图1 路段匹配状态转换Figure 1 State transition of road matching

如图1 所示，路段的匹配分成初始匹配和跟踪匹配状态，分情况处理:

1)初始匹配.将误差区内的所有路段加入候选路段集，统计连续3个定位点的匹配结果，当有至少两点位于同一路段上时，才认为该路段为匹配路段，此后算法进入跟踪匹配状态. 否则继续进行初始匹配，直至找到初始匹配路段;

2)跟踪匹配. 发生在车辆变更路段的时候，地点为交叉路口.利用历史匹配信息，在建立候选路集时只将与历史匹配路段相连通的路段纳入其中，然后用匹配评估模型挑选出当前定位点的匹配路段.当算法检测出匹配错误或者不存在匹配路段时，转入初始匹配状态.

1.3 确定车辆匹配位置

垂直投影法［7］取定位点到匹配路段上的垂直投影点作为匹配位置，该方法原理简单，易于实现，但是只能消除与路段垂直方向的误差，对与路段平行方向上的误差(以下简称为径向误差)没有减小效果.本文对垂直投影法进行改进，得到一种能够消除部分径向误差的优化方法.

为了更好地描述本文的优化方法，先考虑如图2 所示情况.假设GPS 定位误差保持不变，则定位点P1～P3刚好位于与路段N1N2平行的直线l1上，过P4作N2N3的平行线l2，再假设车辆在道路的拐弯点N2处刚好产生一个GPS 定位点. 用向量ei(i=1，2，3，4，N)来表示各点的定位误差(图2)，显然有e1=e2=e3=e4=eN. 由分析可知，点刚好是l1和l2的交点，可以由两直线的方程求得，又由于N2的坐标已知，因此可以求出定位误差eN. 用eN对每个定位点进行修正，就可以得到车辆真实位置，消除定位误差.

图2 车辆过弯道时的理想定位Figure 2 Hypothetical vehicle positioning around turning

在真实情况下，尽管GPS 定位误差是随机变化的，但也有规律可循.文献［8］通过大量实验发现车辆定位轨迹与所在道路形状相似，对于同一终端，短时间内定位点大致会偏在道路的同一侧，而且偏移量近似于常量.本文利用这一规律来优化垂直投影法，减小部分径向误差.

车辆过弯道时的真实定位情况往往如图3 所示.优化方法在车辆过路段拐弯点N2后并在N2N3上产生3个定位点P1、P2、P3，按以下步骤求解eN:

step1.判断P1、P2、P3是否位于N2N3的同一侧:是则继续;否则求解失败.

step2.从刚经过的路段N1N2上取最近的3个历史定位点P4、P5、P6，判断它们是否位于N1N2的同一侧:是则继续;否则求解失败.

step3.使用最小二乘法分别由P1、P2、P3和P4、P5、P6拟合出直线l1、l2(图中虚线)，计算出角度差是否满足条件:

其中θ 是各直线与正北方向的夹角，αTH是一个角度阈值，具体取值需要通过实验测定.若满足条件(5)则认为这6 点的轨迹与路径一致，误差基本一致，满足求解eN的条件;否则求解失败.

step4.分别由P1、P2、P3和P4、P5、P6拟合出与路段平行的直线l'1、l'2，求出交点，然后求得eN.

若eN求解成功，则从N2N3上的第4个定位点起开始优化.以P7为例，先通过垂直投影法求得垂直匹配点P7'，然后分情况讨论:若该P7到l'1的距离小于等于(P1、P2、P3到l'2的平均距离)，则使用eN在N2N3上的水平分量修正P7';否则不修正.

在车辆过第一个拐弯点之前，使用垂直投影法求匹配位置.以后车辆每过一个拐弯点，就使用上述方法更新一次eN，然后从当前路段上的第4个定位点开始优化. 显然，该方法的优化效果视GPS 定位误差的情况而定:若在某一时段内比较稳定则效果较好;否则变为垂直投影法.

图3 车辆过道路拐弯点时的定位Figure 3 Real vehicle positioning around turning

1.4 出错检测

由于定位误差的随机性、现实中道路网络的复杂性，再加上算法本身也难免存在一定缺陷，错误匹配是不可避免的.利用历史匹配信息的做法存在一定的隐患，一旦路段匹配出错，后续的定位点也会跟着出错.因此必须要有匹配出错检测机制及时地发现并处理错误.正确匹配时，车辆在路段上的匹配位置和定位点之间的距离应该相差不大. 由本文采用的圆形误差区域可知，匹配点Pm(xm，ym)应位于以定位点P(x，y)为圆心、dTH为半径的圆内部，因此将通过距离检测的条件设置为:

当定位点与匹配点的距离大于dTH，则认为是错误匹配，需要重新执行确定匹配道路的过程.需要明确的是，出错检测并不能马上检测出匹配错误，而是具有一定的滞后性，滞后的时间跟道路的形状、车辆速度等都有一定的关系.

2 算法实现

2.1 详细流程

匹配的详细流程如图4 所示.算法的输入包括GPS 定位数据(可见的卫星数量、经纬度坐标、行驶速度)和车辆行驶方向. 算法的输出视匹配结果而定:当成功找到匹配路段且匹配位置正确时，输出的结果为匹配路段和匹配位置坐标;若未找到匹配路段(匹配失败的原因可能是车辆离开道路网络或者地图数据库不完成而未包含当前路段信息)，则直接输出未经匹配的原始定位点坐标. 在进行跟踪匹配时首先判断车辆是否已经变换了路段，若行驶到了新的路段则需要执行跟踪匹配过程重新确定匹配路段，否则直接在当前路段上确定匹配位置.

图4 匹配的详细流程Figure 4 Flow of the map-matching algorithm

2.2 获取车辆行驶方向

车辆行驶方向可以从GPS 定位数据中直接获取，也可以由相邻两定位点坐标计算得到.但是这2种方法得到的方向信息受车速的影响较大:车速越大则方向信息越准确;车速越小则越不可靠，得到方向信息与实际行驶方向有较大出入. 当车速小于3 m/s 时，从GPS 定位数据得到的行驶方向将完全不可靠［5］. 本文采用从Android 移动终端自带传感器获取行驶方向的方法.为了获取行驶方向，需要利用方向传感器，这是一个虚拟的感应器.方向传感器将磁感应器和重力加速度计的数据融合得到行驶方向，具体算法已经封装在Android 的SDK 中，具体实现可以参考文献［9］.

3 结果与分析

实验硬件环境为一款普通Android 平板电脑(CPU 为ARMv6 单核245 MHz，内存402 MB，配备加速度计、磁感应器等传感器)，测试表明终端的GPS 定位精度为5 ～20 m. 搭载该终端在广州市进行大量的跑车实验，终端每隔1 s 记录一次当前的经纬度坐标、车辆速度和可见卫星数，并用一个DGPS(Differential GPS，差分GPS)接收机同步地记录差分定位坐标. 定位数据采集完成后，使用OSM［10］(Open Street Map，开放街道地图)矢量地图数据进行地图匹配实验，从路段识别正确率和匹配后的位置精度来评价地图匹配的效果. 如图5 所示，用不同距离权重(0，5，10，…，100)下的匹配评估模型对定位数据进行评估，找出相应的匹配路段，然后将匹配路段与真实行车线路进行比对，得到每种权重下的路段识别正确率.当wD=65 时，正确率达到最大值92.64%.

图5 不同权重下的路段识别正确率Figure 5 Road segment identifying rate under different weights

由于DGPS 定位坐标的精度较高(2 ～5 m)，这里将其视为车辆的真实位置. 以DGPS 定位坐标为参照，计算出地图匹配前GPS 坐标的平均位置精度(即GPS 坐标到DGPS 坐标之间的距离)为12.46 m.使用本文的优化方法对每个点进行匹配，得到不同αTH值下匹配后的位置精度(图5).当αTH=0°时，优化方法相当于垂直投影法，此时平均位置精度为8.23 m，比匹配前提高了4.23 m.当αTH=30°时，平均位置精度达到5.22 m，比垂直投影法提高了3.01 m(图6).图7 给出了复杂路段的匹配效果，GPS 定位点经过匹配之后都落到了正确的道路上面，匹配之后视觉效果有较大改善.

图6 不同αTH值下匹配后的平均位置精度Figure 6 Average positioning accuracy under different αTH values

图7 地图匹配效果Figure 7 Effect of the map-matching algorithm

4 结论

本文基于Android 移动终端的地图匹配算法利用了路段拓扑信息来缩小候选路段范围，采用综合考虑距离和方向两种要素的加权匹配评估模型来确定匹配路段，在确定匹配位置时对垂直投影法进行了优化.通过大量实验确定了算法的最佳参数设置，实验结果表明，该算法具有较高的路段识别正确率，优化方案相对于直接投影法在匹配后的位置精度上有所提高，地图匹配效果较好.

［1］王美玲，程林. 浮动车地图匹配算法研究［J］. 测绘学报，2012，41(1):133－138.Wang M L，Cheng L. Study on map-matching algorithm for floating car［J］.Acta Geodaetica et Cartographica Sinica，2012，41(1):133－138.

［2］Quddus M A，Ochieng W Y，Noland R B. Current mapmatching algorithms for transport applications:State-ofthe art and future research directions［J］. Transportation Research Part C:Emerging Technologies，2007，15(5):312－328.

［3］Velaga N R，Quddus M A，Bristow A L. Developing an enhanced weight-based topological map-matching algorithm for intelligent transport systems［J］. Transportation Research Part C:Emerging Technologies，2009，17(6):672－683.

［4］Wu Q P，Guo Z Y，Wang Y L. Study on GPS/DR/MM integrated navigation system for vehicle based DSP［C］.IEEE Xplore，2012:1591－1595.

［5］王敏，魏衡华，鲍远律. GPS 导航系统中的地图匹配算法［J］. 计算机工程，2012，38(14):259－261.Wang M，Wei H H，Bao Y L.Map-matching algorithm in GPS navigation system［J］. Computer Engineering，2012，38(14):259－261.

［6］陈滨，王平，施文灶，等. GPS 轨迹数据的综合地图匹配算法研究［J］. 电子科技，2014，27(12):20－23.Chen B，Wang P，Shi W Z，et al. An integrated mapmatching algorithm based on GPS［J］. Electronic Science and Technology，2014，27(12):20－23.

［7］王忠民，王青，张荣，等. 一种基于位置点的地图匹配改进算法［J］. 计算机应用研究，2013，30(11):3318－3323.Wang Z M，Wang Q，Zhang R，et al. Improved map-matching algorithm based on position points［J］. Application Research of Computers，2013，30(11):3318－3323.

［8］柳林，李万武，王志佘，等. 实时高精度地图匹配技术的研究与实现［J］. 测绘科学，2010，35(5):51－53.Liu L，Li W W，Wang Z Y，et al. Research and implementation of real-time high accuracy map-matching technique［J］.Science of Surveying and Mapping，2010，35(5):51－53.

［9］徐兵，廖友成，刘文杰，等. 基于Android 平台的车载导航系统研究［J］. 计算机测量与控制，2014，22(2):601－603.Xu B，Liao Y C，Liu W J，et al. Research on vehicle navigation system based on Android［J］. Computer Measurement ＆ Control，2014，22(2):601－603.

［10］张绛丽，张笑非，徐丹，等. 基于OpenStreetMap 的智能交通路网数据的构建［J］. 道路交通与安全，2014，14(1):41－47.Zhang J L，Zhang X F，Xu D，et al. Road_net data construction for intelligent transportation based on the Open Street Map［J］. Road Traffic＆Safety，2014，14(1):41－47.