王碩，張奕群

(北京電子工程總體研究所，北京 100854)

一種抑制DPA評價函數(shù)擴散的方法*

王碩，張奕群

(北京電子工程總體研究所，北京 100854)

傳統(tǒng)DPA算法在跟蹤目標的過程中存在評價函數(shù)的擴散現(xiàn)象，即目標周圍的評價函數(shù)會被“抬高”，形成以目標所在位置為頂點的“目標錐”。若目標相距較近，各目標錐會相互融合，導致DPA算法難以有效地將全部目標檢測出來。且經(jīng)研究發(fā)現(xiàn)，目標的信噪比越高、或檢測時間越長，擴散的程度就越大，故抑制各目標(特別是較高信噪比目標)的擴散很有必要。為此，提出了一種對評價函數(shù)擴散的抑制方法，目標信噪比越高，該方法對擴散的抑制效果越顯著。仿真結(jié)果表明，采用新方法后目標周圍評價函數(shù)的擴散程度相比傳統(tǒng)DPA算法有了明顯減弱，提高了DPA算法檢測密集目標的能力。

動態(tài)規(guī)劃算法；多目標；檢測；跟蹤；評價函數(shù)；擴散抑制

0 引言

動態(tài)規(guī)劃法(dynamic programming algorithm，DPA)是一種有效的低信噪比目標檢測方法，該方法在對原始圖像中所有潛在目標的跟蹤過程中，逐漸找到目標并獲得目標軌跡。DPA最初由Bellman提出[1]，隨后Larson及Viterbi等人將它應(yīng)用于信號處理和最優(yōu)估計[2-5]。Barniv率先將該算法作為一種低信噪比目標的檢測方法提出來，并對算法的跟蹤性能進行了詳盡分析[6-8]。在此之后，Arnold和Tonission等人分別對DPA算法加以修改和完善，使之具有更好的檢測性能或更易于工程實現(xiàn)[9-16]。

在研究中發(fā)現(xiàn)，由于DPA搜索目標的過程是依逆時間方向進行的，故在搜索過程中，噪聲會不斷的“依附”在目標軌跡上，導致算法的評價函數(shù)出現(xiàn)以目標為中心的擴散現(xiàn)象，形成一個個“目標錐”。若目標相距較近，目標錐會相互融合，其中規(guī)模較小的會被“吞并”，使目標錐的個數(shù)減少，這樣算法很難把所有的目標都檢測出來[15]。

在目標錐的形成過程中，算法若能“主動”地對目標周圍的評價函數(shù)擴散加以抑制，就會減小較弱目標錐被吞并的可能性，改善算法對密集目標的檢測能力，故研究一種在檢測過程中抑制擴散的辦法很有必要。為此，本文提出了一種新的抑制評價函數(shù)擴散的方法，可在檢測過程中“主動”對目標周圍評價函數(shù)的擴散加以抑制，以提高DPA算法檢測多目標的實際性能。

1 DPA目標檢測算法

考慮一組連續(xù)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)為連續(xù)n個時刻的狀態(tài)θ(k)(1≤k≤n)的集合，即

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

(3)

則目標的檢測問題可描述為：給定連續(xù)n幀圖像的測量值Z(n)，其中

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

(4)

以Tonission的DPA為例[10]，其實現(xiàn)過程如下：

(1) 初始化

對任意像元(i,j)處的θ(1)，定義其評價函數(shù)s(θ(1))為

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

(5)

(2) 遞歸過程

當2≤k≤n，對所有θ(k)，其評價函數(shù)

(6)

式中：集合R由所有可能轉(zhuǎn)移到θ(k)的θ(k-1)構(gòu)成，以圖1為例。在一個采樣間隔內(nèi)，目標在像平面的移動距離是有上限的，若將它記為lmax，則能轉(zhuǎn)移到θ(k)的θ(k-1)均位于圖中灰色區(qū)域R內(nèi)。

(3) 終止

選取

(7)

為n時刻DPA對目標的估計，其中VT為檢測門限。

圖1 狀態(tài)轉(zhuǎn)移區(qū)域Fig.1 State transition area

圖2 評價函數(shù)擴散的原因Fig.2 Reason of MF scattering

同時檢測多個目標時，若目標相距很近，各目標由擴散所形成的目標錐會相互融合，其中規(guī)模較小的會被吞并以致無法被檢測到，影響了算法的多目標檢測能力。容易證實，評價函數(shù)擴散的程度受目標信噪比影響。在相同檢測幀數(shù)內(nèi)，較高信噪比目標的評價函數(shù)擴散范圍更大，故它們的擴散更應(yīng)先被抑制住。對一個n步DPA算法來說，由其實現(xiàn)過程可見，目前僅僅在第n步檢測目標。若能提前將那些較高信噪比的目標檢測出來，獲得它們的運動規(guī)律，那么這些信息便可以被用來改進尋優(yōu)過程、抑制評價函數(shù)擴散，提高算法的多目標檢測能力。

2 擴散的抑制方法

下文將提出一種對評價函數(shù)擴散的抑制方法。

(8)

在得到各時刻k的全部預(yù)測區(qū)域Bi(k)后，將式(6)的尋優(yōu)過程拆分為以下2個環(huán)節(jié)：

(1) 先對各Bi內(nèi)的θ(k)尋優(yōu)(即對圖4中區(qū)域I內(nèi)的θ(k)尋優(yōu))，得到若干以各θ(k)為端點的軌跡，將它們的集合記為T(k)。

圖3 目標位置預(yù)測Fig.3 Target position prediction

(2) 再對所有剩余的θ(k)尋優(yōu)(即對圖4中區(qū)域II內(nèi)的θ(k)尋優(yōu))。在尋優(yōu)過程中，確保各θ(k)的最優(yōu)軌跡與T(k)中任意軌跡的重合度不得大于α(軌跡的重合度是指兩條軌跡的重合部分占整條軌跡的比例，α=1時軌跡完全重合，α=0則兩軌跡獨立)，否則該軌跡無效，以其他次優(yōu)軌跡代替，再判斷重合度，依此類推。若某θ(k)始終無法尋得有效軌跡，則對該θ(k)初始化，令其評價函數(shù)

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

(9)

在這2個環(huán)節(jié)中，前一個確保了那些已被檢測出來目標不會丟失，后一個使DPA算法能夠?qū)@些目標的評價函數(shù)擴散加以抑制，以提高算法檢測多目標的能力。

至此，將上述擴散抑制方法的實現(xiàn)流程加以歸納，如表1所示。

表1 擴散抑制方法的實現(xiàn)流程Table 1 Realization of MRMFS

3 仿真分析

下面先通過仿真，以檢測單目標為例，驗證MRMFS對目標周圍評價函數(shù)擴散的抑制能力。

仿真場景設(shè)置如下。傳感器的分辨率為64×64，背景噪聲n(k)～N(0,1.52)，目標幅值a(k)=5，且做幀間移動一個像元的勻速直線運動。DPA的搜索區(qū)域R和目標的預(yù)測區(qū)域Bi均取為由3×3像元構(gòu)成。

圖5給出檢測步數(shù)k=15時傳統(tǒng)DPA算法的評價函數(shù)，其中目標位于評價函數(shù)的峰值處。可以看到，受擴散影響，目標周圍的評價函數(shù)也被“抬高”了，影響范圍大致為15×15個像元。相比而言，由圖6，若取擴散抑制方法的軌跡重合度α=0.2，則在相同步數(shù)內(nèi)，在保留圖5中評價函數(shù)峰值的同時，評價函數(shù)的擴散被限制在了2×2像元的范圍內(nèi)，擴散范圍減小了98%，近于將目標“純粹”地選擇出來，達到了十分理想的評價函數(shù)抑制效果。

圖4 目標預(yù)測區(qū)域Fig.4 Prediction region of target

圖5 傳統(tǒng)DPA的評價函數(shù)Fig.5 The merit function of traditional DPA

接下來，驗證本文擴散抑制方法對DPA的多目標檢測性能帶來的改善。

考慮2個目標相互接近時的情況，它們的幅值均為a(k)=5，且其幀間移動距離均為一個像元。當k=15時兩目標分別位于(35,34)和(35,40)處，如圖7所示。分別以采用擴散抑制方法前后的DPA算法對這2個目標進行檢測，并在k=15時輸出它們的評價函數(shù)。

圖6 基于擴散抑制的評價函數(shù)Fig.6 MRMFS based merit function

圖7 目標的運動情況Fig.7 Situation of target movement

圖8為傳統(tǒng)DPA的檢測結(jié)果。由于兩目標在k=15時相距很近，目標2的目標錐幾乎完全被“吞沒”，致使從評價函數(shù)圖像上僅能分辨出一個峰值，即DPA此時僅能夠直接檢測到一個目標。反觀圖9，由于對評價函數(shù)的擴散加以抑制，k=15時兩目標錐完全獨立，使我們可以完整且準確地將2個目標檢測出來，體現(xiàn)出該方法檢測密集目標時的優(yōu)越性。

圖8 傳統(tǒng)DPA算法的評價函數(shù)Fig.8 Merit function of traditional DPA

圖9 基于擴散抑制方法的評價函數(shù)Fig.9 MRMFS based merit function

4 結(jié)束語

本文提出了一種抑制DPA算法評價函數(shù)擴散的方法。通過分步設(shè)置檢測門限，該方法能及時有效地將目標分批分次的檢測出來，并利用它們的運動規(guī)律對DPA算法目標周圍評價函數(shù)的擴散進行抑制，減小了目標錐之間融合的可能性，提高了DPA算法檢測密集目標的能力。仿真結(jié)果表明，擴散抑制方法使目標周圍評價函數(shù)的擴散程度相比傳統(tǒng)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