基于Douglas⁃Peucker算法的船舶AIS航迹数据压缩

张树凯，刘正江，张显库，史国友，蔡垚

（大连海事大学航海学院，辽宁大连116026）

基于Douglas⁃Peucker算法的船舶AIS航迹数据压缩

张树凯，刘正江，张显库，史国友，蔡垚

（大连海事大学航海学院，辽宁大连116026）

为解决普通模式下，将海量AIS航迹数据显示在ECDIS平台上效率低、实时性差等问题，设计一种基于Douglas⁃Peucker算法的AIS航迹数据压缩算法。通过分析AIS航迹数据的特征，总结普通模式下ECDIS平台AIS航迹显示实时性差的原因，提出在保留原始航迹特征和误差允许的范围内剔除冗余和重复信息的思想，结合Douglas⁃Peucker算法，根据设定的不同阈值提取出关键特征点从而对AIS航迹数据进行压缩。在VC2010平台下对该算法进行实现，实践证明，该算法能在较低失真度的前提下对船舶AIS航迹数据进行压缩，提高了轨迹回放、再现效率，与普通模式下ECDIS显示大量AIS航迹相比，系统占用资源少、处理效率高并具有较高的稳定性。

船舶；AIS航迹；Douglas⁃Peucker算法；数据压缩

船载自动识别系统（automatic identification sys⁃tem，AIS）在船舶导航与监控、船舶交通流研究等方面越来越显示出方便、轻巧的特点。AIS数据可以有效叠加到电子海图上，方便航海人员观察某一水域交通流的整体态势或显示某条船舶的历史轨迹［1］。船载AIS设备一般2 s－6 min发布一条信息，船舶的历史轨迹数据相当庞大。除了海量数据的存储问题，当把海量AIS数据导入到ECDIS平台观察交通流的整体态势或交通流特征时，由于数据量大，系统的处理效率非常低，ECDIS平台对海图平移、缩放响应的速度也变得十分缓慢。AIS航迹中包含大量重复和冗余的信息。一方面是船载AIS设备的发送频率较高造成的，例如某条锚泊船可以用2条AIS信息代替在锚泊期间发送的所有AIS信息；另一方面是由具体应用产生的，例如大比例尺海图下的数据用于小比例尺海图显示和应用时就会存在冗余。为了能够实时的回放AIS的历史轨迹，如何在较低失真度的前提下压缩这些冗余和重复的信息显得尤为重要。Douglas⁃Peucker算法现已广泛应用在矢量地图压缩、数字高程模型简化等方面［2⁃6］。

本文根据Douglas⁃Peucker算法的原理和特点对AIS航迹数据进行预处理，并将其应用到AIS航迹数据的压缩；在验证其可行性的基础上提出不同比例尺和不同条件下的推荐阈值。

1 Douglas⁃Peucker压缩算法原理

1973年，Douglas等提出了一种简化二维曲线的算法［7］。该算法的核心思想是从构成曲线的点集合A中提取出一个能反映曲线总体及局部形态主要特征的点集A′。

假设描述曲线的点集A为

以图1为例说明Douglas⁃Peucker算法的原理。将首点和尾点分别作为初始锚点和初始漂浮点，并将其连成的直线称为基线。依次计算中间各点到基线的垂直距离，并找出最大距离对应的点。若最大距离小于设定的阈值，则用基线代替原始曲线。若最大距离大于设定的阈值，则将最大距离对应的点作为分裂点，并将该分裂点作为前向点集的漂浮点和后向点集的锚点。依次递归选取分裂点和分段，直到每一个子集中都不再出现新的分裂点。

图1 Douglas⁃Peucker算法Fig.1 Douglas⁃Peucker algorithm

由Douglas⁃Peucker算法提取出的特征点之所以能够反映原始曲线的总体和局部特征，是因为活跃的基线始终由当前最有特点的2个点连接而成，而后以基线作为“视平线”去“端详”最大局部的区段，并选取该区段的主要特征点［8⁃10］。

2 AIS数据库设计

海量AIS数据的存储和调用是进行快速压缩和实时显示的关键因素。如何快速提取出同一海上移动通信业务标识码（maritime mobile service identify，MMSI）的AIS记录并按时间顺序导入到Douglas⁃Peu⁃cker算法中进行压缩是亟需解决的一个关键问题。系统采用SQLite数据库，库结构采用单“TRACK”表建立，单表的每一条记录包含MMSI、经度、纬度和时间4个字段。单表的一条记录对应AIS设备一次发送的数据。数据库管理方案如图2所示。

图2 数据库管理方案Fig.2 Database management

AIS数据中的地理位置以经纬度形式存储，在压缩前，应首先将经纬度坐标转换为墨卡托坐标，然后转换为屏幕坐标显示。根据等角正圆柱投影原理，假设某点的经纬度坐标为（φ，λ），平面坐标为（x，y），则经纬度到平面坐标的转换公式为：

式中：r0为基准纬度圈半径；a为地球椭球长轴半径；q为等量维度；e为椭球第一偏心率。

3 实例验证与分析

3.1 数据压缩的实现

SQLite数据库解决了海量AIS数据的快速存储和调用的问题，但频繁的调用依旧会降低处理效率，因此程序使用SQL语句从数据库提取出某一条船舶的AIS航迹后将数据映射到结构体数组std：：vec⁃tor＜POINT＞中，这样引用结构体数组就相当于引用数据库中的数据［11］。在内存中建立的数据结构及作用如表1所示，整体实现流程如图3所示。

表1 算法中用到的数据类型Table 1 Data type used in algorithm

图3 整体实现流程Fig.3 Workflow of implementation

3.2 实例分析

为了验证Douglas⁃Peucker算法压缩AIS数据的有效性和效率问题，以琼海海峡VTS中心AIS基站10月某日收到的数据作为测试数据。该数据包括224条船舶的AIS轨迹，共计953 203对坐标点。分别采用0～2 m之间不同的阈值进行压缩，得到相应的压缩后特征点和压缩率，如表2所示。

表2 不同阈值下的特征点数和压缩率Table 2 Number of feature points and compression rates in different thresholds

从表2可以看出，随着阈值的增大，压缩后特征点越来越少，压缩率越来越大。当阈值为0.5 m时，压缩率达到49.22%，也就是说可用原始航迹一半的点数代替原始航迹且绝对误差限小于0.5 m，在保证原始航迹特征和精度的基础上数据压缩率相当可观。

为了更加直观、形象的展示压缩效果，随机选取224艘船中的一艘进行观察。从SQLite数据库中选取MMSI为563156000的船舶AIS轨迹，将压缩阈值分别设置为0.2 m和2.0 m进行压缩。该船共有原始点8 155个，压缩后特征点分别为5 900个和1 247个，压缩率分别为27.65%和84.71%。将压缩后的特征点转换为S57格式，分别导入到ECDIS平台显示，海图比例尺为1：1 000 000，显示效果如图4所示。通过观察可知：虽然压缩率相差较大，但显示在ECDIS平台上时并无明显差异。

如图5所示，提取出MMSI为563156000的船舶AIS数据，分别将阈值设置为2、20、200 m和2 000 m进行压缩，将压缩后的特征点用小方块表示并显示在1∶1 000 000海图上。由图可知，阈值为2 m时特征点过于密集；阈值为2 000 m时特征点过于稀松，表示原始轨迹特征的能力较差；阈值为20 m时特征点疏密程度较为适宜；阈值为200 m时较为稀松，表示单船原始航迹特征的能力相对较差，但对于观察交通流的宏观态势是足够的，而且占用系统资源少，显示实时性高，对海图操作的响应快。如图6所示，压缩阈值为200 m时表征宏观交通流的能力与压缩阈值为0 m时几乎相似。

图4 563156000船在不同阈值下的压缩效果Fig.4 Compression result of ship 563156000 in different thresholds

图5 不同阈值下特征点在1：1 000 000海图的显示效果Fig.5 Display of feature points in different thresholds in chart of mapscale1：1 000 000

图6 不同阈值下交通流整体态势Fig.6 The overall state of traffic flow in different thresholds

在大比例尺海图下表述船舶运动行为和特征的最小点集在小比例尺海图下显示时必然存在冗余。因此，为了在不同的比例尺海图下显示船舶的AIS轨迹，同时加快显示效率，需要根据不同的比例尺设定不同的阈值。

3.3 推荐阈值

由3.2实例分析可知，在同一比例尺下选择不同的阈值进行压缩可得到不同的效果，用户可根据需要选择不同的阈值进行压缩，例如，观察整个海域的交通流整体态势时可将阈值设置得大一点，观察某一艘船舶的运动轨迹特征时可以将阈值设定得小一点。在不同的比例尺下根据设定的不同阈值进行压缩也会得到不同的效果，用于大比例尺海图下显示船舶轨迹的点在小比例尺海图下肯定会存在冗余，因此在小比例海图下进行压缩时应将阈值设置得大一些，在大比例尺海图下进行压缩时应该阈值设置得小一些。

表3 1－20 m不同阈值下的特征点数和压缩率Table 3 Number of feature points and compression rates in different threshold 1－20 m

图7 阈值增加1 m时压缩率增长值Fig.7 Growth of compression rate when increasing the threshold by 1 m

由表3可知，当设定的阈值为16～20 m时，压缩率已经高达97.03%，之后随着设定的阈值的增大，压缩率并没有明显提高。通过图7也可看出，当阈值分别设定为1～20 m时，后一阈值较前一阈值压缩率的增大情况在16 m时已经非常小。且随着阈值越大，压缩后的点表征原始轨迹特点的能力越差，失真度越大。因此建议在观察单船AIS轨迹特征时设定阈值的上限为16 m，当阈值比16 m大时，压缩率不会明显增加，但失真度会增大；在观察宏观交通流特征时可将阈值适当扩大。

根据海图的用途不同可将海图分为总图、航行图和港湾图，航行图又包括远洋航行图、近海航行图和沿岸航行图。根据大量实验的结果，表4给出了不同比例尺下的推荐最佳阈值，用户可根据实际情况适当调整。

表4 不同比例尺下的推荐阈值Table 4 Recommended thresholds in different scales

4 结论

1）在ECDIS平台显示海量AIS数据时，处理这些数据会花费很长时间，不仅使显示的时效性受到影响，而且ECDIS对海图的平移、缩放等操作的响应速度会大大减慢。本文将简化矢量要素的经典算法Douglas⁃Peucker算法应用于压缩AIS数据，大幅度提高了显示的实时性和海图操作的快速响应。

2）将Douglas⁃Peucker算法的阈值设置为200 m对AIS航迹数据进行压缩，通过观察实验结果可知，压缩后的AIS航迹仍然能够较好的展示出整体交通流的态势。另外，由于压缩率高达99%，大大提高了处理效率。用户可根据不同的需要和精度要求设置不同阈值压缩AIS航迹数据，在保持原始数据特征和误差允许的范围内剔除原始数据中重复和冗余的信息。

3）通过初步的实验分析，本文提出的基于Douglas⁃Pecuker算法的AIS航迹数据压缩算法可根据不同的比例尺、用户的要求和精度进行有效的压缩，算法简单，压缩率和表征原始轨迹的能力令人满意。下一步的工作将把速度和时间要素考虑在内，建立基于三维Douglas⁃Peucker算法的AIS航迹数据压缩算法。

［1］初秀民，徐海潮，万剑，等.基于多线程的船载自动识别系统报文解析［J］.中国航海，2011，34（2）：19⁃23.

CHU Xiumin，XU Haichao，WAN Jian，et al.Parsing ship⁃borne AIS messages based on multithreading［J］.Navigation of China，2011，34（2）：19⁃23.

［2］ROSEN I.Real⁃time GPS track simplification algorithm for outdoor navigation of visually impaired［J］.Journal of Net⁃work and Computer Applications，2012，35（5）：1559⁃1567.

［3］YU Jing，CHEN Gang，ZHANG Xiao，et al.An improved Douglas⁃Peucker algorithm aimed at simplifying natural shoreline into direction⁃line［C］／／Proceedings of 21stInter⁃national Conference on Geoinformation.Kaifeng，China，2013：20⁃22.

［4］SONG Xiaomei，CHENG Changxiu，ZHOU Chenghu，et al.Gestalt⁃based Douglas⁃Peucker algorithm to keep shape sim⁃ilarity and area consistency of polygons［J］.Sensor Letters，2013，11（6／7）：1015⁃1021.

［5］SHI Shaozhong，CHARLTON M.A new approach and pro⁃cedure for generalising vector⁃based maps of real⁃world fea⁃tures［J］.Giscience＆Remote Sensing，2013，50（4）：473⁃482.

［6］CHEN C J，LEE T Y，HUANG Y M，et al.Extraction of characteristic points and its fractal reconstruction for terrain profile data［J］.Chaos Solitons＆Fractals，2009，39，1732⁃1743.

［7］DOUGLAS D H，PEUCKER T K.Algorithms for the reduc⁃tion of the number of points required to represent a digitized line or its caricature［J］.The Canadian Cartographer，1973，10（2）：112⁃122.

［8］何津，费立凡.再论三维Douglas⁃Peucker算法及其在DEM综合中的应用［J］.武汉大学学报：信息科学版，2008，33（2）：160⁃163.

HE Jin，FEI Lifan.Further study on three dimensional Douglas⁃Peucker algorithm and its application to generaliza⁃tion of DEM［J］.Geomatics and Information Science of Wu⁃nan University，2008，33（2）：160⁃163.

［9］PALLERO J L G.Robust line simplification on the plane［J］.Computers and Geosciences，2013，61：152⁃159.

［10］曹刘娟，门朝光，孙建国.二维矢量地图双重零水印算法［J］.哈尔滨工程大学学报，2011，32（3）：340⁃344.

CAO Liujuan，MEN Chaoguang，SUN Jianguo.A double ze⁃ro⁃watermarking algorithm for 2D vector maps［J］.Journal of Harbin Engineering University，2011，32（3）：340⁃344.

［11］SHEN Wenwei，YANG Jianhua，CHEN Shefu，et al.Ap⁃plication of embedded database SQLite in smell⁃seeing sys⁃tem［J］.Chinese Journal of Scientific Instrument，2010，31（6）：1289⁃1293.

［12］张兴福，黄少滨.自适应近邻的局部线性嵌入算法［J］.哈尔滨工程大学学报，2012，33（4）：489⁃495.

ZHANG Xingfu，HUANG Shaobin.Adaptive neighborhoods based locally linear embedding algorithm［J］.Journal of Harbin Engineering University，2012，33（4）：489⁃495.

A method for AIS track data compression based on Douglas⁃Peucker algorithm

ZHANG Shukai，LIU Zhengjiang，ZHANG Xianku，SHI Guoyou，CAI Yao
（Navigation College，Dalian Maritime University，Dalian 116026，China）

This paper proposes a compression method based on Douglas⁃Peucker algorithm to solve the low efficiency problem and overcome the network latency in real⁃time system for massive AIS tracks displayed in the ECDIS.The paper analyzes data characteristics of AIS tracks and concludes the reasons for bad real⁃time performance of AIS track display in the ECDIS under general mode.Under the premise of keeping original characteristics of tracks，the proposed method eliminates the redundant and repeated information within an allowable range for errors.Thus，it compresses AIS track data through extracting critical features using specific thresholds.The concept is implemented in VC2010.It is proven in practice that data compression for AIS tracks is conducted rapidly with low distortion and the performance of playback is improved using this method.Compared with other traditional methods，it takes less resource in the system and realizes higher processing efficiency and stability for calculation.

ship；AIS tracks；Douglas⁃Peucker algorithm；data compression

10.3969／j.issn.1006⁃7043.201401013

http：／／www.cnki.net／kcms／detail／23.1390.U.20150414.1635.016.html

U675.7

A

1006⁃7043（2015）05⁃0595⁃05

2014⁃01⁃07.网络出版时间：2015⁃04⁃14.

国家自然科学基金资助项目（51309041）；国家863计划基金资助项目（2009AA045003）；中央高校基本科研业务费基金资助项目（3132014201）.

张树凯（1990⁃），男，博士研究生；

刘正江（1959⁃），男，教授，博士生导师.

张树凯，E⁃mail：zhangshukai1990＠126.com.