張銀昊，潘家財,趙夢鴿

(集美大學(xué)航海學(xué)院，福建 廈門 361021)

0 引言

船舶AIS(automatic identification system)數(shù)據(jù)蘊含豐富的船舶信息，利用這些數(shù)據(jù)能夠發(fā)現(xiàn)和分析船舶的行為，從而為海事部門對船舶航行的安全監(jiān)管和決策提供支持服務(wù)[1-2]。船舶AIS數(shù)據(jù)具有量大、實時、多樣等特征，準(zhǔn)確地存儲和提取這些數(shù)據(jù)是分析船舶軌跡的前提，但是海量的數(shù)據(jù)會使查詢和計算效率降低，因此，通常需要采用軌跡簡化的方法來處理軌跡數(shù)據(jù)，進而保留關(guān)鍵數(shù)據(jù)點，減少軌跡數(shù)據(jù)存儲的負(fù)擔(dān)。目前，國內(nèi)外學(xué)者對船舶軌跡簡化進行了許多研究。文獻(xiàn)[3]提出了使用垂直歐式距離(perpendicular euclidean distance)進行軌跡簡化；時間同步歐式距離(time synchronized euclidian distance)[4]是基于時間同步的軌跡計算方式來產(chǎn)生近似軌跡。Zhao[5]基于douglas-peucker模型[6]建立軌跡點批處理模式,但在實際的軌跡簡化處理中,很難實現(xiàn)批處理模式，該研究僅僅衡量了船舶的經(jīng)緯度的位置信息，忽視了航速和航向信息。潘家財[7]根據(jù)船舶航行的特征，對航向和航速變化率設(shè)置閾值進行特征點的選??；而肖瀟[8]利用最小描述長度準(zhǔn)則[9](minimum description length，MDL)進一步在航速、航向變化率之上篩選特征點，但是該方法缺少對AIS信息多因素的綜合考慮。角度閾值法[10]是一種以軌跡點的角度變化作為衡量標(biāo)準(zhǔn)的軌跡簡化方法，計算每一個軌跡點的角度變化量，若大于閾值，當(dāng)前軌跡點視為特征點。

軌跡簡化主要運用于軌跡聚類，軌跡聚類主要分為兩種：1)將船舶的軌跡視為整體進行聚類[11]；2)將船舶軌跡進行分段，分別對分段后的軌跡子段進行聚類分析，將相似的軌跡子段歸類為簇，保證軌跡運動的細(xì)節(jié)信息不丟失[12-15]。目前，對兩種簡化方式均能兼顧的軌跡簡化方法較少。

本文根據(jù)船舶移動軌跡的運動特征，在角度閾值法[10]的基礎(chǔ)上提出一種新的軌跡簡化方法——閾值引導(dǎo)采樣法，并采用聚類實驗方法進行驗證。實驗結(jié)果表明，該方法在軌跡段聚類和整體軌跡聚類的應(yīng)用上均有較好的聚類效果。

1 閾值引導(dǎo)采樣算法

1.1 相關(guān)理論

閾值引導(dǎo)采樣法是在角度閾值法[10]的基礎(chǔ)上提出的一種新的簡化方法。角度閾值法[10]通過設(shè)置角度的閾值，并將當(dāng)前點與上一個點之間的角度進行對比，角度差大于閾值時，當(dāng)前軌跡點視為特征點。閾值引導(dǎo)采樣法沿用了角度特征判斷的特點，設(shè)置了船舶轉(zhuǎn)向角變化的角度閾值θmax，進行角度特征的判定；同時，還增設(shè)了速度閾值Smax，以及方位角閾值βmax，從船舶速度及轉(zhuǎn)角兩個方面對船舶軌道特征點做進一步判斷。

船舶數(shù)據(jù)出現(xiàn)時間位置不合理的情況主要為：在較大時間區(qū)間內(nèi)反復(fù)進出研究水域的邊界；在較大時間段內(nèi)突然丟失船舶的軌跡數(shù)據(jù)；僅有一個數(shù)據(jù)點的船舶。為解決這個問題，設(shè)置了中斷特征點(Interrupted feature point)，為了判斷中斷特征點，對軌跡設(shè)置了時間間隔閾值tmax，準(zhǔn)確地分割軌跡。

1.2 參數(shù)定義

1.2.1 初始軌跡信息

原始軌跡Ti={p1,…,pj,…,pn}，pj=(i,sj,cj,tj,lonj,latj)，其中：Ti是船舶為i的軌跡數(shù)據(jù)點集合；pj為軌跡i的第j個軌跡點；sj為軌跡點j的SOG(speed over ground)；cj為軌跡點j的COG(course over ground)；tj為軌跡點j的時刻；lonj和latj分別表示軌跡點j的經(jīng)度和緯度。

簡化后的軌跡信息：Tmsimp={pmsimp_1,pmsimp_2,…,pmsimp_k,…,pmsimp_d}，pmsimp_k表示Ti中的特征點。

1.2.2 角度閾值和速度閾值

對于Ti中的軌跡點pj，滿足Cdiff≥θmax，則pj視為角度特征點。其中：角度差Cdiff=|cj-1-cj|；θmax為角度閾值。

對于Ti中的軌跡點pj，滿足Sdiff≥Smax，則pj視為速度特征點。其中：速度差Sdiff=|sj-1-sj|；Smax為速度閾值。

通常角度閾值和速度閾值需要根據(jù)研究對象的運動習(xí)慣來確定。例如，船舶的極限舵角通常為30°～35°，航行時船舶改變航向次數(shù)往往多于改變航速次數(shù)。因此，角度閾值一般設(shè)置為0°～5°，若為了追求更簡潔的簡化軌跡，可將角度閾值設(shè)為15°，而速度閾值一般在0～3 kn內(nèi)選取。

1.2.3 中斷特征點

對于Ti中的軌跡點pj，滿足tdiff≥tmax，則pj視為中斷特征點，pj=pmsimp_d，pj+1=pm+1simp_1。其中：時間差tdiff=|tj-1-tj|；tmax為時間間隔閾值。選取A級船長230 m以上船舶的AIS數(shù)據(jù)，該類船舶自主模式下信息更新率最大為180 s[16]。中斷特征點以時間差為閾值進行判斷，再考慮誤差，tmax一般選取為180～300 s。

1.2.4 方位角閾值

對于Ti中的軌跡點pj，滿足βdiff≥βmax，則pj視為方位角特征點。其中：βmax為方位角閾值，軌跡線段的坐標(biāo)方位角差為aziij=|ci-cj|，方位角差βdiff=|azii(i+1)-aziij|，ci為pj的上一個特征點的COG，cj為pj的COG。通常方位角閾值的大小需要根據(jù)研究水域的轉(zhuǎn)向點的角度來確定，例如，當(dāng)轉(zhuǎn)向點處兩航道的夾角為20°時，為了保留一定的空間，方位角閾值設(shè)置需要在夾角基礎(chǔ)上增加約10°，即方位角閾值設(shè)為30°，然后在這個閾值附近進行調(diào)整，進行多次的實驗，選取更精確的閾值。

1.3 軌跡點特征優(yōu)先級的判斷

在軌跡簡化過程中，為避免數(shù)據(jù)點出現(xiàn)的時間位置不合理而被視為一條軌跡的情況，應(yīng)優(yōu)先判斷數(shù)據(jù)點是否為中斷特征點，將軌跡進行分割。在船舶軌跡分析中，船位的突變必然導(dǎo)致航速或航向的異常，但船速和航向的突變未必會帶來船位的異常。根據(jù)信息熵理論[17]，船位異常事件所攜帶的信息大于航速與航向異常事件的信息量，在判斷優(yōu)先級上優(yōu)先判斷信息量較大的屬性，能減少運算量，提高運算效率。因此，需要優(yōu)先判斷數(shù)據(jù)點的方位角特征，再判斷角度與速度特征。

軌跡點特征判斷具體如下：

1)判斷點的方向和速度位于上一個點的方向和速度的閾值區(qū)間內(nèi)，則該點視為可簡化。如圖1所示，O、A、B、C、D為一條船舶的5個AIS軌跡點，按照時序排列；Vmin為上一個點的SOG；Vmax=Vmin+Smax；2θmax的中分線方向為上一個點的COG；FX表示船舶在點X的COG。由于O、D兩點為起點與終點，無需判斷，均視為特征點。從第二個點A開始判斷是否屬于特征點，F(xiàn)A的長度為船舶在A點的SOG，當(dāng)F的長度沒有落在(Vmin,Vmax)內(nèi)時，A點因速度變化過大而視為軌跡的特征點；同理，F(xiàn)A的方向沒有落在2θmax范圍內(nèi)，則A點因角度變化過大而視為軌跡的特征點。因此，當(dāng)判斷點不滿足以上任意一個條件，就將該點視為軌跡特征點。同理，下一個待判斷點B，將上一個點A的SOG視為Vmin，點A的COG視為2θmax的中分線方向。以此類推，直至軌跡的倒數(shù)第二個點，簡化完全部軌跡點。

2)方位角的特征判斷如圖2所示。其中，TOE和TOA為軌跡OE和OA的線方位角，點A、B、C、D均滿足角度和速度閾值的傳遞要求，由于|TOE-TOA|>βmax，表明從D點之后所有點超過方位角閾值，因此，將超過方位角閾值E點的上一個點D視為軌跡的方位角特征點，最終簡化軌跡為ODE，即OD段和DE段軌跡；當(dāng)2βmax=360°時，不設(shè)置方位角閾值，此時算法為整體軌跡的簡化；當(dāng)2βmax<360°時，算法存在方位角閾值判定，為分段軌跡的簡化。

1.4 閾值引導(dǎo)采樣法算法流程圖

算法流程如圖3所示。首先輸入一條軌跡的特征點集，對數(shù)據(jù)點進行中斷特征點的判定，將軌跡進行分割；其次，對數(shù)據(jù)點進行方位角特征判定，對軌跡進行分段；最后，通過判斷角度與速度特征進行子軌跡的簡化。

1.5 閾值引導(dǎo)采樣法的偽代碼

輸入原始軌跡T={T1,…,Ti,…,TN}，Ti={p1,…,pj,…,pn}，pj=(i,sj,cj,tj,lonj,latj)；輸入速度閾值Smax、角度閾值θmax、方位角閾值βmax、時間間隔閾值tmax。簡化后的軌跡段集合為：Lsimp={Psimp_1,…,Psimp_m,…,Psimp_k},(1≤m≤k)。其中簡化的軌跡段Psimp_m(pmstart,pmdown)元素pmstart和pmdown分別為軌跡點集簡化后選取的特征點的起點和終點。

基于閾值引導(dǎo)采樣法的船舶軌跡簡化算法如下：

1)輸入：原始軌跡T，參數(shù)Smax、θmax、βmax、tmax，

2)foriinN，

3) forjinn:

4)tdiff=|tj-tj-1|,Sdiff=|sj-1-sj|,Cdiff=|cj-1-cj|，

5) iftdiff>tmax:

6)pj-1=pmdown,m=m+1，pj=pmstart，

7) continue，

8) Else if |aziii+1-aziij|>βmax:

9)pmdown=pj-1，m=m+1，pmstart=pj-1，

10) ElseCdiff>θmaxorSdiff>Smax:

11)pmdown=pj-1，m=m+1，pmstart=pj-1，

12)輸出：軌跡段集合Lsimp。

2 實驗結(jié)果分析

本文選取了兩組實驗數(shù)據(jù)與角度閾值法進行對比分析，為了避免誤差分析的不準(zhǔn)確，軌跡的預(yù)處理條件均相同，采用的驗證聚類算法為DBSCAN[18]，軌跡相似性度量的方法選擇為Hausdorff距離[17]。其中，DBSCAN的參數(shù)Eps(領(lǐng)域距離閾值)和MinPts(密度閾值)為反復(fù)多次實驗選取。實驗所有涉及距離和方位角信息均以WGS84為坐標(biāo)進行計算。

第一組軌跡簡化和聚類實驗，選取了廈門港2012年1月1日全天的AIS數(shù)據(jù)，一共有88條船舶，3 650個數(shù)據(jù)點。水域范圍選取24.340°N～24.450°N，118.130°E～118.167°E；方位角閾值參數(shù)βmax=180°;時間間隔閾值tmax=180 s，180 s為AIS信息播發(fā)的最大間隔。同時為了使初始數(shù)據(jù)具有可操作性與真實性，刪除了以下幾種情況的AIS數(shù)據(jù)：MMSI≤100000000；0°>COG；COG>360°；SOG>50 kn；SOG<0 kn。

第二組簡化分段聚類實驗，選取了廈門港2016年1月1日至2016年1月13日的10 000條船舶的AIS數(shù)據(jù)點，水域范圍選取24.350°N～24.600°N，117.900°E～118.150°E，船舶類型選取船長大于230 m的貨船。各參數(shù)值為：時間間隔閾值為180 s;方位角閾值設(shè)置為15°；因船舶的移動特性，將角度閾值設(shè)置為10°;速度閾值設(shè)置為3 kn；因廈門港航道寬度約為300 m，經(jīng)反復(fù)實驗將DBSCAN的Eps設(shè)置為230 m，MinPts為5。

第三組實驗與第二組實驗數(shù)據(jù)水域范圍相同，選取2016年2月1日至2016年2月9日的20 000條AIS數(shù)據(jù)點，船舶類型不做限定，船長選擇大于20 m。各參數(shù)取值為：時間間隔閾值為180 s；方位角閾值為20°；因船舶的移動特性，將角度閾值設(shè)置為10°；速度閾值為3 kn；經(jīng)反復(fù)實驗將DBSCAN的Eps設(shè)置為600 m，MinPts為5。

2.1 簡化率和誤差定義

定義1：設(shè)軌跡簡化率η為剩余簡化軌跡點的數(shù)量n-pa_b與原始軌跡點數(shù)量n之間的比值，即η=(n-pa_b)/n。其中：pa_b表示角度閾值為a，速度閾值為b時的簡化軌跡點數(shù)量；n≥2，且n≥pa_b。

定義2：設(shè)簡化效率μ為A方法軌跡簡化率ηA與B方法軌跡簡化率ηB的比值，即μ=ηA/ηB。

定義3：設(shè)簡化誤差率δ為A方法簡化后剩余軌跡與B方法簡化后剩余軌跡之差與原始軌跡點數(shù)之間的比值，即δ=(pA-pB)/n。

2.2 軌跡簡化實驗結(jié)果分析

用第一組實驗數(shù)據(jù)分析船舶軌跡簡化結(jié)果。原始軌跡如圖4所示，該水域包括兩條航道和一個錨泊水域，其中位于水域最頂部較多曲折軌跡為錨泊水域，中間與下半部分的軌跡集為兩條航道。

采用控制變量法對各參數(shù)的簡化效率進行分析,簡化后剩余的軌跡點實驗結(jié)果如圖5所示。

在進行中斷特征點的判定后，Smax=0時的閾值引導(dǎo)采樣法，即為Long[10]提出的角度閾值法。采用閾值引導(dǎo)采樣法分別對角度閾值的變化以及速度閾值的變化進行實驗，簡化結(jié)果可知：當(dāng)角度閾值固定時，隨著速度閾值的增大，每一條折線的縱坐標(biāo)依次遞減，數(shù)據(jù)減少，簡化效率提高；當(dāng)速度閾值固定，隨著角度閾值的增大，每一列(相同速度的不同角度閾值視為一列)的縱坐標(biāo)依次遞減，數(shù)據(jù)減少，簡化效率提高。可見本算法比角度閾值法有了較大提升。例如：實驗中選取角度閾值法進行簡化，15°角度閾值時，簡化率最高為：η=(n-p15_0)/n=(3650-2726)/3650=25.31%。

以閾值引導(dǎo)采樣法進行軌跡簡化，當(dāng)角度閾值為15°，速度閾值為3 kn，軌跡簡化率η=(n-p15_3)/n=(3650-338)/3650=90.73%;簡化效率μ=η15_3/η15_0=90.71%/25.31%≈3.6。

即閾值引導(dǎo)采樣法的簡化效率是角度閾值法的3.6倍。同理，當(dāng)以速度閾值不變，角度閾值變化的情況下，隨著角度閾值增大，簡化效率也增大，簡化剩余的軌跡數(shù)越少。

簡化效率并非越高越好，而是應(yīng)該在盡可能保留特征屬性的情況下進行高效的簡化。在角度閾值為0°，速度閾值為2 kn與3 kn的條件下，簡化結(jié)果表明，僅存在7個數(shù)據(jù)點的相鄰速度變化超過了2 kn，即速度特征點為7個；角度閾值為15°，速度閾值為2 kn與3 kn的條件下，簡化結(jié)果表明，存在16個數(shù)據(jù)點的相鄰速度變化超過了2 kn，即多識別出9個角度特征點。因此相比角度閾值法，閾值引導(dǎo)采樣法的簡化誤差率δ=[(p15_2-p15_3)-(p0_2-p0_3)]/n=[(404-388)-(3493-3486)]/3650=2.47‰。

以上分析表明，經(jīng)過處理后的數(shù)據(jù)依舊具有較好的特征點識別率，能極大地保留原始軌跡的形狀與特征點。

2.3 軌跡簡化算法的聚類實驗

在軌跡簡化的應(yīng)用方面，閾值引導(dǎo)采樣法不僅有較好的聚類效果，而且能精準(zhǔn)地識別角度閾值法不能識別的異常軌跡。

第一組實驗的軌跡聚類結(jié)果如圖6所示。軌跡集一共分為三個簇(cluster)，代表了3條習(xí)慣航路的軌跡，航跡A和航跡B被標(biāo)記為異常軌道。其中：航跡A橫穿中間航道，該部分原始軌跡局部放大后如圖7所示；航跡B處于中間航道和下側(cè)航道中間，閾值引導(dǎo)采樣法的軌跡聚類結(jié)果如圖8所示。除了3條習(xí)慣航路的軌跡被準(zhǔn)確識別外，橫穿航道的航跡A以及部分航行數(shù)據(jù)異常的軌跡也被識別出，橫穿航道的航跡A被進行了準(zhǔn)確分割，局面放大后如圖9所示。

綜上可知：對比角度閾值法，本算法不僅能完全識別橫穿航道的軌跡，而且可以對時間間隔過大的軌跡進行分割，避免了反復(fù)進出研究水域的相同MMSI的軌跡點被視為同一時序中的序列，提高了數(shù)據(jù)的質(zhì)量。

第二組實驗在區(qū)域較大且環(huán)境復(fù)雜的港口水域進行。該實驗不同于整體聚類，需要將軌跡先進行分段簡化再聚類。由于主航道至海滄航道的轉(zhuǎn)向較小，因此從海滄航道至主航道的來往船舶軌跡視為一類；而東渡航道至主航道往來船舶在Y型分叉口有極大的轉(zhuǎn)向，因此視為兩類船舶軌跡，一類為東渡航道至主航道往來船舶截至Y型分叉口的軌跡，一類為主航道至東渡航道來往船舶截至Y型分叉口的軌跡。

實驗的聚類結(jié)果如圖10所示。其中：簇1為從海滄航道至主航道的船舶來往軌跡；簇2即為東渡航道至主航道往來船舶截至Y型分叉口的軌跡；簇3為主航道至東渡航道來往船舶截至Y型分叉口的軌跡。

實驗結(jié)果表明：本文提出的軌跡簡化算法對原始軌跡進行簡化后，其簡化的軌跡能應(yīng)用于軌跡聚類，能分段聚類出較大轉(zhuǎn)向的船舶軌跡。

第三組實驗數(shù)據(jù)為船長20 m以上的船舶在廈門港的聚類，此時船舶軌跡出現(xiàn)在招銀航道、廈鼓航道，tmax=180 s，Smax=3kn，θmax=10°，βmax=20°，船舶的軌跡點的數(shù)量由20 000簡化至3930，簡化率η=(n-p10_3)/n=(20 000-3930)/20 000=80.35%，軌跡簡化效果較為理想。

實驗的聚類結(jié)果如圖11所示。其中：簇1為主航道至招銀航道的船舶往來軌跡；簇2為海滄航道至主航道的船舶來往軌跡；簇3為東渡航道的船舶軌跡；簇4為主航道至廈鼓航道的船舶往來軌跡；簇5位為東渡航道至主航道往來船舶截至Y型分叉口的軌跡。

實驗結(jié)果表明：在頻繁變向的船舶軌跡數(shù)據(jù)中，本文提出的簡化算法簡化率良好，將簡化的軌跡數(shù)據(jù)進行聚類實驗，聚類效果較為理想。

3 結(jié)論

閾值引導(dǎo)采樣法包含角度閾值法的特征點判定，而且綜合衡量了軌跡的速度、方向、位置、時間信息。該算法不僅比角度閾值法有更好的簡化效率，并且可以根據(jù)不同的閾值選取不同精度的簡化結(jié)果，具有更加良好的適應(yīng)性。

在計算復(fù)雜度方面，閾值引導(dǎo)采樣法與角度閾值法一致，僅需對所有的點遍歷一次，具有高效的計算復(fù)雜度。閾值引導(dǎo)采樣法簡化誤差率為2.47‰，符合實際使用的允許誤差要求。在軌跡簡化后聚類適應(yīng)性上，閾值引導(dǎo)采樣算法不僅能進行整體的軌跡簡化，而且還能對軌跡進行簡化分段聚類。