基于網(wǎng)格的航道模式提取算法研究?

牛敬華 馬良荔 覃基偉

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

1 引言

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

2 相關(guān)研究

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

1）基于點的軌航跡取算法

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

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

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

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

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

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

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

3.1 航點的提取

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

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

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

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

3.2 航道的提取

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

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

表1 航點提取算法

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

圖1 軌跡預(yù)處理

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

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

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

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

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

表3 航道提取算法

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

4 實驗與分析

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

圖2

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

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

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

4.2 航點提取

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

圖3

4.3 航道提取

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

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

圖4

圖5

如圖5，當船舶在航道中沿1→2→3→6→5→4和10→9→8→7→6→5→4方向航行時，對于船舶未來方向的預(yù)測是容易的，只需沿著連接航點的道路前進即可，終點都是4位置。反之，當沿反方行航行，尤其是到達點6時，未來航向的預(yù)測有兩種可能，即駛向點3或駛向點7，本實驗中其概率分別為 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ōu)點，提出了一種基于網(wǎng)格的航道模式提取算法。此算法復(fù)雜度低，可應(yīng)用于特定區(qū)域航道模型的快速提取，且得到的有向加權(quán)圖可進行船舶未來運動模式的預(yù)測。

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

未來的研究工作包括：

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

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