基于運動屬性約束的船舶AIS 航跡去糾纏方法

劉敬一, 高曉倩, 郭 琦, 姚 晨, 裴新宇, 陳金勇

(中國電子科技集團公司第五十四研究所, 河北 石家莊 050081)

0 引言

隨著船舶自動識別系統(tǒng)(Automatic Identification System,AIS)的不斷發(fā)展,船舶航跡數(shù)據(jù)呈現(xiàn)爆炸式增長[1-3],這為船舶行為模式特征以及交通航行規(guī)律的挖掘與分析提供了豐富的數(shù)據(jù)支撐[4]。船舶原始航跡數(shù)據(jù)的可靠性和可用性是進行上述分析挖掘的前提,因此船舶AIS 異常定位數(shù)據(jù)篩選、剔除等預(yù)處理對船舶行為預(yù)測、異常監(jiān)測和航路規(guī)劃等諸多具體應(yīng)用具有重要意義[5]。

航跡糾纏作為AIS 數(shù)據(jù)的常見異常之一,是進行航跡預(yù)處理的難點[6]。 船舶航跡糾纏是指AIS 數(shù)據(jù)中的船位相連之后得到的船舶航跡在時間排序上存在錯位,致使產(chǎn)生糾纏點[7]。 基于AIS 數(shù)據(jù)的船舶航跡糾纏產(chǎn)生的原因概括為2 種:一是船舶定位誤差較大,導(dǎo)致AIS 數(shù)據(jù)中的船位偏離真實船位;二是AIS 數(shù)據(jù)在傳輸或者解析過程中出現(xiàn)了錯誤,導(dǎo)致船位時序?qū)傩猿霈F(xiàn)較大誤差。

現(xiàn)有船舶航跡糾纏去除方法可以劃分為3 大類:① 基于航跡抽稀的航跡去糾纏;② 基于閾值篩選的航跡去糾纏;③ 基于神經(jīng)網(wǎng)絡(luò)的航跡去糾纏。

基于航跡抽稀的航跡糾纏去除方法是利用下采樣或航跡壓縮的方式,通過減少航跡點數(shù)量實現(xiàn)糾纏點的去除。 艾佳琪[8]、盛畔[9]、張樹凱等[10]、Zhang 等[11]以及Sang 等[12]學(xué)者們均采用此類方式消除AIS 異常定位點。 上述方法實用性強、復(fù)雜度較低,但都無法避免在處理過程中會去除一些非糾纏點,致使存在丟失船舶重要運動特征信息的風險,同時采樣間隔設(shè)定一般無法達到全局最優(yōu),使得無法有效對糾纏進行完全去除。

基于閾值篩選的航跡糾纏去除方法是通過設(shè)定不同異常閾值去除糾纏點以及其他噪聲點。 吳建華等[13]、劉磊等[14]、衛(wèi)桂榮等[15]以及聶陽等[16]學(xué)者們根據(jù)AIS 數(shù)據(jù)特性制定了多種數(shù)據(jù)清洗規(guī)則,實現(xiàn)航跡異常點的篩選與去除。 此類方法較為方便、易操作,但只能去除一些明顯的異常定位點[6],且閾值的設(shè)定不具備普適性和自適應(yīng)性,去糾纏的漏警率和虛警率都很難同時取得較好的效果。

基于神經(jīng)網(wǎng)絡(luò)的航跡糾纏去除方法是利用神經(jīng)網(wǎng)絡(luò),以航跡糾纏樣本訓(xùn)練網(wǎng)絡(luò),自動識別糾纏并進行剔除。 王永明[6]提出了基于BP 神經(jīng)網(wǎng)絡(luò)的異常AIS 數(shù)據(jù)甄別方法,較前2 種方法具有較高的去糾纏準確性,但需要較為完備以及豐富的訓(xùn)練樣本集,較為復(fù)雜且具有參數(shù)和訓(xùn)練樣本依賴,在實際業(yè)務(wù)中實用性不強。

綜上分析,上述方法在一定程度上可以解決航跡糾纏的問題,但無法兼顧船舶軌跡去糾纏的有效性與業(yè)務(wù)實用性。 基于此,本文通過分析AIS 定位數(shù)據(jù)特性,在考慮運動約束、時空跨度以及定位誤差的情況下,提出基于運動屬性約束的船舶AIS 航跡去糾纏方法(A Method for Removing Entanglement of AIS Trajectory Based on the Constraints of Motion Attributes,CoMA),在保障損失最少航跡點的前提下,高效、簡便去除船舶軌跡糾纏,實現(xiàn)兼顧保留船舶運動行為特征以及業(yè)務(wù)實用性的船舶軌跡處理,彌補現(xiàn)有方法在船舶軌跡去糾纏中存在的系列問題。

1 方法介紹

1.1 船舶航跡糾纏示例

按照AIS 原始定位數(shù)據(jù)進行時序的連接后,由于數(shù)據(jù)上報機制以及其他原因,原始航跡會出現(xiàn)較為明顯的離群點、錯誤點等噪聲,同時也會產(chǎn)生航跡糾纏的問題。 圖1 所示為原始AIS 航跡Tra-A,其在靠近港口的多個位置(圖中I,II,III 處)均出現(xiàn)了航跡糾纏現(xiàn)象。

圖1 船舶航跡糾纏示意Fig.1 Schematic diagram of ship trajectory entanglement

以II 處的航跡糾纏為例,從圖1 中可以看出,該處航跡在P2,P3 和P4 處發(fā)生了糾纏,即正常航行情況下移動目標的航跡點順序應(yīng)為P1 →P3 →P4→P2→P5,但原始航跡數(shù)據(jù)中航跡點的順序為P1→P2→P3→P4→P5,在P2 和P3,P4 之間出現(xiàn)了異常。 表1 給出了II 處部分連續(xù)航跡點記錄(包含時 間、 航 向、 航 速(SOG)、 經(jīng) 度(LON) 和 緯 度(LAT))。 從表1 中可以看出,該目標在第2 組數(shù)據(jù)中的航向穩(wěn)定在138°左右,正常情況下AIS 數(shù)據(jù)中的LON 將逐漸減小,LAT 將逐漸增加。 然而,對比表1中的經(jīng)緯度發(fā)現(xiàn),航跡點(118°6. 335′E,24°23.883′N)出現(xiàn)了LON 增加而LAT 減小的現(xiàn)象,這也是航跡糾纏的典型運動屬性變化特點。

表1 Tra-A 航跡糾纏部分航跡點記錄表(部分)Tab.1 Record of partial trajectory entanglement points in Tra-A (part)

1.2 算法設(shè)計

為有效解決上述航跡糾纏問題,本文提出CoMA 方法,其主要包含3 個核心步驟:① 原始AIS數(shù)據(jù)預(yù)處理。 基于原始的已解碼AIS 定位數(shù)據(jù),按照時間前后順序提取原始船舶航跡,并采用時間間隔與航速約為0 對航跡分割點進行確定,得到原始船舶航跡數(shù)據(jù)集。 ② 基于航速約束的糾纏點去除。以原始船舶航跡集中每一條航跡為處理對象,以實時航行速度確定的最大航行距離為約束,對糾纏點進行篩查識別,去除由于定位偏差造成的航跡糾纏點。 ③ 基于航向約束的糾纏點去除。 將經(jīng)過上述處理的航跡點進一步在航行轉(zhuǎn)向上進行約束,去除由于AIS 設(shè)備時序解譯誤差造成的航跡糾纏點。 通過上述步驟的處理,實現(xiàn)對船舶航跡的徹底去糾纏。具體流程如圖2 所示。

圖2 CoMA 算法流程Fig.2 The algorithm flowchart of CoMA

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

原始的已解碼AIS 定位數(shù)據(jù)包含靜態(tài)數(shù)據(jù)、動態(tài)數(shù)據(jù)以及航程信息數(shù)據(jù)。 靜態(tài)數(shù)據(jù)主要記錄船舶的特定屬性信息,如船名、呼號、標識碼、船舶長度、船舶寬度和船舶類型等;動態(tài)數(shù)據(jù)主要記錄船舶在航行中的實時更新信息,如船舶經(jīng)緯度、實時時間、航向、航速、船舶類型和船首向等;航程信息數(shù)據(jù)主要記錄存在固定航線的行程信息,如吃水、目的地、船舶狀態(tài)和到港時間等。 船舶航跡的生成一般會采用動態(tài)數(shù)據(jù)進行時序的連接,并同時記錄船舶的實時更新信息,本文基于航速、航行狀態(tài)和航跡點位間隔時間進行航行軌跡的自動識別與提取,具體步驟為:

① 將原始AIS 記錄文件按照船舶唯一標識(MMSI)進行規(guī)整,查詢當前船舶所有航跡數(shù)據(jù)并按照時間序列進行排序;

② 按照MMSI 進行航跡點遍歷,直到找到航跡點Ti,其與上一航跡點Ti-1的時間間隔大于閾值θ1,且其行駛速度為0 或接近于0,標識Ti為航跡切分點;

③ 重復(fù)上述步驟,直到具有當前標識碼MMSI的航跡時間序列結(jié)束,找到若干切分點,按照時間先后將上述分割點重新標記為航跡的起點和終點,識別并提取原始航跡;

④ 重復(fù)上述步驟,直到全部MMSI 被遍歷,生成原始船舶航跡數(shù)據(jù)集。

上述步驟中涉及2 個閾值,其中時間間隔閾值θ1為自適應(yīng)確定,2 倍標準差是判斷異常值的常用方法之一[17-18],切分點處的時間間隔相對于常規(guī)軌跡點的時間采樣間隔一般較大,即存在異常,因此可根據(jù)當前船舶全部航跡點采樣間隔的2 倍標準差進行時間間隔閾值的確定,如式(1)所示:

式中,θ1為當前未被訪問MMSI 船舶航跡識別提取時間間隔閾值,共存在n個定位采樣間隔;Tm為其中任意一個采樣時間間隔值;Tave為全部航跡點采樣間隔平均值。

行駛速度“接近于0”可根據(jù)船舶航行規(guī)范中對船舶停泊入港以及錨泊等情況下船舶的航行速度的限制來進行判定,即當航速小于1 n mile/h 則認定為其為“接近于0”的狀態(tài)。 由上述給出的步驟可知,原始AIS 數(shù)據(jù)中的“航行狀態(tài)”并未加入約束中,這是由于AIS 原始數(shù)據(jù)此列屬性存在較多空缺值以及錯誤標記的情況,此屬性可作為以上2 種判斷條件的補充進行分割點識別的驗證,如航跡分割點一般應(yīng)對應(yīng)“錨泊”和“停泊”等狀態(tài)屬性。

1.2.2 基于航速約束的糾纏點去除

通過上述步驟獲取了原始船舶航跡,每個航跡點均記錄了當前時刻、經(jīng)緯度、航速和航向等信息,在此基礎(chǔ)上首先通過航速和時間間隔的約束對航跡糾纏點進行識別與去除。 設(shè)原始船舶航跡為Trai={p1,p2,…,pi,…,pn},在糾纏去除步驟中,默認每條目標船舶航跡第一個點p1和最后一個點pn為正常航跡點,pi為原始船舶航跡Trai的某未被訪問的航跡點,loni為其瞬時位置經(jīng)度,lati為其瞬時位置緯度,vi為其瞬時航速,hi為其瞬時航向,ti為其所處時刻。 基于航速約束的糾纏點去除步驟如下:

① 從i= 1 開始(即第一個未被訪問的航跡點),按照pi和pi+1中實時記錄瞬時航速的最大值Vmax(vi,vi+1)以及航跡點間的時間間隔Δt,計算最大航行距離dmax=Vmax×Δt;

② 按照兩航跡點pi和pi+1的經(jīng)緯度計算實際真實航行距離;

③ 計算最大航行距離dmax與實際真實航行距離dreal的比值,記為,判斷δ與預(yù)設(shè)閾值θ2的大小;

④ 若δ≤θ2,判斷當前第i+1 個航跡點是否為最后一個航跡點,若是則完成當前航跡的去糾纏處理,若不是則直接進行基于航向約束的糾纏點去除處理;

⑤ 若δ>θ2,則認為第i+1 個航跡點為航跡糾纏點,將其剔除,并判斷當前第i+1 個航跡點是否為最后一個航跡點,若是則完成當前航跡的去糾纏處理,若不是則將第i+2 個航跡點替代為第i+1 個航跡點,重復(fù)上述步驟;

⑥ 重復(fù)步驟①~⑤,初步得到基于航速約束糾纏點去除處理后的航跡。

上述步驟中涉及1 個預(yù)設(shè)閾值θ2,即用于衡量實際航行距離的合理與否。 經(jīng)過大量的實驗驗證以及航運專家知識,規(guī)定在一般航運條件下預(yù)設(shè)閾值θ2取值為0.2 較為合理。

1.2.3 基于航向約束的糾纏點去除

在基于航速約束的糾纏點去除后,能夠同時剔除傳統(tǒng)航跡預(yù)處理工作中存在的較明顯的空間離群點,并解決了由于定位偏差造成的小范圍內(nèi)密集航跡點區(qū)域的糾纏情況。 但由于時序誤差造成的航跡糾纏點無法只基于航速約束進行剔除,尤其是在保持較高航速的狀態(tài)下,因此還需要再基于航向約束對糾纏點進行進一步的識別與剔除。 以通過上述步驟處理后的航跡點pi及后續(xù)航跡點為輸入,基于航向約束的糾纏點去除步驟如下:

① 基于pi及pi+1的瞬時位置經(jīng)緯度,按照如下公式計算船舶實際航向Hi,i+1;

② 計算pi及pi+1的瞬時航向hi和hi+1的差值;

③ 當Δh>180 時,判斷船舶實際航向Hi,i+1是否不小于pi及pi+1的瞬時航向中較大值,或者不大于pi及pi+1的瞬時航向中較小值,即Hi,i+1≥max(hi,hi+1)或Hi,i+1≤min(hi,hi+1)是否成立;

④ 當Δh≤180 時,判斷船舶實際航向Hi,i+1是否在pi及pi+1的瞬時航向范圍之內(nèi),即min(hi,hi+1)≤Hi,i+1≤max(hi,hi+1)是否成立;

⑤ 若上述航向約束成立,判斷當前第i+1 個航跡點是否為最后一個航跡點,若是則完成航跡的全部去糾纏處理,若不是則繼續(xù)從第i+1 個航跡點開始重復(fù)上述操作;

⑥ 若上述航向約束不成立,則認為第i+1 個航跡點為航跡糾纏點,將其剔除,并判斷當前第i+1 個航跡點是否為最后一個航跡點,若是則完成航跡的全部去糾纏處理,若不是則將第i+2 個航跡點替代為第i+1 個航跡點,重復(fù)上述步驟;

⑦ 重復(fù)步驟①~⑥,直到全部航跡點被訪問,完成當前原始航跡Trai的去糾纏處理。

全部原始航跡按照前述步驟進行處理后,最終得到去糾纏后的航跡數(shù)據(jù)集合,可為后續(xù)船舶運動行為及模式深入分析提供準確的數(shù)據(jù)基礎(chǔ)。

2 算法實例驗證

為了驗證CoMA 方法在航跡去糾纏方面的有效性和優(yōu)勢性,基于真實的南海區(qū)域船舶AIS 定位數(shù)據(jù)以及模擬航跡數(shù)據(jù),從定性和定量2 個方面驗證CoMA 方法的有效性;并采用傳統(tǒng)的航跡抽稀、航跡壓縮方法以及擴展卡爾曼濾波方法與CoMA 方法進行對比,驗證CoMA 方法的優(yōu)勢性。

2.1 實驗數(shù)據(jù)介紹

實驗數(shù)據(jù)首先選取我國東南沿海區(qū)域(107°E~123°E,5°N~26°N)中多類型船舶的歷史AIS 數(shù)據(jù),來源于中國 AIS 岸基網(wǎng)絡(luò)的存檔報文記錄,時間范圍是2017 年12 月—2020 年12 月,由于船舶航跡糾纏一般發(fā)生在靠近大陸以及港口區(qū)域,因此將在上述區(qū)域通過數(shù)據(jù)預(yù)處理步驟后,隨機篩選50 條原始船舶航跡作為實例數(shù)據(jù)放入實驗數(shù)據(jù)集合中。 同時,為了更精準地驗證CoMA 方法的去糾纏能力,本文通過空間和時間屬性上進行加噪處理模擬生成100 條存在糾纏點的原始船舶航跡作為模擬數(shù)據(jù)放入實驗數(shù)據(jù)集合中。

為了測試不同采樣間隔以及航跡長度等因素對CoMA 方法在航跡去糾纏方面的處理效果影響,按照不同處理方式,將前述包含150 條原始航跡的實驗數(shù)據(jù)集合劃分為2 類共計6 組測試數(shù)據(jù)集,如表2和表3 所示。 表2 給出3 組在相同原始航跡長度條件的不同時間采樣間隔的數(shù)據(jù)集,用于測試CoMA方法在不同采樣間隔影響下的航跡去糾纏處理效果;表3 給出3 組在相同時間采樣間隔條件下的不同航跡長度的數(shù)據(jù)集,用于測試CoMA 方法在航跡長度影響下的航跡去糾纏效果。

表2 不同時間采樣間隔實驗航跡數(shù)據(jù)分組情況Tab.2 Test trajectory data grouping under different time sampling intervals

表3 不同空間長度實驗航跡數(shù)據(jù)分組情況Tab.3 Test trajectory data grouping under different spatial scales

2.2 方法驗證

首先采用定性方法對CoMA 方法進行驗證,選取圖1 所示具有多處糾纏的實際船舶航跡Tra-A 進行去糾纏處理(其也是實例數(shù)據(jù)中的一條原始航跡),處理結(jié)果如圖3 所示。 由圖中處理結(jié)果可以看出,在區(qū)域II 中,P2 被識別為糾纏點并剔除,并按照原始P1→P3→P4→P5 的時序?qū)υ己桔E進行記錄,實現(xiàn)了航跡的去糾纏。 同樣,在區(qū)域I 和區(qū)域III處的糾纏也得到了較好的處理。 由此可得,CoMA方法可在保證航行整體趨勢不變以及運動特征結(jié)構(gòu)最大程度保留的情況下,通過船速、航向等運動屬性的雙重約束剔除最少的糾纏點完成航跡的去糾纏處理,由此證明CoMA 方法的有效性。

圖3 Tra-A 去糾纏處理結(jié)果Fig.3 Processing result of removing entanglement for Tra-A

其次,基于實驗數(shù)據(jù)集合對CoMA 方法進行定量化驗證,采用航跡點損失率/糾纏去除虛警率(FAR)、糾纏去除準確率(TP)、糾纏去除漏警率(FNR)等作為評價指標進行驗證分析,各評價指標的計算如式(3) ~式(5)所示。 上述指標均針對某一航跡進行評價,因此6 組實驗數(shù)據(jù)集合采用每組的平均值進行驗證,得出在不同條件下CoMA 方法的處理效果對比結(jié)果。

式中,FAR表示航跡點損失率/糾纏去除虛警率;TP表示糾纏去除準確率;FNP表示糾纏去除漏警率;E′表示測試樣本實際為糾纏點,且測試結(jié)果也是糾纏點的航跡點數(shù)量;E″表示測試樣本實際為非糾纏點,且測試結(jié)果是糾纏點的航跡點數(shù)量;Ew表示測試樣本中的全部實際糾纏點;P′表示測試樣本實際為非糾纏點,且測試結(jié)果也是非糾纏點的航跡點數(shù)量;P表示測試樣本全部航跡點數(shù)量。

基于上述評價指標,CoMA 方法在6 組實驗數(shù)據(jù)集上的驗證結(jié)果如表4 所示。 由驗證結(jié)果可知,各組平均糾纏去除準確率均超過95%,同時具有較小的航跡點損失率和漏警率,不僅證明了CoMA 方法的有效性和準確性,同時也表明CoMA 方法不受時間采樣間隔大小以及航跡長度的影響,在不同條件下均具有較好的魯棒性。

表4 CoMA 方法定量評價結(jié)果Tab.4 Quantitative evaluation results of the CoMA單位:%

2.3 方法對比分析

為了進一步驗證CoMA 方法的優(yōu)勢性,分別采用傳統(tǒng)的航跡抽稀(Thinning Algorithm,TA)、航跡壓縮方法(MDL)[19]以及擴展卡爾曼濾波方法(EKF)[20]與其進行對比。 首先選取圖1 所示具有多處糾纏的實際船舶航跡Tra-A 進行定性對比,上述3 種方法的處理結(jié)果如圖4 所示(只詳細展示了Tra-A 區(qū)域III 的處理結(jié)果進行去糾纏效果的直觀對比),由圖4 和圖3 的處理結(jié)果對比可知,本文提出的CoMA 方法在去糾纏效果上明顯好于3 種傳統(tǒng)方法。

圖4 Tra-A 區(qū)域III 傳統(tǒng)方法去糾纏處理結(jié)果Fig.4 Processing result of removing entanglement for Tra-A region III from traditional methods

再次選取在前述定量化驗證實驗過程中CoMA方法表現(xiàn)相對較差的實驗組進行定量化對比實驗,即在不同時間采樣間隔實驗航跡數(shù)據(jù)組中選取L2,在不同空間長度實驗航跡數(shù)據(jù)組中選擇L5,各方法的定量化評價指標結(jié)果如表5 所示。

表5 不同條件下多方法處理效果對比Tab.5 Comparison of processing effects of multiple methods under different conditions單位:%

由表5 可得,在不同條件下CoMA 方法的去糾纏處理效果均好于其他3 種方法。 TA 和MDL 的去糾纏原理是減少航跡采樣密度達到去除異常點的目的,然而這會造成在去除糾纏點的同時將其他非糾纏點去除,從表中可以看出,上述2 種方法的FAR值均較高,利用這2 種方法進行航跡的處理會丟失部分關(guān)鍵船舶運動特征信息,不利于后續(xù)的深入分析;EKF 方法相較于前2 種傳統(tǒng)處理方法而言,在去糾纏準確率上表現(xiàn)更好,但由于其在處理過程中會存在計算成本過高的問題,同時由于其基本原理是對線性過程的近似與逼近,致使其在FNR 上表現(xiàn)較差。 通過上述對比實驗,表明CoMA 方法相較于傳統(tǒng)處理方法而言,具有更全面的去糾纏能力,能夠在糾纏點徹底、精準、高效去除前提下,減少對非糾纏點的損失,從而最大程度地保留船舶運動行為特征,可為后續(xù)船舶運行等深入分析提供準確輸入。

3 結(jié)論

本文面向AIS 船舶原始航跡存在的糾纏問題,基于船舶運動特征以及時空統(tǒng)計的基本思想,提出基于運動屬性約束的船舶AIS 航跡去糾纏方法,以實時航行速度和時間間隔約束船舶空間位置合理范圍,以實時航向約束船舶轉(zhuǎn)向的合理區(qū)間,雙重約束下對航跡糾纏點進行去除。 通過實驗驗證以及與經(jīng)典航跡預(yù)處理方法的對比得出,本文所提出的基于運動屬性約束的船舶AIS 航跡去糾纏方法不受航跡長度以及采樣間隔的影響,能夠更好地實現(xiàn)在不損失船舶運動行為特征的前提下的航跡去糾纏。

雖然本文提出的航跡去糾纏方法能夠保證較為高效和準確的航跡處理,但在處理過程中仍涉及人為設(shè)定閾值的問題,在后續(xù)工作中可在現(xiàn)有方法基礎(chǔ)上發(fā)展參數(shù)自適應(yīng)的航跡去糾纏策略,進一步提升原始AIS 航跡處理的有效性和實用性,更好地支撐海上航運智能分析等服務(wù)。