基于改進(jìn)Frechet距離的海上目標(biāo)航跡相似性度量方法

劉敬一，郭 琦，陳金勇，楚博策

(中國(guó)電子科技集團(tuán)公司第五十四研究所，河北 石家莊 050081)

0 引言

隨著船舶自動(dòng)識(shí)別系統(tǒng)(Automatic Identification System，AIS)的不斷發(fā)展，大量的船舶航行軌跡被記錄并保存下來(lái)。船舶航行軌跡蘊(yùn)含著豐富的船舶行為模式特征以及交通航行規(guī)律，可以為船舶目標(biāo)行為預(yù)測(cè)、異常檢測(cè)和航路規(guī)劃等諸多應(yīng)用提供支撐，具有十分重要的現(xiàn)實(shí)意義和經(jīng)濟(jì)價(jià)值[1]。

運(yùn)動(dòng)目標(biāo)軌跡相似性度量作為目標(biāo)行為規(guī)律分析的基礎(chǔ)，是軌跡挖掘分析中的研究重點(diǎn)之一。相對(duì)于陸地移動(dòng)目標(biāo)軌跡相似性度量方法較為成熟的發(fā)展，船舶等海上移動(dòng)目標(biāo)軌跡的相似性度量研究較少，主要有以下兩方面原因：① 船舶運(yùn)動(dòng)受到島礁分布、洋流流向和作業(yè)內(nèi)容等特殊條件約束；② 相對(duì)于陸地運(yùn)動(dòng)目標(biāo)軌跡的較小時(shí)空跨度，船舶的運(yùn)動(dòng)軌跡一般是長(zhǎng)時(shí)間跨度、大空間范圍。因此，面向船舶等海上目標(biāo)移動(dòng)軌跡相似性度量，需要綜合考慮船舶的行為模式和運(yùn)動(dòng)特征，以及AIS數(shù)據(jù)的數(shù)據(jù)特點(diǎn)，建立一種適用于船舶等海上運(yùn)動(dòng)目標(biāo)的軌跡相似性度量方法。

現(xiàn)有針對(duì)移動(dòng)目標(biāo)軌跡相似性的度量方法可以劃分為：① 基于深度學(xué)習(xí)的軌跡相似性度量；② 基于軌跡空間分布特征的相似性度量。

基于深度學(xué)習(xí)的軌跡相似性度量是利用深度表征學(xué)習(xí)等技術(shù)對(duì)移動(dòng)軌跡的特征進(jìn)行抽象，并在此基礎(chǔ)上進(jìn)行軌跡相似性的衡量。 Li等[2]、Abdalla等[3]和Yao等[4]許多國(guó)外學(xué)者以及陳垣毅等[5]、王新瑞等[6]許多國(guó)內(nèi)學(xué)者在此方面都取得了較好的研究成果。深度學(xué)習(xí)技術(shù)在許多軌跡相似性度量中取得了超過(guò)傳統(tǒng)方法的表現(xiàn)，但此類(lèi)方法嚴(yán)重依賴(lài)于數(shù)據(jù)的質(zhì)量和規(guī)模，在數(shù)據(jù)量不足或質(zhì)量較差時(shí)模型效果難以保證。

基于軌跡時(shí)空分布特征的相似性度量根據(jù)關(guān)注對(duì)象的不同，可以將此類(lèi)方法進(jìn)一步劃分為基于航跡點(diǎn)的相似性分析以及基于航跡段的相似性分析，其中，基于軌跡點(diǎn)的相似性度量主流的方法有Hausdorff距離[7]、Frechet距離[8]、最大/最小歐氏距離[9]、DTW[10]、LCSS[11]和ERP[12]等；基于軌跡段的相似性度量方法將軌跡段作為分析的基本單元，通過(guò)分析軌跡段之間的相似性來(lái)實(shí)現(xiàn)對(duì)航跡整體相似性的度量[13-20]。此類(lèi)方法多數(shù)采用地理空間距離閾值來(lái)衡量軌跡間相似性，在特定應(yīng)用背景下需要融合相關(guān)專(zhuān)家知識(shí)進(jìn)行閾值確定，使得軌跡相似性度量受到人為干擾因素較大。

綜上分析，現(xiàn)有軌跡相似性度量方法并沒(méi)有一種可適用于所有應(yīng)用背景下的各種情況，而面向船舶等海上移動(dòng)目標(biāo)，現(xiàn)有研究多是直接采用陸地目標(biāo)軌跡相似性衡量方法[16-17]，忽略了海上移動(dòng)目標(biāo)的特殊約束條件以及運(yùn)動(dòng)特性。基于此，本文通過(guò)分析船舶運(yùn)動(dòng)特征，在考慮運(yùn)動(dòng)約束、時(shí)空跨度以及定位誤差的情況下，提出了基于改進(jìn)Frechet距離的海上目標(biāo)航跡相似性度量方法，實(shí)現(xiàn)船舶航跡相似性度量在不同空間尺度及噪聲影響下的航跡相似性度量。

1 基于改進(jìn)Frechet距離航跡相似性度量方法

Frechet距離在考慮時(shí)間順序的情況下，通過(guò)最小化2段航跡上航跡點(diǎn)之間的最大距離來(lái)衡量二者的相似程度[7]。Frechet距離示意如圖1所示，以船舶為例，船A和船B分別在各自航跡上自起點(diǎn)至終點(diǎn)單向航行，航行過(guò)程中兩船均可以暫時(shí)停下但是不可以后退，在最優(yōu)航行方式下從起點(diǎn)到終點(diǎn)兩船之間距離的最大值即為Frechet距離。

Frechet距離可評(píng)價(jià)處理連續(xù)曲線(xiàn)的相似性程度，但是仍然存在變尺度下距離閾值難確定以及噪聲敏感的問(wèn)題。出于對(duì)上述問(wèn)題的考慮，本文提出了基于改進(jìn)離散Frechet距離的海上目標(biāo)航跡相似度分析方法，通過(guò)定義相對(duì)Frechet距離和點(diǎn)相似系數(shù)實(shí)現(xiàn)了對(duì)海上目標(biāo)航跡相似度的準(zhǔn)確度量。以下對(duì)方法多包涵的各部分進(jìn)行詳細(xì)介紹。

圖1 Frechet距離示意Fig.1 Diagram of the Frechet distance

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

(a) 相同空間顆粒度情況

(b) 不同空間顆粒度情況圖2 不同空間顆粒度對(duì)Frechet距離的影響Fig.2 Influence of different spatial granularity on Frechet distance

為達(dá)此目的，需要預(yù)先設(shè)定海上目標(biāo)最小航行vmin和最短采樣時(shí)間tmin，由此確定插值的空間顆粒度為：

lmin=vmin×tmin。

(1)

1.2 相對(duì)Frechet距離

針對(duì)航跡預(yù)處理得到的2條航跡L′1和L′2，首先計(jì)算Frechet距離及相應(yīng)的距離跟蹤矩陣DF。

(2)

基于此，定義相對(duì)Frechet距離df，為Frechet距離dF與2條航跡長(zhǎng)度l1和l2平均值的比值：

(3)

相對(duì)Frechet距離利用2條航跡的相對(duì)距離衡量相似性，因此其不受航跡空間尺度大小的影響。在面向不同空間尺寸的航跡時(shí)有較好的穩(wěn)定性，可以更加準(zhǔn)確地衡量2條航跡的相似程度，相對(duì)距離越大，表明2條航跡之間的空間距離相較于其自身長(zhǎng)度而言越大，2條航跡的相似性越低；反之，表明2條航跡之間的相似性越高。

1.3 點(diǎn)相似系數(shù)

為了降低噪聲信號(hào)的影響，充分借鑒最長(zhǎng)公共子序列(LCSS)等算法中的思想，以離散化的方式度量航跡點(diǎn)之間的距離，定義相對(duì)距離小于閾值的點(diǎn)為相似點(diǎn)，大于等于閾值的點(diǎn)為非相似點(diǎn)。點(diǎn)相似系數(shù)cpp定義為最優(yōu)匹配結(jié)果下，相似點(diǎn)數(shù)量占總點(diǎn)數(shù)的比例。cpp越大，表明2條航跡中相似點(diǎn)所占比例越高，2條航跡的相似度越高；反之，2條航跡之間的相似度越低。通過(guò)點(diǎn)相似系數(shù)cpp實(shí)現(xiàn)了兩航跡之間距離的離散化度量。具體實(shí)現(xiàn)如下：

① 基于距離跟蹤矩陣DF，抽取最優(yōu)情況下2條航跡中航跡點(diǎn)的對(duì)應(yīng)關(guān)系，得到匹配點(diǎn)對(duì)序列Lp：

1≤i1≤i2≤…≤M′,1≤j1≤j2≤…≤N′。

② 進(jìn)而由Lp得到匹配點(diǎn)對(duì)相對(duì)距離序列Ld，其中x即為L(zhǎng)d的長(zhǎng)度：

Ld=[d1,d2,d3,…,dx]，x=max(M′,N′),

(4)

式中，相對(duì)距離d定義為2個(gè)經(jīng)緯度之間的地理空間距離dist(p1,p2)與2條航跡長(zhǎng)度l1和l2平均值的比值：

(5)

③ 根據(jù)預(yù)先設(shè)定的點(diǎn)相對(duì)距離閾值ε以及d計(jì)算點(diǎn)相似系數(shù)cpp：

(6)

1.4 基于改進(jìn)Frechet距離的海上目標(biāo)航跡相似性系數(shù)

點(diǎn)相似系數(shù)cpp從航跡內(nèi)部，即組成2條航跡的各個(gè)坐標(biāo)點(diǎn)之間，刻畫(huà)2條航跡的相似程度，相對(duì)Frechet距離df從航跡外部，即從2條航跡整體的走向和距離上，度量2條航跡的相似程度，在最優(yōu)匹配的情況下，所有匹配點(diǎn)對(duì)之間的相對(duì)距離均在df之內(nèi)，df越小，表明2條航跡之間的接近程度越高。本文利用相對(duì)Frechet距離df和相似系數(shù)cpp，給出基于改進(jìn)Frechet距離的海上目標(biāo)航跡相似性系數(shù)(Trajectory Similarity Coefficient of Sea Target Based on Frechet Distance，TSCF)，計(jì)算如下：

ρTSCF=αcpp+βdf，

(7)

式中，α，β為比例系數(shù)。為統(tǒng)一相對(duì)Frechet距離df和相似系數(shù)cpp與相關(guān)性強(qiáng)弱之間的變化關(guān)系，一般β為負(fù)值。

由上述分析可知，ρTSCF可以兼顧整體相似性和局部相似性，實(shí)現(xiàn)對(duì)2條航跡相似程度的準(zhǔn)確度量，同時(shí)大幅增加算法在面向變尺度航跡及強(qiáng)噪聲航跡情況下航跡相似性指標(biāo)的穩(wěn)定性。

2 實(shí)例驗(yàn)證與對(duì)比分析

為了驗(yàn)證TSCF衡量航跡相似程度的有效性，首先分析了其在不同空間尺度航跡以及不同強(qiáng)弱噪聲影響下的表現(xiàn)，借助已有專(zhuān)家知識(shí)對(duì)算法效果進(jìn)行評(píng)估。其次，將TSCF與傳統(tǒng)Frechet距離、LCSS和DTW等進(jìn)行對(duì)比，以算法在各種不同類(lèi)型航跡下相似度指標(biāo)變化情況為衡量標(biāo)準(zhǔn)。

2.1 實(shí)驗(yàn)數(shù)據(jù)介紹

實(shí)驗(yàn)數(shù)據(jù)選取了美國(guó)國(guó)家海洋和大氣局公布的2019年1月1日—1月15日美國(guó)近海及公海范圍內(nèi)的AIS數(shù)據(jù)(https:∥coast.noaa.gov/htdata/CMSP/AISDataHandler/2019/index.html)，該數(shù)據(jù)中包含大量海上船舶航行記錄，但是缺乏大空間尺度航跡。因此，在AIS數(shù)據(jù)基礎(chǔ)上基于真實(shí)航跡數(shù)據(jù)特征通過(guò)數(shù)據(jù)仿真的方式進(jìn)行實(shí)驗(yàn)數(shù)據(jù)擴(kuò)充。

首先結(jié)合港口位置信息從上述數(shù)據(jù)集中提取標(biāo)準(zhǔn)航跡數(shù)據(jù)(標(biāo)準(zhǔn)航跡指船只從某一港口出發(fā)后返回或者到達(dá)另一港口所產(chǎn)生的航跡，剔除拖網(wǎng)捕魚(yú)等海上作業(yè)過(guò)程)。按照航跡長(zhǎng)度將提取的航跡劃分為6組，如表1所示，用于驗(yàn)證算法對(duì)于不同空間尺度航跡的應(yīng)用效果；其次，從眾多航跡中選取若干包含噪聲較小的參照航跡對(duì)，通過(guò)在其中加入不同強(qiáng)度的噪聲信號(hào)，生成5個(gè)實(shí)驗(yàn)組，如表2所示，用于驗(yàn)證算法在不同強(qiáng)度噪聲干擾下的表現(xiàn)。

表1 不同空間尺度實(shí)驗(yàn)航跡數(shù)據(jù)分組情況

表2 不同噪聲實(shí)驗(yàn)航跡數(shù)據(jù)分組情況

2.2 方法驗(yàn)證

基于上述實(shí)驗(yàn)航跡數(shù)據(jù)集，對(duì)TSCF從不同空間尺度和抗噪性方面進(jìn)行綜合評(píng)價(jià)。本文結(jié)合已有專(zhuān)家知識(shí)對(duì)“相似航跡”進(jìn)行如下定義：① 二者的出發(fā)港口和到達(dá)港口相同；② 二者走向一致，若航跡存在明顯轉(zhuǎn)向，則二者轉(zhuǎn)向位置接近；③ 二者航行路徑相同，即在因島嶼或其他地理因素的影響下存在多條航行路徑時(shí)，二者選擇的航行路徑一致。按照上述定義對(duì)相似性度量方法在不同情況下的分析結(jié)果進(jìn)行評(píng)估和對(duì)比分析。

首先，評(píng)估TSCF在不同空間尺度條件下對(duì)航跡數(shù)據(jù)相似性度量的效果。按照實(shí)驗(yàn)航跡數(shù)據(jù)集合的第1種劃分方法，分別從各組中隨機(jī)抽取20%航跡，分別計(jì)算其與樣本集中各個(gè)航跡的相似系數(shù)，在各組相似性閾值均取0.8的情況下得到相應(yīng)的相似性分析結(jié)果，TSCF在各個(gè)空間尺度下的表現(xiàn)如表3所示，表中TP為相似航跡分析結(jié)果中正確的數(shù)量；FP為相似航跡分析結(jié)果中錯(cuò)誤的數(shù)量；FN為相似航跡中被預(yù)測(cè)錯(cuò)誤的數(shù)量；Precision為分類(lèi)精確率，表示航跡分析結(jié)果中正確結(jié)果所占的比例；Recall為分類(lèi)召回率，表示所有相似航跡中被有效檢出的比例。由表3可以看出，各組在使用相同閾值0.8的情況下，相似性分析結(jié)果相近，總體精確率為79.70%，召回率為100%。表明TSCF在不同空間尺度下均能夠取得良好的相似性分析結(jié)果。

表3 不同空間尺度下航跡相似性度量效果

為了驗(yàn)證TSCF在不同噪聲情況下的穩(wěn)定性，選取10對(duì)不同空間尺度、不同幾何特征的航跡，分別在其中加入不同程度的噪聲信號(hào)并多次計(jì)算求平均值作為計(jì)算結(jié)果，以不同噪聲下結(jié)果的均方差為評(píng)價(jià)指標(biāo)判斷該指標(biāo)在噪聲信號(hào)下的表現(xiàn)，結(jié)果如表4所示。由表4可以看出，對(duì)同一對(duì)航跡，不同強(qiáng)度噪聲信號(hào)的加入并未對(duì)航跡相似性評(píng)價(jià)指標(biāo)產(chǎn)生較大影響，各組均方差均極小，表明TSCF對(duì)噪聲信號(hào)具有一定的魯棒性。

表4 不同噪聲情況下航跡相似性度量效果

2.3 方法對(duì)比分析

為了進(jìn)一步驗(yàn)證TSCF的有效性，對(duì)比傳統(tǒng)Frechet距離、LCSS算法和DTW算法，以各個(gè)算法在不同實(shí)驗(yàn)組之間航跡相似度評(píng)價(jià)指標(biāo)的變化程度為衡量標(biāo)準(zhǔn)，比較算法在多種情況下的穩(wěn)定性與有效性。借助專(zhuān)家知識(shí)從每個(gè)實(shí)驗(yàn)組中重新抽取5對(duì)相似航跡，分別計(jì)算各個(gè)相似性度量指標(biāo)，對(duì)每個(gè)指標(biāo)的5個(gè)計(jì)算結(jié)果取平均值作為最終結(jié)果，如表5所示。

表5 不同空間尺度情況下航跡相似性度量效果

由表5可以看出，TSCF在不同實(shí)驗(yàn)組中的計(jì)算結(jié)果相近，具有較高的穩(wěn)定性和準(zhǔn)確性,能夠較為準(zhǔn)確地描述2條航跡之間的相似關(guān)系。而傳統(tǒng)Frechet距離、DTW算法則完全依賴(lài)于絕對(duì)距離的計(jì)算，不同空間尺度的航跡之間計(jì)算結(jié)果差距巨大，無(wú)法通過(guò)設(shè)定統(tǒng)一的閾值來(lái)實(shí)現(xiàn)相似性判斷；LCSS算法通過(guò)將距離二值化在一定程度上避免了上述問(wèn)題，但是由于距離二值化過(guò)程中仍然存在無(wú)法設(shè)定統(tǒng)一閾值的問(wèn)題，所以該算法在不同實(shí)驗(yàn)組中的表現(xiàn)仍然存在較大差距。

3 結(jié)束語(yǔ)

本文基于船舶運(yùn)動(dòng)特征，在考慮運(yùn)動(dòng)約束、時(shí)空跨度以及定位誤差的情況下，提出了基于改進(jìn)Frechet距離的海上目標(biāo)航跡相似性度量方法，通過(guò)定義相對(duì)Frechet距離和點(diǎn)相似系數(shù)，實(shí)現(xiàn)了對(duì)于海上目標(biāo)航跡相似度的準(zhǔn)確度量。通過(guò)實(shí)驗(yàn)驗(yàn)證基于經(jīng)典相似性度量方法的對(duì)比得出，本文所提出的基于改進(jìn)Frechet距離的海上目標(biāo)航跡相似性度量方法具有較好的空間尺度不變性與噪聲魯棒性，在不同噪聲以及空間尺度下均有著較為穩(wěn)定的表現(xiàn)，在分析海上目標(biāo)運(yùn)動(dòng)軌跡的問(wèn)題中，相較于以往的軌跡相似性分析方法，能夠較為準(zhǔn)確地刻畫(huà)2條航跡的相似程度。本文提出的航跡相似性度量方法主要考慮了航跡的空間分布特征，并未利用航向、航速和時(shí)序信號(hào)等其他維度的特征，在后續(xù)的工作中可以將此類(lèi)信息加入到航跡特征描述中，進(jìn)一步提升了航跡相似性描述的準(zhǔn)確性。