基于動態時間彎曲的欠時間信息雷達精度評估方法

龐 卓，詹進雄，呂永樂

(南京電子技術研究所，南京 210000)

0 引言

測量精度屬于雷達重要系統指標，對其進行精確評估能夠幫助用戶準確掌握雷達狀態，規劃任務部署。測量精度可分為系統誤差與隨機誤差兩部分，其中系統誤差指保持恒定或按確定的方法變化的誤差，反映了雷達系統自身性質；隨機誤差指偶然誤差和不定誤差，反映了雷達運行穩定性[1]。為準確獲取雷達精度，特別是系統誤差，需要目標位置真值數據，并將雷達測量數據與真實數據進行匹配與插值計算。當前目標真值可通過民航飛機安裝的廣播式自動相關監視(ADS-B, automatic dependent surveillance-broadcast)系統得到，且具有飛行狀態穩定、航線可重復、可多條航線檢查驗證、接收設備體積小的優點，因此利用民航數據進行雷達外場精度檢查和考核的方法逐步被采用，具體原理可參見[2-6]，其中航跡匹配對齊是最重要的環節。由于ADS-B與雷達賦時方法不同，兩者存在一定時間誤差，在精度計算前需要進行對齊操作[7-10]。

文獻[12]介紹了基于ADS-B數據的雷達精度測量原理，同時利用航跡拐點作為基準點來人工對齊航跡以降低匹配誤差。文獻[13]通過對ADS-B誤差及目標回波中心變化引入的誤差影響進行建模，利用目標在不同位置時誤差變化來最小化誤差影響，對計算結果作聯合修正，提高了雷達系統誤差標定的精度和穩定性。文獻[14]則通過建立單雷達直線航跡線加權估計模型，實現對雷達觀測目標的坐標值修正。上述方法采用人工或建模手段減少ADS-B誤差從而提升精度評估效果，但都依賴于時間信息，在時間信息缺失或誤差較大的情況效果會急劇下降甚至失效。而實際應用中存在由于噪聲等原因會產生時間信息缺失、時間節拍不均勻、點跡丟失等情況，大大影響航跡匹配準確度，甚至導致基于時間的匹配方法失效。因此尋找一種對時間信息依賴度低，同時保證一定精度的航跡匹配方法對提高測量精度評估準確性、擴寬測量精度評估應用時機與范圍具有重要意義。

本文研究一種基于動態時間彎曲(DTW, dynamic time warping)理論的低時間信息依賴航跡匹配方法。DTW是一種廣泛應用的序列相似度計算方法[15-18]，原理利用序列整體信息和形狀特征，允許時間軸的彎曲以及一條時間序列上的一個點對應另一條時間序列上的多個點，利用動態規劃矩陣來對齊時間序列，獲取最優的對齊策略得到最短彎曲路徑從而計算匹配路徑長度和作為相似度。利用DTW算法進行航跡匹配不需要時間信息，可根據匹配序列整體形狀特征自適應生成對應點匹配矩陣，然而原始DTW算法實際應用中存在三個缺陷[19-21]：一是由于噪聲等因素影響，實際雷達和ADS-B獲取的目標航跡序列往往呈碎片化，需要預先確定待匹配序列(包括序列起止點)；二是由于要考慮全局信息，DTW算法時間復雜度較高，尤其在進行長序列匹配時用時較長；三是在大噪聲及緩變序列情況下，DTW匹配過程中會出現異常點，影響匹配精度。

針對上述問題，本文采用片段預篩選方法構造可能匹配序列集合；同時利用下界技術提前終止匹配循環，減少計算量；最后在匹配過程中采用改進歐式距離度量的方法解決大噪聲緩變序列匹配異常問題，提高匹配精度。仿真數據與實測數據上的驗證結果表明本文提出的方法在缺少時間信息的情況下仍能準確快速地找出匹配片段，面對大噪聲場景仍然有較好結果，同時計算復雜度低，有效擴展了基于ADS-B的應用范圍。

1 動態時間彎曲算法原理

動態時間彎曲(DTW)算法原理通過將時序序列進行時間上的規整彎曲進行匹配來衡量不同長度序列相似性。DTW對樣本長度沒有統一要求，且算法相對簡單，不需要歷史數據及額外參數輸入，在時序數據處理領域得到了廣泛的應用。其原理如下：

首先假設時間序列X=(x1,x2,…,xm)與Y=(y1,y2,…,yn)，長度分別為m與n，且xi,yj∈RP維度相同。定義距離矩陣M∈Rm×n為：

M(i,j)=dist(xi,yj) 1≤i≤m,1≤j≤n

(1)

其中:dist(xi,yj)為向量之間度量距離，一般取歐式距離。

此時定義規整路徑W：

W=[w1,w2,…,wt,…,wT]

max(m,n)≤T≤m+n-1

(2)

為兩個時間序列間的映射關系，wt=dist(i,j)表示路徑上的第t個節點，在xi與yj之間建立對應關系，且度量距離為wt。規整路徑從w1=dist(1,1)開始，至wT=dist(m,n)結束，滿足連續單調遞增條件。

假定滿足上述條件的多種規整路徑W組成集合Ω，選出路徑中對應點度量距離和的最小值定義為為DTW距離，即：

(3)

實際應用中采用動態規劃方法求取DTW距離。構建距離累計矩陣D∈Rm×n，滿足：

1≤i≤m,1≤j≤n

(4)

則有dtw(X,Y)=D(m,n)，從D(1,1)開始到計算D(m,n)所經過的路徑即為相應規整路徑W的對應關系，如圖1所示。

圖1 DTW算法匹配規整路徑與距離累計矩陣

利用DTW算法進行航跡序列匹配時候會遇到三個問題：

1)DTW算法具有邊界束縛問題，會強迫兩個待匹配序列的起止點對應，而實際航跡受環境因素、采集條件等影響往往不完整，并不能保證兩序列起止點同時性，強行首尾匹配會引入額外誤差；

2) 傳統插值匹配算法時間復雜度為O(n)，而DTW算法時間復雜度為O(mn)，實際應用過程中當序列長度不斷增加時DTW算法計算量與消耗資源會顯著增加；

3)在針對緩變序列時，序列點之間DTW距離度量結果差別不大，受噪聲影響可能導致多個點匹配到一個點的異常情況出現。

針對上述問題，需要對DTW算法加以改進，提升航跡序列匹配性能。

2 基于動態時間彎曲的精度估計算法設計

2.1 序列預篩選技術

本文采用待匹配序列集合預生成技術，即利用精度先驗知識預先選取相應序列集合，而DTW計算過程中只從待匹配序列集合中進行選取，從而解決邊界束縛問題，提升計算速度。

假定航跡序列P=(p1,p2,…,pm)與真值序列Q=(q1,q2,…,qn)，由于環境噪聲導致航跡未完整跟蹤，即序列長度m

(5)

其中:ri為目標真實值，epi和eqi分別為航跡序列與真值序列誤差，ε1和ε2可分別由雷達與真值序列獲取設備的出廠精度近似代替。根據概率分布知識，eqi-epi位于T=[-3×(ε1+ε2),3×(ε1+ε2)]區間內概率為99.7%，即由測量精度引起的同一時刻航跡序列與真值序列差值在區間T之外的概率為0.3%，認定為不會發生的小概率事件。此外，由于傳輸延遲等引起的航跡序列與真值序列間時間對齊誤差最大為相鄰點間距的1/2，相鄰點間距考慮最壞情況可由序列相鄰兩點間最大距離估計。

此外引入序列長度關系，假定航跡序列采樣率為f1，真值序列采樣率為f2,則考慮無丟失點情況，正確匹配的航跡序列與真值序列時間長度抑制，點數應滿足如下關系：

N1/f1=N2/f2

(6)

其中:N1,N2分別為航跡與真值序列點數，因此在確定匹配序列時可參考上式進行篩選。

綜上所述，片段預篩選具體流程如下：

1) 選取P與Q中采樣率較高的序列，并計算該序列相鄰兩點間最大距離ε0，選取0.5×ε0作為時間所引起誤差上界估計；獲取雷達與真值測量設備出廠精度分別為ε1和ε2，將3×(ε1+ε2)作為測量設備引起誤差上界估計，計算起止點匹配誤差范圍上界：

T=0.5×ε0+3×(ε1+ε2)

(7)

2)從真值序列Q中搜索落于[p1-T,p1+T]區間內的點，組成起始點預篩選集合S，再搜索落于[pm-T,pm+T]區間內的點，組成終止點點預篩選集合E；

3)構造集合Seg={ck=(qi,qj)|qi∈S,qj∈E,i

4)對序列ck進一步進行篩選，選取長度落于[(f2/f1)·N1-K,(f2/f1)·N1+K]的序列ck，最終組成最終片段預篩選集合Seg，其中K為考慮到噪聲等原因測量點丟失后的放松值，可根據實際應用場景修改。

2.2 下界加速技術

大量的文獻研究表明[22]，目前最為有效的DTW加速技術為下界函數技術。其原理是針對待匹配序列通過簡便有效的算法完成DTW估計，得到DTW距離下界，并進行提前剔除，最終只針對篩選后序列進行完整DTW計算，從而降低整個匹配過程中計算開銷。結合本算法，本文在匹配過程中記錄當前最短DTW距離，當從片段預篩選集合Seg中選取新序列時計算其DTW下界，而下界距離大于當前最短DTW距離時直接舍去，減少計算量。

本文選取LB_Kim下界作為判斷指標，LB_Kim方法是一種具有代表性的下界函數[22],其主要思想是使用兩條序列所固有的特征即序列首節點、序列尾節點、序列最大值、序列最小值，來完成這個序列表述工作，得到DTW距離估計，公式如下：

LB_kim(P,ck)=max(dist(A1,A2),dist(B1,B2),

dist(C1,C2),dist(D1,D2))

A1,B1,C1,D1∈PandA2,B2,C2,D2∈ck

(8)

其中:A,B,C,D分別代表序列P,ck中的起始點，最大值點，最小值點，終止點。根據下界定義，有：

dtw(P,ck)≥LB_kim(P,ck)

(9)

且LB_Kim方法時間復雜度為O(n)，小于DTW算法，因此選取序列ck進行DTW計算前可先計算其與P的LB_Kim下界，預先排除明顯不相似的子序列，若大于之前計算的DTW距離，可直接放棄計算，選擇下一序列，減少不必要的計算量，實現算法進一步加速。

2.3 聯合距離度量技術

實際應用過程中由于噪聲原因會導致DTW算法產生異常匹配，影響匹配精度計算，尤其在數據變化較為緩慢時更為明顯。實際雷達量測獲取的是目標高維數據(包括目標某一時刻距離、方位、俯仰等)，因此可通過將數據充分利用聯合距離度量，即在計算匹配序列間點距離時將點視為距離、方位、俯仰組成的高維向量，計算點向量間的歐式距離作為DTW度量距離，從而減少異常匹配概率。需要注意的是由于量綱與精度不同，目標特征元素需歸一化，且計算歐式距離時應依據精度進行加權。

將航跡序列P=(p1,p2,…,pm) 與真值序列Q=(q1,q2,…,qn)分別修改為P=(P1,P2,…,Pm)與Q=(Q1,Q2,…,Qn)，其中:

Pi,Qi∈R3andPi,Qi=(Ri,Ai,Ei)

(10)

(11)

(12)

考慮到不同維度精度不同，在DTW進行距離度量時可依據不同維度出廠精度進行加權，精度越高，權重越大，如下所示：

εx/mean(x) andx∈[R,A,E]

(13)

圖2 低時間信息依賴航跡序列匹配算法

2.4 精度估計算法流程

結合上述改進，本研究基于DTW理論設計一種低時間信息依賴的航跡序列匹配算法：包括充分利用先驗知識構建預匹配集合，降低邊界效應并減少匹配量；同時采用下界技術快速刪除不相似序列，進一步降低匹配計算次數從而加速算法；最后綜合場景高維數據特征利用聯合距離度量方法降低噪聲影響與異常匹配點數。本文算法能夠在時間信息缺失的情況下輸出匹配段落與相應距離，整體流程如圖2所示。

算法首先接收數據輸入，包括一條真值序列(ADS-B序列)、一條航跡序列、雷達初始精度及采樣率；接下來是預匹配序列集合構建，利用2.1所示方法提取起止點，構建并依據采樣率篩選適宜長度得到最終預匹配集合；然后不斷從集合中選取預匹配序列，進行LB_Kim下界計算篩選提速；最后利用聯合距離度量DTW進行匹配距離計算，直到集合中所有序列都被選中；輸出最短DTW距離與對應匹配序列和匹配關系作為航跡匹配結果。

3 實驗結果與分析

3.1 實驗數據來源與說明

實驗分析數據使用5組雷達實測民航數據與對應時間段內采集的ADS-B數據，ADS-B數據已通過坐標轉換到以雷達為中心的極坐標系RAE中，并進行相對化處理，同時為驗證算法準確性保留相對時間標簽。相對化處理后民航數據示例如圖3所示。

圖3 ADS-B與雷達航跡民航實驗數據示例

可以看出在同一段時間內，ADS-B與雷達均能獲取目標的距離、方位、俯仰信息，但兩者采樣率不同，航跡數據采樣率高于ADS-B；兩者均為未非均勻采樣，采樣節拍存在擾動，且兩者采樣點時刻不統一。實際應用中由于數據獲取時刻和時間分配時刻之間的差異會產生一定的系統誤差，反映在圖中是ADS-B與航跡對應點間匹配需要一定時間平移。

3.2 實驗結果

實驗對采集數據進行分析，利用聯合距離度量DTW匹配算法建立ADS-B與雷達航跡點的匹配，然后基于匹配對應關系分別利用時間戳與不加時間戳計算精度指標，得到最終結果。實驗中將時間延遲結合線性插值方法計算的精度指標作為真實結果進行對比分析，時間對齊插值后精度指標計算方法如下：

Etotal=rms(ERR),Esys=mean(ERR),Erand=std(ERR),

whereERR=RHJ-RADSB

(14)

其中:RHJ,RADSB為插值后的距離序列。

其中一組數據DTW匹配結果如圖4所示，圖3為ADS-B與航跡序列匹配結果，圖4為對應規整路徑。可以看出由于ADS-B采樣率較低，相同時間段內采樣點較少，會有一個ADS-B點對應多個雷達航跡點的情景出現；且由于采樣節拍誤差或環境噪聲原因，匹配模式不均勻，每個ADS-B點對應的航跡點數不一致。

在獲取匹配規整路徑后接下來進行精度指標計算，以ADS-B為基礎將每個ADS-B點所匹配的雷達航跡點的橫縱坐標均值作為規整航跡點的橫縱坐標，然后進行插值匹配得到精度。需要注意的是序列若包含時間信息則橫坐標為采樣時間點，若不包含則橫坐標為序數點。某一段數據計算結果如圖5所示。

圖5 雷達精度指標比對結果

圖5中所示為某一段目標目標距離、方位角、俯仰角誤差計算歸一化結果，分別采用原始線性插值方法、DTW匹配方法(包含和不含時間信息)與基準方法對比，越接近1代表與標準結果越接近。可以看出：

1)DTW匹配算法算出結果與標準結果較為接近，滿足正確性要求，可以用于進行航跡匹配工作。

2)是否包含時間信息對DTW匹配精度計算結果影響不大，與原始插值方法相比可用于時間信息丟失、不完全或誤差較大的場景中。

3)與原始方法相比，DTW匹配距離和方位精度誤差較小，俯仰精度誤差較大，但都在容忍范圍內。這是由于距離和方位實際系統差相對自身實際測量值較小，且誤差主要由時間不匹配導致，采用DTW方法能夠得到較為精準的時間匹配關系，從而減少精度誤差；而俯仰實際系統差相對自身實際測量值偏大，采用DTW方法匹配效果下降，導致精度誤差計算結果增大。后續計算時針對此種情況在帶有時間信息時可采用原始插值方法，在時間信息不完全時再采用本文DTW匹配方法作為補充。

5組數據上實驗結果與標準精度值(時間延遲加線性差值)間誤差如表1～3所示，行中1、2、3分別代表原始插值方法(不進行時間延遲)、DTW匹配(不帶時間戳)、DTW匹配(帶時間戳)3種方法。

表1 距離精度計算誤差 m

表2 方位角精度計算誤差 度

表3 俯仰角精度計算誤差(度)

結果表明DTW匹配方法計算精度誤差令人滿意，算法滿足正確性要求；其在針對距離、方位等指標進行精度計算時，由于其系統誤差相對較小且主要由時間節拍不匹配引起，算法計算結果更好；而在俯仰角等指標精度計算過程時，由于系統誤差較大導致自適應匹配效果下降，計算結果不如原始方法，但誤差仍在可接受范圍內。此外原始方法需要時間信息輸入，DTW匹配方法對時間依賴度低，是否包含時間信息對算法結果影響不大，時間信息未知情況下仍然能夠得到令人滿意的結果。

3.3 算法分析與驗證

3.3.1 篩選加速技術驗證

本實驗針對序列篩選技術與下界加速技術進行分析驗證，針對5組實際數據進行分析。首先利用原始DTW算法，強迫首尾對應計算結果；然后利用分段遍歷搜索DTW算法，將所有可能DTW序列遍歷計算，本實驗選取起止點1 s以內數據點分別座位起止點進行遍歷循環，得到最短值作為匹配結果；最后利用本文預篩選加速DTW方法，先構造預篩選集合，再采用下界篩選技術選取最有可能的序列計算DTW最小值。五組數據距離精度計算結果均值如表4所示。

表4 數據篩選加速技術驗證結果均值

可以看出原始DTW計算次數與花費時間最短，但是距離精度計算誤差最大，接近與原始差值算法；本文提出的預篩選加速DTW算法與分段遍歷搜索DTW算法均能從輸入序列中找到正確匹配的片段，誤差較小；而相較于遍歷搜索，本文算法提前構造預篩選集合并利用下界過濾，大大降低了DTW匹配計算次數，在保證誤差不便的基礎上花費時間減少了98%。

3.3.2 聯合度量技術驗證

本實驗針對聯合度量技術進行分析驗證，從實際數據中選取變化較慢的距離采樣片段進行匹配。首先基于校準后時間戳，利用相近隸屬方法得到正確匹配關系，即將校準時間最為接近的點進行匹配；然后分別采用僅距離序列的DTW與聯合度量DTW算法分別進行匹配，結果如圖6所示。

圖6 序列規整路徑匹配關系結果

如圖6所示為同一時間段雷達航跡序列(240點)與ADS-B序列(60點)分別使用聯合度量DTW與原始DTW算法的匹配結果。其中最上部分為基于校準后時間標簽的標準匹配結果，連線表示兩點之間具備匹配對應關系，為序列之間時間間隔最短的點。可以看出，使用原始DTW算法匹配時，由于噪聲原因會產生異常匹配點，如圖中紅圈最下部分所示，航跡序列多個點錯誤匹配到ADS-B序列一個點上，而聯合度量DTW算法會將其匹配到正確對應的點上，如圖紅圈部分中間所示。結果表明聯合度量DTW算法通過利用高維信息，能夠解決大噪聲緩變序列匹配異常問題，提高匹配精度。

4 結束語

基于ADS-B設備的雷達精度評估技術在實際應用中常因為時間信息的缺失或誤差導致精度評估誤差增大甚至失效。本文利用DTW算法實現欠時間信息下航跡精確匹配與雷達精度準確計算。針對DTW實際應用中邊界束縛與計算量大的問題，本文提出序列預篩選方法，利用精度、采樣率等先驗知識構造匹配待選集合，實現匹配片段邊界自動選取與快速計算；同時采用LB_Kim下界加速技術降低循環計算量；最后針對緩變大噪聲場景下DTW異常匹配的問題采用聯合度量方法綜合序列中距離、時間角、方位角高維信息實現序列點的精確匹配。實驗表明，本文所提出的方法利用ADS-B數據在時間信息缺失的情況下仍能夠較準確地估計雷達精度，且計算時間較快。本研究可擴展ADS-B精度評估應用范圍，具有廣泛實用價值。

同時，本算法適用于離線狀態下雷達精度評估，針對在線狀態下雷達精度實時評估技術將后續進一步研究。