張 煜 張 鑠 馬 杰
(1.武漢理工大學(xué)物流工程學(xué)院 武漢 430063;2.武漢理工大學(xué)航運(yùn)學(xué)院 武漢 430063;3.武漢理工大學(xué)國(guó)家水運(yùn)安全工程技術(shù)研究中心 武漢 430063)
船舶自動(dòng)識(shí)別系統(tǒng)(Automatic Identification System,AIS)已成為當(dāng)前船舶助導(dǎo)航系統(tǒng)的標(biāo)準(zhǔn)配置。AIS記錄的船舶軌跡信息是開(kāi)展水上交通研究的重要數(shù)據(jù)源,在航線規(guī)劃、交通監(jiān)控、船舶避碰等領(lǐng)域都發(fā)揮了重要作用[1-3]。這些研究的實(shí)施都高度依賴AIS軌跡數(shù)據(jù)的質(zhì)量。
AIS中的船舶定位信息(經(jīng)緯度)主要由GPS系統(tǒng)提供,非常容易受到環(huán)境空間的干擾。此外,不同海況環(huán)境下,AIS信號(hào)的多徑信號(hào)成分和傳輸損耗均會(huì)影響數(shù)據(jù)傳輸質(zhì)量[4],造成采集獲取的船舶AIS軌跡數(shù)據(jù)與船舶實(shí)際位置及航跡存在偏差。這些不能正確反映船舶位置的軌跡點(diǎn)稱為噪聲點(diǎn),對(duì)開(kāi)展交通流和交通行為研究產(chǎn)生了無(wú)法忽略的影響。H.A.Mokhtari等[5]分析AIS數(shù)據(jù)的定位誤差,發(fā)現(xiàn)有30%的軌跡數(shù)據(jù)中存在噪聲點(diǎn)。一些失真較大的噪聲點(diǎn)對(duì)軌跡重建[6]的干擾極大,導(dǎo)致重建結(jié)果與實(shí)際船舶軌跡相差很大,嚴(yán)重影響軌跡分析與挖掘的質(zhì)量。通過(guò)軌跡去噪,能大幅地減少噪聲點(diǎn),提高軌跡數(shù)據(jù)的質(zhì)量。因此,對(duì)軌跡噪聲去除的研究具有重要的理論意義和實(shí)用價(jià)值。
已有許多學(xué)者針對(duì)軌跡噪聲去除方法進(jìn)行了深入研究。Ying等[7]引入時(shí)空鄰域中的最小邊界框重疊量來(lái)表示軌跡相似度,然后使用基于密度的聚類算法DBSCAN(density-based spatial clustering of applications with noise)去除軌跡噪聲。Qu等[8]提出速度閾值法,利用位置記錄和船舶的加減速能力來(lái)檢查速度記錄是否在合理范圍內(nèi)。S.Ando等[9]提出異常聚類集成框架,基于目標(biāo)和輔助數(shù)據(jù)之間的相對(duì)密度的近似值,通過(guò)元特征聚類,實(shí)現(xiàn)了有效的異常檢測(cè)。林明亮[10]提出平均速度監(jiān)督方法,通過(guò)比較量軌跡點(diǎn)間平均速度和速度閾值,檢測(cè)并刪除船舶軌跡的異常和漂移數(shù)據(jù)。Ruan等[11]在軌跡分割的過(guò)程中利用速度閾值法去除噪聲,提出一種基于并行計(jì)算的軌跡預(yù)處理框架。BAO等[12]應(yīng)用DBSCAN從原始軌跡中提取正常點(diǎn)的特征,利用提取特征與待處理軌跡的特征間的相似程度識(shí)別噪聲點(diǎn)。WANG等[13]設(shè)計(jì)了基于差異和相交集距離的異常軌跡檢測(cè)方法,通過(guò)計(jì)算軌跡的異常值,并根據(jù)閾值確定是否為異常軌跡。
目前,常見(jiàn)的軌跡噪聲去除方法主要有速度閾值法和密度聚類法。上述2類方法根據(jù)軌跡形態(tài),人為設(shè)定速度閾值或密度閾值來(lái)判斷1個(gè)點(diǎn)或片段與整體軌跡的從屬關(guān)系來(lái)判別噪聲數(shù)據(jù)。這類方法雖然較為簡(jiǎn)單直觀,但沒(méi)有考慮船舶運(yùn)動(dòng)特性,對(duì)軌跡點(diǎn)連續(xù)偏離實(shí)際運(yùn)動(dòng)路線(即軌跡漂移現(xiàn)象)的處理能力有限,容易產(chǎn)生誤判的情況。基于此,在考慮噪聲點(diǎn)分布特征情況下,綜合船舶運(yùn)動(dòng)學(xué),引入狀態(tài)可達(dá)域的概念,提出一種軌跡去噪算法,解決復(fù)雜情況下的噪聲去除問(wèn)題。
圖1 復(fù)雜噪聲分布示例Fig.1 Example of complex noise distribution
由于受到多源干擾,AIS定位數(shù)據(jù)中的噪聲呈現(xiàn)不同的分布特征[14]。1種常見(jiàn)的特征是分布零散的噪聲尖點(diǎn)。見(jiàn)圖1(a)所示,軌跡單點(diǎn)明顯偏離運(yùn)動(dòng)路線成為噪聲點(diǎn)。這種類型的噪聲點(diǎn)隨機(jī)出現(xiàn)在軌跡的任意位置,分解到每一個(gè)位置分現(xiàn)象中,具有正常點(diǎn)形態(tài)相似的噪聲點(diǎn),傳統(tǒng)噪聲去除算法會(huì)把這類軌跡點(diǎn)誤判成正常點(diǎn)。表1為所測(cè)變量及參數(shù)意義。
表1 相關(guān)變量及參數(shù)定義Tab.1 Related variables and parameter definitions
量的時(shí)域上,見(jiàn)圖1(c)和圖1(d),噪聲點(diǎn)處曲線出現(xiàn)跳躍的尖點(diǎn)。除上述噪聲特征外,另一類特征是軌跡片段漂移:從圖1(a)可看出,軌跡數(shù)據(jù)中存在3段航向明顯變化的軌跡片段,分別是始末2小段疑似偏航后回航的片段和中間段的偏航片段。但根據(jù)圖1(b)和圖1(e),船舶角度變化幅度始終在 ±4°以內(nèi),船舶速度變化幅度也在±3knot以內(nèi),認(rèn)為船舶以勻速直線行駛。3處片段的定位數(shù)據(jù)與分析得到的實(shí)際船舶運(yùn)動(dòng)不符,說(shuō)明這3處片段的軌跡點(diǎn)連續(xù)偏離實(shí)際運(yùn)動(dòng)路線。這類噪聲點(diǎn)僅在軌跡部分片段處分布集中,分解到每一個(gè)位置分量的時(shí)域上,見(jiàn)圖1(c)和圖1(d),噪聲點(diǎn)處的曲線段呈現(xiàn)出明顯違背船舶運(yùn)動(dòng)的不規(guī)律變化。以上2種特征的噪聲點(diǎn)及其組合構(gòu)成軌跡噪聲分布的復(fù)雜情況。
事實(shí)上,軌跡噪聲問(wèn)題的本質(zhì)是AIS定位數(shù)據(jù)與船舶實(shí)際運(yùn)動(dòng)不符,傳統(tǒng)的基于軌跡形態(tài)的噪聲去除方法僅從軌跡形態(tài)這一表象入手,去噪能力有限,尤其對(duì)軌跡片段漂移的處理效果不佳。主要原因有以下2點(diǎn):①軌跡片段漂移的噪聲點(diǎn)分布密集,造成具有逐點(diǎn)迭代過(guò)程的算法失效。若某點(diǎn)為噪聲片段中的1點(diǎn),以該點(diǎn)為基準(zhǔn)點(diǎn)均無(wú)法準(zhǔn)確判斷后續(xù)時(shí)刻點(diǎn)的情況,這是逐點(diǎn)迭代過(guò)程的初值敏感問(wèn)題。②主觀擬定的速度閾值或聚類密度無(wú)法兼顧所有噪聲分布特征。通過(guò)圖1(a)的部分噪聲片段可以看出,軌跡漂移現(xiàn)象中,具有正常點(diǎn)形態(tài)相似的噪聲點(diǎn),傳統(tǒng)噪聲去除算法會(huì)把這類軌跡點(diǎn)誤判成正常點(diǎn)。
自主運(yùn)動(dòng)對(duì)象表現(xiàn)出隨著交通環(huán)境變化不斷改變機(jī)動(dòng)行為模式的離散動(dòng)態(tài)行為特性,因此該運(yùn)動(dòng)對(duì)象是一個(gè)典型的混合系統(tǒng),解決混合系統(tǒng)的不確定性問(wèn)題的有效途徑是將其轉(zhuǎn)換為可達(dá)性判定問(wèn)題[15]。給定運(yùn)動(dòng)對(duì)象的初始狀態(tài)和采樣間隔,通過(guò)運(yùn)動(dòng)學(xué)建模,計(jì)算對(duì)象可能采用的機(jī)動(dòng)行為,得到對(duì)象在有限時(shí)間內(nèi)可到達(dá)位置的集合。該集合被稱為位置可達(dá)域[16]。
計(jì)算位置可達(dá)域時(shí),常用歐氏距離表示2點(diǎn)之間的運(yùn)動(dòng)距離,以運(yùn)動(dòng)對(duì)象為中心形成的圓作為位置可達(dá)域[17]。但這種方法不適用于衡量船舶采樣點(diǎn)間的距離。事實(shí)上,由于船舶慣性大,導(dǎo)致其更改運(yùn)動(dòng)方向困難,2個(gè)相鄰點(diǎn)之間的距離往往是曲線的弧長(zhǎng),可達(dá)域的計(jì)算不僅受2采樣點(diǎn)位置的影響,還受航速和航向的影響。
因此,計(jì)算位置可達(dá)域需確定船舶的具體運(yùn)動(dòng)過(guò)程。見(jiàn)圖2所示,Mi和Ni為前后2個(gè)時(shí)刻的軌跡點(diǎn)。建立以Mi的運(yùn)動(dòng)方向?yàn)閥軸正方向,Mi的坐標(biāo)為原點(diǎn)的直角坐標(biāo)系??紤]船舶向右轉(zhuǎn)向(向左轉(zhuǎn)向的情形與向右轉(zhuǎn)向的情形是對(duì)稱的),最后到達(dá)的運(yùn)動(dòng)過(guò)程。定義相對(duì)方位角θi為從Mi運(yùn)動(dòng)方向起,以順時(shí)針轉(zhuǎn)至Ni運(yùn)動(dòng)方向的夾角。根據(jù)是否更改方向,船舶運(yùn)動(dòng)有以下2個(gè)階段:①轉(zhuǎn)向運(yùn)動(dòng):船舶更改運(yùn)動(dòng)方向,運(yùn)動(dòng)產(chǎn)生一段曲線;②保向運(yùn)動(dòng):船舶不更改運(yùn)動(dòng)方向,沿原方向運(yùn)動(dòng)。
圖2 位置可達(dá)域Fig.2 Position reachable domain
在誤差允許的前提下簡(jiǎn)化模型,提出如下假設(shè)。
1)轉(zhuǎn)向運(yùn)動(dòng)中,認(rèn)為船舶進(jìn)入轉(zhuǎn)向運(yùn)動(dòng)時(shí),就開(kāi)始做圓周運(yùn)動(dòng),圓弧與Mi處運(yùn)動(dòng)方向相切。結(jié)束轉(zhuǎn)向運(yùn)動(dòng)時(shí),圓弧與Ni運(yùn)動(dòng)方向相切,以切向方向開(kāi)始做保向運(yùn)動(dòng),直至到達(dá)Ni。不考慮進(jìn)入穩(wěn)定回轉(zhuǎn)前的初始運(yùn)動(dòng)曲線。
2)轉(zhuǎn)向運(yùn)動(dòng)中,相對(duì)方位角?的極限取值范圍為[0,2π],最小回轉(zhuǎn)半徑為rmin。
3)轉(zhuǎn)向運(yùn)動(dòng)中,線速度大小保持不變;保向運(yùn)動(dòng)中,速度大小可能變化。
基于上述假設(shè),在有限時(shí)間τ內(nèi),船舶的2個(gè)階段的具體運(yùn)動(dòng)如下:①回轉(zhuǎn)運(yùn)動(dòng),船舶以恒定線速度v1,經(jīng)轉(zhuǎn)向運(yùn)動(dòng)行至Gi,時(shí)間為τ1。其中為以線速度v1繞回轉(zhuǎn)圓1周的時(shí)間;②保向運(yùn)動(dòng),船舶經(jīng)保向運(yùn)動(dòng)行至Ni,時(shí)間為τ2,τ2=τ-τ1>0,保向運(yùn)動(dòng)長(zhǎng)度。
通過(guò)運(yùn)動(dòng)學(xué)關(guān)系和幾何約束,可以計(jì)算Mi的位置可達(dá)域。首先確定從Mi出發(fā)的轉(zhuǎn)向運(yùn)動(dòng)模式,分別計(jì)算回轉(zhuǎn)圓半徑r和回轉(zhuǎn)角?的取值范圍。
根據(jù)Mi和Ni的坐標(biāo)和保向運(yùn)動(dòng)的直線斜率k可以得到r的取值,見(jiàn)式(1)。根據(jù)假設(shè)和幾何關(guān)系,當(dāng)yN>0時(shí),k的取值范圍為。當(dāng)yN<0時(shí),有以下2種情況:①當(dāng)2rmin>xN時(shí),k的取值范圍為;②當(dāng) 2rmin<xN時(shí),k的取值范圍為。只有當(dāng)k在上述取值范圍內(nèi)時(shí),軌跡有實(shí)際意義,k1和k2的具體計(jì)算見(jiàn)式(2)和式(3)。
式中:h=rmin-xN。計(jì)算回轉(zhuǎn)角?的取值范圍。見(jiàn)圖2所示,回轉(zhuǎn)角θ?的取值范圍為。當(dāng)時(shí),船舶僅進(jìn)行保向運(yùn)動(dòng);當(dāng)時(shí),船舶具有轉(zhuǎn)向運(yùn)動(dòng)和保向運(yùn)動(dòng)2個(gè)過(guò)程;當(dāng)時(shí),船舶僅進(jìn)行轉(zhuǎn)向運(yùn)動(dòng)。
然后確定從Mi出發(fā)的保向運(yùn)動(dòng)模式,計(jì)算保向運(yùn)動(dòng)距離的取值范圍。由于保向運(yùn)動(dòng)的速度v2不為常數(shù),且與進(jìn)入保向運(yùn)動(dòng)的速度v1和船舶的加速度a的取值范圍有關(guān)。按勻加速直線運(yùn)動(dòng)的定義,根據(jù)式4,分別取a=amin和a=amax,可以計(jì)算出保向運(yùn)動(dòng)的速度取值范圍
2邊對(duì)τ2積分,分別取a=amin和a=amax計(jì)算的取值范圍,計(jì)算見(jiàn)式(5)。
所有的構(gòu)成右位置可達(dá)域。見(jiàn)圖 2 所示,當(dāng),不同取值的?對(duì)應(yīng)位置可達(dá)點(diǎn),構(gòu)成曲線 Γ1;當(dāng)時(shí),不同取值的?對(duì)應(yīng)位置可達(dá)點(diǎn),構(gòu)成曲線Γ2。2曲線與y軸組成的封閉圖形(陰影部分),構(gòu)成Mi點(diǎn)在時(shí)間τ內(nèi)的右位置可達(dá)域(左位置可達(dá)域SL與右位置可達(dá)域SR關(guān)于y軸對(duì)稱)。
通過(guò)Mi的位置可達(dá)域S=SL∪SR,可以判定Ni的可達(dá)性。見(jiàn)圖2所示,Ni落在該可達(dá)區(qū)域外,即Ni?S,則判定Ni不可達(dá)。
根據(jù)馬爾可夫鏈[18],不管先前的狀態(tài)如何,船舶未來(lái)狀態(tài)僅與當(dāng)前狀態(tài)有關(guān)。因此,可以根據(jù)前一時(shí)刻的點(diǎn)的位置確定后續(xù)點(diǎn)的可達(dá)區(qū)域,通過(guò)逐點(diǎn)依次判斷軌跡點(diǎn)的可達(dá)性來(lái)濾除噪聲。利用位置可達(dá)域的性質(zhì),設(shè)計(jì)基于位置可達(dá)域的噪聲去除算法(position reachable domain-based trajectory noise reduction,PRDBTNR),算法的流程見(jiàn)圖3。其中,軌跡數(shù)據(jù)表示為有序元組。。其中:ti為第i個(gè)軌跡點(diǎn)的時(shí)間;Pi為第i點(diǎn)的空間狀態(tài),包含經(jīng)度、緯度、對(duì)地航速和對(duì)地航向。
圖3 PRDBTNR主要流程Fig.3 Main process of PRDBTNR
計(jì)算轉(zhuǎn)向運(yùn)動(dòng)和保向運(yùn)動(dòng)的參數(shù),初步判斷Ni的可達(dá)性。建立Mi與Ni的坐標(biāo)系。根據(jù)Ni點(diǎn)的坐標(biāo)和最小回轉(zhuǎn)半徑rmin,確定k的取值范圍。若k的取值落在該范圍內(nèi),則軌跡有實(shí)際意義,令ζ=True并根據(jù)第3節(jié)的方法算出回轉(zhuǎn)圓半徑r和保向運(yùn)動(dòng)的長(zhǎng)度L;反之,軌跡無(wú)實(shí)際意義,令ζ=False,直接判定Ni不可達(dá)并跳過(guò)后續(xù)計(jì)算。根據(jù)采樣間隔τ、Mi的速度v1和回轉(zhuǎn)圓半徑r求得θ?的取值范圍。比較θ與的大小,有如下2種情況。
為衡量不同算法的去噪效果,選用如下的評(píng)價(jià)指標(biāo)作為一級(jí)指標(biāo):ntp是算法判斷為噪聲,且實(shí)際為噪聲的點(diǎn)的數(shù)量;nfn是算法判斷為非噪聲,且實(shí)際為噪聲的點(diǎn)的數(shù)量;nfp是算法判斷為噪聲,且實(shí)際為非噪聲的點(diǎn)的數(shù)量。
由上述一級(jí)指標(biāo)構(gòu)成以下二級(jí)指標(biāo)。
1)精確率δpre,表征算法識(shí)別噪聲點(diǎn)的正確程度。該值越高,表明算法識(shí)別的噪聲點(diǎn)中,識(shí)別正確的噪聲點(diǎn)越多。
2)召回率?rec,表征算法識(shí)別噪聲點(diǎn)的完備程度。該值越高,表明算法能夠從樣本中識(shí)別出的更多的噪聲點(diǎn)。
3)F1,綜合考慮δpre和?rec的指標(biāo)。
實(shí)驗(yàn)選用在長(zhǎng)江口南槽交匯水域航行的中型貨船AIS數(shù)據(jù)集,選取10個(gè)在多源干擾下,具有的復(fù)雜噪聲點(diǎn)分布的軌跡樣本。其中,樣本的最小采樣周期為2 s。PRDBTNR算法的輸入?yún)?shù)按照中型貨船的運(yùn)動(dòng)情況[19-21],對(duì)參數(shù)設(shè)置適當(dāng)?shù)脑6龋员阌谒惴▽?duì)同類船舶進(jìn)行處理,具體取值見(jiàn)表2。
表2PRDBTNR參數(shù)設(shè)置Tab.2 Parameter settings of PRDBTNR
分別采用速度閾值法[8],DBSCAN[12]和PRDBTNR進(jìn)行處理。記錄每個(gè)實(shí)驗(yàn)的處理指標(biāo),得到如表3的處理結(jié)果。每個(gè)實(shí)驗(yàn)評(píng)價(jià)指標(biāo)的最高值被加粗標(biāo)出。從結(jié)果可以明顯看出,速度閾值法的綜合指標(biāo)F1值低于92%,δpre值較高,但?rec值保持低于85%的水平;DBSCAN的處理結(jié)果的各項(xiàng)指標(biāo)存在波動(dòng),原因是受到軌跡形態(tài)和噪聲分布的綜合影響。圖4展示圖1(a)示例的去噪結(jié)果,2種算法均去除所有零散的噪聲點(diǎn),但對(duì)軌跡片段漂移的處理效果不佳。見(jiàn)圖4(a)和圖4(b),對(duì)第2段中大于速度閾值或分布密度較低的噪聲點(diǎn),2種算法的去噪結(jié)果較好;然而對(duì)小于速度閾值或軌跡漂移噪聲,2種算法的去噪效果均不理想,未識(shí)別如第1,3段和第2段起始的分布密度較高的噪聲點(diǎn),甚至將這種類型的噪聲點(diǎn)識(shí)別為軌跡片段的一部分。
圖4 樣例去噪結(jié)果對(duì)比Fig.4 Comparison of denoising result
表3 實(shí)驗(yàn)評(píng)價(jià)結(jié)果Tab.3 Results of the experimental evaluation
與上述算法不同,PRDBTNR能夠適用于各種分布特征的噪聲點(diǎn),尤其能夠妥善處理軌跡片段漂移類型的噪聲點(diǎn)。結(jié)合表3的結(jié)果,對(duì)于每一個(gè)實(shí)驗(yàn)而言,PRDBTNR保證綜合指標(biāo)F1均高于94%的同時(shí),使各分項(xiàng)指標(biāo)?rec和δpre均高于90%。從10條軌跡實(shí)驗(yàn)的均值上對(duì)比其他2個(gè)方法,PRDBTNR的綜合評(píng)價(jià)指標(biāo)F1比速度閾值法和DBSCAN分別高出14.31%和24.03%。從圖4(c)的軌跡可視化結(jié)果上看,無(wú)論是分布零散的噪聲尖點(diǎn),還是軌跡片段漂移類型的噪聲點(diǎn),PRDBTNR算法都能進(jìn)行有效識(shí)別。噪聲被盡數(shù)去除,船舶軌跡被還原成1條直線。
設(shè)計(jì)實(shí)驗(yàn)對(duì)比各個(gè)算法的運(yùn)算速度,通過(guò)處理含不同數(shù)量軌跡點(diǎn)的片段,記錄算法運(yùn)行耗時(shí),結(jié)合算法時(shí)間復(fù)雜度進(jìn)行分析。見(jiàn)圖5所示,隨著軌跡點(diǎn)數(shù)量增大,算法間出現(xiàn)明顯的差異:①速度閾值法的時(shí)間復(fù)雜度為O(n),實(shí)際計(jì)算實(shí)驗(yàn)中平均運(yùn)算耗時(shí)最?。虎贒BSCAN理論上的最差時(shí)間復(fù)雜度為O(n2)。實(shí)際計(jì)算實(shí)驗(yàn)中,隨著軌跡點(diǎn)的數(shù)量增大,計(jì)算耗時(shí)迅速增長(zhǎng)且遠(yuǎn)高于其他2種算法;③PRDBTNR的最差時(shí)間復(fù)雜度為為常數(shù),具體取值見(jiàn)第3節(jié)。理論上,PRDBTNR是與速度閾值法同數(shù)量級(jí)的算法。實(shí)際計(jì)算實(shí)驗(yàn)中PRDBTNR的平均計(jì)算耗時(shí)也介于速度閾值和DBSCAN之間,且比較接近速度閾值法。從具體數(shù)值看,PRDBTNR計(jì)算1 000個(gè)軌跡點(diǎn)的平均耗時(shí)僅為0.2 s,不僅適用離線數(shù)據(jù)的去噪,也適用于運(yùn)算實(shí)時(shí)性較高的在線去噪場(chǎng)合。
圖5 運(yùn)算時(shí)間比較Fig.5 Comparison of operating time
針對(duì)船舶AIS軌跡數(shù)據(jù)噪聲去除問(wèn)題,綜合多源干擾下的不同噪聲分布特征,提出基于船舶運(yùn)動(dòng)規(guī)律的位置可達(dá)域模型。同時(shí),構(gòu)建含滑窗機(jī)制的算法解決逐點(diǎn)迭代過(guò)程的初值敏感問(wèn)題。選用含噪AIS軌跡數(shù)據(jù),驗(yàn)證模型與算法的有效性。相比基于軌跡形態(tài)的噪聲去除方法,基于位置可達(dá)域的噪聲去除方法能夠結(jié)合運(yùn)動(dòng)學(xué)模型準(zhǔn)確識(shí)別并去除具有各種分布特征的噪聲。算法的時(shí)間復(fù)雜度低,計(jì)算速度快,能夠滿足不同數(shù)據(jù)處理場(chǎng)景的需求。后續(xù)將使用該方法,針對(duì)在線去噪的實(shí)際應(yīng)用場(chǎng)景展開(kāi)研究。