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

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

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

0 引 言

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

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

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

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

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

1.1 航跡壓縮算法

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

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

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

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

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

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

整條航跡按照上述方法處理完畢后，依次連接航跡曲線上的各個(gè)關(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)存在兩個(gè)主要缺點(diǎn)：(1)忽略了航跡間的順序性；(2)算法復(fù)雜度高。針對(duì)這兩個(gè)主要缺點(diǎn)，本文提出一種相對(duì)簡(jiǎn)單的最小平均直接翻轉(zhuǎn)距離。對(duì)于最小平均直接翻轉(zhuǎn)距離所要求的不同船舶航跡應(yīng)具有相同數(shù)量的樣本點(diǎn)，可通過(guò)線性插值的方法達(dá)到。

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

(4)

(,)=(,)=(,)

(5)

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

(6)

a)直接距離

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

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

=∑/

(7)

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

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

2 實(shí)例驗(yàn)證與分析

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

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

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

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

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

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

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

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

a)壓縮前航跡

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

a)壓縮前航跡

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

a)聚類閾值為2 m

a)聚類閾值為2 m

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

3 結(jié)束語(yǔ)

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