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

摘要：

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

關鍵詞：

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

中圖分類號：U697.33

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

0引言

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

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

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

1AIS數(shù)據(jù)的預處理

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

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

2軌跡聚類

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

2.1軌跡分割

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

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

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

2.2軌跡結(jié)構(gòu)相似性度量

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

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

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

航跡向?qū)Ρ确椒?/p>

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

（2）位置的比較.

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

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

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

2.3聚類算法

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

步驟1設定權(quán)重W，轉(zhuǎn)向角閾值ω，近鄰閾值η，近鄰的數(shù)目ε.

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

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

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

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

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

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

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

3.1算法分析

為比較算法的優(yōu)劣，將基于軌跡結(jié)構(gòu)距離的DBSCAN算法與傳統(tǒng)的DBSCAN算法進行對比，結(jié)果見表2.

表2算法對比結(jié)果

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

3.2聚類應用

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

3.2.1速度監(jiān)控

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

圖5為監(jiān)控系統(tǒng)的速度報警，可以看出編號為A的船超速，說明該船航速不在監(jiān)控航速范圍內(nèi)，予以報警.

3.2.2位置監(jiān)控

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

3.2.3航向監(jiān)控

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

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

4結(jié)論

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

參考文獻：

[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，F(xiàn)ALKMANG，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和北斗終端組合在船舶動態(tài)監(jiān)控中的應用[J].上海海事大學學報，2011，32（4）：1721.