江海洋，高 超，馬 勇

（1.武漢理工大學(xué)航運(yùn)學(xué)院，武漢 430063；2.中國艦船研究設(shè)計(jì)中心，武漢 430063）

1 引言

船舶自動識別系統(tǒng)（Automatic Identification System,AIS）軌跡數(shù)據(jù)中蘊(yùn)含著大量信息[1-4]，包括船舶的靜態(tài)和動態(tài)信息、船舶駕駛員的人為因素、船舶避碰行為、船員通常做法和習(xí)慣航路等。通過分析和研究船舶軌跡，可獲取能夠反映船舶規(guī)律的有效和潛在信息，進(jìn)而為海上安全監(jiān)管、船舶通航、航海保障等活動提供必要的數(shù)據(jù)支持[5-6]。然而，海量的AIS 數(shù)據(jù)中存在一些利用價(jià)值較低的數(shù)據(jù)點(diǎn)，當(dāng)移除此類數(shù)據(jù)后船舶軌跡不會產(chǎn)生改變。由此，為提高數(shù)據(jù)的利用效率，需要對冗雜的船舶AIS 軌跡數(shù)據(jù)進(jìn)行壓縮處理。

通常，包括道格拉斯–普克（Douglas-Peucker,DP）在內(nèi)的多數(shù)船舶軌跡壓縮算法往往僅考慮軌跡的距離偏移量來壓縮軌跡[7]，在壓縮過程中舍棄了船舶航速、航向改變、進(jìn)出某區(qū)域邊界等航跡特征點(diǎn)，得到的軌跡忽略了船舶的動態(tài)信息，降低了數(shù)據(jù)的利用價(jià)值；少部分壓縮算法通過航向、航速變化率均值來保留船舶軌跡特征點(diǎn)[8-10]，但忽略了由傳感器誤差導(dǎo)致的航速、航向出現(xiàn)的小范圍波動，進(jìn)而保留了波動點(diǎn)，使得壓縮后保留的數(shù)據(jù)點(diǎn)過多；極少數(shù)壓縮算法雖然考慮了船舶的時(shí)空特性[11-13]，但僅將時(shí)間特性作為分類和排序的指標(biāo)，一般壓縮后的軌跡失真率較高。

為提升軌跡壓縮算法質(zhì)量，充分應(yīng)用船舶動態(tài)特征點(diǎn)（Feature Point,FP）數(shù)據(jù)以及時(shí)空特性（Temporal and Spatial,TS），在DP 算法的基礎(chǔ)上提出FP-TSDP 船舶軌跡壓縮算法。對比結(jié)果表明，經(jīng)FP-TSDP 算法壓縮后的軌跡質(zhì)量得到較好的提升。

2 AIS 數(shù)據(jù)解碼與預(yù)處理

AIS 數(shù)據(jù)分析主要包括數(shù)據(jù)解碼、數(shù)據(jù)預(yù)處理和數(shù)據(jù)挖掘3 個(gè)步驟。數(shù)據(jù)預(yù)處理包括軌跡異常點(diǎn)清除和船舶軌跡壓縮環(huán)節(jié)，經(jīng)過預(yù)處理的數(shù)據(jù)，較為精簡，具有較高的實(shí)用性和使用價(jià)值。

2.1 AIS 數(shù)據(jù)解碼

AIS 報(bào)文信息是一串復(fù)雜晦澀的字符串，封裝度極高，難以被人們直接理解和應(yīng)用，為獲取直觀信息，需要解碼原始信息。數(shù)據(jù)中的每個(gè)記錄點(diǎn)代表一個(gè)由船載AIS 設(shè)備在某個(gè)瞬間發(fā)出的AIS 報(bào)告信息。

AIS 數(shù)據(jù)解碼主要由3 個(gè)階段實(shí)現(xiàn)[14]。首先，將AIS 原始數(shù)據(jù)轉(zhuǎn)換為ASCII 碼。然后，將ASCII碼值與16 進(jìn)制數(shù)80H 相比較，如果大于80H，則轉(zhuǎn)換出的ASCII 碼值加上20H；如果小于80H，則轉(zhuǎn)換的ASCII 碼值加上28H。經(jīng)變換，原來的ASCII 碼變成了6 位ASCII 碼。單條信息轉(zhuǎn)換后全長最大為168bit，每個(gè)字符都是轉(zhuǎn)換后6bit 的ASCII 碼，從字符“1”開始為有效信息。最后，參照AIS 國際標(biāo)準(zhǔn)信息對照表，解析出對應(yīng)信息。解碼后的信息是一連串由數(shù)字0 和1 組成的二進(jìn)制編碼，需對比國際AIS 制定的標(biāo)準(zhǔn)協(xié)議，利用27 種電文的格式分配相應(yīng)的比特位，拼接信息后解析出AIS 信息。

2.2 AIS 數(shù)據(jù)預(yù)處理

經(jīng)數(shù)據(jù)解碼后的AIS 數(shù)據(jù)不能直接使用，主要是存在許多異常數(shù)據(jù)，會影響船舶軌跡壓縮的結(jié)果。為保證數(shù)據(jù)的準(zhǔn)確性，需要對AIS 數(shù)據(jù)進(jìn)行異常數(shù)據(jù)處理工作。AIS 數(shù)據(jù)主要有3 種異常情況。其一，存在靜態(tài)信息輸入錯(cuò)誤和部分信息未輸入的情況；其二，存在船舶航次相關(guān)信息輸入錯(cuò)誤或信息未輸入的情況；其三，存在因傳感器故障，導(dǎo)致船舶動態(tài)信息出現(xiàn)錯(cuò)誤的情況。

由此，針對解碼后的數(shù)據(jù)，需要開展AIS 數(shù)據(jù)篩選預(yù)處理工作[15]，即需要?jiǎng)h除AIS 報(bào)告信息MMSI 記錄為0 的點(diǎn)；刪除數(shù)據(jù)中偏離所選水域航道較遠(yuǎn)的點(diǎn)，如經(jīng)緯度顯著超出航道，速度出現(xiàn)負(fù)值或超出正常值；刪除時(shí)間相鄰的2 個(gè)AIS報(bào)告點(diǎn)距離超過實(shí)際可能最大值的軌跡點(diǎn)。在數(shù)據(jù)預(yù)處理階段，刪除無效的、不合理的、偏離航道的數(shù)據(jù)，確保獲得有效的AIS 數(shù)據(jù)。

出于安全考慮，國際海事組織要求AIS 數(shù)據(jù)點(diǎn)的報(bào)告間隔較短。經(jīng)過上述篩選處理的AIS 數(shù)據(jù)規(guī)模非常大，直接使用導(dǎo)致運(yùn)算速度緩慢，難以得到有效應(yīng)用。為此，需要對AIS 數(shù)據(jù)進(jìn)行壓縮處理。傳統(tǒng)DP 壓縮算法[16]根據(jù)距離閾值來判定。在DP 算法中，通常將軌跡的起點(diǎn)和終點(diǎn)連成直線，計(jì)算軌跡上每個(gè)點(diǎn)到這條直線的距離，選擇其中距離最大的點(diǎn)，將其距離與預(yù)設(shè)的距離閾值進(jìn)行比較，小于距離閾值，則舍棄這條直線兩側(cè)的點(diǎn)，若大于距離閾值，則保留這個(gè)點(diǎn)；然后，將起點(diǎn)和終點(diǎn)分別同這個(gè)點(diǎn)進(jìn)行連線，得到兩條直線，再分別重復(fù)上述步驟，迭代計(jì)算，直至所有點(diǎn)到對應(yīng)直線的距離都小于距離閾值，則完成壓縮?？芍?，上述方法壓縮出來的軌跡，動態(tài)信息丟失較多、軌跡失真率較高，有必要設(shè)計(jì)一種高質(zhì)量的船軌跡壓縮算法。

3 船舶軌跡壓縮FP-TSDP 算法

3.1 特征點(diǎn)優(yōu)化

傳統(tǒng)DP 算法一般僅通過距離偏移量來壓縮軌跡，會導(dǎo)致在壓縮過程中舍棄部分船舶的動態(tài)信息、航速及航向改變、進(jìn)出某區(qū)域邊界等航跡特征點(diǎn)，降低了數(shù)據(jù)的利用價(jià)值。因此，在DP算法的基礎(chǔ)上，需要優(yōu)化軌跡特征點(diǎn)，開展提取和保留特征點(diǎn)研究工作。

針對船舶航速、航向改變點(diǎn)的提取保留工作，可通過判斷各數(shù)據(jù)點(diǎn)的船舶航速、航向改變率是否高于某一設(shè)定閾值來實(shí)現(xiàn)。

船舶航速改變率及航向改變率的示意圖如圖1所示，其中，Bi-1,Bi,Bi+1為連續(xù)的3 個(gè)數(shù)據(jù)點(diǎn)，Vin,Vout分別為航段Bi-1Bi,BiBi+1上的平均航速，COGin,COGout分別為Bi-1Bi,BiBi+1上的平均航向。

圖1 船舶航速改變率和航向改變率計(jì)算示意圖Fig.1 Schematic diagram of calculating of ship speed change rate and course change rate

各數(shù)據(jù)點(diǎn)的船舶航速、航向改變率分別由式(1)、(2)計(jì)算得出[17]。

在確定閾值的過程中，首先由式(3)、(4)計(jì)算整體數(shù)據(jù)全航程的平均航速改變率以及平均航向改變率；考慮到船載AIS 設(shè)備傳感器精度的限制，航速和航向數(shù)據(jù)會存在小范圍的波動，如以平均改變率作為閾值，可能會將此類波動點(diǎn)視為航速改變、航向改變的軌跡特征點(diǎn)而保留下來，導(dǎo)致壓縮后數(shù)據(jù)量依然龐大；通過多次測驗(yàn)分析引入擴(kuò)大系數(shù)M,N，其中9≤M≤11,3≤N≤5。分別對平均航速改變率和平均航向改變率進(jìn)行M和N倍擴(kuò)大處理，在接近原始軌跡的同時(shí)可顯著縮小數(shù)據(jù)量。

船舶駛?cè)?出行為[18]包括駛?cè)?出碼頭、錨地、橋區(qū)水域、漁區(qū)水域、環(huán)形道等閉合區(qū)域以及航道、危險(xiǎn)線、邊界線等非閉合區(qū)域。船舶駛?cè)?出軌跡特征點(diǎn)是指船舶通過上述非閉合區(qū)域邊界線前后的AIS 數(shù)據(jù)點(diǎn)。對于此類軌跡特征點(diǎn)，可以通過判斷相鄰兩個(gè)AIS 數(shù)據(jù)點(diǎn)分別代入邊界線方程后值的乘積是否小于0。若小于0，則標(biāo)記并保留為船舶進(jìn)出某區(qū)域軌跡點(diǎn)，構(gòu)成進(jìn)出某區(qū)域點(diǎn)集合。

DP 算法特征點(diǎn)優(yōu)化即通過上述方法，對軌跡中的特征點(diǎn)進(jìn)行識別保留，以特征點(diǎn)為DP 算法輸入的初始點(diǎn)進(jìn)行軌跡壓縮。經(jīng)過特征點(diǎn)優(yōu)化后的DP 算法進(jìn)行軌跡壓縮，壓縮后的軌跡保留了這些軌跡特征點(diǎn)，關(guān)鍵信息含量高于傳統(tǒng)DP 算法進(jìn)行壓縮后的軌跡，輪廓特征更加接近于原始軌跡，具有較高的利用價(jià)值。

3.2 時(shí)空特性優(yōu)化

AIS 數(shù)據(jù)的時(shí)空特性[19]，如圖2所示，圖中為時(shí)刻船舶的位置，對此段軌跡進(jìn)行壓縮，的連線為預(yù)期直線軌跡，為計(jì)算到預(yù)期直線軌跡歐式距離對應(yīng)的船位，為時(shí)刻預(yù)期直線軌跡上實(shí)際的船位。不難看出，在預(yù)期軌跡上偏移點(diǎn)所對應(yīng)的實(shí)際預(yù)期船位應(yīng)在偏移點(diǎn)計(jì)算到預(yù)期軌跡線歐式距離的船位之前。傳統(tǒng)DP 算法計(jì)算軌跡的偏移量的方式往往采用歐式幾何上的垂直距離，此距離略小于時(shí)空偏移距離，使用此距離進(jìn)行壓縮，雖然壓縮后數(shù)據(jù)量較小，但壓縮后軌跡的失真率較高。因此，在DP 算法的基礎(chǔ)上，需要進(jìn)行時(shí)空特性優(yōu)化，計(jì)算偏移船位與實(shí)際預(yù)期船位的時(shí)空距離，以時(shí)空距離對比DP 算法距離閾值進(jìn)行偏移點(diǎn)的取舍。

圖2 時(shí)空特性優(yōu)化原理Fig.2 Principle of optimization using time and space characteristics

時(shí)空距離計(jì)算方法如下：連接每個(gè)分段航跡的起點(diǎn)和終點(diǎn)，并根據(jù)起點(diǎn)與終點(diǎn)的經(jīng)度，緯度轉(zhuǎn)換后的墨卡托坐標(biāo)系坐標(biāo)和時(shí)間建立虛擬直線時(shí)空軌跡，對每個(gè)子軌跡段，計(jì)算該子軌跡段AIS數(shù)據(jù)點(diǎn)在虛擬直線時(shí)空軌跡上同時(shí)刻點(diǎn)的墨卡托坐標(biāo)系坐標(biāo)，將該子軌跡段的AIS 數(shù)據(jù)點(diǎn)的墨卡托坐標(biāo)系坐標(biāo)與該AIS 數(shù)據(jù)點(diǎn)在虛擬直線時(shí)空軌跡上同時(shí)刻點(diǎn)的墨卡托坐標(biāo)系坐標(biāo)之間的距離作為該AIS 數(shù)據(jù)點(diǎn)到虛擬直線時(shí)空軌跡的時(shí)空距離，即為。

3.3 FP-TSDP 算法流程

通過上述特征點(diǎn)優(yōu)化與時(shí)空特性優(yōu)化，提出FP-TSDP 算法流程，流程圖如圖3所示。

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

FP-TSDP 算法具體實(shí)現(xiàn)步驟如下：

（1）識別并保留AIS 時(shí)序性數(shù)據(jù)記錄中的船舶航向和航速的改變點(diǎn)，船舶駛?cè)?出某區(qū)域特征點(diǎn)，分別記錄到航速改變點(diǎn)集合S，航向改變點(diǎn)集合C，駛?cè)?出某區(qū)域特征點(diǎn)集合E；

（2）設(shè)置距離閾值dT，以船舶軌跡的起點(diǎn)、終點(diǎn)以及集合S、E、C中的特征軌跡點(diǎn)為初始點(diǎn)對軌跡進(jìn)行分段標(biāo)記，相鄰兩個(gè)軌跡特征點(diǎn)之間的軌跡為一個(gè)子軌跡段；

（3）連接每個(gè)分段航跡的起點(diǎn)和終點(diǎn)，并根據(jù)起點(diǎn)與終點(diǎn)的經(jīng)度，緯度轉(zhuǎn)換后的墨卡托坐標(biāo)系坐標(biāo)和時(shí)間建立虛擬直線時(shí)空軌跡。對每個(gè)子軌跡段，計(jì)算該子軌跡段AIS 數(shù)據(jù)點(diǎn)在虛擬直線時(shí)空軌跡上同時(shí)刻點(diǎn)的墨卡托坐標(biāo)系坐標(biāo)，將該子軌跡段AIS 數(shù)據(jù)點(diǎn)的墨卡托坐標(biāo)系坐標(biāo)與該AIS 數(shù)據(jù)點(diǎn)在虛擬直線時(shí)空軌跡上同時(shí)刻點(diǎn)的墨卡托坐標(biāo)系坐標(biāo)之間的距離作為該AIS 數(shù)據(jù)點(diǎn)到虛擬直線時(shí)空軌跡的時(shí)空距離d，找到所有時(shí)空距離中的最大距離dmax，比較該最大距離與預(yù)設(shè)距離閾值dT的大??；

（4）如果dmax＜dT，則該子軌跡段上所有中間數(shù)據(jù)點(diǎn)全部舍掉，舍掉所有中間點(diǎn)后，連接該子軌跡段起點(diǎn)和終點(diǎn)的直線就作為該子軌跡段的近似，該段子軌跡處理完畢；

（5）如果dmax＞dT，則對應(yīng)最大距離的AIS數(shù)據(jù)點(diǎn)應(yīng)保留為結(jié)果軌跡上的數(shù)據(jù)點(diǎn)，同時(shí)通過對應(yīng)最大距離的AIS 數(shù)據(jù)點(diǎn)將該段子軌跡分為兩部分，對這兩部分曲線分別采用步驟（3）和步驟（4）進(jìn)行處理，直到所有的dmax＜dT；

（6）當(dāng)所有子軌跡段處理完后，依次連接各分割點(diǎn)形成的軌跡，即為原軌跡壓縮后的近似軌跡。壓縮過程示意圖如圖4所示，如圖中①表示起始點(diǎn)和特征點(diǎn)劃分子軌跡段以及子軌跡段時(shí)空插值的結(jié)果，圖中②～⑤表示各子軌跡段的處理流程，圖⑥表示對①中軌跡最終處理結(jié)果。

圖4 FP-SPDP 算法壓縮軌跡過程示意圖Fig.4 Schematic diagram of the trajectory compression process of the FP-SPDP algorithm

4 仿真結(jié)果及分析

長江武漢段屬于長江中游與下游的交接段，是長江中下游水運(yùn)的重要中轉(zhuǎn)站，水運(yùn)較為繁忙，AIS 基站僅一天接收到的AIS 數(shù)據(jù)就有15 萬條之多。水域內(nèi)橋區(qū)多、港區(qū)和停泊區(qū)多，增加了船舶在水域內(nèi)航行的安全隱患。為提升利用AIS 數(shù)據(jù)對船舶軌跡的分析研究，可以從中獲取能夠反映船舶規(guī)律的、有效的、潛在的信息，進(jìn)而為海事機(jī)關(guān)對船舶違章行為監(jiān)管，修訂航行規(guī)則，推行船舶定線制提供有效的數(shù)據(jù)支持。為提升數(shù)據(jù)利用效率，需要對數(shù)據(jù)進(jìn)行壓縮處理。

本文分別使用傳統(tǒng)DP 算法和本文進(jìn)行優(yōu)化過的DP 算法，對長江武漢段2016年8月9日當(dāng)天所采集AIS 數(shù)據(jù)，原始軌跡點(diǎn)總計(jì)146789 個(gè)，作為原始數(shù)據(jù)進(jìn)行壓縮實(shí)驗(yàn)，距離閾值均為100，特征點(diǎn)優(yōu)化擴(kuò)大系數(shù)M為10，N為5。原始船舶軌跡圖如圖5所示，總體壓縮結(jié)果如圖6 和圖7所示，單船壓縮結(jié)果如圖8 和圖9所示。傳統(tǒng)DP算法壓縮后保留軌跡點(diǎn)12272 個(gè)，壓縮率（壓縮后軌跡點(diǎn)數(shù)量/原始軌跡點(diǎn)數(shù)量）為8.36%，優(yōu)化DP 算法壓縮后保留軌跡點(diǎn)數(shù)量17703 個(gè)，壓縮率為12.06%。

圖6 傳統(tǒng)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，可以明顯看出傳統(tǒng)DP 算法壓縮后有一段軌跡丟失，F(xiàn)P-TSDP 算法壓縮后的軌跡與原始軌跡更為相近；如圖8 和圖9所示，傳統(tǒng)DP 算法壓縮后軌跡點(diǎn)較少，但特征點(diǎn)缺失較多，F(xiàn)P-TSDP 算法所得到的軌跡更加平滑，接近于原始軌跡，且特征點(diǎn)保留完整。在圖 8 和圖 9的基礎(chǔ)上增加一個(gè)維度表示船舶速度，分別做出兩種方法軌跡壓縮后單船軌跡–速度復(fù)合曲線，如圖10 和圖11所示。對比分析圖10 和圖11，可看出傳統(tǒng)軌跡壓縮方法壓縮后的軌跡中船舶航速改變點(diǎn)明顯少于FP-TSDP 算法壓縮后的船舶軌跡，同時(shí)大部分軌跡特征點(diǎn)偏離復(fù)合曲線。

圖5 原始船舶軌跡圖Fig.5 Original ship trajectory map

圖8 傳統(tǒng)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 傳統(tǒng)DP 算法壓縮后單船軌跡-速度復(fù)合曲線Fig.10 Single ship trajectory-speed compound curve compressed by traditional DP algorithm

圖11 FP-TSDP 算法壓縮后的單船軌跡-速度復(fù)合曲線Fig.11 Single ship trajectory-speed compound curve compressed by FP-TSDP algorithm

5 結(jié)論

針對船舶AIS 數(shù)據(jù)中無用數(shù)據(jù)點(diǎn)的剔除問題，本文對傳統(tǒng)DP 算法進(jìn)行了特征點(diǎn)優(yōu)化和時(shí)空特性優(yōu)化，提出了基于FP-TSDP 算法的船舶AIS 軌跡壓縮方法。實(shí)驗(yàn)結(jié)果表明，在保證一定壓縮率的前提下，F(xiàn)P-TSDP 算法充分考慮了特征軌跡點(diǎn)的保留問題，對船舶行駛中加速、減速、轉(zhuǎn)向、進(jìn)出特殊區(qū)域等重要的動態(tài)行為點(diǎn)較完整地進(jìn)行保留。同時(shí)，利用時(shí)空距離壓縮軌跡，較好地保留了原始軌跡的形狀。通過FP-TSDP 算法簡化后的數(shù)據(jù)較為簡潔，且有較大的二次利用價(jià)值。