閾值引導采樣法的船舶軌跡簡化算法

張銀昊，潘家財,趙夢鴿

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

0 引言

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

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

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

1 閾值引導采樣算法

1.1 相關理論

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

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

1.2 參數定義

1.2.1 初始軌跡信息

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

簡化后的軌跡信息：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為速度閾值。

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

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數據，該類船舶自主模式下信息更新率最大為180 s[16]。中斷特征點以時間差為閾值進行判斷，再考慮誤差，tmax一般選取為180～300 s。

1.2.4 方位角閾值

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

1.3 軌跡點特征優先級的判斷

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

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

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

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

1.4 閾值引導采樣法算法流程圖

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

1.5 閾值引導采樣法的偽代碼

輸入原始軌跡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分別為軌跡點集簡化后選取的特征點的起點和終點。

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

1)輸入：原始軌跡T，參數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 實驗結果分析

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

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

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

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

2.1 簡化率和誤差定義

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

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

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

2.2 軌跡簡化實驗結果分析

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

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

在進行中斷特征點的判定后，Smax=0時的閾值引導采樣法，即為Long[10]提出的角度閾值法。采用閾值引導采樣法分別對角度閾值的變化以及速度閾值的變化進行實驗，簡化結果可知：當角度閾值固定時，隨著速度閾值的增大，每一條折線的縱坐標依次遞減，數據減少，簡化效率提高；當速度閾值固定，隨著角度閾值的增大，每一列(相同速度的不同角度閾值視為一列)的縱坐標依次遞減，數據減少，簡化效率提高?？梢姳舅惴ū冉嵌乳撝捣ㄓ辛溯^大提升。例如：實驗中選取角度閾值法進行簡化，15°角度閾值時，簡化率最高為：η=(n-p15_0)/n=(3650-2726)/3650=25.31%。

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

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

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

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

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

在軌跡簡化的應用方面，閾值引導采樣法不僅有較好的聚類效果，而且能精準地識別角度閾值法不能識別的異常軌跡。

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

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

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

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

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

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

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

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

3 結論

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

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