高精度地图已经成为实现无人驾驶和智能交通的重要一环^[1]，高精度地图的采集和成图也面临越来越大的挑战。目前使用最广泛的方法是对轨迹数据进行成图，其精度较高但采集设备价格高昂，车道轨迹数据量庞大，手工编辑任务繁重^[2]。城市道路中的双线道路通常形状相似、相互平行且保持固定的距离，结构特征明显^[3]。依据这些特征，可利用采集的轨迹数据自动生成车道，首先采集道路最右侧的车道中心线轨迹，然后利用轨迹相似性算法查找构成同一路段的两条轨迹，最后基于两轨迹之间的距离以及车道宽度或数目等附加信息推理出车道位置。此方法已成为高精地图自动成图方法之一。轨迹相似性计算与相似轨迹提取^[4-6]是该方法数据处理环节的关键步骤，只有找到构成同一路段的两条轨迹，才能顺利推断出剩余车道的位置。因此，相似轨迹提取对于高精地图的自动成图具有重要意义，其正确率极大地影响地图的精度。

随着全球定位系统（Global Positioning Sys- tem，GPS）的广泛应用，轨迹数据急剧增加，如何挖掘其中的有用信息已成为研究热点。轨迹相似性度量是轨迹聚类的重要手段^[7]，广泛应用于驾驶行为预测、群体路径偏好、路径预测等领域。轨迹相似性度量轨迹之间的相似程度^[8]，常用的方法包括欧氏距离^[9-10]、动态时间规划（dynamic time warping，DTW）^[11]、编辑距离（edit distance on real sequence，EDR）^[12]和最长公共子序列（longest common subsequence，LCSS）。欧氏距离局限于采样点数目相同的轨迹，易受噪声影响^[10]。DTW、EDR可适用于不同采样间隔和采样点数的轨迹，且对噪声鲁棒。这3类方法计算序列的整体相似性，对个别的差异点非常敏感，如果两序列存在小部分不相似的区间，则会认为整个序列不相似。LCSS可弥补这个缺陷。LC-SS最早被用于计算两个字符串的公共子序列。文献[13-14]将LCSS用于度量两个序列的相似性，适用于点数不同和具有强噪声的轨迹^[15]。

传统LCSS算法多是针对移动对象经过同一路径的重叠轨迹，这些轨迹是同步的。文献[14]将轨迹相似问题转化为LCSS问题，但没有处理轨迹不同步的情形。文献[16]利用LCSS提取大量车辆轨迹之间的相似子轨迹，文献[17]计算了LCSS相似度时结合时间和地理因素，并在此基础上分析移动用户轨迹的相似性。

本文研究对象是道路最右侧的车道中心线轨迹，如图 1所示，两轨迹在垂直轨迹方向存在横向距离差（d₁），在沿轨迹方向存在纵向距离差（d₂），因此是不同步的。传统LCSS方法不适合直接计算其相似度，为使轨迹同步，需减小这些距离差的影响，因此本文先对轨迹进行对齐操作。与本文数据相似的是双线道路，在城市双线道路提取方面，文献[18]利用Hausdorff距离（Hausdorff dis- tance，HD）筛选候选线对，但HD对顶点分布不均、局部形变较大的情况非常敏感^[19]。文献[3]提出一种新的距离度量方法，即正对投影距离（project distance，PD），该距离的实质是点到线的距离，其比HD更稳定，识别双线道路的正确率也更高，但仅局限于提取固定宽度的道路。

本文提出一种改进的LCSS轨迹相似性算法，首先构建缓冲区提取可能形成相似轨迹的候选轨迹对；然后对轨迹对进行对齐操作，将两条轨迹投影至同一主方向并垂直于主方向平移，再对轨迹进行三次样条拟合并计算沿法线的重采样点；最后基于LCSS计算轨迹的相似性，实现相似轨迹提取。

1 算法总体框架

本文算法的流程图如图 2所示。主要包括构建候选轨迹集合、轨迹对齐以及基于LCSS的轨迹相似性计算3个步骤。输入的车辆轨迹数据是已经去除路口轨迹点和异常点的分段轨迹数据。轨迹对齐包括将两条轨迹投影至同一主方向并垂直于主方向进行平移，以及对轨迹进行三次样条拟合并沿航向的垂直方向进行重采样两个步骤。

2 轨迹对齐策略 2.1 基于主方向的轨迹平移

为获取平移方向及距离，用一条直线来近似表达轨迹。考虑到主成分分析（principal compo- nent analysis，PCA）方法可将数据投影至该数据集的主特征方向上，本文采用PCA计算轨迹的主方向，将轨迹用一条沿主方向的直线表示。为找到最佳直线，本文作出如下定义。

定义1  直线过点：点到直线的距离小于阈值δ。

定义2  最佳参考直线：方向为轨迹主方向且经过轨迹上最多点的直线。

定义3  最佳点：最佳参考直线经过的所有轨迹点的重心。

求得最佳点到最佳参考直线的投影点，将轨迹沿投影点方向平移。现实中的轨迹一般分为直线轨迹（图 3（a））和曲线轨迹（图 3（b）），两种轨迹寻找最佳直线和最佳点的方法相同，轨迹平移的计算方法也相同。图 3中，L₁和L₂是同一路段两条轨迹，l₁、l₂分别是L₁、L₂的最佳参考直线，两直线均以L₁的主方向k₁为斜率，Q₁ (x₁，y₁)、Q₂ (x₂，y₂)分别为L₁、L₂的最佳点，Q₂到l₁的投影点Q₂' ( x₂'，y₂')的计算式如下：

$ \left\{ \begin{array}{l} {x_2}' = \left( {{k_1}\left( {{y_2} - {y_1}} \right) + {k_1}^2{x_1} + {x_2}} \right)/\left( {{k_1}^2 + 1} \right)\\ {y_2}'{\rm{ = }}\left( {{k_1}\left( {{x_2} - {x_1}} \right) + {k_1}^2{y_2} + {y_1}} \right)/\left( {{k_1}^2 + 1} \right) \end{array} \right. $

(1)

取$ \overrightarrow {{Q_2}{Q_2}'} $为平移方向，$ \left| {\overrightarrow {{Q_2}{Q_2}'} } \right|$为平移距离，其计算式为：

$ \left| {\overrightarrow {{Q_2}{Q_2}'} } \right| = \sqrt {{{\left( {{x_2}' - {x_2}} \right)}^2} + {{\left( {{y_2}' - {y_2}} \right)}^2}} $

(2)

2.2 轨迹重采样

对轨迹进行重采样，需定义轨迹的数据模型。本文轨迹受道路交通网络约束，表示真实的道路形状，为尽量保留轨迹的特征信息，采用三次样条曲线模型。轨迹点包含车辆航向信息，车辆航向与道路方向基本一致，基于航向的法线方向对轨迹进行重采样，使两条轨迹对齐。

如图 3所示，P₁是轨迹L₁上一轨迹点，其航向为α₁，蓝色虚线F₂是轨迹L₂的三次样条拟合曲线，过点P₁作α₁的垂线，其与F₂的交点P₁ '即为轨迹L₂的重采样点。

2.3 轨迹对齐具体步骤

轨迹对齐步骤如图 4所示。

1）任选一条轨迹L_i作为参考轨迹，选择其候选轨迹集中的轨迹L_j作为候选轨迹，计算_i、L_j的最佳参考直线l_i、l_j及_j的最佳点Q_j；

2）计算最佳点Q_j到直线l_i的投影点Q_j '，取$ \left| {\overrightarrow {{Q_2}{Q_2}'} } \right|$为投影距离t；

3）将轨迹L_j沿$ \overrightarrow {{Q_2}{Q_2}'} $方向平移距离t；

4）对平移后的轨迹L_j进行三次样条拟合，得到拟合曲线F_j；

5）对轨迹L_i上的每个轨迹点P_i，沿其航向α₁的垂直方向对F_j进行重采样；

6）得到对齐后的轨迹L_j'。

3 基于改进LCSS的相似轨迹提取 3.1 构建候选轨迹集合

同一路段的两条轨迹在空间上具有邻近性，通过建立缓冲区，从大量轨迹数据中筛选出可能相似的候选轨迹集，能够有效缩小匹配范围，减少候选轨迹数量，提高计算效率。

对任一轨迹建立缓冲区，将位于缓冲区内的轨迹作为该轨迹的候选轨迹。为尽可能包含所有可能与该轨迹相似的轨迹，缓冲区半径应设置较大的阈值。

3.2 基于改进LCSS的轨迹相似性计算

对于两条点数分别为n和m的轨迹R和S，用点集合表示为R = { r₁，r₂…r_n}和S = { s₁，s₂…s_m}，则其最长公共子序列的长度为^[20]：

$ {\rm{LCSS}}(R, S) = \\ \left\{ \begin{array}{l} 0, 当n = 0或m = 0时\\ 1{\rm{ }} + {\rm{ LCSS}}({r_{i - 1}}, {s_{j - 1}}), 若{\rm{dist }}({r_i}, {s_j}){\rm{ }} ＜\varepsilon \\ {\rm{max }}({\rm{ LCSS}}({r_{i - 1}}, {s_j}), {\rm{LCSS}}({r_i}, {s_{j - 1}}){\rm{ }}), 其他 \end{array} \right. $

(3)

式中，i = 1，2…n；j = 1，2…m；ε表示衡量轨迹点对之间相似程度的阈值。

本文采用欧氏距离衡量两个点之间的相似程度，对于两个点r_i(x_i，y_i)、s_j(x_j，y_j)，其欧氏距离计算公式如下：

$ {\rm{dist }}({r_i}, {s_j}) = {\rm{ }}\sqrt {{{({x_i} - {x_j})}^2} + {{({y_i} - {y_j})}^2}} $

(4)

若dist (r_i，s_j) ≤ ε，则认为两个点相似。最长公共子序列LCSS(R，S)代表两条轨迹中判定为相似点对的对数，LCSS(R，S)与整条轨迹总点数的比值越大，两条轨迹的相似程度越高。因此，本文定义轨迹相似度如下：

$ {\rm{SD }}(R, S) = {\rm{ LCSS}}(R, S){\rm{ }}/{\rm{ min }}(n, m) $

(5)

式中，min (n，m)表示两条轨迹总点数的较小值；SD (R，S)的取值为[0, 1]，0表示两条轨迹完全不相似，1表示两条轨迹完全重合。本文中，当SD大于某个阈值γ时，两条轨迹相似。

4 实验与分析 4.1 数据采集

本文实验数据由武汉大学自动驾驶车“途友号”（图 5）采集，该车采用Novatel SPAN-FSAS惯性组合导航系统作为定位系统，定位精度为厘米级。驾驶车辆沿最右侧车道的中心线行驶，控制车速在20 km/h左右，采集频率为100 Hz。对采集的数据进行检核，剔除跳点及路口轨迹点并进行抽稀之后，最终获取精度在5 cm范围内的车道中心线轨迹数据（图 6）。

实验测区总面积达20 km²，实验数据总长82.7 km，共7 515个点，包含97个路段，共194条轨迹。受定位误差及动态干扰影响，采集的同一路段的两条轨迹可能不相似。经统计，194条轨迹中相似轨迹为178条，不相似轨迹为16条。本文算法用MATLAB软件实现，程序运行环境为Windows 10操作系统，计算机中央处理器为主频3.6 GHz的i7处理器，内存8 GB。

4.2 阈值分析

缓冲区半径 r影响候选轨迹的完整性，r过小可能造成候选轨迹漏检，过大则影响计算效率。通过对整个测区进行测量分析，可知同一路段两条轨迹之间距离最大为45 m。经过微调，本文将r设为50 m^[18]。

直线过点的距离阈值δ会影响轨迹表达成直线的准确性。判断点对是否相似的距离阈值ε影响相似轨迹提取的正确率，ε过大会将不相似轨迹误判为相似，过小则会造成漏检。衡量两条轨迹是否相似的相似度阈值 γ也会影响相似轨迹的识别结果，γ过大可能造成漏检，过小则会误检。

为分析阈值δ、ε、γ对提取效果的影响，本文进行多次实验，采用正确率和查全率对提取结果进行评价^[20]，统计结果如图 7所示。

由图 7可知，在γ取不同值下，当δ固定不变时，随着ε的增大，正确率逐渐降低，查全率逐渐升高，二者变化均较缓慢，当δ=1 m、ε=4.5 m时，查全率更是达到了100%，继续增大ε，查全率不会增大，正确率反而会降低。当ε一定时，正确率和查全率变化均不明显，大体上呈缓慢增大趋势，且正确率均比较高，说明当δ在[0.1，1.5]范围取值时，均能取得较好的效果。

为综合考虑正确率和查全率，采用F1-mea-sure来选择阈值，其计算式如下：

$ F1{\rm{ }} = {\rm{ }}\frac{{2{\rm{ }} \times {\rm{ Precision }} \times {\rm{ Recall}}}}{{{\rm{Precision }} + {\rm{ Recall}}}} $

(6)

式中，F1表示F1-measure；Precision和Recall分别表示正确率和查全率。分别计算γ取0.85、0.9、0.95时的F1值，根据统计结果绘制如图 8所示的柱状图。本文选择δ=1 m、ε=3.5 m、γ=0.9作为最终的阈值。

4.3 实验对比分析

为验证本文算法的有效性和合理性，将文献[3]中的正对投影距离度量方法与本文算法进行对比，参数阈值采用§4.2确定的最终阈值，相似轨迹提取的结果统计见表 1。

由表 1可知，文献[3]方法查全率为100%，即该方法将所有相似轨迹都提取出来，提取效果较好。与该方法相比，本文方法查全率较低，正确率较高，说明提取出的轨迹中相似轨迹占的比重较高。作为高精度地图成图的步骤之一，相似轨迹提取需要在保证正确率的同时提高查全率，因此，采用本文方法进行相似轨迹提取能达到较好的效果。

正对投影距离本质上是点到线的距离，因此线要素的顶点分布不均匀、局部形变等因素可能影响距离的度量结果，且该方法局限于提取固定路宽的双线道路。而本文利用LCSS计算两条轨迹的相似度，其核心是寻找两条轨迹的最长公共子序列，对强噪声具有很好的鲁棒性，同时能够提取任意宽度的轨迹。文献[3]计算了两条线要素之间的正对投影距离并构建距离一致性参数，若小于阈值，则认为这两条线要素相似。该方法对于本身不相似的轨迹容易造成误提取。如图 9所示的两条轨迹是不相似的，而正对投影距离方法将其错误识别为相似，本文方法则认为其不相似。

5 结语

轨迹相似性计算及相似轨迹提取是车道位置自动推算的一个重要步骤，本文根据采集轨迹的结构特征，提出一种改进的LCSS相似轨迹提取方法。针对传统LCSS多用于重叠轨迹的问题，在计算相似度之前，先通过平移和重采样使两条轨迹对齐。本文采用真实轨迹数据对该方法进行了评估，结果表明，采用本文方法进行相似轨迹提取能取得较高的正确率。

通过采集最外侧车道中心线轨迹，利用轨迹相似性推算车道的位置，对高精度地图成图的自动化具有重要意义。然而，车辆定位不可避免地会有误差^[21]，轨迹数据不一定表示真实的道路形状。同时，城市道路也存在车道数增多的情况，不一定完全平行。因此未来还需要进行更加深入的研究。本方法阈值较多，如何快速确定最佳阈值也是需进一步研究的问题。