1.   引言

经典轨迹是对目标活动规律的总结生成的综合轨迹^[1]。将在线获取的实时轨迹与总结的经典轨迹进行比较，判断两轨迹是否相似，从而分析目标的行为意图或异常活动情况^[2]，是经典轨迹的重要任务之一。

轨迹间的比较主要通过轨迹之间的距离来表示。文献[3]利用相同时间的欧式距离，判断轨迹是否相关，该方法准确度较高，但该方法需要利用轨迹时间。文献[4]丢弃轨迹时间，增加轨迹位置顺序特征，提高轨迹识别率，但该方法需要大量样本进行训练。文献[5]不用轨迹时间，直接计算轨迹之间的欧氏距离。欧氏距离计算简单，但要求两轨迹必须有相同的长度。文献[6-8]分别采用动态时间弯曲距离、Frechet距离、Hausdorff距离，能够适应不同长度轨迹，但这些算法都要求轨迹不能有强噪声。文献[9]利用编辑距离来适应强噪声的处理，但编辑距离计算的轨迹相似区间是离散的，不易被直观理解。文献[10]利用最长公共子序列(Longest Common Subsequence, LCS)距离，用实验说明了LCS对强噪声的鲁棒性，但该文未考虑轨迹断裂、轨迹非等周期等情况。文献[11]引入线段与线段之间的欧氏距离，用LCS算法来计算轨迹相似度，用实验说明了该算法能够处理非等周期轨迹，但该文未考虑经典轨迹与实时轨迹的大差异性问题，即经典轨迹的多个点可能与实时轨迹的同一条线段匹配的“多对1”问题。本文针对该问题，将传统的“1对1”LCS算法改为“多对1”的LCS算法，将点与点之间的欧氏距离改为点与线段之间的欧氏距离，提出了一种鲁棒的相似度计算方法。

2.   最长公共子序列长度基础算法

LCS算法最早由Wagner等人^[12]提出，具有很好的抗干扰属性，在轨迹聚类、轨迹比较中得到了广泛的应用^[13]，其定义如下所示。

定义1：1对1最长公共子序列(one-to-one Longest Common Subsequence, 1-1LCS)。

设两序列${{{C}}_m} = ({c_1},{c_2}, ··· ,{c_m})$与${{{Q}}_n} = ({q_1},{q_2}, ··· ,$${q_n})$的公共子序列为${{{Z}}_r} = ({z_1},{z_2}, ··· ,{z_r})$，则${{{Z}}_r}$必须满足条件

${{{Z}}_r}$为两序列的1-1LCS，当且仅当${{{Z}}_r}$为满足式(1)条件中长度最长的序列。

根据最长公共子序列定义，文献[14]给出了如下的求最长公共子序列长度的算法。

设${{{C}}_i} = ({c_1},{c_2}, ··· ,{c_i})$为${{{C}}_m}$的子序列，${{{Q}}_j} = ({q_1},$${q_2}, ··· ,{q_j})$为${{ Q}_n}$的子序列，令${{L}}1(i,j)$表示序列${C_i}$与序列${Q_j}$的最长公共子序列长度，则${{L}}1(i,j)$由式(2)所示的1对1递推计算公式求出

式(2)为1对1最长公共子序列长度算法，${{L}}1(i,j)$计算的时空复杂度为$O(mn)$。

3.   改进的最长公共子序列长度算法

LCS基础算法中的最长公共子序列是1对1的最长公共子序列，即1个序列中至多只能有1个元素与另一个序列中的1个元素进行匹配，为了适应多对1情况，定义如下的多对1最长公共子序列。

定义2：多对1最长公共子序列(multi-to-one Longest Common Subsequence, m-1LCS)。

设两序列${{{C}}_m} = ({c_1},{c_2}, ··· ,{c_m})$与${{ Q}_n} = ({q_1}, ··· ,$${q_j}, ··· ,{q_n})$的多对1公共子序列为${{{Z}}_r} = ({{\rm{z}}_1},{z_2}, ··· ,{z_r})$，则${{{Z}}_r}$必须满足条件

${{{Z}}_r}$为两序列${{ C}_m}$与${{ Q}_n}$的m-1LCS，当且仅当${{{Z}}_r}$为满足式(3)条件中长度最长的序列。

根据多对1最长公共子序列定义，可推出如下的多对1最长公共子序列长度计算公式，其推导过程略。

设${{{C}}_i} = ({c_1},{c_2}, \cdots ,{c_i})$为${{{C}}_m}$的子序列，${{{Q}}_j} = ({q_1},$${q_2}, ··· ,{q_j})$为${{ Q}_n}$的子序列，令$L2(i,j)$表示序列${{ C}_i}$与序列${{ Q}_j}$的多对1最长公共子序列长度，则$L2(i,j)$由如式(4)所示的递推计算公式求出

式(4)为多对1最长公共子序列长度算法，$L2(i,j)$计算的时空复杂度为$O(mn)$。

4.   经典轨迹的相似度量算法

为了说明将点与点之间的欧氏距离改为点与线段之间的欧氏距离，将1-1LCS改为m-1LCS的必要性，特提出点到点1对1、点到点多对1、点到线1对1、点到线多对1共4种算法。

4.1   点到点1对1的轨迹相似度量算法

根据最长公共子序列定义，有如下的点到点1对1的最长公共子轨迹定义。

定义3：点到点1对1的最长公共子轨迹(Point-to-Point one-to-one Longest Common Subtrajectory, P2P1-1LCS)。

设经典轨迹${{ C}_m} = ({c_1}, ··· ,{c_i}, ··· ,{c_m})$与实时轨迹${{ Q}_n} = ({q_1}, ··· ,{q_j}, ··· ,{q_n})$的点到点1对1公共子轨迹为${{{Z}}_r} = ({z_1},{z_2}, ···,{z_r})$，则${{{Z}}_r}$必须满足条件

其中，$\varepsilon$为距离阈值，${\rm dis}({z_s},{q_{{v_s}}})$为两点${z_s}$与${q_{{v_s}}}$之间的欧式距离。

${{{Z}}_r}$为两轨迹${C_{{m}}}$与${Q_{{n}}}$的P2P1-1LCS，当且仅当${{{Z}}_r}$为满足式(5)条件中点数最多的轨迹。

根据P2P1-1LCS定义，有如下的P2P1-1LCS长度计算的递推公式^[15]。

令$\varepsilon > 0$为距离阈值，$L{1_\varepsilon }(m,n)$为经典轨迹${{ C}_m}$与实时轨迹${{ Q}_{\rm{n}}}$的P2P1-1LCS长度，则$L{1_\varepsilon }(m,n)$可由式(6)所示的递推公式求出

其中，计算$L1$的初始值为：对任意$i \ge 0$, $L{1_\varepsilon }(i,0) = 0$；对任意$j \ge 0$, $L{1_\varepsilon }(0,j) = 0$。

令$f1$为经典轨迹${{ C}_m}$与实时轨迹${{ Q}_{{n}}}$的点到点1对1的轨迹相似度，则$f1$可由式(7)求出

4.2   点到点多对1的轨迹相似度量算法

定义4：点到点多对1的最长公共子轨迹(Point-to-Point multi-to-one Longest Common Subtrajectory, P2Pm-1LCS)。

设经典轨迹${{ C}_m} = ({c_1}, ··· ,{c_i}, ··· ,{c_m})$与实时轨迹${{ Q}_n} = ({q_1}, ··· ,{q_j}, ··· ,{q_n})$的点到点多对1公共子轨迹为${{{Z}}_r} = ({z_1},{z_2}, ··· ,{z_r})$，则${{{Z}}_r}$必须满足条件

其中，$\varepsilon$为距离阈值。

${{{Z}}_r}$为两轨迹${{ C}_m}$与${{ Q}_n}$的P2Pm-1LCS，当且仅当${{{Z}}_r}$为满足式(8)条件中点数最多的轨迹。

根据P2Pm-1LCS定义，有如下的P2Pm-1LCS长度计算的递推公式，其推导过程略。

令$\varepsilon > 0$为距离阈值，令$L{2_\varepsilon }(m,n)$为经典轨迹${{ C}_m}$与实时轨迹${{ Q}_{{n}}}$的P2Pm-1LCS长度，则$L{2_\varepsilon } (m,n)$可由式(9)所示的递推公式求出

其中，计算$L2$的初始值为：$L{3_\varepsilon }(i,0) = 0$, $i \ge 0$; $L{3_\varepsilon }(0,j) = 0$, $j \ge 0$。

令$f2$为经典轨迹${C_m}$与实时轨迹${Q_n}$的点到点多对1的轨迹相似度，则$f2$可由式(10)所示的公式求出

4.3   点到线1对1的轨迹相似度量算法

定义5：点到线1对1的最长公共子轨迹(Point-to-Segment one-to-one Longest Common Subtrajectory, P2S1-1LCS)。

设经典轨迹${{ C}_m} = ({c_1}, ··· ,{c_i}, ···s ,{c_m})$与实时轨迹${{ Q}_n} = ({q_1}, ··· ,{q_j}, ··· ,{q_n})$的点到线1对1公共子轨迹为${{{Z}}_r} = ({z_1},{z_2}, ··· ,{z_r})$，则${{{Z}}_r}$必须满足条件

其中，$\varepsilon$为距离阈值，${\rm dis}({z_s},\overrightarrow {{q_{{v_s} - 1}}{q_{{v_s}}}} )$与${\rm dis}({z_s},$$\overrightarrow {{q_{{v_s}}}{q_{{v_s} + 1}}} )$为点到线段之间的欧式距离。

${{{Z}}_r}$为两轨迹${{ C}_{{m}}}$与${{ Q}_n}$的P2S1-1LCS，当且仅当${{{Z}}_r}$为满足式(11)条件中点数最多的轨迹。

根据P2S1-1LCS定义，有如下的P2S1-1LCS长度计算的递推公式，其推导过程略。

令$\varepsilon > 0$为距离阈值，$L{3_\varepsilon }(m,n)$为经典轨迹${{ C}_m}$与实时轨迹${{ Q}_n}$的P2S1-1LCS长度，则$L{3_\varepsilon }(m,n)$可由式(12)所示的递推公式求出

其中，计算$L3$的初始值为：$L{3_\varepsilon }(i,0) = 0$, $i \ge 0$; $L{3_\varepsilon }(0,j) = 0$, $j \ge 0$。

令$f3$为经典轨迹${C_m}$与实时轨迹${Q_n}$的点到线1对1的轨迹相似度，则$f3$可由式(13)所示的公式求出

4.4   点到线多对1的轨迹相似度量算法

定义6：点到线多对1的最长公共子轨迹(Point-to-Segment multi-to-one Longest Common Subtrajectory, P2Sm-1LCS)。

设经典轨迹${{ C}_m} = ({c_1}, ··· ,{c_i}, ··· ,{c_m})$与实时轨迹${{ Q}_n} = ({q_1}, ··· ,{q_j}, ··· ,{q_n})$的点到线多对1公共子轨迹为${{{Z}}_r} = ({z_1},{z_2}, ··· ,{z_r})$，则${{{Z}}_r}$必须满足条件

其中，$\varepsilon$为距离阈值，${\rm dis}({z_s},\overrightarrow {{q_{{v_s} - 1}}{q_{{v_s}}}} )$与${\rm dis}({z_s},$$\overrightarrow {{q_{{v_s}}}{q_{{v_s} + 1}}} )$为点到线段之间的欧式距离。

${{{Z}}_r}$为两轨迹${{ C}_m}$与${{ Q}_n}$的P2Sm-1LCS，当且仅当${{{Z}}_r}$为满足式(14)条件中点数最多的轨迹。

根据P2Sm-1LCS定义，有如下的P2Sm-1LCS长度计算的递推公式，其推导过程略。

令$\varepsilon > 0$为距离阈值，令$L{4_\varepsilon }(m,n)$为经典轨迹${C_m}$与实时轨迹${Q_n}$的P2Sm-1LCS长度，则$L{4_\varepsilon }(m,n)$可由式(15)所示的递推公式求出

其中，计算$L4$的初始值为：对任意$i \ge 0$, $L{4_\varepsilon }(i,0) = 0$；对任意$j \ge 0$, $L{4_\varepsilon }(0,j) = 0$。

令$f4$为经典轨迹${{ C}_m}$与实时轨迹${{ Q}_n}$的点到线多对1的轨迹相似度，则$f4$可由式(16)所示的公式求出

4.5   鲁棒的相似度量算法性质

设任意经典轨迹为${{ C}_m}$，实时轨迹为${{ Q}_n}$，令$\varepsilon > 0$为距离阈值，$f1$, $f2$, $f3$, $f4$分别为经典轨迹${{ C}_m}$与实时轨迹${{ Q}_n}$之间的点到点1对1轨迹相似度、点到点多对1轨迹相似度、点到线1对1轨迹相似度、点到线多对1轨迹相似度，则有如下性质成立：

(1) $f4 \ge \max \{ f3,f2,f1\}$, $f2 \ge f1$, $f3 \ge f1$。

(2) 当$\varepsilon \to \infty$时，有$f4 = f2 = 1$, $3 = f1 =$$\min \{ m,n\} /m$。

(3) 当${{ Q}_n}$=${{ C}_m}$时，有$f4 = f3 = f2 = f1 = 1$。

上述性质证明略。

5.   实验

为了检验该算法的鲁棒性，通过设计不同的距离门限、对数据进行不同的轨迹抽样删除及抽样扰动等不同情况，将点到线多对1轨迹相似度与其它3种算法(点到点1对1轨迹相似度^[16]、点到线1对1轨迹相似度、点到点多对1轨迹相似度)进行比较，说明算法的有效性。

5.1   试验数据

实验所用轨迹数据中包含6个经典目标的经典轨迹和实时轨迹。轨迹是按时间从小到大排列而成的有序的轨迹点集，轨迹点为2维坐标位置。6个目标的经典轨迹和实时轨迹长度分别为107和156, 114和107, 177和160, 162和169, 125和126, 145和149, 107和114。6个目标中的实时轨迹与经典轨迹之间的轨迹长度不同，轨迹起止点不同，轨迹相邻两点的间距不同，能有效检验算法的鲁棒性。

5.2   不同距离门限的轨迹相似度量试验

为了检验算法中距离门限对算法的影响，令$\varepsilon$从1000 m逐步递增到10000 m，统计各算法在选取不同的距离门限$\varepsilon$时的轨迹相似度。经过统计，6个目标的经典轨迹与实时轨迹之间的4种算法的轨迹相似度如图1所示。

图 1  不同距离门限的轨迹相似度量

下载: 全尺寸图片 幻灯片

从图1可以看出：距离门限$\varepsilon$从1000 m逐步递增到10000 m时，点到线多对1算法的轨迹相似度是4种算法中相似度最高的，点到点1对1算法的轨迹相似度都是4种算法中相似度最低的，这验证了4.5节性质(1)的正确性，同时也说明了点到线多对1算法对距离门限是鲁棒的。

5.3   实时轨迹抽样差异的试验结果分析

为了更深入地检验算法的鲁棒性，将6条实时轨迹进行等间隔抽样删除。设轨迹删除率$d$为轨迹中删除的轨迹点数$k$与轨迹删除前总点数$n$之比值，即轨迹删除率$d = k/n$。令距离门限$\varepsilon$=5000 m，分别计算删除后实时轨迹与经典轨迹的轨迹相似度。经过统计，6个目标的4种算法在不同抽样删除率下的轨迹相似度如图2所示。

图 2  不同轨迹删除率的轨迹相似度量

下载: 全尺寸图片 幻灯片

从图2可以看出：在轨迹删除率由0%增加到50%时，点到线1对1与点到点1对1的航迹相似度下降了30%以上；点到线多对1算法的轨迹相似度始终是最高的，且几乎不受轨迹删除的影响，这说明了点到线多对1算法对轨迹删除是鲁棒的。

5.4   实时轨迹增加位置扰动的试验结果分析

为了检验位置扰动对算法的影响，将6条实时轨迹进行等间隔抽样扰动。设轨迹扰动率$d$为轨迹中扰动点数$k$与轨迹总点数$n$之比值，即轨迹扰动率。令距离门限$\varepsilon$=5000 m，扰动的噪声大小$r$=20000 m，分别计算扰动后实时轨迹与经典轨迹的轨迹相似度。经过统计，6个目标4种算法在不同扰动率下的轨迹相似度如图3所示。

图 3  不同轨迹扰动率的轨迹相似度量

下载: 全尺寸图片 幻灯片

从图3可以看出:在轨迹扰动率由0%增加到50%时，点到线多对1算法、点到线1对1算法的轨迹相似度几乎不变，但点到线多对1算法始终是4种算法中相似度最高的，这说明了点到线多对1算法对轨迹扰动是鲁棒的。

6.   结束语

两轨迹的相似度量是很多应用中的关键技术，如轨迹相似度查询、轨迹识别、轨迹聚类、轨迹预测、轨迹行为分析、轨迹频繁模式挖掘等。目前大部分研究成果主要是用两轨迹点与点之间的欧氏距离，再用经典的最长公共子序列算法计算两轨迹的最长公共子轨迹长度或两轨迹的相似度。计算时，如果轨迹不同步，则会带来较大的计算误差。本文利用点到线段之间的欧氏距离替代传统的点与点之间的欧氏距离，再通过改进的多对1最长公共子序列算法替代传统的1对1最长公共子序列算法，使得经典轨迹的多个点可以与实时轨迹中的一个线段进行匹配，提高了轨迹的相似度量。在仿真实验中表明，本文的改进方法更适用于经典轨迹的相似轨迹的度量计算，本文计算的点到线多对1的轨迹相似度比文献[16]计算的点到点1对1的轨迹相似度高，同时也说明了点到线多对1的轨迹相似度对不同的距离门限、不同的轨迹删除情况、不同的轨迹扰动情况都是鲁棒的。

本文算法主要基于经典轨迹的与实时轨迹的大差异性，提出的点到线多对1相似度算法，提高了轨迹相似度。如果待比较的两轨迹都不完整，则可以将其中的点到线段的欧氏距离替换为线段到线段的欧氏距离，但耗时更多，故本文未采用线段到线段之间的欧氏距离。如果待比较的两轨迹都比较完整，则点到点多对1相似度与点到线多对1相似度接近，但耗时更少。下一步将计划研究如何在保持精度时提高算法效率，减少算法处理时间，这也是当前工程中急需研究的课题。