0 引　言

国际海事组织（IMO）要求300吨以上的船舶必须安装船舶自动识别系统（Automatic Identification System，AIS）^[1]。AIS在船舶航行状态监控、航路规划以及海上事故搜救等领域应用广泛，随着大数据技术的快速发展，AIS的重要性日益凸显。然而，伴随而来的海量数据也带来了数据冗余的问题，极大地增加了数据存储的难度，这对AIS数据的分析、处理和存储技术提出了更高要求^[2]。

针对AIS数据的简化与压缩处理，国内外学者已有诸多研究，最流行的是以DP算法为代表的自上而下型压缩算法，经典的DP算法在运行效率上表现优异，能够较好地表征船舶轨迹的整体形状，然而，该算法在捕捉船舶轨迹时空特性（如航速和航向）方面存在不足，且在处理复杂轨迹时效果不理想。如图1所示，在二维平面上弯曲度变化较小的轨迹段可能航速变化较大，DP算法只考虑了点之间的距离，并没有考虑具体时间和速度信息，并且DP算法对于局部轨迹的形状细节处理较差。

在船舶AIS轨迹压缩领域，如何在保证压缩效率的同时保留更多的轨迹运动特征一直是研究的核心问题。现有研究主要集中在时间特征提取、空间特征保留和时空特征相结合等方向，各种方法在提升特征保留能力的同时也面临运算量增加的挑战。

在船舶运动时间特征提取方面，相关研究大多针对时间与航速进行分析。徐凯等^[3]提出的离线压缩算法引入了时间维度，相较于动态DP算法具有更快的运行速度，能够更好地保留船舶的速度与加速度变化特征，但由于三维向量自身的限制，并未直接利用AIS数据中的航速与航向信息；Yan等^[1]基于航速信息设计了轨迹噪声检测与校正算法，并提出了2种适用于不同压缩任务的算法，然而在海岸线附近的压缩性能有所下降；Gao等^[4]提出一种基于船舶航行状态和加速度变化的航迹数据压缩算法，能够更好地保留船舶轨迹的航速变化信息，缺点是需要手动设定压缩阈值。以上算法主要侧重对船舶轨迹进行运动状态分析，对压缩阈值和轨迹局部细节缺乏深入研究。

在优化轨迹空间特征保留方面，相关研究更关注轨迹弯曲部分形状特征的保留。Zhao等^[5]提出一种改进的DP压缩算法，通过区分轨迹形状并简化直线路径的压缩过程，在运行效率和轨迹特征保留上表现优异，但该算法未考虑航速信息，导致运动特征保留能力有限；Tang等^[6]提出的自适应阈值DP算法克服了传统算法中基于经验阈值选择的缺陷，显著改善了压缩质量，同时在压缩率和运行时间上较DP算法和滑动窗口算法更具优势，但其对速度变化缺乏分析，仍存在优化空间；Lee等^[7]提出一种考虑地形信息的AIS轨迹压缩算法，能够有效地避免压缩后轨迹与障碍物相交，未来的优化研究侧重于引入船舶的航速与航向信息；段浩然等^[8]设计了自适应阈值渔船轨迹压缩方法，避免了滑动窗口算法导致轨迹不完整的风险，但航速和航向变化对轨迹特征的影响未被充分考虑；刘奕等^[9]设计的自适应压缩算法，通过为直线和转弯轨迹采用不同的阈值进行压缩，能够在提高压缩率的同时保留重要的特征点，然而，该算法对航速变化缺乏考量，限制了其适用范围。上述算法针对轨迹弯曲特征进行自适应压缩，避免了经验阈值引起的压缩错误问题，但大多未能在形状特征保留的同时兼顾船舶运动的时间特征。

在时空特征相结合方面，宋鑫等^[2]采用分阶段与全局优化结合的方法，通过对轨迹进行分段处理并动态更新阈值，提升了压缩精度，但该算法需要对多个指标（如航速、航向等）设定阈值，若阈值选择不当，运行结果可能受较大影响；Wei等^[10]提出的算法兼顾了轨迹运动与空间特征，但无法自适应调整阈值，且压缩时间较长；刘畅等^[11]提出一种考虑航速和航向的典型轨迹提取算法，利用航速和航向特征点筛选保留了运动特征，同时具备较高的运行效率。然而，该算法对轨迹局部形状细节的处理和阈值选择缺乏深入分析；刘海砚等^[12]结合DP算法和滑动窗算法设计了一种时空与语义结合的轨迹压缩方法，能够较好保留轨迹的运动特征，但算法缺乏自适应压缩功能，在处理轨迹弯曲程度较大时计算量较高；Guo等^[13]基于DP算法设计了一种自上而下的自适应压缩算法，该算法充分考虑了船舶轨迹的航速、航向、时间与位置信息，但随着数据量增大压缩时间相较于其他算法明显增多。时空特征结合的算法与模型大多较为复杂，虽然能够较好地保留轨迹的时间与空间特征，但会大大增加处理数据时的运算量，面临庞大数据时需要较大的运算成本。

针对以上问题，基于DP算法，提出一种考虑航速变化的船舶AIS轨迹改进自适应压缩算法（Improved AIS Trajectory Adaptive Compression Algorithm for Ships Considering Speed Variations，ATACS），该算法将分段式压缩与自适应算法结合，通过计算航速和航向变化值来自适应标记航速特征点和航向特征点，以航向特征点为基准点分割原始轨迹，简化运算流程，对子轨迹进行自适应压缩，将压缩后的数据与航速特征点整合得到最终数据。

1 相关算法及算法改进 1.1 相关算法 1.1.1 DP算法

DP算法的原理是预先设定一个压缩阈值$ \varepsilon $，连接点集中的首尾两点，计算中间各点到连线的垂直欧氏距离（本文以符号$d$表示），假设在平面上有点$A\left( {{x_1},{y_1}} \right)$，$B\left( {{x_2},{y_2}} \right)$，$Q\left( {{x_m},{y_m}} \right)$，则点$Q$到直线$AB$的垂直欧式距离计算为式(1)，取这些点中垂直欧式距离的最大值${d_{\max }}$与预先设定的阈值$ \varepsilon $相比较，若${d_{\max }} \leqslant \varepsilon $，去掉两点间全部的点，若${d_{\max }} > \varepsilon $，则该点视为分割点，保留分割点并将原线段从分割点处分为两段，两段新轨迹重复上述步骤直到所有的子轨迹都不能找到分割点，在式(1)中，若分母为0，则表示在某段轨迹中经纬度相同，即2个点坐标相同，在进行数据预处理时删掉位置重复点即可解决这个问题。

$ d = \frac{{\left| {\left( {{y_2} - {y_1}} \right){x_m} - \left( {{x_2} - {x_1}} \right){y_m} + {x_2}{y_1} - {x_1}{y_2}} \right|}}{{\sqrt {{{\left( {{y_2} - {y_1}} \right)}^2} + {{\left( {{x_2} - {x_1}} \right)}^2}} }}。$

(1)

1.1.2 考虑航速的改进DP算法

DP算法只考虑了船舶运动轨迹的形状，并没有考虑船舶航速的变化，如果只考虑轨迹点的位置信息，会造成速度特征点的缺失，将航速作为一个变量引入到DP算法中可以更好地保留船舶运动特征。由于AIS系统中包含船舶的实时航速信息，故可以直接将速度作为影响因素参与到船舶轨迹压缩中，考虑航速的DP算法（Douglas Peucker Algorithm Considering Voyage Speed，DPS） 在经典DP算法的基础上引入第三维−速度，设定合适的阈值是问题的关键，为了简化运算步骤，后续对比实验中的DPS算法采取标记速度特征点并合并数据的方法对原始轨迹进行压缩。

1.1.3 自适应压缩算法

自适应压缩算法（Adaptive Douglas Peucker，ADP）的核心是识别轨迹段类型并分割，根据船舶运动状态判定轨迹属于直行还是转向状态并分割，不同类型子轨迹段采取不同的压缩阈值，可以在保证压缩率的基础上保留更多的空间特征点，自适应压缩算法侧重考虑船舶轨迹的空间特性，对于船舶轨迹时间运动特征的保留有所欠缺。

1.2 算法改进

船舶轨迹数据的运动特征主要体现在船舶的对地航速（Speed Over Ground，SOG）和对地航向（Course Over Ground，COG），这2项数据均可通过AIS系统获得，可以通过其数值变化计算并表示船舶的航行特征^[7]。

定义1　平均航速差$V$。对于轨迹中某个点$ {P}_{m} $（非端点），分别计算其与前后两点航速差值的绝对值并取均值，如式(2)所示，${V_0}$为总体轨迹的平均航速差，如式(3)所示。

$ {V_m} = \frac{{\left| {{v_m} - {v_{m - 1}}} \right| + \left| {{v_m} - {v_{m + 1}}} \right|}}{2}，\quad 1 < m < n，$

(2)

$ {V_0} = \frac{{\displaystyle\sum\limits_{i = 1}^n {{V_i}} }}{n} 。$

(3)

式中：$ v $为航速；$ n $为该轨迹的总点数。

定义2　航速特征点。设定平均航速差阈值$s$，分别计算轨迹段中每个点的平均航速差，若某个点的平均航速差${V_m} > s$，则这个点视为变速点并保存。原始轨迹的起点和终点视为航速特征点。

定义3　平均航向差$A$。对于轨迹中某个点$ {P}_{m} $（非端点），分别计算其与前后两点航向角差值的绝对值并取均值，如式(4)所示。$ \alpha $为航向角，$ n $为该轨迹的总点数，航向角差值的绝对值必须是小于180°的，若$\left| {{\alpha _m} - {\alpha _{m - 1}}} \right|$>180°，则应替换为360°-$\left| {{\alpha _m} - {\alpha _{m - 1}}} \right|$；${A_{_0}}$为总体轨迹的平均航向差，如式(5)所示。

$ {A_m} = \frac{{\left| {{\alpha _m} - {\alpha _{m - 1}}} \right| + \left| {{\alpha _m} - {\alpha _{m + 1}}} \right|}}{2}, \quad 1 < m < n , $

(4)

$ {A_0} = \frac{{\displaystyle\sum\limits_{i = 1}^n {{A_i}} }}{n}。$

(5)

定义4　航向特征点。设定平均航向差阈值$\theta $，计算轨迹段中每个点的平均航向差，若某个点的平均航向差${A_m} > \theta $，则这个点视为转向点并保存。原始轨迹的起点和终点视为航行特征点。

考虑航速变化的船舶AIS轨迹改进自适应压缩算法采取标记特殊点分段压缩的方式对轨迹数据进行处理，具体流程如图2所示。

首先对原始数据进行清洗，剔除掉错误数据；然后分别计算平均航速差和平均航向差，根据设定的阈值寻找并保存航速特征点和航向特征点，以航向特征点为分割点分裂原始轨迹，对每段子轨迹分别进行DP压缩，处理后的数据和航速特征点数据整合到一起得到最终数据。

2 阈值选择

在船舶轨迹压缩中，实验之前需要确定压缩的阈值，不同于经典DP算法，本文设计的考虑航速变化的船舶AIS轨迹改进自适应压缩算法在筛选速度特征点和航向特征点时也需要设定相应的阈值，本节选取了样本库中同一航线20次航行数据作为样本进行试算并确定合适的阈值。

2.1 压缩阈值ε

压缩阈值的选择是DP算法的重要内容之一，地图的比例尺越大所设置的压缩阈值也应该随之增大^[4]，考虑到压缩效率，本节从10～100 m选取了多个阈值对样本数据进行DP压缩，压缩结果如图3所示。

根据图3可知，随着压缩阈值的增大，同一数据样本中保留的点数逐渐减少，压缩率逐步提高，当阈值增至一定水平后，压缩率趋于平稳。如果阈值过小，不仅压缩率较低，而且保留的数据量较大，容易造成冗余；而当阈值过大时，保留的数据量则不足，可能影响后续研究的准确性。可以看出，当压缩阈值为90 m时，压缩结果趋于稳定，各数据样本的压缩情况如表1所示，此时既保证了压缩效率，也避免了过多的信息损失。因此，后续实验将选取压缩阈值ε = 90 m进行进一步分析和示例说明。

2.2 平均航速差阈值

在压缩阈值ε = 90 m时进行实验，平均航速差阈值$s$在$0.5{V_0} \sim10{V_0}$时压缩率的变化情况如图4所示。随着平均航速差阈值$s$的不断增加，保留的轨迹点数逐渐增加，压缩率逐渐提高，在阈值为$8{V_0}$时航速特征点数趋于一个较为平稳且较低的值，此时，压缩率和压缩效果均处于较好的水平。根据其余实验以及压缩算法的特性分析，在DP压缩阈值$\varepsilon $取其他值时规律相同，即随着平均航速差阈值$s$增大，保留的点数会逐渐减少并趋于稳定，直到没有点的平均速度差大于阈值。为了便于计算，下一部分比实验中航速差阈值选择$8{V_0}$进行运算，值得说明的是，在进行此实验时平均航速差阈值$s$是可以根据实际需求进行调整的，也可以设置为动态值。

当航速差阈值取$8{V_0}$时，航速特征点的最大值为443，最小值为20，对应的原始点数分别为45537和1873，占比均在1%附近，属于合理的范围。

2.3 平均航向差阈值

在压缩阈值$\varepsilon $ = 90 m时，对样本数据进行平均航向差阈值试算，计算结果如图5所示。

可知，随着平均航向差阈值的增大，航向特征点的数量逐渐减少。当阈值接近某一临界值时，航向特征点数量趋于稳定，当平均航向差阈值取$5{A_0}$时，航向特征点的最大值为1864，最小值为64，而对应的原始点数分别为53656和1873，占比均未超过5%，这属于合理范围。根据表中的计算结果，选定$5{A_0}$作为平均航向差阈值进行后续计算。

3 实证分析

本文实验数据由龙船网提供，选取时间范围从2021年1月至2023年1月由厦门港开往天津港的22艘船舶共234次航行数据，数据包含MMSI、经纬度、航速、航向、定位时间等信息。以4艘船舶共20次的航行数据的实验结果举例说明，4艘船舶的基本数据如表2所示。

3.1 实验说明 3.1.1 数据预处理

AIS数据主要依赖传感器和人工输入，由于人为原因、设备原因和其他原因导致了收集到的AIS数据不可避免的存在一些问题。在利用AIS数据时，常常遇到数据缺失和出现异常值等情况，因此需要对数据进行预处理，通常通过异常值删除、填补缺失值以及数据标准化等方法对数据进行清洗和处理^[9]。

3.1.2 误差分析

DP算法及其改进算法本身就是一种近似的简化算法，从原理上来看误差不可避免，同时，该系列算法若通过墨卡托坐标计算船舶轨迹长度和点到线的垂直欧式距离需要将经纬度转化为墨卡托坐标，在较高纬度地区会产生较大的误差；使用经纬度进行运算也会导致误差，在球面上计算原始轨迹中的垂直欧式距离会导致结果不准确，需要利用球面公式进行计算，但这会导致工作量大大增加，本文旨在举例说明考虑航速变化的船舶AIS轨迹改进自适应压缩算法的可行性，不涉及精密的数学运算，经过实验计算，实验数据样本线路航程约1168 nmile，纬度最大跨度约为15°（24°N~39°N，均处于中低纬度地区），经度跨度较小，样本计算过程中最长子轨迹约为原始轨迹的10%，纬度差约为1.5°，故忽略误差进行近似计算。

3.2 航速特征保留

本节实验压缩阈值$\varepsilon $、平均航速差阈值$s$和平均航向差阈值$\theta $分别取值为90 m、$8{V_0}$和$5{A_0}$，随机选取一组数据（相同阈值下4种算法的处理结果），进行说明，如图6所示。后续对比实验选择与本节相同的阈值进行操作。

可知，在07:00和15:00左右，DPS算法和ATACS算法比DP算法和ADP算法额外保留了航速变化点。这是因为DPS和ATACS算法在设计时就考虑了航速的变化，通过增大平均航速差阈值，可以捕捉到更多的航速特征点。此外，ATACS算法由于综合考虑了更多因素，因此保留了更多的轨迹点，每个轨迹点都携带航速信息，这导致在0:00~9:00期间速度变化较为频繁，并且局部速度变化范围相对较小。

3.3 航向特征保留

SED误差表示某个轨迹点在压缩后轨迹段中的对应时间比例位置与其原位置之间的距离，为比较DP算法、DPS算法、ADP算法和ATACS算法在航向特征保留上的效果，本节选择平均SED误差^[14]作为度量指标。平均SED误差越小，表示2条轨迹越接近，压缩效果越优，压缩阈值与第2节保持一致，平均SED误差结果见图7。

可知，对于部分样本4种算法的平均SED误差十分接近，在超过一半的样本中ATACS算法的平均SED误差要小于其他3种算法，综合来看ATACS算法在保留轨迹航向特征上明显优于其他3种算法。

3.4 压缩效率对比

除了轨迹的航速特征和航向特征，数据的压缩时间和压缩率也是检验压缩算法的重要指标，本节分别列举了用4种算法处理20条样本数据的压缩率和压缩时间，结果分别如表3和表4所示。

通过表3可知，对于同一样本，相同阈值下不同算法的压缩率有所区别，总体上十分接近，ATACS算法的压缩率相较于另外3种算法总体略低，但保持在一个十分接近的范围，这是由于ATACS算法保留了更多的轨迹运动特征点；对于部分样本，4种算法的压缩率相较于其他样本都偏低，这是因为该样本的原始数据量较低，而轨迹总里程和其他样本大致相同，在相同阈值下保留的数据量也接近，因此压缩率较低。

由表4可知，在相同阈值的情况下ATACS算法处理同一样本的时间是普遍低于DPS算法和ADP算法的，这是因为ATACS算法自适应分割了原始轨迹，大大简化了运算复杂程度，但相较于DP算法耗时总体略高，考虑的因素越多，压缩过程中的运算量也会越大，因此ATACS算法的运行时间略高于DP算法，平均用时相较于DP算法仅高出10.16%。

3.5 压缩效果可视化

本节通过ATACS算法压缩后的轨迹图和原始轨迹图对照来论述ATACS算法的可靠性，如图8所示，不难看出使用ATACS算法压缩后的数据量明显减少，图中各样本的压缩率基本位于90%以上，并且压缩后的轨迹能够较为准确表示原始轨迹的走向和形状特征。

4 结　语

本文提出的考虑航速变化的船舶AIS轨迹改进自适应压缩算法（ATACS算法）在保证压缩效率的前提下，可以更好地保留船舶轨迹的运动特征，且算法原理较为简单，在运行时效率较高，并且可以根据不同的数据类型手动设定阈值或者设置为滑动阈值，可以更好地满足保存数据的要求。

本算法还存在一些需要改进优化的地方，一方面，本文对实验样本数据选取了部分阈值进行压缩实验，关于阈值的选择还需要进一步的大量实验进行论证；特征点筛选的规则过于简单，虽然能够保证较高的效率，但对于复杂的数据未必适用且存在一定的误差，优化算法中判定航速特征点和航向特征点的判定以及减小误差影响是本算法未来研究的重点方向。