基于信息熵的船舶軌跡自適應(yīng)分段壓縮算法

楊家軒　馬令琪　

摘要：針對(duì)目前軌跡壓縮研究僅考慮船舶位置而忽略船舶操縱特征以及目前軌跡分段研究需確定多種閾值等問題，提出一種基于信息熵的船舶軌跡自適應(yīng)分段壓縮算法。該算法綜合考慮船舶位置、航向和速度等信息，引入信息熵作為評(píng)判軌跡特征點(diǎn)的指標(biāo)，從船舶軌跡中提取分段關(guān)鍵點(diǎn)，進(jìn)而自適應(yīng)劃分出多條子軌跡，再利用自頂向下時(shí)間比（topdown time ratio， TDTR）算法分別對(duì)子軌跡進(jìn)行壓縮。以老鐵山水域船舶交通數(shù)據(jù)為實(shí)驗(yàn)樣本，從壓縮誤差、運(yùn)行效率等方面對(duì)比分段前后的軌跡壓縮效果。結(jié)果表明，該算法能根據(jù)船舶的航向和速度信息對(duì)船舶軌跡進(jìn)行自適應(yīng)分段，分段后再壓縮可大幅降低各種壓縮誤差，提升壓縮效率，特別在軌跡數(shù)據(jù)量較大情況下效果更佳。

關(guān)鍵詞：? 船舶軌跡; 分段; 壓縮; 信息熵

中圖分類號(hào)：? U675.7;U697.3文獻(xiàn)標(biāo)志碼：? A

An adaptive segmentation and compression algorithm of ship

trajectory based on entropy of information

Abstract： Aiming at the current trajectory compression research that only considers the ship position but ignores the ship maneuvering characteristics， and the current trajectory segmentation research that needs to determine multiple thresholds， an adaptive segmentation and compression algorithm based on the entropy of information is proposed. The algorithm comprehensively considers the ship position， heading and speed， introduces the entropy of information as an index to judge the trajectory feature points， extracts the key segmentation points from a ship trajectory to adaptively divide the trajectory into multiple subtrajectories， and then compresses subtrajectories separately using the topdown time ratio （TDTR） algorithm. The ship traffic data of Laotieshan waters are taken as the experimental sample， and the effects of trajectory compression before and after segmentation are compared in terms of the compression error and efficiency. The results show that， the algorithm can adaptively segment a ship trajectory according to the ship heading and speed information， and the segmentation compression can significantly reduce various compression errors and improve the compression efficiency， especially in the case of large amount of trajectory data.

Key words： ship trajectory; segmentation; compression; entropy of information

引言

海洋約覆蓋了71%的地球表面，大多數(shù)國際貿(mào)易都是通過海運(yùn)完成的。面對(duì)愈加復(fù)雜的海上航行環(huán)境，利用船舶自動(dòng)識(shí)別系統(tǒng)（automatic identification system， AIS）感知海上態(tài)勢(shì)越來越重要[1]。不同的船舶由于運(yùn)動(dòng)模式的不同，以大約2 s～6 min的時(shí)間間隔發(fā)送AIS信息，因此AIS數(shù)據(jù)量非常大[2]。為減少AIS數(shù)據(jù)處理過程中的存儲(chǔ)和計(jì)算成本，通常需要對(duì)軌跡進(jìn)行壓縮。

目前，船舶軌跡壓縮主要有在線壓縮和離線壓縮兩類方法。在線壓縮方法無須得到整艘船的軌跡。高邈等[3]將改進(jìn)后的滑動(dòng)窗（sliding window，SW）算法應(yīng)用到AIS軌跡壓縮中。SUN等[4]基于掃描拾取移動(dòng)（scanpickmove，SPM）和SW的思想提出SWSPM算法。ZHANG等[5]提出一種考慮位置、方向和速度的在線多維船舶軌跡壓縮算法。而離線壓縮方法考慮完整的軌跡，比在線壓縮方法更容易實(shí)現(xiàn)全局優(yōu)化。道格拉斯普克（DouglasPeucker，DP）算法是一種常用的離線壓縮方法。除地理位置信息之外，AIS數(shù)據(jù)還包含時(shí)間、速度、航向等重要信息[6]。一些學(xué)者在使用船舶位置進(jìn)行船舶軌跡離線壓縮的基礎(chǔ)上拓展考慮了時(shí)間、速度、航向等其他信息。MERATNIA等[7]提出了自頂向下時(shí)間比（topdown time ratio， TDTR）算法，以同步歐氏距離（synchronous Euclidean distance， SED）代替歐氏距離對(duì)DP算法進(jìn)行改進(jìn)。QI等[8]提出一種識(shí)別船舶航向變化并提取船舶軌跡代表點(diǎn)的方法。ZHAO等[9]考慮軌跡點(diǎn)的航向信息，對(duì)DP壓縮算法進(jìn)行了改進(jìn)。ZHU等[10]考慮軌跡點(diǎn)的位置、航向和航速，提出一種多維特征距離計(jì)算方法。根據(jù)航向和速度等信息對(duì)軌跡進(jìn)行分段預(yù)處理可以使壓縮軌跡保留航向和速度信息。YUAN等[11]提出一種基于軌跡轉(zhuǎn)向角的分段方法，但該方法只考慮了軌跡方向的突變。何愛林等[12]考慮了轉(zhuǎn)向角突變及其累計(jì)變化，但沒有考慮速度因素。韓陳壽等[13]通過在給定距離內(nèi)找軌跡的開放角和變速點(diǎn)對(duì)軌跡進(jìn)行分段。金佳龍等[14]和盛凱等[15]提出基于船舶運(yùn)動(dòng)模式的軌跡分段算法。宋鑫等[16]在進(jìn)行壓縮前對(duì)軌跡進(jìn)行了分段處理。這幾種船舶軌跡分段方法雖然考慮了船舶的航向或速度信息，但需要人為確定航向閾值、速度閾值甚至?xí)r間閾值，不同的閾值對(duì)結(jié)果影響較大，因此具有一定局限性。F6AB678E-6402-4886-AC74-C9922E3EE7A6

對(duì)時(shí)間跨度長、空間跨度大、數(shù)據(jù)量極大的船舶軌跡進(jìn)行壓縮時(shí)，分段是必不可少的一步，以子軌跡段為分析對(duì)象也有利于發(fā)現(xiàn)軌跡的局部相似運(yùn)動(dòng)模式。因此，本文提出一種基于信息熵的船舶軌跡自適應(yīng)分段壓縮算法，根據(jù)船舶的航向和速度等特征對(duì)軌跡進(jìn)行無須確定多種閾值的自適應(yīng)分段，再對(duì)子軌跡段分別進(jìn)行基于自適應(yīng)閾值的TDTR壓縮。

1基本定義和算法

1.1軌跡相關(guān)的基本定義

原始軌跡：原始AIS軌跡T為若干有序軌跡點(diǎn)數(shù)據(jù)的集合，可被表述為T={pii=1，2，…，n}，其中pi=（xi，yi，ti，ci，si），xi、yi、ti、ci和si分別代表第i個(gè)軌跡點(diǎn)所對(duì)應(yīng)的經(jīng)度、緯度、時(shí)刻、航向和速度。

壓縮軌跡：對(duì)原始軌跡T采用壓縮算法刪除若干軌跡點(diǎn)（除首、尾點(diǎn)）后得到的軌跡，用T′表示，T′={p′ii=1，2，…，m;m≤n}。

子軌跡：在原始軌跡T（或壓縮軌跡T′）中，任意兩點(diǎn)之間軌跡點(diǎn)組成的軌跡稱為T（或T′）的子軌跡。

1.2壓縮性能評(píng)估方法

軌跡壓縮會(huì)帶來不同維度上的損失[17]。本文選取航向誤差、SED誤差、速度誤差、壓縮率、運(yùn)行時(shí)間等5個(gè)指標(biāo)評(píng)估軌跡壓縮算法的性能。

定義壓縮率為r=1-T′/T，其中T代表原始軌跡點(diǎn)的數(shù)目，T′代表壓縮后軌跡點(diǎn)的數(shù)目。運(yùn)行時(shí)間指對(duì)軌跡進(jìn)行壓縮需要的時(shí)間，是衡量壓縮算法執(zhí)行效率的重要依據(jù)。

平均SED誤差SED的計(jì)算公式為? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（1）式中：Pi指原始軌跡中的第i個(gè)點(diǎn);n指原始軌跡點(diǎn)數(shù)。當(dāng)Pi被保留在壓縮后的軌跡中時(shí)，dSED（Pi）=0;當(dāng)Pi未被保留在壓縮后的軌跡中時(shí)，dSED（Pi）為以壓縮后軌跡上Pi前后兩個(gè)相鄰的點(diǎn)為基準(zhǔn)點(diǎn)計(jì)算的Pi的同步歐氏距離。

平均航向（或速度）誤差指原始軌跡中每個(gè)點(diǎn)的航向（或速度）誤差的平均值。當(dāng)Pi被保留在壓縮后的軌跡中時(shí)，Pi的航向（或速度）誤差為0;當(dāng)Pi未被保留在壓縮后的軌跡中時(shí)，Pi的航向（或速度）誤差為Pi的航向（或速度）與壓縮后軌跡上Pi前后兩個(gè)相鄰點(diǎn)的平均航向（或速度）差值的絕對(duì)值。

1.3TDTR算法

TDTR算法是一種基于DP算法的考慮全局特征的壓縮算法。不同于DP算法直接采用歐氏距離作為壓縮衡量標(biāo)準(zhǔn)，TDTR算法采用的是SED。SED是一種將位置和時(shí)間考慮在內(nèi)的距離度量，如圖1所示，點(diǎn)Pm的SED（用dSED（Pm）表示）為點(diǎn)Pm與其同步點(diǎn)P′m之間的歐氏距離，計(jì)算式如下：

（2）

（3）

（4）

2基于信息熵的軌跡分段算法

信息熵常被用來作為一個(gè)系統(tǒng)信息含量的量化指標(biāo)，能衡量隨機(jī)事件的不確定性。隨機(jī)事件不確定性越高，信息熵值越大。設(shè)X是一個(gè)取有限值的離散隨機(jī)變量，其概率分布為? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（5）則隨機(jī)變量X的信息熵定義為? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（6）對(duì)于一條軌跡，當(dāng)且僅當(dāng)軌跡中每個(gè)軌跡點(diǎn)的某一特征均不同時(shí)，該軌跡這一特征的信息熵值最大。軌跡中至少有一個(gè)位置總是使兩段子軌跡之間的差異最大，基于此，可對(duì)軌跡進(jìn)行基于航向和速度特征的分段。進(jìn)行基于信息熵的軌跡分段前需先利用k均值聚類算法獲得軌跡的航向和速度區(qū)間，然后根據(jù)航向和速度區(qū)間確定軌跡的航向標(biāo)簽和速度標(biāo)簽。軌跡的航向信息熵En，course（T）計(jì)算式如下：? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （7）

（8）式中：Li，course為根據(jù)航向區(qū)間劃分得到的航向標(biāo)簽;Lcourse為航向標(biāo)簽總數(shù);N（Li，course）為Lcourse中某一相等標(biāo)簽出現(xiàn)的總次數(shù);ci表示各類航向標(biāo)簽在Lcourse中出現(xiàn)的頻率。速度信息熵En，speed（T）計(jì)算式如下：（9）

（10）式中：Li，speed為根據(jù)速度區(qū)間劃分得到的速度標(biāo)簽;Lspeed為速度標(biāo)簽總數(shù);N（Li，speed）為Lspeed中某一相等標(biāo)簽出現(xiàn)的總次數(shù);si表示各類速度標(biāo)簽在Lspeed中出現(xiàn)的頻率。

將軌跡T1，n-1在第i（1≤i≤n-1）個(gè)軌跡點(diǎn)處進(jìn)行分段，分成兩段子軌跡T1，i和Ti+1，n-1，根據(jù)式（11）依次計(jì)算在不同的軌跡點(diǎn)處分段的信息熵En，split（T1，n-1）（以基于航向信息熵的分段為例），選擇En，split（T1，n-1）值最小處為最終分段的位置。En，split（T1，n-1）=N1NEn，course（T1，i）+N2NEn，course（Ti+1，n-1）（11）式中：N1、N2和N分別代表T1，i、Ti+1，n-1和T1，n-1的軌跡點(diǎn)數(shù)。

基于信息熵的軌跡分段偽代碼如下：

輸入：k1，k2，T={p1，p2，…，pn}，En，threshold

輸出：分段后的軌跡Taftersplit

/*第一階段，從原始軌跡中獲取軌跡的航向和速度信息*/F6AB678E-6402-4886-AC74-C9922E3EE7A6

1. for each point in T do

2. courselist.append（p[3]）/*獲取航向信息courselist*/

3.speedlist.append（p[4]）/*獲取速度信息speedlist*/

4. end for

/*第二階段，基于k均值聚類的航向和速度區(qū)間獲取*/

5. c←kmeans（k1，courselist）/*k均值函數(shù)將航向聚成k1類，得到k1個(gè)中心點(diǎn)*/

6. courseinterval←c.sort（）/*對(duì)k1個(gè)航向中心點(diǎn)升序排列，得到航向區(qū)間courseinterval*/

7. s←kmeans（k2，speedlist）/*k均值函數(shù)將速度聚成k2類，得到k2個(gè)中心點(diǎn)*/

8. speedinterval←s.sort（）/*對(duì)k2個(gè)速度中心點(diǎn)升序排列，得到速度區(qū)間speedinterval*/

/*第三階段，對(duì)軌跡進(jìn)行考慮航向的劃分*/

9. Lcourse←courseinterval（courselist）/*根據(jù)航向區(qū)間，得到航向標(biāo)簽Lcourse*/

10. entropycourse←En，course/*計(jì)算航向信息熵entropycourse*/

11. if entropycourse≥En，threshold then

12. find min（En，split（T））/*找到最小En，split，在該點(diǎn)處進(jìn)行分段*/

13. Tcourse1←T1，i/*該點(diǎn)之前的點(diǎn)組成一條軌跡段Tspeed1*/

14. Tcourse2←Ti+1，n-1/*該點(diǎn)之后的點(diǎn)組成一條軌跡段Tcourse2*/

15. else

16. Tcourse1←T/*該軌跡無須分段*/

17. Tcourse3←Tcourse1 1，i/*對(duì)Tcourse1和Tcourse2繼續(xù)上述分段操作，得到新子軌跡Tcourse3和Tcourse4*/

18. Tcourse4←Tcourse1 i+1，n-1

19. Taftercoursesplit←{Tcourse1，Tcourse2，…，Tcoursem}/*Taftercoursesplit為經(jīng)過航向信息熵分段的子軌跡*/

/*第四階段，對(duì)軌跡進(jìn)行考慮速度的劃分*/

20. for each trajectory T′ in Taftercoursesplit do

21. Lspeed←speedinterval（speedlist）/*根據(jù)速度區(qū)間，得到速度標(biāo)簽Lspeed*/

22. entropyspeed←En，speed（Lspeed）/*計(jì)算速度信息熵entropyspeed*/

23. if entropyspeed≥En，threshold then

24. find min（En，split（T′））/*找到最小En，split，在該點(diǎn)處進(jìn)行分段*/

25. Tspeed1←T′1，i/*該點(diǎn)之前的點(diǎn)組成一條軌跡段Tspeed1*/

26. Tspeed2←T′i+1，n-1/*該點(diǎn)之后的點(diǎn)組成一條軌跡段Tspeed2*/

27. else

28. Tspeed1←T′/*該軌跡無須分段*/

29. Tspeed3←Tspeed1 1，i/*對(duì)Tspeed1和Tspeed2繼續(xù)上述分段操作，得到新的子軌跡Tspeed3和Tspeed4*/

30. Tspeed4←Tspeed1 i+1，n-1

31. Taftersplit←{Tspeed1，Tspeed2，…，Tspeedn}

32. end for

33. end

在利用k均值聚類算法對(duì)各軌跡點(diǎn)的航向和速度進(jìn)行聚類時(shí)，需要確定k值，即確定得到幾個(gè)航向或速度區(qū)間。為確保分段前后TDTR算法壓縮性能對(duì)比的合理性，本文將軌跡分段數(shù)控制在10以內(nèi)。將航向聚類數(shù)k1分別取1、2、3與速度聚類數(shù)k2分別取1、2、3的聚類結(jié)果進(jìn)行兩兩組合，選取將軌跡分段數(shù)控制在10以內(nèi)且分段數(shù)最多的k1、k2值?；谛畔㈧氐姆侄螣o須確定航向閾值、速度閾值或者時(shí)間閾值，只需一個(gè)信息熵閾值En，threshold，閾值越小，分段越精細(xì)。比如，閾值設(shè)為0時(shí)，信息熵分段算法可以將包含n個(gè)軌跡點(diǎn)的軌跡分成n-1段（即每兩個(gè)相鄰軌跡點(diǎn)之間的軌跡為一條子軌跡）。3實(shí)驗(yàn)和結(jié)果

3.1實(shí)驗(yàn)數(shù)據(jù)來源

實(shí)驗(yàn)數(shù)據(jù)來自20170310至20170311老鐵山水域的部分船舶軌跡。船舶軌跡及船舶速度變化情況（顏色越深對(duì)應(yīng)速度越大，顏色越淺對(duì)應(yīng)速度越?。┮妶D2。

3.2軌跡分段效果展示

本文設(shè)置En，threshold=0.3。為證明分段算法的合理性，可視化呈現(xiàn)了3條代表性船舶軌跡的分段結(jié)果，見表1。由表1可以看出：軌跡a的船舶航向幾乎沒有變化，基于航向信息熵的處理沒有對(duì)軌跡a分段，基于速度信息熵的處理把軌跡a分為2段，分段處的船舶速度變化較明顯。軌跡b比較曲折，基于航向信息熵的處理將其在明顯彎曲處分成4段子軌跡。由于軌跡b上船舶速度幾乎沒有變化，基于速度信息熵的分段處理沒有得到新的子軌跡。軌跡c上船舶航向和速度變化都比較大，基于航向信息熵的處理將其在航向變化較大處分成4段，后續(xù)基于速度信息熵進(jìn)一步將其分段，最終得到5段子軌跡。

利用基于信息熵的分段方法分別對(duì)軌跡進(jìn)行考慮航向信息和速度信息的分段，可得到軌跡的航向和速度特征點(diǎn)，即子軌跡段的起止點(diǎn)。文獻(xiàn)[16]提出了航向和速度特征點(diǎn)檢測(cè)方法，即若某點(diǎn)與相鄰點(diǎn)的距離差值、航速差值、航向差值均大于各自對(duì)應(yīng)的閾值，則稱該點(diǎn)為特征點(diǎn)。選取MMSI為636011643的船舶軌跡（見圖3）進(jìn)行對(duì)比實(shí)驗(yàn)，比較用文獻(xiàn)[16]方法與基于信息熵檢測(cè)方法檢測(cè)出的特征點(diǎn)，結(jié)果見圖4。文獻(xiàn)[16]將航向閾值和速度閾值分別設(shè)為5°和5 kn，但該閾值并不適用于MMSI為636011643的船舶軌跡，本文依據(jù)該軌跡情況重新設(shè)定閾值。基于航向信息熵對(duì)該軌跡進(jìn)行分段，可以看到5個(gè)航向特征點(diǎn)位于明顯彎曲的位置，如圖4a所示。圖4b和4c為用文獻(xiàn)[16]的方法在設(shè)置不同航向閾值時(shí)得到的結(jié)果。由圖4b可以看出，用該方法可以檢測(cè)到若干航向特征點(diǎn)，但檢測(cè)出的特征點(diǎn)缺乏代表性。由圖4c可以看出，在航向閾值為2°時(shí)僅能檢測(cè)出該軌跡的一個(gè)航向特征點(diǎn)，可表1代表性軌跡分段結(jié)果呈現(xiàn)軌跡原始軌跡速度變化情況根據(jù)航向分段后的軌跡根據(jù)速度分段后的軌跡abcF6AB678E-6402-4886-AC74-C9922E3EE7A6

見檢測(cè)結(jié)果易受航向閾值影響。用基于速度信息熵的方法檢測(cè)出4個(gè)速度特征點(diǎn)（見圖4d），結(jié)合圖3可看出檢測(cè)結(jié)果的合理性，即速度明顯變化處被認(rèn)定為速度特征點(diǎn)。而用文獻(xiàn)[16]的方法檢測(cè)得到的結(jié)果差別大，在速度閾值為0.1 kn時(shí)僅能檢測(cè)出一個(gè)速度特征點(diǎn)，在速度閾值為0.2 kn時(shí)未能檢測(cè)出速度特征點(diǎn)。這是因?yàn)樵摯乃俣茸兓徛湎噜徿壽E點(diǎn)之間速度變化均沒有超過0.2 kn。

綜上可知，相比于其他需要人為確定航向或速度閾值的特征點(diǎn)檢測(cè)方法，基于信息熵的檢測(cè)方法可以自適應(yīng)地對(duì)軌跡特征點(diǎn)進(jìn)行檢測(cè)，且效果不受航向或速度變化幅度的影響，檢測(cè)出的特征點(diǎn)更具有代表性。

3.3分段壓縮和不分段壓縮對(duì)比實(shí)驗(yàn)

利用TDTR算法分別對(duì)未分段軌跡和分段后軌跡進(jìn)行壓縮，壓縮閾值根據(jù)文獻(xiàn)[18]提出的自適應(yīng)分?jǐn)?shù)來確定。該分?jǐn)?shù)表示每一次軌跡壓縮后誤差比分與軌跡點(diǎn)數(shù)比分之和，分?jǐn)?shù)越低表示軌跡壓縮效果越好。分段前后軌跡壓縮性能的對(duì)比結(jié)果見表2。由表2可知，在壓縮率略微降低的情況下，無論是在壓縮耗時(shí)還是在各種誤差方面，對(duì)分段后軌跡進(jìn)行壓縮的結(jié)果都大大優(yōu)于對(duì)未分段軌跡進(jìn)行壓縮的結(jié)果。

根據(jù)軌跡點(diǎn)數(shù)將軌跡分成短軌跡、中等軌跡和長軌跡三類（見表3），其中軌跡長度指一條軌跡所有相鄰軌跡點(diǎn)之間距離的累加值。計(jì)算各類軌跡的壓縮誤差和壓縮率的平均值，結(jié)果見圖5。從航向誤差、速度誤差和SED誤差來看，隨著軌跡數(shù)據(jù)量的增大，無論是未分段軌跡還是分段后軌跡的壓縮誤差都逐漸增加。相比較而言，分段后軌跡的各種壓縮誤差增幅很小且一直明顯低于未分段軌跡的壓縮誤差，尤其是SED誤差。從壓縮率來看，雖然未分段軌跡的壓縮率一直高于分段后軌跡的壓縮率，但未分段軌跡的壓縮率隨著數(shù)據(jù)量的增大沒有明顯變化，而分段后軌跡的壓縮率隨著數(shù)據(jù)量的增加卻在緩慢增加，逐漸逼近未分段軌跡的壓縮率。為證實(shí)這一點(diǎn)，對(duì)軌跡點(diǎn)數(shù)超過2 000的其他水域的長軌跡進(jìn)行進(jìn)一步實(shí)驗(yàn)，結(jié)果見圖6。隨著軌跡點(diǎn)數(shù)的增加，分段后軌跡與未分段軌跡的壓縮率差距逐漸減小。因此，無論是從壓縮誤差還是從壓縮率都可以看出，分段后軌跡壓縮性能的優(yōu)越性隨著軌跡長度的增加越來越明顯。

由于AIS發(fā)送數(shù)據(jù)的頻率隨船舶狀態(tài)的變化而變化，軌跡點(diǎn)數(shù)多并不一定代表軌跡長。由表2也可知，部分中等軌跡的長度小于短軌跡，部分長軌跡的長度小于中等軌跡。因此，本文利用軌跡長度損失值對(duì)分段后軌跡和未分段軌跡壓縮性能進(jìn)行對(duì)比。軌跡長度損失值指原始軌跡與壓縮后軌跡的實(shí)際長度差值。將軌跡按實(shí)際長度分為不同數(shù)據(jù)集并計(jì)算軌跡長度損失值，統(tǒng)計(jì)結(jié)果見圖7。由圖7可以看出：分段后軌跡的長度損失值一直小于未分段軌跡的長度損失值。整體上看，軌跡長度損失值隨著軌跡長度的增加而增加，但20～40 n mile的軌跡長度損失值異常大。這是因?yàn)檫@一部分軌跡的復(fù)雜度較大，如圖7b所示。軌跡復(fù)雜度為每個(gè)軌跡點(diǎn)拐角余弦的平均值，主要反映軌跡的彎曲程度，其值越大說明軌跡越曲折。

運(yùn)行時(shí)間是衡量軌跡壓縮效果的另一重要指標(biāo)，圖8為軌跡分段前后壓縮耗時(shí)。由圖8可知：軌跡分段前后壓縮耗時(shí)都隨著軌跡點(diǎn)數(shù)量的增加而增加;分段后軌跡壓縮耗時(shí)明顯低于未分段軌跡壓縮耗時(shí)，且差距隨著軌跡點(diǎn)數(shù)量的增加而增加，這說明

對(duì)長軌跡進(jìn)行分段預(yù)處理是必要的。圖9展示了自適應(yīng)確定TDTR壓縮閾值的計(jì)算時(shí)間。由圖9可以看出：對(duì)軌跡分段后再壓縮的計(jì)算效率較高;對(duì)未分段軌跡的自適應(yīng)閾值計(jì)算時(shí)間隨軌跡點(diǎn)數(shù)量的增加顯著增加，而對(duì)分段后軌跡的閾值計(jì)算時(shí)間增加量不大，這是因?yàn)樽赃m應(yīng)閾值的計(jì)算需要迭代到每一個(gè)軌跡點(diǎn)，軌跡點(diǎn)越多，計(jì)算閾值的耗時(shí)必然越久。

4結(jié)論

針對(duì)船舶軌跡壓縮算法忽略操縱信息和分段算法確定閾值難的問題，引入信息熵理論，考慮速度和航向，提出一種基于信息熵的船舶軌跡自適應(yīng)分段壓縮算法。采用老鐵山水域的部分船舶軌跡數(shù)據(jù)進(jìn)行對(duì)比實(shí)驗(yàn)，結(jié)果表明，該算法可以對(duì)船舶軌跡進(jìn)行合理的分段。相比于未分段軌跡壓縮，在壓縮率略微降低的情況下，對(duì)軌跡分段后再壓縮可大幅降低壓縮誤差和運(yùn)行時(shí)間，且隨著軌跡數(shù)據(jù)量的增加性能更好。在處理規(guī)模巨大的軌跡時(shí)，船舶軌跡的自適應(yīng)分段壓縮算法表現(xiàn)出更好的性能，這對(duì)海上交通態(tài)勢(shì)感知和船舶交通信息的挖掘具有重要價(jià)值。

參考文獻(xiàn)：

[1]WU X B， WU L， XU Y J， et al. Vessel trajectory partitioning based on hierarchical fusion of position data[C]//Proceeding of IEEE 18th International Conference on Information Fusion. IEEE， 2015： 12301237.

[2]SHENG P， YIN J B. Extracting shipping route patterns by trajectory clustering model based on automatic identification system data[J]. Sustainability， 2018， 10（7）： 2327. DOI： 10.3390/su10072327.

[3]高邈， 史國友， 李偉峰. 改進(jìn)的Sliding Window在線船舶AIS軌跡數(shù)據(jù)壓縮算法[J]. 交通運(yùn)輸工程學(xué)報(bào)， 2018， 18（3）： 218227. DOI： 10.19818/j.cnki.16711637.2018.03.022.

[4]SUN S， CHEN Y， PIAO Z J， et al. Vessel AIS trajectory online compression based on scanpickmove algorithm added sliding window[J]. IEEE Access， 2020， 8： 109350109359. DOI： 10.1109/ACCESS.2020.3001934.F6AB678E-6402-4886-AC74-C9922E3EE7A6

[5]ZHANG Y Q， SHI G Y， LI S， et al. Vessel trajectory online multidimensional simplification algorithm[J]. Journal of Navigation， 2019， 73（2）： 122. DOI： 10.1017/S037346331900064X.

[6]QI L， JI Y Y. Ship trajectory data compression algorithms for automatic identification system： comparison and analysis[J]. Journal of Water Resources and Ocean Science， 2020， 9（2）： 4247. DOI： 10.11648/j.wros.20200902.11.

[7]MERATNIA N， DE BY R A. Spatiotemporal compression techniques for moving point objects[C]//International Conference on Advances in Database Technology. DBLP， 2004： 765782. DOI： 10.1007/9783540247418_44.

[8]QI L， ZHENG Z Y. Vessel trajectory data compression based on course alteration recognition[J]. International Journal of Simulation： Systems， Science & Technology， 2016： 18. DOI： 10.5013/IJSSST.a.17.01.05.

[9]ZHAO L B， SHI G Y. A method for simplifying ship trajectory based on improved DouglasPeucker algorithm[J]. Ocean Engineering， 2018， 166： 3746. DOI： 10.1016/j.oceaneng.2018.08.005.

[10]ZHU F X， MIAO L M， LIU W. Research on vessel trajectory multidimensional compression algorithm based on DouglasPeucker theory[J]. Applied Mechanics and Materials， 2014， 694： 5962. DOI： 10.4028/www.scientific.net/AMM.694.59.

[11]YUAN G， XIA S X， ZHANG L， et al. An efficient trajectoryclustering algorithm based on an index tree[J]. Transactions of the Institute of Measurement & Control， 2012， 34（7）： 850861. DOI： 10.1177/0142331211423284.

[12]何愛林， 周德超， 陳萍， 等. 基于軌跡聚類的運(yùn)動(dòng)趨勢(shì)分析[J]. 海軍工程大學(xué)學(xué)報(bào)， 2017， 29（5）： 103107. DOI： 10.7495/j.issn.10093486.2017.05.022.

[13]韓陳壽， 夏士雄， 張磊， 等. 基于速度約束的分段軌跡聚類算法[J]. 計(jì)算機(jī)工程， 2011， 37（7）： 219221. DOI： 10.3969/j.issn.10003428.2011.07.074.

[14]金佳龍， 周偉， 姜佰辰. 基于行為模式的海上目標(biāo)軌跡分段算法[J]. 信號(hào)處理， 2020， 36（12）： 115. DOI： 10.16798/j.issn.10030530.2020.12.014.

[15]盛凱， 劉忠， 周德超， 等. 基于運(yùn)動(dòng)模式的船舶軌跡分段壓縮算法[J]. 海軍工程大學(xué)學(xué)報(bào)， 2018， 30（6）： 5057. DOI： 10.7495/j.issn.10093486.2018.06.009.

[16]宋鑫， 朱宗良， 高銀萍， 等. 動(dòng)態(tài)閾值結(jié)合全局優(yōu)化的船舶AIS軌跡在線壓縮算法[J]. 計(jì)算機(jī)科學(xué)， 2019， 46（7）： 333338. DOI： 10.11896/j.issn.1002137X2019.07.051.

[17]梁明， 陳文靜， 段平， 等. 軌跡壓縮的典型方法評(píng)價(jià)[J]. 測(cè)繪通報(bào)， 2019（4）： 6064. DOI： 10.13474/j.cnki.112246.2019.0113.

[18]LIN C Y， HUNG C C， LEI P R. A velocitypreserving trajectory simplification approach[C]//2016 Conference on Technologies and Applications of Artificial Intelligence. IEEE， 2016： 5865. DOI： 10.1109/TAAI.2016.7880172.

（編輯賈裙平）

收稿日期： 20210519修回日期： 20210917

基金項(xiàng)目： 國家自然科學(xué)基金（41861144014）;中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金（3132021154）

作者簡介： 楊家軒（1981—），男，山東濟(jì)寧人，副教授，博士，研究方向?yàn)楹Ｉ辖煌üこ?、航海安全保障、AIS數(shù)據(jù)挖掘、水面無人航行器避碰等，（Email）yangjiaxuan@dlmu.edu.cnF6AB678E-6402-4886-AC74-C9922E3EE7A6