基于FPTSDP算法的船舶轨迹压缩

　　摘要在船舶轨迹压缩方面，通常存在难以有效剔除海量船舶自动识别系统(AIS)数据中无用数据点的问题。为改进船舶轨迹压缩质量，提出基于道格拉斯—普克(DP)改进的特征点(FP)–时空(TS)算法。在FPTSD算法中，关注船舶行驶过程中加减速、转向、进出特殊区域等重要的动态行为点，采用数值计算方法提取和保留AIS数据中上述动态行为FP，以FP为初始点使用DP算法对AIS数据进行压缩;同时，考虑AIS数据的TS特性，以时空距离为标准进行取舍，进而在FP和TS特性优化的基础上实现了船舶轨迹压缩。结果表明，在保证压缩率的前提下，经FPTSDP算法压缩后的轨迹更接近原始轨迹，同时其重要动态行为点留存率更高。

　　关键词AIS;FPTSDP算法;轨迹特征点;时空特性;船舶轨迹压缩

　　1引言

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

　　通常，包括道格拉斯–普克(Douglaseucker,DP)在内的多数船舶轨迹压缩算法往往仅考虑轨迹的距离偏移量来压缩轨迹[7]，在压缩过程中舍弃了船舶航速、航向改变、进出某区域边界等航迹特征点，得到的轨迹忽略了船舶的动态信息，降低了数据的利用价值;少部分压缩算法通过航向、航速变化率均值来保留船舶轨迹特征点[810]，但忽略了由传感器误差导致的航速、航向出现的小范围波动，进而保留了波动点，使得压缩后保留的数据点过多。

　　极少数压缩算法虽然考虑了船舶的时空特性[1113]，但仅将时间特性仅作为分类和排序的指标，一般压缩后的轨迹失真率较高。为提升轨迹压缩算法质量，充分应用船舶动态特征点(FeaturePoint,FP)数据以及时空特性(TemporalandSpatial,TS)，在DP算法的基础上提出FPTSDP船舶轨迹压缩算法。对比结果表明，经FPTSDP算法压缩后的轨迹质量得到较好的提升。

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

　　2.1AIS数据解码

　　AIS报文信息是一串复杂晦涩的字符串，封装度极高，难以被人们直接理解和应用，为获取直观信息，需要解码原始信息。数据中的每个记录点代表一个由船载AIS设备在某个瞬间发出的AIS报告信息。AIS数据解码主要由个阶段实现14]。首先，将AIS原始数据转换为ASCII码。然后，将ASCII码值与16进制数80H相比较，如果大于80H，则转换出的ASCII码值加上20H;如果小于80H，则转换的ASCII码值加上28H。

　　经变换，原来的ASCII码变成了位ASCII码。单条信息转换后全长最大为168bit，每个字符都是转换后6bit的ASCII码，从字符“”开始为有效信息。最后，参照AIS国际标准信息对照表，解析出对应信息。解码后的信息是一连串由数字和组成的二进制编码，需对比国际AIS制定的标准协议，利用27种电文的格式分配相应的比特位，拼接信息后解析出AIS信息。

　　2.2AIS数据预处理

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

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

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

　　3船舶轨迹压缩FPTSDP算法

　　3.1特征点优化

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

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

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

　　3.2时空特性优化AIS数据的时空特性

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

　　4仿真结果及分析

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

　　结论

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

　　参考文献

　　[1]杨博辰.基于AIS的船舶轨迹分析的研究与应用[D].成都:电子科技大学2018.

　　[2]DeVriesGKD,VanSomerenM.Machinelearningforvesseltrajectoriesusingcompression,alignmentsanddomainknoledge[J].ExpertSystemswithApplications,2012,39(18):1342613439.

　　[3]郭乃琨,马壮壮,岳明桥.船舶轨迹挖掘与可视化技术分析研究[J].电子元器件与信息技术2020,4(3):137138.

　　[4]朱飞祥,张英俊,高宗江基于数据挖掘的船舶行为研究[J].中国航海2012,35(2):5054.

　　[5]LinK,LiX,ZhangZ,etal.AKmeansclusteringwithoptimizedinitialcenterbasedonHadoopplaform[C].InternationalConferenceonComputerScience&.Education.IEEE,2014:263266.

　　[6]XuK,ZhenH,LiY,etal.Bigdataacquisitionandanalysisplatformforintermodaltransport[J].InternationalJournalofDatabaseTheoryandAppliction,2016,9(12):6778.

　　[7]毕月琨.AIS基站系统中的数据解析与压缩[D].舟山:浙江海洋学院2014.

　　[8]张永兵,孟凡彬,孟科.一种基于航向和航速变化率的船舶轨迹压缩方法[P].天津:CN110990504A,20200410.

　　[9]张广娜,梁营力.船舶高速航行运动轨迹分段压缩算法研究[J].舰船科学技术2020,42(12):4951.

　　[10]陈永超.基于数据挖掘的船舶轨迹预测研究[D].哈尔滨:哈尔滨工程大学2020.

　　[11]徐凯,邱家瑜,李燕.一种加入时间维的船舶轨迹高效离线压缩算法研究[J].计算机科学2017,44(S2):498502.

　　作者：江海洋，高超，马勇