基于Douglas?Peucker算法的船舶AIS航跡數(shù)據(jù)壓縮

張樹凱，劉正江，張顯庫，史國友，蔡垚

（大連海事大學(xué)航海學(xué)院，遼寧大連116026）

基于Douglas?Peucker算法的船舶AIS航跡數(shù)據(jù)壓縮

張樹凱，劉正江，張顯庫，史國友，蔡垚

（大連海事大學(xué)航海學(xué)院，遼寧大連116026）

為解決普通模式下，將海量AIS航跡數(shù)據(jù)顯示在ECDIS平臺上效率低、實時性差等問題，設(shè)計一種基于Douglas?Peucker算法的AIS航跡數(shù)據(jù)壓縮算法。通過分析AIS航跡數(shù)據(jù)的特征，總結(jié)普通模式下ECDIS平臺AIS航跡顯示實時性差的原因，提出在保留原始航跡特征和誤差允許的范圍內(nèi)剔除冗余和重復(fù)信息的思想，結(jié)合Douglas?Peucker算法，根據(jù)設(shè)定的不同閾值提取出關(guān)鍵特征點從而對AIS航跡數(shù)據(jù)進行壓縮。在VC2010平臺下對該算法進行實現(xiàn)，實踐證明，該算法能在較低失真度的前提下對船舶AIS航跡數(shù)據(jù)進行壓縮，提高了軌跡回放、再現(xiàn)效率，與普通模式下ECDIS顯示大量AIS航跡相比，系統(tǒng)占用資源少、處理效率高并具有較高的穩(wěn)定性。

船舶；AIS航跡；Douglas?Peucker算法；數(shù)據(jù)壓縮

船載自動識別系統(tǒng)（automatic identification sys?tem，AIS）在船舶導(dǎo)航與監(jiān)控、船舶交通流研究等方面越來越顯示出方便、輕巧的特點。AIS數(shù)據(jù)可以有效疊加到電子海圖上，方便航海人員觀察某一水域交通流的整體態(tài)勢或顯示某條船舶的歷史軌跡［1］。船載AIS設(shè)備一般2 s－6 min發(fā)布一條信息，船舶的歷史軌跡數(shù)據(jù)相當龐大。除了海量數(shù)據(jù)的存儲問題，當把海量AIS數(shù)據(jù)導(dǎo)入到ECDIS平臺觀察交通流的整體態(tài)勢或交通流特征時，由于數(shù)據(jù)量大，系統(tǒng)的處理效率非常低，ECDIS平臺對海圖平移、縮放響應(yīng)的速度也變得十分緩慢。AIS航跡中包含大量重復(fù)和冗余的信息。一方面是船載AIS設(shè)備的發(fā)送頻率較高造成的，例如某條錨泊船可以用2條AIS信息代替在錨泊期間發(fā)送的所有AIS信息；另一方面是由具體應(yīng)用產(chǎn)生的，例如大比例尺海圖下的數(shù)據(jù)用于小比例尺海圖顯示和應(yīng)用時就會存在冗余。為了能夠?qū)崟r的回放AIS的歷史軌跡，如何在較低失真度的前提下壓縮這些冗余和重復(fù)的信息顯得尤為重要。Douglas?Peucker算法現(xiàn)已廣泛應(yīng)用在矢量地圖壓縮、數(shù)字高程模型簡化等方面［2?6］。

本文根據(jù)Douglas?Peucker算法的原理和特點對AIS航跡數(shù)據(jù)進行預(yù)處理，并將其應(yīng)用到AIS航跡數(shù)據(jù)的壓縮；在驗證其可行性的基礎(chǔ)上提出不同比例尺和不同條件下的推薦閾值。

1 Douglas?Peucker壓縮算法原理

1973年，Douglas等提出了一種簡化二維曲線的算法［7］。該算法的核心思想是從構(gòu)成曲線的點集合A中提取出一個能反映曲線總體及局部形態(tài)主要特征的點集A′。

假設(shè)描述曲線的點集A為

以圖1為例說明Douglas?Peucker算法的原理。將首點和尾點分別作為初始錨點和初始漂浮點，并將其連成的直線稱為基線。依次計算中間各點到基線的垂直距離，并找出最大距離對應(yīng)的點。若最大距離小于設(shè)定的閾值，則用基線代替原始曲線。若最大距離大于設(shè)定的閾值，則將最大距離對應(yīng)的點作為分裂點，并將該分裂點作為前向點集的漂浮點和后向點集的錨點。依次遞歸選取分裂點和分段，直到每一個子集中都不再出現(xiàn)新的分裂點。

圖1 Douglas?Peucker算法Fig.1 Douglas?Peucker algorithm

由Douglas?Peucker算法提取出的特征點之所以能夠反映原始曲線的總體和局部特征，是因為活躍的基線始終由當前最有特點的2個點連接而成，而后以基線作為“視平線”去“端詳”最大局部的區(qū)段，并選取該區(qū)段的主要特征點［8?10］。

2 AIS數(shù)據(jù)庫設(shè)計

海量AIS數(shù)據(jù)的存儲和調(diào)用是進行快速壓縮和實時顯示的關(guān)鍵因素。如何快速提取出同一海上移動通信業(yè)務(wù)標識碼（maritime mobile service identify，MMSI）的AIS記錄并按時間順序?qū)氲紻ouglas?Peu?cker算法中進行壓縮是亟需解決的一個關(guān)鍵問題。系統(tǒng)采用SQLite數(shù)據(jù)庫，庫結(jié)構(gòu)采用單“TRACK”表建立，單表的每一條記錄包含MMSI、經(jīng)度、緯度和時間4個字段。單表的一條記錄對應(yīng)AIS設(shè)備一次發(fā)送的數(shù)據(jù)。數(shù)據(jù)庫管理方案如圖2所示。

圖2 數(shù)據(jù)庫管理方案Fig.2 Database management

AIS數(shù)據(jù)中的地理位置以經(jīng)緯度形式存儲，在壓縮前，應(yīng)首先將經(jīng)緯度坐標轉(zhuǎn)換為墨卡托坐標，然后轉(zhuǎn)換為屏幕坐標顯示。根據(jù)等角正圓柱投影原理，假設(shè)某點的經(jīng)緯度坐標為（φ，λ），平面坐標為（x，y），則經(jīng)緯度到平面坐標的轉(zhuǎn)換公式為：

式中：r0為基準緯度圈半徑；a為地球橢球長軸半徑；q為等量維度；e為橢球第一偏心率。

3 實例驗證與分析

3.1 數(shù)據(jù)壓縮的實現(xiàn)

SQLite數(shù)據(jù)庫解決了海量AIS數(shù)據(jù)的快速存儲和調(diào)用的問題，但頻繁的調(diào)用依舊會降低處理效率，因此程序使用SQL語句從數(shù)據(jù)庫提取出某一條船舶的AIS航跡后將數(shù)據(jù)映射到結(jié)構(gòu)體數(shù)組std：：vec?tor＜POINT＞中，這樣引用結(jié)構(gòu)體數(shù)組就相當于引用數(shù)據(jù)庫中的數(shù)據(jù)［11］。在內(nèi)存中建立的數(shù)據(jù)結(jié)構(gòu)及作用如表1所示，整體實現(xiàn)流程如圖3所示。

表1 算法中用到的數(shù)據(jù)類型Table 1 Data type used in algorithm

圖3 整體實現(xiàn)流程Fig.3 Workflow of implementation

3.2 實例分析

為了驗證Douglas?Peucker算法壓縮AIS數(shù)據(jù)的有效性和效率問題，以瓊海海峽VTS中心AIS基站10月某日收到的數(shù)據(jù)作為測試數(shù)據(jù)。該數(shù)據(jù)包括224條船舶的AIS軌跡，共計953 203對坐標點。分別采用0～2 m之間不同的閾值進行壓縮，得到相應(yīng)的壓縮后特征點和壓縮率，如表2所示。

表2 不同閾值下的特征點數(shù)和壓縮率Table 2 Number of feature points and compression rates in different thresholds

從表2可以看出，隨著閾值的增大，壓縮后特征點越來越少，壓縮率越來越大。當閾值為0.5 m時，壓縮率達到49.22%，也就是說可用原始航跡一半的點數(shù)代替原始航跡且絕對誤差限小于0.5 m，在保證原始航跡特征和精度的基礎(chǔ)上數(shù)據(jù)壓縮率相當可觀。

為了更加直觀、形象的展示壓縮效果，隨機選取224艘船中的一艘進行觀察。從SQLite數(shù)據(jù)庫中選取MMSI為563156000的船舶AIS軌跡，將壓縮閾值分別設(shè)置為0.2 m和2.0 m進行壓縮。該船共有原始點8 155個，壓縮后特征點分別為5 900個和1 247個，壓縮率分別為27.65%和84.71%。將壓縮后的特征點轉(zhuǎn)換為S57格式，分別導(dǎo)入到ECDIS平臺顯示，海圖比例尺為1：1 000 000，顯示效果如圖4所示。通過觀察可知：雖然壓縮率相差較大，但顯示在ECDIS平臺上時并無明顯差異。

如圖5所示，提取出MMSI為563156000的船舶AIS數(shù)據(jù)，分別將閾值設(shè)置為2、20、200 m和2 000 m進行壓縮，將壓縮后的特征點用小方塊表示并顯示在1∶1 000 000海圖上。由圖可知，閾值為2 m時特征點過于密集；閾值為2 000 m時特征點過于稀松，表示原始軌跡特征的能力較差；閾值為20 m時特征點疏密程度較為適宜；閾值為200 m時較為稀松，表示單船原始航跡特征的能力相對較差，但對于觀察交通流的宏觀態(tài)勢是足夠的，而且占用系統(tǒng)資源少，顯示實時性高，對海圖操作的響應(yīng)快。如圖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 不同閾值下交通流整體態(tài)勢Fig.6 The overall state of traffic flow in different thresholds

在大比例尺海圖下表述船舶運動行為和特征的最小點集在小比例尺海圖下顯示時必然存在冗余。因此，為了在不同的比例尺海圖下顯示船舶的AIS軌跡，同時加快顯示效率，需要根據(jù)不同的比例尺設(shè)定不同的閾值。

3.3 推薦閾值

由3.2實例分析可知，在同一比例尺下選擇不同的閾值進行壓縮可得到不同的效果，用戶可根據(jù)需要選擇不同的閾值進行壓縮，例如，觀察整個海域的交通流整體態(tài)勢時可將閾值設(shè)置得大一點，觀察某一艘船舶的運動軌跡特征時可以將閾值設(shè)定得小一點。在不同的比例尺下根據(jù)設(shè)定的不同閾值進行壓縮也會得到不同的效果，用于大比例尺海圖下顯示船舶軌跡的點在小比例尺海圖下肯定會存在冗余，因此在小比例海圖下進行壓縮時應(yīng)將閾值設(shè)置得大一些，在大比例尺海圖下進行壓縮時應(yīng)該閾值設(shè)置得小一些。

表3 1－20 m不同閾值下的特征點數(shù)和壓縮率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可知，當設(shè)定的閾值為16～20 m時，壓縮率已經(jīng)高達97.03%，之后隨著設(shè)定的閾值的增大，壓縮率并沒有明顯提高。通過圖7也可看出，當閾值分別設(shè)定為1～20 m時，后一閾值較前一閾值壓縮率的增大情況在16 m時已經(jīng)非常小。且隨著閾值越大，壓縮后的點表征原始軌跡特點的能力越差，失真度越大。因此建議在觀察單船AIS軌跡特征時設(shè)定閾值的上限為16 m，當閾值比16 m大時，壓縮率不會明顯增加，但失真度會增大；在觀察宏觀交通流特征時可將閾值適當擴大。

根據(jù)海圖的用途不同可將海圖分為總圖、航行圖和港灣圖，航行圖又包括遠洋航行圖、近海航行圖和沿岸航行圖。根據(jù)大量實驗的結(jié)果，表4給出了不同比例尺下的推薦最佳閾值，用戶可根據(jù)實際情況適當調(diào)整。

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

4 結(jié)論

1）在ECDIS平臺顯示海量AIS數(shù)據(jù)時，處理這些數(shù)據(jù)會花費很長時間，不僅使顯示的時效性受到影響，而且ECDIS對海圖的平移、縮放等操作的響應(yīng)速度會大大減慢。本文將簡化矢量要素的經(jīng)典算法Douglas?Peucker算法應(yīng)用于壓縮AIS數(shù)據(jù)，大幅度提高了顯示的實時性和海圖操作的快速響應(yīng)。

2）將Douglas?Peucker算法的閾值設(shè)置為200 m對AIS航跡數(shù)據(jù)進行壓縮，通過觀察實驗結(jié)果可知，壓縮后的AIS航跡仍然能夠較好的展示出整體交通流的態(tài)勢。另外，由于壓縮率高達99%，大大提高了處理效率。用戶可根據(jù)不同的需要和精度要求設(shè)置不同閾值壓縮AIS航跡數(shù)據(jù)，在保持原始數(shù)據(jù)特征和誤差允許的范圍內(nèi)剔除原始數(shù)據(jù)中重復(fù)和冗余的信息。

3）通過初步的實驗分析，本文提出的基于Douglas?Pecuker算法的AIS航跡數(shù)據(jù)壓縮算法可根據(jù)不同的比例尺、用戶的要求和精度進行有效的壓縮，算法簡單，壓縮率和表征原始軌跡的能力令人滿意。下一步的工作將把速度和時間要素考慮在內(nèi)，建立基于三維Douglas?Peucker算法的AIS航跡數(shù)據(jù)壓縮算法。

［1］初秀民，徐海潮，萬劍，等.基于多線程的船載自動識別系統(tǒng)報文解析［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綜合中的應(yīng)用［J］.武漢大學(xué)學(xué)報：信息科學(xué)版，2008，33（2）：160?163.

HE Jin，F(xiàn)EI 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］.哈爾濱工程大學(xué)學(xué)報，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］張興福，黃少濱.自適應(yīng)近鄰的局部線性嵌入算法［J］.哈爾濱工程大學(xué)學(xué)報，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.網(wǎng)絡(luò)出版時間：2015?04?14.

國家自然科學(xué)基金資助項目（51309041）；國家863計劃基金資助項目（2009AA045003）；中央高校基本科研業(yè)務(wù)費基金資助項目（3132014201）.

張樹凱（1990?），男，博士研究生；

劉正江（1959?），男，教授，博士生導(dǎo)師.

張樹凱，E?mail：zhangshukai1990＠126.com.