基于網格的航道模式提取算法研究?

牛敬華 馬良荔 覃基偉

（海軍工程大學 武漢 430000）

1 引言

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

2 相關研究

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

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

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

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

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

本文提出一種結合點與軌跡信息的方法，首先根據單個點的靜態和動態信息，采用基于網格的算法提取航點數據，然后根據軌跡信息把得到的航點位置聯系起來，形成有向加權圖，提取出航道信息。

3 航道提取模型設計

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

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

3.1 航點的提取

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

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

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

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

3.2 航道的提取

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

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

表1 航點提取算法

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

圖1 軌跡預處理

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

表2 軌跡預處理算法

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

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

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

表3 航道提取算法

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

4 實驗與分析

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

圖2

4.1 數據預處理

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

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

4.2 航點提取

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

圖3

4.3 航道提取

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

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

圖4

圖5

如圖5，當船舶在航道中沿1→2→3→6→5→4和10→9→8→7→6→5→4方向航行時，對于船舶未來方向的預測是容易的，只需沿著連接航點的道路前進即可，終點都是4位置。反之，當沿反方行航行，尤其是到達點6時，未來航向的預測有兩種可能，即駛向點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 結語

本文借鑒了基于點的航道提取算法和基于軌跡的航道提取的算法的優點，提出了一種基于網格的航道模式提取算法。此算法復雜度低，可應用于特定區域航道模型的快速提取，且得到的有向加權圖可進行船舶未來運動模式的預測。

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

未來的研究工作包括：

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

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