劉海硯,郭 漩,劉俊楠

1.信息工程大學數據與目標工程學院,河南 鄭州 450000; 2.鄭州大學計算機與人工智能學院,河南 鄭州 450000; 3.鄭州大學地球科學與技術學院,河南 鄭州 450000

近年來,大數據、移動互聯、衛(wèi)星定位技術高速發(fā)展,船舶自動識別系統(tǒng)(automatic identification system,AIS)得到普及和推廣[1]。AIS產生了覆蓋范圍廣、時效性強的船舶軌跡數據,被廣泛應用于船舶航行特征挖掘、國際經濟貿易模式分析等方面[2]。海量軌跡數據的大數據特征既帶來了研究機遇,也對傳統(tǒng)數據分析方法帶來一系列挑戰(zhàn)[3]。此外,海量冗余的軌跡數據降低了軌跡檢索分析的效率[4-5],不利于進行數據挖掘。為有效縮減軌跡數據存儲和傳輸的成本,亟須結合船舶語義時空特征控制壓縮過程,使用關鍵信息表示船舶軌跡數據,進而滿足數據壓縮需求。

軌跡數據壓縮的本質是數據的有損壓縮,即通過最重要的時空和語義信息表示軌跡,滿足壓縮后數據與原始軌跡的相似度[6]。軌跡具有精確的地理空間坐標,因此傳統(tǒng)的軌跡數據壓縮方法通常僅考慮其空間特征,將軌跡抽象為線要素并采用線化簡技術實現壓縮。如道格拉斯—普克(Douglas-Peucker,DP)[7]、滑動窗口(sliding window,SD)[8]、普通開放窗口[9]等算法,分別在全局和局部兩個方面使用歐氏距離計算并刪除偏移量較小的點,實現顧及幾何特征的軌跡線要素壓縮。由于軌跡具有時間屬性,文獻[10—11]結合了時間和空間信息壓縮軌跡。此外,文獻[12]引入時空距離,優(yōu)化DP等算法,提高軌跡距離的度量精度,但仍需預先傳入距離閾值參數。文獻[13]提出了一種DP算法的閾值估算方法,根據軌跡長度自動控制軌跡數據壓縮過程,但難以顧及軌跡關聯城市設施的語義信息。在語義壓縮方面,伴隨城市路網結構的愈發(fā)成熟,部分學者逐漸采用路網獲取軌跡語義信息實現軌跡數據壓縮。文獻[14]基于城市路口的語義特征,設計了車輛軌跡的語義表示和分段軌跡數據壓縮方法。文獻[15]結合興趣點、重點地物和路段,輔助用戶理解軌跡信息,提高軌跡數據壓縮比例。文獻[16]根據城市和鄉(xiāng)村地區(qū)興趣點的分布差異,探索適應不同區(qū)域地物密度的軌跡語義壓縮方法。雖然基于路網的軌跡語義壓縮可顯著減少空間存儲開銷,但在海洋中行駛的船舶軌跡缺少足量的興趣點和路網結構,難以基于地物實現船舶軌跡語義壓縮。

針對以上問題,本文以AIS船舶軌跡為試驗數據,提出一種時空和語義結合的軌跡數據壓縮方法(spatio-temporal and semantic trajectory compression,SSTC)。首先,分析船舶軌跡的時空和語義特征,并設計軌跡數據壓縮流程。其次,分別根據時空和語義信息,計算船舶軌跡點的特征值。然后,采用BLG樹(binary line generalization tree)和加權融合法綜合軌跡點的時空和語義特征值,獲取軌跡點的重要性排序,最終實現顧及船舶航行時空和語義特征的軌跡數據壓縮。

1 船舶軌跡特征和壓縮流程

1.1 軌跡時空和語義特征

船舶軌跡(Trj)是船舶在地理空間留下的痕跡,由包含空間位置、時間節(jié)點、語義特征等信息的軌跡點集合組成,可表示為Trj={P1,P2,…,Pn}。其中Pi={li,bi,ti,vsi}為軌跡點,li、bi、ti、vsi分別表示軌跡點的經度、緯度、采樣時間、具體語義信息,且軌跡中?1≤i≤j≤n,均存在ti

空間特征是事物的基本特征,可通過li、bi表示軌跡的空間形態(tài)、分布和走向等[17]。其中,空間形態(tài)作為軌跡數據的主要特征,可通過少量的空間特征點表示原始軌跡。時間特征是軌跡數據區(qū)別于傳統(tǒng)地理空間數據的本質特征,展示移動對象的動態(tài)變化特點。為了形成一體化時空特征,文獻[13]提出時間同步歐氏距離,在近似軌跡上按時間比例獲取原始軌跡點的近似點并計算兩點的歐氏距離,對時間和空間特征進行轉換,使時間與空間位于統(tǒng)一的度量標準,以度量并獲取時空特征顯著的軌跡點。在遠距離載運工具中,船舶運載的歷時最長,因此產生的冗余點顯著多于其他移動對象,且存在周期長,跨度大,軌跡間長度差別明顯等特征。

語義特征指事物蘊含的基本含義,語義是詞語和事實之間的關系,可作為聯系知識表示和現實世界的途徑[18],通常包括靜態(tài)語義和動態(tài)語義[19]。其中,靜態(tài)語義涉及興趣點等地理空間環(huán)境信息,但是海洋存在的興趣點等地理空間設施較少,難以與船舶軌跡建立關聯。動態(tài)語義包括船舶航速、航向等隨時間平緩變化的信息,可直接表示船舶驟?；蚣鞭D等航行狀態(tài)變化,也可間接體現船舶受地理空間環(huán)境的影響[8],為船舶軌跡數據壓縮提供了一種途徑。

1.2 軌跡數據壓縮流程

本文以船舶軌跡數據為研究對象,提出了一種結合船舶軌跡時空和語義特征的數據壓縮方法。如圖1所示,壓縮算法包括船舶軌跡的時空特征值計算、語義特征值計算、特征點融合排隊和軌跡數據壓縮4個部分,具體內容如下。

(1) 軌跡時空特征值計算。以軌跡的時間標簽和經緯度坐標為基礎,通過DP算法和時間同步歐氏距離,計算并獲取軌跡的時空特征點,進而通過少量軌跡點反映軌跡的時空特征。

(2) 軌跡語義特征值計算。以軌跡點的航速和航向作為語義信息,通過SD算法依次計算軌跡點的語義信息變化,進而獲取軌跡點的語義特征。

(3) 特征點融合排隊。分別對軌跡點的時空和語義特征進行重要性排序,并采用加權融合排隊方法,獲得綜合考慮時空和語義特征的軌跡點重要性隊列。

(4) 軌跡數據壓縮。按照重要性程度對軌跡點進行排列,僅根據傳入的壓縮比例獲取目標軌跡點數目即可保留特征顯著的軌跡點并刪除其他點,實現軌跡數據壓縮,減少數據冗余,優(yōu)化存儲結構。

2 船舶軌跡點的時空和語義特征值計算

軌跡數據壓縮算法應保留更能體現船舶行駛特征的軌跡點,而時空和語義屬于不同的評價標準,因此需分別在時空和語義角度計算軌跡點的特征值。

2.1 軌跡點的時空特征值計算

DP算法是一種可以根據空間特征保留重要軌跡點的線壓縮算法,該方法思想簡單且性能較好,在線化簡等制圖綜合領域應用廣泛[20]。然而,DP算法采用垂直歐氏距離度量偏移量,僅考慮了位置信息,而軌跡點表示的是船舶在具體時刻的位置,因此還需綜合考慮軌跡點的時間信息。

圖2 時空特征值計算

2.2 軌跡點的語義特征值計算

船舶軌跡數據的動態(tài)語義信息包括船舶的對地航速(speed over ground,SOG)和對地航向(course over ground,COG),可以通過其數值變化計算船舶的航行特征[8]。其中,SOG表示船舶在風和水流影響下的航行速度,航速的通常單位為節(jié)或海里/小時,相當于1 h船舶行駛的距離,1節(jié)為1.852 km/h[21]。COG表示船舶在風和水流影響下的航行角度[22],由真北線順時針方向開始計量當前時刻(t1)與下一時刻(t2)船舶航行角度,計量范圍為0°～360°(圖3)。COG和SOG結合可體現船舶動態(tài)變化信息,也可間接表示其受水和風的影響,可作為計算軌跡語義特征值的重要變量。

圖3 對地航向示例

DP算法可以在全局角度保留船舶軌跡的時空特征[4],卻難以在局部顧及船舶航行狀態(tài)變化的語義信息,傳統(tǒng)SD算法采用垂直歐氏距離計算窗口內的特征變化,僅能應用于時空特征誤差的度量,均不直接適用于船舶軌跡動態(tài)語義特征點的計算。本文以SD算法的滑動窗口為基礎,從軌跡起點開始,初始化滑動窗口,并逐步移動窗口,在一個固定大小的窗口中根據固定數目的軌跡點,計算局部窗口內軌跡點的語義特征值。圖4展示了軌跡的語義特征計算過程,首先初始化一個窗口大小為3的滑動窗口,窗口內包括3個軌跡點;然后計算第1個窗口內軌跡點的語義特征值,即第2個點(P2)相對于第1個點(P1)和第3個點(P3)對地航速(Δsog_P2)變化的絕對值平均數,3個軌跡點形成的對地航向變化夾角(Δcog_P2);最后,窗口向前滑動,依次計算P3、P4、P5和P64個軌跡點的對地航速和對地航向變化,由此獲得船舶軌跡點的語義特征值。

圖4 語義特征值計算

3 船舶軌跡數據壓縮

船舶軌跡通過部分特征點即可概略表達軌跡特征,而且軌跡特征點數目與壓縮比例呈現反比關系,本文將在語義和時空綜合約束下壓縮原始船舶軌跡。

3.1 軌跡特征點排隊

SD算法以局部窗口為約束,計算的軌跡點語義特征值,可以分別根據Δsog和Δcog的數值對比,獲取降序排序。然而時空特征值采用逐層二分方式的DP算法,直接構建偏離值的排序隊列方式容易忽視DP算法的層次性[23]。

為了獲取DP算法的偏離值排序隊列,本文以文獻[23]提出的單條曲線BLG樹為基礎,采用二叉樹表示整條軌跡的時空特征值。該二叉樹的根結點為軌跡點到近似軌跡的最大時空歐氏距離點,即最大時空特征值點,根結點的左右子結點則分別為其左右子軌跡的最大時空特征值點。圖5展示了DP算法分割原始軌跡構建BLG樹的過程,其中軌跡Trj1由{P1,P2,…,P10}點集組成,P1和P10是首尾軌跡點構建的初始近似軌跡線,由時空同步歐氏距離可知P4為最大特征點,因此將其作為根結點;然后將軌跡分為{P1,P2,P3,P4}和{P4,P5,P6,P7,P8,P9,P10}兩個子軌跡,此時最大特征值點分別為P2和P8,即BLG樹中根節(jié)點的左右子節(jié)點為P2和P8,由此類推可構建軌跡的BLG樹(圖5(b))。

圖5 原始軌跡和BLG樹

BLG樹的結點存儲層次和偏離值體現了軌跡點表示時空特征的能力,層次越高、偏移量越大則能力越強。通常父結點的偏移量會比子結點的偏移量大,然而DP算法不能保證子軌跡最大特征值結點的偏移量一定小于其父軌跡最大特征值結點的偏移量。

如果直接按照特征值大小排隊軌跡點,將會破壞軌跡和子軌跡之間的層次關系,而如果按照先層次后特征值的順序對軌跡點進行排隊,則會出現子節(jié)點特征值大于父節(jié)點特征值的現象。如圖5(b)所示,P6是子節(jié)點,其偏移量(926 km)大于父節(jié)點P8(910 km),也大于節(jié)點P2(573 km)。為了根據時空同步距離構建線性排序,需從根節(jié)點開始按照先層次、后特征值的方式將BLG樹轉為排序BLG樹。具體來說,①將根節(jié)點P4加入排序BLG樹,序號為1,并將P4的左右子節(jié)點P2和P8加入待排序隊列;②在待排序隊列中選擇偏移量最大的節(jié)點P8加入排序BLG樹,并將P8的左右子節(jié)點也加入待排序隊列,此時待排序隊列包括P2、P6和P9;③重復步驟②,直至待排序隊列為空;④獲得最終排序BLG樹。經過以上步驟構建的排序BLG樹,既可保證層次間的父子關系,又可保證特征值的大小順序。如圖5(c)所示,P8和P6的節(jié)點排序為2和3,保證了層次關系,同時P2和P6的節(jié)點排序為4和3,保證了特征值的排序關系。最后根據排序BLG樹、語義特征值和時空特征值的變化,依次進行降序排列,其中原始軌跡的首尾點直接排序在前2位,進而將以特征值為依據的軌跡數據壓縮,轉換為以特征值排序為基礎的軌跡數據壓縮。圖6列出了Trj1的時空特征值、語義特征值Δsog和Δcog的排序結果,其中P4在排序BLG樹中的序號為1,但在排序結果中需在首尾點之后,因此序號為3。

圖6 特征值排序

3.2 軌跡數據壓縮

作為船舶行為特征挖掘等應用的主要數據源之一,船舶軌跡數據可充分體現船舶航線和航速等時空和語義變化,但二者間的評價標準存在差異[24]。為了融合軌跡特征點的時空和語義評價因素,本文采用加權融合方法[25]對單特征值排序結果進行加權,以獲得最終的排序結果(O),融合不同指標的評價結果并提高運算速度,具體公式如下

O=ωaOst-1+ωbOcog-1+ωcOsog-1

(1)

式中,Ost、Ocog和Osog分別表示軌跡點的時空、航向和航速特征值的排序結果,排序的倒數表示軌跡點的重要性程度;ωa、ωb、ωc是3個重要性的權重,用于平衡不同因素的重要性程度,且滿足ωa+ωb+ωc=1。

特征值隊列排序之后的軌跡點已經按照重要性程度進行排列,排序靠前的軌跡點指時空和語義特征顯著的點,排序靠后的軌跡點指顯著性低的點,進而建立了壓縮比例和排序隊列的關聯關系,根據壓縮比例可壓縮船舶原始軌跡。如式(2)所示,根據壓縮比例(ratio)和軌跡點總數(Countall)計算保留(Countreserved)或刪除(Countremoved)的軌跡點數目,并以排序隊列為基礎,保留排序靠前的Countreserved個軌跡特征點,同時刪除排序靠后的Countremoved個軌跡點,經過以上步驟無須考慮域值參數,根據壓縮比例即可自動獲取壓縮結果

(2)

4 試驗與分析

為驗證軌跡數據壓縮方法的可行性,本文以Windows 10(64位)操作系和C++語言為軟件運行環(huán)境,以AMD Ryzen 9 5900HX with Radeon Graphics 3.30 GHz處理器和32 GB內存為硬件運行環(huán)境,同時以2016年覆蓋全球的中國油輪數據作為試驗軌跡展開驗證,其中軌跡點的上傳間隔為2 s至3 min不等。根據時空信息對原始軌跡進行誤差點刪除和分段等預處理,經統(tǒng)計,試驗數據涉及油輪5265艘,選取軌跡點數目位于900～1000區(qū)間的正常行駛軌跡段進行試驗分析,共包含軌跡10 120條,軌跡點9 625 498個。同時,為消除時空和語義因素對軌跡數據壓縮的影響差異,本文將軌跡的時空和語義特征值排序隊列賦予等量的權重(即ωa是0.5),并將角度(ωb)和速度(ωc)兩個權重均取值為0.25,以確保兩個語義因素對軌跡數據壓縮具有相同的影響。

4.1 壓縮評價方法

船舶軌跡數據壓縮技術可消減無用點數據,進而提升軌跡挖掘的效率,降低數據存儲成本。目前,軌跡數據壓縮的評價指標主要包括壓縮比例、運行時間,以及長度損失和長度損失率[22]。其中SSTC算法根據壓縮比例動態(tài)調整壓縮過程,因此壓縮比例并不作為本文方法的評價指標。運行時間是評價海量軌跡數據壓縮算法優(yōu)劣的重要指標,在相同數據規(guī)模下,算法運行時間短,則效率高且實用性更強。長度損失評價方法可通過原始船舶軌跡點與壓縮后軌跡線的相對偏差進行評價,也可通過原始軌跡和壓縮后的軌跡長度偏差衡量壓縮精度,但前者通常作為DP和SD算法壓縮過程的評判指標,后者難以適應船舶軌跡周期長、跨度大、軌跡間長度差別明顯等特征。為了更加客觀地評價算法性能,本文采用長度損失率表示軌跡的壓縮精度,根據原始軌跡和壓縮后的軌跡長度評價壓縮算法的質量,計算如下

(3)

式中,|PnPn-1|表示2個離散軌跡點的歐氏距離,Length和Length′表示原始軌跡和壓縮后軌跡的總長度,且二者差值表示長度損失(Length_loss),長度損失與原始軌跡長度的比值是長度損失率,用于衡量軌跡數據壓縮精度。

4.2 壓縮算法質量對比分析

影響壓縮軌跡長度損失的最大因素是壓縮比例,壓縮比例越小保留的軌跡點越多,產生的長度損失越小,越能保持軌跡的形態(tài)特征。如圖7所示,SSTC、DP和SD算法的長度損失均隨壓縮比例增加而加大,但即使壓縮比例增加至0.9時,3種算法的長度損失比例均小于0.000 35%,相對于船舶的長途航行,其誤差較小。此外,壓縮比例在0.2～0.5之間時,SSTC算法的壓縮質量較高,而隨著壓縮比例增加,3種壓縮算法的誤差增長明顯。壓縮比例達到0.6后,在同等壓縮條件下,本文為了保留語義特征點需忽視部分時空特征值較小的軌跡點,因此本文的長度損失稍高于其他兩種算法。綜上,SSTC算法結合了DP和SD算法的優(yōu)勢,3種算法壓縮后的軌跡數據,均與原始軌跡具有較高的相似度,在質量方面不分上下。

圖7 軌跡數據壓縮算法的長度損失率

4.3 壓縮算法效率對比分析

本文通過對比分析SSTC、DP和SD算法的運行時間,評價壓縮算法的效率。假如軌跡點的數目為N,傳統(tǒng)DP算法的時間復雜度為O(N2),SD算法的時間復雜度為O(N),而SSTC算法是對DP和SD算法的結合,還需涉及時間復雜度為O(Nlog2N)的堆排序操作,則時間復雜度可估算為O(N2+N+Nlog2N)。然而,DP和SD算法需要通過距離閾值控制壓縮過程,不同地理環(huán)境下需要多次測試閾值,才可獲取指定壓縮比例的結果。而本文可以根據壓縮比例自動獲取需要保留的軌跡特征點,跳過閾值參數測試即可獲得壓縮結果,因此SSTC算法雖然單次運行耗時較長,但實際應用中多次運行的平均效率較高。

為在同一壓縮比例下測量算法時間,經過試驗壓縮比例0.1～0.9分別對應的DP和SD算法的平均閾值為0.08、0.26、0.5、1.3、2.7、6.7、18、100、500 m,本文在不同壓縮比例下分析3種算法的壓縮效率(圖8)。如圖8(a)所示,SD算法的效率最高,壓縮算法單次運行需要10 ms。DP算法的運行效率居中,并且隨著壓縮比例的增加,其運行時間逐漸減少。SSTC算法對全部軌跡點進行排序,與閾值無關,僅與軌跡點的時空和語義特征相關,雖然單次運行時間最長,但僅需構建一次排隊序列,即可根據壓縮比例進行多次壓縮。如圖8(b)所示,經過5次閾值試驗后,SSTC算法平均耗時將明顯低于DP算法,也優(yōu)于SD算法,表明多次測試閾值或閾值動態(tài)變化情況下,SSTC算法效率較高。

圖8 軌跡數據壓縮算法的平均運行時間

4.4 本文壓縮算法實例分析

本文以MMSI號為414213000的油輪為例,針對2016年1月15日至2016年1月25日由波斯灣航行至中國南海的一條軌跡數據(圖9(a)),展示本文方法船舶軌跡數據壓縮結果,其中黑色線為原始軌跡,紅色點表示壓縮比例為0.1情況下,SSTC算法保留的軌跡特征點。如圖9(b)和圖9(c)所示,黃色圓點為本文壓縮算法可以保留,但傳統(tǒng)DP和SD算法無法保留的軌跡點,其中軌跡點31、32和33的COG為6°、12.2°和12.4°,軌跡點32與前后時刻存在較大的航向變化差值,因此保留具有此類對地航向變化明顯的軌跡點。同樣軌跡點717、718和719的SOG分別為3.3、11.1和13.6節(jié),軌跡點718是一個加速特征明顯的軌跡點,因此本文方法也將此類軌跡點保留。此外,圖9(d)中黃色方點展示了DP算法保留但本文方法并未保留的軌跡點,其中軌跡點884的航速和航向語義特征在各自的排序隊列相對靠后,雖然其時空特征變化較為明顯,但無法滿足在現有壓縮比例下的軌跡點保留條件。通過算法實例分析表明,SSTC算法可以在保證時空幾何特征的同時兼顧語義特征,壓縮后的軌跡更能體現船舶的行駛狀態(tài)。

圖9 軌跡數據壓縮實例

5 結 論

海量船舶軌跡數據存在冗余,容易增加存儲負擔和傳輸成本,因此亟須結合業(yè)務需求壓縮船舶軌跡數據。然而船舶軌跡的語義特征和時空特征在度量標準和評價標準方面存在差異,現有軌跡數據壓縮方法無法綜合考慮船舶航行的語義特征和軌跡的時空特征。針對以上問題,本文以AIS為數據源提出了一種顧及時空和語義特征的船舶軌跡數據壓縮方法。首先,分別計算船舶軌跡點的時空、航速和航向特征值,獲取單獨特征值的排序隊列。然后,采用加權融合法綜合軌跡點的時空和語義特征的單獨排序隊列,獲取軌跡點重要性排序。最后,通過船舶軌跡的壓縮效率、質量對比分析,以及壓縮算法實例分析,證明本文方法可有效保留船舶行駛的動態(tài)語義信息和時空形態(tài)特征,也可以根據壓縮比例控制船舶軌跡數據壓縮過程,為海量船舶軌跡數據的存儲與分析提供了基礎。在后續(xù)研究中還需結合高斯分布函數,探索軌跡點特征值變化的分布特征,確定軌跡點的特征變化閾值,進而輔助實現船舶軌跡的語義壓縮方法,進一步提高軌跡數據壓縮效果和質量。此外,如何依據壓縮任務的特點和區(qū)域特征等先驗知識動態(tài)調整時空和語義特征權重,進而提升算法的普適性和通用性,也需進行深入研究。