基于改進滑動窗口的漁船軌跡在線壓縮算法

顧杰, 宋鑫, 施笑畏, 萇道方

(1.上海海事大學物流工程學院,上海 201306;2.上海海事大學青島研究院,山東 青島 266237;3.上海海事大學物流科學與工程研究院,上海 201306)

0 引 言

船舶自動識別系統(automatic identification system, AIS)由岸基(岸臺基站)設施和船載設備共同組成,它能夠將船舶識別碼、船位、對地航向、船首向、航速、船舶尺度、船型和貨物等相關信息通過甚高頻(very high frequency, VHF)向附近水域船舶和岸臺廣播,使鄰近船舶和岸臺能及時掌握附近海面所有船舶的動態和靜態信息。隨著國家對漁業重視程度的不斷增加,AIS已經在漁業信息化建設中得到廣泛應用[1]。海事部門和漁業管理部門可以利用AIS提供的漁船航行、漁業生產信息等對漁船進行管理。[2]漁船作業區域相對集中,且海區內漁船密集程度較高,因此監管人員若要通過AIS掌握漁船的實時狀態,就需要漁船能夠及時、準確地上傳AIS數據。然而,海量的軌跡數據會長時間、高頻率地占用數據傳輸的通道,導致其他可能需要協調避讓的船舶錯過溝通的良機,從而影響海上的航行安全。[3]此外,目前漁船上普遍使用的AIS設備為B類AIS設備,其功能存在缺陷且發送信息的速度較慢,致使漁船AIS數據難以被有效利用。因此,需要快速高效的在線AIS軌跡數據壓縮算法對數量龐大的AIS數據進行壓縮。

船舶軌跡壓縮主要分為離線壓縮和在線壓縮兩種,其中最經典的離線壓縮算法是DOUGLAS等[4]提出的DP(DOUGLAS-PECUKER)算法。由于DP算法在用于對數據進行離線批處理時具有較好的效果,很多學者在DP算法基礎上進行了更深入的研究:徐凱等[5]提出一種考慮時間維的快速DP算法,利用向量的內積、外積改善算法的壓縮效率和運行速度;ZHAO等[6]在根據空間位置特征采用DP算法的同時,考慮了航向變化和速度特性;LIU等[7]和TANG等[8]均對自適應閾值的DP算法進行了研究。在在線壓縮領域影響較廣的是KEOGH等[9]提出的滑動窗口(sliding window,SW)算法:高邈等[10]通過加入風流壓差角降低SW算法的誤差;GAO等[11]根據船舶航向角偏差、位置偏差和AIS數據的時空特性從船舶軌跡中提取關鍵特征點,對SW算法進行了改進;董婉婷等[12]以相鄰軌跡點間的經緯度變化趨勢為參照來保留特征點,在壓縮高密度停滯點的同時用采樣法保留直行中間點,從而避免采用SW算法壓縮軌跡可能出現的軌跡形態失真。宋鑫等[13]提出一種動態閾值結合全局優化的兩階段在線壓縮算法,在分段提取特征點后利用改進的SPM(scan-pick-move)算法進行全局優化,在提高壓縮效率的同時取得了良好的壓縮效果。SUN等[14]將滑動窗口添加到經典的SPM算法中。ZHU等[15]采用滑動窗口中的軌跡變化率和速度變化率作為當前軌跡點是否可以簡化的判斷標準。

上述在線壓縮算法用于對航線較為固定、AIS數據質量較好的商船軌跡的壓縮能夠取得較好的效果,但在用于處理沿岸航行的漁船的軌跡數據時會丟失大量軌跡特征點。這是由于:海上船舶遠洋航運的航線較為固定,在一段時間內采集到的船舶航跡數據具有一定的重復性和規律性;漁船不會沿著固定的航道航行,且其航向和航速變化較大,特別是在進行捕撈作業時漁船會在作業區停留較長時間并在某個區域來回慢速航行,因此在對漁船軌跡數據進行壓縮的過程中采用單一的距離閾值難以考慮漁船航向的變化,而采用多種閾值組合不僅會誤刪一些局部的特征點,而且會大大提高算法的時間復雜度。

為解決傳統算法在漁船軌跡點密集處易丟失軌跡,難以保留方向變化較大的特征點的問題,本文提出一種基于改進滑動窗口的漁船軌跡在線壓縮算法。該算法結合船舶領域的思想,在原本的滑動窗口中構造一個以窗口起止點為焦點、以距離閾值為短軸半徑的橢圓形船舶領域,在考慮時序信息和傳統距離閾值的同時,保留一部分局部方向變化較大的特征點,從而實現更有效的軌跡數據在線壓縮。

1 算法壓縮原理

船舶軌跡壓縮的原理是:以較少的點表示原有的軌跡,并且盡可能減小壓縮軌跡的誤差。如圖1所示,軌跡點P1和P2分別為當前窗口的起始點和終止點,其余的點為當前窗口內待處理的軌跡點。簡化閾值是指從原始軌跡點到簡化軌跡線的最大允許歐氏距離(perpendicular Euclidean distance, PED),而與直線P1P2平行的兩條虛線內的區域就是待壓縮的區域。壓縮時計算每個軌跡點到直線P1P2的歐氏距離,因為d3、d5的長度小于簡化閾值而d4的長度大于簡化閾值,所以僅有P4被保留下來。然而,僅以歐氏距離作為壓縮閾值是難以判斷船舶航向角的變化的。以圖1中(P1,P5,P2)軌跡段為例:船舶在行駛過程中航向發生了很大的變化,軌跡點P5因其包含較大的信息量而被作為特征點保留,但實際上根據上述壓縮算法P5會因其到直線P1P2的歐氏距離小于簡化閾值而被刪除。

圖1 經典的船舶軌跡壓縮原理示意圖

由于漁船不受固定航道的約束,其運動模式與其他類型船舶的相比較為復雜,所以漁船軌跡相較于其他船舶的軌跡存在數據點密集、航速和航向波動較大的特點。為在壓縮軌跡的過程中加入對船舶航向的考慮,保留更多的特征點,在此引入船舶領域的概念。船舶領域本義是指圍繞船舶的自由空間,由日本學者藤井彌平于20世紀60年代初提出,目前主要應用在船舶避碰、碰撞風險評估、航道容量分析這幾方面[16]。如圖2所示,FUJII等[17]提出的橢圓形船舶領域模型,橢圓的中心為船舶中心,橢圓的長軸在船舶首尾連線上,橢圓的短軸在正橫方向上,船舶領域的大小與船長L成正比。傳統的船舶領域實際上是一個圍繞該船的、將其他船舶和固定物體排除在外的有效水域,通過劃定一個界限來保證該船附近沒有其他船舶或障礙物存在,從而使其自身始終處于較為安全的狀態。借鑒船舶領域思想,本文構造了一個以滑動窗口的中心為中心,用于將軌跡點篩除的特殊區域。

(a)模型1

在軌跡壓縮研究領域,POTAMIAS等[18]首次在threshold-guided sampling算法中提出“安全區域”的概念。如圖3所示,該算法通過限定最后一個軌跡點速度的可容忍變化以及方向的最大允許偏差來控制安全區域的實際形狀,通過判斷軌跡點是否落在此安全區域內決定是否保留軌跡點,從而達到軌跡簡化的目的。ZHANG等[19]在改進DP算法時針對簡化閾值這個唯一參數,提出一種新的基于AIS數據的最小船舶區域評價方法。為保證原始軌跡點對應的簡化軌跡點的位置在原始軌跡點的安全范圍內,采用船舶領域的大小作為閾值確定的標準。

圖3 POTAMIAS等[18]在threshold-guided sampling算法中提出的安全區域

本文結合船舶領域的思想,在滑動窗口中劃定一個橢圓形的界限作為船舶軌跡壓縮的依據,該界限之外的點均被作為特征點保留。以圖4為例,以窗口的起始點P1和終止點P2作為焦點構造標準橢圓,將軌跡點到直線P1P2的歐氏距離作為短軸半徑,軌跡點如果被包含在船舶領域內則被刪除,否則被作為特征點保留,即在圖1的基礎上保留了更多、更有價值的特征點。從圖4可以看出:類似P5這樣的方向變化較大且距離窗口起始點有一定距離的軌跡點因位于船舶領域外而得以保留;類似P3這樣的方向變化較小且歐氏距離小于閾值的軌跡點被刪除。以船舶領域作為篩選特征點的依據,不僅可以保留更多特征點,還可以避免點弦距離的計算。改進后的算法利用橢圓的第一定義,比較軌跡點到窗口起始點與到終止點的距離之和與船舶領域的長軸長度的大小,若前者大于后者則判定軌跡點在船舶領域外,反之判定軌跡點在船舶領域內。與原算法相比,這樣的判斷方式不僅能夠保留更多有用的信息,還能夠減少海倫公式的使用,使得算法的時間復雜度降低。

圖4 結合船舶領域的軌跡壓縮原理

2 算法設計與實現

2.1 相關定義與公式

定義1所有的軌跡點數據均由三元組組成,上傳的AIS軌跡數據中軌跡點i的數據為

pi=(xi,yi,ti)

(1)

式中:xi和yi分別為軌跡點i的經度和緯度;ti為船舶經過點i的時間。

定義2原始軌跡T是指漁船在航行過程中上傳的AIS軌跡數據集合,該軌跡含有n個軌跡點,可以表示為

T={p1,p2,…,pn},pi∈T

(2)

簡化軌跡Tsim是指原始軌跡經過壓縮處理后保留的特征點集合,該軌跡含有m個軌跡點,可以表示為

(3)

hi=pi·pi+1,pi≠pn

(4)

(5)

(6)

定義4在原始軌跡中的某一軌跡點所在滑動窗口創建一個橢圓形可變船舶領域(用SD表示),用于判斷該軌跡點是否應被剔除。該標準橢圓以滑動窗口的起始點與終止點的距離為焦距,以歐氏距離閾值為短軸長。

在預處理數據時,需要將初始數據的WGS-84大地坐標系轉換成墨卡托坐標系,假設某軌跡點的經緯度坐標為(φ,ω),平面坐標為(x,y),則轉換公式如下:

(7)

(8)

x=r0ω

(9)

y=r0q

(10)

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

2.2 基于改進滑動窗口的漁船軌跡在線壓縮算法

2.2.1 經典SW算法

經典SW算法的思想是:在起點初始化一個滑動窗口,保證窗口的大小始終為3個點并逐步加入軌跡點實現在線壓縮。判斷某軌跡點能否被作為特征點保留的依據是:計算待處理點到窗口起始點與終止點連線的歐氏距離,若該歐氏距離大于設定的閾值,則將該待處理點作為特征點保留并將終止點作為新窗口的起始點繼續壓縮,若該歐氏距離小于閾值則將窗口的終止點向后滑動,重復上述步驟直到所有的軌跡點都被處理完畢。如圖5所示,初始滑動窗口為(P0,P1,P2),點P0作為起始點得以保留。計算待處理點P1與線段P0P2之間的歐氏距離,若該歐氏距離小于閾值,則剔除點P1并加入新的軌跡點P3作為窗口(P0,P2,P3)的終止點。繼續計算待處理點P2到線段P0P3的歐氏距離,由于該歐氏距離超過設定的距離閾值,所以點P2作為特征點被保留。加入點P4,點P2成為新的窗口(P2,P3,P4)的起始點,重復上述步驟,得到最終的簡化軌跡為(P0,P2,P3,P4,P6,P7)。

圖5 經典SW算法

2.2.2 改進的SW算法

針對漁船AIS數據變化幅度大的特點,結合船舶領域的思想,提出基于改進滑動窗口的漁船軌跡在線壓縮算法。由于漁船軌跡數據量大,且在漁船航行過程中航向和航速等變化頻繁,經典SW算法以單一的歐氏距離閾值作為篩選標準很難保留所有的特征點,所以經典SW算法對漁船軌跡數據的壓縮率不高。本研究對經典SW算法加以改進,選取原窗口內的起始點和終止點作為標準橢圓形船舶領域的焦點,原來的距離閾值作為標準橢圓的短軸半徑,在壓縮的軌跡帶中構造一個篩選能力更強的橢圓形船舶領域。

算法流程見圖6。算法基本步驟如下:

圖6 改進SW算法流程

(1)輸入原始軌跡T,并將第一個軌跡點加入簡化軌跡Tsim,初始化滑動窗口。

(2)為防止漁船在某一位置長時間保持靜止,若當前窗口的起始點與終止點之間的距離小于距離閾值,則直接剔除當前待處理點,并加入下一個軌跡點組成新的滑動窗口。

(3)令當前滑動窗口為(P0,P1,P2),即P0和P2分別為滑動窗口的起始點和終止點。若P0與P2之間的距離大于距離閾值,則以P0與P2之間的距離為焦距、以歐氏距離閾值為短軸半徑構造橢圓形船舶領域SD。判斷點P1是否在船舶領域內,若在領域內則剔除點P1并加入下一個軌跡點,組成新的滑動窗口(P0,P2,P3),否則將點P1作為特征點加入簡化軌跡Tsim,并將點P1作為新窗口的起始點(滑動窗口變為(P1,P2,P3))。

(4)繼續執行算法,直到滑動窗口的終止點為原始軌跡T的最后一點,算法結束,輸出簡化軌跡Tsim。

3 實驗驗證與分析

3.1 實驗設計

為驗證基于改進滑動窗口的漁船軌跡在線壓縮算法的有效性,進行單船軌跡的不同閾值分析以及該算法與其他算法的對比分析。算法采用Python3.9編寫,實驗設備的具體配置為:Windows 10,Intel(R) Core(TM) i7-10750H 2.6 GHz,16 GB內存。本文的原始數據集來自中國港口網(http://ship.chinaports.com/)。隨機選取2021年4月1—30日東海沿岸100艘漁船的軌跡,共450 162條數據。

EAED(T,Tsim)=

(11)

(12)

3.2 單船軌跡壓縮結果

在數據集中隨機抽取一艘MMSI為900406865的漁船在2021年4月的一條AIS軌跡數據,共有1 307個軌跡點。在距離閾值取50 m時,用經典SW算法壓縮后剩余的軌跡點數為807,用改進后的SW算法壓縮后剩余的軌跡點數為948。單條軌跡的壓縮結果見圖7,其中:圖7(a)為完整軌跡;圖7(d)為船舶前進的軌跡段;圖7(g)為船舶無規則運動的軌跡段。對比圖7(e)與圖7(f)可知,改進后的SW算法對船舶航向的變化更加敏感。對比圖7(h)與圖7(i)可知,在較為復雜的航行情況下,用改進后的SW算法壓縮船舶軌跡可以在船舶航向變化較大的局部區域保留更多的有用信息,從而保證壓縮后的軌跡不失真。通過對壓縮前后漁船軌跡的對比可以看出,雖然用本文算法壓縮后僅剩72.5%的軌跡點,但是所得軌跡仍能近似地表現出原軌跡的特征。

(a)完整軌跡

由于壓縮數據的目的是為了后期更方便地進行分析,所以壓縮的首要前提是保證壓縮后軌跡的誤差盡可能低,而不是僅以壓縮率作為算法的評價指標。本實驗對歐氏距離閾值、壓縮率和平均歐氏距離誤差這三者之間的關系進行了分析。如圖8所示,隨著歐氏距離閾值的不斷增大,壓縮率不斷減小,但平均歐氏距離誤差加速增大,數據所保留下來的有用信息越來越少,因此盲目增大壓縮閾值會使得軌跡關鍵特征點信息被刪除的風險變大。雖然算法選取較高的壓縮閾值能夠壓縮掉大量的軌跡點,但是所得軌跡的失真度會增加,最終影響壓縮軌跡數據的質量。因此,在軌跡壓縮的過程中,應當根據實際的需求選擇合理的閾值,確保能夠保留關鍵特征點,從而使壓縮得到的軌跡能夠有效代替原始軌跡。

圖8 距離閾值、壓縮率和平均距離誤差的關系

3.3 不同閾值下各算法的比較

為比較各算法在不同閾值下的壓縮效果,對于DP算法、TD-TR算法、SW算法和本文改進后的SW算法設定距離閾值分別為10、20、30、40、50 m,對于SQUISH算法設定壓縮率閾值分別為95%、90%、85%、80%、75%,對450 162條AIS數據進行壓縮。5種算法的軌跡數據壓縮結果見表1。由表1可知:(1)隨著閾值逐漸增大,各算法的壓縮率均呈明顯的下降趨勢。(2)在平均歐氏距離誤差和平均方向誤差對比方面,DP算法和TD-TR算法比SW算法和SQUISH算法更具優勢。這是由于DP算法和TD-TR算法屬于離線批處理算法,能夠對漁船軌跡進行全局處理,而SW算法和SQUISH算法作為在線壓縮算法,更偏向于從局部提取特征點,難以兼顧軌跡的全局變化情況。(3)本文提出的改進SW算法不僅在平均歐氏距離誤差的控制上更出色,而且彌補了經典SW算法忽略船舶航向變化的缺點,對漁船航行過程中的方向變化更為敏感,壓縮所得軌跡的平均方向誤差在5種算法中是最小的。

不同算法運行時間的對比見圖9。由圖9可知,隨著軌跡點數的增加,5種算法的壓縮時間都增加。SQUISH算法壓縮時間的增加幅度最大,這是由于優先隊列的容量隨軌跡點數的增加而增大。由于數據的成倍增加使迭代次數增加,所以DP算法和TD-TR算法壓縮時間的增長幅度也較大。本文提出的改進SW算法在壓縮速度上不僅繼承了經典SW算法的優勢,還在原有基礎上有小幅度的提升,能夠更好地用于在線壓縮的場景。

圖9 算法運行時間對比

4 結 論

針對現有軌跡壓縮算法僅以歐氏距離為壓縮閾值,在漁船軌跡點密集處易丟失軌跡,難以保留方向變化較大的特征點等問題,結合船舶領域的思想,提出一種基于改進滑動窗口的漁船軌跡在線壓縮算法。采用東海沿岸的漁船AIS數據進行對比實驗,結果表明該算法與經典滑動窗口算法相比在不增加算法運行時間的同時,在不同閾值下壓縮率平均提高了5%左右,不僅能在壓縮時保留更多方向變化較大的軌跡點,而且壓縮后得到的軌跡相對于原始軌跡的誤差更小,具有一定的理論研究價值。本文的研究也存在一些不足,如在軌跡壓縮中未考慮不同水域(開放水域、限制水域、狹水道、冰區等)的不同特點,也未考慮不同漁船的船長、吃水的差異。未來將在軌跡壓縮過程中考慮更多的船舶參數以提高壓縮后軌跡的精度。