基于动态时间弯曲的欠时间信息雷达精度评估方法

庞 卓，詹进雄，吕永乐

(南京电子技术研究所，南京 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精度评估应用范围，具有广泛实用价值。

同时，本算法适用于离线状态下雷达精度评估，针对在线状态下雷达精度实时评估技术将后续进一步研究。