基于Douglas-Peucker和Quick Bundles算法的水上交通模式識別

陳信強，徐祥龍，彭靜，孫洋，王梓創，閻瑩

(1.上海海事大學 a.物流科學與工程學院; b.商船學院，上海 201306；2.長安大學運輸工程學院，西安 710064)

0 引 言

隨著經濟全球化的進一步發展，航運業已經成為經濟和社會發展的重要載體。十九大報告提出“加快建設海洋強國”，進一步促進了我國水上交通的發展。船舶交通流量的快速增長導致海上通航環境日趨復雜，給水上交通監管部門和船上工作人員帶來了全新挑戰。交通模式識別技術用來從移動對象的空間軌跡信息中挖掘并提取交通參與者主要的活動規律，是交通需求分析、交通規劃和交通管理的基礎。與道路交通和軌道交通等不同的是，水上交通沒有明確的物理航道邊界。因此，利用船舶航跡數據高效、準確地挖掘水上交通模式，幫助交管部門研判水上交通態勢，及時制定交通管控措施，也成為海事領域的一個研究熱點。

ZHANG等基于船舶自動識別系統(automatic identification system，AIS)數據設計了一種狹水域通航條件下的船舶軌跡時空分析方法，用于分析交通需求和交通狀態等的時空變化規律。李爽等提出一種結合滑動窗口算法和改進譜聚類算法的航路識別框架，實現對船舶航路的辨識。王震等、萬輝等和ZHAO等采用道格拉斯-普克(Douglas-Peucker，DP)壓縮算法對AIS數據進行稀疏處理，并基于船舶航跡和交通流密度等因素對船舶行為特征進行分析。王壯等基于船端數據和氣象數據建立通航環境數據庫，并通過改進的均值聚類算法實現對船舶通航環境的智能識別。WANG等提出一種基于Hausdorff距離和具有噪聲的基于密度的聚類方法，結合船舶形狀特征對船舶航跡進行自適應聚類，并引入綜合聚類性能指標對聚類結果進行優化。GAO等首先利用AIS數據對船舶航跡進行分段并編碼，然后采用分布鄰域嵌入算法對編碼數據進行降維，最后基于譜聚類算法實現船舶行為模式識別。

部分學者基于水上交通模式識別的思路對船舶異常行為檢測和航跡預測等問題展開了相關研究。ZHEN等首先根據AIS數據的空間和方向特征設計了一種船舶航跡的相似性度量方法，然后利用層次和中心點聚類方法對船舶交通模式進行建模和學習，最后利用貝葉斯分類器對船舶行為進行分類和檢測。ARGUEDAS等基于歷史自報定位數據(如AIS數據)自動生成水上交通監控網絡，為海上交通的實時自動監控、異常檢測和交通態勢判斷奠定了基礎。XIAO等、ZHAO等、張春瑋等、周海等提出一種基于密度的噪聲應用程序空間聚類算法以獲取船舶航行模式，并進一步做了船舶運動行為分析、船舶異常檢測等。SHENG等提出一種無監督學習方法從AIS數據中挖掘船舶交通模式，并根據船舶航跡特征對不同的航路進行自動分類。

在上述研究中：當航跡樣本數據分布不均勻時，具有噪聲的基于密度的聚類方法對船舶航跡的聚類效果不理想；基于Hausdorff距離的方法雖然能夠對船舶航跡進行聚類，但時間復雜度較高；將船舶單次航跡分解為若干子軌跡后再聚類，不能充分挖掘船舶航跡變化規律。基于此，本文提出一種融合DP算法與快速捆綁包(Quick Bundles，QB)算法的船舶交通模式挖掘框架。該框架首先基于DP算法對AIS數據進行壓縮，以解決數據冗余和計算開銷問題；然后在QB算法中引入基于最小直接翻轉距離的聚類評價指標,以簡化不同船舶航跡相似性的計算過程，準確實現水上交通模式識別。

1 基于DP和QB算法的水上交通模式識別

1.1 航跡壓縮算法

AIS設備被廣泛安裝于各種航行船舶，AIS數據更新頻率與船舶航行速度成正比(航行速度快，則更新頻率高)。由于AIS數據更新速度快(近海在航船舶數據每隔2 s～10 min更新一次)，產生了海量的AIS數據，對水上交通態勢感知、船舶航跡預測等相關研究提出了新的挑戰。為此，引入軌跡壓縮算法剔除冗余數據，在保留船舶航跡數據特征的前提下，實現快速辨識船舶航跡的目的。

DP算法采用“以直代曲”的思想，保留關鍵航跡點，舍棄非關鍵航跡點，最終實現船舶航跡數據壓縮的目的。假設船舶某航次的航跡如圖1所示，用DP算法實現航跡壓縮的基本步驟如下：

連接該航次出發地、目的地兩點，標記為線段。

計算船舶航跡曲線上各點與直線的距離，從航跡點中選取出與直線的距離最遠的點，并將點與直線的距離記為。

比較距離與預先設定的壓縮閾值之間的大小關系。若距離小于等于壓縮閾值，則使用線段替代原始的航跡曲線(如圖1a所示)；若距離大于壓縮閾值，則以點為關鍵點，將航跡劃分為曲線和曲線兩段(如圖1b所示)，并分別對兩段曲線重復步驟1至步驟3。

a)距離d未超過壓縮閾值θ

整條航跡按照上述方法處理完畢后，依次連接航跡曲線上的各個關鍵點，得到原航跡曲線的壓縮航跡。

1.2 QB算法

Hausdorff距離函數是描述兩組點集之間相似度的一種度量方法，即Hausdorff距離的大小表征兩組點集之間的不匹配程度，故現有研究常采用該距離函數作為船舶航跡簇的聚類指標。假設有兩組點集={,,…,}和={,,…,}，則這兩組點集之間的Hausdorff距離定義為

(,)=max((,),(,))

(1)

(2)

(3)

Hausdorff距離函數作為航跡簇的聚類指標存在兩個主要缺點：(1)忽略了航跡間的順序性；(2)算法復雜度高。針對這兩個主要缺點，本文提出一種相對簡單的最小平均直接翻轉距離。對于最小平均直接翻轉距離所要求的不同船舶航跡應具有相同數量的樣本點，可通過線性插值的方法達到。

考慮到船舶航向因素，對于給定的船舶航跡點集和，其翻轉航跡點集分別記為={,-1,…,}和={,-1,…,}，則兩條船舶航跡的直接距離、翻轉距離和最小直接翻轉距離定義如下：

(4)

(,)=(,)=(,)

(5)

(,)=min((,),(,))

(6)

a)直接距離

基于上述對QB算法的介紹，現對船舶航跡聚類算法進行如下描述。在算法的任何一步，均有個簇。如果將一條船舶航跡放至第一簇，則此時=1。

計算船舶航跡(用矩陣表示)與當前所有簇的質心航跡(用矩陣表示)之間的最小直接翻轉距離。對不同船舶航跡數據進行重采樣操作，使得不同船舶航跡片段均具有相同數量的樣本點，以生成相同階數的聚類矩陣。質心航跡為當前簇中所有船舶航跡矩陣求和后的均值：

=∑/

(7)

式中：是經過重采樣后的包含個船舶位置(經緯度)信息的某條航跡數據構成的×2階的矩陣；為簇內船舶航跡數量。

若與當前所有簇的質心航跡之間的最小直接翻轉距離均大于聚類閾值，則創建一個新的簇，并將添加至新簇中；反之，則將添加至與其最小直接翻轉距離最小的簇中。

2 實例驗證與分析

為驗證本文提出方法的有效性，選取兩片水域作為研究對象：東經121°56′～122°12′、北緯30°30′～30°43′范圍內的洋山港水域;東經121°40′～122°21′、北緯29°38′～30°06′范圍內的舟山水域。對于洋山港水域，選取2019年11月212艘船的1 056條船舶航跡數據作為實驗數據源；對于舟山水域，選取2021年6月19—21日286艘船的852條船舶航跡數據作為實驗數據源。

由于原始AIS數據混合了不同船舶、不同航次的航跡信息，不能直接用于船舶航跡分析研究，所以需要根據水上移動通信業務標識碼(maritime mobile service identify，MMSI)、速度特征和時間間隔建立軌跡分割機制。首先對原始數據按照船舶的MMSI進行初步拆分，然后對同一艘船的不同航次數據進行二次拆分。具體來講，若同一艘船的相鄰兩個航跡點的時間戳間距大于5 h，則將這兩個航跡點信息視為同一艘船不同航次的航跡信息，并進行二次拆分。

由于船舶航速相對較低、AIS數據更新頻率較高，故原始數據中存在大量冗余數據。為減小計算開銷，需要通過提取船舶航跡關鍵點的方法來簡化船舶的航跡信息。為驗證不同算法的船舶航跡數據壓縮性能，首先分析DP算法和滑動窗口算法在不同壓縮閾值下的壓縮效果。以洋山港水域的船舶航跡數據為例，當壓縮閾值設置為4 m時，滑動窗口算法的壓縮率約為DP算法壓縮率的2/3(DP算法壓縮率為88.10%，滑動窗口算法的壓縮率為63.50%)，但是滑動窗口算法的壓縮誤差是DP算法的3倍。即在壓縮閾值相同的條件下，滑動窗口算法是以損失船舶航跡數據壓縮精度為代價提升數據壓縮率的。當壓縮閾值為8 m和12 m時，DP算法與滑動窗口算法的壓縮率和壓縮誤差呈現出類似的分布規律。基于此，認為DP算法對船舶航跡數據的壓縮效果優于滑動窗口算法。DP算法與滑動窗口算法對洋山港水域船舶航跡數據的壓縮性能對比見表1。

表1 不同壓縮閾值下DP算法與滑動窗口算法對洋山港水域船舶航跡數據的壓縮性能對比

為確定DP算法的最佳壓縮閾值，以0.5 m為步長，分別測試壓縮閾值分別為0，0.5 m,…,20 m時DP算法的壓縮效果，結果見圖3。當壓縮閾值增加至12 m時，壓縮率為71.4%，壓縮誤差達到1.3 m；隨著壓縮閾值的進一步增大，船舶航跡數據的壓縮率變化緩慢，但數據的壓縮誤差急劇增大。綜合考慮壓縮率和壓縮誤差等因素，本研究設置壓縮閾值為12 m。

圖3 不同壓縮閾值下DP算法的船舶航跡數據壓縮率和壓縮誤差

為進一步驗證壓縮閾值設置的合理性，從研究水域內各選取1條典型船舶航跡進行分析,分析結果如下：

(1)在洋山港水域內，MMSI為413427690的船的航跡壓縮效果見圖4。當壓縮閾值為8 m時，壓縮率為53%，壓縮誤差為0.91 m；當壓縮閾值為12 m時，壓縮率為44%，壓縮誤差為1.93 m。

a)壓縮前航跡

(2)在舟山水域內，MMSI為351372000的船的航跡壓縮效果見圖5。當壓縮閾值為8 m時，壓縮率為54%，壓縮誤差為0.97 m；當壓縮閾值為12 m時，壓縮率為43%，壓縮誤差為2.15 m。通過對比不同壓縮閾值下的實驗結果不難發現，當壓縮閾值為12 m時，不僅能夠有效地壓縮數據量，而且能夠保證良好的精度，同時顯著降低了算法的時間開銷。

a)壓縮前航跡

QB算法要求各航跡具有相同數量的AIS數據點，因此在使用GPS距離定義航跡之間距離函數的基礎上，需要對所有船舶航跡進行重采樣。選取不同的聚類閾值分別對洋山港水域和舟山水域的船舶交通模式進行分析，聚類結果分別見圖6和7。在原始聚類結果中，有一部分聚類簇包含的航跡數量較少，不能作為顯著的交通模式，因此建立了航跡簇篩查機制。具體來說，只有包含的航跡數量大于30條的航跡簇，才能可視化到地圖上。

a)聚類閾值為2 m

a)聚類閾值為2 m

從船舶航跡聚類結果中不難發現，聚類閾值越小，船舶交通模式的挖掘結果越精細(即航跡簇越多)，其計算開銷也越大。然而，閾值較小可能導致大量的小軌跡簇，會對水上交通模式挖掘產生較大的干擾。實驗結果表明，洋山港水域在聚類閾值為2 m時，聚類結果較好。洋山港水域的船舶活動規律為：絕大部分船舶活動于中門堂島和薄刀嘴島東側，大洋山北側、大烏龜島南側和西北側的船舶相對較少。舟山水域為狹水道，船舶的主要運動模式相對復雜，在聚類閾值為4 m時能夠挖掘出其主要的航跡規律特征。舟山水域船舶活動規律為：絕大部分船舶往返于涂茨鎮東北側與鎮海區或西堠門大橋風景旅游區之間，部分船舶活動于金塘鎮的南側和東北側、舟山普陀山機場與登步鄉之間。

3 結束語

船舶航跡挖掘有助于水上交通監管部門進一步了解海上交通發展態勢，及時根據海上交通狀況制定合適的交通管控策略(海區通航規劃、航路優化等)，有利于識別整體或指定類型船舶的活動規律，為水上交通的精細化管控提供數據支持。本文提出一種基于數據壓縮和聚類的水上交通模式識別方法。首先根據船舶航跡數據特征確定DP算法的壓縮閾值，然后利用QB算法實現船舶航跡的聚類，最后基于不同水域的AIS數據驗證分析方法的有效性。后續研究將結合船舶類型、船舶密度、船舶速度等水上交通特性對船舶交通模式及特征開展進一步的研究和探索。