張 煜 張 鑠 馬 杰

（1.武漢理工大學(xué)物流工程學(xué)院 武漢 430063；2.武漢理工大學(xué)航運學(xué)院 武漢 430063；3.武漢理工大學(xué)國家水運安全工程技術(shù)研究中心 武漢 430063）

0 引 言

船舶自動識別系統(tǒng)（Automatic Identification System，AIS）已成為當前船舶助導(dǎo)航系統(tǒng)的標準配置。AIS記錄的船舶軌跡信息是開展水上交通研究的重要數(shù)據(jù)源，在航線規(guī)劃、交通監(jiān)控、船舶避碰等領(lǐng)域都發(fā)揮了重要作用[1-3]。這些研究的實施都高度依賴AIS軌跡數(shù)據(jù)的質(zhì)量。

AIS中的船舶定位信息（經(jīng)緯度）主要由GPS系統(tǒng)提供，非常容易受到環(huán)境空間的干擾。此外，不同海況環(huán)境下，AIS信號的多徑信號成分和傳輸損耗均會影響數(shù)據(jù)傳輸質(zhì)量[4]，造成采集獲取的船舶AIS軌跡數(shù)據(jù)與船舶實際位置及航跡存在偏差。這些不能正確反映船舶位置的軌跡點稱為噪聲點，對開展交通流和交通行為研究產(chǎn)生了無法忽略的影響。H.A.Mokhtari等[5]分析AIS數(shù)據(jù)的定位誤差，發(fā)現(xiàn)有30%的軌跡數(shù)據(jù)中存在噪聲點。一些失真較大的噪聲點對軌跡重建[6]的干擾極大，導(dǎo)致重建結(jié)果與實際船舶軌跡相差很大，嚴重影響軌跡分析與挖掘的質(zhì)量。通過軌跡去噪，能大幅地減少噪聲點，提高軌跡數(shù)據(jù)的質(zhì)量。因此，對軌跡噪聲去除的研究具有重要的理論意義和實用價值。

已有許多學(xué)者針對軌跡噪聲去除方法進行了深入研究。Ying等[7]引入時空鄰域中的最小邊界框重疊量來表示軌跡相似度，然后使用基于密度的聚類算法DBSCAN（density-based spatial clustering of applications with noise）去除軌跡噪聲。Qu等[8]提出速度閾值法，利用位置記錄和船舶的加減速能力來檢查速度記錄是否在合理范圍內(nèi)。S.Ando等[9]提出異常聚類集成框架，基于目標和輔助數(shù)據(jù)之間的相對密度的近似值，通過元特征聚類，實現(xiàn)了有效的異常檢測。林明亮[10]提出平均速度監(jiān)督方法，通過比較量軌跡點間平均速度和速度閾值，檢測并刪除船舶軌跡的異常和漂移數(shù)據(jù)。Ruan等[11]在軌跡分割的過程中利用速度閾值法去除噪聲，提出一種基于并行計算的軌跡預(yù)處理框架。BAO等[12]應(yīng)用DBSCAN從原始軌跡中提取正常點的特征，利用提取特征與待處理軌跡的特征間的相似程度識別噪聲點。WANG等[13]設(shè)計了基于差異和相交集距離的異常軌跡檢測方法，通過計算軌跡的異常值，并根據(jù)閾值確定是否為異常軌跡。

目前，常見的軌跡噪聲去除方法主要有速度閾值法和密度聚類法。上述2類方法根據(jù)軌跡形態(tài)，人為設(shè)定速度閾值或密度閾值來判斷1個點或片段與整體軌跡的從屬關(guān)系來判別噪聲數(shù)據(jù)。這類方法雖然較為簡單直觀，但沒有考慮船舶運動特性，對軌跡點連續(xù)偏離實際運動路線（即軌跡漂移現(xiàn)象）的處理能力有限，容易產(chǎn)生誤判的情況?；诖?，在考慮噪聲點分布特征情況下，綜合船舶運動學(xué)，引入狀態(tài)可達域的概念，提出一種軌跡去噪算法，解決復(fù)雜情況下的噪聲去除問題。

圖1 復(fù)雜噪聲分布示例Fig.1 Example of complex noise distribution

1 問題描述

由于受到多源干擾，AIS定位數(shù)據(jù)中的噪聲呈現(xiàn)不同的分布特征[14]。1種常見的特征是分布零散的噪聲尖點。見圖1（a）所示，軌跡單點明顯偏離運動路線成為噪聲點。這種類型的噪聲點隨機出現(xiàn)在軌跡的任意位置，分解到每一個位置分現(xiàn)象中，具有正常點形態(tài)相似的噪聲點，傳統(tǒng)噪聲去除算法會把這類軌跡點誤判成正常點。表1為所測變量及參數(shù)意義。

表1 相關(guān)變量及參數(shù)定義Tab.1 Related variables and parameter definitions

量的時域上，見圖1（c）和圖1（d），噪聲點處曲線出現(xiàn)跳躍的尖點。除上述噪聲特征外，另一類特征是軌跡片段漂移：從圖1（a）可看出，軌跡數(shù)據(jù)中存在3段航向明顯變化的軌跡片段，分別是始末2小段疑似偏航后回航的片段和中間段的偏航片段。但根據(jù)圖1（b）和圖1（e），船舶角度變化幅度始終在 ±4°以內(nèi)，船舶速度變化幅度也在±3knot以內(nèi)，認為船舶以勻速直線行駛。3處片段的定位數(shù)據(jù)與分析得到的實際船舶運動不符，說明這3處片段的軌跡點連續(xù)偏離實際運動路線。這類噪聲點僅在軌跡部分片段處分布集中，分解到每一個位置分量的時域上，見圖1（c）和圖1（d），噪聲點處的曲線段呈現(xiàn)出明顯違背船舶運動的不規(guī)律變化。以上2種特征的噪聲點及其組合構(gòu)成軌跡噪聲分布的復(fù)雜情況。

事實上，軌跡噪聲問題的本質(zhì)是AIS定位數(shù)據(jù)與船舶實際運動不符，傳統(tǒng)的基于軌跡形態(tài)的噪聲去除方法僅從軌跡形態(tài)這一表象入手，去噪能力有限，尤其對軌跡片段漂移的處理效果不佳。主要原因有以下2點：①軌跡片段漂移的噪聲點分布密集，造成具有逐點迭代過程的算法失效。若某點為噪聲片段中的1點，以該點為基準點均無法準確判斷后續(xù)時刻點的情況，這是逐點迭代過程的初值敏感問題。②主觀擬定的速度閾值或聚類密度無法兼顧所有噪聲分布特征。通過圖1（a）的部分噪聲片段可以看出，軌跡漂移現(xiàn)象中，具有正常點形態(tài)相似的噪聲點，傳統(tǒng)噪聲去除算法會把這類軌跡點誤判成正常點。

2 位置可達域模型

自主運動對象表現(xiàn)出隨著交通環(huán)境變化不斷改變機動行為模式的離散動態(tài)行為特性，因此該運動對象是一個典型的混合系統(tǒng)，解決混合系統(tǒng)的不確定性問題的有效途徑是將其轉(zhuǎn)換為可達性判定問題[15]。給定運動對象的初始狀態(tài)和采樣間隔，通過運動學(xué)建模，計算對象可能采用的機動行為，得到對象在有限時間內(nèi)可到達位置的集合。該集合被稱為位置可達域[16]。

計算位置可達域時，常用歐氏距離表示2點之間的運動距離，以運動對象為中心形成的圓作為位置可達域[17]。但這種方法不適用于衡量船舶采樣點間的距離。事實上，由于船舶慣性大，導(dǎo)致其更改運動方向困難，2個相鄰點之間的距離往往是曲線的弧長，可達域的計算不僅受2采樣點位置的影響，還受航速和航向的影響。

因此，計算位置可達域需確定船舶的具體運動過程。見圖2所示，Mi和Ni為前后2個時刻的軌跡點。建立以Mi的運動方向為y軸正方向，Mi的坐標為原點的直角坐標系。考慮船舶向右轉(zhuǎn)向（向左轉(zhuǎn)向的情形與向右轉(zhuǎn)向的情形是對稱的），最后到達的運動過程。定義相對方位角θi為從Mi運動方向起，以順時針轉(zhuǎn)至Ni運動方向的夾角。根據(jù)是否更改方向，船舶運動有以下2個階段：①轉(zhuǎn)向運動：船舶更改運動方向，運動產(chǎn)生一段曲線；②保向運動：船舶不更改運動方向，沿原方向運動。

圖2 位置可達域Fig.2 Position reachable domain

在誤差允許的前提下簡化模型，提出如下假設(shè)。

1）轉(zhuǎn)向運動中，認為船舶進入轉(zhuǎn)向運動時，就開始做圓周運動，圓弧與Mi處運動方向相切。結(jié)束轉(zhuǎn)向運動時，圓弧與Ni運動方向相切，以切向方向開始做保向運動，直至到達Ni。不考慮進入穩(wěn)定回轉(zhuǎn)前的初始運動曲線。

2）轉(zhuǎn)向運動中，相對方位角?的極限取值范圍為[0，2π]，最小回轉(zhuǎn)半徑為rmin。

3）轉(zhuǎn)向運動中，線速度大小保持不變；保向運動中，速度大小可能變化。

基于上述假設(shè)，在有限時間τ內(nèi)，船舶的2個階段的具體運動如下：①回轉(zhuǎn)運動，船舶以恒定線速度v1，經(jīng)轉(zhuǎn)向運動行至Gi，時間為τ1。其中為以線速度v1繞回轉(zhuǎn)圓1周的時間；②保向運動，船舶經(jīng)保向運動行至Ni，時間為τ2，τ2=τ-τ1>0，保向運動長度。

通過運動學(xué)關(guān)系和幾何約束，可以計算Mi的位置可達域。首先確定從Mi出發(fā)的轉(zhuǎn)向運動模式，分別計算回轉(zhuǎn)圓半徑r和回轉(zhuǎn)角?的取值范圍。

根據(jù)Mi和Ni的坐標和保向運動的直線斜率k可以得到r的取值，見式（1）。根據(jù)假設(shè)和幾何關(guān)系，當yN>0時，k的取值范圍為。當yN＜0時，有以下2種情況：①當2rmin>xN時，k的取值范圍為；②當 2rmin＜xN時，k的取值范圍為。只有當k在上述取值范圍內(nèi)時，軌跡有實際意義，k1和k2的具體計算見式（2）和式（3）。

式中：h=rmin-xN。計算回轉(zhuǎn)角?的取值范圍。見圖2所示，回轉(zhuǎn)角θ?的取值范圍為。當時，船舶僅進行保向運動；當時，船舶具有轉(zhuǎn)向運動和保向運動2個過程；當時，船舶僅進行轉(zhuǎn)向運動。

然后確定從Mi出發(fā)的保向運動模式，計算保向運動距離的取值范圍。由于保向運動的速度v2不為常數(shù)，且與進入保向運動的速度v1和船舶的加速度a的取值范圍有關(guān)。按勻加速直線運動的定義，根據(jù)式4，分別取a=amin和a=amax，可以計算出保向運動的速度取值范圍

2邊對τ2積分，分別取a=amin和a=amax計算的取值范圍，計算見式（5）。

所有的構(gòu)成右位置可達域。見圖 2 所示，當，不同取值的?對應(yīng)位置可達點，構(gòu)成曲線 Γ1；當時，不同取值的?對應(yīng)位置可達點，構(gòu)成曲線Γ2。2曲線與y軸組成的封閉圖形（陰影部分），構(gòu)成Mi點在時間τ內(nèi)的右位置可達域（左位置可達域SL與右位置可達域SR關(guān)于y軸對稱）。

通過Mi的位置可達域S=SL∪SR，可以判定Ni的可達性。見圖2所示，Ni落在該可達區(qū)域外，即Ni?S，則判定Ni不可達。

3 基于位置可達域的噪聲去除算法

根據(jù)馬爾可夫鏈[18]，不管先前的狀態(tài)如何，船舶未來狀態(tài)僅與當前狀態(tài)有關(guān)。因此，可以根據(jù)前一時刻的點的位置確定后續(xù)點的可達區(qū)域，通過逐點依次判斷軌跡點的可達性來濾除噪聲。利用位置可達域的性質(zhì)，設(shè)計基于位置可達域的噪聲去除算法（position reachable domain-based trajectory noise reduction，PRDBTNR），算法的流程見圖3。其中，軌跡數(shù)據(jù)表示為有序元組。。其中：ti為第i個軌跡點的時間；Pi為第i點的空間狀態(tài)，包含經(jīng)度、緯度、對地航速和對地航向。

圖3 PRDBTNR主要流程Fig.3 Main process of PRDBTNR

計算轉(zhuǎn)向運動和保向運動的參數(shù)，初步判斷Ni的可達性。建立Mi與Ni的坐標系。根據(jù)Ni點的坐標和最小回轉(zhuǎn)半徑rmin，確定k的取值范圍。若k的取值落在該范圍內(nèi)，則軌跡有實際意義，令ζ=True并根據(jù)第3節(jié)的方法算出回轉(zhuǎn)圓半徑r和保向運動的長度L；反之，軌跡無實際意義，令ζ=False，直接判定Ni不可達并跳過后續(xù)計算。根據(jù)采樣間隔τ、Mi的速度v1和回轉(zhuǎn)圓半徑r求得θ?的取值范圍。比較θ與的大小，有如下2種情況。

4 實驗設(shè)計與結(jié)果分析

4.1 評價指標

為衡量不同算法的去噪效果，選用如下的評價指標作為一級指標：ntp是算法判斷為噪聲，且實際為噪聲的點的數(shù)量；nfn是算法判斷為非噪聲，且實際為噪聲的點的數(shù)量；nfp是算法判斷為噪聲，且實際為非噪聲的點的數(shù)量。

由上述一級指標構(gòu)成以下二級指標。

1）精確率δpre，表征算法識別噪聲點的正確程度。該值越高，表明算法識別的噪聲點中，識別正確的噪聲點越多。

2）召回率?rec，表征算法識別噪聲點的完備程度。該值越高，表明算法能夠從樣本中識別出的更多的噪聲點。

3）F1，綜合考慮δpre和?rec的指標。

4.2 實驗結(jié)果分析

實驗選用在長江口南槽交匯水域航行的中型貨船AIS數(shù)據(jù)集，選取10個在多源干擾下，具有的復(fù)雜噪聲點分布的軌跡樣本。其中，樣本的最小采樣周期為2 s。PRDBTNR算法的輸入?yún)?shù)按照中型貨船的運動情況[19-21]，對參數(shù)設(shè)置適當?shù)脑６龋员阌谒惴▽ν惔斑M行處理，具體取值見表2。

表2PRDBTNR參數(shù)設(shè)置Tab.2 Parameter settings of PRDBTNR

分別采用速度閾值法[8]，DBSCAN[12]和PRDBTNR進行處理。記錄每個實驗的處理指標，得到如表3的處理結(jié)果。每個實驗評價指標的最高值被加粗標出。從結(jié)果可以明顯看出，速度閾值法的綜合指標F1值低于92%，δpre值較高，但?rec值保持低于85%的水平；DBSCAN的處理結(jié)果的各項指標存在波動，原因是受到軌跡形態(tài)和噪聲分布的綜合影響。圖4展示圖1（a）示例的去噪結(jié)果，2種算法均去除所有零散的噪聲點，但對軌跡片段漂移的處理效果不佳。見圖4（a）和圖4（b），對第2段中大于速度閾值或分布密度較低的噪聲點，2種算法的去噪結(jié)果較好；然而對小于速度閾值或軌跡漂移噪聲，2種算法的去噪效果均不理想，未識別如第1，3段和第2段起始的分布密度較高的噪聲點，甚至將這種類型的噪聲點識別為軌跡片段的一部分。

圖4 樣例去噪結(jié)果對比Fig.4 Comparison of denoising result

表3 實驗評價結(jié)果Tab.3 Results of the experimental evaluation

與上述算法不同，PRDBTNR能夠適用于各種分布特征的噪聲點，尤其能夠妥善處理軌跡片段漂移類型的噪聲點。結(jié)合表3的結(jié)果，對于每一個實驗而言，PRDBTNR保證綜合指標F1均高于94%的同時，使各分項指標?rec和δpre均高于90%。從10條軌跡實驗的均值上對比其他2個方法，PRDBTNR的綜合評價指標F1比速度閾值法和DBSCAN分別高出14.31%和24.03%。從圖4（c）的軌跡可視化結(jié)果上看，無論是分布零散的噪聲尖點，還是軌跡片段漂移類型的噪聲點，PRDBTNR算法都能進行有效識別。噪聲被盡數(shù)去除，船舶軌跡被還原成1條直線。

4.3 時間復(fù)雜度分析

設(shè)計實驗對比各個算法的運算速度，通過處理含不同數(shù)量軌跡點的片段，記錄算法運行耗時，結(jié)合算法時間復(fù)雜度進行分析。見圖5所示，隨著軌跡點數(shù)量增大，算法間出現(xiàn)明顯的差異：①速度閾值法的時間復(fù)雜度為O(n)，實際計算實驗中平均運算耗時最??；②DBSCAN理論上的最差時間復(fù)雜度為O(n2)。實際計算實驗中，隨著軌跡點的數(shù)量增大，計算耗時迅速增長且遠高于其他2種算法；③PRDBTNR的最差時間復(fù)雜度為為常數(shù)，具體取值見第3節(jié)。理論上，PRDBTNR是與速度閾值法同數(shù)量級的算法。實際計算實驗中PRDBTNR的平均計算耗時也介于速度閾值和DBSCAN之間，且比較接近速度閾值法。從具體數(shù)值看，PRDBTNR計算1 000個軌跡點的平均耗時僅為0.2 s，不僅適用離線數(shù)據(jù)的去噪，也適用于運算實時性較高的在線去噪場合。

圖5 運算時間比較Fig.5 Comparison of operating time

5 結(jié)束語

針對船舶AIS軌跡數(shù)據(jù)噪聲去除問題，綜合多源干擾下的不同噪聲分布特征，提出基于船舶運動規(guī)律的位置可達域模型。同時，構(gòu)建含滑窗機制的算法解決逐點迭代過程的初值敏感問題。選用含噪AIS軌跡數(shù)據(jù)，驗證模型與算法的有效性。相比基于軌跡形態(tài)的噪聲去除方法，基于位置可達域的噪聲去除方法能夠結(jié)合運動學(xué)模型準確識別并去除具有各種分布特征的噪聲。算法的時間復(fù)雜度低，計算速度快，能夠滿足不同數(shù)據(jù)處理場景的需求。后續(xù)將使用該方法，針對在線去噪的實際應(yīng)用場景展開研究。