一种抑制DPA评价函数扩散的方法*

王硕，张奕群

(北京电子工程总体研究所，北京 100854)

一种抑制DPA评价函数扩散的方法*

王硕，张奕群

(北京电子工程总体研究所，北京 100854)

传统DPA算法在跟踪目标的过程中存在评价函数的扩散现象，即目标周围的评价函数会被“抬高”，形成以目标所在位置为顶点的“目标锥”。若目标相距较近，各目标锥会相互融合，导致DPA算法难以有效地将全部目标检测出来。且经研究发现，目标的信噪比越高、或检测时间越长，扩散的程度就越大，故抑制各目标(特别是较高信噪比目标)的扩散很有必要。为此，提出了一种对评价函数扩散的抑制方法，目标信噪比越高，该方法对扩散的抑制效果越显著。仿真结果表明，采用新方法后目标周围评价函数的扩散程度相比传统DPA算法有了明显减弱，提高了DPA算法检测密集目标的能力。

动态规划算法；多目标；检测；跟踪；评价函数；扩散抑制

0 引言

动态规划法(dynamic programming algorithm，DPA)是一种有效的低信噪比目标检测方法，该方法在对原始图像中所有潜在目标的跟踪过程中，逐渐找到目标并获得目标轨迹。DPA最初由Bellman提出[1]，随后Larson及Viterbi等人将它应用于信号处理和最优估计[2-5]。Barniv率先将该算法作为一种低信噪比目标的检测方法提出来，并对算法的跟踪性能进行了详尽分析[6-8]。在此之后，Arnold和Tonission等人分别对DPA算法加以修改和完善，使之具有更好的检测性能或更易于工程实现[9-16]。

在研究中发现，由于DPA搜索目标的过程是依逆时间方向进行的，故在搜索过程中，噪声会不断的“依附”在目标轨迹上，导致算法的评价函数出现以目标为中心的扩散现象，形成一个个“目标锥”。若目标相距较近，目标锥会相互融合，其中规模较小的会被“吞并”，使目标锥的个数减少，这样算法很难把所有的目标都检测出来[15]。

在目标锥的形成过程中，算法若能“主动”地对目标周围的评价函数扩散加以抑制，就会减小较弱目标锥被吞并的可能性，改善算法对密集目标的检测能力，故研究一种在检测过程中抑制扩散的办法很有必要。为此，本文提出了一种新的抑制评价函数扩散的方法，可在检测过程中“主动”对目标周围评价函数的扩散加以抑制，以提高DPA算法检测多目标的实际性能。

1 DPA目标检测算法

考虑一组连续n帧的分辨率为M×M的灰度图像，k时刻的测量矩阵z(k)可定义为

z(k)={zij(k)}，

(1)

式中：1≤i,j≤M；zij(k)为像元(i,j)的测量值，

(2)

式中：nij(k)为测量噪声；a(k)为目标幅值。

定义Θ(n)为连续n个时刻的状态θ(k)(1≤k≤n)的集合，即

Θ(n)={θ(1),θ(2),…,θ(n)}，

(3)

则目标的检测问题可描述为：给定连续n帧图像的测量值Z(n)，其中

Z(n)={z(1),z(2),…,z(n)}.

(4)

以Tonission的DPA为例[10]，其实现过程如下：

(1) 初始化

对任意像元(i,j)处的θ(1)，定义其评价函数s(θ(1))为

s(θ(1))=zij(1).

(5)

(2) 递归过程

当2≤k≤n，对所有θ(k)，其评价函数

(6)

式中：集合R由所有可能转移到θ(k)的θ(k-1)构成，以图1为例。在一个采样间隔内，目标在像平面的移动距离是有上限的，若将它记为lmax，则能转移到θ(k)的θ(k-1)均位于图中灰色区域R内。

(3) 终止

选取

(7)

为n时刻DPA对目标的估计，其中VT为检测门限。

图1 状态转移区域Fig.1 State transition area

图2 评价函数扩散的原因Fig.2 Reason of MF scattering

同时检测多个目标时，若目标相距很近，各目标由扩散所形成的目标锥会相互融合，其中规模较小的会被吞并以致无法被检测到，影响了算法的多目标检测能力。容易证实，评价函数扩散的程度受目标信噪比影响。在相同检测帧数内，较高信噪比目标的评价函数扩散范围更大，故它们的扩散更应先被抑制住。对一个n步DPA算法来说，由其实现过程可见，目前仅仅在第n步检测目标。若能提前将那些较高信噪比的目标检测出来，获得它们的运动规律，那么这些信息便可以被用来改进寻优过程、抑制评价函数扩散，提高算法的多目标检测能力。

2 扩散的抑制方法

下文将提出一种对评价函数扩散的抑制方法。

(8)

在得到各时刻k的全部预测区域Bi(k)后，将式(6)的寻优过程拆分为以下2个环节：

(1) 先对各Bi内的θ(k)寻优(即对图4中区域I内的θ(k)寻优)，得到若干以各θ(k)为端点的轨迹，将它们的集合记为T(k)。

图3 目标位置预测Fig.3 Target position prediction

(2) 再对所有剩余的θ(k)寻优(即对图4中区域II内的θ(k)寻优)。在寻优过程中，确保各θ(k)的最优轨迹与T(k)中任意轨迹的重合度不得大于α(轨迹的重合度是指两条轨迹的重合部分占整条轨迹的比例，α=1时轨迹完全重合，α=0则两轨迹独立)，否则该轨迹无效，以其他次优轨迹代替，再判断重合度，依此类推。若某θ(k)始终无法寻得有效轨迹，则对该θ(k)初始化，令其评价函数

s(θ(k))=zij(k).

(9)

在这2个环节中，前一个确保了那些已被检测出来目标不会丢失，后一个使DPA算法能够对这些目标的评价函数扩散加以抑制，以提高算法检测多目标的能力。

至此，将上述扩散抑制方法的实现流程加以归纳，如表1所示。

表1 扩散抑制方法的实现流程Table 1 Realization of MRMFS

3 仿真分析

下面先通过仿真，以检测单目标为例，验证MRMFS对目标周围评价函数扩散的抑制能力。

仿真场景设置如下。传感器的分辨率为64×64，背景噪声n(k)～N(0,1.52)，目标幅值a(k)=5，且做帧间移动一个像元的匀速直线运动。DPA的搜索区域R和目标的预测区域Bi均取为由3×3像元构成。

图5给出检测步数k=15时传统DPA算法的评价函数，其中目标位于评价函数的峰值处。可以看到，受扩散影响，目标周围的评价函数也被“抬高”了，影响范围大致为15×15个像元。相比而言，由图6，若取扩散抑制方法的轨迹重合度α=0.2，则在相同步数内，在保留图5中评价函数峰值的同时，评价函数的扩散被限制在了2×2像元的范围内，扩散范围减小了98%，近于将目标“纯粹”地选择出来，达到了十分理想的评价函数抑制效果。

图4 目标预测区域Fig.4 Prediction region of target

图5 传统DPA的评价函数Fig.5 The merit function of traditional DPA

接下来，验证本文扩散抑制方法对DPA的多目标检测性能带来的改善。

考虑2个目标相互接近时的情况，它们的幅值均为a(k)=5，且其帧间移动距离均为一个像元。当k=15时两目标分别位于(35,34)和(35,40)处，如图7所示。分别以采用扩散抑制方法前后的DPA算法对这2个目标进行检测，并在k=15时输出它们的评价函数。

图6 基于扩散抑制的评价函数Fig.6 MRMFS based merit function

图7 目标的运动情况Fig.7 Situation of target movement

图8为传统DPA的检测结果。由于两目标在k=15时相距很近，目标2的目标锥几乎完全被“吞没”，致使从评价函数图像上仅能分辨出一个峰值，即DPA此时仅能够直接检测到一个目标。反观图9，由于对评价函数的扩散加以抑制，k=15时两目标锥完全独立，使我们可以完整且准确地将2个目标检测出来，体现出该方法检测密集目标时的优越性。

图8 传统DPA算法的评价函数Fig.8 Merit function of traditional DPA

图9 基于扩散抑制方法的评价函数Fig.9 MRMFS based merit function

4 结束语

本文提出了一种抑制DPA算法评价函数扩散的方法。通过分步设置检测门限，该方法能及时有效地将目标分批分次的检测出来，并利用它们的运动规律对DPA算法目标周围评价函数的扩散进行抑制，减小了目标锥之间融合的可能性，提高了DPA算法检测密集目标的能力。仿真结果表明，扩散抑制方法使目标周围评价函数的扩散程度相比传统DPA算法有了明显地减弱，目标锥之间融合的可能性显著降低，提高了DPA算法检测密集目标的能力。

[1] BELLMAN R. Dynamic Programming [M]. Princeton University Press, 1957.

[2] LARSON R E, PESCHON J. A Dynamic Programming Approach to Trajectory Estimation [J]. IEEE Trans. on Automatic Control, 1966, 11(3): 537-540.

[3] VITERBI A J. Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm [J]. IEEE Trans. on Information Theory, 1967(3):260-269.

[4] VITERBI A J, ODENWALDER J P. Further Result on Optimal Decoding of Convolutional Codes [J]. IEEE Trans. on Information Theory, 1969(15):732-734.

[5] VITERBI A J. Convolutional Codes and Their Perform-

ance in Communication Systems [J]. IEEE Trans. on Communication Technology, 1971, 19(5): 751-772.

[6] BLACKMAN S, POPOLI R. Design and Analysis of Modern Tracking systems [M]. Artech House, 1999.

[7] BARNIV Y. Dynamic Programming Solution for Detecting Dim Moving Targets [J]. IEEE Trans. on Aerospace and Electronic Systems, 1985, 21(1): 144-156.

[8] BARNIV Y, KELLA O. Dynamic Programming Solution for Detecting Dim Moving Targets Part II:Analysis [J]. IEEE Trans. on Aerospace and Electronic Systems, 1987, 23(6): 776-788.

[9] ARNOLD J, SHAW S, PASTERNACK H. Efficient Target Tracking Using Dynamic Programming [J]. IEEE Trans. on Aerospace and Electronic Systems, 1993, 29(1): 44-56.

[10] TONISSEN S M, EVANS R.J. Performance of Dynamic Programming Techniques for Track-Before-Detect [J]. IEEE Trans. on Aerospace and Electronic Systems, 1996, 32(4): 1440-1451.

[11] JOHNSTON L A., KRISHNAMURTHY V. Performance Analysis of a Dynamic Programming Track Before Detect Algorithm [J]. IEEE Trans. on Aerospace and Electronic Systems, 2002, 38(1): 228-242.

[12] NICHTERN O, ROTMAN S R. Tracking of a Point Target in an IR Sequence Using Dynamic Programming Approach [C]∥ IEEE Convention of Electrical and Electronics Engineers, 2006: 265-269.

[13] BUZZI S, LOPS M, VENTURINO L,et al. Track-Before-Detect Procedures in a Multi-Target Environment [J]. IEEE Trans. on Aerospace and Electronic Systems, 2008, 44(3): 1135-1150.

[14] PULFORD G W, LA SCALA B F. Multihypothesis Viterbi Data Association: Algorithm Development and Assessment [J]. IEEE Trans. on Aerospace and Electronic Systems, 2010, 46(2): 583-609.

[15] YI W, KONG L, YANG J, et al. A tracking Approach Based on Dynamic Programming Track-before-Detect [C]∥IEEE Radar Conference, 2009.

[16] YI W, MORELANDE M R, KONG L, et al. Multi-Target Tracking via Dynamic-Programming Based Track-Before-Detect [C]∥ IEEE Radar Conference, 2012.

Method for Restraining Merit Function Scattering Based on Dynamic Programming Algorithm

WANG Shuo, ZHANG Yi-qun

(Beijing Institute of Electronic System Engineering, Beijing 100854, China)

The merit function (MF) of traditional dynamic programming algorithm (DPA) scatters during target tracking, and MFs around target arises forming a “MF group”. Once in dense multi-target environment, the MF groups are merged, which makes the DPA hardly detect all targets successfully. Researches show that, the higher the signal-to-noise ratio (SNR) of a target or the longer a detecting period is, the more a scattering will be. Thus, restraining the MF scattering of targets, especially of higher SNR targets, is necessary. A novel method is presented for restraining MF scattering (MRMFS), especially the scattering of higher SNR targets. Simulation results show that, the scattering of MRMFS is reduced, indicating that the performance of multi-target detection is improved with this method.

dynamic programming algorithm; multi-target; detection; tracking; merit function; scattering restrain

2014-12-31；

2015-01-13

有

王硕(1987-)，男，辽宁丹东人。博士生，主要研究方向为目标检测与识别。

通信地址：100854 北京142信箱30分箱 E-mail：danielws@163.com

10.3969/j.issn.1009-086x.2015.04.025

TN911.73

A

1009-086X(2015)-04-0150-05