基于改進Frechet距離的海上目標航跡相似性度量方法

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

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

0 引言

隨著船舶自動識別系統(Automatic Identification System，AIS)的不斷發展，大量的船舶航行軌跡被記錄并保存下來。船舶航行軌跡蘊含著豐富的船舶行為模式特征以及交通航行規律，可以為船舶目標行為預測、異常檢測和航路規劃等諸多應用提供支撐，具有十分重要的現實意義和經濟價值[1]。

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

現有針對移動目標軌跡相似性的度量方法可以劃分為：① 基于深度學習的軌跡相似性度量；② 基于軌跡空間分布特征的相似性度量。

基于深度學習的軌跡相似性度量是利用深度表征學習等技術對移動軌跡的特征進行抽象，并在此基礎上進行軌跡相似性的衡量。 Li等[2]、Abdalla等[3]和Yao等[4]許多國外學者以及陳垣毅等[5]、王新瑞等[6]許多國內學者在此方面都取得了較好的研究成果。深度學習技術在許多軌跡相似性度量中取得了超過傳統方法的表現，但此類方法嚴重依賴于數據的質量和規模，在數據量不足或質量較差時模型效果難以保證。

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

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

1 基于改進Frechet距離航跡相似性度量方法

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

Frechet距離可評價處理連續曲線的相似性程度，但是仍然存在變尺度下距離閾值難確定以及噪聲敏感的問題。出于對上述問題的考慮，本文提出了基于改進離散Frechet距離的海上目標航跡相似度分析方法，通過定義相對Frechet距離和點相似系數實現了對海上目標航跡相似度的準確度量。以下對方法多包涵的各部分進行詳細介紹。

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

1.1 數據預處理

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

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

為達此目的，需要預先設定海上目標最小航行vmin和最短采樣時間tmin，由此確定插值的空間顆粒度為：

lmin=vmin×tmin。

(1)

1.2 相對Frechet距離

針對航跡預處理得到的2條航跡L′1和L′2，首先計算Frechet距離及相應的距離跟蹤矩陣DF。

(2)

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

(3)

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

1.3 點相似系數

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

① 基于距離跟蹤矩陣DF，抽取最優情況下2條航跡中航跡點的對應關系，得到匹配點對序列Lp：

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

② 進而由Lp得到匹配點對相對距離序列Ld，其中x即為Ld的長度：

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

(4)

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

(5)

③ 根據預先設定的點相對距離閾值ε以及d計算點相似系數cpp：

(6)

1.4 基于改進Frechet距離的海上目標航跡相似性系數

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

ρTSCF=αcpp+βdf，

(7)

式中，α，β為比例系數。為統一相對Frechet距離df和相似系數cpp與相關性強弱之間的變化關系，一般β為負值。

由上述分析可知，ρTSCF可以兼顧整體相似性和局部相似性，實現對2條航跡相似程度的準確度量，同時大幅增加算法在面向變尺度航跡及強噪聲航跡情況下航跡相似性指標的穩定性。

2 實例驗證與對比分析

為了驗證TSCF衡量航跡相似程度的有效性，首先分析了其在不同空間尺度航跡以及不同強弱噪聲影響下的表現，借助已有專家知識對算法效果進行評估。其次，將TSCF與傳統Frechet距離、LCSS和DTW等進行對比，以算法在各種不同類型航跡下相似度指標變化情況為衡量標準。

2.1 實驗數據介紹

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

首先結合港口位置信息從上述數據集中提取標準航跡數據(標準航跡指船只從某一港口出發后返回或者到達另一港口所產生的航跡，剔除拖網捕魚等海上作業過程)。按照航跡長度將提取的航跡劃分為6組，如表1所示，用于驗證算法對于不同空間尺度航跡的應用效果；其次，從眾多航跡中選取若干包含噪聲較小的參照航跡對，通過在其中加入不同強度的噪聲信號，生成5個實驗組，如表2所示，用于驗證算法在不同強度噪聲干擾下的表現。

表1 不同空間尺度實驗航跡數據分組情況

表2 不同噪聲實驗航跡數據分組情況

2.2 方法驗證

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

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

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

為了驗證TSCF在不同噪聲情況下的穩定性，選取10對不同空間尺度、不同幾何特征的航跡，分別在其中加入不同程度的噪聲信號并多次計算求平均值作為計算結果，以不同噪聲下結果的均方差為評價指標判斷該指標在噪聲信號下的表現，結果如表4所示。由表4可以看出，對同一對航跡，不同強度噪聲信號的加入并未對航跡相似性評價指標產生較大影響，各組均方差均極小，表明TSCF對噪聲信號具有一定的魯棒性。

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

2.3 方法對比分析

為了進一步驗證TSCF的有效性，對比傳統Frechet距離、LCSS算法和DTW算法，以各個算法在不同實驗組之間航跡相似度評價指標的變化程度為衡量標準，比較算法在多種情況下的穩定性與有效性。借助專家知識從每個實驗組中重新抽取5對相似航跡，分別計算各個相似性度量指標，對每個指標的5個計算結果取平均值作為最終結果，如表5所示。

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

由表5可以看出，TSCF在不同實驗組中的計算結果相近，具有較高的穩定性和準確性,能夠較為準確地描述2條航跡之間的相似關系。而傳統Frechet距離、DTW算法則完全依賴于絕對距離的計算，不同空間尺度的航跡之間計算結果差距巨大，無法通過設定統一的閾值來實現相似性判斷；LCSS算法通過將距離二值化在一定程度上避免了上述問題，但是由于距離二值化過程中仍然存在無法設定統一閾值的問題，所以該算法在不同實驗組中的表現仍然存在較大差距。

3 結束語

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