閾值引導(dǎo)采樣法的船舶軌跡簡(jiǎn)化算法

張銀昊，潘家財(cái),趙夢(mèng)鴿

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

0 引言

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

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

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

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

1.1 相關(guān)理論

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

船舶數(shù)據(jù)出現(xiàn)時(shí)間位置不合理的情況主要為：在較大時(shí)間區(qū)間內(nèi)反復(fù)進(jìn)出研究水域的邊界；在較大時(shí)間段內(nèi)突然丟失船舶的軌跡數(shù)據(jù)；僅有一個(gè)數(shù)據(jù)點(diǎn)的船舶。為解決這個(gè)問題，設(shè)置了中斷特征點(diǎn)(Interrupted feature point)，為了判斷中斷特征點(diǎn)，對(duì)軌跡設(shè)置了時(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ù)點(diǎn)集合；pj為軌跡i的第j個(gè)軌跡點(diǎn)；sj為軌跡點(diǎn)j的SOG(speed over ground)；cj為軌跡點(diǎn)j的COG(course over ground)；tj為軌跡點(diǎn)j的時(shí)刻；lonj和latj分別表示軌跡點(diǎn)j的經(jīng)度和緯度。

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

1.2.2 角度閾值和速度閾值

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

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

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

1.2.3 中斷特征點(diǎn)

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

1.2.4 方位角閾值

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

1.3 軌跡點(diǎn)特征優(yōu)先級(jí)的判斷

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

軌跡點(diǎn)特征判斷具體如下：

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

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

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

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

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

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

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

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 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

2.1 簡(jiǎn)化率和誤差定義

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

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

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

2.2 軌跡簡(jiǎn)化實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

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

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

2.3 軌跡簡(jiǎn)化算法的聚類實(shí)驗(yàn)

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

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

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

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

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

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

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

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

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

3 結(jié)論

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

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