Implementation of a Proposed Multiple Target Tracking Algorithm using LabVIEW

Implementation of a Proposed Multiple Target Tracking Algorithm using LabVIEW

M. Nabil

Department of Radar Military Technical College Cairo, Egypt

1. Kamel

   Department of Radar Military Technical College Cairo, Egypt

   1. 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®

      1. 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 [10-18], 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

         Observation-to-Track 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 target-originated 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 nearest-neighbor (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 nx-dimensional 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.

      2. 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 first-order 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 1|k

         k|k

         i

         2 i1

         xxk

         k|k

         target tracking. Another proposed tracking filter is presented in Subsection 2.3.

         1. 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

            k|k

            xxk k

            k|k

            (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

            k|k 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 1|k

            x k|k x

            ei e j tr fxx Pk|k fxx Pk|k 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 zero-mean white noise such that:

            k 1|k

            k 1|k

            i

            2 i1

            xxk 1

            k 1|k

            i j i ij

            E ' Q

            (3)

            where ei is the ith ny-dimensional 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 1|k

            xk 1

            i j

            2 i1 j1

            xxk 1

            k 1|k

            xxk 1

            k 1|k

            k 1

            x k|k

            Ex Z

            (5)

            where hx is the Jacobian of h giv(e5n) by:

            with an approximate zero-mean estimation error and the

            h h h'k 1, x'

            (14)

            mean-square error (MSE) matrix (not the associated

            xk 1 x

            x xxk |k

            covariance matrix) Pk|k as xk|k is not the exact conditional mean. The third-order 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 zero-mean 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 k|k xk k k|k

            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

            k|k

            xxk k

            k|k

            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 pseudo-noise 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].

         2. 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 miss-detection.

            The PHD filter operates on the single-target 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 k-1 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 multi-target 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, Dt|t (xt |Z1:t ), whose integral:

            K(k) P(k / k 1)HT [HP(k / k 1)HT R]

            where

            P(k/k-1)is the covariance matrix

            (27)

            Dt|t t | Z1:t dxt X t S f t|t 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)

            Dt|t1

            t

            t|t1 ,

            Dt1|t1 t1

            dxt1

            (17)

            t , z

            z(k) Hx(k / k 1)

            t t|t 1

            Dt|t V

            where

            zZ K z D

            Dt|t 1

            ,

            t , z

            (18)

            The value (called error) is the difference between noisy measurement and the target state. This error

            t|t1

            , p f

            t|t1

            | bt|t1 |

            (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 ft|t-1(xt|xt-1) 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.

         3. 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

         discrete-tme 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 zoom-in 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

      3. PROPOSED MULTI-TARGET 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, nearest-neighbor 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

         1. 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 sub-modules with a specific function each with a well-defined input and output. Each sub-module will be explained in detail in the following sub-sections.

            1. 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®

            2. 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)

            3. 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 sub-module, 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

         2. 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 user-friendly 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

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

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

3. Wax, N., Signal-to-Noise Improvement and Statistical of Tracking Populations, Journal of Applied Physics, Vol. 26, pp.586-595, 1955.K. Elissa, Title of paper if known, unpublished.

4. Sittler, R.W., An Optimal Data Association Problem in Surveillance Theory, IEEE Transactions on Military Electronics, MIL-8, 1964.

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

6. Bar-Shalom, Y., and E. Tse, Tracking in a cluttered Environment with Probabilistic Data Association, Automatica, Vol.11, pp. 451-460, 1975.

7. 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.171-175, 1971.

8. 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.423-432, 1974.

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

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

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

12. Y. Bar-Shalom and T. Fortmann, Tracking and Data Association, Academic Press, 1988.

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

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

15. Y. Bar-Shalom and X.-R. Li, Estimation and Tracking: Principles, Techniques and Software, Norwood, MA: Artech House, 1993.

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

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

18. Y. Bar-Shalom and W. Blair, Multitarget- Multisensor Tracking: Applications and Advances Volume III, Norwood, MA: Artech House, 2000.

19. 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. 206-213, 2004.

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

21. Tim Bailey, Ben Upcroft and Hugh Durrant-Whyte, Validation Gating for Non-Linear Non-Gaussian Target Tracking, 9th International Conference on information fusion, 2006.

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

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

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

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

26. Fortmann,T.E., Bar-Shalom,Y., and Scheffe,M., Sonar Tracking of Multiple targets using joint Probabilistic Data Association, IEEE Journal of Oceanic Research, OE-8, PP.173-184,1983.

27. 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. 458-468, 1995.

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

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

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

31. M. Nabil, ''Performance Improvement of Track-While-Scan System in Dense Air Traffic Control,'' M.Sc., MTC, Cairo, 2013.