基于改進Douglas-Peucker 的自適應閾值漁船軌跡數據壓縮方法*

段浩然 劉明劍 朱云鶴 張思佳

（1.大連海洋大學信息工程學院 大連 116023）（2.設施漁業教育部重點實驗室 大連 116023）

1 引言

據農業部2021 年末統計，我國現有漁船52.08萬艘，從事漁業的人口為1634.24萬人，全國漁業經濟總生產值約為29689.73億元，其中海洋漁業捕撈經濟生產值占比較重，約為2303.72 億元［1］。我國是漁業大國，漁業捕撈為沿海地區的發展做出了重要貢獻。為了保證漁船捕撈作業的安全性和合法性，保護海洋生態平衡實現漁業的可持續發展，有必要對漁船行為進行監督與管理［2］。

船舶自動識別系統（Automatic Identification System，AIS）是強制在漁船、貨船和客船等船舶上安裝的助航儀器［3］，能自主地、不斷地向外播發和接收船舶的呼號、船名等靜態信息和航向、航速等動態信息，目的在于識別和跟蹤船舶行駛軌跡［4］。因此通過對漁船的AIS 數據進行分析是監管漁船行為、探明漁船的捕撈方式、作業狀態以及捕魚熱點等深層次信息的有效方式之一［5～7］。漁船出海作業時間較長，橫跨區域廣［8］，長時間長距離的航行產生了大量的AIS 數據［9］，同時也會加劇數據存儲分析的任務量和系統的負荷［10］，因此需要有效的軌跡壓縮算法處理海量的AIS數據。

軌跡壓縮算法是在減少軌跡點的同時設定壓縮條件，保障軌跡特征信息損失最少。對相同軌跡設置不同的壓縮條件，壓縮后的軌跡會存在較大的差異，因此需要對軌跡壓縮算法中壓縮閾值進行合理設置。

Douglas［11］等提出Douglas-Peucker 算法，根據設置固定的壓縮閾值對軌跡進行簡化，但不適用于所有類型的軌跡。大部分學者在該算法基礎上進行改進，張樹凱等［12］基于DP 算法為多個實驗選擇了不同的閾值，該方法以航行船舶的船舶域為閾值，即船舶長度的0.8 倍。趙梁濱等［13］將合適閾值設置為船舶長度的0.5 倍～1 倍。島嶼附近海域的適當比例通常為船舶長度的0.1 倍～10 倍。高淼等［14］將距離閾值設定為［30，300］m，將回旋和漂移的角度閾值設定為［1°，9°］。此外，給出了高、中、低水平的距離閾值，分別為船舶長度的43%、38%和33%。魏趙坤等［15］將滑動窗口算法、船舶導航角度偏差、位置偏差和AIS 的時空特征結合起來，距離閾值分別為船寬的0.731倍和1.274倍，航行角度偏差閾值是3.8°和5°。此外劉敬賢等［16］還提出了一種DP 算法和滑動窗口算法結合的軌跡簡化算法。將DP算法的閾值設置為船舶長度的0.8倍，滑動窗口算法的閾值系數設置為1.6。

綜上所述，軌跡壓縮閾值設置主要有兩種方式。1）經驗閾值；2）船舶長度或寬度的倍數。然而，經驗閾值容易受到水域的限制，難于確定測試范圍以外水域的閾值。對于基于船舶長度或寬度設置的閾值，在大量異常靜態信息的影響下會有誤差。為了克服這些算法在閾值設置方面的不足，迫切需要一種自適應軌跡壓縮算法，其閾值設置不再根據經驗或船舶靜態信息進行設定。

本研究針對上述問題，在DP 算法的基礎上提出了ADP 自適應閾值壓縮方法。首先，選擇航向狀態屬性篩選軌跡點；其次，擬合所有子軌跡段的最大臨界閾值集的曲線；最后，根據曲線中閾值變化不大且方向在垂直和水平上變化的特點，利用相鄰點間的角度變化率設置自適應閾值。

2 相關定義

2.1 漁船AIS軌跡數據特點

由經度、緯度、時間等信息組成的軌跡點集合，被稱為船舶的AIS軌跡。

相比于定班定線航行的商船和客船，漁船的軌跡數據有以下幾種特點：

1）部分AIS 數據不準確。如表1 所示，船舶運動狀態對數據的采集會產生一定影響，運動狀態不同其上傳數據的時間間隔也有所不同，將導致數據在傳送和接收的過程中缺失［17］，部分漁船由人工輸入狀態信息，存在操作失誤的情況。

表1 AIS數據上傳時間間隔

2）特征點數量多且密集。漁船在作業區內來回低速拖拽捕撈，頻繁的轉彎和掉頭，這將導致產生了大量且密集的軌跡數據。圖1［18］為船訊網中一漁船前往作業區捕撈的航行特征。

圖1 漁船捕撈時航行特征

3）軌跡長且曲折。由于海面的環境復雜多變以及不固定的航線，漁船在捕撈作業后的軌跡點更隨機。

2.2 相關定義與公式

定義1軌跡點：船舶的位置點用p表示，是一個三維的的軌跡數據，屬性分別為經度、緯度、時間，表達式為

定義2原始軌跡：一連串隨著時間前后順序的原始軌跡點組成的集合，用T表示，其表達式為

定義3壓縮軌跡：對原始軌跡進行壓縮處理，篩選軌跡點后，按照時間前后順序組成的新軌跡集合，用Tc表示，即

定義4軌跡段：在原始軌跡T或簡化軌跡Tc中，將pi和pj連接組成的線段，用表示。

定義5特征點：若某點處的航向角差值和距離差值大于對應的航向角閾值和距離閾值，則稱該點為特征點。

定義6壓縮率：指丟棄的軌跡點數量與原始軌跡點數量的比率。單個軌跡（表示為SCR）的壓縮率為

式中n是軌跡點的總數，m是丟棄軌跡點的數量。

定義7點的臨界閾值ξ：如果距離閾值僅使軌跡點a在壓縮后成為特征點，則該閾值稱為點a的臨界閾值，記錄為ξ。

定義8經緯度坐標轉換：將地理坐標轉換為墨卡托投影中的坐標來提升精度。假設未轉換軌跡點的經緯度坐標為(φ，ω)，轉換為墨卡托投影的坐標為(x，y)，則轉換公式如下：

式中，r0為基準緯度圈的半徑；a為地球的長軸半徑。

式中，e為地球的第一偏心率；q為等距緯度。

在式（3）中，Tc為同步歐氏距離（Squared Euclid Distance，SED）。表示為原始軌跡中的點在壓縮軌跡中按照時間比例對應的歐氏距離。假設原始軌跡中的某一點為p=(xi，yi，ti)，壓縮軌跡中的某一點為則p'的坐標計算公式為

所有軌跡的平均SED 表示為AASED（All Average Squared Euclid Distance），其中N為船舶軌跡總數：

定義9角度變化率r：指擬合曲線中兩個相鄰點在切線方向上的變化率。

3 相關算法及算法設計

3.1 DP算法

DP 算法的基本原理是保留原始軌跡的首尾兩點并相連接做基線，依次計算該軌跡上所有點到基線的歐式距離，并找出距離最大的軌跡點，將其距離值與設定的距離閾值進行比較，小于距離閾值，則舍棄這條直線上的點，大于距離閾值，則保留該點。將原始軌跡從該點處分成兩段，得到兩條子軌跡段并對子軌跡段重復上述步驟，迭代計算，直到所有軌跡點到對應基線的距離都小于距離閾值或軌跡內只剩余首尾兩軌跡點。

如圖2 所示，設置距離閾值ε，原始軌跡為。DP 算法先將起點和終點連接得到軌跡段并代替原始軌跡，分別計算所有軌跡點p1，p2，p3，p4，p5，p6到的歐氏距離，p3點距離最遠，且dmax(P3) ＞ε，保留p3點，再次遞歸處理軌跡段，直到對應軌跡段的最大歐式距離小于給定的距離閾值ε，最終得出簡化軌跡為Tc={p0，p3，，p5，p7} 。

圖2 DP算法

3.2 ADP自適應閾值壓縮方法

本研究在DP 算法基礎上提出的ADP 自適應閾值壓縮方法是為了能自適應進行閾值壓縮。解決以往方法中閾值設置基于經驗，導致應用受限，以及閾值設置基于船舶靜態信息，由于信息不正確而導致壓縮效果差甚至不成功的問題。

漁船軌跡數據中屬性較多，但漁船在作業時會在某區域內低速行駛并存在多次轉向、掉頭的情況。故本研究在算法中使用航向狀態屬性，利用相鄰軌跡點之間的航向變化狀態信息過濾非轉折點。在初步保留轉折點之后，對小于距離閾值的軌跡點進一步壓縮提取特征點，并同時計算所有子軌道段的最大臨界閾值來檢查閾值的臨界點。最終達到對軌跡設置自適應閾值的目的。

3.2.1 非轉折軌跡點過濾

漁船在捕撈時會在作業區域內低速拖拽并多次往返。針對漁船在作業時航向多變的特點，提出一種軌跡點過濾方法，通過軌跡點的航向變化過濾非轉折點，篩選軌跡點。將航向變化小于角度閾值的點刪除，大于角度閾值的點反應了漁船真實的運動情況，需要進行保留。

采用非軌跡點過濾方法，得出過濾率和角度閾值Δθ之間的關系，結果如表2 所示。當Δθ＞10°時，過濾率的變化不顯著。本文將角度閾值Δθ設為10°。

表2 過濾率與Δθ 的關系表

3.2.2 ADP算法基本步驟

1）輸入原始軌跡點集T，航向角度閾值Δθ、距離閾值ε，通過濾除非轉折點的方法，對航向變化差小于Δθ的點過濾，得到轉折點集。

2）保留轉折點集中的首軌跡點p0和末軌跡點p13并存儲在集合Tc中，連接兩點得到軌跡段，計算所有點到軌跡段的距離，得到距離最大值點p4以及ξ1，如果ξ1大于距離閾值，則p4點為特征點，保留該點存儲在集合Tc中，將ξ1存儲在集合Set(ξ)中，并以該點為界分為兩個子軌跡段分是ST1，1和ST1，2。否則舍去這條軌跡上的點。

3）分別對兩個子軌跡段ST1，1和ST1，2取最大距離值點p3和p9。比較兩點到子軌跡段的距離，優先處理距離最大的子軌跡段。p9點到子軌跡段ST1，2的距離大于p3點到子軌跡段ST1，1的距離。如果p9點為特征點，則將p9點存儲在集合Tc中，將該點到基線的距離ξ1，2存儲在集合Set(ξ)中并以該點為界分為兩個子軌跡段分別是ST2，1和ST2，2。

4）重復上述步驟，直到處理完所有子軌跡段。輸出壓縮軌跡集Tc以及所有子軌跡段的臨界閾值集Set(ξ)。ADP算法如圖3。

圖3 ADP算法

為了能更直觀地得出臨界閾值之間的變化規律，對臨界閾值集Set(ξ)進行擬合。

圖4 子軌跡段臨界閾值的分布（截取一部分）

函數擬合后得出a=321.32，b=0.03，c=1.22，d=0.11。將參數代入并畫出曲線變化圖，如圖5 所示。

圖5 子軌跡段臨界閾值擬合結果

在數據庫中隨機選取兩條軌跡T0和T17，做出擬合曲線并和圖5 中的擬合曲線進行對比，如圖6所示。

圖6 多條軌跡的臨界閾值擬合結果

圖6 中三條擬合曲線的擬合優度R2計算公式如下：

式中，yi為真值，平均值為˙，擬合值為。三條曲線擬合優度分別為R2y=0.53，R2T0=0.70，R2T17=0.91。

如圖6所示，區域3中的線是垂直的，雖然臨界閾值變化迅速，但其方向變化不大；4 區的線是水平的，臨界閾值變化不大，方向也幾乎不變。從垂直方向到水平方向的變化主要發生在1 區。兩個方向之間的轉折點更能反映出曲線的特征，因此通過計算曲線中相鄰點之間的最大角度變化率來設置最優閾值。

雙曲線函數的導數計算公式如下：

第pi點和第pi+1點之間的角度變化率為

由上述公式可得，y曲線中x=3 時角度變化率最大，即y=55.6，最優閾值應設為55.6m，T0曲線中x=124 時角度變化率最大，即y=552.8，最優閾值為552.8m。T17曲線中x=25 時角度變化率最大，即y=33.3，最優閾值應設為33.3m。

4 驗證試驗

4.1 試驗設計

為驗證本文提出的自適應閾值漁船軌跡數據壓縮方法的有效性，分別對單條漁船軌跡進行不同算法的壓縮對比試驗。算法采用Python語言編寫，版本為3.7，IDE 采用PyCharm。軌跡數據以及試驗數據集來源于“大連望海大數據信息有限公司”，漁船軌跡數據以.txt的文件格式存儲。

4.2 試驗結果

圖7 中三種算法對漁船軌跡進行壓縮處理后，原始軌跡點數目都較大幅度的減少，DP 算法雖能夠保留軌跡的路徑形狀，但大量的特征信息被壓縮，SW算法在軌跡點密集的區域出現失真，ADP算法壓縮后的軌跡形態對于保留漁船的特征軌跡點和軌跡的形狀特征有很大的幫助。

圖7 漁船軌跡壓縮前后效果對比圖

算法對比結果如表3 所示，3 種算法的壓縮率平均為99.5%（SW 算法），99.4%（DP 算法），98%（ADP 算法）。ADP 算法在保留了更多特征點的同時使得壓縮后的軌跡與原始軌跡更相似。

表3 三種壓縮算法試驗結果

5 結語

針對現有軌跡壓縮算法在設置距離閾值時存在采用基于經驗設置最佳閾值的問題，在DP 算法的基礎上提出了ADP 算法。實驗表明，ADP 算法能夠自適應設置閾值，不僅獲得了較高的壓縮效率，同時在保留軌跡特征的方面也有較大的優勢，為漁船的行為分析提供更加精確的壓縮軌跡。

然而，也有不足之處。沒有考慮到船舶的航向和速度所帶來的影響。因此在以后的工作中會著重考慮上述兩種因素來改進壓縮算法。