基于改进Frechet距离的海上目标航迹相似性度量方法

刘敬一，郭 琦，陈金勇，楚博策

(中国电子科技集团公司第五十四研究所，河北 石家庄 050081)

0 引言

随着船舶自动识别系统(Automatic Identification System，AIS)的不断发展，大量的船舶航行轨迹被记录并保存下来。船舶航行轨迹蕴含着丰富的船舶行为模式特征以及交通航行规律，可以为船舶目标行为预测、异常检测和航路规划等诸多应用提供支撑，具有十分重要的现实意义和经济价值[1]。

运动目标轨迹相似性度量作为目标行为规律分析的基础，是轨迹挖掘分析中的研究重点之一。相对于陆地移动目标轨迹相似性度量方法较为成熟的发展，船舶等海上移动目标轨迹的相似性度量研究较少，主要有以下两方面原因：① 船舶运动受到岛礁分布、洋流流向和作业内容等特殊条件约束；② 相对于陆地运动目标轨迹的较小时空跨度，船舶的运动轨迹一般是长时间跨度、大空间范围。因此，面向船舶等海上目标移动轨迹相似性度量，需要综合考虑船舶的行为模式和运动特征，以及AIS数据的数据特点，建立一种适用于船舶等海上运动目标的轨迹相似性度量方法。

现有针对移动目标轨迹相似性的度量方法可以划分为：① 基于深度学习的轨迹相似性度量；② 基于轨迹空间分布特征的相似性度量。

基于深度学习的轨迹相似性度量是利用深度表征学习等技术对移动轨迹的特征进行抽象，并在此基础上进行轨迹相似性的衡量。 Li等[2]、Abdalla等[3]和Yao等[4]许多国外学者以及陈垣毅等[5]、王新瑞等[6]许多国内学者在此方面都取得了较好的研究成果。深度学习技术在许多轨迹相似性度量中取得了超过传统方法的表现，但此类方法严重依赖于数据的质量和规模，在数据量不足或质量较差时模型效果难以保证。

基于轨迹时空分布特征的相似性度量根据关注对象的不同，可以将此类方法进一步划分为基于航迹点的相似性分析以及基于航迹段的相似性分析，其中，基于轨迹点的相似性度量主流的方法有Hausdorff距离[7]、Frechet距离[8]、最大/最小欧氏距离[9]、DTW[10]、LCSS[11]和ERP[12]等；基于轨迹段的相似性度量方法将轨迹段作为分析的基本单元，通过分析轨迹段之间的相似性来实现对航迹整体相似性的度量[13-20]。此类方法多数采用地理空间距离阈值来衡量轨迹间相似性，在特定应用背景下需要融合相关专家知识进行阈值确定，使得轨迹相似性度量受到人为干扰因素较大。

综上分析，现有轨迹相似性度量方法并没有一种可适用于所有应用背景下的各种情况，而面向船舶等海上移动目标，现有研究多是直接采用陆地目标轨迹相似性衡量方法[16-17]，忽略了海上移动目标的特殊约束条件以及运动特性。基于此，本文通过分析船舶运动特征，在考虑运动约束、时空跨度以及定位误差的情况下，提出了基于改进Frechet距离的海上目标航迹相似性度量方法，实现船舶航迹相似性度量在不同空间尺度及噪声影响下的航迹相似性度量。

1 基于改进Frechet距离航迹相似性度量方法

Frechet距离在考虑时间顺序的情况下，通过最小化2段航迹上航迹点之间的最大距离来衡量二者的相似程度[7]。Frechet距离示意如图1所示，以船舶为例，船A和船B分别在各自航迹上自起点至终点单向航行，航行过程中两船均可以暂时停下但是不可以后退，在最优航行方式下从起点到终点两船之间距离的最大值即为Frechet距离。

Frechet距离可评价处理连续曲线的相似性程度，但是仍然存在变尺度下距离阈值难确定以及噪声敏感的问题。出于对上述问题的考虑，本文提出了基于改进离散Frechet距离的海上目标航迹相似度分析方法，通过定义相对Frechet距离和点相似系数实现了对海上目标航迹相似度的准确度量。以下对方法多包涵的各部分进行详细介绍。

图1 Frechet距离示意Fig.1 Diagram of the Frechet distance

1.1 数据预处理

(a) 相同空间颗粒度情况

(b) 不同空间颗粒度情况图2 不同空间颗粒度对Frechet距离的影响Fig.2 Influence of different spatial granularity on Frechet distance

为达此目的，需要预先设定海上目标最小航行vmin和最短采样时间tmin，由此确定插值的空间颗粒度为：

lmin=vmin×tmin。

(1)

1.2 相对Frechet距离

针对航迹预处理得到的2条航迹L′1和L′2，首先计算Frechet距离及相应的距离跟踪矩阵DF。

(2)

基于此，定义相对Frechet距离df，为Frechet距离dF与2条航迹长度l1和l2平均值的比值：

(3)

相对Frechet距离利用2条航迹的相对距离衡量相似性，因此其不受航迹空间尺度大小的影响。在面向不同空间尺寸的航迹时有较好的稳定性，可以更加准确地衡量2条航迹的相似程度，相对距离越大，表明2条航迹之间的空间距离相较于其自身长度而言越大，2条航迹的相似性越低；反之，表明2条航迹之间的相似性越高。

1.3 点相似系数

为了降低噪声信号的影响，充分借鉴最长公共子序列(LCSS)等算法中的思想，以离散化的方式度量航迹点之间的距离，定义相对距离小于阈值的点为相似点，大于等于阈值的点为非相似点。点相似系数cpp定义为最优匹配结果下，相似点数量占总点数的比例。cpp越大，表明2条航迹中相似点所占比例越高，2条航迹的相似度越高；反之，2条航迹之间的相似度越低。通过点相似系数cpp实现了两航迹之间距离的离散化度量。具体实现如下：

① 基于距离跟踪矩阵DF，抽取最优情况下2条航迹中航迹点的对应关系，得到匹配点对序列Lp：

1≤i1≤i2≤…≤M′,1≤j1≤j2≤…≤N′。

② 进而由Lp得到匹配点对相对距离序列Ld，其中x即为Ld的长度：

Ld=[d1,d2,d3,…,dx]，x=max(M′,N′),

(4)

式中，相对距离d定义为2个经纬度之间的地理空间距离dist(p1,p2)与2条航迹长度l1和l2平均值的比值：

(5)

③ 根据预先设定的点相对距离阈值ε以及d计算点相似系数cpp：

(6)

1.4 基于改进Frechet距离的海上目标航迹相似性系数

点相似系数cpp从航迹内部，即组成2条航迹的各个坐标点之间，刻画2条航迹的相似程度，相对Frechet距离df从航迹外部，即从2条航迹整体的走向和距离上，度量2条航迹的相似程度，在最优匹配的情况下，所有匹配点对之间的相对距离均在df之内，df越小，表明2条航迹之间的接近程度越高。本文利用相对Frechet距离df和相似系数cpp，给出基于改进Frechet距离的海上目标航迹相似性系数(Trajectory Similarity Coefficient of Sea Target Based on Frechet Distance，TSCF)，计算如下：

ρTSCF=αcpp+βdf，

(7)

式中，α，β为比例系数。为统一相对Frechet距离df和相似系数cpp与相关性强弱之间的变化关系，一般β为负值。

由上述分析可知，ρTSCF可以兼顾整体相似性和局部相似性，实现对2条航迹相似程度的准确度量，同时大幅增加算法在面向变尺度航迹及强噪声航迹情况下航迹相似性指标的稳定性。

2 实例验证与对比分析

为了验证TSCF衡量航迹相似程度的有效性，首先分析了其在不同空间尺度航迹以及不同强弱噪声影响下的表现，借助已有专家知识对算法效果进行评估。其次，将TSCF与传统Frechet距离、LCSS和DTW等进行对比，以算法在各种不同类型航迹下相似度指标变化情况为衡量标准。

2.1 实验数据介绍

实验数据选取了美国国家海洋和大气局公布的2019年1月1日—1月15日美国近海及公海范围内的AIS数据(https:∥coast.noaa.gov/htdata/CMSP/AISDataHandler/2019/index.html)，该数据中包含大量海上船舶航行记录，但是缺乏大空间尺度航迹。因此，在AIS数据基础上基于真实航迹数据特征通过数据仿真的方式进行实验数据扩充。

首先结合港口位置信息从上述数据集中提取标准航迹数据(标准航迹指船只从某一港口出发后返回或者到达另一港口所产生的航迹，剔除拖网捕鱼等海上作业过程)。按照航迹长度将提取的航迹划分为6组，如表1所示，用于验证算法对于不同空间尺度航迹的应用效果；其次，从众多航迹中选取若干包含噪声较小的参照航迹对，通过在其中加入不同强度的噪声信号，生成5个实验组，如表2所示，用于验证算法在不同强度噪声干扰下的表现。

表1 不同空间尺度实验航迹数据分组情况

表2 不同噪声实验航迹数据分组情况

2.2 方法验证

基于上述实验航迹数据集，对TSCF从不同空间尺度和抗噪性方面进行综合评价。本文结合已有专家知识对“相似航迹”进行如下定义：① 二者的出发港口和到达港口相同；② 二者走向一致，若航迹存在明显转向，则二者转向位置接近；③ 二者航行路径相同，即在因岛屿或其他地理因素的影响下存在多条航行路径时，二者选择的航行路径一致。按照上述定义对相似性度量方法在不同情况下的分析结果进行评估和对比分析。

首先，评估TSCF在不同空间尺度条件下对航迹数据相似性度量的效果。按照实验航迹数据集合的第1种划分方法，分别从各组中随机抽取20%航迹，分别计算其与样本集中各个航迹的相似系数，在各组相似性阈值均取0.8的情况下得到相应的相似性分析结果，TSCF在各个空间尺度下的表现如表3所示，表中TP为相似航迹分析结果中正确的数量；FP为相似航迹分析结果中错误的数量；FN为相似航迹中被预测错误的数量；Precision为分类精确率，表示航迹分析结果中正确结果所占的比例；Recall为分类召回率，表示所有相似航迹中被有效检出的比例。由表3可以看出，各组在使用相同阈值0.8的情况下，相似性分析结果相近，总体精确率为79.70%，召回率为100%。表明TSCF在不同空间尺度下均能够取得良好的相似性分析结果。

表3 不同空间尺度下航迹相似性度量效果

为了验证TSCF在不同噪声情况下的稳定性，选取10对不同空间尺度、不同几何特征的航迹，分别在其中加入不同程度的噪声信号并多次计算求平均值作为计算结果，以不同噪声下结果的均方差为评价指标判断该指标在噪声信号下的表现，结果如表4所示。由表4可以看出，对同一对航迹，不同强度噪声信号的加入并未对航迹相似性评价指标产生较大影响，各组均方差均极小，表明TSCF对噪声信号具有一定的鲁棒性。

表4 不同噪声情况下航迹相似性度量效果

2.3 方法对比分析

为了进一步验证TSCF的有效性，对比传统Frechet距离、LCSS算法和DTW算法，以各个算法在不同实验组之间航迹相似度评价指标的变化程度为衡量标准，比较算法在多种情况下的稳定性与有效性。借助专家知识从每个实验组中重新抽取5对相似航迹，分别计算各个相似性度量指标，对每个指标的5个计算结果取平均值作为最终结果，如表5所示。

表5 不同空间尺度情况下航迹相似性度量效果

由表5可以看出，TSCF在不同实验组中的计算结果相近，具有较高的稳定性和准确性,能够较为准确地描述2条航迹之间的相似关系。而传统Frechet距离、DTW算法则完全依赖于绝对距离的计算，不同空间尺度的航迹之间计算结果差距巨大，无法通过设定统一的阈值来实现相似性判断；LCSS算法通过将距离二值化在一定程度上避免了上述问题，但是由于距离二值化过程中仍然存在无法设定统一阈值的问题，所以该算法在不同实验组中的表现仍然存在较大差距。

3 结束语

本文基于船舶运动特征，在考虑运动约束、时空跨度以及定位误差的情况下，提出了基于改进Frechet距离的海上目标航迹相似性度量方法，通过定义相对Frechet距离和点相似系数，实现了对于海上目标航迹相似度的准确度量。通过实验验证基于经典相似性度量方法的对比得出，本文所提出的基于改进Frechet距离的海上目标航迹相似性度量方法具有较好的空间尺度不变性与噪声鲁棒性，在不同噪声以及空间尺度下均有着较为稳定的表现，在分析海上目标运动轨迹的问题中，相较于以往的轨迹相似性分析方法，能够较为准确地刻画2条航迹的相似程度。本文提出的航迹相似性度量方法主要考虑了航迹的空间分布特征，并未利用航向、航速和时序信号等其他维度的特征，在后续的工作中可以将此类信息加入到航迹特征描述中，进一步提升了航迹相似性描述的准确性。