Probabilistic data association algorithm based on ensemble Kalman filter with observation iterated update①

Hu Zhentao (胡振涛), Fu Chunling

(*Institute of Image Processing and Pattern Recognition, Henan University, Kaifeng 475004, P.R.China)(**College of Physics and Electronics, Henan University, Kaifeng 475004, P.R.China)



Probabilistic data association algorithm based on ensemble Kalman filter with observation iterated update①

Hu Zhentao (胡振涛)*, Fu Chunling②

(*Institute of Image Processing and Pattern Recognition, Henan University, Kaifeng 475004, P.R.China)(**College of Physics and Electronics, Henan University, Kaifeng 475004, P.R.China)

Aiming at improving the observation uncertainty caused by limited accuracy of sensors, and the uncertainty of observation source in clutters, through the dynamic combination of ensemble Kalman filter(EnKF) and probabilistic data association(PDA), a novel probabilistic data association algorithm based on ensemble Kalman filter with observation iterated update is proposed. Firstly, combining with the advantages of data assimilation handling observation uncertainty in EnKF, an observation iterated update strategy is used to realize optimization of EnKF in structure. And the object is to further improve state estimation precision of nonlinear system. Secondly, the above algorithm is introduced to the framework of PDA, and the object is to increase reliability and stability of candidate echo acknowledgement. In addition, in order to decrease computation complexity in the combination of improved EnKF and PDA, the maximum observation iterated update mechanism is applied to the iteration of PDA. Finally, simulation results verify the feasibility and effectiveness of the proposed algorithm by a typical target tracking scene in clutters.

nonlinear filter, observation iterated update, ensemble Kalman filter (EnKF), probabilistic data association (PDA)

0 Introduction

Target tracking is used by the subjects to realize the process of state modeling, estimation and tracking for the objects concerned by means of various observation and calculation methods. In the military field, the application of this technology can provide basic information for fire control, threaten evaluation, situation assessment, and decision-making of the command and control system at different levels by issuing early warning against moving targets in ground, marine, air space and tracking them, discovering and locking onto unknown targets, and estimating and analyzing of their motion state and attribute features. In the civil field, ranging from air control system, robotic system and video monitor system to workpiece positioning in various production processes, identification and estimation of moving objects exist in all over various aspects of our production and life[1]. In actual realization of target tracking, the problem of model nonlinearity caused by the transforming process from target motion modeling to observation modeling coordinate system, the physical characteristics of sensors themselves, the problem of fuzzy, deficient, uncertain, inconsistent, even contradictory and conflicting information resulting from limited accuracy of sensors, complex detecting surroundings, the maneuvering, defrauding, disturbing, invisible, disguising and sheltering phenomenon of the targets are needed to be taken into consideration. In recent years, researches about target tracking mainly focus on two aspects including optimization of nonlinear filter and improvement of data association technology[2].

The optimal strategy dealing with nonlinear estimated problems needs integrate description of state conditional posteriori probability. However, because of demanding infinite parameters, the accurate description is hardly practically applied and just some of specific problems are given to the optimal solutions[3]. Recently, combining with analytical approximation, numerical approximation and Gaussian sum approximation, some suboptimal filters are proposed. The main feature of extended Kalman filter (EKF)[4], the typical implementation of analytical approximation, approximates to state and observation equations with local linearization technology and applies to state estimation of weak nonlinear system. But EKF will cause a large estimation error for strong nonlinear system, and the Jacobian matrixes of nonlinear function are difficult to obtain directly in some practical problems. Gird filter (GF)[5]is one of the typical implementations of numerical value approximation, the primary characteristic of which is to substitute integration by sum of the discrete variables. However, good approximation of state space is obtained only when the grid is dense enough, and the computational complexity will increase intensely with the increase of estimated system state dimension. Gaussian sum filter[6], as the typical implementation of Gaussian sum approximation, obtains the demanded approximate precision by selecting appropriate number of Gaussian mixtures. GSF is deficient because the weight of each Gaussian distribution is difficult to work out, and the number of Gaussian mixtures will probably increase exponentially as time goes on. In recent years, with the improvement of computer performance, the approach of handling nonlinear system problems with sampling method approximating to state posteriori probability distribution has caught attention of scholars in relevant research field gradually. The sampling method is divided into two categories, i.e. the deterministic sampling and the random sampling, according to different sampling pattern. Unscented Kalman filter (UKF)[7], central difference filter (CDF)[8], and cubature Kalman filter (CKF)[9]are some of the typical implementations of deterministic sampling method, which applies the approach of direct approximating to the probability density distribution of nonlinear function as a substitute to approximate to the nonlinear function by the UT transform or the numerical difference calculation, and the filtering precision and the implementing ability are superior to the above mentioned nonlinear filters. The typical implementations of random sampling method are particle filter (PF)[10]and EnKF[11]. PF realizes Bayesian sequential estimation in Monte-Carlo simulation framework with importance sampling and re-sampling, and obtains better filtering result than EKF and UKF. PF has advantages because it is appropriate to nonlinear system estimation of arbitrary noise distribution format. However, in the process of implementation, PF cannot overcome the intrinsic particles degeneracy and particles diversity scarcity after re-sampling. Moreover, the filtering precision of PF is closely related to the estimated system dimensions and the amount of particles, and those makes parameters in PF lack of universality for various applications[12]. EnKF generates initial samples set which can characterize state statistics with the sequential Monte-Carlo simulation method, and applies nonlinear function to samples in the initial sample set. EnKF gets the solution of state estimation at current time by solving the mean and covariance of converted samples set[13]. In addition, compared with PF, EnKF can weaken the adverse effects on filtering precision resulting from the uncertainty of observation caused by limited accuracy of sensors, and its estimation precision is superior to that of PF in the case that the number of samples is constant[14].

The key of data association technology is to deal with the uncertainty of observation source which can be derived from one certain target, clutter or multiple targets. At first, the track division method is applied to data association, but it is seldom used because it requires lots of calculation and has low precision[15]. Besides, taking the statistic distance between target and echo and the echo intensity as the decision criterion, the nearest neighbor method is constructed by the nearest neighbor theory of echo acknowledgement[16]. In the implementation of the nearest neighbor algorithm, a hard decision is necessary on the basis of single scan operation. It performs pretty well when the clutter is sparse, but its performance degrades when the clutters are dense. Aiming at the theoretical defect of nearest neighbor algorithm, with the criterion of all-adjacency, PDA provides a novel idea to implement the association in probability for all the observations in the gate of one certain track[17]. Since all observation information in the gate is considered, PDA has better association performance than the nearest neighbor algorithm in dense clutters. In addition, joint probability data association (JPDA), 0-1 integer scheme approach and multi-hypothesis approach are presented for multi-target tracking[18,19].

Based on the analysis mentioned above, combining with the character of data assimilation technology in EnKF the observation uncertainty caused by sensor’s limited accuracy can be improved, and the advantage of PDA is taken into consideration that it can deal with the uncertainty of observation source in clutters. The combination structure of EnKF and PDA is designed in this paper. Since the estimation precision of non-linear filter will directly affect the reliability and stability of the candidate echo acknowledgement and the resolution of equivalent observation in PDA, an improved EnKF (IEnKF) is constructed by adopting observation iterative update strategy, and the improved algorithm is introduced into the framework of PDA. A novel probabilistic data association algorithm based on ensemble Kalman filter with observation iterated update (IEnKF-PDA) is proposed in this paper, and the theory analysis and simulation verify the effectiveness of the proposed method.

1 The ensemble Kalman filter with observation iterated update

1.1 The standard ensemble Kalman filter

The non-linear state spatial model is as follows:

xk=f(xk-1)+uk

(1)

zk=h(xk)+vk

(2)

Xk/k-1

(3)

Xk-1/k-1

(4)

(5)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

Xk/k

(14)

(15)

(16)

(17)

(18)

1.2 The observation iterated update strategy

(19)

(20)

(21)

(22)

(23)

(24)

(25)

(26)

(27)

(28)

The capacity from repeated utilization of observation to improve the estimate performance is limited. In practical applications, the balance between filtering precision and calculation amount are taken into consideration, the number of iterations should not be too large, and the maximum iteration number L is usually set as 1 or 2[20].

2 Probabilistic data association algorithm based on ensemble Kalman filter with observation iterated update

The object of the proposed algorithm is to handle the observation uncertainty of target tracking process in clutters. The uncertainty not only consists of the observation uncertainty caused by sensor’s limited accuracy but also the uncertainty of observation source in the association realization of observation and target in clutters. The data assimilation technology in EnKF provides an effective approach to handle observation uncertainty caused by sensor’s limited accuracy according to Monte-Carlo simulation mechanism, and PDA provides an effective association method between observation and target based on all-adjacent principle. Meanwhile, considering the fact that the improvement of filtering precision can help lift the performance of data association, through dynamic combination of IEnKF and PDA, this section gives a novel PDA based on IEnKF.

2.1 Probabilistic data association

2.2 The concrete realization of IEnKF-PDA

(29)

here

(30)

P(θk,m|M,Z1:k-1)=

(31)

(32)

(33)

(34)

where λ denotes the spatial intensity of virtual observation (the number of clutters in unit area), λVkis the number of clutters in the relevant gate. Substitute Eq.(34) into Eq.(31) as follows.

P(θk,m|N,Z1:k-1)=

(35)

According to Eq.(30) and Eq.(35), Eq.(29) can be simplified further. And the mathematical expression of βk,mwith Possion distribution model of clutters is achieved as follows.

(36)

(37)

(38)

3 Simulation result and analysis

To verify the feasibility and effectiveness of the proposed algorithm, the observations from two-coordinate radar are adopted to realize the typical scene for target tracking of uniform motion in the X-Y plane. Combining with the dynamic characteristic of target motion and the physical property of radar sensors, the system state equation and the observation equation are as follows.

xk=Fxk-1+Γuk-1

zk,d=[γkθk]Τ+vk

θk=tan-1(yk/xk)

Fig.1 and Fig.4 show the motion trajectory of target and the clutter distribution in radar monitored region when λ is set to 0.01 or 0.025. Fig.2, Fig.3, Fig.5 and Fig.6 show the comparison of root mean square error (RMSE) of state estimation of five algorithms under 50 independent experiments. According to RMSE, the ranking from the best to worst of all five algorithms are as follows: PDA-IEnKF, PDA-PF, PDA-EnKF, PDA-UKF and PDA-EKF. It is worth noting that the filtering precision of PDA-PF and PDA-EnKF is similar, and PDA-IEnKF is better than PDA-EnKF. The main reason is that IEnKF improves the filtering precision relative to EnKF by the introduction of observation iterated update strategy. Table 1 and Table 2 provide quantitatively the mean of RMSE and the average running time in the cases that λ is set as 0.01 or 0.025, respectively. The data verifies the results analyzed above as well. In addition, in the same simulation condition, regarding to the cost time of algorithms, PDA-PF takes the first place, and PDA-IEnKF comes second but with the highest precision. The above results are conducive to reasonable selection of filters as for the two performance criterion of filtering precision and calculation amount in actual engineering.

Fig.1 Trajectory of target and clutters distribution under λ=0.01

Fig.2 Horizontal direction under λ=0.01

Fig.3 Vertical direction under λ=0.01

Fig.5 Horizontal direction under λ=0.025

Fig.6 Vertical direction under λ=0.025

AlgorithmHorizontaldirectionVerticaldirectionCosttimePDA-EKF0.144650.136660.04526PDA-UKF0.120160.112420.07352PDA-EnKF0.087280.081750.68515PDA-PF0.081260.0765610.1781PDA-IEnKF0.051230.062330.79342

Table 2 The comparison of the mean of RMSE and the average cost time under λ=0.025

4 Conclusions

The optimization of nonlinear filter and the effective acknowledgement of candidate echo are the key to realize target tracking process in clutters, and they are always the hot and difficult problems in target tracking field. This paper proposes a novel probabilistic data association algorithm based on ensemble Kalman filter with observation iterated update. In the framework of EnKF, combining with observation iterated update technology, IEnKF is constructed to make further improvement in filtering precision. And then IEnKF is adopted into the framework of PDA to improve the reliability and stability of echo acknowledgment and the calculation of conditional probability that the candidate echo comes from target. In addition, considering the structure characteristic of IEnKF, in order to decrease computation complexity further, the realization process of new algorithm is designed by the maximum observation iterated update mechanism. Results from practical simulation examples have verified that the proposed algorithm is superior to PDA and its improved algorithms. It is known that the application objects of PDA are mainly to solve the single target tracking in clutters, therefore, new algorithm is not suitable for multiple targets tracking. The realization of EnKF in multiple targets tracking will be our next step research emphasis.

[ 1] Daum F. Nonlinear filters: beyond the Kalman filter. IEEE Aerospace and Electronic Systems Magazine, 2005, 20(8): 57-69

[ 2] Chavali P, Nehorai A. Concurrent particle filtering and data association using game theory for tracking multiple maneuvering targets. IEEE Transactions on Signal Processing, 2013,61(20): 4934-4948

[ 3] Ronald P S Mahler. Statistical Multisource-multitarget Information Fusion. Boston, London: Artech House Publishers, 2007. 23-27

[ 4] Gustafsson F, Hendeby G. Some relations between extended and unscented Kalman filters. IEEE Transactions on Signal Processing, 2012 ,60(2): 545-555

[ 5] Laneuville D, Vignal H. Grid based target motion analysis. In: Proceedings of the IEEE Aerospace Conference, Big Sky, USA, 2007. 1-7

[ 6] Terejanu G, Singla P, Singh T, et al. Adaptive Gaussian sum filter for nonlinear bayesian estimation. IEEE Transactions on Automatic Control, 2011, 56(9):2151-2156

[ 7] Dunik J, Simandl M, Straka O. Unscented Kalman filter: aspects and adaptive setting of scaling parameter. IEEE Transactions on Automatic Control, 2012,57(9):2411-2416

[ 8] Wang Y F, Sun F C, Zhang Y A, et al. Central difference particle filter applied to transfer alignment for SINS on missiles. IEEE Transactions on Aerospace and Electronic Systems, 2012,48(1): 375-387

[ 9] Arasaratnam I, Haykin S, Hurd T R. Cubature Kalman filtering for continuous-discrete systems: theory and simulations. IEEE Transactions on Signal Processing, 2010, 58(10): 4977-4993

[10] Karlsson R. Particle filter for positioning and tracking applications[Ph.D dissertation]. Linkoping: Linkoping University, 2005

[11] Evensen G. Sequential data assimilation with a nonlinear quasigeostrophic model using Monte Carlo methods to forecast error statistics. Geophys, 1994, 99(5):143-162

[12] Cappe O, Godsill S J, Moulines E. An overview of existing methods and recent advances in sequential Monte Carlo. Proceedings of the IEEE, 2007,95(5):899-924

[13] Gillijns S, Mendoza O B, Chandrasekar J, et al. What is the ensemble Kalman filter and how well does it work. In: Proceedings of the American Control Conference, Minneapolis, USA, 2006. 4448-4453

[14] Evensen G. The ensemble Kalman filter for combined state and parameter estimation. IEEE Control Systems, 2009, 29(3): 83-104

[15] Chummun M R, Kirubarajan T, Pattipati K R, et al. Fast data association using multidimensional assignment with clustering. IEEE Transactions on Aerospace and Electronic Systems, 2001,37(3): 898-913

[16] Wijesoma W S, Perera L D L,Adams M D. Toward multidimensional assignment data association in robot localization and mapping. IEEE Transactions on Robotics, 2006 , 22(2): 350-365

[17] Bar-Shalom Y, Daum F, Huang J. The probabilistic data association filter. IEEE Control Systems, 2009, 29(6):82-100

[18] Svensson D,Ulmke M, Hammarstrand L. Multitarget sensor resolution model and joint probabilistic data association. IEEE Transactions on Aerospace and Electronic Systems, 2012 ,48(4): 3418-3434

[19] Panta K, Ba-Ngu V, Sumeetpal S. Novel data association schemes for the probability hypothesis density filter. IEEE Transactions on Aerospace and Electronic Systems, 2007, 43(2): 556-570

[20] Chang L, Hu B, Chang G, et al. Marginalised iterated unscented Kalman filter. IET Control Theory & Applications, 2012,6(6): 847-854

[21] Shaoshi Y， Tiejun L， Maunder R G, et al. From nominal to true a posteriori probabilities: an exact Bayesian theorem based probabilistic data association approach for iterative MIMO detection and decoding. IEEE Transactions on Communications, 2013,61(7):2782-2793

[22] Habtemariam B K, Tharmarasa R, Kirubarajan T, et al. Multiple detection probabilistic data association filter for multistatic target tracking. In: Proceedings of the 14th International Conference on Information Fusion, Chicago, USA, 2011. 1-6

Hu Zhentao, born in 1979. He received his Ph.D degrees in Control Science and Engineering from Northwestern Polytechnical University in 2010. He also received his B.S. and M.S. degrees from Henan University in 2003 and 2006 respectively. Now, he is an assistant professor of College of Computer and Information Engineering, Henan University. His research interests include complex system modeling and estimation, target tracking and particle filter, etc.

10.3772/j.issn.1006-6748.2015.03.009

①Supported by the National Nature Science Foundation of China (No. 61300214), the Science and Technology Innovation Team Support Plan of Education Department of Henan Province (No. 13IRTSTHN021), the National Natural Science Foundation of Henan Province (No.132300410148), the Science and Technology Research Key Project of Education Department of Henan Province (No.13A413066), the Post-doctoral Science Foundation of China (No.2014M551999), the Funding Scheme of Young Key Teacher of Henan Province Universities (No.2013GGJS-026), the Postdoctoral Fund of Henan Province (No. 2013029) and the Outstanding Young Cultivation Foundation of Henan University (No.0000A40366).

②To whom correspondence should be addressed. E-mail: fuchunling@henu.edu.cn Received on June 15， 2014**, Li Junwei*