牛敬華 馬良荔 覃基偉

（海軍工程大學(xué) 武漢 430000）

1 引言

在經(jīng)濟(jì)全球化背景下，海上貿(mào)易運(yùn)輸占據(jù)了全球貿(mào)易運(yùn)輸量的90%以上，海上運(yùn)輸安全因此顯得尤為重要，船舶自動(dòng)識(shí)別系統(tǒng)（Automatic Identification System，AIS）正是在這一背景下產(chǎn)生的。AIS簡(jiǎn)化和促進(jìn)了信息的交換，首先它在海上交通防避碰方面發(fā)揮了重要作用，其發(fā)出的內(nèi)容包括船只當(dāng)前的經(jīng)度、緯度、船首向、航跡向、航速等動(dòng)態(tài)信息，為船只避讓提供了充分的準(zhǔn)備時(shí)間。其次，其包含的靜態(tài)內(nèi)容包括船名、呼號(hào)、水上移動(dòng)通信業(yè)務(wù)標(biāo)識(shí)碼（Maritime Mobile Service Identify，MMSI）、國(guó)際海 事 組 織（International Maritime Organization，IMO）、船舶類(lèi)型、船長(zhǎng)、船寬、船舶狀態(tài)、吃水、目的地等，方便了海事部門(mén)對(duì)船舶的航行進(jìn)行連續(xù)的監(jiān)視和管理。AIS包含的信息比較豐富，通過(guò)分析挖掘歷史數(shù)據(jù)，可以還原船舶的歷史軌跡，分析船舶的行為模式，為海事監(jiān)管提供方便。其發(fā)出信號(hào)的頻率從兩秒到幾分鐘不等，根據(jù)船只當(dāng)前的航向狀態(tài)決定，航行速度越快，轉(zhuǎn)向速率越快，發(fā)出信號(hào)的頻率也就越高，反之，當(dāng)船只?？看a頭或者拋錨時(shí)，發(fā)出信號(hào)的頻率最低。安裝該系統(tǒng)的船只產(chǎn)生了大量的數(shù)據(jù)，合理有效地分析利用這些數(shù)據(jù)可以提高海事監(jiān)管的效率。當(dāng)前國(guó)外學(xué)者對(duì)AIS的研究比較多，海事成立了專(zhuān)門(mén)的機(jī)構(gòu)進(jìn)行研究；國(guó)內(nèi)相對(duì)來(lái)說(shuō)起步較晚，研究資料比較少。本文在研究國(guó)內(nèi)外資料的基礎(chǔ)上，提出一種基于網(wǎng)格的航道實(shí)時(shí)提取算法，可對(duì)特定區(qū)域進(jìn)行處理，提取出航道信息，用于展示實(shí)時(shí)的航道情況。

2 相關(guān)研究

按照研究對(duì)象進(jìn)行劃分，當(dāng)前的航道提取算法主要分為兩種：基于點(diǎn)的航道提取算法和基于軌跡的航道提取算法。其中，基于點(diǎn)的提取算法以單條AIS數(shù)據(jù)為單位，對(duì)點(diǎn)進(jìn)行分析，不考慮同一條船產(chǎn)生數(shù)據(jù)的關(guān)聯(lián)性，認(rèn)定AIS數(shù)據(jù)服從獨(dú)立同分布；基于軌跡的提取算法以每條船的航跡為單位，對(duì)線進(jìn)行分析。基于點(diǎn)的航道提取算法因不考慮點(diǎn)之間存在的關(guān)聯(lián)性，丟失了很多潛在信息，然而應(yīng)用比較靈活，算法復(fù)雜度低，通用性廣?；谲壽E的航道提取算法克服了以上的不足，首先把同一目標(biāo)的點(diǎn)集合組成一條軌跡，然后以軌跡為單位進(jìn)行挖掘提取，但這種方法會(huì)增加了算法設(shè)計(jì)的復(fù)雜性，提高了運(yùn)算量適合對(duì)大量數(shù)據(jù)進(jìn)行實(shí)時(shí)運(yùn)算。

1）基于點(diǎn)的軌航跡取算法

此類(lèi)算法充分利用了AIS信息中的經(jīng)度、緯度、船首向、航跡向、航速等動(dòng)態(tài)信息，采用聚類(lèi)的思想進(jìn)行分析［1］。對(duì)AIS數(shù)據(jù)中的各個(gè)屬性進(jìn)行了離散化處理，把航行速度由低到高劃分為五個(gè)區(qū)間，航行方位均分為八個(gè)區(qū)間，經(jīng)緯度每0.1°平方劃分為一個(gè)格子，在此基礎(chǔ)上對(duì)數(shù)據(jù)進(jìn)行聚類(lèi)處理，并對(duì)聚類(lèi)處理后的結(jié)構(gòu)應(yīng)用Apriori和Fp-Growth算法進(jìn)行關(guān)聯(lián)統(tǒng)計(jì)，最終得到航道信息。此方法充分利用了AIS包含的信息，獲取的知識(shí)可進(jìn)一步應(yīng)用于船舶運(yùn)動(dòng)模式預(yù)測(cè)和異常檢測(cè)［2］。考慮了在采集過(guò)程中數(shù)據(jù)可能存在的不完整性，采用遺傳算法對(duì)AIS數(shù)據(jù)進(jìn)行處理，提取數(shù)據(jù)集中密度大于設(shè)定門(mén)限的航點(diǎn)。由于對(duì)數(shù)據(jù)的處理過(guò)程是迭代進(jìn)行的，且對(duì)已提取的航點(diǎn)增加了衰減系數(shù)來(lái)保證航點(diǎn)的實(shí)時(shí)性，此算法可應(yīng)用于對(duì)實(shí)時(shí)數(shù)據(jù)流的處理［3］。提出了一種新的航道生成方法，在始發(fā)港口和目的港口之間隨機(jī)插入可能經(jīng)過(guò)的航點(diǎn)，將生成的航點(diǎn)與歷史數(shù)據(jù)的相近性作為篩選函數(shù)，通過(guò)遺傳算法進(jìn)行迭代優(yōu)化，最終產(chǎn)生連通始發(fā)港口和目的港口的航道。優(yōu)點(diǎn)在于可以進(jìn)行大量數(shù)據(jù)的運(yùn)算［4］。把電位勢(shì)法應(yīng)用于航道的表示，可使航道進(jìn)行可視化展示，也為異常檢測(cè)提供了有力支持。提出了滑動(dòng)窗口法選擇AIS數(shù)據(jù)集，用線性衰減函數(shù)表示歷史數(shù)據(jù)的權(quán)重，方便航道數(shù)據(jù)的實(shí)時(shí)更新。

2）基于軌跡的航跡提取算法

此類(lèi)算法主要是通過(guò)對(duì)軌跡間相似性應(yīng)用聚類(lèi)或分類(lèi)算法來(lái)實(shí)現(xiàn)的。由于軌跡中不同點(diǎn)之間時(shí)間間隔有長(zhǎng)有短，距離間隔也各不相同，必須先對(duì)軌跡稀疏地方進(jìn)行插值，對(duì)密集地方用軌跡壓縮算法處理，得到相對(duì)均勻平滑的歷史軌跡，再選取合適的軌跡相似度測(cè)量方法對(duì)軌跡間相似度進(jìn)行計(jì)算。文獻(xiàn)［7］通過(guò)航線生成、航線聚類(lèi)、聚類(lèi)中心線提取，提出了一種基于空間聚類(lèi)分析的南海主要航線提取方法，對(duì)南海主要航線分布特征進(jìn)行分析。此方法優(yōu)點(diǎn)在于獲取的航道模型清晰，與實(shí)際航道一致性高。文獻(xiàn)［8］根據(jù)船舶海上的運(yùn)動(dòng)特征，研究了船舶航向和航速變化規(guī)律，為研究船舶行為特征提供了新的依據(jù)。同時(shí)設(shè)計(jì)了在線識(shí)別船舶的擱置行為的算法，對(duì)航線規(guī)劃中的船舶熱點(diǎn)區(qū)域有一定的參考價(jià)值。然而，大多數(shù)已有的算法都是以軌跡的完整性為基礎(chǔ)的，在實(shí)際情況下，因AIS信號(hào)覆蓋率低或因采集時(shí)間太短，大多數(shù)情況下無(wú)法獲取完整軌跡，這些算法的效果便會(huì)下降，無(wú)法適應(yīng)復(fù)雜的應(yīng)用環(huán)境。

本文提出一種結(jié)合點(diǎn)與軌跡信息的方法，首先根據(jù)單個(gè)點(diǎn)的靜態(tài)和動(dòng)態(tài)信息，采用基于網(wǎng)格的算法提取航點(diǎn)數(shù)據(jù)，然后根據(jù)軌跡信息把得到的航點(diǎn)位置聯(lián)系起來(lái)，形成有向加權(quán)圖，提取出航道信息。

3 航道提取模型設(shè)計(jì)

航道模型的表示有多種，基于點(diǎn)的航道模型對(duì)過(guò)去點(diǎn)的信息進(jìn)行統(tǒng)計(jì)分析，把航道模型定義為該海域歷史點(diǎn)的多數(shù)行為。基于軌跡的航道模型對(duì)歷史軌跡進(jìn)行聚類(lèi)，對(duì)每個(gè)類(lèi)泛化擬合通用航跡來(lái)表示模型。

本文中航道提取模型主要分為兩個(gè)部分：航點(diǎn)的提取和航道的提取。其中，航點(diǎn)的提取是指把適航水域中具有代表性的關(guān)鍵節(jié)點(diǎn)找出來(lái)，組成有向圖的節(jié)點(diǎn)，本文定義航行歷史數(shù)據(jù)比較密集的點(diǎn)為關(guān)鍵點(diǎn)。航道提取是指根據(jù)航跡的信息將不同的航點(diǎn)用邊聯(lián)系起來(lái)，并賦予權(quán)值，形成航道模型。

3.1 航點(diǎn)的提取

由于全球的航道信息分布極不規(guī)范，對(duì)于航道的提取和應(yīng)用是分區(qū)域進(jìn)行的，本文中對(duì)航道的提取也是對(duì)選定區(qū)域進(jìn)行的，并對(duì)航點(diǎn)定義如下。

定義1（航點(diǎn)） 對(duì)于地圖上的任意一點(diǎn)P，給定一個(gè)距離閾值θ和一個(gè)數(shù)量閾值α，通過(guò)計(jì)算點(diǎn)P到數(shù)據(jù)記錄中所有AIS點(diǎn)的距離，若距離小于θ的數(shù)量大于α，則認(rèn)定點(diǎn)P為航點(diǎn)，如式（1）所示。

通過(guò)借用分布式計(jì)算的思想，先將選定區(qū)域劃分成長(zhǎng)為Δlon、寬為Δlat的網(wǎng)格，分別計(jì)算得到每一個(gè)網(wǎng)格內(nèi)的航點(diǎn)，然后將每個(gè)網(wǎng)格內(nèi)的航點(diǎn)集合起來(lái)，最終得到整個(gè)區(qū)域內(nèi)的航點(diǎn)數(shù)據(jù)。網(wǎng)格邊長(zhǎng)的選取需要對(duì)具體海域和數(shù)據(jù)進(jìn)行調(diào)整，若網(wǎng)格的邊太大，會(huì)造成各個(gè)網(wǎng)格內(nèi)點(diǎn)分布極為不均，影響計(jì)算性能；若選取太小，則許多網(wǎng)格內(nèi)的點(diǎn)太少以至于無(wú)法識(shí)別為航點(diǎn)。

航點(diǎn)提取算法如表1中算法所示，（2～6）首先遍歷數(shù)據(jù)集，將每個(gè)點(diǎn)劃分到對(duì)應(yīng)的網(wǎng)格中。（7）選擇每個(gè)網(wǎng)格中符合航點(diǎn)的標(biāo)準(zhǔn)的點(diǎn)，首先從網(wǎng)格中任選一點(diǎn)point-a，（11～17）然后統(tǒng)計(jì)網(wǎng)格中附近點(diǎn)的數(shù)量，（18～22）如果點(diǎn)point-a附近點(diǎn)數(shù)量多于閾值α，則認(rèn)定其為航點(diǎn)。航點(diǎn)附近的點(diǎn)作為航點(diǎn)一部分，從待處理的數(shù)據(jù)集中刪去。

3.2 航道的提取

孤立的航點(diǎn)包含的信息量是有限的，只能代表距離該航點(diǎn)周?chē)葍?nèi)的歷史航行情況，只有把孤立的航點(diǎn)聯(lián)系起來(lái)，才能形成有信息支撐的航道圖。

航道的提取是在獲取到航點(diǎn)之后進(jìn)行的，提取過(guò)程中應(yīng)用到軌跡的連續(xù)信息。要得到軌跡數(shù)據(jù)，需要對(duì)AIS數(shù)據(jù)集進(jìn)一步處理。首先將AIS數(shù)據(jù)按照MMSI區(qū)分開(kāi)，得到每條船的軌跡數(shù)據(jù)集，再將每個(gè)數(shù)據(jù)集中點(diǎn)的順序按照時(shí)間戳排列，便得到每條船的軌跡。由于船舶在不同行駛狀態(tài)下發(fā)出AIS信號(hào)的頻率不同，船速較高和轉(zhuǎn)向率高時(shí)頻率高，船速低時(shí)頻率低，這就意味著同一條船的軌跡點(diǎn)分布是不均勻的。

表1 航點(diǎn)提取算法

如圖1（a）所示，為未處理的原始軌跡，其軌跡點(diǎn)密度分布不均勻。在矩形標(biāo)識(shí)區(qū)域太過(guò)稠密，而在圓形標(biāo)識(shí)區(qū)域，沒(méi)有軌跡點(diǎn)，太過(guò)稀疏，軌跡點(diǎn)過(guò)于稠密和稀疏都會(huì)對(duì)算法產(chǎn)生不良影響。此外，在一些AIS基站無(wú)法完全覆蓋到的盲區(qū)，也會(huì)有一些空白。因此要對(duì)軌跡進(jìn)行預(yù)處理，使軌跡平滑均勻，預(yù)處理算法如表2中算法所示。對(duì)軌跡的處理包括兩種情況：對(duì)于軌跡點(diǎn)稀疏的部分，要進(jìn)行插值處理，補(bǔ)足可能遺漏的AIS信息；對(duì)于太密集的部分，為了減少計(jì)算量，要進(jìn)行軌跡壓縮處理，刪去冗余的軌跡點(diǎn)。軌跡插值算法比較成熟，插值后軌跡較為平滑的算法有拉格朗日插值和牛頓插值，本文為了計(jì)算方便采用簡(jiǎn)單的線性插值。插值后會(huì)出現(xiàn)點(diǎn)在陸地上的情況，在實(shí)際實(shí)驗(yàn)中，這種情況較少出現(xiàn)，不會(huì)對(duì)結(jié)果造成影響，故對(duì)此類(lèi)錯(cuò)誤不做額外處理。對(duì)于軌跡壓縮算法近年來(lái)相關(guān)研究也比較多［5～6，9］，本文在結(jié)合已提出壓縮算法的優(yōu)缺點(diǎn)，綜合算法性能和所需實(shí)際出發(fā)，采用在線壓縮算法，將軌跡中密集且非關(guān)鍵點(diǎn)刪除。對(duì)單條軌跡處理效果如圖1（b）所示，處理后的軌跡點(diǎn)分布比較均勻，軌跡平滑。

圖1 軌跡預(yù)處理

算法2中對(duì)軌跡進(jìn)行處理使其密度均勻，（2）對(duì)于軌跡中每個(gè)點(diǎn)Q，（3）計(jì)算其與前一個(gè)點(diǎn)的距離distance，（4～5）若距離大于設(shè)定的臨界點(diǎn)距離，則應(yīng)用插值算法，在這兩點(diǎn)間插入點(diǎn)；（6～7）若距離小于設(shè)定的臨界點(diǎn)距離的一半，則應(yīng)用壓縮算法，刪去點(diǎn)Q及其后面距離太小的點(diǎn)。

表2 軌跡預(yù)處理算法

軌跡預(yù)處理完成后，把軌跡經(jīng)過(guò)的航點(diǎn)關(guān)聯(lián)起來(lái)。對(duì)于每一條軌跡，如果按照時(shí)間順序依次經(jīng)過(guò)了A、B兩個(gè)航點(diǎn)，便認(rèn)為A、B兩點(diǎn)存在聯(lián)系，將A指向B的有向邊權(quán)重加一。如表3中算法所示，（1）首先初始化航道圖，（2）對(duì)于數(shù)據(jù)集中的每一條軌跡，（4～5）遍歷軌跡中的每一個(gè)點(diǎn)，（6～10）如果航跡中當(dāng)前點(diǎn)所屬于的航點(diǎn)與之前點(diǎn)所屬的航點(diǎn)不同，則將兩點(diǎn)對(duì)應(yīng)的航點(diǎn)關(guān)聯(lián)起來(lái)，權(quán)值增加（7）。

定義2 對(duì)于軌跡trajectory和航點(diǎn)Q，若在trajectory上的任意一點(diǎn)P，該點(diǎn)距離航點(diǎn)Q的距離小于θ，則認(rèn)定軌跡trajectory經(jīng)過(guò)航點(diǎn)Q，如式（2）、（3）所示。

在得到的有向加權(quán)圖中，兩個(gè)航點(diǎn)之間的邊權(quán)重越大，說(shuō)明存在的聯(lián)系越密切，從一點(diǎn)駛向另一點(diǎn)的可能性就越高。

表3 航道提取算法

航點(diǎn)之間的聯(lián)系建立之后，需要對(duì)邊的權(quán)重做歸一化處理，歸一化后邊的值表示流動(dòng)的概率，概率大小與權(quán)重正相關(guān)，權(quán)重越大，概率越高，從任意一點(diǎn)出發(fā)的所有的邊權(quán)重和為1。

4 實(shí)驗(yàn)與分析

本文實(shí)驗(yàn)所用計(jì)算機(jī)為通用型計(jì)算機(jī)，CPU型號(hào)i7-4700，內(nèi)存16GB-DRR3。實(shí)驗(yàn)數(shù)據(jù)集為公開(kāi)AIS數(shù)據(jù)，選取南海海域西至113.5°E，東至114°，南至21.9°N，北至22.4°N，共20萬(wàn)條數(shù)據(jù)。如圖2所示，觀察數(shù)據(jù)集可發(fā)現(xiàn)主要包括兩條航道，從點(diǎn)A至B和從A至C，本實(shí)驗(yàn)將航道從AIS信息中提取出來(lái)，并以有向加權(quán)圖的形式予以表示。

圖2

4.1 數(shù)據(jù)預(yù)處理

在獲得的公開(kāi)AIS數(shù)據(jù)中，存在許多錯(cuò)誤數(shù)據(jù)和無(wú)法使用的數(shù)據(jù)，需要對(duì)數(shù)據(jù)進(jìn)行預(yù)處理。預(yù)處理包括兩部分：對(duì)錯(cuò)誤數(shù)據(jù)的剔除和對(duì)軌跡的預(yù)處理。

首先將數(shù)據(jù)中航速過(guò)高、經(jīng)緯度不在正常范圍內(nèi)的數(shù)據(jù)進(jìn)行過(guò)濾處理，其次對(duì)軌跡中前后兩點(diǎn)時(shí)間戳的差太大的數(shù)據(jù)進(jìn)行篩除。

4.2 航點(diǎn)提取

實(shí)驗(yàn)中網(wǎng)格邊的選取為Δlon=Δlat=3θ，θ為0.008°，α為80，對(duì)所選區(qū)域分網(wǎng)格進(jìn)行航點(diǎn)提取，效果如圖4所示，提取到航點(diǎn)后，將距離航點(diǎn)θ以?xún)?nèi)的點(diǎn)清除掉，如圖5所示，只剩下3.75%的點(diǎn)，說(shuō)明航點(diǎn)代表了大部分的點(diǎn)，包含了航道的主要信息。也就是說(shuō)，本次提取到的航點(diǎn)可以作為航道的關(guān)鍵點(diǎn)使用。

圖3

4.3 航道提取

在已得到的航點(diǎn)的基礎(chǔ)上，利用軌跡信息將航點(diǎn)之間的邊補(bǔ)充完整，形成有向加權(quán)圖。

如圖4所示，黑色線表示航點(diǎn)之間的聯(lián)系，線段的粗細(xì)表示權(quán)重大小，這與圖2中表現(xiàn)出的航跡點(diǎn)密度一致。已提取的航道中航點(diǎn)過(guò)于密集，不利于進(jìn)行下一步的使用，需要進(jìn)行壓縮處理，刪除中間部分冗余航點(diǎn)。本文實(shí)驗(yàn)首先根據(jù)每個(gè)點(diǎn)的航向提取出局部公共航向，將垂直于公共航向且鄰接的航點(diǎn)合并，形成一條按航向分布的航點(diǎn)線。然后采用道格拉斯算法對(duì)合并后的航點(diǎn)進(jìn)行壓縮，只保留兩端和中間曲度較大的航點(diǎn)信息。

圖4

圖5

如圖5，當(dāng)船舶在航道中沿1→2→3→6→5→4和10→9→8→7→6→5→4方向航行時(shí)，對(duì)于船舶未來(lái)方向的預(yù)測(cè)是容易的，只需沿著連接航點(diǎn)的道路前進(jìn)即可，終點(diǎn)都是4位置。反之，當(dāng)沿反方行航行，尤其是到達(dá)點(diǎn)6時(shí)，未來(lái)航向的預(yù)測(cè)有兩種可能，即駛向點(diǎn)3或駛向點(diǎn)7，本實(shí)驗(yàn)中其概率分別為 p（6→3）=w（6→3）/（w（6→3）+w（6→7））=13%和 p（6→7）=w（6→ 7）/（w（6→3）+w（6→7））=87%。

5 結(jié)語(yǔ)

本文借鑒了基于點(diǎn)的航道提取算法和基于軌跡的航道提取的算法的優(yōu)點(diǎn)，提出了一種基于網(wǎng)格的航道模式提取算法。此算法復(fù)雜度低，可應(yīng)用于特定區(qū)域航道模型的快速提取，且得到的有向加權(quán)圖可進(jìn)行船舶未來(lái)運(yùn)動(dòng)模式的預(yù)測(cè)。

隨著我國(guó)對(duì)外開(kāi)放水平的提高，海運(yùn)安全也變得越來(lái)越重要。航道的提取，海事異常的檢測(cè)、船舶未來(lái)運(yùn)動(dòng)模式的預(yù)測(cè)是充滿(mǎn)挑戰(zhàn)性的研究課題，針對(duì)當(dāng)前AIS數(shù)據(jù)量大，人工管理困難的現(xiàn)狀，本文提出了一種航道提取算法，可有效表示當(dāng)前航道模型，基于此可進(jìn)行船舶未來(lái)運(yùn)動(dòng)模式的預(yù)測(cè)，為海事情況的自動(dòng)化監(jiān)督提供支撐。

未來(lái)的研究工作包括：

1）建立針對(duì)海量AIS數(shù)據(jù)的存儲(chǔ)查詢(xún)底層數(shù)據(jù)庫(kù)，可以針對(duì)時(shí)間和時(shí)空快速檢索船只的歷史信息。

2）建立可有效檢測(cè)船舶異常行為的模型，進(jìn)一步提升海事管理的智能程度。