,*

1.Shenyang Institute of Automation,Chinese Academy of Sciences,Shenyang 110179,China;2.Key Laboratory on Radar System Research and Application Technology of Liaoning Province,Shenyang 110179,China

Improved multi-target radar TBD algorithm

Xin Bi1,2,Jinsong Du1,2,Qingshi Zhang1,2,and Wei Wang1,2,*

1.Shenyang Institute of Automation,Chinese Academy of Sciences,Shenyang 110179,China;
2.Key Laboratory on Radar System Research and Application Technology of Liaoning Province,Shenyang 110179,China

Considering radar detection for multi-target recognition, a track before detect(TBD)algorithm based on Hough transform is adopted for identifying and tracking multi-target radar.By increasing the dimensions of the target characteristic parameters, the target detection and track accuracy is increased.Also,by multilevel filte ing processing,the diverging points of the echo signal are condensed,which improves the performance of identifying and tracking multiple targets.Simulation results show that compared with traditional TBD algorithms,the presented algorithm has better performance in the aspects of multi-target tracking,detecting and distinguishing.

track before detect(TBD),Hough transform,multidimensional,Kalman filte.

1.Introduction

Usually,radar echo signals contain multi-target information.Itis difficul fortraditionalmethodstoidentifysignals which involvemulti-target.The traditionalmethodto identify radar signals is to undertake detecting firstl and then processing at a single threshold and tracking finall[1,2]. Scholarshaveanalyzedthe performanceof themulti-target tracking algorithm[3,4].While simplifying the tracking data,a lot of potentially useful informationis also ignored. Targets with small signal to noise ratio(SNR)but strong motion characteristic are likely to be discarded.In order to avoid this situation,the track before detect(TBD)algorithm is put forward.

The present studies of the TBD algorithm mainly include the TBD algorithm based on projection transformation [5],the generalized likelihood ratio test[6,7],the dynamic programming(DP)[8–13] and the particle filte(PF)[14–17].The TBD method based on Hough transform is a typical algorithm based on projection transformation,which is suitable for multi-target tracking detection and does not need the advantages of a priori information of the target.This method maps target information from data space to parameter space,improves the performance of noncoherent accumulation and predicts the next expected action of targets;thus the targets can be tracked before being detected.

Carlson et al.proposedthe methodof radar target detection based on Hough transform for the firs time and gave the calculation formula of the false alarm rate and the detection probability.The work of[5,18,19]establishes the theoretical basis of Hough transform for the target detection.Chen proposed a modifie Hough transform to solve the problem which the initial track is determined slowly and the amount of calculation is large by the classical Hough transform method.The results show that the new Hough transform algorithm can improve the performance [20].Kabakchiev et al.put forward a method called porlar Hough transrform.This method is more suitable for processing of radar measured data and does not need to transform the distance-angle coordinate information into cartesian coordinates,but distance-angle coordinate information is processed directly[21].

Generally speaking,this method can effectively estimate and track the target trajectory,but it has bad performance when dealing with the following situations. (i)When the radar echo signal is weak and the echo characteristic parameters are divergent,it is prone to deviate from the forecasting trajectory,unable to effectively track targets.(ii)When radar echo is comprised of targets with similar motion parameters,it is prone to track-loss. (iii)When modifying the judgment threshold to achieve better distinguish performance,it is likely to cause some false track trajectory.

In order to solve the problems above,the multidimensional parameters judgment and multilevel filteing process are introduced into the traditional TBD algorithm.The algorithm based on multi-dimensional parameters[22–24]is proposed by Moyer and Davey.The algorithm does not give the expected results.An improved

multi-target TBD algorithm is proposed in this paper.In this algorithm,target track with tolerance limits is firstl used to lock the target,then filte the relatively diverged targets to obtain their trajectory;further,accumulate energy in TBD parameter space,when the accumulation value reaches the limit,output the target trajectory and adjust the tolerance limit and filter parameters at the same time to make the track trajectory close to actual moving trajectory.

2.Multi-target TBD algorithm

Assuming that there areLtargets,satisfying the discrete time model based on a f xed time period.The dynamics of thelth target is generally given by

whereXk,ldenotes thelth target state at time stepk.Fis the state transition function.Vk,lis the normal random noise vector of thelth target state at time stepk.Xk,lis given as

whereak,l,bk,landck,lrespectively denote the target distance,velocity and angle.

The radar multi-target TBD algorithm mainly includes two parts:

(i)multi-target track and distinction;

(ii)multi-target energy accumulation in TBD parameter space.

The initial positions of the targets are determined by multi-target track and distinction.After determining the initial positions of targets,accumulate energy in TBD parameter space;when the accumulation value reaches the limit,output the target trajectory.

2.1Multi-target track and distinction

TakeLtargets with a single characteristic parameter for example.The firs echo signal is processed and parameter vectorA(1)is obtained.

When the echo signal is obtained again,the second parameter vectorA(2)is obtained.

wherean,1,an,2,...,an,Lrepresent target characteristic parameters.When thenumberof trackingtargetsis smaller thanL,the remaining parameters are set to be zero.According to the judgment threshold,determine

(i)whether the targets correspondingto the nonzeroelements in vectorA(1)are tracked by targets inA(2)respectively;

(ii)whether there are targets inA(1)tracked by several targets inA(2)at the same time;

(iii)whether there are targets inA(1)not being tracked by targets inA(2).Then assign a new value to the old trackedtarget,removethenot-trackedtarget,mergethetarget tracked by several other targets inA(2),and the new target is reserved.A new parameter vectorIis obtained.

ForI,the targets corresponding to zero element are removedandLtargets with high credibility are retained then assign them toA(2)as a new tracked target.Sort the targets inA(2)in the order of old targets,when receiving echo signalA(3)?A(n),and compare them with the last echo signal in the same way.If the tracked target is greater than the threshold,the initial positions of the targets can be determined.

2.2Energy accumulation in parameter space

After determining the initial positions of targets,we can undertake Hough transformation on obtained characteristic parameters then go on energy accumulation on transformed parameters.Assume that targets keep moving linearly(i.e.the equation describing relationship between distance and time is linear).If the trajectory of targets is described by a linear equation,the slope of equation corresponds to the velocity of targets and the intercept of equation corresponds to the initial position of targets.

The motion equation of motion targets can be expressed as

Knowing the targets distance vectorA(i)and time vectorT(i),we can obtain the velocity vectorK(i)and the initial positionA0(i),then undertake energy accumulationin (K(i),A0(i))space.If the accumulated energy exceeds the judgment threshold,the target is valid.Based on the historical data of trajectory,we can predict the position of the target next time and recognize in subsequent target detection.

So far,the principle of traditional multi-target TBD algorithm has been described in Sections 2.1 and 2.2 in details.The following section will focus on describing the improved TBD algorithm proposed in this paper.

3.Improved TBD algorithm

As the radar echo signal has a certain uncertainty,it is inappropriate to determine the initial position of targets simply relying on single characteristic parameters;especially when the characteristic parameters are not obvious, no matter how you adjust the judgment threshold,it is difficul to achieve good tracking performance;moreover,when different targets have similar characteristic parameters,it is also hard to distinguish them.

In order to solve the above problems,we make several improvements in the traditional TBD algorithm.

(i)Increase dimensions of the characteristic parameters. Make the most of all characteristic parameters detected by radar.

(ii)Filter echo signals without obvious motion features and condense divergent trace points.

(iii)Optimize the algorithm process and the judgment threshold to achieve a low threshold while still identifying targets and a high threshold while tracking the targets.

3.1Multi-dimensional characteristic parameters

By analyzing and extracting the radar echo signal,multidimensional characteristic parameters of targets can be obtained,which mainly include targets distance,velocity,angle and so on.Based on the targets information we have acquired,we can distinguish well between differenttargets that have the same single characteristic parameter,thus increasing the discrimination degree of different targets.

The multi-dimensional characteristic parameters of targets at time stepnareA(n),B(n)andC(n),respectively denote distance,velocity and angle.Assuming the multidimensionalcharacteristicparametersof theith targetstate at time stepnrespectively asan,i,bn,iandcn,i.

Finding the minimum values of vectorsRA(n),RB(n)andRC(n)and recording the positions of the minimum values.amin,bmin,cminrepresent the minimum values andp,q,srepresent the positions.

Assuming the judgment thresholds of different characteristic parameters areAmax,BmaxandCmax.Accordingto the judgmentthreshold,determinewhich parameters (^an+1,j,^bn+1,j,^cn+1,j,wherej∈{p,q,s})belong to theith target.The process is shown in Fig.1.

Fig.1 The judgment process

3.2Filter divergent characteristic parameters

It is known that when one of the targets characteristic parameters of radar echo signals is relatively divergent,if we still use the same threshold to detect targets,it is prone to miss tracking the targets or cause large deviation from the targets’actual moving trajectory.For example,when the angle information of the targets echo signal is weak,it is difficul to determine the initial position of targets by relying on the targets angle information,so we have to go through other methods to obtain targets trajectory.In this paper,a commonlyusedαβfilte in current practice is adopted.

whereθ(n?1)represents the old recognized value last time,θ(n)is the new detected value this time,kis the filte parameter,andθ′(n)is the value after filtering By selectingkappropriately,the divergent waveform can be condensed well;however,the largerkis,the slowerθ′(n) generates,which causes a certain phase lag to condensed waveform.

3.3Algorithm process optimization and adjustable judgment threshold

The algorithm process can be summarized as follows:

(i)Detect moving targets firs and track them according to information exceeding the judgment threshold.

(ii)When having tracked a certain threshold,determine the initial position of targets and execute the TBD algorithm.

(iii)When energy accumulation in parameter space achieves the accumulation threshold,predict the output of targets and re-judge the next new value.

The process can be shown in Fig.2.

Fig.2 The fl wchart of the algorithm

Based on the above analysis,we can conclude that,in order to optimize the TBD algorithm further,the dimensions of detecting parameters are increased and the divergent characteristic parameters are filtered meanwhile,the judgment threshold is increased so that more trace points can be processed before targets are not detected.However, when the accumulation exceeds the judgment threshold, thethresholdshouldbedecreasedsothatthedetectedvalue is close to actual trajectory of targets.Moreover,filte parameters k should be assigned different values in accordance with different levels of targets being recognized to reduce phase lag caused by the filte.

4.Simulation results and analysis

The improvedTBD algorithmproposedin this paper is analyzed based on raw data of two moving targets acquired by radar.The original waveform of the data which include distance,velocity,angle and trajectory is shown in Fig.3. Fig.3(a),Fig.3(b)and Fig.3(c)are respectively the distance-time curve of targets,the velocity-time curve of targets and the angle-time curve of targets.Fig.3(d)shows the trajectory.

Fig.3 The original waveform of data

It can be seen from Fig.3 that the trajectory of targets distance and velocity is good and the trajectory of targets angle is relatively divergent.Therefore,the TBD algorithm separates the targets by the distance information. The improved TBD algorithm make several improvements to achieve better tracking performance by dimensions of characteristic parameters.

When we only take the single characteristic parameterdistance of targets into consideration,the tracking trajectory is shown in Fig.4(a).The firs target(blue)and the the second target(red)can not be separated at the intersection and the trajectory only includes the firs target(blue).The second target(red)can be tracked after a period of time. However,when we consider characteristic parameters velocity and distance of targets at the same time,the tracking trajectory is shown in Fig.4(b).Therefore,the targets canbe distinguishedbetter byincreasingthe dimensionsof characteristic parameters.

The next simulations verify that the optimization based on the improved TBD algorithm can further enhance the tracking performance.The optimization effect is reflecte in the angle and time curve.

Fig.4 Increasing the dimensions of characteristic parameters

For divergent the angle trajectories,we process by using the basic improved TBD algorithm.The trajectory of characteristic parameter-angle is shown in Fig.5.

Fig.5 Tracking trajectory with the basic improved TBD algorithm

It can be seen from Fig.5 that tracking trajectory has a relatively large fluctuations therefore,theαβfilte is adopted to filte characteristic parameter-angle in this paper.Whenαβfilte parameterkis set to be 10,the tracking trajectory is shown in Fig.6.

It can be seen from Fig.6 that the tracking fluctuation are suppressed well by using theαβfilter however,theusage of the filte also brings about phase lag,which leads to tracking trajectory deviating from actual target moving trajectory.In order to avoid this situation,the filte parameterkis made adjustable in this paper.At the beginning of targets detection,the initial value ofkis set to be 100 andkgradually decreases during targets detection.

Fig.6 Tracking trajectory withαβfilte

The tracking trajectory of targets with adjustable filte parameterkis shown in Fig.7.

It can be seen in Fig.7 that there are extra trace points (short black points)in tracking trajectory.In order to remove these points,we optimize the judgment threshold.

Fig.7 Tacking trajectory with adjusting filte parameter

We increase the judgment threshold before targets are detected and the judgmentthresholdis decreased when exceedingthe accumulatedthreshold.The tracking trajectory by adjusting the judgment threshold is shown in Fig.8.

Fig.8 Tacking trajectory with adjusting judgment threshold

5.Conclusions

This paper proposes an improved multi-target TBD algorithm.The traditional TBD algorithm is improved by increasing dimensions of the characteristic parameters,undertaking a multilevel filte and adjusting the algorithmprocess,filte parameters and judgment threshold.The simulation results show that compared with the traditional radar TBD detection algorithm,the algorithm presented in this paper has better performance in the aspect of multitargets detecting,tracking and distinguishing,which has broad application prospects.

[1]J.Stein,S.S.Blackman.Generalized correlation of multitarget track data.Aerospace and Electronic Systems,1975, 11(6):1207–1217.

[2]S.S.Blackman.Multiple-target tracking with radar applications.Dedham:Artech House Inc,1986.

[3]B.Ristic,A.Farina,M.Hernandez.Cram′er–Rao lower bound for tracking multiple targets.IEE Proceedings–Radar,Sonar and Navigation,2004,151(3):129–134.

[4]B.Ristic,B.N.Vo,D.Clark,et al.A metric for performance evaluation of multi-target tracking algorithms.IEEE Trans.on Signal Processing,2011,59(7):3452–3457.

[5]B.D.Carlson,E.D.Evans,S.L.Wilson.Search radar detection and track with the Hough transform–Part I:system concept.IEEE Trans.on Aerospace and Electronic Systems,1994, 30(1):102–108.

[6]D.Orlando,G.Ricci.Track-before-detect algorithms for targets withkinematicconstraints.IEEE Trans.onAerospace and Electronic Systems,2011,47(3):1837–1849.

[7]B.Stefano,L.Marco,V.Luca,et al.Track-before-detect procedures in a multi-target environment.IEEE Trans.on Aerospace and Electronic Systems,2008,44(3):1135–1150.

[8]L.A.Johnston,V.Krishnamurthy.Performance analysis of a dynamic programming track before detect algorithm.IEEE Trans.on Aerospace and Electronic Systems,2002,38(1): 228–242.

[9]S.M.Tonissen,R.J.Evans.Peformance of dynamic programming techniques for track-before-detect.IEEE Trans.on Aerospace and Electronic Systems,1996,32(4):1440–1451.

[10]V.Juho,J.Juha,A.K.Timo,et al.Directional filterin for sequential image analysis.IEEE Signal Processing Letters, 2008,15:902–905.

[11]E.Grossi,M.Lops,L.Venturino.A novel dynamic programming algorithm for track-before-detect in radar systems.IEEE Trans.on Signal Processing,2013,61(10):2608–2619.

[12]S.Liu,X.Chen,T.Zeng,et al.New analytical approach to detection threshold of a dynamic programming track-beforedetect algorithm.IET Proceedings–Radar,Sonar and Navigation,2013,7(7):773–779.

[13]W.Yi,L.Kong,J.Yang,et al.Student highlight:dynamic programming-based track-before-detect approach to multitarget tracking.IEEE Aerospace and Electronic Systems Magazine,2012,27(12):31–33.

[14]Y.Boers,J.N.Driessen.Multitarget particle filte track before detect application.IEE Proceedings–Radar,Sonar and Navigation,2004,151(6):351–357.

[15]H.Peter,H.Lang.A multi-rate multiple model track-beforedetect particle filte.Mathematical and Computer Modelling, 2009,49(1/2):146–162.

[16]S.Gao,D.Y.Bi,N.Wei.Small target track-before-detect algorithm based on unscented particle filteringJournal of Computer Applications,2009,29(8):2060–2064.(in Chinese)

[17]Y.Boers,J.Driessen.Multitarget particle filte track before detect application.IEE Proceedings–Radar,Sonar and Navigation,2004,151(6):351–357.

[18]B.D.Carlson,E.D.Evans,S.L.Wilson.Search radar detection and track with the Hough transform–Part II:detection statistics.IEEE Trans.on Aerospace and Electronic Systems, 1994,30(1):109–115.

[19]B.D.Carlson,E.D.Evans,S.L.Wilson. Search radar detection and track with the hough transform–Part III:detection performance with binary integration.IEEE Trans.on Aerospace and Electronic Systems,1994,30(1):116–125.

[20]J.Chen,H.Leung,T.Lo,et al.A modifie probabilistic data association filte in a real clutter environment.IEEE Trans.on Aerospace and Electronic Systems,1996,32(1):300–313.

[21]I.Garvanov,C.Kobakchiev.Radar detection and track determination with a transform analogous to the hough transform.Proc.of the International Radar Symposium,2006:121–124.

[22]L.Moyer,J.Spak,P.Lamanna.A multi-dimensional Hough transform-based track-before-detect technique for detecting weak targets in strong clutter backgrounds.IEEE Trans.on Aerospace and Electronic Systems,2011,47(4):3062–3068.

[23]S.J.Davey,M.G.Rutten,B.Cheung.Using phase to improve track-before-detect.IEEE Trans.on Aerospace and Electronic Systems,2012,48(1):832–849.

[24]L.R.Moyer,J.Spak,P.Lamanna.A multidimensional Hough transform-based track-before-detect technique for detecting weak targets in strong clutter backgrounds.IEEE Trans.on Aerospace and Electronic Systems,2011,47(4):3062–3068.

Biographies

Xin Biwas born in 1980.He received his M.S. and Ph.Ddegrees in pattern recognition and intelligent systems from University of Chinese Academy of Sciences in 2007 and 2013,respectively.He is a professor in Shenyang Institute of Automation (SIA),Chinese Academy of Sciences.He went to Research Laboratory of Electronics at Massachusetts Institute of Technology(MIT)as a visiting scholar in 2014.His research interests are signal and information processing,microwave,millimeter wave,terahertz detection and imaging technology.

E-mail:bixin@sia.cn

Jinsong Duwas born in 1969.He received his M.S. degree in detection technology from Shenyang University of Technology in 1999,Ph.D degree in mechanical and electronic engineering from Graduate University ofChinese Academy ofSciences in2010. He is a professor in Shenyang Institute of Automation(SIA),Chinese Academy of Sciences.

E-mail:jsdu@sia.cn

Qingshi Zhangreceived his M.S.degree in electrical engineering and automation from Harbin Institute of Technology,Harbin,China,in 2010.He is presently a research assistant with Shenyang Institute of Automation.His research interests include moving target detection and multi-target tracking.

E-mail:zhangqingshi@sia.cn

Wei Wangreceived his M.S.degree in signal and information processing fromXidian University,Xi’an, China,in 2014.He is presently a research assistant with Shenyang Institute of Automation.His research interests include multi-target tracking and imaging technology.

E-mail:wangwei2@sia.cn

10.1109/JSEE.2015.00135

Manuscript received July 22,2014.

*Corresponding author.

This work was supported by the Innovation Subject of the Shenyang Institute of Automation,Chinese Academy of Science(YOF5150501).