结合行驶场景语义的轨迹-路网实时匹配方法

傅 琛，黄升钶，汤 焱，吴杭彬,3，刘 春,3，姚连璧,3，黄 炜

1. 同济大学测绘与地理信息学院，上海 200092； 2. 北京大学地球与空间科学学院，北京100871； 3. 同济大学城市交通研究院，上海 200092

近年来，随着各种感知技术与传感器设备的发展，自动驾驶技术成为新的研究热点。自动驾驶过程中，实时地图匹配技术在车辆定位、路线规划、实时导航、路况上报与更新、驾驶决策等过程中起到了重要的作用[1]。

地图匹配技术(map matching)是指将单个或系列GNSS点与地图匹配的过程，其本质是利用地图对GNSS数据进行约束。在实时导航、轨迹数据分析等领域中，地图匹配作为数据分析的前期处理流程，为原始数据赋予路网语义信息，并为路径规划、交通分析、轨迹分析等技术提供基础数据[2]。

针对不同特性的GNSS数据与地图数据，学者们提出了多种地图匹配算法和多种地图匹配算法分类体系。文献[3]对2007年以前已有的地图匹配算法进行了回顾，将地图匹配算法分为基于几何的算法、基于拓扑的算法、基于概率的算法与使用先进技术的算法。文献[4]根据地图匹配算法的时效性将地图匹配算法分为在线匹配算法[5-8]与离线匹配算法[9-12]。在线匹配算法(又称局部匹配)需要实时或在较短时间内根据当前定位点数据或结合历史匹配结果，将当前点捕捉至地图上[13]；而离线匹配(又称全局匹配)是在已知完整轨迹的情况下对轨迹进行整体匹配[12,14-17]。应用于导航和自动驾驶的地图匹配算法需要在短时间内确定车辆位置，因此需要在线匹配算法。引入隐马尔可夫模型[18]、模糊匹配理论[19]等先进方法的在线匹配算法在处理采样频率较低的轨迹时占有优势，但通常计算复杂度较高[4]、存在一定的延时，难以适用于硬件处理能力有限、对实时性要求高的场景。

随着城市不断建设完善、电子地图技术不断发展，城市电子地图越来越复杂，尤其是在城市主干道、高架快速路等路段，在三维空间中不同高度的道路在平面地图上重叠、交织，单一采样点搜索到的备选路段数量快速上升。当前对地图匹配技术的研究中，针对高架沿途路段匹配问题的研究较少，文献[19]利用出租车数据中的特定字段，如载客、载客状态变化等属性，结合车辆的行驶速度与行驶模式，通过模糊推理系统推断车辆是否在高架上。而实际情况可能不满足假设的某些条件要求(如在高架堵车时，高架上车辆也会出现走走停停的模式)，从而造成错误匹配。

驾驶过程中拍摄的图像蕴含着丰富的信息，随着图像采集设备的普及和成本的降低，部分研究开始使用驾驶过程中拍摄的图像作为GNSS轨迹数据的补充。目前此类研究通常将图像用于车道线识别，结合车道级高精度地图实现在单一道路内部的车道匹配和相对定位，而非作用于轨迹与不同道路间的匹配。文献[20]对手机拍摄的图像进行逆透视变换和Hough变换提取车道线，并结合车辆行驶方向确定行驶车道。文献[21]同时使用图像提取的车道线和拓扑匹配法分别进行车道级地图匹配，最终使用扩展卡尔曼滤波将两种匹配结果与GNSS轨迹、航位推算结果进行融合，提高了车道级相对定位精度。

综上所述，现有的普通在线匹配算法在高架、立交等复杂区域容易出现误匹配的现象，而结合图像进行复杂道路场景下道路级轨迹匹配的研究较少。针对这一问题，本文利用与行车轨迹同步采集的系列行车记录图像，提出了一种结合行驶场景分类的地图匹配技术，利用图像确定车辆与高架道路的关系，进而提高在线匹配算法在高架路段的匹配正确率。

1 结合行驶场景分类的轨迹-路网实时匹配方法(DSCMM)

1.1 数据定义

本文使用的轨迹-相片数据来源于自带定位功能的行车记录设备或无人驾驶车。在车辆行驶过程中，按照一定采样频率对车辆位置进行定位，在定位的同时保存相应的视频帧图像，作为属性数据附加在定位点上，得到一组轨迹-相片数据。相关定义如下。

定义1：采样点p

p={timestamp,lon,lat,speed,direction,image}

单个采样点是由单台设备使用其定位模块获取车辆当前位置信息，并同步记录当前时刻视频图像得到的一组数据集合。其中，timestamp代表采样点的时间戳，(lon,lat)代表车辆所处经纬度，speed代表GNSS设备采集的采样点车速，direction代表车辆行驶方向的方位角，image代表与当前采样点同步采集的行车记录图像。

定义2：车辆轨迹T

T={p1,p2,…,pn}

车辆轨迹T是指由同一车辆按照一定时间间隔连续采样得到的一组顺序排列的采样点集合。n表示轨迹点的个数。

定义3：城市道路网络G

G=(Node,Seg)

城市道路网络G为由节点与路段构成的有向图，其中，Node表示两条道路的交点，在节点处，车辆可以在相邻道路内按照转向规则进行转移；Seg表示路段，是指两个节点之间表示道路中心线的单向或双向线段，一条道路由多个路段组成。各路段具有相应的道路类别属性。

定义4：候选路段集C

C=(Seg1,Seg2,…,Segm)

候选路段集C表示当前待匹配点p的候选路段集合。m代表集合中的路段数量。

定义5：最佳匹配路段M

对当前采样点的备选路段集C，以匹配指标得分最高的路段Segj作为最佳匹配路段M。

定义6：行驶场景定义

行驶场景指车辆行驶过程中所处的道路环境，考虑到地图匹配的难点所在，本文将车辆行驶场景分为城市快速道路、普通道路、室内道路(隧道、地下停车场等)3类。图1给出了3种类型典型场景的图像。

图1 各行驶场景行车记录图像Fig.1 Images of each driving scene

1.2 结合行驶场景分类的轨迹-路网实时匹配方法框架(DSCMM)

本文提出的结合行驶场景分类的轨迹-路网实时匹配方法(a real-time map matching method for road network using driving scenario classification，DSCMM算法)(图2)，将车辆或设备实时采集的图像所获得的场景语义信息加入匹配过程，提高行驶车辆位于城市快速路、普通道路、室内道路等场景时实时地图匹配的精度。

图2 算法流程Fig.2 The workflow of map-matching algorithm

算法包括候选路段搜索、行驶场景分类和地图匹配计算等3个步骤。输入采样点后，在路网数据内搜索候选路段集；当车辆处于复杂道路区域时，利用训练好的行驶场景分类模型对图像进行分类，计算图像属于各类行驶场景的概率；计算当前采样点候选路段集中每一条路段各相应指标得分，综合评价该路段得分，取其中得分最高的路段作为当前采样点的匹配结果，完成单个采样点的匹配。

1.3 候选路段集搜索

GNSS设备采集的采样点存在定位误差，且路网中的路段表示的是道路行驶方向的中心线，在实际行车过程中，行驶车道与道路中心线之间存在一定偏差。因此，对当前采样点pi，设置一定阈值d构建缓冲区，与缓冲区相交道路将会被识别为当前采样点pi的候选路段集Ci。地图匹配的目的，就是从Ci集合中选择最合适的匹配结果。

当候选集合Ci中只有一类道路时，现有算法已经能完成地图匹配，不需要进行分类。而当Ci中存在不同类型的道路时(如快速路与普通道路)，传统的地图匹配方法存在困难，因此需要借助轨迹点的视频图像数据进行场景分类，提高匹配精度。

1.4 行驶场景分类

本文采用支持向量机完成行驶场景的分类。支持向量机(support vector machine，SVM)是文献[22]提出的一种机器学习模型，其本质为构造能正确划分数据集且几何间隔最大的超平面。针对非线性分类问题，SVM将样本映射到高维线性特征空间，从而转化为线性可分问题进行求解[23]。利用支持向量机对图像进行分类，实际上是将图像每一像素当作一个特征值，利用支持向量机对不同类别图像的特征进行分类训练，获得当前样本下最佳分类超平面，并利用该分类结果对输入图像进行预测，获得其对应的分类。SVM模型进行预测的时间复杂度为O(M·S)，其中M与核函数相关，S为支持向量数[24]。

在行车轨迹的对应图像中，当车辆在高架下方行驶时，天空会被高架桥遮挡；在高架或高速上行驶时，多数情况下不会受到遮挡，且画面内容与普通道路区别较大；而隧道(包括地下停车场等)内的图像也与其他场景的图像存在较大区别。基于各类场景的特点，这些场景存在较大的可分性，本文基于与采样点pi对应的图像image，利用SVM支持向量机对图像进行分类，将行驶场景分为快速路(包括高架快速路和高速公路)、普通道路(包含高架辅道及高架附近普通道路场景)、室内(包括隧道、地下停车场等)3种场景。利用SVM模型对图像进行预测，得到输入图像属于各类别的概率P

(1)

1.5 地图匹配指标计算

本文提出的结合行驶场景分类的轨迹-路网实时匹配方法综合考虑了驾驶过程中的场景语义信息、车辆行驶方向信息、距离指标、邻接指标等，通过不同指标的综合运算，确定候选路段集中各路段的匹配概率。

1.5.1 行驶场景指标

(2)

式中，i表示第i个采样点；Pi,express、Pi,normal、Pi,indoor分别表示当前图片为快速道路、普通道路和室内道路的概率。

(3)

例如，假设当前点Pi对应图像的分类结果为Pi,express=0.95，Pi,normal=0.03，Pi,indoor=0.02。若某候选路段为城市快速路，则其行驶场景指标为0.95；若另一候选路段为普通道路，则其行驶场景指标为0.03。

1.5.2 方向指标

(4)

图3 方向指标Fig.3 Schematic diagram of direction index

式中，αj表示当前采样点pi的车辆行驶方向与备选路段集Ci中第j条路段首尾方向之间的夹角，当备选路段为双向道路时，使用两个方向中的较小角度作为两个方向的夹角。使用指数函数降低大角度备选路段的匹配可能性，并增加对小角度区域的容忍性。k为缩放因子(k>0)，用于控制方向指标在最终得分中的影响力。

1.5.3 距离指标

采用零均值的高斯分布的概率密度函数[25]作为距离指标，对候选路段是采样点真实匹配路段的概率进行评估

(5)

1.5.4 邻接指标

邻接指标是指对当前采样点pi的第j条备选路段，若该备选路段与上一采样点pi-1的最终匹配路段Mi-1共享至少一个节点(Node)，则认为该路段与上一采样点的匹配路段邻接，即该路段可能与上一采样点的匹配路段直接连接，或为同一路段。邻接指标函数定义为

(6)

自动驾驶车或行车记录设备一般以高频率采样得到数据，因此采样点之间距离近，采用邻接指标可以提高匹配正确率，同时也避免了使用最短路径算法产生的计算量。

1.5.5 最优匹配选择

假设以上各指标之间相互独立，用联合概率计算当前采样点pi的候选路段Ci中，第j条候选路段Segj是真实匹配路段的概率，则各路段的最终得分的计算方法为

(7)

遍历候选路段集Ci中的各路段得分，将得分最高的路段作为最优匹配结果。

2 试验与分析

2.1 试验数据

使用3组位于上海市的行车轨迹和OpenStreetMap数据进行试验，具体信息见图4和表1。轨迹1和轨迹2为正常条件下采集的数据，天气状况好，光照适宜，图像清晰；轨迹3则在早晨5～6点采集，光照较弱，天气状况差，全程降雨且部分路段为大暴雨，能见度较差。轨迹1～3途经上海内环高架、中环高架、逸仙高架、沪嘉高速、京沪高速、沪昆高速等城市快速路和高速路及其附近普通道路，以及大柏树立交、邯郸路地道、外环立交、莘庄立交、共和新路立交等复杂道路区域。

图4 试验轨迹Fig.4 Trajectories used in the experiment

表1 试验数据情况

使用3条试验轨迹的图像和部分零散图像构建行驶场景分类数据集，通过人工判断标注每张图像的行驶场景类别。数据集包含各类场景图像共7801张，其中城市快速道路5980张，普通道路1031张，室内道路790张。数据集中包含了不同清晰度、不同天气(晴朗、小雨、中雨、暴雨)拍摄的图像。

2.2 对比方法及评价指标

本文选取了3种在线匹配算法进行对比：

(1) 最短距离地图匹配方法[13](简称point-to-curve算法)。该算法只使用距离指标，将与采样点最近的路段作为匹配结果。

(2) 局部增量算法[26](简称Incremental算法)。该算法使用距离和角度差加权计算候选路段的相似度，采用一种前瞻规划算法计算沿所有候选路段前进k步之后的总相似度，从中选出相似度最高的作为匹配结果。

(3) 在线隐马尔可夫匹配法[18](简称OHMM算法)。隐马尔可夫模型被广泛应用于地图匹配算法中，该类算法核心是将每个采样点的备选路段作为整条轨迹中的一个状态，通过计算输出概率与相邻状态之间的转移概率，输出全局可能性最高的路径。

地图匹配领域常用匹配率[27]、召回率、精确率[28-29]作为评价指标。

其中，匹配率是指在所有匹配结果中，匹配正确的采样点数占总采样点数的比例，计算公式见式(8)。匹配率越高，说明错误匹配的点越少，匹配方法越有效。受GNSS定位精度影响，采样点在路段交点附近时较难判断车辆真实行驶的路段，本文采用以下标准判断采样点是否匹配正确：

(1) 对任一采样点p，经过匹配计算后当其匹配路段属于该轨迹真实路段集时，认为该采样点匹配正确。

(2) 对于OHMM、Incremental等采用滑动时间窗口的地图匹配算法，其匹配结果是一段匹配路段集，因此在对比这两种方法时，本文使用point-to-curve法将滑动时间窗口内的各采样点匹配到匹配路段集上，采用(1)指标判断该采样点匹配正确情况。

(8)

召回率和精确率计算公式分别为

(9)

(10)

召回率越高，匹配结果中真实路径的长度越长，算法对真实路径的重建效果越好，匹配结果中漏匹配路段越短；精确率则衡量算法匹配结果中误匹配的比例，精确率越高，匹配结果中误匹配的路段越短。

2.3 试验参数设置

在本文中，各计算过程使用的参数设置如下：

Incremental算法的参数为：μd=10,a=0.17,nd=1.4,μα=10,nα=3，其中除nα外均为原文推荐参数。

为了保证实现在线算法，OHMM算法中最大滑动窗口尺寸设置为5，并使用A*最短路径算法计算转移概率。

同时，为比较相关算法在不同采样频率下的匹配性能，本文逐步提高采样间隔至15秒，利用2.2节提出的指标对比各种相关算法。由于各算法均未开源，本文按照文献内的算法描述实现了相应算法。

使用开源机器学习库scikit-learn[30]训练行驶场景SVM分类模型，其中核函数使用多项式核函数(poly核函数)，为了计算各分类概率，probability参数设为True。使用行驶场景数据集60%的图像进行训练，其余图像进行测试。SVM模型训练和预测的速度受到特征维度的影响，为了加快速度，在试验中将原始大小为1920×1080像素的图像统一缩小为192×108像素并转换为8 bit灰度图像。本文使用SVM模型输出图像对应不同类别的概率，时间复杂度略高于仅输出分类结果，但通过试验其速度仍在可接受范围内。

2.4 试验结果与分析

2.4.1 行驶场景分类效果

利用行驶场景分类数据集中的训练集训练SVM模型，在测试集上进行测试，得到的五折交叉验证平均分类准确率为98.0%，测试集混淆矩阵与各类别召回率、精确率计算结果如下。

表2 行驶场景分类的混淆矩阵与召回率、精确率计算结果

2.4.2 不同方法的匹配结果对比

将本文方法与3种对比方法分别作用于3条轨迹，并对比在不同采样间隔下的试验结果(见图5和表3)。其中，实线代表本文方法，其余线型代表其他3种对比方法。横轴的采样间隔代表将原始的数据按不同的间隔(2～15 s)采样。

表3 4种算法匹配精度

图5 3段轨迹试验结果Fig.5 The experiment result of all trajectories

在原始采样间隔1 s的情况下，本文算法匹配率达96.68%，召回率达99.47%，精确率达到90.59%，表明在实时匹配的情况下，本文算法可以保证较高匹配正确率，且能较完整地恢复行驶轨迹，漏匹配的现象不明显；匹配出的路段中，误匹配的情况较少。

随着采样间隔的增加，采样点之间的距离增大，本文算法的匹配率与精确率受到的影响较小(匹配率从96.68%至97.17%，精确率从90.59%至95.04%)，召回率有所下降(从99.47%至90.86%)，这是因为本文算法只获取与采样点对应的匹配路段，随着采样点之间的距离增大，可能会出现跳过某些中间路段的情况[31]，因此召回率会有所下降。

在轨迹2中，本文算法在召回率这一指标上弱于OHMM算法。召回率表示正确匹配路段长度占整个轨迹所有路段长度的比例，由于本文算法仅针对单点进行匹配，当时间间隔增大时，本文算法会跳过部分路段，因为这些路段上没有对应的采样点。而OHMM使用隐马尔可夫模型，基于路网拓扑计算转移概率从而恢复车辆途经的路段，匹配结果连续性更强但可能出现“绕路”的现象，漏匹配较少而错匹配较多，因此OHMM表现出召回率较高而精确率低的特点。

本文方法与其他3种算法的匹配精度都会随着采样间隔的增大而受到影响，但本文算法在采样间隔增大后，仍保持较高水平。表3为4种算法在3条轨迹1～15 s采样间隔的平均精度统计结果。本文算法在1～15 s的采样间隔下平均匹配率为96.86%，平均召回率为97.17%，在4种算法中平均匹配精度最高。

2.4.3 不同算法在复杂路段的比较

在传统算法中，高架的上下匝道与立交等复杂区域是容易匹配错误的地方，因此，选择轨迹1与轨迹2中经过的复杂区域进行对比，如图6、图7所示。

图6 采样间隔为2 s情况下4种算法在复杂路口的匹配表现Fig.6 The matching performance of the four algorithms with overpass (sampling interval=2 s)

在复杂路口与高架道路区域，本文算法能够较好区分高架道路与平行地面道路，从而在复杂路口与高架道路区域实现较好匹配；而其他算法都有出现不同程度的误匹配与漏匹配现象。

2.4.4 不同算法的计算性能对比

对所使用的4种实时匹配算法进行了计算性能上的对比，采用单点匹配耗时、平均延时、内存消耗量等指标衡量不同算法的计算性能，结果见表4—表5。

在匹配效率方面，本文算法对每个采样点实时匹配，不存在匹配延迟现象，而OHMM与Incremental算法都有较大的延迟，延迟的长度与最大滑动窗口的尺寸以及采样频率有关。在单点匹配时间方面，由于DSCMM算法不涉及复杂的网络计算，匹配速度较快，单点匹配耗时小于100 ms，虽略慢于point-to-curve算法，但差异较小；DSCMM中的图像分类过程也未对匹配效率产生明显影响。

在内存占用量上，4种算法占用内存差异较小(表6)。OHMM算法由于在最短路径计算过程中涉及对图的存储与计算，需要占用更大的内存空间。由此可见，本文算法虽然引入图像进行地图匹配，内存占用并未明显增加，适合用于移动端开发。

图7 采样间隔为2 s情况下4种算法在高架道路区域的匹配表现Fig.7 The matching performance of the four algorithms with elevated road (sampling interval=2 s)

表4 1～15 s采样间隔下平均单点匹配耗时表

表5 1～15 s采样间隔下平均延时表

表6 内存占用量对比

3 结 论

地图匹配在自动驾驶、智能交通等领域应用广泛。传统的地图匹配算法在高架、立交等场景容易产生误匹配，从而对自动驾驶、智能交通造成影响。本文借助带有图像的轨迹数据，提出将图像提取的行驶场景类别信息加入地图匹配的技术思路，进一步提出采用行驶场景、距离、方向和邻接等四个指标，计算采样点与候选路段的匹配概率，从而获得最佳匹配结果。

从试验结果看，本文提出的DSCMM算法在1～15 s的采样间隔下都保持较好的匹配精度与匹配稳定性，整体性能优于现有的算法；同时算法计算耗时短，内存占用较少，适合在移动端实现在线计算。因此，本文算法在复杂城市路网(尤其是高架路网区域)能实现较好的在线匹配效果，在未来可以应用于实时车辆定位与实时轨迹追踪，为自动驾驶提供服务。

本文算法在高架匝道出入口处有时也会出现误匹配。这是由于本文算法引入的行驶场景尚未涵盖上下匝道场景，因此针对此类场景还需借助更多的图像样本完成场景识别。在本文算法实现的道路级地图匹配基础上，还可以进一步发掘序列图像的作用，通过识别前方车辆、单目测距实现交通路况监测。目前已有研究使用单目相机拍摄的行驶场景图像提取车道线，结合高精度地图进行车道级定位，本文算法可以与相关研究结合，提供更好的道路级定位基础。单目相机采集的图像存在一定的局限性，例如单向4、5车道的场景下由于视角有限边界车道线较难识别；前方车辆对车道线形成遮挡等。如何融合多传感器，提供快速准确、低成本、多场景适用的高精度匹配结果是未来的研究方向。

致谢：感谢弈人(上海)科技有限公司、弈人数据开放平台(1Rendata)为本文研究提供数据。