基于多属性融合策略的车载导航地图匹配算法

滕志军，曲兆强，郭素阳，于 明，付 饶，井梓鉴

（1.东北电力大学信息工程学院，吉林吉林132012；2.中交天和机械设备制造有限公司，江苏苏州215000；3.国网吉林供电公司，吉林吉林132001）

基于多属性融合策略的车载导航地图匹配算法

滕志军1，曲兆强1，郭素阳2，于 明3，付 饶3，井梓鉴3

（1.东北电力大学信息工程学院，吉林吉林132012；2.中交天和机械设备制造有限公司，江苏苏州215000；3.国网吉林供电公司，吉林吉林132001）

目前直接投影算法常用于嵌入式车载系统，但其时效性以及精确性不能满足日益复杂的城市道路网络.针对传统算法检索复杂道路耗时多等问题，提出了基于多属性融合策略的车载导航地图匹配算法，提高了嵌入式车载地图匹配算法的时效性，算法采用等步长分块策略，建立分块网格索引减少筛选候选区域时间，从而提高算法的时效性；通过引入车辆行驶速度和历史匹配程度改进基于权重的直接投影算法，使用多属性融合策略确定匹配算法权重因子，提高地图匹配的准确性.结果表明：该地图匹配算法能够快速、准确地匹配出行驶路径，单点匹配时间降低至15 ms，复杂道路下，匹配准确率达到90%以上，能较好地适应于城市复杂道路网.

智能交通；地图匹配；融合策略；车载；匹配程度

目前，由定位导航系统得到的定位数据存在难以避免的误差，例如接收机内部噪声、无法修正的传播延迟误差等［1］，为了消除定位误差，提高定位准确性和可靠性，需引进有效的地图匹配算法［2］.地图匹配技术［3］是利用软件的方法，将定位点数据匹配到车载导航地图的道路网络中，从而确定车辆在导航地图上的准确位置.目前多数地图匹配算法的基本步骤：① 按照一定的筛选准则确定车辆当前行驶的道路；② 利用投影方式将定位点匹配到道路，获取车辆的准确位置信息［4－5］.文献［6］采用直接投影法将定位数据点直接投影到道路网络，该方法具有易于实现等优点，但是，定位数据本身的误差使得该方法存在可靠性不足的弊端.文献［7－8］提出了基于拓扑关系的地图匹配算法，此方法对电子地图精确度有较强的依赖性，特别在道路交叉路口，易出现匹配错误的状况.文献［9］采用模糊神经网络建立一种新型算法模型，能够较好地提高匹配的稳定性和时效性，同时也存在着实现难度较大，不适合车载嵌入式系统的问题.文献［10］提出了基于多权值的概率论匹配算法，该算法依据接收到的定位数据设置一个置信区域，利用概率准则选出道路匹配信息，此种算法对地图和定位数据精度具有较强的依赖性，存在稳定性较差的缺点.导航地图匹配算法的性能指标主要分为精确性、时效性和稳定性3个方面［11－12］.精确性是由匹配算法的误差、接收的定位数据误差等方面决定；时效性体现在获取匹配位置点的时间长短；稳定性取决于匹配算法的稳定以及接收的定位数据稳定2个部分.综合上述性能，笔者提出一种新型的地图匹配算法，该算法包括2个部分：①对导航地图分块处理，缩短搜寻匹配路段区域时间，提高系统的时效性；②采用改进的直接投影算法，将距离、速度以及方向偏角等因素预处理，能够有效地提高地图匹配的精确性和稳定性.

1 导航地图分块处理

通过对导航地图进行分块处理，能够有效减小搜寻道路网的数据规模，缩短获取匹配路段区域的时间，显著提高系统的时效性.因此，采用等步长的网格划分方式，建立路段信息的网格索引，定位点匹配过程中仅需考虑定位点周围的3×3网格（依据行驶区域设定）中的路段信息，有效提高了地图匹配过程的时效性.

建立网格坐标系，选取地图网络中的任意一点为坐标原点O，以l（依据工程经验一般选取200 m）为边长划分网格，以G（gx，gy）为分块网格索引号.若定位点为P（i，j），则定位点的网格索引号为

道路网格分块索引如图1所示，将定位点P（i，j）周围3×3的网格设置为搜索遍历区域，区域内的道路为候选匹配路段，分别建立对应的网格索引号.

图1 道路网格分块索引

2 地图匹配算法

通过对道路网的分块处理，使得定位数据能够快速确定其候选道路区域，综合利用地图匹配算法，达到快速定位的目的.由于车载嵌入式定位导航系统硬件等因素的限制，设备计算开销有限，因此相对简单、计算复杂度较低的直接投影地图匹配算法符合要求.由于传统的直接投影方法一般考虑将定位数据点到候选路段的距离和车辆行驶方向与候选道路的方向夹角等因素，通过加权计算来确定匹配路段.传统方式存在着算法过于简易、稳定性相对较差、权重因子需人工设置、缺少科学理论依据等问题.文中通过引进车辆行驶速度和历史匹配程度2个因素，采用多属性决策方法确定权重因子，从而提高直接投影方法的稳定性及精确性.

车辆行驶轨迹与候选道路的匹配程度为

式中：α为定位点到候选路段的距离权重系数；D为定位点到候选道路的距离；β为方向偏角的权重系数；θ为车辆行驶方向与候选路段的方向偏角；γ为行驶速度的权重系数；v为车辆行驶的速度；λ为历史匹配程度权重系数；W′为历史匹配程度.

现实道路网中存在很多弧段，道路网比较复杂，直接投影会出现如图2所示的错误情况.定位点P向弧段S做投影，投影点R落到弧段端点AB的连接线上，造成了错误的投影.因此需要进行弧段分割处理，将弧段分割成更小的线段，并将线段信息提取出来，作为候选匹配路段.

图2 弧段道路投影

3 算法参数设定

由于本算法涉及到定位点到候选路段的距离、车辆行驶方向与候选路段的方向偏角以及车辆行驶速度等参数，不同参数的度量单位不统一为确定当前定位点到候选路段的匹配程度带来了麻烦.因此，提出一种新型的参数设置方法，有效解决算法参数不统一的问题，降低系统计算开销，提高系统的匹配性能.

3.1 距离参数设定

第j个定位点到第i条候选路段的距离为dij，通常分为2种情况：①经定位点P作候选路段AB的垂线，垂足R落在候选路段，垂线长度为d1；②过定位点P做候选路段AB的垂线，垂足R处于路段的延长线上，则定位点到候选路段的距离为定位点到路段端点最近的距离d2.定位点j到候选路段i的距离dij如图3所示.

图3 定位点到候选路段的距离

定位点到候选路段的距离为

由于目前导航定位系统的精度为10 m左右，则设置定位点到候选路段的距离dij时，门限值选取10 m较合适.依据概率分布3倍标准差的原则，考虑到城市道路网的实际情况，最大距离选取30 m，当定位点到候选路段的距离大于30 m时，则认为定位点不会匹配到该候选路段.

3.2 方向偏角参数设定

城市道路网信息复杂多样，如车辆行驶于交叉路口，由定位距离确定候选路段会出现错误匹配的情况，则依据航偏角判断候选路段会较为准确.现定义平角八等分，数字1表示0°到22.5°，数字2表示22.5°到45.0°，依次类推.如图4所示，道路线AB对应的值为1，BC对应的值为2，车辆行驶路线P1P2为1，P2P3为1，P3P4值为2.

图4 定位点道路示意图

为了筛选出候选路段，引入航偏差：

式中：a1为车辆行驶方向值；a2为道路方向值.

通过航偏差得出车辆行驶方向与候选路段的方向偏角为

考虑到航偏差作为车辆行驶方向与候选路段的方向偏角的判断标准时，Δ取值相对较小，车辆方向偏角得出的匹配结果越精确，则航偏差小于1时，方向偏角参数取到最大值1.考虑到航偏差大于6时，车辆相当于掉头行驶，则方向偏角不能作为匹配因数.

3.3 车辆行驶速度参数设定

现城市交通路段大多数有速度限制，当匹配车辆无法确定车辆候选路段时，可以依据车辆行驶速度、道路网信息筛选出符合条件的匹配路段.然而，依据车辆在某一时刻的瞬时速度无法做出判断，则需要车辆第i时刻和前一个时刻i－1的平均速度：

式中：li为车辆由i－1时刻行驶到i时刻的距离；ti－1→i为行驶时间.

当接收到定位点数据后，经过计算可得车辆行驶速度，通过对候选区域内道路网速度信息限制条件比对，当v小于候选道路速度限制条件时，设置其参数为1；否则，认为车辆不会行驶在该路段，其参数设置为0，综合利用道路网信息能够更加有效地筛选出候选匹配路段.

3.4 历史匹配程度参数设定

当前匹配路段与历史匹配路段有关，候选路段的历史匹配程度越高，下一时刻匹配到该路段的可能性就越大.

历史匹配程度为

式中：Wik为第k个定位点到第i条候选路段的匹配程度，由式（2）可以得出；j为当前定位点数，j－1为历史定位点数.

历史匹配程度W′采用取平均的方式计算得出.

3.5 算法参数权重设定

传统算法权重因子由人工主观确定，使得匹配结果差异性较大，稳定性较弱，因此采用多属性决策方法来确定权重系数，较大程度地提高匹配的稳定性.考虑到距离因素d和方向偏角θ与候选路段的性质可以采用多属性决策方法来确定权重因子.然而车辆行驶速度由道路网信息决定，则可以设置：当车辆行驶速度参数为1时，其权重因子也设置为1；当车辆行驶速度参数为0时，其权重因子设置为0.历史匹配程度W′与之前的匹配程度有关，则其权重因子λ可以设置为

定义ρij为第i条候选路段的第j个属性值，根据上文权重因子的设置可知j分为2种情况，现定义ρi1为第i条候选路段对应的定位点到该候选路段的距离属性值，ρi2为第i条候选路段对应的方向偏角属性值.设区域内有m个候选路段，相应的评价定义为

定义ψj为第j个属性对应的权重系数，j＝1时，ψj为定位点到候选路段的距离权重系数α；j＝2时，ψj为方向偏角的权重系数β.

由设定好的参数计算出各定位点对应候选路段的匹配程度，选取匹配程度最大的候选路段作为匹配路段，再采用垂直投影得出匹配点，完成整个匹配过程.

4 仿真结果分析

地图匹配算法以时效性、准确性作为判断标准，为了验证所提出的算法的性能，将本算法以编程语言实现，应用于仿真测试系统中.该系统可以模拟城市复杂区域道路网信息，经过坐标转换，将道路网信息显示于二维坐标系中，模拟定位数据点进行匹配并在模拟地图中显示出匹配结果.模拟地图包含平行路段、交叉路段等复杂道路网络，可以有效验证提出的匹配算法的性能.通过对嵌入式车载常用的3种地图匹配算法仿真比较分析，验证了提出的匹配算法的时效性、准确性较优.

4.1 算法仿真比较分析

为了比较提出的匹配算法的性能，分别对传统的直接投影地图匹配算法与D S匹配算法和与GPS／DR组合导航的地图粗匹配算法进行匹配统计分析.对4种地图匹配算法的单点匹配时间仿真统计比较如图5，6所示.

图5 文中算法与GPS／DR粗匹配算法单点匹配时间比较

图6 直接投影与D S匹配算法单点匹配时间比较

为了验证地图匹配算法时效性性能指标，从不同的候选路段随机选取240个定位匹配点，对各个匹配点的匹配时间进行统计分析.由图5可以看出：提出的匹配算法单点定位时间约为15 ms，GPS／DR组合粗匹配算法单点定位时间为21ms左右；由图6可以看出：直接投影地图匹配算法单点定位时间与D S匹配算法相当，约为50 ms.由仿真统计可以得出，文中提出的地图匹配算法单点匹配时间较小、算法的时效性较优.

通过选取单一路段、平行路段、交叉路段以及相对复杂的组合路段对4种不同的地图匹配算法的匹配准确率进行统计比较，如图7所示.

图7 不同候选路段匹配算法准确率比较

从图7可以看出：单一路段各匹配算法匹配准确率相当，当车辆行驶入平行路段、交叉路段以及复杂的组合路段时，文中提出的地图匹配算法相对于其他算法匹配准确率较高，则该算法的准确性较好，能够更好地适应日益复杂的城市道路网络.

4.2 算法模拟验证

为了使算法更具有说服力，选取复杂程度相对较高的城市道路网作为仿真模拟的区域，其定位点匹配仿真模拟的结果如图8所示.“☆”为模拟定位点，“o”为车辆的匹配位置点.

图8 算法模拟仿真图

从图8可以看出：提出的匹配算法能够较为准确地匹配车辆真实位置，但是，当车辆行驶于道路交叉路口时，该匹配算法依然会受到影响，虽然能够较为准确匹配车辆行驶路段，但路口交叉处会出现匹配点集中的现象.考虑到嵌入式车载地图匹配算法的实际应用情况，交叉路口的匹配问题可以忽略不计.因此由图8可以得出：提出的匹配算法能够较为准确地匹配出车辆真实位置，匹配算法性能有较大的提高.

5 结 论

随着现代道路网络日益复杂，传统的地图匹配算法不能有效、准确地匹配车辆行驶位置.在传统投影算法的基础上，引入车辆行驶速度和历史匹配程度2个因素，考虑到各因素之间单位不统一的情况为匹配性能带来了影响，对各参数进行了统一设置，采用多属性融合策略确定权重因子.仿真结果表明：文中提出的地图匹配算法能够实时、准确地匹配出车辆行驶位置，适用于复杂的城市道路网.但引入速度参量时仅考虑车辆正常行驶情况，未对超速行驶作出分析，如何实现非正常状态行驶的道路匹配是下一步研究的方向.

（References）

［1］ CHEN F，SHHEN M Y，TANG Y N.Local path searc hing based map matching algorithm for floating car data［J］.Procedia Environmental Sciences，2011，10（7）：576－582.

［2］ LIX，WANG Y N，WANG M，et al.Map matching al gorithm design based on GPS information［C］∥IEEE Workshop on Electronics，Computer and Applications.USA：IEEE，2014：898－901.

［3］ BLAZAQ CA，VONDEA A P.Effects of controlling pa rameters on performance of a decision rulemap matching algorithm［J］.Journal of Transportation Engineering，2009，135（12）：966－973.

［4］ 李清泉，黄练.基于GPS轨迹数据的地图匹配算法［J］.测绘学报，2010，39（2）：207－211.LIQ Q，HUANG L.A map matching algorithm for GPS tracking data［J］.Acta Geodaetica et Cartographica Si nica，2010，39（2）：207－211.（in Chinese）

［5］ JIA B，LIU C.Map matching algorithms based on inva riantmoments［J］.Journal of Computational Information Systems，2011，7（16）：5668－5673.

［6］ 苏奎峰，邓志东，黄振.基于曲率特征的自主车辆地图匹配定位方法［J］.机器人，2012，34（4）：440－446.

SU K F，DENG Z D，HUANG Z.A novel localization approach for autonomous vehicles based on map matc hing with curvature features［J］.Robot，2012，34（4）：440－446.（in Chinese）

［7］ YANG H Q，CENG SW，JANG H F，et al.An en hanced weight based topologicalmap matching algorithm for intricate urban road network［J］.Procedia Social and Behavioral Sciences，2013，96（6）：1670－1678.

［8］ SALAMAT N，ZAHZAH E H.On the improvement of combined fuzzy topologicaland directional relations infor mation［J］.Pattern Recognition，2012，45（4）：1559－1568.

［9］ 李洋，张晓冬，鲍远律.多权值概率论实时地图匹配［J］.电子测量与仪器学报，2012，26（2）：166－170.

LIY，ZHANG X D，BAO Y L.Algorithm on real time map matching ofmulti weight probability［J］.Journal of Electronic Measurement and Instrument，2012，26（2）：166－170.（in Chinese）

［10］ DEKA L，QUDDUSM.Network level accident mapping：distance based pattern matching using artificial neural network［J］.Accident Analysis＆Preventin，2014，65（4）：105－113.

［11］ 方凌，赖际舟，张小山，等.基于故障状态监测的惯性／卫星信息融合技术［J］.江苏大学学报（自然科学版），2011，32（1）：94－98.FANG L，LAIJZ，ZHANG X S，et al.Information fu sion technology of INS／GNSS based on fault state detec tion［J］.Journal of Jiangsu University（Natural Science Edition），2011，32（1）：94－98.（in Chinese）

［12］ 杨英杰，钦鹏明.一种改进的GPS微弱信号捕获算法［J］.东北电力大学学报，2013，33（5）：57－60.YANG Y J，QIN P M.An improved GPS weak signal capture algorithm［J］.Journalof Northeast DianliUniver sity，2013，33（5）：57－60.（in Chinese）

Vehicle navigation map matching algorithm based on multiple attribute integration strategy

TENG Zhijun1，QU Zhaoqiang1，GUO Suyang2，YU Ming3，FU Rao3，JING Zijian3
（1.School of Information Engineering，Northeast Electric Power University，Jilin，Jilin 132012，China；2.Tianhe Mechanical Equipment Manufacturing Co.，Ltd.，Suzhou，Jiangsu 215000，China；3.State Grid Jilin Power Supply Company，Jilin，Jilin 132001，China）

The present direct projection algorithm is often used in embedded vehicle system，while the timeliness and accuracy can notmeet the increasingly complex urban road network.To solve the time consuming problem of complex road in traditional retrieval algorithm，a matching algorithm for vehicle navigation map fusion strategy was proposed based on multi attribute matching algorithm to improve the efficiency of embedded vehicle map.The equal step block strategy was adopted for building block grid index to reduce screening candidate regions and improve the algorithm efficiency.The direct projection algorithm based on weightwas improved by the introduction of vehicle speed and historymatching degree，and themultiple attribute fusion strategy was used to determine thematching algorithm ofweighting factor and improve themap matching accuracy.The experimental results show that themap matching algorithm can quickly and accurately match the driving path，and the single pointmatching time is reduced to 15 mswith accurate rate more than 90%under complex roads.The proposed algorithm is suitable for the complex city road network.

intelligent transportation；map matching；integration strategy；vehicle；matching degree

10.3969／j.issn.1671－7775.2018.01.003

TN967.1

A

1671－7775（2018）01－0014－05

2016－11－25

国家自然科学基金资助项目（51277023）

滕志军（1973—），男，吉林吉林人，教授（tengzhijun＠163.com），主要从事无线电通信研究.

曲兆强（1990—），男，山东泰安人，硕士研究生（753731087＠qq.com），主要从事地图匹配算法研究.

滕志军，曲兆强，郭素阳，等.基于多属性融合策略的车载导航地图匹配算法［J］.江苏大学学报（自然科学版），2018，39（1）：14－18，25.

（责任编辑 贾国方）