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

龐 卓，詹進雄，呂永樂

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

0 引言

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

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

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

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

1 動態(tài)時間彎曲算法原理

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

首先假設(shè)時間序列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)為向量之間度量距離，一般取歐式距離。

此時定義規(guī)整路徑W：

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

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

(2)

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

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

(3)

實際應(yīng)用中采用動態(tài)規(guī)劃方法求取DTW距離。構(gòu)建距離累計矩陣D∈Rm×n，滿足：

1≤i≤m,1≤j≤n

(4)

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

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

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

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

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

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

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

2 基于動態(tài)時間彎曲的精度估計算法設(shè)計

2.1 序列預(yù)篩選技術(shù)

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

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

(5)

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

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

N1/f1=N2/f2

(6)

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

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

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

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

(7)

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

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

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

2.2 下界加速技術(shù)

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

本文選取LB_Kim下界作為判斷指標，LB_Kim方法是一種具有代表性的下界函數(shù)[22],其主要思想是使用兩條序列所固有的特征即序列首節(jié)點、序列尾節(jié)點、序列最大值、序列最小值，來完成這個序列表述工作，得到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中的起始點，最大值點，最小值點，終止點。根據(jù)下界定義，有：

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

(9)

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

2.3 聯(lián)合距離度量技術(shù)

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

將航跡序列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進行距離度量時可依據(jù)不同維度出廠精度進行加權(quán)，精度越高，權(quán)重越大，如下所示：

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

(13)

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

2.4 精度估計算法流程

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

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

3 實驗結(jié)果與分析

3.1 實驗數(shù)據(jù)來源與說明

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

圖3 ADS-B與雷達航跡民航實驗數(shù)據(jù)示例

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

3.2 實驗結(jié)果

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

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

whereERR=RHJ-RADSB

(14)

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

其中一組數(shù)據(jù)DTW匹配結(jié)果如圖4所示，圖3為ADS-B與航跡序列匹配結(jié)果，圖4為對應(yīng)規(guī)整路徑?？梢钥闯鲇捎贏DS-B采樣率較低，相同時間段內(nèi)采樣點較少，會有一個ADS-B點對應(yīng)多個雷達航跡點的情景出現(xiàn)；且由于采樣節(jié)拍誤差或環(huán)境噪聲原因，匹配模式不均勻，每個ADS-B點對應(yīng)的航跡點數(shù)不一致。

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

圖5 雷達精度指標比對結(jié)果

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

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

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

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

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

表1 距離精度計算誤差 m

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

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

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

3.3 算法分析與驗證

3.3.1 篩選加速技術(shù)驗證

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

表4 數(shù)據(jù)篩選加速技術(shù)驗證結(jié)果均值

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

3.3.2 聯(lián)合度量技術(shù)驗證

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

圖6 序列規(guī)整路徑匹配關(guān)系結(jié)果

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

4 結(jié)束語

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

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