 Open Access
 Total Downloads : 511
 Authors : Mohamed Nabil, Hazem Kamel, Mamdouh Hassan
 Paper ID : IJERTV4IS090432
 Volume & Issue : Volume 04, Issue 09 (September 2015)
 Published (First Online): 22092015
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Implementation of a Proposed Multiple Target Tracking Algorithm using LabVIEW
M. Nabil
Department of Radar Military Technical College Cairo, Egypt

Kamel
Department of Radar Military Technical College Cairo, Egypt

Hassan
l
Branch of Research & Development Military Technical College
Cairo, Egypt
Abstract Radar tracking systems are very common and necessary parts of any aviation and/or defense system. However, target tracking problem is more difficult if the target is maneuvering. Kalman filter has a poor behavior to track maneuvering targets. In this paper, a Proposed Tracking Filter (PTF) is used [24] able to track targets with highly maneuverability. A complete proposed multiple tracking algorithm and a graphical user interface (GUI) software are developed using LabVIEWÂ®. For performance evaluation, the tracking algorithm has been tested in tracking three simulated maneuverable targets. Once the algorithm is validated in LabVIEWÂ®, it can be easily realized in an embedded hardware for real time multiple target tracking applications.
KeywordsMultiple Target Tracking, Kalman Filter, PHD Filter, Maneuvering Targets, LabviewÂ®

INTRODUCTION
Tracking maneuvering targets is required in a wide range of civilian applications such as intelligent transportation system, air traffic control and surveillance. Therefore, researchers have concerned about this issue during the past several decades [1]. Surveillance systems are employing one or more sensors together with computer subsystems to interpret the environment. Typically sensor systems such as infrared (IR), sonar, and radar sensor reports measurement form diverse sources. The target tracking objective is to collect sensor data from field of view (FOV) containing one or more potential targets of interest and then partition sensor data into set of observation, or tracks that are produced by same object (or target),once tracks are formed and confirmed ,the number of target of interest can be estimated and quantities, such as target velocity future predicted position and target classification characteristics ,can be computed from each track [2].
Multiple target tracking (MTT) algorithm is applied in many surveillance radar applications. Fig. 1 [2] shows the basic elements of a typically MTT system. This system has been formulated in the early papers by Wax [3] and Sittler [4], but these papers were written before the widespread application of the Kalman filtering techniques [5]. Bar Shalom [6] and Singer [7,8] can be credited of modern MTT schemes that combine the data association techniques and Kalman filtering theory. Starting with Farina and Studer [9], a number of books, including [1018], have been written to address the numerous problems involved in tracking multiple targets with one or more sensors [19].
Sensor Data processing and Measurement formation
ObservationtoTrack Association
Track Maintainance (Initiation,Confirmation
,and Deletion)
Gating computations
Filtering and Prediction
Fig. 1. Basic elements of MTT system [2]
Gating is a necessary part of target tracking in clutter. The purpose of gating is to reduce computational expenses by eliminating from consideration measurements which are far from the predicted measurement location. Gating is performed for each track at each scan by defining an area of surveillance space which is called the gate [20]. All measurements positioned in the gate are selected and used for the track update while measurements not positioned in the gate are ignored for the purpose of the track update. The gate is usually formed in such a way that the probability of a targetoriginated measurement falling within the gate, provided that the target exists and is detected, is given by a gating probability (PG) which can be evaluated from the available track statistics. Since the size or volume of the gate is dependent on the tracking accuracy, it therefore varies from scan to scan and from track to track, and the standard validation gate is ellipsoid [21].
Several classical data association methods exist. The simplest is probably the nearestneighbor (NN) approach. In [22], this approach is referred to as the nearest neighbor standard filter (NNSF) and uses only the closest observation to any given state to perform the measurement update step.
Another MTT data association method is the probability data association (PDA) [25]. It estimates the states by a sum overall the association hypothesis weighted by the probabilities from the likelihood. An extension of this method is the joint probability data association (JPDA) [26, 27] algorithm, the first developed by Fortmann et al [28]. Another major approach is the multiple hypothesis tracking (MHT) [2, 29] and the first develop by Reid [30] which calculates every possible update hypothesis. Also, the Fuzzy data association (FDA) [28] is formulated using the extended Kalman filter and FDA is accomplished using the fuzzy logic algorithm.
The measurements which correlate to a given track is processed by a filter to update the track parameter for these tracks that didn't receive correlating observations, the previous
where ei is the ith nxdimensional Cartesian basis vector, the Jacobian of the vector f given by:
f is
x
k
x
predicted estimates are treated as the filtered estimates. Then, the predictions are made to the time when the next data scan is to be received [24].
fxk
f
x
f 'k, x'
xxk  k
(7)
In Section 2 of this paper, both conventional and proposed
and f i
xx
k
is the Hessian of the ith component of f given by:
k
adaptive estimation/prediction filters are presented. The
2 f i
i
i
proposed MTT algorithm flowchart is explained in Section 3. Then, the algorithm performance analysis and evaluation are
fxx
x2
x 'x f
k, x
xxk  k
(8)
investigated in Section 4. Finally, the proposed algorithm implementation in LabVIEWÂ® is explained in Section 5 followed by a conclusion.

CONVENTIONAL AND PROPOSED PREDICTION FILTERS In this section, the extended Kalman filter (EKF)
The higher order terms will be neglected. By calculating the expectation of Equation (6) conditioned on Zk and assuming that the firstorder term in Equation (6) is approximately zero, the predicted state to time k+1 from time k will be:
and probability hypothesis density (PHD) filter are presented
x f k, x
1 nx e trf i P
(9)
as conventional estimation/prediction filter used for multiple
k 1k
kk
i
2 i1
xxk
kk
target tracking. Another proposed tracking filter is presented in Subsection 2.3.

Extended Kalman filter (EKF)
Subtracting Equation (9) from Equation (6), the state prediction error is derived:
n
e f e 1 x e 'x x f i x x
To approximate a nonlinear system to a linear one, a
first (or second) order series expansion is used. By least
xk 1 k
n
xk xk  k
2 i1 i k
kk
xxk k
kk
(10)
minimum mean square error (LMMSE) estimation and the

1 x e trf i P
approximation of the nonlinear dynamic and/or measurement
2 i1 i
xxk
kk k
equations, the extended Kalman filter (EKF) is derived.
Consider the system with dynamics:
The state prediction covariance (the MSE matrix) is obtained by multiplying Equation (10) by its transpose and
calculating the expectation conditioned on Zk:
x f k, x ,
k 1 k k
(1)
P f P
f ' 1 nx nx (1)' i
j Q
(11)
k 1 k k
k 1k
x kk x
ei e j tr fxx Pkk fxx Pkk k
and the measurement is:
k k 2 i1 j1 k k
z hk,x ,
Similarly, the predicted measurement is given by:
(2) (2)
k k k
z hk 1, x 1 nz e trhi P
(12)
where both the process and the measurement noises are mutually independent zeromean white noise such that:
k 1k
k 1k
i
2 i1
xxk 1
k 1k
i j i ij
E ' Q
(3)
where ei is the ith nydimensional Cartesian basis vector. The measurement prediction cova(3ri)ance (also called the
innovation covariance or residual covariance) is:
E ' R
(4) (4)
i j i ij
S h P h' 1 nz nz e e' trhi P
h j P
R
(13)
k
k
k
Let us consider the initial state as an approximate conditional mean:
k 1
xk 1
k 1k
xk 1
i j
2 i1 j1
xxk 1
k 1k
xxk 1
k 1k
k 1
x kk
Ex Z
(5)
where hx is the Jacobian of h giv(e5n) by:
with an approximate zeromean estimation error and the
h h h'k 1, x'
(14)
meansquare error (MSE) matrix (not the associated
xk 1 x
x xxk k
covariance matrix) Pkk as xkk is not the exact conditional mean. The thirdorder moments of the estimation error is
and the Hessian of its ith component is:
h
2 hi
x
assumed to be approximately zero as in the case of zeromean white Gaussian random variable.
i
xxk 1
x2
x'
hi k 1,x
xxk k
(15)
Using the vector Taylor series expansion of xk+1, we get:
k 1 kk xk k kk
x f k, x f x x
n
The EKF inherent approximations may lead to unbounded
estimation errors; i.e., divergence of the filter. Also, neglecting higher orders and ev(a6lu)ating the Jacobian and the
Hessian at the estimated and predicted state rather than the
1 x e 'x x f i x x
(6)
2 i1 i k
… k
kk
xxk k
kk
actual state may cause errors. Consequently, a consistency test is very important to evaluate the performance of the EKF. One method to compensate for errors is implemented by adding an artificial process pseudonoise for compensation for
errors in the state prediction. In practice, if the initial errors and the noises are not too large, the EKF performs well [31].


Probability hypothesis density (PHD) filter
The probability hypothesis density (PHD) filtering approach is an attractive alternative to tracking unknown numbers of targets and their states in the presence of data association uncertainty, clutter, noise, and missdetection.
The PHD filter operates on the singletarget state space and avoids the combinatorial problem that arises from data association. These salient features render the PHD filter extremely attractive. However, the PHD recursion involves multiple integrals that have no closed form solutions in general.
The PHD represents the expectation, the integral of which in any region of the state space S is the expected number of
noisy measurement and the target state 0 exceeds a certain value. else, the Kalman filter is applied.
k = Ak 1 + Buk + wk 1 (23) with a measurement z R m that is
zk = Hk + vk (24)
The random variables wk and vk represent the process and measurement noise, respectively. They are assumed to be independent of each other, white, and with normal probability distributions.
P (w)~ N(0,Q) (25)
P(v)~ N(0,R) (26)
The nn matrix A in the difference equation (23) relates the state at the previous time step k1 to the state at the current step k. The n x l matrix B relates the optional control
objects in S.
input
u R l
to the state x. The mn matrix H in the
The PHD is estimated instead of the multiple target posterior distribution as it is much less computationally expensive to do so. The time required for calculating joint multitarget likelihoods grows exponentially with the number of targets and is thus not very practical for sequential target
measurement equation (24) relates the state to the measurement zk.
The equations of linear Kalman filter are in consistence of
time update and measurement update. The nm matrix K in
(27) is chosen to be the gain
estimation as this may need to be undertaken in real time.
The PHD is defined as the density, Dtt (xt Z1:t ), whose integral:
K(k) P(k / k 1)HT [HP(k / k 1)HT R]
where
P(k/k1)is the covariance matrix
(27)
Dtt t  Z1:t dxt X t S f tt X t  Z1:t dX t s
(16)
R.. is the variance matrix of the measured data
H is the measurement matrix which is given by
On any region S of the state space is the expected number of targets in S. The estimated object states can be detected as peaks of this distribution.
H 1
0
0 0 0
0
0 1
The derivation for the PHD equations is provided by Mahler [36], the prediction and update equations are given by:
and from the state of the previous scan with the data of the actual scan, the future state of the next scan is given by:
x(k / k) x(k / k 1) K(k)z(k) Hx(k / k 1) (28)
Dtt1
t
tt1 ,
Dt1t1 t1
dxt1
(17)
t , z
z(k) Hx(k / k 1)
t tt 1
Dtt V
where
zZ K z D
Dtt 1
,
t , z
(18)
The value (called error) is the difference between noisy measurement and the target state. This error
tt1
, p f
tt1
 btt1 
(19)
value is checked every scan and compared to certain
threshold th defined as:
s
V x 1 PD x, (20)
z(k) Hx(k / k 1) th
(29)
kt z t ct z
and
(21)
where th is the checking threshold. If the case is true, the matrix P will be initialized to its initial value P=P0 to
t ,z PD g z  x , (22)
In the prediction equation, bt is the PHD for spontaneous birth of a new target at time t, PS is the probability of target survival and ftt1(xtxt1) is the single target motion distribution. In the data update equation, g is the single target likelihood
compensate the deviation in the matrix values in case of maneuvering targets, which is proportional to the error between the predicted and actual targets position. Elsewhere, the P matrix is computed as in Kalman filter equation as follow
function, PD is the probability of detection, t is the Poisson parameter specifying the expected number of false alarms and ct is the probability distribution over the state space of clutter points.

Proposed tracking filter
P(k / k) [I K(k)H ]P(k / k 1)
where I is the identity matrix.
The estimated stated of the target is given by
x(k 1/ k) Ax(k / k)
(30
)
(31)
The proposed tracking filter [23] addresses the
where A.is the state transition matrix of CT model
general problem of trying to estimate the state
R n
of a
which we will use and it is given by
1 T
0 1* w *T *T / 2
discretetme process that is governed by the linear stochastic difference equation (23) but with resetting the covariance
0
A
0
1 w *T *T / 2 0
w *T *T / 2 1
1* w *T
T
(32)
matrix P to its initial value P0 when the difference between
0
and
w *T
0 1 w *T *T / 2
w. is constant = 0.2.
T. is time of one rotation of antenna.
The error covariance matrix is given by
exit. At the beginning, the program has ability to zoomin a specified region using the cursor on panel. Data are updated and/or loaded at each north pulse.
P(k 1/ k) AP(k / k)AT Q
(33)
IV. PERFORMANCE ANALYSIS AND EVALUATION


PROPOSED MULTITARGET TRACKING ALGORITHM FLOWCHART
Start
Load Scenario & measurement
initiation at Scan
k T1,..,Tn
Scenario Display
Gating
Data association
Bank of PTF
Radar display
Fig. 2. The flowchart of the proposed MTT algorithm
First of all, a bank of the proposed tracking algorithm is implemented; a filter is associated to each track. Number of filters in the bank (or number of targets to be tracked, simultaneously) depends on the processor speed; i.e. a faster algorithm will provide more targets to be tracked. As shown in Fig. 2, either the target scenario is loaded from the simulator or the target data are fed from the radar signal processor. Then, the initiation of a tentative target track with track quality initial value set at 1 is performed. Next to target initiation, the gating will be formed around the target according to gating equations. In the next scan, according to the measurement which falls within the gate, nearestneighbor approach chooses only one measurement to update the trajectory of the target and the track quality is increased. A track quality value 3 means that the track is stable and true. If there is no measurement inside the gate, the track is updated by the predicted position calculated from the previous scan. Besides, the track score is decreased by 1. When the track quality reaches the 0 value, the track is automatically terminated/deleted. Estimation/prediction is calculated using the Proposed Tracking Filter [23]. The total number of scans from the beginning of the program till stopping the program is
In order to examine the MTT algorithm, this section introduces different scenarios for the tracking program. The first one uses three parallel targets. Then, the second scenario uses two crossing targets and one parallel to one of them. Finally, the third scenario uses three attacks moving each one has its own maneuver.
Fig. 3. First scenario
Fig. 4. Second scenario
Fig. 5. Third scenario

PROPOSED ALGORITHM IMPLEMENTATION USING
LABVIEWÂ®
This section shows the implementation of the tracking algorithm using LabVIEWÂ®. Target position is retrieved coarsely by the position of mouse click and refined by choosing the nearest target location to the mouse position. LabVIEWÂ® modules are used to implement the tracking algorithm written by MATLABÂ®.
As the tracking algorithm is too large to show in one figure, it has been divided into several submodules with a specific function each with a welldefined input and output. Each submodule will be explained in detail in the following subsections.

Monitoring
In order to implement a digital radar display working in raster scan displays, a digital circuit to perform the scan conversion implemented, shown in Fig.5, which writes the image (in digital form) in video memory.
Memory
Acquisition
/write section
Read / display section
Video Signal
Synchronization
Signal
Azimuth Signal
To CRT
Fig. 8. Block diagram of LabVIEWÂ® displaying section
The radar display front panel, shown in fig.8, is designed to be 1024*1024 pixels and the center is at the pixel (512,512). It consists of four range markers shown as linearly separated circles and at the top right corner the gate is found.
Fig. 6. Block diagram of digital scan converter circuit
The video memory will hold all the signals which are entered by Acquisition/Write section to display on the monitor. The memory consists of logical zeros and ones; each cell corresponds to one pixel of the display. The pixels are arranged into rows and columns which are converted to Cartesian coordinates (X and Y axis) from polar information (range, azimuth). The read/display section contains circuitry which reads the data from memory and produces PPI display on CRT by scanning the memory cells (zeros or ones). The conversion circuit is implemented by LabVIEWÂ® and its block diagram is shown in Fig. 6.
Fig. 7. LabVIEWÂ® conversion section
In Fig.7, the block diagram of displaying section is shown. It is responsible for displaying the measurements and targets, gates of each target, targets ID, grid and circles and the colors.
Fig. 9. Radar display in LabVIEWÂ®

Getting cursor/mouse position
When click action is done over target in the radar display, operators may not click over the target accurately. So, nearby pixels are searched around the mouse click in a small area and if target exists it will initiate a track and this code is inserted in the first step of the sequence and this is done by the code in Fig. 10.
Fig. 10. Property node of mouse (up) and first click check around area (down)

Tracking algorithm implementation
This section shows the implementation of the whole tracking algorithm using Proposed Tracking Filter for prediction and the NN approach for association. The source code is written in math script and takes its input from simulation scenario data and its output is monitored on the display.
Fig. 11. Block diagram of tracking algorithm
In this submodule, shown in Fig. 11, the initial gate checks whether the target is found in the next scan or not. If it exists, the track is updated and track quality is increased by one. Otherwise, the track is ended and its quality remains at zero waiting another click to begin tracking upon request of the user.
Fig.12. shows how to act if there is no data associated to the target track. The predicted position that is calculated from the previous step is used together with the gate according to the distance between the target position in the last two scans, and the NN data association approach is used. Prediction is calculated using proposed tracking Filter. The track quality is increased till it reaches 3 and, then, it is fixed at this value. If a measurement update is not received within any scan the track quality is decreased by one, and the program takes the predicted position to update the track.
Fig. 12. Block diagram in case of no data in the gate
The track can be forced to end now by click over End track now, this action forces track quality value to zero and the prediction data is reset to zero which leads to end the track. By the same way it is able to force all the targets tracks to end by clicking over End all tracks as in Fig.13.
Fig. 13. End all tracks
In Fig.14, the GUI for the tracking program is shown, three target data, north led, zooming option, antenna rotation, end tracks, and stop the program is shown.
Fig. 14. Radar tracking GUI


CONCLUSION



A proposed multiple target tracking algorithm has been derived. The proposed algorithm performance was analyzed and tested in tracking various scenarios. Beside less computational complexity, the algorithm succeeded to track all various simulated scenarios. A LabVIEWÂ® program is implemented to track multiple targets in real time. The multiple tracking program is based on the creation of a bank of adaptive filter, each is associated for an individual track. A graphical user interface has been creted in a userfriendly way to provide the user a full control on the radar monitor and tracking option. This tracking program as implemented using NI LabVIEWÂ® could be easily downloaded on an embedded system for any radar.
REFERENCES

M. H. Bahari, N. Pariz, A. Karsaz, High Maneuvering Target Tracking Using A Novel Hybrid Kalman FilterFuzzy Logic Architecture, International Journal of Innovative Computing, Information and Control, Vol. 6, No. 5, 2010.

Blackman, Multi hypothesis tracking for multi target tracking," IEEE system magazine, vol. 19, NO. 1, pp.518, Jan. 2004.

Wax, N., SignaltoNoise Improvement and Statistical of Tracking Populations, Journal of Applied Physics, Vol. 26, pp.586595, 1955.K. Elissa, Title of paper if known, unpublished.

Sittler, R.W., An Optimal Data Association Problem in Surveillance Theory, IEEE Transactions on Military Electronics, MIL8, 1964.

Kalman, R.E., A new Approach to linear Filtering and Prediction Problems, Journal of Basic Engineering, pp.3546, 1960.M. Young, The Technical Writers Handbook. Mill Valley, CA: University Science, 1989.

BarShalom, Y., and E. Tse, Tracking in a cluttered Environment with Probabilistic Data Association, Automatica, Vol.11, pp. 451460, 1975.

Singer, R.A., and J.J. Stein, An Optimal Tracking Filter for Processing Sensor Data of Imprecisely Determined origin in Surveillance Systems, Procedings of the 1971 IEEE Conference on Decision and Control, pp.171175, 1971.

Singer, R.A., R.G. Sea, and K.B. Housewright, Derivation and Evaluation of Improved Tracking Filters for Use in Dense Multitarget Environment, IEEE Transactions on Information Theory, pp.423432, 1974.

A. Farina and F. Studer, Radar Data Processing, Vols. I and II, Letchworth, Hertfordshire, UK: J. Wiley and Sons, 1985.

S. Blackman and R. Popoli, Design and Analysis of Modern Tracking Systems, Artech House, 1999.

S. Blackman, Multiple Target Tracking with Radar Applications, Artech House, 1986.

Y. BarShalom and T. Fortmann, Tracking and Data Association, Academic Press, 1988.

E. Waltz and J. Llinas, Multisensor Data Fusion, Artech House, 1990.

D. Hall, Mathematical Techniques in Multisensor Data Fusion, Artech House, 1992.

Y. BarShalom and X.R. Li, Estimation and Tracking: Principles, Techniques and Software, Norwood, MA: Artech House, 1993.

L. Klein, Sensor and Data Fusion Concepts and Applications, Bellingham, WA: SPIE Optical Engineering Press, 1993.

Y. Bar Shalom and X.R. Li, Multitarget Multisensor Tracking: Principles and Techniques, Storrs, CT: YBS Pub., 1995.

Y. BarShalom and W. Blair, Multitarget Multisensor Tracking: Applications and Advances Volume III, Norwood, MA: Artech House, 2000.

A. Gad, M. Farooq, J. Serdula, and D. Peters, Multitarget Tracking in a Multisensor Multiplatform Environment , the Seventh International Conference on Information Fusion, Stockholm Sweden , pp. 206213, 2004.

D Mu_sicki, Mark R. Morelande, Gate Volume estimation for Target Tracking, the Seventh International Conference on Information Fusion, Stockholm Sweden, pp. 455462, 2004.

Tim Bailey, Ben Upcroft and Hugh DurrantWhyte, Validation Gating for NonLinear NonGaussian Target Tracking, 9th International Conference on information fusion, 2006.

Rickard Karlsson, Fredrik Gustafsson, Monte Carlo data association for multiple target tracking, Target Tracking: Algorithms and Applications, vol.1, 2001.

M. Nabil, H. Kamal, and M. Hassan, Comparison Between Kalman Filter and PHD Filter in Multitarget Tracking, 8th International Conference on Electrical Engineering, MTC, Cairo, 2012.

Rickard Karlsson, Simulation Based Methods for Target Tracking, Linkoping Studies in Science and Technology, Thesis No. 930, Sweden, 2002.

Y. BarShalom, T. Kirubarajanb and X. Lina, Probabilistic Data Association Techniques for Target Tracking with Applications to Sonar, Radar and EO Sensors, IEEE System Magazine, 2003.

Fortmann,T.E., BarShalom,Y., and Scheffe,M., Sonar Tracking of Multiple targets using joint Probabilistic Data Association, IEEE Journal of Oceanic Research, OE8, PP.173184,1983.

B.Zhou and N.K.Bose, An Efficient Algorithm for Data Association in Multitarget Tracking, IEEE Transactions on Aerospace and Electronic Systems,Vol.31, No.1, pp. 458468, 1995.

Y. M. Chen, A New Data Association Algorithm for Multitarget Tracking in a Cluttered Environment, ISIF,(2003).

Matthias Luber, Gian Diego Tipaldi, Kai O. Arras, Spatially Grounded MultiHypothesis Tracking of People, IEEE ICRA 2009 Workshop on People Detection and Tracking, Kobe, Japan, 2009.

D.B.Reied, "An Algorithm for Tracking Multiple Targets", IEEE Transactions on Automatic Control, Vol.24, PP. 843854, 1979.

M. Nabil, ''Performance Improvement of TrackWhileScan System in Dense Air Traffic Control,'' M.Sc., MTC, Cairo, 2013.