基于改進(jìn)滑動(dòng)窗口的漁船AIS軌跡數(shù)據(jù)壓縮算法

董婉婷，于紅、2、3*，周弈志，張方言，梁亮，盧曉黎

(1.大連海洋大學(xué) 信息工程學(xué)院，遼寧 大連 116023; 2.設(shè)施漁業(yè)教育部重點(diǎn)實(shí)驗(yàn)室，遼寧 大連 116023; 3.遼寧省海洋信息技術(shù)重點(diǎn)實(shí)驗(yàn)室，遼寧 大連 116023)

漁船是一種重要的海洋漁業(yè)生產(chǎn)工具，漁船的運(yùn)行軌跡中包含了漁船的時(shí)空分布信息[1]，通過分析漁船軌跡數(shù)據(jù)可以發(fā)現(xiàn)漁船的運(yùn)動(dòng)規(guī)律、行為模式、作業(yè)方式等[2]，對(duì)精準(zhǔn)掌握漁船作業(yè)行為[3]、保障漁船作業(yè)安全[4]、發(fā)現(xiàn)漁船異常行為、規(guī)范漁業(yè)執(zhí)法等具有重要意義[5]。

船舶自動(dòng)識(shí)別系統(tǒng)(Automatic Identification System,AIS)是強(qiáng)制在客船、貨船、自航船舶和港作拖船上配備的一種船載裝置[6]，目的在于識(shí)別和跟蹤船舶，避免船舶碰撞，保障航行安全[7]。AIS系統(tǒng)借助GPS和傳感器向岸基站和其他船舶發(fā)送船名、呼號(hào)等靜態(tài)信息和船位、航向、航速等動(dòng)態(tài)信息[8]，其中船位信息能夠較好地描述船舶的軌跡，是船舶軌跡數(shù)據(jù)的主要來源之一[9]，因此，通過挖掘AIS數(shù)據(jù)進(jìn)行船舶軌跡分析成為船舶軌跡分析的重要方法之一[10]。由于AIS數(shù)據(jù)的發(fā)布頻率很高，通常為幾秒到幾分鐘發(fā)布一條[11]，系統(tǒng)中產(chǎn)生了海量的AIS數(shù)據(jù)，大大增加了數(shù)據(jù)存儲(chǔ)和分析的工作量，因此，需要有效的AIS軌跡數(shù)據(jù)壓縮算法對(duì)海量AIS軌跡數(shù)據(jù)進(jìn)行處理[12]。

軌跡數(shù)據(jù)壓縮是指利用壓縮算法將軌跡簡(jiǎn)化，去掉冗余的點(diǎn)，在確保不丟失軌跡特征信息的基礎(chǔ)上盡可能降低存儲(chǔ)代價(jià)[13]。Douglas等[14]提出Douglas-Peucker算法(簡(jiǎn)稱為D-P)，算法核心是連接初始軌跡的起點(diǎn)和終點(diǎn)，計(jì)算所有的點(diǎn)到直線的距離，再與固定閾值做比對(duì)，通過迭代用若干個(gè)線段代替原始軌跡，但該算法無法壓縮動(dòng)態(tài)信息。為此，李名等[15]提出動(dòng)態(tài)D-P算法，在D-P算法基礎(chǔ)上加入時(shí)間維，將原始軌跡按停泊點(diǎn)分段后在三維空間進(jìn)行壓縮，保留了更多軌跡特征，但是分段后的每段軌跡仍使用經(jīng)典D-P算法，算法效率上沒有突破。張樹凱等[16]對(duì)比了不同閾值下經(jīng)典D-P算法的壓縮率，得出不同的閾值可得到不同的壓縮效果，不同的海域條件可以選擇不同的閾值壓縮。徐凱等[17]在動(dòng)態(tài)D-P算法基礎(chǔ)上提出快速D-P算法，將算法對(duì)應(yīng)到向量空間中，利用向量的幾何性質(zhì)對(duì)算法做出改善。由于D-P算法需要明確軌跡的起點(diǎn)和終點(diǎn)，不適用于實(shí)時(shí)數(shù)據(jù)，且復(fù)雜度較高[18]。Keogh等[19]提出Sliding Window算法(簡(jiǎn)稱為SW)，主要思想就是從軌跡起點(diǎn)開始，初始化一個(gè)大小固定的窗口，以數(shù)據(jù)流的形式逐步輸入軌跡點(diǎn)，應(yīng)用逐步壓縮的思想實(shí)現(xiàn)在線壓縮。高邈等[20]對(duì)SW算法進(jìn)行改進(jìn)，加入風(fēng)流壓差角來降低誤差，但局部處理考慮不到部分特征點(diǎn)對(duì)軌跡形態(tài)的重要性。宋鑫等[21]提出動(dòng)態(tài)閾值結(jié)合全局優(yōu)化的壓縮算法，通過停留點(diǎn)將軌跡分為若干個(gè)軌跡段后獲取特征點(diǎn)，再利用改進(jìn)SPM算法進(jìn)行全局優(yōu)化。

上述軌跡壓縮算法多數(shù)在利用船位信息的基礎(chǔ)上使用了AIS數(shù)據(jù)中提供的航速、航向和航行狀態(tài)等信息，對(duì)于壓縮AIS數(shù)據(jù)質(zhì)量較高的商船軌跡數(shù)據(jù)能夠取得較好的效果。但在對(duì)漁船AIS數(shù)據(jù)進(jìn)行分析過程中發(fā)現(xiàn)存在屬性數(shù)據(jù)丟失問題，如漁船在兩個(gè)相鄰時(shí)間點(diǎn)上的位置信息發(fā)生了較大變化，理論上講該漁船的速度和航向大于0，但是獲取的AIS數(shù)據(jù)中速度和航向數(shù)值卻為0，這樣利用航速、航向等屬性信息的軌跡壓縮算法不能實(shí)現(xiàn)對(duì)漁船軌跡的有效壓縮。此外，漁船在捕撈作業(yè)過程中會(huì)以較慢的速度航行，特別是可能在某個(gè)區(qū)域來回慢速航行，所以漁船軌跡的壓縮需要保留更多的特征點(diǎn)，這些特征點(diǎn)可能是后續(xù)進(jìn)行軌跡分析的重要指標(biāo)。因此，需要針對(duì)漁船軌跡的特點(diǎn)研究有效的漁船軌跡數(shù)據(jù)壓縮算法。

本研究中針對(duì)漁船軌跡數(shù)據(jù)的特點(diǎn)，提出一種改進(jìn)滑動(dòng)窗口的漁船AIS軌跡壓縮算法，利用相鄰軌跡點(diǎn)之間的經(jīng)緯度變化狀態(tài)信息提取特征點(diǎn)，在算法中加入時(shí)間維，選擇屬性中的時(shí)間、經(jīng)度、緯度屬性，舍棄存在不確定性的屬性，在保留特征點(diǎn)的同時(shí)，對(duì)密度較高的軌跡點(diǎn)進(jìn)一步壓縮，以實(shí)現(xiàn)停滯點(diǎn)直接壓縮、運(yùn)動(dòng)點(diǎn)按比例壓縮、作業(yè)點(diǎn)盡量保留的壓縮目標(biāo)。

1 數(shù)據(jù)特點(diǎn)與相關(guān)定義

1.1 漁船AIS軌跡數(shù)據(jù)特點(diǎn)分析

漁船AIS軌跡數(shù)據(jù)中主要包括靜態(tài)信息和動(dòng)態(tài)信息，靜態(tài)信息包括船的信息識(shí)別碼(MMSI)等，動(dòng)態(tài)信息包括對(duì)地航速、船首向、航行狀態(tài)、實(shí)時(shí)船位(經(jīng)度、緯度)等[22]，對(duì)船舶軌跡的信息屬性解析如表1所示。

相對(duì)于在海上有固定航道的商船，漁船的軌跡數(shù)據(jù)有以下幾個(gè)特點(diǎn)：

(1)數(shù)據(jù)點(diǎn)密度高。漁船捕撈作業(yè)過程中會(huì)在作業(yè)區(qū)域內(nèi)以很慢的速度航行，在作業(yè)區(qū)停留時(shí)間較長(zhǎng)，這將導(dǎo)致在作業(yè)區(qū)內(nèi)漁船的AIS軌跡點(diǎn)分布密集，產(chǎn)生大量的軌跡數(shù)據(jù)，這將浪費(fèi)存儲(chǔ)資源和計(jì)算資源，每個(gè)軌跡點(diǎn)對(duì)應(yīng)了一條數(shù)據(jù)。

表1 AIS軌跡信息表

Tab.1 Information on automatic identification system(AIS) trajectory

名稱attribute英文全稱(中文釋義)full name(Chinese an-notation)備注noteMMSIMessage ID(信息識(shí)別碼)NAVSTATUSNavigation status(航行狀態(tài))0=動(dòng)力航行中, 1=錨泊, 2=未受令, 3=機(jī)動(dòng)性受限, 4=受吃水限制, 5=錨鏈系泊, 6=擱淺, 7=捕撈中, 8=風(fēng)帆動(dòng)力航行, 9～15為未來保留ROTRate of turn(轉(zhuǎn)向率)SOGSpeed over ground(對(duì)地航速)以1/10節(jié)距為單位, 1023=無, 1022=102.2節(jié)POSSACCPosition accuracy(船位精確度)1=高精度(差分式), 0=低精度LONlongitude(經(jīng)度)LATlatitude(緯度)COGCourse over ground(對(duì)地航向)TRUEHEADING(船首真航向)TIMESTAMP(時(shí)間標(biāo)記)DATASRC(數(shù)據(jù)源)

(2)部分AIS屬性信息不準(zhǔn)確。漁船的部分速度和狀態(tài)信息會(huì)由于傳感器故障在傳送和接收的過程中發(fā)生數(shù)據(jù)缺失問題[23]。此外，經(jīng)咨詢漁船駕駛?cè)藛T得知，AIS數(shù)據(jù)中的漁船狀態(tài)信息是由人工輸入的，可能存在狀態(tài)數(shù)據(jù)不能完全準(zhǔn)確描述漁船實(shí)際狀態(tài)的情況。

(3)特征點(diǎn)數(shù)量多。如圖1所示，由于漁船在捕撈作業(yè)時(shí)會(huì)多次在作業(yè)區(qū)往返航行，在航行過程中拐彎或掉頭情況較多，這些點(diǎn)均為漁船的特征點(diǎn)，因此，與其他類別的船舶相比，漁船軌跡數(shù)據(jù)中特征點(diǎn)數(shù)量較多。

鑒于漁船AIS數(shù)據(jù)的上述特點(diǎn)，需要給出適合于漁船AIS軌跡分析的基本概念。

1.2 相關(guān)定義與公式

定義1軌跡點(diǎn)：漁船的位置點(diǎn)用p表示，一個(gè)位置點(diǎn)含有3個(gè)屬性信息:時(shí)間、經(jīng)度、緯度，軌跡點(diǎn)表達(dá)式為

p=(x,y,t)。

(1)

其中：x、y分別為軌跡點(diǎn)的經(jīng)度和緯度；t為時(shí)間。

定義2原始軌跡：由原始軌跡點(diǎn)按照時(shí)間順序排列起來的軌跡集合，用T表示，其表達(dá)式為

T={p0,p1,…,pn},i∈[0,n]。

(2)

其中：pi=(xi,yi,ti)表示原始軌跡點(diǎn)，對(duì)同一條船的軌跡T中的兩個(gè)軌跡點(diǎn)存在ti

定義3經(jīng)度差值和緯度差值：已知兩個(gè)相鄰的軌跡點(diǎn)pi(xi,yi,ti)和pi+1(xi+1,yi+1,ti+1)，將兩點(diǎn)經(jīng)度或緯度坐標(biāo)值作差,得出經(jīng)度差值Δxi或緯度差值Δyi,即

Δxi=xi+1-xi，

(3)

Δyi=yi+1-yi。

(4)

定義4特征點(diǎn)：在軌跡中令軌跡的經(jīng)緯度趨勢(shì)發(fā)生改變的點(diǎn)稱為特征點(diǎn)，特征點(diǎn)集合用F表示。已知3個(gè)軌跡點(diǎn)pi、pi+1和pi+2，當(dāng)經(jīng)度趨勢(shì)和緯度趨勢(shì)中任意一個(gè)發(fā)生改變時(shí)，將點(diǎn)pi+2加入特征點(diǎn)集合F，表達(dá)式為

F={pi+2‖(ΔxiΔxi+1<0∪ΔyiΔyi+1<0)},

i∈[0,n]。

(5)

定義5壓縮軌跡：指對(duì)原始軌跡進(jìn)行壓縮處理后，去除了冗余的軌跡點(diǎn)，按照產(chǎn)生的時(shí)間順序組成的新軌跡集合，用Tc表示，即

Tc={pc1,…,pci,…,pcn},ci∈[c1,cn],

tc1<…

(6)

定義6停留點(diǎn)：在軌跡中，若漁船在某個(gè)位置進(jìn)行長(zhǎng)時(shí)間停留，即在某一區(qū)域有大量距離極近的軌跡點(diǎn)，則該位置的特征點(diǎn)稱為停留點(diǎn)，用si(0

定義7軌跡段：在原始軌跡T或者壓縮軌跡Tc中，將點(diǎn)pi和pj連接組成的線段用pipj表示。

定義8軌跡點(diǎn)距離PD：指兩個(gè)相鄰的軌跡點(diǎn)間的恒向線距離[24]，計(jì)算公式為

(7)

c=Δyi/a,

(8)

(9)

由于恒向線是墨卡托投影上的直線,該線的長(zhǎng)度就是沿恒向線兩點(diǎn)之間的距離,其中a為等量維度,r為地球的半徑。

2 漁船AIS軌跡數(shù)據(jù)壓縮算法

Sliding Window算法是目前公認(rèn)的經(jīng)典算法，相比較于側(cè)重軌跡全局形態(tài)的Douglas-Peucker算法等，該算法傾向于局部軌跡的優(yōu)化壓縮[25]，漁船軌跡需要在壓縮時(shí)保留更多的局部特征點(diǎn)，所以Sliding Window算法更加符合漁船軌跡的壓縮宗旨。

2.1 Sliding Window算法

Sliding Window的算法思想是在起點(diǎn)初始化一個(gè)大小為1的滑動(dòng)窗口，往窗口中逐步加入后續(xù)的軌跡點(diǎn)。將窗口內(nèi)的第一個(gè)點(diǎn)和最后一個(gè)點(diǎn)連接，得到近似線段。計(jì)算近似線段與原始軌跡的垂直歐氏距離，若小于設(shè)定的距離閾值，則繼續(xù)增大滑動(dòng)窗口，大于閾值的點(diǎn)作為特征點(diǎn)保留，同時(shí)更新窗口直到窗口內(nèi)的誤差小于閾值，并重復(fù)以上步驟。

如圖2所示，以p0為起點(diǎn)，初始化滑動(dòng)窗口為{p0，p1}。以線段p0p2作為{p0，p1，p2}部分的近似軌跡，計(jì)算p1點(diǎn)和線段p0p2之間的垂直歐氏距離。若距離小于閾值，那么繼續(xù)擴(kuò)大窗口，加入新的軌跡點(diǎn)p3，滑動(dòng)窗口為{p0，p1，p2，p3}，以線段p0p3為近似軌跡，計(jì)算窗口內(nèi)其他點(diǎn)的垂直歐氏距離。由于其距離超過設(shè)定的距離閾值，所以之前的窗口{p0，p1，p2}被選作近似軌跡的一段。接著以p3為新的滑動(dòng)窗口起點(diǎn)，加入p3、p4，重復(fù)之前的步驟，直到軌跡終點(diǎn)。圖中原始軌跡最終被簡(jiǎn)化為{p0，p2，p5，p8}。

2.2 基于改進(jìn)滑動(dòng)窗口的漁船AIS軌跡數(shù)據(jù)壓縮算法

本文中針對(duì)漁船軌跡數(shù)據(jù)的特點(diǎn)，提出一種基于改進(jìn)滑動(dòng)窗口的漁船軌跡壓縮算法，由于漁船軌跡數(shù)據(jù)中屬性較多，且因?yàn)樽鳂I(yè)區(qū)信號(hào)丟失等問題導(dǎo)致漁船的航向狀態(tài)、船首向等屬性丟失或不準(zhǔn)確，如表2所示，漁船的位置信息顯示漁船處于運(yùn)動(dòng)狀態(tài)，但速度和航向顯示為0，說明該漁船存在屬性丟失。 故本研究在算法中只使用準(zhǔn)確的屬性，既時(shí)間、經(jīng)度和緯度，利用相鄰軌跡點(diǎn)之間的經(jīng)緯度變化狀態(tài)信息提取特征點(diǎn)，解決Sliding Window算法在壓縮頻繁轉(zhuǎn)向軌跡時(shí)出現(xiàn)的失真問題，并同時(shí)在算法中加入時(shí)間維，提高壓縮的精準(zhǔn)度。在初步保留特征點(diǎn)之后，對(duì)密度較高的軌跡點(diǎn)根據(jù)距離閾值進(jìn)一步壓縮，最終達(dá)到實(shí)現(xiàn)停滯點(diǎn)直接壓縮、運(yùn)動(dòng)點(diǎn)按比例壓縮、作業(yè)點(diǎn)盡量壓縮的目的。

表2 信息丟失的軌跡樣例Tab.2 Sample of the lost-information trajectory

算法流程如圖3所示。算法基本步驟如下：

(1)取一條漁船的軌跡數(shù)據(jù)。

(2)保留第一個(gè)軌跡點(diǎn)p0和最后一個(gè)軌跡點(diǎn)pn為特征點(diǎn)。

(3)以p0到p1的經(jīng)緯度變化趨勢(shì)為參照，相同方向航行的軌跡點(diǎn)經(jīng)緯度變化呈現(xiàn)持續(xù)遞增或遞減趨勢(shì)，趨勢(shì)發(fā)生變化則考慮漁船在行駛中方向發(fā)生改變或者漁船的狀態(tài)發(fā)生改變。分別比較相鄰點(diǎn)之間的經(jīng)度和緯度變化，只要二者有一項(xiàng)變化狀態(tài)發(fā)生改變時(shí)，保留其為特征點(diǎn)。

(4)若在一定范圍內(nèi)的同一區(qū)域趨勢(shì)頻繁發(fā)生改變，考慮漁船是否處于靜止或相對(duì)靜止?fàn)顟B(tài)(停滯或捕撈狀態(tài))，根據(jù)相鄰軌跡點(diǎn)間距離判斷是否處于停滯狀態(tài)，相鄰軌跡點(diǎn)之間距離小于3 m則直接壓縮，直到得到一個(gè)距離大于3 m的點(diǎn)，重新開始判斷。

3 驗(yàn)證試驗(yàn)

3.1 試驗(yàn)設(shè)計(jì)

為驗(yàn)證漁船AIS軌跡數(shù)據(jù)壓縮算法的有效性，分別對(duì)單條漁船軌跡進(jìn)行不同算法的壓縮對(duì)比試驗(yàn)。算法采用Python語言編寫，版本為3.6,IDE使用Spyder。

原始試驗(yàn)數(shù)據(jù)集來自大連世想海洋科技有限公司，漁船軌跡數(shù)據(jù)以.csv的文件格式存儲(chǔ)，時(shí)間跨度從2018年10月1日至2018年11月30日，大小約3.57G,原始數(shù)據(jù)樣例如表3所示。

表3 原始軌跡數(shù)據(jù)樣例Tab.3 Sample of original trajectory data

原始漁船數(shù)據(jù)未經(jīng)過預(yù)處理，可能會(huì)因?yàn)锳IS信號(hào)不穩(wěn)等問題出現(xiàn)軌跡點(diǎn)漂移或缺失的情況，使軌跡的位置信息與實(shí)際不符，影響軌跡壓縮效果，為此首先對(duì)出現(xiàn)以上情況的異常數(shù)據(jù)進(jìn)行清洗。

若發(fā)生信號(hào)漂移的情況，若漂移點(diǎn)與前一點(diǎn)及漂移點(diǎn)與后一點(diǎn)的時(shí)間間隔小但距離間隔較大，而漂移點(diǎn)前后兩點(diǎn)之間的時(shí)間間隔小距離間隔正常，則剔除該漂移點(diǎn)。

若發(fā)生信號(hào)丟失的情況，則通過缺失點(diǎn)前后兩個(gè)已知的數(shù)據(jù)點(diǎn)對(duì)缺失部分進(jìn)行線性擬合，如圖4所示。

設(shè)缺失的數(shù)據(jù)點(diǎn)為(xi,yi,ti)，前后兩個(gè)已知點(diǎn)為(xi-1,yi-1,ti-1)和(xi+1,yi+1,ti+1)，通過這兩個(gè)已知的數(shù)據(jù)來擬合點(diǎn)(xi,yi,ti)，填補(bǔ)缺失值。擬合公式如下：

(xi,yi)=(xi+1,yi+1)+[(xi+1,yi+1)-

(xi-1,yi-1)]/(ti+1-ti-1)×(ti-ti-1)。

(10)

將數(shù)據(jù)進(jìn)行預(yù)處理后，從庫中抽取一條船連續(xù)6 d的運(yùn)行軌跡，從數(shù)據(jù)庫中選取的漁船唯一識(shí)別號(hào)(MMSI)為42424242，時(shí)間為10月1日至6日，按照時(shí)序整理提取漁船信息，包含航行狀態(tài)、精度、對(duì)地航速、經(jīng)度、緯度，如表4所示。

本文選用Sliding Window算法和D-P算法作為對(duì)比算法，以壓縮效率作為試驗(yàn)結(jié)果參考，對(duì)3種算法進(jìn)行評(píng)測(cè)，評(píng)測(cè)公式如下：

R=1-N/M×100%。

(11)

表4 整理后的軌跡數(shù)據(jù)樣例Tab.4 Samples of the processed trajectory data

其中：R為壓縮率；M為壓縮前軌跡點(diǎn)的個(gè)數(shù)；N為壓縮后的軌跡點(diǎn)的個(gè)數(shù)。

3.2 試驗(yàn)結(jié)果

從圖5可見：3種算法對(duì)漁船軌跡進(jìn)行壓縮后，原始軌跡點(diǎn)都大幅度減少，但當(dāng)數(shù)據(jù)中出現(xiàn)折返路徑，即漁船在捕撈區(qū)域作業(yè)的情況下，D-P算法雖然能夠保留軌跡形態(tài)(圖5-A2、B2)，但壓縮掉大量的有用信息；Sliding Window算法在軌跡點(diǎn)密集的地方出現(xiàn)軌跡丟失的現(xiàn)象(圖5-A3、B3)，壓縮后的軌跡存在較大誤差；相比D-P算法而言，基于改進(jìn)滑動(dòng)窗口的漁船軌跡壓縮算法能夠更好地保留漁船作業(yè)時(shí)的軌跡點(diǎn)(圖5-A4、B4)，能夠較好地保留3軌跡的形狀特征。

算法運(yùn)算結(jié)果如表5所示，3種算法中SW算法的壓縮率最高，6 d的數(shù)據(jù)壓縮率平均在99.6%以上，其次是D-P算法，壓縮率在99.3%左右，而改進(jìn)的滑動(dòng)窗口壓縮算法的壓縮率控制在94%以下，保留了更多的漁船軌跡特征點(diǎn)，更有利于后續(xù)的漁船作業(yè)行為分析工作。

表5 3種壓縮算法的試驗(yàn)結(jié)果Tab.5 Experimental results of three compression algorithms

4 結(jié)論

針對(duì)現(xiàn)有軌跡壓縮算法在漁船軌跡數(shù)據(jù)方面存在壓縮率太高導(dǎo)致特征點(diǎn)丟失等問題，提出一種改進(jìn)的滑動(dòng)窗口壓縮算法。通過對(duì)比試驗(yàn)證明，D-P算法應(yīng)用于漁船軌跡壓縮工作時(shí)，由于壓縮率高而導(dǎo)致特征點(diǎn)大量丟失，壓縮誤差較大，文中提出的基于改進(jìn)滑動(dòng)窗口的壓縮算法雖然壓縮率有所降低，但能夠保留大量特征點(diǎn)，而且壓縮后得到的軌跡與原始軌跡相似度更高，具有一定的研究?jī)r(jià)值，對(duì)于如何進(jìn)一步減少壓縮誤差，將在未來繼續(xù)研究。

致謝：感謝大連世想海洋科技有限公司提供數(shù)據(jù)支撐！