瞿逸伦，卿 立，张 迪，何 伟，李殿茜

(1.北京自动化控制设备研究所·北京·100074；2.空装驻北京地区第二军事代表室·北京·100074)

0 引 言

地图匹配技术已被广泛应用于车载导航定位系统[1]。该技术实质上是基于车辆始终行驶在道路上的假设，通过各类传感器获取车辆的行驶轨迹，并将行驶轨迹与数字地图中提供的路径信息进行匹配，以获取车辆的绝对位置[2]。

目前，现有的地图匹配算法包括直接投影法、概率统计法、相关性算法、基于网络拓扑关系的算法等。直接投影法是一种典型的点到线的确定型匹配算法。其基本思路为：求取定位点与周围路段之间的距离，通过比较投影距离的大小，确定车辆所在的道路。一般而言，可选择定位点和路段间垂直投影距离最小的路段为匹配路段，取投影点作为车辆在道路上的匹配点。直接投影法的算法逻辑简单，匹配速度快，但其不能消除沿道路方向上的定位误差。直接投影法对原始定位精度的要求较高，对道路交叉口等复杂路段的匹配精度较低，稳定性较差[3-5]。

概率统计法的基本思想是依据车辆的定位信息、利用概率准则设置一个置信区域(误差椭圆)，从而在每次匹配时不再需要遍历所有路段，极大地缩小了候选路段的范围，最后可通过对候选路段的判断得到最佳的匹配结果。概率统计法的优点在于通过设置误差区域，缩小了匹配路段的选择范围，使得匹配效率得到了提高。但是，概率统计法并没有有效利用车辆行驶的历史信息。如果当前置信区域道路密集，匹配位置在相邻路段间可能反复跳跃，产生误匹配，进而影响匹配精度[6]。

基于拓扑关系的地图匹配算法通过对前一次的匹配结果和对车辆前进方向进行分析，利用道路的空间拓扑关系，确定当前定位点候选路段的范围，并快速找出定位点所在的匹配路段，进而计算出当前定位点的匹配点。基于拓扑关系的地图匹配算法实时性较好，而且在候选路段相互平行的情况下匹配效果明显。但是，该算法必须在电子地图道路拓扑关系完整的情况下才可应用。同时，匹配的正确性对初始匹配结果的依赖性大，算法的容错能力较差[5]。

现有的地图匹配算法往往需要根据行驶轨迹在地图道路信息中寻找匹配路段，或依赖初始匹配结果。城市道路环境多存在多种岔路、路口、死路，以及短支路等，并且路网分布密集。现有地图匹配算法在此场景下需要频繁寻路，并且容易发生寻路错误、难以及时修正寻路结果的情况，进而影响后续匹配结果。在城市峡谷环境中，卫星信号会被遮挡，易导致初始定位误差较大[7-9]。

对此，本文提出了一种基于图像卷积的地图匹配算法。该算法利用车载惯性/里程计组合导航系统确定车辆行驶轨迹，将轨迹图像与地图图像进行匹配、完成定位，并且通过匹配结果对惯性/里程计定位结果进行补偿，抑制其误差发散。该算法不依赖于对匹配路段的寻找，可适用于初始定位误差较大的使用场景。同时，由于惯性/里程计不依赖外部信息源，用其轨迹进行匹配可在提高精度的同时保持系统的自主性。

1 Web墨卡托坐标系

Web墨卡托坐标系是一种利用公共可视化伪墨卡托投影方法而得到的坐标系，是一种为谷歌地图、微软虚拟地球等网络地理所应用的地图投影坐标系，如图1所示。

图1 墨卡托投影Fig.1 Mercator projection

公共可视化伪墨卡托投影是正轴等角圆柱投影。设地球为正球体，假想存在一个与地轴方向一致的圆柱切于地球，按等角条件将经纬网投影到圆柱面上，将圆柱面展为平面，即可得到其投影[10]，通过墨卡托投影可得到Web墨卡托坐标系。

不同于WGS-84坐标系、GCJ-02坐标系等椭球面地理坐标系，Web墨卡托坐标系以地球经纬度作为参考。Web墨卡托坐标系为投影坐标系，是平面坐标系，以米为单位。

本文后续对于地图信息、道路信息以及定位信息的描述皆在Web墨卡托坐标系下进行，取东向为X正方向，北向为Y正方向。

2 二维离散卷积

图像经过数字采样可转化为矩阵，因此图像卷积实质上是二维离散卷积，如式(1)～式(2)所示。其中，*表示卷积运算

H=F*G

(1)

(2)

图像经数字采样得到矩阵G。在卷积过程中，采用一个大小为a×b的矩阵F来表示特征权值，这样的矩阵被称为卷积核。F的尺寸通常小于G。当F中第1行第1列元素F(1,1)与G中第i行第j列元素G(i,j)重合时，将F中的每个元素与G中重叠区域的每个元素分别相乘，其乘积之和为该区域的卷积值，即卷积阵H中第i行第j列元素H(i,j)。F在G上滑动，通过每一次滑动可得到对应区域的卷积值。最终，F遍历G，可得出关于图像的卷积矩阵H。

卷积可以从输入的图像中提取图像的特征，并可以保留像素间的空间关系。在每次运算中，将卷积核元素与图像中卷积核覆盖区域的元素分别相乘求和，可得到卷积值。卷积值反应了该区域内图像特征与卷积核特征的相关性。以二值图像及二值卷积核为例，每个卷积值代表了该图像重复区域与卷积核的图像重复像素点个数。

3 基于二维离散卷积的地图匹配算法

车载惯性/里程计组合导航系统能够测量车辆的位置信息，且不依靠外界信息源，具备自主性。但是，惯性/里程计自身的特性导致其定位误差随时间及行驶里程的增加而发散，难以在长时间、大范围条件下保持定位精度。对此，本文提出根据车辆行驶轨迹进行地图匹配，以确保长时间、大范围条件下的定位精度[11-13]。

本文通过车载惯性/里程计组合导航系统的定位信息，获得车辆行驶轨迹及轨迹图像，将轨迹图像与地图道路图像进行卷积，在地图图像上寻找与行驶轨迹相关度最高的道路，进而通过像素点位置与地图道路信息进行匹配，输出当前的位置信息。

3.1 算法流程

设每次匹配需截取的车辆行驶轨迹长度为Lt。在初次匹配时，根据里程计信息，在行驶里程大于Lt后，截取车辆行驶轨迹，并根据历史信息对其进行补偿，以补偿后的轨迹作为初始轨迹，绘制轨迹图像。根据截取轨迹的边界信息判断此时轨迹是否处于当前载入的地图块之内，若不在地图块内，则根据当前轨迹所在位置搜索其所在的地图块，并载入新的地图块信息、绘制其地图块的图像；若在地图块内，则判断此时轨迹是否正在跨越地图块边界，若是则进入下一拍，若不是则开始匹配。

由于惯性/里程计组合定位信息存在一定的初始误差，故需要在轨迹图像范围的基础上扩大匹配区域。开始匹配后，首先将轨迹图像的边界南北向与东西向各延展le米，以此范围在地图块图像上进行截取，得到匹配区域的地图图像。将轨迹图像作为卷积核在匹配区域的地图图像上进行卷积，得到与本次匹配的卷积矩阵。对卷积矩阵进行归一化后，进行判决：(1)卷积矩阵中有且仅有一个最大卷积值；(2)卷积值超过门限。若同时满足上述两条判决，则本次匹配成功，推算地图匹配的位置信息；否则，匹配失败，进入下一拍。

通过搜索卷积矩阵中最大卷积值相对于卷积阵的坐标，以及轨迹图像中末端点像素相对于轨迹图像的坐标，即可推算出当前位置在地图图像中的像素坐标，通过地图信息得到当前位置信息，并输出本拍的匹配位置信息。同时，计算惯性/里程计定位结果与匹配结果的差值，以此差值对下次匹配时的惯性/里程计定位结果进行补偿。先进行补偿，再进行下次匹配。

本次匹配结束后，根据里程计信息，在继续往前行驶l米后，截取从当前位置向前、长度为Lt的轨迹作为新的匹配轨迹，并进行下次匹配。算法流程如图2所示。

图2 算法流程图Fig.2 Flow diagram

3.2 轨迹截取及轨迹图像绘制

在初次匹配时，需利用到里程计的信息。当里程计输出首次大于Lt时，取车辆行驶轨迹为初始轨迹，并根据惯性/里程计组合定位信息绘制其轨迹图像。

将惯性/里程计组合导航定位系统的输出位置坐标转换为其在Web墨卡托坐标系下的坐标，即可得到一组Web墨卡托坐标系下的轨迹坐标。设轨迹中的坐标组数为n，则Web墨卡托坐标系下的轨迹坐标可表示为

(3)

取轨迹X方向坐标最大值Xtmax、X方向坐标最小值Xtmin、Y方向坐标最大值Ytmax、Y方向坐标最小值Ytmin为轨迹边界。将轨迹绘制为轨迹图像，需要将轨迹位置转换为像素点的坐标轨迹图像矩阵中所有的轨迹点坐标处对应的矩阵元素置为1，其余置0，即可得到轨迹图像矩阵Tm×n。

同理，当一拍匹配结束后，等待里程计测量值增加l米，根据里程计信息截取从末端起长度为Lt的轨迹信息。根据上述步骤计算得到新的轨迹图像矩阵，以此进行下一拍的匹配。

3.3 地图搜索与地图图像绘制

截取轨迹期间，可得到轨迹于Web墨卡托坐标系下的边界信息Xtmax、Xtmin、Ytmax、Ytmin，以及惯性/里程计组合输出的Web墨卡托坐标系下的当前位置(Xtn,Ytn)。将当前位置(Xtn,Ytn)与当前已载入地图块的边界进行对比，判断轨迹是否仍处于当前载入的地图块。Xbmin为地图X坐标的最小值，Xbmax为地图X坐标的最大值，Ybmin为地图Y坐标的最小值，Ybmax为地图Y坐标的最大值。若满足

(4)

则轨迹已在地图内；若轨迹不在地图内，则重新搜索地图。若是初次匹配，则无需判断当前位置是否在地图内，可直接进入地图搜索步骤。

搜索地图则根据惯性/里程计输出的当前位置于Web墨卡托坐标系下坐标(Xtn,Ytn)，搜索当前所处的地图块。遍历地图文件中的每个地图块的边界，当存在地图块满足式(4)条件时，则选取该地图块为当前所在，并载入地图信息，绘制地图块。

绘制地图图像与绘制轨迹图像类似。将地图图像矩阵中道路所在的像素点对应的矩阵元素设置为1，将其余置为0，即可得到地图图像矩阵Μp×q。

3.4 地图像素对应的地理位置

为后续推算匹配位置，需要为地图图像的每个像素添加与其对应的Web墨卡托坐标系下的位置坐标。设地图图像中第1行第1列像素对应的Web墨卡托坐标系下的坐标为(Xmw1,Ymw1)，其中

(5)

式中，R为取整运算，Ppixel为一个正方形像素的边长所代表的实际距离。图像中第p0行和第q0列像素对应的Web墨卡托坐标系下的坐标为(Xmwp0,Ymwq0)，其中

(6)

由此，可以推算地图图像上每个像素点对应的Web墨卡托坐标系下的位置坐标。

3.5 匹配区域截取

由于惯性/里程计组合定位信息存在一定的初始误差，需要在轨迹图像范围的基础上扩大匹配区域。地图块的整体图像较大，将地图块图像整体与轨迹图像进行卷积，将带来巨大的计算量，影响匹配的实时性，故需要从地图块图像中截取部分图像作为匹配区域图像。

将惯性/里程计输出的轨迹图像的边界南北向与东西向各延展le米，以此范围在地图图像上进行截取。匹配区域在地图图像上的边界像素坐标可按下式求出

(7)

设

(8)

根据边界，截取地图图像矩阵中由Xpmin列至Xpmax列、由Ypmin行至Ypmax行区域内的元素作为匹配区域，得到匹配区域图像矩阵Pj×k。

3.6 轨迹匹配

将轨迹图像矩阵作为卷积核，在匹配区域图像上进行二维离散Valid卷积，即卷积核内的所有元素均有图像矩阵中的元素与其对应。卷积核在输入图像中滑动，滑动步长为1。在每一次滑动过程中，卷积核内的每个元素与对应匹配区域图像中的重叠区域的每个元素分别相乘，其乘积之和即为该区域的卷积值。卷积核遍历图像中所有的点，即得到卷积矩阵C0

C0(m-p+1)×(n-q+1)=Tm×n*Pp×q

(9)

在得到卷积阵C0后，对卷积阵C0进行归一化处理，设

(10)

则归一化的卷积阵C为

(11)

通过卷积阵C对本次匹配的可用性进行判别。设C中的最大元素为Cmax，判别条件如下

(1)C有且仅有一个最大值Cmax；

(2)Cmax超过门限值Cs。

若同时满足上述两项判决条件，则本次匹配有效，继续推算匹配位置的坐标；否则，本次匹配失败，进入下一拍。

3.7 匹配位置推算

若满足判决条件，设Cmax元素在C阵中的矩阵坐标为(Xc,Yc)。当前所处位置为轨迹末端点，其在轨迹图像矩阵T中的矩阵坐标为(Xtfn,Ytfn)。根据式(6)，Web墨卡托坐标系下的轨迹末端点的匹配位置可通过式(12)进行解算

(12)

3.8 地图匹配在定位定向系统中的应用

当定位定向系统采用纯惯性导航时，由于惯性器件的误差积累效应，惯性导航系统的定位误差将会随导航时间的增加而迅速发散。惯性/里程计组合能够在一定程度上抑制惯性误差发散，但随着里程增加，定位误差依然会逐渐积累[14-15]。

地图匹配具有较高的理论精度，但在复杂路况下，其存在匹配结果不可用的情况，故其定位结果存在不连续性。可通过地图匹配修正惯性/里程计的积累误差，使地图匹配与惯性/里程计形成优势互补，从而保证长时间、连续的高精度定位输出。

设当地图匹配结果可用时，地图匹配当前输出的定位结果为(Xw,Yw)，定位定向系统当前输出的定位结果为(Xtn,Ytn)，则此时的位置修正量为

(13)

用本次匹配所得的修正量对后续的惯性/里程计定位结果进行补偿

(X′tn+1,Y′tn+1)=(Xtn+1+eX,Ytn+1+eY)

(14)

以此类推，当进入下一次地图匹配时，轨迹信息被上一拍匹配的修正量所补偿。先补偿、后匹配的方式能够避免由惯性/里程计误差发散所导致的轨迹与真实路段距离过远、进而匹配失败的情况。同时，由于卷积计算本身的特性，匹配对图像畸变有一定的适应性。上述适应性使得即使由于误差发散导致轨迹出现一定的变形，仍能保证匹配的正确性与精度。当下次匹配有效时，则对修正量进行更新；当地图匹配结果不可用时，则不对修正量进行更新。

4 仿真验证

根据跑车数据，对地图匹配与定位定向设备组合定位效果进行仿真验证。定位定向系统采用惯性/里程计组合导航系统进行定位，仿真条件如表1所示。

表1 仿真条件Tab.1 Simulation Condition

将惯性/里程计组合位置输出作为轨迹信息，进行地图匹配。当匹配成功时，根据式(13)、式(14)的地图匹配结果对惯性/里程计定位结果进行补偿，仿真结果如图3～图5所示。

图4 东向位置误差Fig.4 East position error

图5 综合位置误差Fig.5 Position error

仿真的位置误差统计如表2所示。

表2 误差统计(1σ)Tab.2 Error statistics(1σ)

从图3～图5可以看出，当匹配成功时，可通过匹配结果对后续惯性/里程计定位结果进行补偿。这种补偿方式能够消除一定的定位误差，对惯性/里程计的定位误差发散具有一定的抑制作用。由表2的统计结果可以看出，经地图匹配的补偿，惯性/里程计组合定位精度高于无匹配的惯性/里程计组合。

5 结 论

本文通过图像卷积的方式，对车辆行驶轨迹图像与地图图像进行了匹配，并完成了定位。相比现有的地图匹配算法，该算法不依赖路口匹配，避免了由较大的初始误差场景所带来的寻路错误，以及由路口匹配错误对后续匹配精度带来的影响。通过地图匹配对定位定向设备进行误差修正，提高了定位精度，且其不需要依靠外部信息源，具备一定的自主性。