Dynamic programming track-before-detect algorithm based on exponential smoothing method
-
摘要: 针对传统动态规划检测前跟踪(Dynamic Programming Track-Before-Detect, DP-TBD)算法在低信噪比(Signal to Noise Ratio, SNR)环境下跟踪性能较差以及容易出现团聚效应的问题, 提出一种基于指数平滑法的DP-TBD算法.该算法的创新之处在于:利用指数平滑法预测当前帧的目标状态, 当对当前帧代价函数进行优化时利用预测的目标状态对前一帧搜索窗内的代价函数进行加权.仿真结果表明, 文中所提算法能够有效抑制团聚效应, 且算法的检测性能和跟踪性能都比传统算法有所提高, 并且信噪比越低, 性能提高越明显.因此文中算法相对于传统算法来说更适用于低信噪比环境.Abstract: Accounting for the issues of bad tracking performance and agglomeration phenomenon of conventional dynamic programming track-before-detect (DP-TBD) algorithm in low signal to noise ratio(SNR) situation, a DP-TBD algorithm based on exponential smoothing method is proposed in this paper. The innovation lies in an algorithm that the merit function in search window at previous frame is weighted with the predicted target state which is obtained by exponential smoothing method while the merit function at current frame is optimized. Simulation results indicate that the proposed algorithm can mitigate the agglomeration phenomenon efficiently and has better detection and tracking performance over the conventional algorithm. Furthermore, the lower the SNR is, the greater the improvement will be. Therefore, the proposed algorithm is more applicable in the low SNR environment than the conventional ones.
-
引言
检测前跟踪(Track-Before-Detect, TBD)是低信噪比(Signal to Noise Ratio, SNR)情况下对微弱目标进行检测和跟踪的一种技术.相对于传统检测方法而言, TBD并不是通过每帧设置门限来检测目标, 而是将多帧数据进行联合处理, 经过积累后得到目标检测结果的同时给出目标的轨迹.由于单帧并没有过门限处理, TBD保留了更多的目标信息.所以说TBD的本质是通过时间积累来提高信噪比.目前TBD的主要实现方法有:三维匹配滤波、霍夫变换、多阶假设检验、动态规划、粒子滤波等[1-3].
动态规划检测前跟踪(Dynamic Programming TBD, DP-TBD)算法已广泛应用于红外弱目标检测[4-5], 目前也正应用于雷达系统中[6-10].传统算法在进行状态搜索时, 只是在前一帧的搜索窗内寻找代价函数最大者, 这种方式会使能量扩散到目标真实状态附近, 称为团聚效应.团聚效应会对最终的目标检测造成困难.文献[11]将目标后验概率比的对数作为代价函数, 本质上就是在状态搜索过程中加入状态转移惩罚项, 利用目标运动特征对搜索状态进行调整, 但该方法假设目标状态信息在时间上独立且各个状态之间也是独立的, 这种假设在实际雷达系统中是不容易成立的.文献[12]根据目标在相邻帧间运动不会倒退的原理, 提出一种方向加权算法, 改进了算法性能, 但当帧间时间间隔变大时算法的性能会急速下降.文献[13]在原来可能状态转移的基础上又对后续状态进行了估计, 因此可以减少目标强度起伏的影响, 提高了关联精度.文献[14]在第k帧观测值与第k-1帧窗内某观测值累加的基础上, 沿此方向再与第k-2帧区域内的代价函数最大者进行累加, 并记录累加后最优代价函数值所对应的前两帧的位置, 用于回溯航迹, 但这种方法对目标的机动性很敏感.
文中首先利用指数平滑法进行状态预测, 当对目标的每个可能状态进行状态搜索时, 利用预测状态与当前帧状态所对应的距离差对前一帧搜索窗内的代价函数加权.当状态预测精度足够高时, 目标前一帧真实状态所对应的预测状态就会贴近当前帧状态, 因此前一帧真实状态处的代价函数就会获得较大的权值, 从而提高了被关联的概率.文中给出所提算法检测和跟踪性能的仿真结果, 并与传统算法进行了比较, 验证了算法性能.
1 传统动态规划检测前跟踪算法
假设雷达每帧数据由M×N个分辨单元组成, 第k帧观测数据可表示为Zk={zk(x, y)|x=1, 2, …, N; y=1, 2, …, M}, 其中zk(x, y)表示第k帧(x, y)处的观测值:
zk(x,y)={Ak+nk(x,y)有目标nk(x,y)无目标, (1) Ak表示目标幅度；nk(x, y)表示(x, y)处的观测噪声幅度.信噪比RSN由下式计算:
RSN=20lgAN0, (2) A和N0分别表示目标和噪声幅度值.总的观测数据表示为Z={Z1, Z2, …, ZK}, K为数据帧数.假设目标在第k帧的状态xk=(x, y, ˙x,˙y), (x, y)、(˙x,˙y)分别表示目标的位置和速度, 则目标的轨迹可表示为X=(x1, x2, …, xk, …, xK), 假设目标的运动模型为
{\mathit{\boldsymbol{x}}_k} = \left[ {\begin{array}{*{20}{c}} 1&0&1&0\\ 0&1&0&1\\ 0&0&1&0\\ 0&0&0&1 \end{array}} \right]{\mathit{\boldsymbol{x}}_{k - 1}}. (3) DP-TBD的目的就是利用数据Z估计目标轨迹X.根据弹道积分原理, 目标沿轨迹上积累的能量必定大于沿非轨迹上积累的能量.因此DP-TBD问题可以归结为一个K维优化问题.根据动态规划最优化原理, 不论过去的状态和优化结果如何, 对前面的优化过程所形成的状态而言, 余下的优化过程必须满足最优化策略, 所以上述K维优化问题可以转化为K个一维优化问题:
{V_k}\left( {{\mathit{\boldsymbol{x}}_k}} \right) = {z_k}\left( {{\mathit{\boldsymbol{x}}_k}} \right) + \mathop {\max }\limits_{{\mathit{\boldsymbol{x}}_{k - 1}} \in {U_{{\mathit{\boldsymbol{x}}_k}}}} \left[ {{V_{k - 1}}\left( {{\mathit{\boldsymbol{x}}_{k - 1}}} \right)} \right]; (4) {\mathit{\Psi }_k}\left( {{\mathit{\boldsymbol{x}}_k}} \right) = {\rm{arg}}\mathop {\max }\limits_{{\mathit{\boldsymbol{x}}_{k - 1}} \in {U_{{\mathit{\boldsymbol{x}}_k}}}} \left[ {{V_{k - 1}}\left( {{\mathit{\boldsymbol{x}}_{k - 1}}} \right)} \right]. (5) 式中: Vk(xk)表示第k帧状态xk的代价函数; Uxk表示可能转移到xk的状态xk-1的集合, 一般取Uxk={(x, y)|-v≤x′-x≤v; -v≤y′-y≤v; }, (x, y)、(x′, y′)分别表示第k-1和第k帧的状态位置, v由目标最大速度决定; Ψk(xk)是航迹追踪函数, 记录转移到xk的xk-1.当K帧数据积累结束后, 利用门限VT检测目标, 寻找{{\mathit{\boldsymbol{\hat x}}}_k}={xk：VK(xk)＞VT}, 利用{{\mathit{\boldsymbol{\hat x}}}_{k-1}}=Ψk(xk)(k=K, K-1, …, 1)进行航迹回溯, 得到目标航迹X=({{\mathit{\boldsymbol{\hat x}}}_1}, {{\mathit{\boldsymbol{\hat x}}}_2}, \cdots, {{\mathit{\boldsymbol{\hat x}}}_k}, \cdots, {{\mathit{\boldsymbol{\hat x}}}_K}).
2 基于指数平滑的DP-TBD算法
2.1 基于预测值加权的DP-TBD算法
针对传统DP-TBD算法在低SNR情况下容易出现航迹关联错误, 难以回溯真实的目标航迹这一问题, 文中提出一种加权算法:利用式(4)优化第k帧任意Vk(xk)时, 针对Uxk中每个xk-1, 首先运用指数平滑法获取对应的预测值{{\mathit{\boldsymbol{\tilde x}}}_k}, 然后根据{{\mathit{\boldsymbol{\tilde x}}}_k}和xk所对应的距离差对Vk-1(xk-1)进行加权, 即将式(4)更新为
{V_k}\left( {{\mathit{\boldsymbol{x}}_k}} \right) = {z_k}\left( {{\mathit{\boldsymbol{x}}_k}} \right) + \mathop {\max }\limits_{{\mathit{\boldsymbol{x}}_{k - 1}} \in {U_{{\mathit{\boldsymbol{x}}_k}}}} \left[ {w\left( {{\mathit{\boldsymbol{x}}_{k - 1}},{\mathit{\boldsymbol{x}}_k}} \right){V_{k - 1}}\left( {{\mathit{\boldsymbol{x}}_{k - 1}}} \right)} \right], (6) w\left( {{\mathit{\boldsymbol{x}}_{k - 1}},{\mathit{\boldsymbol{x}}_k}} \right) = \frac{1}{{1 + \sqrt {{{\left( {{{\mathit{\boldsymbol{\tilde x}}}_k} - {\mathit{\boldsymbol{x}}_k}} \right)}^2}} }}. (7) 2.2 指数平滑法
为了获得高精度预测值, 文中采用线性二次指数平滑法[15]进行状态预测, 由于线性二次指数平滑法也是递归地进行预测, 因此既不需要存储大量数据也可以很好地加入动态规划优化过程.
该方法分为平滑和预测两个阶段.首先平滑当前帧的状态, 平滑公式如下:
\left\{ \begin{array}{l} S_{k - 1}^1\left( {{\mathit{\boldsymbol{x}}_{k - 1}}} \right) = \alpha {\mathit{\boldsymbol{x}}_{k - 1}} + \left( {1 - \alpha } \right)S_{k - 2}^1\left( {{\mathit{\boldsymbol{x}}_{k - 2}}} \right)\\ S_{k - 1}^2\left( {{\mathit{\boldsymbol{x}}_{k - 1}}} \right) = \alpha S_{k - 1}^1\left( {{\mathit{\boldsymbol{x}}_{k - 1}}} \right) + \left( {1 - \alpha } \right)S_{k - 2}^2\left( {{\mathit{\boldsymbol{x}}_{k - 2}}} \right) \end{array} \right.. (8) 式中: Sk-11 (xk-1)和Sk-12 (xk-1)分别为第k-1帧状态xk-1的第一次和第二次平滑结果; xk-2是转移到xk-1的状态; α∈(0, 1)是平滑系数, α越大表示越信任当前的状态, 越小表示越信任前一帧的平滑结果.然后利用下式进行预测:
{{\mathit{\boldsymbol{\tilde x}}}_k}\left( {{\mathit{\boldsymbol{x}}_{k - 1}}} \right) = {a_{k - 1}} + {b_{k - 1}}. (9) 式中:
{a_{k - 1}} = 2S_{k - 1}^1\left( {{\mathit{\boldsymbol{x}}_{k - 1}}} \right) - S_{k - 1}^2\left( {{\mathit{\boldsymbol{x}}_{k - 1}}} \right);\\ {b_{k - 1}} = \frac{\alpha }{{1 - \alpha }}\left( {S_{k - 1}^1\left( {{\mathit{\boldsymbol{x}}_{k - 1}}} \right) - S_{k - 1}^2\left( {{\mathit{\boldsymbol{x}}_{k - 1}}} \right)} \right). 由式(9)可知, 想要获得{{\mathit{\boldsymbol{\tilde x}}}_k} (xk-1), 只需xk-1和k-1帧的平滑值Sk-11 (xk-1)和Sk-12 (xk-1), 因此只需要在TBD递归过程中引入变量Sk1和Sk2, 便可以实现指数平滑预测.
2.3 基于指数平滑的DP-TBD算法实现流程
1) 初始化(k=1)
对于所有x1, 令
{V_1}\left( {{\mathit{\boldsymbol{x}}_1}} \right) = {z_1}\left( {{\mathit{\boldsymbol{x}}_1}} \right); {\mathit{\Psi }_1}\left( {{\mathit{\boldsymbol{x}}_1}} \right) = 0; S_1^1\left( {{\mathit{\boldsymbol{x}}_1}} \right) = S_1^2\left( {{\mathit{\boldsymbol{x}}_1}} \right) = {\mathit{\boldsymbol{x}}_1}. 2) 初始预测(k=2)
对于任意的x2, 运用式(4)、(5)得到相应的代价函数和航迹追踪函数, 然后运用式(8)计算第2帧平滑值:
\left\{ \begin{array}{l} S_2^1\left( {{\mathit{\boldsymbol{x}}_2}} \right) = \alpha {\mathit{\boldsymbol{x}}_2} + \left( {1 - \alpha } \right)S_1^1\left( {{\mathit{\Psi }_2}\left( {{\mathit{\boldsymbol{x}}_2}} \right)} \right)\\ S_2^2\left( {{\mathit{\boldsymbol{x}}_2}} \right) = \alpha S_2^1\left( {{\mathit{\boldsymbol{x}}_2}} \right) + \left( {1 - \alpha } \right)S_1^2\left( {{\mathit{\Psi }_2}\left( {{\mathit{\boldsymbol{x}}_2}} \right)} \right). \end{array} \right. (10) 3) 循环递推(3≤k≤K)
将前一帧平滑值代入式(9)预测当前帧状态, 然后将式(7)计算出的权值代入式(6)、(5)计算代价函数和航迹追踪函数, 最后计算当前帧平滑值.
4) 目标检测
当积累K帧数据后, 对于任意状态xK, 利用以下方法进行目标检测:
\left\{ {\begin{array}{*{20}{l}} {{V_K}\left( {{\mathit{\boldsymbol{x}}_K}} \right) \ge {V_T}}&{{\mathit{\boldsymbol{x}}_K}{\rm{属于目标状态}}}\\ {{V_K}\left( {{\mathit{\boldsymbol{x}}_K}} \right) < {V_T}}&{{\mathit{\boldsymbol{x}}_K}{\rm{不属于目标状态}}} \end{array}} \right., (11) 其中门限由下式决定[13]
{V_T} = - {b_n} \cdot \ln \left( { - \ln \left( {1 - {p_{\rm{d}}}} \right)} \right) + {a_n}. (12) 式中: pd为检测概率;
{a_n} = \mu + \sigma \left[ {{{\left( {2\lg n} \right)}^{1/2}} - \frac{1}{2}\frac{{\left( {\lg \left( {\lg n} \right) + \lg \left( {4\pi } \right)} \right)}}{{{{\left( {2\lg n} \right)}^{1/2}}}}} \right]; (13) {b_n} = \frac{{{{\left( {2\lg n} \right)}^{1/2}}}}{\sigma },n = M \times N \times {v^2}; (14) 式(13)、(14)中, M和N分别为x、y方向的距离单元数; v为两帧之间目标可能跨越的距离单元数; μ、σ分别为目标所在轨迹积累K帧的代价函数的均值和方差.
5) 航迹回溯
运用
{\mathit{\boldsymbol{x}}_{k - 1}} = {\mathit{\Psi }_k}\left( {{\mathit{\boldsymbol{x}}_k}} \right)\;\;\left( {k = K,K - 1, \cdots ,1} \right) (15) 进行航迹回溯得到目标轨迹X=(x1, x2, …, xK).
3 仿真结果及分析
为验证文中算法的性能, 将文中算法和传统算法进行了比较.假设雷达观测区域为{(x, y)|1.5×105≤x≤1.55×105; 1.2×105≤y≤1.25×105}, 每帧接收数据大小为50×50, x轴和y轴分辨单元均分100 m, 总共有20帧接收数据, 相邻帧的时间间隔为1 s.设目标初始状态x1=(1.51×105, 1.21×105, 100, 100), 在观测区域内做匀速直线运动, 观测噪声为参数为1的瑞利分布.文中利用目标检测概率和跟踪概率来验证算法性能.检测概率表示经过20帧的数据积累后检测到目标的概率, 允许误差为一个分辨单元.跟踪概率表示检测到目标并且经过航迹回溯后每帧的状态都和目标真实状态相差在一个分辨单元内的概率.仿真中进行100次蒙特卡罗实验.
图 1为传统算法和文中所提算法在SNR为6 dB时经过20帧积累处理后得到的代价函数比较图, 图 1(a)为传统算法代价函数, 图 1(b)为文中所提算法代价函数.比较可知, 传统算法在目标真实位置附近的代价函数同样也很高, 存在明显的团聚效应, 在检测目标时会对门限的设置造成困难, 而所提算法则有效地抑制了这种现象, 可以更加准确地检测目标真实状态.
图 2为传统算法和所提算法的检测概率随SNR变化的比较图.由图可知:在SNR相同的情况下, 文中提出算法的检测概率都要高于传统算法; 当SNR高于7 dB时, 两种算法性能差距不大; 当SNR较低为4时, 文中算法检测概率比传统算法高出0.3.可见SNR越低, 文中算法检测优势越明显.
图 3为SNR为4 dB时传统算法与文中算法的跟踪效果比较图.由图可知, 传统算法有多处出现关联偏差而文中算法则较准确地恢复了目标航迹.因此在低SNR环境下, 文中算法拥有更好的跟踪性能.
图 4为传统的DP-TBD算法和文中算法的跟踪概率随SNR的变化比较图.在SNR相同的情况下, 文中提出算法的跟踪概率都要优于传统算法.当SNR为7 dB时, 文中算法跟踪概率只比传统算法高0.05, 但当SNR为4 dB, 跟踪概率差距扩大到0.3, 可见在低SNR情况下, 传统算法的跟踪概率很低, 而文中算法仍然具有较好的跟踪性能.
4 结论
针对传统DP-TBD算法在低信噪比情况下容易出现关联错误和团聚效应的问题, 提出了一种基于指数平滑的加权DP-TBD算法.文中方法的创新之处在于:运用指数平滑法预测目标状态, 再利用预测的目标状态加权前一帧的代价函数.由于充分利用了目标的运动特性, 文中算法比传统算法具有更好的检测和跟踪性能.仿真结果表明, 文中所提算法的检测性能和跟踪性能都比传统算法有一定的提高, 且SNR越低, 文中算法的优势越明显.因此文中算法比传统算法更适用于低信噪比环境.但当目标机动性较强, 指数平滑法出现较大偏差时, 算法性能会随之恶化.
-
[1] REED I, GAGLIARDI R, SHAO H. Application of three-dimensional fitering to moving target detectin[J]. IEEE rransactions on aerospace and electronic systems, 1983, 19(6): 898-905. http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4102882
[2] 曾建奎, 何子述, 刘红明.一种基于改进Hough变换的雷达检测方法[J].电波科学学报, 2008, 23(5): 838-841. doi: 10.3969/j.issn.1005-0388.2008.05.008 ZENG J K, HE Z S, LIU H M. Improved detection algorithm for radar based on Hough transform[J]. Chinese journal of radio science, 2008, 23(5): 838-841. (in Chinese) doi: 10.3969/j.issn.1005-0388.2008.05.008
[3] 鲜海滢, 傅志中, 李在铭.强噪声背景下红外微弱目标集成检测[J].电波科学学报, 2008, 23(3): 438-442. http://www.cnki.com.cn/Article/CJFDTotal-DBKX200803009.htm XIAN H Y, FU Z Z, LI Z M. Integration detection algorithm of infrared small dim moving target based on strong complex noise[J]. Chinese journal of radio science, 2008, 23(4): 438-442. (in Chinese) http://www.cnki.com.cn/Article/CJFDTotal-DBKX200803009.htm
[4] BARNIV Y. Dynamic programming solution for detecting dim moving targets[J]. IEEE transactions on aerospace and electronic systems, 1985, 21(1):144-156. doi: 10.1109-TAES.1985.310548/
[5] BARNIV Y, KELLA O. Dynamic programming solution for detecting dim moving targets Part Ⅱ: analysis[J]. IEEE transactions on aerospace and electronic systems, 1987, 23(6):776-788. http://www.ams.org/mathscinet-getitem?mr=926002
[6] ORLANDO D, VENTURINO L, LOPS M, et al. Track-before-detect strategies for STAP radar[J]. IEEE transactions on singal processing, 2010, 58(2):933-938. doi: 10.1109/TSP.2009.2032991
[7] BUZZI S, LOPS M, VENTURINO L. Track-before-detect procedures for early detection of moving target from airborne radars[J]. IEEE transactions on aerospace and electronic systems, 2005, 41(3):937-954. doi: 10.1109/TAES.2005.1541440
[8] GAO F, ZHANG F F, ZHU H, et al. An improved TBD algorithm based on dynamic programming for dim SAR target detection[C]//12th International Conference on Signal Processing. Hangzhou, 19-23 Oct, 2014: 1880-1884. http://ieeexplore.ieee.org/xpl/articleDetails.jsp?tp=&arnumber=7015319
[9] LIU R, YI W, KONG L J, et al. An efficient multi-target track-before-detect algorithm for low PRF surveillance radars[C]//12th International Conference on Singal Processing, 2014: 1273-1277. http://ieeexplore.ieee.org/xpls/icp.jsp?arnumber=6875794
[10] 战立晓, 汤子跃, 易蕾, 等.基于广义似然比检验-动态规划的检测前跟踪算法[J].电波科学学报, 2013, 28(1): 190-196. http://www.cjors.cn/CN/abstract/abstract612.shtml ZHAN L X, TANG Z Y, YI L, et al. Novel GLRT-DP based TBD algorithm in range-doppler domain[J]. Chinese journal of radio science, 2013, 28(1): 190-196. (in Chinese) http://www.cjors.cn/CN/abstract/abstract612.shtml
[11] ARNOLD J, SHAW S, PASTERNACK H. Efficient target tracking using dynamic programming[J]. IEEE transactions on aerospace and electronic systems, 1993, 29(1):44-56. doi: 10.1109/7.249112
[12] 陈尚峰, 陈华明, 卢焕章.基于加权动态规划和航迹关联的小目标检测技术[J].国防科技大学学报, 2003, 25(2): 46-50. doi: 10.3969/j.issn.1001-2486.2003.02.011 CHEN S F, CHEN H M, LU H Z. Detection and tracking of dim targets based on dynamic programming and track matching[J]. Journal of national univeisity of defense technology, 2003, 25(2): 46-50. (in Chinese) doi: 10.3969/j.issn.1001-2486.2003.02.011
[13] 孙立宏, 王俊.用于雷达弱小目标检测的改进TBD算法[J].雷达科学与技术, 2004, 12(8): 292-295. http://d.old.wanfangdata.com.cn/Periodical/ldkxyjs200704012 SUN L H, WANG J. An improved track-before-detect algorithm for radar weak target detection[J]. Radar science and technology, 2004, 12(8): 292-295. (in Chinese) http://d.old.wanfangdata.com.cn/Periodical/ldkxyjs200704012
[14] 吴卫华, 王首勇, 杜鹏飞.一种基于目标状态关联的动态规划TBD算法[J].空军雷达学院学报, 2011, 25(6): 415-418. doi: 10.3969/j.issn.1673-8691.2011.06.007 WU W H, WANG S Y, DU P F. A dynamic programming track-before-detect algorithm based on targets state association[J]. Journal of air force radar academy, 2011, 25(6): 415-418. (in Chinese) doi: 10.3969/j.issn.1673-8691.2011.06.007
[15] 张忠平.指数平滑法[M].北京:中国统计出版社, 1996, 36-49. -
期刊类型引用(4)
1. 钟钰彬，杨鹏，窦磊. 基于纵横比自适应的相关滤波跟踪算法. 电子学报. 2024(06): 2112-2122 . 
百度学术
2. 邢浩，索继东，孙博. 改进状态转移集的动态规划检测前跟踪算法. 现代电子技术. 2020(19): 1-5 . 百度学术
3. 孟宁，史小斌，高青松，连豪，任哲毅，孙藏安. 一种机动目标动态规划检测前跟踪算法. 火控雷达技术. 2019(03): 65-70 . 百度学术
4. 汪晋，曹志亮，朱昌荣. 一种改进的外推动态规划检测前跟踪算法. 现代雷达. 2017(07): 54-57+74 . 百度学术
其他类型引用(5)
下载:
计量
- 文章访问数: 218
- HTML全文浏览量: 100
- PDF下载量: 159
- 被引次数: 9
