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

陳信強(qiáng)，徐祥龍，彭靜，孫洋，王梓創(chuàng)，閻瑩

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

0 引 言

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

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

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

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

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

1.1 航跡壓縮算法

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

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

連接該航次出發(fā)地、目的地兩點(diǎn)，標(biāo)記為線段。

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

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

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

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

1.2 QB算法

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

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

(1)

(2)

(3)

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

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

(4)

(,)=(,)=(,)

(5)

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

(6)

a)直接距離

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

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

=∑/

(7)

式中：是經(jīng)過重采樣后的包含個船舶位置(經(jīng)緯度)信息的某條航跡數(shù)據(jù)構(gòu)成的×2階的矩陣；為簇內(nèi)船舶航跡數(shù)量。

若與當(dāng)前所有簇的質(zhì)心航跡之間的最小直接翻轉(zhuǎn)距離均大于聚類閾值，則創(chuàng)建一個新的簇，并將添加至新簇中；反之，則將添加至與其最小直接翻轉(zhuǎn)距離最小的簇中。

2 實例驗證與分析

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

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

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

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

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

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

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

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

a)壓縮前航跡

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

a)壓縮前航跡

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

a)聚類閾值為2 m

a)聚類閾值為2 m

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

3 結(jié)束語

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