徐亞圣 丁赤飚 任文娟 許光鑾

①(中國科學院大學 北京 100049)

②(中國科學院電子學研究所 北京 100190)

③(中國科學院空間信息處理與應用系統(tǒng)技術重點實驗室 北京 100190)

④(微波成像技術重點實驗室 北京 100190)

1 引言

數(shù)據(jù)融合目前在各個領域有著廣泛地應用[1，2]，分布式多傳感器融合系統(tǒng)是一種典型的多傳感器數(shù)據(jù)融合系統(tǒng)[3，4]，具有魯棒性強、成本低的特點。航跡關聯(lián)方法的研究一直是分布式多傳感器融合系統(tǒng)中的一個熱點。航跡關聯(lián)就是確認多條來自不同傳感器的目標軌跡是否屬于同一目標，關聯(lián)后可以有效地降低數(shù)據(jù)的冗余，正確的關聯(lián)也是實現(xiàn)數(shù)據(jù)融合的前提。目前航跡關聯(lián)的方法可以分為兩大類，一類是基于統(tǒng)計的方法，另一類是基于模糊數(shù)學的方法。基于統(tǒng)計的方法主要是利用狀態(tài)估計的差作為統(tǒng)計量并建立統(tǒng)計假設，然后以設定的概率閾值來判定航跡是否關聯(lián)[4-6]?；谀：龜?shù)學的方法主要是選定或設計關聯(lián)隸屬度，通過計算兩兩航跡的關聯(lián)隸屬度來判斷航跡是否關聯(lián)[6-8]。這些方法主要存在以下問題：(1)對目標的航跡進行逐點比較，沒有從航跡整體的角度來考慮，忽視了航跡的全局性的特征；(2)基于統(tǒng)計的方法需要人工設定閾值和大量的調試，擴展性不強；(3)只考慮了隨機誤差，而忽視了其他誤差的影響。

針對上述問題，大量文獻對其進行了研究。文獻[9]將航跡的整體視為時間序列，使用動態(tài)時間規(guī)整(Dynamic Time Warping， DTW)來測量任意兩條航跡之間的相似度，從整體上考慮了航跡形狀的相似性。將DTW相似性引入航跡關聯(lián)當中，避免了在時域上進行配準，在一定程度上減小了誤差。文獻[10]將系統(tǒng)誤差引入到原始的傳感器量測中，構建了一種混合整數(shù)非線性規(guī)劃模型，并對系統(tǒng)誤差進行了估計，有效地提高了系統(tǒng)的性能。文獻[11]提出了一種具有自適應閾值的最大后驗概率(Maximum A Posteriori probability， MAP)關聯(lián)算法。該算法顯示，具有自適應閾值的算法性能優(yōu)于固定閾值算法。

針對現(xiàn)有方法存在的需要人工設定閾值、參數(shù)設置復雜、只考慮單個航跡點以及航跡信息利用不充分的問題，本文提出了一種基于多特征組合的航跡關聯(lián)方法。首先從航跡的整體出發(fā)，在傳統(tǒng)歐式距離度量的基礎上，提出了一種距離分布直方圖的特征并提取了航跡的相似特征，有效地利用了航跡整體的特性，具有較好的抗噪聲性能以及關聯(lián)準確率。其次挖掘了航跡間的速度差分布直方圖特征、傳感器來源特征，然后將這些特征組合，考慮到目前機器學習方法強大的特征學習能力，能夠自動地學習特征中隱含的知識信息，且參數(shù)設置較為簡單，因此利用機器學習方法對挖掘的特征進行學習得到航跡關聯(lián)模型，從而有效地避免了需要人工設定閾值以及參數(shù)設置復雜的問題。最后通過實驗驗證了本文方法的有效性。

2 系統(tǒng)模型描述

船舶的航跡由一系列時空數(shù)據(jù)點(即經(jīng)度、緯度、時間)組成，并且通過多種定位方式獲得，由于同一個目標可能會被多個源觀測到，因此在數(shù)據(jù)融合中心會出現(xiàn)一個目標的多條航跡觀測(對于多條觀測的情況，我們可以對觀測中的航跡兩兩進行關聯(lián)判斷，最后得到關聯(lián)結果)，在系統(tǒng)中造成大量的數(shù)據(jù)冗余，在未判明目標時則會造成大量虛假目標信息，對后續(xù)的一些航跡知識挖掘任務，如目標識別、航跡融合造成很大的影響。

假設分布式多傳感系統(tǒng)中有M個傳感器，每個傳感器輸出的航跡數(shù)為ms，將其中任意一條的航跡數(shù)據(jù)即目標的狀態(tài)估計表示為sk，其中s=1,2,3,???,M,k=1,2,3,???,ms。目 標 的 狀 態(tài)估計sk可以表示成為時間序列(1維或者多維的)，這里定義sk為如下的一個多維的時間序列：

其中，m表示航跡的長度，n表示屬性的維數(shù)。對于任意的兩條航跡數(shù)據(jù)(經(jīng)過一定預處理后，在同一時間段里的兩條航跡數(shù)據(jù))存在以下兩種假設H0和H1：

3 算法描述

3.1 特征挖掘

3.1.1 距離分布直方圖特征

距離是航跡間最基礎也是最直觀的特征，傳統(tǒng)的航跡間的距離特征有歐式距離、編輯距離以及其它描述航跡形狀相似度的距離等，傳統(tǒng)的歐式距離主要是計算航跡對應的距離和或者最大最小距離[12]，且需要兩條航跡在時間上對齊，這些特征雖然簡單且能在一定程度上解決關聯(lián)的問題，但也有著十分明顯的缺點：(1)單一數(shù)值不能很好地反映航跡間的細節(jié)差異；(2)在關聯(lián)時需要人工設定閾值，依賴于人工經(jīng)驗，且關聯(lián)準確率敏感于噪聲。

針對上述存在的問題，本文在歐式距離算法的基礎上，提出了一種基于距離分布直方圖特征(圖1)。特征描述如下：

經(jīng)過一定預處理(按照4.1.2節(jié)中，第1部分所做的時間對齊和抽樣。3.1.2節(jié)及3.1.3節(jié)的特征提取也經(jīng)過這樣的預處理)，兩條時間上對齊(采樣點的時間相同)、航跡長度相同、特征維度為經(jīng)度、緯度、時間的航跡

其中，m表示航跡的長度，設航跡的距離序列為

其中，di表示 和 第i個航跡點對應的距離。為了規(guī)范化處理，本文對距離序列 d istance取對數(shù)，得到：

3.1.2 動態(tài)時間規(guī)整(DTW)相似度特征

航跡作為一種時間序列，可以考慮將其相似度作為一種特征，而DTW是一種典型的用于計算時間序列相似度的算法，它廣泛應用于科學、醫(yī)學、工業(yè)、金融等領域，在人工智能領域使用得更為頻繁[13-22]。DTW定義了時間序列間的最佳匹配，它同時支持不同時間長度的相似度量，具有更好的魯棒性。DTW也從一定程度上反映了航跡間的形狀相似度。因此本文計算航跡間的DTW相似度，并將其作為一類特征。同上設有兩條航跡長度分別為m,n且m,n＞1。特征維度為經(jīng)度、緯度、時間的航跡

我們構建一個m×n的矩陣其中，dij為d(xi,yj)，是兩條航跡兩個點xi和yj的距離。本文將距離定義為兩個經(jīng)緯度點的實際距離，因此矩陣中的每個元素(i,j)表示的是兩個點的匹配程度。在矩陣中構建一條路徑表示航跡和的匹配程度：

圖1 距離分布直方圖特征計算示意圖Fig.1 Schematic diagram of feature calculation of distance distribution histogram

路徑 必須滿足以下3個條件：

(1) 邊界條件：w1=(1,1),wk=(m,n)；

(2) 連續(xù)條件：給定wp=(ip,jp),wp+1=(ip+1,jp+1)，有ip+1-ip≤1,jp+1-jp≤1；

(3) 單調條件：給定wp=(ip,jp),wp+1=(ip+1,jp+1)，有ip+1-ip≥0,jp+1-jp≥0。

其中有多條路徑滿足上述的條件，取滿足以下條件的路徑：

為了計算式(4)，需要構建一個累加距離矩陣，并且利用動態(tài)規(guī)劃的思想求解這個矩陣，遞歸如下：

初始條件為

最終得到的f(m,n)為航跡的DTW特征。圖2及圖3顯示了兩條航跡在DTW算法下的逐點對應關系。

3.1.3 其他特征

航跡間除了距離和DTW相似度兩種主要特征外，本文還提取了速度差分布直方圖特征以及航跡的來源特征，考慮到船舶的行駛速度較慢且傳感器的采樣頻率較高，本文假設任意兩個航跡點之間，船做的是勻速直線運動，從而可以得到每一個航跡點的速度，對于航跡 和，記航跡 和 的速度序列為

圖2 DTW航跡點對應關系Fig.2 Correspondence of DTW track points

圖3 DTW算法匹配關系Fig.3 DTW algorithm matching relationship

其中：

d(i-1,i) 表示的是第i個點與i-1個點的距離，t(i-1,i) 表示的是第i個點與i-1個點的時間差。

設：

為航跡X和Y的速度差序列，其中difvi表示 和第i個航跡點對應的速度的差。然后對做與d istance相同的后續(xù)處理得到速度差分布直方圖特征。

不同來源誤差往往不同，傳統(tǒng)的一些方法在進行仿真實驗的時候假定誤差服從高斯分布，而實際的誤差情況不僅有隨機誤差還有系統(tǒng)誤差的影響，同時不同來源的精度、特性也不相同，因此本文將不同數(shù)據(jù)來源量化為特征，結合機器學習的方法隱性地學習誤差信息從而在一定程度上更好地克服誤差影響。假設有n個不同的來源：

本文將其進行一定的編碼作為來源特征

3.2 關聯(lián)流程

對任意兩條航跡數(shù)據(jù)提取距離、速度差分布直方圖特征、DTW相似度特征以及來源特征，并將這些特征進行組合。然后利用機器學習的模型來進行訓練和判斷。算法的流程圖如圖4所示。

4 實驗驗證

4.1 實驗數(shù)據(jù)集構建及預處理

4.1.1 數(shù)據(jù)集構建

傳統(tǒng)的一些方法實驗都是仿真數(shù)據(jù)上進行的，雖然為了接近真實的情況，在仿真數(shù)據(jù)上加入了噪聲等干擾，但大多數(shù)都是假定噪聲服從高斯分布，忽視其他誤差的影響，因此與實際的船舶航跡數(shù)據(jù)仍然有著較大的差距。本文構建了一個真實的船舶航跡數(shù)據(jù)集，船舶航跡數(shù)據(jù)集是1年多的船舶航跡數(shù)據(jù)，涵蓋了較多的航跡運動情況，數(shù)據(jù)集中每一個實驗樣本由兩條航跡組成，兩條航跡可能源于同一目標，也可能源于不同的目標。數(shù)據(jù)集的航跡樣本標注都是經(jīng)過一定的歷史分析以及多個有經(jīng)驗的判讀員檢驗標注的。因此數(shù)據(jù)集的標注具有較高的可靠性。本文一共標注了8063個航跡實驗樣本對，令兩條航跡源于同一目標的為正樣本，兩條航跡源于不同目標的為負樣本。其中正樣本數(shù)量為2522個、負樣本為5541個。

圖4 關聯(lián)流程圖Fig.4 Association flow chart

4.1.2 數(shù)據(jù)預處理

(1) 時間對齊和抽樣

一般情況下，各個傳感器采樣頻率上報間隔都不盡相同，因此會出現(xiàn)如圖5所示的情形。不同傳感器的采樣頻率往往不同，得到的航跡點的時間并不一一對應，如果直接計算距離會有較大的誤差，且不滿足計算距離分布直方圖特征的條件，因此需要對航跡進行插值，再在同一時刻進行采樣。

通過對航跡數(shù)據(jù)集中的數(shù)據(jù)(在本文構建的數(shù)據(jù)集里)進行分析后，發(fā)現(xiàn)傳感器的采樣頻率大多數(shù)在3～300 s，船舶行駛速率大多在11節(jié)左右(20 km/h)。因此本文假設船舶的兩個采樣點之間是做勻速直線運動，從而進行線性插值處理，此假設主要是為了減小直接計算非時間對齊航跡點的歐式距離時的較大誤差同時滿足距離分布直方圖特征的計算條件。線性插值采樣如圖6所示。同時為了更符合勻速直線運動的假設，本文將不對采樣間隔大于600 s的點做插值處理。

圖5 兩條航跡對應點時間不同示意圖Fig.5 Different timings of the corresponding points on the two tracks

圖6 航跡線性插值采樣示意圖Fig.6 Linear interpolation sampling schematic diagram

(2) 樣本擴充

原始的可用樣本較少，正樣本數(shù)量僅為2522個、負樣本為5541個，通過對樣本的觀察發(fā)現(xiàn)：部分樣本的時間跨度較長且樣本點數(shù)極多(例如有些樣本航跡點數(shù)有3萬多個，時間長度超過20 h)。這樣的樣本可以對其進行拆分，拆分方式如圖7所示，本文將其拆分為時間長度為2～3 h的多個樣本以此來擴充樣本。

圖7 航跡樣本拆分示意圖Fig.7 Schematic diagram of separation of track samples

4.2 實驗結果分析

為了驗證算法的性能，本文首先比較了傳統(tǒng)方法提取的加權距離特征(加權航跡方法計算出的統(tǒng)計量特征)[23，24]、平均距離特征、最大距離特征在設定閾值與利用機器學習方法時性能的差異，其次比較了距離分布直方特征與傳統(tǒng)的平均距離特征、加權航跡特征、最大距離特征，之后對本文提出特征進行組合，比較組合特征和單一特征的性能，最后對比了不同的機器學習方法的性能。實驗數(shù)據(jù)集是經(jīng)上述預處理后并隨機打亂后的船舶樣本集，其中80%的樣本用來訓練，20%的樣本用來測試。

4.2.1 評價指標

本文采用常用的機器學習評價指標[25]，精度、查全率、查準率、F1度量、ROC (Receiver Operating Characteristic)曲線以及AUC (Area Under Curve)值，令兩條航跡源于同一目標的為正樣本，兩條航跡源于不同目標的為負樣本。則評價指標的具體定義如下：

ROC曲線根據(jù)學習器的預測結果對樣本進行排序，并且按照這個順序把樣本預測為正例，性能越好的模型，ROC曲線越接近于左上角。由于從圖形上無法直觀比較ROC曲線，因此可以通過計算ROC曲線下方的面積，即AUC值，來比較模型的好壞，一般來說AUC值越大則表示模型性能越好。

產(chǎn)業(yè)結構的區(qū)域差異性是制約我國經(jīng)濟發(fā)展的重要因素，學術界關于我國產(chǎn)業(yè)結構區(qū)域特征的研究由來已久。中國產(chǎn)業(yè)結構的確存在區(qū)域差異性（Naughton，2003），但這種差異性在趨同作用下逐漸衰減且呈收斂特征（Poncet，2003）。三大產(chǎn)業(yè)的發(fā)展成本有所不同，其中第三產(chǎn)業(yè)的發(fā)展能降低加工成本和交易成本，有利于提高社會整體的經(jīng)濟效率（吳敬璉，2014）。

表1 平均距離特征閾值方法與機器學習方法指標對比Tab.1 Comparison of average distance characteristics threshold method and machine learning method index

表2 加權距離特征閾值方法與機器學習方法指標對比Tab.2 Comparison of weighted distance characteristics threshold method and machine learning method index

表3 最大距離特征閾值方法與機器學習方法指標對比Tab.3 Comparison of maximum distance characteristics threshold method and machine learning method index

4.2.2 閾值方法與機器學習方法對比實驗

傳統(tǒng)的方法閾值設置大多根據(jù)統(tǒng)計以及設計者經(jīng)驗來決定[26]，其中一些方法還依賴于系統(tǒng)的參數(shù)[4，27]，本文根據(jù)真實數(shù)據(jù)集的情況，利用了3種數(shù)據(jù)的統(tǒng)計值作為閾值來與機器學習方法進行比較，它們分別是精度最高閾值、平均數(shù)閾值以及中位數(shù)閾值。精度最高閾值：也是一般常用的閾值設置方法[4]，在特征域值范圍內的值，通過一定的步長設置尋找最佳精度閾值；平均數(shù)閾值和中位數(shù)閾值主要是利用特征的統(tǒng)計特性[28]，本文對3種特征分別求得它們平均數(shù)與中位數(shù)作為閾值，具體的閾值與實驗結果如表1～表3所示。機器學習模型則選較為常用的樹模型，從表1～表3中可以看出，機器學習的方法則能夠更好學習特征表示的含義，具有更強的泛化能力，因此關鍵指標均遠高于設定閾值的方法，且不需要人工設定閾值(精度最高閾值需要大量的實驗才能確定)，進而說明了引入機器學習方法的有效性。

4.2.3 距離分布直方圖特征與傳統(tǒng)特征對比實驗

表4是利用樹模型學習不同特征的各項指標，圖8描述了不同特征的ROC曲線圖。從表4以及圖8可以看出本文提出的距離分布直方圖特征的性能優(yōu)于傳統(tǒng)的距離特征。主要原因是距離分布直方圖特征從航跡的整體出發(fā)，更好地考慮了整體的距離分布。圖9是傳統(tǒng)距離特征無法識別而距離分布直方圖特征能識別的關聯(lián)目標，圖中紅色和藍色分別代表了不同來源觀測的同一目標的航跡。從圖中可以看出，傳統(tǒng)的距離特征由于是單一數(shù)值描述，對有噪聲干擾的目標不能準確關聯(lián)，而距離分布直方圖特征考慮的是整體的距離分布，因此具有較好的抗噪性能。圖10是距離分布直方圖特征關聯(lián)失敗的典型情況，圖10(a)和圖10(b)是兩條航跡源于同一目標，圖10(c)為兩條航跡源于不同目標。從圖10(a)和圖10(b)中可以直觀地看出，其受噪聲干擾較為嚴重，而圖10(c)兩條航跡十分接近，通過對它們特征的可視化分析發(fā)現(xiàn)，圖10(a)、圖10(b)距離整體分布呈現(xiàn)較大差異，此時距離分布直方圖特征難以有效地關聯(lián)圖10(a)、圖10(b)所示的情況。圖10(c)的距離整體分布十分接近，但速度整體分布差異較大，單一的距離分布直方圖特征在這種情況難以正確完成關聯(lián)判斷。

表4 不同特征指標對比Tab.4 Comparison of different characteristics

圖8 不同方法ROC曲線Fig.8 Different methods of ROC curves

圖9 傳統(tǒng)距離特征無法識別而距離分布直方圖能夠識別的目標Fig.9 The targets that can’t be identified by traditional distance feature but can be identified by distance distribution histogram

圖10 距離分布直方圖特征關聯(lián)失敗的目標Fig.10 The targets of distance distribution histogram feature error association

表5 組合特征指標對比Tab.5 Comparison of composite features

圖11 特征組合ROC曲線Fig.11 Feature combination ROC curve

4.2.4 組合特征對比實驗

表5是利用樹模型學習不同組合特征的各項指標，圖11描述了不同組合特征的ROC曲線圖，表5以及圖11中，DDH (Distance Distribution Histogram)表示的是距離分布直方圖特征，SDDH (Speed Difference Distribution Histogram)表示的速度差分布直方圖特征。圖12給出了單一特征錯誤關聯(lián)而組合特征正確識別情況(圖10(c)在加入速度差分布直方圖特征后能夠準確地判斷其為不同的目標)，圖12(a)是DDH特征錯誤關聯(lián)的目標而加入DTW相似度特征準確識別的情形，主要原因是兩條航跡的距離較近，在距離維度上很難區(qū)分，而其DTW相似度差異較大(DTW相似度在一定程度上描述了航跡形狀上的相似度)。圖12(b)是DDH+DTW特征錯誤關聯(lián)的目標而加入速度差分布直方圖特征準確識別的情形，主要原因是兩條航跡的距離較近，DTW相似度也較高，而其有12.5%的航跡點速度相差5節(jié)航速，速度差分布差異較大。圖12(c)是DDH+DTW+SDDH特征錯誤關聯(lián)而加入來源特征準確識別的情形，主要原因是兩條航跡的距離較近，DTW相似度也高，速度差分布也相近，但兩條航跡來自同一觀測源，因此判定不是同一目標。圖13是距離分布直方圖特征關聯(lián)失敗的典型情況，圖13(a)和圖13(b)是兩條航跡源于同一目標，圖13(c)為兩條航跡源于不同目標。從圖13(a)、圖13(b)中可以直觀地看出，其受噪聲干擾較為嚴重，而圖13(c)兩條航跡十分接近，通過對它們特征的可視化分析發(fā)現(xiàn)，圖13(a)和圖13(b)的距離、速度整體分布以及DTW相似度呈現(xiàn)較大差異，此時組合特征難以有效地關聯(lián)圖13(a)和圖13(b)所示的情況。圖13(c)的目標十分接近，且?guī)缀鯖]有移動，因此各項特征十分接近，組合特征在這種情況難以正確完成關聯(lián)判斷。綜上分析以及從表5和圖11中可以看出，每增加一組特征，模型的各項指標都有所提升，不僅說明了所提特征的有效性，而且由于不同特征之間具有一定的互補性，多種特征的組合能夠更加全面地表征航跡間的關系，進一步提升航跡關聯(lián)準確性。在噪聲干擾較大時航跡間的特征也受到了較大的干擾，此時很難有效地進行關聯(lián)判定，同時由于目前航跡點信息有限，可以挖掘的特征有限，因此在一些較為特殊的情況下當前組合特征不能準確地完成關聯(lián)判斷。

4.2.5 不同機器學習方法對比實驗

圖13 組合特征關聯(lián)失敗的目標Fig.13 The targets of combination features error association

表6 不同機器學習方法指標對比Tab.6 Comparison of different machine learning indicators

圖14 不同機器學習方法ROC曲線Fig.14 ROC curves for different machine learning methods

5 結論

針對傳統(tǒng)航跡關聯(lián)方法存在需要人工設定閾值、參數(shù)設置復雜的問題，本文將機器學習的方法引入航跡關聯(lián)中，針對一些傳統(tǒng)方法只考慮航跡單個點的信息及抗噪聲性能較差的問題，本文從航跡的整體出發(fā)，提出了一種距離分布直方圖特征。與此同時對航跡的特征進行挖掘，提取了航跡間的DTW相似度特征、速度差分布直方圖特征以及來源特征，結合機器學習的方法提出了一種基于多特征組合的航跡關聯(lián)方法，該方法在有限的航跡點信息中挖掘了多種有效的特征信息，獲得了較高的關聯(lián)準確率，并且在實際應用中取得較好的效果，隨著樣本和航跡點信息不斷增多，關聯(lián)模型的準確率以及泛化性能還將進一步提升。理論分析和實驗結果均表明該方法的有效性和合理性。根據(jù)算法設計中各環(huán)節(jié)的假設和約束，本文目前提出的航跡關聯(lián)算法主要適用于傳感器采樣頻率較高，運動目標速度較慢(船舶、汽車、行人等)的情況，對于高速運動的目標則需要進一步地分析其運動情況，建立更加精細的插值模型，這也是本文后續(xù)工作中的一個重要的研究方面。