基于FP-TSDP算法的船舶轨迹压缩

江海洋，高 超，马 勇

（1.武汉理工大学航运学院，武汉 430063；2.中国舰船研究设计中心，武汉 430063）

1 引言

船舶自动识别系统（Automatic Identification System,AIS）轨迹数据中蕴含着大量信息[1-4]，包括船舶的静态和动态信息、船舶驾驶员的人为因素、船舶避碰行为、船员通常做法和习惯航路等。通过分析和研究船舶轨迹，可获取能够反映船舶规律的有效和潜在信息，进而为海上安全监管、船舶通航、航海保障等活动提供必要的数据支持[5-6]。然而，海量的AIS 数据中存在一些利用价值较低的数据点，当移除此类数据后船舶轨迹不会产生改变。由此，为提高数据的利用效率，需要对冗杂的船舶AIS 轨迹数据进行压缩处理。

通常，包括道格拉斯–普克（Douglas-Peucker,DP）在内的多数船舶轨迹压缩算法往往仅考虑轨迹的距离偏移量来压缩轨迹[7]，在压缩过程中舍弃了船舶航速、航向改变、进出某区域边界等航迹特征点，得到的轨迹忽略了船舶的动态信息，降低了数据的利用价值；少部分压缩算法通过航向、航速变化率均值来保留船舶轨迹特征点[8-10]，但忽略了由传感器误差导致的航速、航向出现的小范围波动，进而保留了波动点，使得压缩后保留的数据点过多；极少数压缩算法虽然考虑了船舶的时空特性[11-13]，但仅将时间特性作为分类和排序的指标，一般压缩后的轨迹失真率较高。

为提升轨迹压缩算法质量，充分应用船舶动态特征点（Feature Point,FP）数据以及时空特性（Temporal and Spatial,TS），在DP 算法的基础上提出FP-TSDP 船舶轨迹压缩算法。对比结果表明，经FP-TSDP 算法压缩后的轨迹质量得到较好的提升。

2 AIS 数据解码与预处理

AIS 数据分析主要包括数据解码、数据预处理和数据挖掘3 个步骤。数据预处理包括轨迹异常点清除和船舶轨迹压缩环节，经过预处理的数据，较为精简，具有较高的实用性和使用价值。

2.1 AIS 数据解码

AIS 报文信息是一串复杂晦涩的字符串，封装度极高，难以被人们直接理解和应用，为获取直观信息，需要解码原始信息。数据中的每个记录点代表一个由船载AIS 设备在某个瞬间发出的AIS 报告信息。

AIS 数据解码主要由3 个阶段实现[14]。首先，将AIS 原始数据转换为ASCII 码。然后，将ASCII码值与16 进制数80H 相比较，如果大于80H，则转换出的ASCII 码值加上20H；如果小于80H，则转换的ASCII 码值加上28H。经变换，原来的ASCII 码变成了6 位ASCII 码。单条信息转换后全长最大为168bit，每个字符都是转换后6bit 的ASCII 码，从字符“1”开始为有效信息。最后，参照AIS 国际标准信息对照表，解析出对应信息。解码后的信息是一连串由数字0 和1 组成的二进制编码，需对比国际AIS 制定的标准协议，利用27 种电文的格式分配相应的比特位，拼接信息后解析出AIS 信息。

2.2 AIS 数据预处理

经数据解码后的AIS 数据不能直接使用，主要是存在许多异常数据，会影响船舶轨迹压缩的结果。为保证数据的准确性，需要对AIS 数据进行异常数据处理工作。AIS 数据主要有3 种异常情况。其一，存在静态信息输入错误和部分信息未输入的情况；其二，存在船舶航次相关信息输入错误或信息未输入的情况；其三，存在因传感器故障，导致船舶动态信息出现错误的情况。

由此，针对解码后的数据，需要开展AIS 数据筛选预处理工作[15]，即需要删除AIS 报告信息MMSI 记录为0 的点；删除数据中偏离所选水域航道较远的点，如经纬度显著超出航道，速度出现负值或超出正常值；删除时间相邻的2 个AIS报告点距离超过实际可能最大值的轨迹点。在数据预处理阶段，删除无效的、不合理的、偏离航道的数据，确保获得有效的AIS 数据。

出于安全考虑，国际海事组织要求AIS 数据点的报告间隔较短。经过上述筛选处理的AIS 数据规模非常大，直接使用导致运算速度缓慢，难以得到有效应用。为此，需要对AIS 数据进行压缩处理。传统DP 压缩算法[16]根据距离阈值来判定。在DP 算法中，通常将轨迹的起点和终点连成直线，计算轨迹上每个点到这条直线的距离，选择其中距离最大的点，将其距离与预设的距离阈值进行比较，小于距离阈值，则舍弃这条直线两侧的点，若大于距离阈值，则保留这个点；然后，将起点和终点分别同这个点进行连线，得到两条直线，再分别重复上述步骤，迭代计算，直至所有点到对应直线的距离都小于距离阈值，则完成压缩。可知，上述方法压缩出来的轨迹，动态信息丢失较多、轨迹失真率较高，有必要设计一种高质量的船轨迹压缩算法。

3 船舶轨迹压缩FP-TSDP 算法

3.1 特征点优化

传统DP 算法一般仅通过距离偏移量来压缩轨迹，会导致在压缩过程中舍弃部分船舶的动态信息、航速及航向改变、进出某区域边界等航迹特征点，降低了数据的利用价值。因此，在DP算法的基础上，需要优化轨迹特征点，开展提取和保留特征点研究工作。

针对船舶航速、航向改变点的提取保留工作，可通过判断各数据点的船舶航速、航向改变率是否高于某一设定阈值来实现。

船舶航速改变率及航向改变率的示意图如图1所示，其中，Bi-1,Bi,Bi+1为连续的3 个数据点，Vin,Vout分别为航段Bi-1Bi,BiBi+1上的平均航速，COGin,COGout分别为Bi-1Bi,BiBi+1上的平均航向。

图1 船舶航速改变率和航向改变率计算示意图Fig.1 Schematic diagram of calculating of ship speed change rate and course change rate

各数据点的船舶航速、航向改变率分别由式(1)、(2)计算得出[17]。

在确定阈值的过程中，首先由式(3)、(4)计算整体数据全航程的平均航速改变率以及平均航向改变率；考虑到船载AIS 设备传感器精度的限制，航速和航向数据会存在小范围的波动，如以平均改变率作为阈值，可能会将此类波动点视为航速改变、航向改变的轨迹特征点而保留下来，导致压缩后数据量依然庞大；通过多次测验分析引入扩大系数M,N，其中9≤M≤11,3≤N≤5。分别对平均航速改变率和平均航向改变率进行M和N倍扩大处理，在接近原始轨迹的同时可显著缩小数据量。

船舶驶入/出行为[18]包括驶入/出码头、锚地、桥区水域、渔区水域、环形道等闭合区域以及航道、危险线、边界线等非闭合区域。船舶驶入/出轨迹特征点是指船舶通过上述非闭合区域边界线前后的AIS 数据点。对于此类轨迹特征点，可以通过判断相邻两个AIS 数据点分别代入边界线方程后值的乘积是否小于0。若小于0，则标记并保留为船舶进出某区域轨迹点，构成进出某区域点集合。

DP 算法特征点优化即通过上述方法，对轨迹中的特征点进行识别保留，以特征点为DP 算法输入的初始点进行轨迹压缩。经过特征点优化后的DP 算法进行轨迹压缩，压缩后的轨迹保留了这些轨迹特征点，关键信息含量高于传统DP 算法进行压缩后的轨迹，轮廓特征更加接近于原始轨迹，具有较高的利用价值。

3.2 时空特性优化

AIS 数据的时空特性[19]，如图2所示，图中为时刻船舶的位置，对此段轨迹进行压缩，的连线为预期直线轨迹，为计算到预期直线轨迹欧式距离对应的船位，为时刻预期直线轨迹上实际的船位。不难看出，在预期轨迹上偏移点所对应的实际预期船位应在偏移点计算到预期轨迹线欧式距离的船位之前。传统DP 算法计算轨迹的偏移量的方式往往采用欧式几何上的垂直距离，此距离略小于时空偏移距离，使用此距离进行压缩，虽然压缩后数据量较小，但压缩后轨迹的失真率较高。因此，在DP 算法的基础上，需要进行时空特性优化，计算偏移船位与实际预期船位的时空距离，以时空距离对比DP 算法距离阈值进行偏移点的取舍。

图2 时空特性优化原理Fig.2 Principle of optimization using time and space characteristics

时空距离计算方法如下：连接每个分段航迹的起点和终点，并根据起点与终点的经度，纬度转换后的墨卡托坐标系坐标和时间建立虚拟直线时空轨迹，对每个子轨迹段，计算该子轨迹段AIS数据点在虚拟直线时空轨迹上同时刻点的墨卡托坐标系坐标，将该子轨迹段的AIS 数据点的墨卡托坐标系坐标与该AIS 数据点在虚拟直线时空轨迹上同时刻点的墨卡托坐标系坐标之间的距离作为该AIS 数据点到虚拟直线时空轨迹的时空距离，即为。

3.3 FP-TSDP 算法流程

通过上述特征点优化与时空特性优化，提出FP-TSDP 算法流程，流程图如图3所示。

图3 FP-SPDP 算法流程图Fig.3 FP-SPDP algorithm flow chart

FP-TSDP 算法具体实现步骤如下：

（1）识别并保留AIS 时序性数据记录中的船舶航向和航速的改变点，船舶驶入/出某区域特征点，分别记录到航速改变点集合S，航向改变点集合C，驶入/出某区域特征点集合E；

（2）设置距离阈值dT，以船舶轨迹的起点、终点以及集合S、E、C中的特征轨迹点为初始点对轨迹进行分段标记，相邻两个轨迹特征点之间的轨迹为一个子轨迹段；

（3）连接每个分段航迹的起点和终点，并根据起点与终点的经度，纬度转换后的墨卡托坐标系坐标和时间建立虚拟直线时空轨迹。对每个子轨迹段，计算该子轨迹段AIS 数据点在虚拟直线时空轨迹上同时刻点的墨卡托坐标系坐标，将该子轨迹段AIS 数据点的墨卡托坐标系坐标与该AIS 数据点在虚拟直线时空轨迹上同时刻点的墨卡托坐标系坐标之间的距离作为该AIS 数据点到虚拟直线时空轨迹的时空距离d，找到所有时空距离中的最大距离dmax，比较该最大距离与预设距离阈值dT的大小；

（4）如果dmax＜dT，则该子轨迹段上所有中间数据点全部舍掉，舍掉所有中间点后，连接该子轨迹段起点和终点的直线就作为该子轨迹段的近似，该段子轨迹处理完毕；

（5）如果dmax＞dT，则对应最大距离的AIS数据点应保留为结果轨迹上的数据点，同时通过对应最大距离的AIS 数据点将该段子轨迹分为两部分，对这两部分曲线分别采用步骤（3）和步骤（4）进行处理，直到所有的dmax＜dT；

（6）当所有子轨迹段处理完后，依次连接各分割点形成的轨迹，即为原轨迹压缩后的近似轨迹。压缩过程示意图如图4所示，如图中①表示起始点和特征点划分子轨迹段以及子轨迹段时空插值的结果，图中②～⑤表示各子轨迹段的处理流程，图⑥表示对①中轨迹最终处理结果。

图4 FP-SPDP 算法压缩轨迹过程示意图Fig.4 Schematic diagram of the trajectory compression process of the FP-SPDP algorithm

4 仿真结果及分析

长江武汉段属于长江中游与下游的交接段，是长江中下游水运的重要中转站，水运较为繁忙，AIS 基站仅一天接收到的AIS 数据就有15 万条之多。水域内桥区多、港区和停泊区多，增加了船舶在水域内航行的安全隐患。为提升利用AIS 数据对船舶轨迹的分析研究，可以从中获取能够反映船舶规律的、有效的、潜在的信息，进而为海事机关对船舶违章行为监管，修订航行规则，推行船舶定线制提供有效的数据支持。为提升数据利用效率，需要对数据进行压缩处理。

本文分别使用传统DP 算法和本文进行优化过的DP 算法，对长江武汉段2016年8月9日当天所采集AIS 数据，原始轨迹点总计146789 个，作为原始数据进行压缩实验，距离阈值均为100，特征点优化扩大系数M为10，N为5。原始船舶轨迹图如图5所示，总体压缩结果如图6 和图7所示，单船压缩结果如图8 和图9所示。传统DP算法压缩后保留轨迹点12272 个，压缩率（压缩后轨迹点数量/原始轨迹点数量）为8.36%，优化DP 算法压缩后保留轨迹点数量17703 个，压缩率为12.06%。

图6 传统DP 算法压缩后整体船舶轨迹图Fig.6 Overall ship trajectory map compressed by the traditional DP algorithm

图7 FP-TSDP 算法压缩后整体船舶轨迹图Fig.7 Overall ship trajectory map compressed by FP-TSDP algorithm

对比图5～7，可以明显看出传统DP 算法压缩后有一段轨迹丢失，FP-TSDP 算法压缩后的轨迹与原始轨迹更为相近；如图8 和图9所示，传统DP 算法压缩后轨迹点较少，但特征点缺失较多，FP-TSDP 算法所得到的轨迹更加平滑，接近于原始轨迹，且特征点保留完整。在图 8 和图 9的基础上增加一个维度表示船舶速度，分别做出两种方法轨迹压缩后单船轨迹–速度复合曲线，如图10 和图11所示。对比分析图10 和图11，可看出传统轨迹压缩方法压缩后的轨迹中船舶航速改变点明显少于FP-TSDP 算法压缩后的船舶轨迹，同时大部分轨迹特征点偏离复合曲线。

图5 原始船舶轨迹图Fig.5 Original ship trajectory map

图8 传统DP 算法压缩后单船轨迹图Fig.8 Single ship trajectory after compression by traditional DP algorithm

图9 FP-TSDP 算法压缩后的单船轨迹图Fig.9 Single ship trajectory compressed by FP-TSDP algorithm

图10 传统DP 算法压缩后单船轨迹-速度复合曲线Fig.10 Single ship trajectory-speed compound curve compressed by traditional DP algorithm

图11 FP-TSDP 算法压缩后的单船轨迹-速度复合曲线Fig.11 Single ship trajectory-speed compound curve compressed by FP-TSDP algorithm

5 结论

针对船舶AIS 数据中无用数据点的剔除问题，本文对传统DP 算法进行了特征点优化和时空特性优化，提出了基于FP-TSDP 算法的船舶AIS 轨迹压缩方法。实验结果表明，在保证一定压缩率的前提下，FP-TSDP 算法充分考虑了特征轨迹点的保留问题，对船舶行驶中加速、减速、转向、进出特殊区域等重要的动态行为点较完整地进行保留。同时，利用时空距离压缩轨迹，较好地保留了原始轨迹的形状。通过FP-TSDP 算法简化后的数据较为简洁，且有较大的二次利用价值。