時(shí)空和語(yǔ)義結(jié)合的船舶軌跡數(shù)據(jù)壓縮方法

劉海硯,郭 漩,劉俊楠

1.信息工程大學(xué)數(shù)據(jù)與目標(biāo)工程學(xué)院,河南 鄭州 450000; 2.鄭州大學(xué)計(jì)算機(jī)與人工智能學(xué)院,河南 鄭州 450000; 3.鄭州大學(xué)地球科學(xué)與技術(shù)學(xué)院,河南 鄭州 450000

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

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

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

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

1.1 軌跡時(shí)空和語(yǔ)義特征

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

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

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

1.2 軌跡數(shù)據(jù)壓縮流程

本文以船舶軌跡數(shù)據(jù)為研究對(duì)象,提出了一種結(jié)合船舶軌跡時(shí)空和語(yǔ)義特征的數(shù)據(jù)壓縮方法。如圖1所示,壓縮算法包括船舶軌跡的時(shí)空特征值計(jì)算、語(yǔ)義特征值計(jì)算、特征點(diǎn)融合排隊(duì)和軌跡數(shù)據(jù)壓縮4個(gè)部分,具體內(nèi)容如下。

(1) 軌跡時(shí)空特征值計(jì)算。以軌跡的時(shí)間標(biāo)簽和經(jīng)緯度坐標(biāo)為基礎(chǔ),通過(guò)DP算法和時(shí)間同步歐氏距離,計(jì)算并獲取軌跡的時(shí)空特征點(diǎn),進(jìn)而通過(guò)少量軌跡點(diǎn)反映軌跡的時(shí)空特征。

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

(3) 特征點(diǎn)融合排隊(duì)。分別對(duì)軌跡點(diǎn)的時(shí)空和語(yǔ)義特征進(jìn)行重要性排序,并采用加權(quán)融合排隊(duì)方法,獲得綜合考慮時(shí)空和語(yǔ)義特征的軌跡點(diǎn)重要性隊(duì)列。

(4) 軌跡數(shù)據(jù)壓縮。按照重要性程度對(duì)軌跡點(diǎn)進(jìn)行排列,僅根據(jù)傳入的壓縮比例獲取目標(biāo)軌跡點(diǎn)數(shù)目即可保留特征顯著的軌跡點(diǎn)并刪除其他點(diǎn),實(shí)現(xiàn)軌跡數(shù)據(jù)壓縮,減少數(shù)據(jù)冗余,優(yōu)化存儲(chǔ)結(jié)構(gòu)。

2 船舶軌跡點(diǎn)的時(shí)空和語(yǔ)義特征值計(jì)算

軌跡數(shù)據(jù)壓縮算法應(yīng)保留更能體現(xiàn)船舶行駛特征的軌跡點(diǎn),而時(shí)空和語(yǔ)義屬于不同的評(píng)價(jià)標(biāo)準(zhǔn),因此需分別在時(shí)空和語(yǔ)義角度計(jì)算軌跡點(diǎn)的特征值。

2.1 軌跡點(diǎn)的時(shí)空特征值計(jì)算

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

圖2 時(shí)空特征值計(jì)算

2.2 軌跡點(diǎn)的語(yǔ)義特征值計(jì)算

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

圖3 對(duì)地航向示例

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

圖4 語(yǔ)義特征值計(jì)算

3 船舶軌跡數(shù)據(jù)壓縮

船舶軌跡通過(guò)部分特征點(diǎn)即可概略表達(dá)軌跡特征,而且軌跡特征點(diǎn)數(shù)目與壓縮比例呈現(xiàn)反比關(guān)系,本文將在語(yǔ)義和時(shí)空綜合約束下壓縮原始船舶軌跡。

3.1 軌跡特征點(diǎn)排隊(duì)

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

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

圖5 原始軌跡和BLG樹(shù)

BLG樹(shù)的結(jié)點(diǎn)存儲(chǔ)層次和偏離值體現(xiàn)了軌跡點(diǎn)表示時(shí)空特征的能力,層次越高、偏移量越大則能力越強(qiáng)。通常父結(jié)點(diǎn)的偏移量會(huì)比子結(jié)點(diǎn)的偏移量大,然而DP算法不能保證子軌跡最大特征值結(jié)點(diǎn)的偏移量一定小于其父軌跡最大特征值結(jié)點(diǎn)的偏移量。

如果直接按照特征值大小排隊(duì)軌跡點(diǎn),將會(huì)破壞軌跡和子軌跡之間的層次關(guān)系,而如果按照先層次后特征值的順序?qū)壽E點(diǎn)進(jìn)行排隊(duì),則會(huì)出現(xiàn)子節(jié)點(diǎn)特征值大于父節(jié)點(diǎn)特征值的現(xiàn)象。如圖5(b)所示,P6是子節(jié)點(diǎn),其偏移量(926 km)大于父節(jié)點(diǎn)P8(910 km),也大于節(jié)點(diǎn)P2(573 km)。為了根據(jù)時(shí)空同步距離構(gòu)建線性排序,需從根節(jié)點(diǎn)開(kāi)始按照先層次、后特征值的方式將BLG樹(shù)轉(zhuǎn)為排序BLG樹(shù)。具體來(lái)說(shuō),①將根節(jié)點(diǎn)P4加入排序BLG樹(shù),序號(hào)為1,并將P4的左右子節(jié)點(diǎn)P2和P8加入待排序隊(duì)列;②在待排序隊(duì)列中選擇偏移量最大的節(jié)點(diǎn)P8加入排序BLG樹(shù),并將P8的左右子節(jié)點(diǎn)也加入待排序隊(duì)列,此時(shí)待排序隊(duì)列包括P2、P6和P9;③重復(fù)步驟②,直至待排序隊(duì)列為空;④獲得最終排序BLG樹(shù)。經(jīng)過(guò)以上步驟構(gòu)建的排序BLG樹(shù),既可保證層次間的父子關(guān)系,又可保證特征值的大小順序。如圖5(c)所示,P8和P6的節(jié)點(diǎn)排序?yàn)?和3,保證了層次關(guān)系,同時(shí)P2和P6的節(jié)點(diǎn)排序?yàn)?和3,保證了特征值的排序關(guān)系。最后根據(jù)排序BLG樹(shù)、語(yǔ)義特征值和時(shí)空特征值的變化,依次進(jìn)行降序排列,其中原始軌跡的首尾點(diǎn)直接排序在前2位,進(jìn)而將以特征值為依據(jù)的軌跡數(shù)據(jù)壓縮,轉(zhuǎn)換為以特征值排序?yàn)榛A(chǔ)的軌跡數(shù)據(jù)壓縮。圖6列出了Trj1的時(shí)空特征值、語(yǔ)義特征值Δsog和Δcog的排序結(jié)果,其中P4在排序BLG樹(shù)中的序號(hào)為1,但在排序結(jié)果中需在首尾點(diǎn)之后,因此序號(hào)為3。

圖6 特征值排序

3.2 軌跡數(shù)據(jù)壓縮

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

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

(1)

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

特征值隊(duì)列排序之后的軌跡點(diǎn)已經(jīng)按照重要性程度進(jìn)行排列,排序靠前的軌跡點(diǎn)指時(shí)空和語(yǔ)義特征顯著的點(diǎn),排序靠后的軌跡點(diǎn)指顯著性低的點(diǎn),進(jìn)而建立了壓縮比例和排序隊(duì)列的關(guān)聯(lián)關(guān)系,根據(jù)壓縮比例可壓縮船舶原始軌跡。如式(2)所示,根據(jù)壓縮比例(ratio)和軌跡點(diǎn)總數(shù)(Countall)計(jì)算保留(Countreserved)或刪除(Countremoved)的軌跡點(diǎn)數(shù)目,并以排序隊(duì)列為基礎(chǔ),保留排序靠前的Countreserved個(gè)軌跡特征點(diǎn),同時(shí)刪除排序靠后的Countremoved個(gè)軌跡點(diǎn),經(jīng)過(guò)以上步驟無(wú)須考慮域值參數(shù),根據(jù)壓縮比例即可自動(dòng)獲取壓縮結(jié)果

(2)

4 試驗(yàn)與分析

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

4.1 壓縮評(píng)價(jià)方法

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

(3)

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

4.2 壓縮算法質(zhì)量對(duì)比分析

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

圖7 軌跡數(shù)據(jù)壓縮算法的長(zhǎng)度損失率

4.3 壓縮算法效率對(duì)比分析

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

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

圖8 軌跡數(shù)據(jù)壓縮算法的平均運(yùn)行時(shí)間

4.4 本文壓縮算法實(shí)例分析

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

圖9 軌跡數(shù)據(jù)壓縮實(shí)例

5 結(jié) 論

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