基于AIS數據的船舶運動模式識別與應用

魏照坤+周康+魏明+史國友

摘要：

船舶運動模式的提取是軌跡數據分析的重要任務，它可以為船舶異常行為的檢測提供參考依據，同時也可以作為航路規劃和定線制設計的技術指標.針對現存的聚類算法大多為了追求效率而忽略了運動軌跡特征的問題，對聚類算法中的軌跡結構距離進行改進，將其作為軌跡相似度的評價標準.采用無監督DBSCAN聚類算法實現船舶運動模式的提取.利用瓊州海峽船舶自動識別系統（AutomaticIdentificationSystem，AIS）數據，對該水域的船舶運動模式進行提取，獲得行駛于該水域的船舶運動軌跡分布以及各類軌跡中轉向區域的分布，其中船舶運動軌跡包括從瓊州海峽東峽口向西航行的船舶軌跡，從瓊州海峽西峽口向東航行的船舶軌跡，從秀英港前往海安港的船舶軌跡，從海安港前往秀英港的船舶軌跡和從瓊州海峽東峽口前往?？诟鄣拇败壽E.將最終的聚類結果應用于電子海圖顯示與信息系統（ElectronicChartDisplayandInformationSystem，ECDIS）上，實現了對船舶的動態監控仿真.

關鍵詞：

船舶自動識別系統（AIS）；模式識別；聚類分析；電子海圖顯示與信息系統（ECDIS）；瓊州海峽

中圖分類號：U697.33

文獻標志碼：A 收稿日期：20150907 修回日期：20151102

0引言

隨著全球船舶自動識別系統（AutomaticIdentificationSystem，AIS）岸站的建立和不斷完善，各地海事主管機關時刻都能接收到大量有關船舶信息的數據.對這些數據的研究可以幫助我們提取船舶運動模式，分析船舶行為，從而進一步挖掘不同航線船舶、不同類型船舶的運動特點.例如：在一些運量較大的港口附近，對船舶運動軌跡進行分類能夠幫助監控人員識別異常行為；根據漁船運動的無規律性和貨船運動的周期性，利用聚類結果區分船舶種類，判斷運動特征是否與船舶類型相符，是否需要進一步的監控和調查.此外，船舶運動軌跡的聚類分析能夠為航路規劃和定線制的設計提供理論依據，有利于加強船舶動態監控，提高海事監管的效率.

目前國內外學者提出了諸多從目標對象的軌跡中獲取運動模式的方法.SHU等[1]利用自組織映射網絡作為預處理技術標記行人的運動特征，然后采用后向算法建立馬爾科夫模型，實現了對人行為模式的提取；胡宏宇等[2]以改進的Hausdorff距離作為相似度標準，采用譜聚類算法實現了對車輛軌跡空間分布的提?。宦劶训萚3]利用加權的Hausdorff距離和周分割算法實現了車輛軌跡的聚類；RISTIC等[4]基于港口信息，采用核密度估計的方法對船舶軌跡進行分類；ETIENNE等[5]提出了一種基于統計學和圖論的軌跡聚類分析方法，該方法將船舶的起訖港作為節點，將相似軌跡歸一化為特定的有向路徑；AARSETHER等[6]采用圖像匹配的方法對船舶軌跡進行聚類；GERBEN等[7]對提取船舶運動模式的兩種主要的相似度對比的方法進行了分析，總結出二者中更適合于船舶軌跡聚類的方法；ANDERS等[8]將軌跡聚類應用于近海監控系統來識別船舶的異常行為；LAXHAMMAR等[9]通過高斯混合模型和核密度估計的方法對船舶運動進行統計分析，獲得有異常行為的船舶數據.此外，神經網絡和以K均值為代表的無監督聚類方法也被廣泛應用于軌跡聚類，如JONHSON等[10]建立自組織特征映射網絡學習軌跡分布模式，ATEV等[11]則利用K均值算法完成對軌跡的聚類.

海上交通與陸路交通有一定的相似性.道路被劃分為單行道、雙行道等，而航路也被劃分為單向航路和雙向航路.雖然海上交通的航行范圍廣闊，但在某些特定水域（港口、通航分道、狹水道）船舶密度較大，軌跡分布較密集.鑒于此特點，應用在陸路交通上的一些方法也可以應用到海上交通，以提高海上交通的監管力度和效率.

1AIS數據的預處理

由船舶交通管理中心（VesselTrafficServicecenter，VTS）提供的AIS數據通常具有較高的可信度，但是AIS數據中的船舶位置、船舶速度等信息會由于設備以及信號漂移等原因發生較大的改變，如AIS數據顯示船舶位于陸地上，顯示航速為35kn甚至更高[12].

為保證數據的可用，需要對數據做預處理，具體方法如下.

2軌跡聚類

移動目標軌跡的聚類能否取得良好的效果，在于軌跡間的相似性度量是否合理.當前主要的相似性度量的方法有基于歐氏距離的算法、基于公共子序列的算法、基于動態時間彎曲距離的方法和基于Hausdorff距離的方法，其中基于歐氏距離的算法通常用于計算等長的船舶軌跡相似性，其他的幾種方法可以用于不同長度的船舶軌跡相似性計算.以上方法都僅從距離方面反映相似度，而基于軌跡結構距離的相似性度量方法的優點在于能夠刻畫每條子軌跡變化的趨勢.因此，為便于度量船舶軌跡的變化，需要將整條軌跡劃分成若干條子軌跡.

2.1軌跡分割

船舶軌跡的劃分是通過設置船舶轉向角的閾值實現的.船舶軌跡轉向角是指相鄰兩個子軌跡段的航跡向之差，見圖1.

圖1中，a，b為軌跡中的兩條子軌跡段，其航跡向的夾角為θ1，即為這兩條子軌跡的轉向角.鑒于AIS數據的位置坐標采用的是WGS84坐標系，利用恒向線直接反解算法[13]求得兩條子軌跡段的航跡向，根據其航跡向的差值可以獲得船舶子軌跡間的轉向角.

恒向線直接反解算法的步驟如下.

2.2軌跡結構相似性度量

船舶子軌跡段相似性計算從子軌跡段的航跡向和兩條子軌跡段間的距離兩個方面進行.對兩方面的度量結果賦以一定的權重求和，形成軌跡的結構距離.

（1）船舶航跡向的比較.

如圖2所示，Li，Lj表示兩條航跡線，θ表示航跡段的方向夾角，J表示Lj相對于Li的偏轉程度.

航跡向對比方法為

通過上式不難發現：當夾角為0°時為最佳狀態，即兩條子軌跡方向完全一致；當夾角大于90°時可以認為兩條軌跡基本反向，將兩條軌跡的距離設置為無窮大，這樣有利于區分航向相反船舶的軌跡.

（2）位置的比較.

本文在兩條子軌跡段間距離的度量方面所采用的相似性度量方法為基于Hausdorff距離的方法：

式中：P（Li，Lj）為兩軌跡間的位置距離；h（Li，Lj）為兩軌跡間的直接Hausdorff距離；d（a，b）為a與b之間的歐氏距離.

船舶軌跡結構是指船舶軌跡所具有的屬性的集合，這些屬性刻畫了船舶軌跡的特性和狀態.船舶軌跡結構通常包含船舶運動信息，如：船舶的航跡向、船舶的位置.同時，在實際應用中還可以加入速度以及波動性的度量.進行軌跡相似性的比較時，充分考慮這些因素可以提高聚類的精度[14].依照式（8）和（9）可以求得子軌跡航跡向以及子軌跡間距離相似度.為計算軌跡結構的相似性，還需設定他們在軌跡結構中所占的權重W=（WT，WP），其中WT表示角度距離權重，WP表示位置距離權重.各權重值設定應滿足：權重值之和應為1；各權重值應為非負，同時不能大于1.通常情況下采用的是將結構距離中的權重平均分配.式（11）和（12）分別為結構距離和相似度計算方法.

2.3聚類算法

基于軌跡結構距離的聚類算法是以DBSCAN算法為框架的，即從子軌跡集合中任取一條軌跡并判斷在其鄰域半徑內是否包含滿足要求的最小實體數.如果滿足以上述條件，則認為是核實體，并搜索該實體的密度可達對象，標記為一類，直至子軌跡集合全部掃描完畢，未被標記的子軌跡則是孤立軌跡.具體的實現方法如下.

步驟1設定權重W，轉向角閾值ω，近鄰閾值η，近鄰的數目ε.

步驟2根據ω將軌跡T分割成若干個子軌跡Ti.

步驟3對子軌跡段Ti，計算其與未標記的子軌跡段的D和N，若滿足D和N條件的軌跡數目大于ε則將該子軌跡段標記為核心子軌跡段.

步驟4將Ti子軌跡段距離范圍D內滿足N條件的子軌跡段Tj與Ti聚為一類.

步驟5對Tj重復步驟3和4，將滿足條件的子軌跡段繼續歸為一類，如果Tj不再滿足上述條件，則重新從子軌跡集合中選取未被聚類的子軌跡段重復步驟3和4.直至軌跡集合全部掃描完畢.

3瓊州海峽應用實例與應用

瓊州海峽位于雷州半島與海南島之間，寬10～20nmile，長50～60nmile，是廣州港、湛江港等港口與北部灣各港口海上交通的捷徑.瓊州海峽主要可分為3部分，分別為：瓊州海峽東口，包括外羅水道、北水道、中水道和南水道；瓊州海峽西口，包括燈樓角與臨高角聯線以西、兵馬角所在經度線以東水域，該水域是來往于瓊州海峽駛往八所港、三亞港等地的轉向點，也是往北部灣各港口的轉向點；瓊州海峽中部，包括山狗吼燈塔經度線以西、燈樓角與臨高角聯線以東水域，該水域的水較深（20～118m），礙航物較少.

算例采用32位WIN7系統、2GRAM，在VS2010編譯條件下提取750條船舶運動軌跡進行聚類，獲得了5類結果，見圖3.A類結果為從瓊州海峽東峽口向西行駛于通航分道內的船舶的航行軌跡分布、B類結果為從瓊州海峽西峽口向東行駛于反向航道的船舶的航行軌跡分布、C類結果為從海安港到秀英港的船舶的航行軌跡分布、D類結果為從秀英港到海安港的船舶的航行軌跡分布、E類結果為瓊州海峽東峽口向西行駛進入?？诟鄣拇暗暮叫熊壽E分布.

3.1算法分析

為比較算法的優劣，將基于軌跡結構距離的DBSCAN算法與傳統的DBSCAN算法進行對比，結果見表2.

表2算法對比結果

從表2中可以看出，基于軌跡結構距離的DBSCAN算法在運行時間方面劣于傳統的DBSCAN算法，但是在分類結果和準確度方面皆優于傳統的DBSCAN算法.這是因為：基于軌跡結構距離的DBSCAN算法需要進行軌跡的分割、角度的度量、歸一化等操作，增加了計算復雜度；該算法以軌跡特征為參考，從多方面計算軌跡相似度，易發現比較隱蔽的軌跡群，使其聚類效果優于傳統的DBSCAN算法的聚類效果.

3.2聚類應用

將上述所獲得的船舶軌跡聚類的結果應用到船舶監控、異常檢測上，能夠大幅度提高海上安全保障能力，防止海上交通事故的發生[15].

3.2.1速度監控

速度監控是利用監控水域的AIS信息，對聚類結果中的船舶速度進行統計，獲得船速分布圖.根據實際工作中的經驗和需要，確定行駛于該監控水域的船舶速度監控范圍.圖4是對從瓊州海峽東峽口航行至?？诟鄣拇八俣冉y計.對于該監控水域，本文以80%船舶運營速度（9～14kn）為標準.

圖5為監控系統的速度報警，可以看出編號為A的船超速，說明該船航速不在監控航速范圍內，予以報警.

3.2.2位置監控

位置監控主要是對航行于聚類結果區域的船舶進行船位的實時監控，如果船舶偏離監控水域，本船和監控系統應給予報警和提示，提醒監控人員和船舶駕駛員關注船舶動向.圖6a為本船的位置報警示意圖，圖6b為監控系統的位置報警示意圖.

3.2.3航向監控

航向監控主要利用AIS數據對聚類結果中船舶航向進行統計，獲得船舶的航向分布，以此作為監控依據.圖7a是對從瓊州海峽東峽口到?？诟鄣木垲惤Y果中船舶轉向后的航向統計結果.圖7b和7c為本船和監控系統的航向報警示意圖.

綜上所述，可以得到船舶監控的實現流程圖（圖8），首先對進入監控水域的船舶進行位置監控（若偏離監控水域則報警），然后進行速度監控（判斷速度是否超出規定范圍，如果超出則進行速度報警），接著進行航向的監控直至船舶駛離監控水域.

4結論

本文利用軌跡結構距離作為相似性的度量標準，對軌跡段間的相似性進行評價，采用無監督的DBSCAN算法將相似性接近的船舶軌跡歸為一類，實現了對船舶運動模式的提取.以瓊州海峽為例，利用預處理過的部分瓊州海峽AIS數據，將航行于該水域的船舶軌跡分為5類，分別為從瓊州海峽東峽口向西航行的船舶軌跡、從瓊州海峽西峽口向東航行的船舶軌跡、從海安港到秀英港的船舶軌跡、從秀英港到海安港的船舶軌跡以及從瓊州海峽東峽口向西航行進入?？诟鄣拇败壽E.從瓊州海峽東峽口向西航行的船舶軌跡位于（20°14′25″N，110°26′20″E）與（20°09′05″N，110°01′24″E）之間的通航分道內；從瓊州海峽西峽口向東航行的船舶軌跡分布于（20°13′N，110°26′20″E）與（20°06′45″N，110°01′24″E）之間的通航分道內；從瓊州海峽東峽口向西航行進入海口港的船舶軌跡，其轉向位置大約發生在以（20°10′16″N，110°14′08″E）為圓心，半徑為0.5nmile的水域范圍內.將聚類的結果與ECDIS模擬器相結合，從船舶位置、速度、航向等3個方面實現了船舶動態監控的仿真.實驗證明船舶運動模式識別能夠有效地應用于船舶動態監控，進而保障航行安全，增強海上安全保障能力.

參考文獻：

[1]SHUHM，KATSU.TraininghiddenMarkovmodelstructurewithgeneticalgorithmforhumanmotionpatternclassification[C]//SCIICASEInternationalJointConference.Busan：IEEEPress，2006：618622.

[2]胡宏宇，王慶年，曲昭偉，等.運動目標空間模式識別與異常行為檢測[J].吉林大學學報，2011，41（6）：15981602.

[3]聞佳，崔維.實時視頻中的車輛運動軌跡的提取和聚類[J].計算機工程與應用，2010，46（11）：155157.

[4]RISTICB，SCALARL.StatisticalanalysisofmotionpatterninAISdata：anomalydetectionandmotionprediciton[C]//11thInternationalConferenceonInformaiton.Fusion，Cologne：IEEEPress，2008：17.

[5]ETIENNEL，DEVOGELET.Similarityanalysisofmobileobjectstrajectoriesfollowingthesameitinerary[J].IngenierieDesSystemesDinformation，2009，14（5）：85106.

[6]AARSETHERKG，TORGEIRM.EstimatingnavigationpatternsfromAIS[J].JournalofNavigaiton，2009，65（4）：587607.

[7]GERBENKDV，MAARTENVS.Ananalysisofalignmentandintegralbasedkernelsformachinelearningfromvesseltrajectoris[J].ExpertSystemswithApplications，2014，41（2）：75967607.

[8]ANDERSD，LARSN.Trajectoryclusteringforcoastalsurveillance[C]//10thInternationalConferenceonInformationFusion.Quebec：IEEEPress，2007：18.

[9]LAXHAMMARR，FALKMANG，SVIESTINSE.AnomalydetectioninseatrafficacomparisionoftheGaussianmixturemodelandthekerneldensityesimator[C]//12thInternationalConferenceonInformaitonFusion.Seattle：IEEEPress，2009：756763.

[10]JOHNSONN，HOGGD.Learningthedistributionofobjecttrajectoriesforeventrecognition[J].ImageandVisionComputing，1996，14（8）：609615.

[11]ATEVS，MASOUDO，PAPANIKOLOPOULOSN.Learningtrafficpatternsatintersectionsbyspectralclusteringofmotiontrajectories[C]//IEEEInternationalConferenceonIntelligentRobotsandSystems.Beijing：IEEEPress，2006：48514856.

[12]QUXB，MENGQ，LISY.ShipcollisionriskassessmentfortheSingaporestrait[J].AccidentAnalysisPrevention，2011，43（3）：20302036.

[13]史國友，朱公志，賈傳熒，等.恒向線主題直接正反解的高精度算法[J].大連海事大學學報，2009，35（2）：59.

[14]YUANG，XIASX，ZHANGL.Anefficienttrajectoryclusteringalgorithmbasedonstructuralfeatures[J].JournalofComputationalInformationSystems，2011，7（11）：10271035.

[15]王艷軍，王曉峰.AIS和北斗終端組合在船舶動態監控中的應用[J].上海海事大學學報，2011，32（4）：1721.