Vol. 3  No. 12 (2011) , Article ID: 9209 , 6 pages DOI:10.4236/eng.2011.312144

Maneuvering Multi-Target Tracking Algorithm Based on Modified Generalized Probabilistic Data Association

Zhentao Hu1, Chunling Fu2, Xianxing Liu1

1College of Computer and Information Engineering, Henan University, Kaifeng, China

2Basic Experiments Teaching Center, Henan University, Kaifeng, China


Received July 8, 2011; revised October 1, 2011; accepted November 1, 2011

Keywords: Multi-Target Tracking, Particle Filter, Generalized Probabilistic Data Association, Clutters


Aiming at the problem of strong nonlinear and effective echo confirm of multi-target tracking system in clutters environment, a novel maneuvering multi-target tracking algori-thm based on modified generalized probabilistic data association is proposed in this paper. In view of the advantage of particle filter which can deal with the nonlinear and non-Gaussian system, it is introduced into the framework of generalized probabilistic data association to calculate the residual and residual covariance matrices, and the intercon-nection probability is further optimized. On that basis, the dynamic combination of particle filter and generalized probabilistic data association method is realized in the new algorithm. The theoretical analysis and experimental results show the filtering precision is obviously improved with respect to the tradition method using suboptimal filter.

1. Introduction

In actual engineering applications, maneuvering multitarget tracking in clutters is always one of hottest and most difficult issues in target tracking studies, which could be solved by means of the two key technologies including filter design and data association. In recent years, the growth of computational power has made computer intensive statistical methods feasible. Based on the technique of sequential importance sampling and the recursive Bayesian filter principle, particle filter (PF) is particularly useful in dealing with nonlinear and nonGaussian problems, and it can achieve the minimum variance estimation in theory [1-3]. Because of the above advantages, PF has been widely applied in many fields, such as signal processing, target tracking, fault diagnosis and image processing, et al. In data association methods, some novel solutions have been proposed to implement effective echo validation in clutters, mainly based on Bayesian estimation theory, evidential reasoning theory, and such intelligence calculation as fuzzy theory, neural networks and genetic evolution [4-7]. Where data association algorithms based on Bayesian estimation theory are the mainstream, of which probabilistic data association (PDA) and joint probabilistic data association (JPDA) proposed by Bar-Shalom, et al., are always considered as the superior methods to solve the single target tracking and the multi-target tracking [8,9]. Two basic principles are applied in JPDA. One is that every measurement derives from unique target, the other is that observation deriving from one target is not more than one. Some scholars have attempted to replace the suboptimal filter by PF in JPDA, and the results show the tracking precision is obviously improved.

It has set the higher requirement for modern tracking and monitoring system, since the existence of various natural and artificial disturbance, the application of the penetration technology of large batches targets and the improvement of target maneuverability and control properties in the modern war environment, cause much denser formation and cross motion, which leads to the strong fuzzy and uncertainty of obtained data. When targets maneuvers with cross motion and denser formation, sensors are likely to regard many observations coming from different planes as one observation. In addition, with the improvement of resolution ratio of radar, the phenomenon, the many observations corresponding to one target, often arise form the multipath effect of observation and systematic error of networking radar. In these cases, the one-to-one correspondence rules between observation and target is not coincident with actual facts. Quan P. et al. break the feasibility-based rule in JPDA and give the definition of generalized joint event and generalized event, and propose a new method of partition and combination about them. On this basis, the generalized probabilistic data association (GPAD) is proposed on account of Bayesian estimation criteria. Theoretical analysis and simulation results for various kinds of typical environment show that the filtering precision and real time of GPDA are superior to JPDA. However, the application of suboptimal filters in GPDA inevitably cause that filtering precision is limited the adverse effects of strong nonlinear of tracking system [10,11].

According to the analysis above, through the dynamic combination of particle filter and generalized probabilistic data association, a novel maneuvering multi-target tracking algorithm based on modified generalized probabilistic data association in clutters is proposed. Experimental results show the feasibility and validity of the algorithm.

2. Particle Filter

The problem of state estimation can be solved by calculating the posterior probability density function of the state variable at timebased on all the available data of observation sequence. Because the complete information of sequential estimation is in, some parameters which system state estimation need can be obtained, such as mean and variance, etc. The concrete implementation is to approximate with particles in PF, and the mathematical description is written as


where is Dirac’s delta function. xk represents particle used in estimated system, which is sampled directly from. However, is unknown generally, and the above process is often impossible to implement. The difficulty can be circumvented by sampling particles with associated importance weights from a known and easy-to-sample proposal distribution. The process is described as the importance sampling. Where the associated importance weights of particle is defined as


To depict further the generation of, the proposal distribution is factorized as follows


It is known that is sampled by augmenting each sampled from the proposal distribution with the new state sampled from. In order to obtain the recursive equation of particle weights, is expressed in terms of, and. Noting that


Under assumptions that states subject to a Markov process and the observations are conditionally independent, and combining with Equations (2)-(4), the particle weights is given by


In the practical application, the proposal distribution is commonly selected as


Substituting Equation (6) into Equation (5), the particle weights update equation can then be shown to be


Thenis normalized before the re-sampling stage, anddenotes normalized weights. The key idea of re-sampling is to eliminate particles that have small weights and to duplicate particles with large weights, under the conditions of the total particles number invariant. A set of new particles are sampled after the re-sampling stage. According to Monte Carlo simulation technology, state estimation can be ultimately achieved by calculating the arithmetic mean of. At present, re-sampling methods are mainly in the following categories: the residual re-sampling, the system re-sampling, the polynomial re-sampling, etc. That is standard particle filter and also known as bootstrap filter.

3. Maneuvering Multi-Target Tracking Algorithm Based on Modified Generalized Probabilistic Data Association

Data association is one of the key technologies in multitarget tracking, because it directly effects on the whole performance of tracking system. Based on the multiplexing principle with observation and target, GPDA is considered as a kind of better echo confirmation method. It is known that the construction of GPDA completely adopts the framework of Kalman filter, thus GPDA lacks the effective processing ability for strong nonlinear cases. For nonlinear system, the extended Kalman filter (EKF) can directly replace KF, but the filtering precision of EKF sometimes is hard to meet the practical needs. Considering that PF and GPDA can effective treat strong nonlinear problem and echo confirmation, respectively, In this section, we give the generalized probabilistic data association based on particle filter (GPDA-PF) in clutters is proposed.

3.1. Generalized Probabilistic Data Association

Considering targets move in radar scanning region, the observations consist of the real measurement and clutters in each sample time. The state equation and observation equation of the t-th target is modeled as the following form.



where and denote the unknown state vector of t-th target and m-th observation vector at time, respectively. and denote the evolution function of state and observation, respectively. System noise and observation noise are subject to white noise sequence, respectively, and meet independently identically distribution. Let denotes the candidate echo set that fall into correlation window at time. Different from feasibility-based rule in JPDA, GPDA adopts the following rules. Firstly, each target has possessed observations (one or more, including zero observation). Secondly, each observation originates from targets (one or more, including zero target). Thirdly, the probability corresponding to any target (observation) and observation (target) should be not less than the other correlated events probability in last two rules. Here, the zero target refers to no target, but it may be the new target of target concerned outside or the false object from interferences or clutters. The zero observation refers to no observation, namely target is not detected.

The first rule shows that observations can be multiplexed when target is considered as a benchmark, which is mainly used to solve the association problem between one target and multiple observations. The second rule shows that target can be multiplexed when observation is considered as a benchmark, which is mainly used to solve the association problem between one observation target and multiple targets. The third rule shows that the probability of one-to-one correlated events is dominant among all the correlated events assumed. To calculate interconnected probability in GPDA, the generalized joint events set and poly-probability matrix are defined as follows.

and denote generalized events subset which meet the first rule and the second rule, respectively. denotes statistical distance between the m-th observation and the t-th target.



and denote the residual and residual covariance matrices at time, respectively. denotes the m-th confirmed echo from target, and denotes the one-step state prediction of the t-th target. denotes the volume of correlation window. denotes the probability of true observations falling into the correlation window, and denotes the target detection probability, that is the complete detection probability of true observation. denotes the volume of correlation window and denotes coefficient and is usually taken as the positive integer. Assuming the false-alarm and the numbers of clutters are subject to the uniform distribution and the Poisson distribution, respectively. denotes the space density of clutters, that is the expectation number of clutters in unit volume. The interconnection probability of the -th confirmed echo is calculated as.




and denote the index of target and observation label, respectively. is normalized coefficient.

3.2. Generalized Probabilistic Data Association Based on Particle Filter

Firstly, particles are sampling from the proposal distribution on account of prior model information, and then one step observation prediction of particle and are calculated by the following equations.





Echo confirmation principle is realized by the following equation.


where denotes the threshold of hypothesis testing. Then of the confirmed echo is calculated by the poly-probability matrix. The equivalent observation is solved by, and.


The likelihood score that particle is relative to, is used to measure particle weights, and then weights are normalized.


The re-sampling is realized by normalized weights , and are obtained. On the basis of Monte Carlo simulation principle, the state estimation of t-th target can be solved as follows.


4. Simulation Results and Analysis

To illustrate the performance of GPDA-PF, the example of maneuvering target tracking based on two-coor-dinate radar is given. The target moves within the horizontalvertical plane according to the standard second-order model.

where denotes state vector of t-th taeget., , and denote position component and velocity component in the horizontal direction and the vertical direction, respectively. denotes the system state transition matrixes, , and. denotes the system noise matrix. denotes the sampling time. and denote system noise vector, and suppose they are subject to zero-mean Gaussian white noise with standard deviation,. denote the observation noise vector and suppose it is subject to zero-mean Gaussian white noise process with standard deviation, here the noise standard deviations of radial distance component and azimuth angle component are and, respecttively., and. and denote the actual initial states of two targets, and the negative sign of state vector denotes that targets move on the negative half shaft of X axis (horizontal direction) and Y axis (vertical direction). The number of Monte Carlo simulation is 50 and the number of particles is 1000, and the total simulation step is. In order to verify the effect of clutters for algorithm performances, two kinds of simulation results are compared when is 0.002 and 0.0055, respectively. And the root mean square error is used as the performance evaluation index of algorithm precision, which is defined as, where and denote the true state value and the state estimation value of the t-th target in times Monte Carlo simulations at current time, respectively.

Two target trajectories and clutters distribution are given in Figure 1 under and. By 50 times Monte Carlo simulations, the comparison of


Figure 1. Trajectory of target and clutters distribution. (a) = 0.002; (b) = 0.0055.


Figure 2. RMSE of position estimation of target 1. (a) Horizontal direction; (b) Vertical direction.


Figure 3. RMSE of position estimation of target 2. (a) Horizontal direction; (b) Vertical direction.

Table 1. The comparison of the mean of RMSEunder and.

the RMSE of state estimation based on GPDA-EKF and GPDA-PF under are given in Figures 2 and 3. The data from Table 1 quantitatively show the mean of RMSE of state estimation, when is 0.002 and 0.0055, respectively. According to the above comparison of RMSE, it is shown that the filter precision of GPDAPF is superior to GPDA-EKF. In addition, the following conclusions can be drawn by the analysis of data from Table 1 with the increase of clutters number in tracking environment, the filter precision of two algorithms all decline, but the performance of GPDA-PF is always stably superior to GPDA-EKF. In general case, PF is used as filter can lead to the increase of computational complexity, and the simulation also gets the same result in this paper. However, the real time of algorithm has a close relationship with the number of particle and filtering initial value. When the prior information is better, namely, the filtering initial value is close to the real state of target or system model is more accurate, the real time of GPDA-PF is effectively improved. Based on the above results, PF will be extended into the maneuvering multi-target tracking in clutters, which is our next research direction.

5. Conclusions

A novel maneuvering multi-target tracking algorithm based on modified generalized probabilistic data association in clutters is proposed in this paper. The new algorithm effectively improves the decline problem of filtering precision caused by system strong nonlinear and dense clutters environment. The theory analysis and simulation results show GPDA-PF has the following advantages relative to existing methods. Firstly, adopting the basis framework of PF, so it preserves the advantage to solve nonlinear and non-Gaussian problems. Secondly, the construction of GPDA-PF avoids the derivation of Jacobi matrix and the calculation of state prediction covariance matrix and state estimation covariance matrix when EKF is utilized, which make the algorithm simple and is easy to realize. Finally, the feasibility-based rule of GPDA is accord with the actual situation of modern battlefield environment, which enhances the adaptability of algorithm and improves the reliability and stability for target tracking result.

6. Acknowledgements

The project work is supported by the National Natural Science Foundation of China (60972119, 61170243) and the Science Technology Department Natural Science Foundation of Henan Province (112102210196). In addition, we thank Dr. Yandong Hou and Prof. Quan Pan for helpful discussions.


  1. O. Cappe, S. J. Godsill and E. Moulines, “An Overview of Existing Methods and Recent Advances in Sequential Monte Carlo,” Proceedings of the IEEE, Vol. 95, No. 5, 2007, pp. 899-924. doi:10.1109/JPROC.2007.893250
  2. M. S. Arulampalam, S. Maskell, N. Gordon, et al., “A Tutorial on Particle Filters for Online Nonlinear/Non- Gaussian Bayesian Tracking,” IEEE Transactions on Signal Processing, Vol. 50, No. 2, 2002, pp. 174-188. doi:10.1109/78.978374
  3. H. A. P. Blom and E. A. Bloem, “Exact Bayesian and Particle Filtering of Stochastic Hybrid Systems,” IEEE Transactions on Aerospace and Electronic Systems, Vol. 43, No. 1, 2007, pp. 55-70. doi:10.1109/TAES.2007.357154
  4. S. Puranik and J. K. Tugnait, “Tracking of Multiple Maneuvering Targets Using Multiscan JPDA and IMM Filtering,” IEEE Transactions on Aerospace and Electronic Systems, Vol. 43, No. 1, 2007, pp. 23-35. doi:10.1109/TAES.2007.357152
  5. H. X. Liu, Y. Liang, Q. Pan, et al., “A Multi-Path Viterbi Data Association Algorithm,” Acta Electronica Sinica, Vol. 34, No. 3, 2006, pp. 1640-1644.
  6. R. L. Popp, K. R. Pattipati and Y. Bar-Shalom, “M-Best S-D Assignment Algorithm with Application to MultiTarget Tracking,” IEEE Transactions on Aerospace and Electronic Systems, Vol. 37, No. 1, 2001, pp. 22-39. doi:10.1109/7.913665
  7. H. L. Kennedy, “Comparison of MHT and PDA Track Initiation Performance,” International Conference on Radar, Adelaide, 2-5 September 2008, pp. 508-512. doi:10.1109/RADAR.2008.4653977
  8. M. Ekman, “Particle Filters and Data Association for Multi-Target Tracking,” The 11th International Conference on Information Fusion, Cologne, 30 June-3 July 2008, pp. 1-8.
  9. Z. T. Hu, Q. Pan and F. Yang, “A Novel Maneuvering Multi-Target Tracking Algorithm Based on Multiple Model Particle Filter in Clutters,” High Technology Letters, Vol. 17, No. 1, 2011, pp. 19-24.
  10. X. N. Ye, Q. Pan and Y. M. Cheng, “A New and Better Algorithm for Multi-Target Tracking in Dense Clutter,” Journal of Northwestern Polytechnical University, Vol. 22, No. 3, 2004, pp. 388-391.
  11. Q. Pan, X. N. Ye and H. C. Zhang, “Generalized Probability Data Association Algorithm,” Acta Electronica Sinica, Vol. 33, No. 3, 2005, pp. 467-472.