PMCCPMCCPMCC

Search tips
Search criteria 

Advanced

 
Logo of sensorsMDPI Open Access JournalsMDPI Open Access JournalsThis articleThis JournalInstructions for authorssubscribe
 
Sensors (Basel). 2016 June; 16(6): 805.
Published online 2016 June 1. doi:  10.3390/s16060805
PMCID: PMC4934231

An Improved Interacting Multiple Model Filtering Algorithm Based on the Cubature Kalman Filter for Maneuvering Target Tracking

Xue-Bo Jin, Academic Editor

Abstract

In order to improve the tracking accuracy, model estimation accuracy and quick response of multiple model maneuvering target tracking, the interacting multiple models five degree cubature Kalman filter (IMM5CKF) is proposed in this paper. In the proposed algorithm, the interacting multiple models (IMM) algorithm processes all the models through a Markov Chain to simultaneously enhance the model tracking accuracy of target tracking. Then a five degree cubature Kalman filter (5CKF) evaluates the surface integral by a higher but deterministic odd ordered spherical cubature rule to improve the tracking accuracy and the model switch sensitivity of the IMM algorithm. Finally, the simulation results demonstrate that the proposed algorithm exhibits quick and smooth switching when disposing different maneuver models, and it also performs better than the interacting multiple models cubature Kalman filter (IMMCKF), interacting multiple models unscented Kalman filter (IMMUKF), 5CKF and the optimal mode transition matrix IMM (OMTM-IMM).

Keywords: target tracking, cubature Kalman filter, unscented Kalman filter, interacting multiple models

1. Introduction

Bayes filtering algorithms have been broadly used in target tracking systems [1,2,3,4], while a large number of Gaussian approximation filters and Monte Carlo filters have been introduced to solve target tracking problems [5]. Although the particle filter (PF) can deal with non-linear and non-Gaussian systems, the computational complexity always makes its use prohibitive [6]. Gaussian approximation filtering algorithms are more efficient. Among the Gaussian approximation filters, the extended Kalman filter (EKF) has been widely used in nonlinear systems [7,8]. It uses first order Taylor series expansion, which can induce deviations when the systems have higher order and complex non-linear character. In order to reduce the system linearization errors, the unscented Kalman filter (UKF) was introduced to deal with nonlinear systems and it outperforms EKF [9]. Recently, Arasaratnam and Haykin presented the cubature Kalman filter (CKF) based on the spherical-radial cubature rule [10,11]. The CKF has a rigid mathematical proof that is different from the UKF, and both UKF and CKF can approximate the model of the system using specially chosen points. It has been proved that when the dimension of the system is three, the CKF has the same performance as the UKF [12].

Blom and Shalom have proposed the interacting multiple model (IMM) algorithm based on a generalized pseudo-random algorithm to decrease the error of single model algorithm, which will improve the quick response and accuracy of target tracking [13]. The IMM algorithm processes all the models simultaneously and changes different models by checking their weights. It has been proved that the IMM algorithm performs better than any single model algorithm in complex tracking problems [14]. Many filters have been integrated with the IMM algorithm to enhance the accuracy and quick response of nonlinear target tracking [14,15,16]. The performance of interacting multiple models unscented Kalman filter (IMMUKF) is compared with the interacting multiple models extended Kalman filter (IMMEKF), and the results show that IMMUKF performs better than IMMEKF in bearings-only maneuvering tracking problems [15]. However, when the dimension of the system is more than three, the weights of UKF are negative which will cause the divergence of the filter [12,17]. Then the CKF is introduced in IMM to overcome the issue, and the new algorithm can reduce the computational complexity and improve the accuracy of the filter [17,18]. Lee, Motai and Choi have proposed the multichannel interacting multiple model estimator (MC-IMME) to improve the overall performance of the traditional particle filter, ensemble KF and IMME [19]. The multiple delta quaternion extended Kalman filter is proposed in [20] for head orientation prediction. The proposed multiple model delta quaternion (DQ) (MMDQ) filters integrate constant velocity (CV) and constant acceleration (CA) DQ filters in an IMME framework, and the experimental results show that the new filter performs better than DQ-EKF albeit with increased computation. In [21], the authors proposed a sensor fusion algorithm which introduces dynamic noise covariance matrix into interacting multiple models. The proposed filter is more accurate than the Kalman filter when there are abrupt changes in the path of the vehicle. In order to improve the accuracy of the traditional IMM algorithm, the optimal mode transition matrix IMM (OMTM-IMM) algorithm was proposed in [22]. The OMTM-IMM utilizes the linear minimum variance theory to minimize the error of the initial state and the simulation results show that it outperforms the traditional IMM when the sojourn times of the system are not known.

In this paper, the interacting multiple models five degree cubature Kalman filter (IMM5CKF) based on a five degree cubature Kalman filter and IMM algorithm is proposed to improve the tracking accuracy, model estimation accuracy and quick response of target tracking algorithms. The negative weights of 5CKF go to 0 when the system dimensions go to ∞, so 5CKF is more stable than UKF [23]. The simulation results show that the IMM5CKF exhibits better accuracy and switching sensitivity performance than IMMCKF, IMMUKF, 5CKF and OMTM-IMM. The remainder of the paper is organized as follows: the high degree of cubature Kalman filter is analyzed in Section 2. In Section 3, IMM5CKF is derived. The performance of the target tracking algorithms are compared in a benchmarked target tracking problem in Section 4. Conclusions are given in Section 5.

2. Five Degree Cubature Kalman Filter

The five degree cubature Kalman filter is proposed to improve the accuracy of the traditional Cubature Kalman Filter [23]. It chooses deterministic odd points to transfer the nonlinear functions to calculate the posterior mean and covariance of the system.

Supposing state variables x=N(x¯,P), where x¯ is mathematical expectation of x, P is the covariance of x. The five degree Cubature Kalman Filter includes two steps, time update and measurement update.

2.1. Time Update

(1) Factorize

The Cholesky decomposition of Pk1|k1 is calculated as:

Pk1|k1=Sk1|k1Sk1|k1T
(1)

(2) Evaluate the cubature points:

X0i,k1|k1=x^k1|k1
(2)

X1i,k1|k1=(n+2)Sk1|k1ei+x^k1|k1
(3)

X2i,k1|k1=(n+2)Sk1|k1ei+x^k1|k1
(4)

X3i,k1|k1=(n+2)Sk1|k1si++x^k1|k1
(5)

X4i,k1|k1=(n+2)Sk1|k1si++x^k1|k1
(6)

X5i,k1|k1=(n+2)Sk1|k1si+x^k1|k1
(7)

X6i,k1|k1=(n+2)Sk1|k1si+x^k1|k1
(8)

si+={12(ej+el)}:j<l,j,l=1,2,...,n
(9)

si={12(ejel)}:j<l,j,l=1,2,...,n
(10)

w0=2n+2
(11)

w1=4n2(n+2)2,i=1,2,n
(12)

w2=2(n+2)2,i=1,2,...,n(n1)/2
(13)

where w0, w1 and w2 is the weights of the cubature points, ei is the unit vector.

(3) Evaluate the propagated cubature points

The sample points are obtained by propagating the cubature points through the state equation as:

X0i,k|k1=f(X0i,k1|k1)
(14)

X1i,k|k1=f(X1i,k1|k1)
(15)

X2i,k|k1=f(X2i,k1|k1)
(16)

X3i,k|k1=f(X3i,k1|k1)
(17)

X4i,k|k1=f(X4i,k1|k1)
(18)

X5i,k|k1=f(X5i,k1|k1)
(19)

X6i,k|k1=f(X6i,k1|k1)
(20)

(4) Estimate the predicted points

State prediction x^k|k1 is then calculated by the weighted combination of sample points as:

x^k|k1=w0X0i,k|k1+w1X1+w2X2
(21)

X1=i=1n(X1i,k|k1+X2i,k|k1)
(22)

X2=i=1n(n1)/2(X3i,k|k1+X4i,k|k1+X5i,k|k1+X6i,k|k1)
(23)

(5) Estimate the predicted error covariance:

Pk|k1=w0Xoi,k|k1Xoi,k|k1T+P1+P2
(24)

P1=w1i=1n(X1i,k|k1X1i,k|k1T+X2i,k|k1X2i,k|k1T)
(25)

P2=w2i=1n(n1)/2(X3i,k|k1X3i,k|k1T+X4i,k|k1X4i,k|k1T+X5i,k|k1X5i,k|k1T+X6i,k|k1X6i,k|k1T)
(26)

2.2. Measurement Update

(1) Factorize:

Pk|k1=Sk|k1Sk|k1T
(27)

(2) Evaluate the cubature points:

X0i,k|k1=x^k|k1
(28)

X1i,k|k1=(n+2)Sk|k1ei+x^k|k1
(29)

X2i,k|k1=(n+2)Sk|k1ei+x^k|k1
(30)

X3i,k|k1=(n+2)Sk|k1si++x^k|k1
(31)

X4i,k|k1=(n+2)Sk|k1si++x^k|k1
(32)

X5i,k|k1=(n+2)Sk|k1si+x^k|k1
(33)

X6i,k|k1=(n+2)Sk|k1si+x^k|k1
(34)

(3) Evaluate the propagated cubature points

The sample points are obtained by propagating the cubature points through the observation equation:

Z0i,k|k1=h(X0i,k|k1)
(35)

Z1i,k|k1=h(X1i,k|k1)
(36)

Z2i,k|k1=h(X2i,k|k1)
(37)

Z3i,k|k1=h(X3i,k|k1)
(38)

Z4i,k|k1=h(X4i,k|k1)
(39)

Z5i,k|k1=h(X5i,k|k1)
(40)

Z6i,k|k1=h(X6i,k|k1)
(41)

(4) Estimate the predicted measurement:

z^k|k1=w.0Z0i,k|k1+w1Z1+w2Z2
(42)

Z1=i=1n(Z1i,k|k1+Z2i,k|k1)
(43)

Z2=i=1n(n1)/2(Z3i,k|k1+Z4i,k|k1+Z5i,k|k1+Z6i,k|k1)
(44)

(5) Estimate the innovation covariance matrix:

Pzz,k|k1=w0Z0i,k|k1Z0i,k|k1T+Pzz1+Pzz2z^k|k1z^k|k1T+Rk
(45)

Pzz1=w1i=1n(Z1i,k|k1Z1i,k|k1T+Z2i,k|k1Z2i,k|k1T)
(46)

Pzz2=w2i=1n(n1)2(Z3i,k|k1Z3i,k|k1T+Z4i,k|k1Z4i,k|k1T+Z5i,k|k1Z5i,k|k1T+Z6i,k|k1Z6i,k|k1T)
(47)

(6) Estimate the cross-covariance matrix:

Pxz,k|k1=w0X0i,k|k1Z0i,k|k1T+Pxz1+Pxz2x^k|k1z^k|k1T
(48)

Pxz1=w1i=1n(X1i,k|k1Z1i,k|k1T+X2i,k|k1Z2i,k|k1T)
(49)

Pxz2=w2i=1n(n1)/2(X3i,k|k1Z3i,k|k1T+X4i,k|k1Z4i,k|k1T+X5i,k|k1Z5i,k|k1T+X6i,k|k1Z6i,k|k1T)
(50)

(7) Estimate the Kalman gain:

Wk=Pxz,k|k1Pzz,k|k11
(51)

(8) Estimate the updated state:

x^k|k=x^k|k1+Wk(zkz^k|k1)
(52)

(9) Estimate the corresponding error covariance:

Pk|k=Pk|k1WkPzz,k|k1WkT
(53)

3. IMM High Degree Cubature Kalman Filter

In the paper, the proposed IMM5CKF includes the merits of the 5CKF algorithm and IMM algorithm. The main character of IMM5CKF is that it calculates the state distribution and error covariance matrix by choosing an odd number of special cubature points with equal weights, and the negative weights go to 0 when the dimension of the system goes to . This means that it is more stable than UKF. The IMM-5CKF algorithm includes input integration, five degree cubature Kalman filter, model probability update and output integration. The structure diagram is shown in Figure 1. The filtering processes are shown in the following subsection.

Figure 1
IMM-5CKF structure diagram.

3.1. Input Integration

uk1|k1i/j=pijuk1iCj
(54)

X^k1|k10j=X^k1|k1iuk1|k1i/j
(55)

Pk1|k10j=i=1ruk1|k1i/j{Pk1|k1i+[X^k1|k1iX^k1|k10j][X^k1|k1iX^k1|k10j]T}
(56)

where Cj=i=1rpijuk1i, uk1|k1i/j is the conditional probability of model i at time k1, uk1i is the probability of model i at time k1, X^k1|k10j is the initial mean value of model j, Pk1|k10j is the initial error covariance, X^k1|k1i is the estimated value of model i at time k1, Pk1|k1i is the relative covariance.

3.2. Five Degree Cubature Kalman Filtering

The mixed initial value and measure value (z) are the input of each filter at time k. Then the new state vector X^k|kj, error covariance Pk|kj, predicted measure value zk|k1j and residual vkj can be got from the 5CKF.

The likelihood value Lkj is:

Lkj=N(z;zk|k1j,vkj)=12πVkj·exp(12[zkz^k|k1j]T(Vkj)1[zkz^k|k1j])
(57)

where Vkj is the associated covariance of residual vkj.

3.3. Model Probability Update

It has been known that if the filter model matches with the actual model, the filter residual is zero and the variance v(k) is Gaussian White Noise. Then the model probability can be updated by Equation (58):

ukj=LkjCjj=1nmLkjCj
(58)

3.4. Output Integration

The probabilities of the model are integrated with the estimated value of each filter based on the given weights. The output of IMM-5CKF can be calculated as:

X^k|k=j=1rXk|kjukj
(59)

Pk|k=j=1rukj{Pk|kj+[X^k|kjX^k|k][X^k|kjX^k|k]T}
(60)

4. Results and Discussion

In this section, the IMM-5CKF is compared with IMMCKF, IMMUKF, 5CKF and OMTM-IMM in a benchmark target tracking scenario. The state variable at time k is Xk=[x,x˙,y,y˙]T, where x and y are the position variables, x˙ and y˙ are the velocity variables.

The coordinated turn model is:

F2=[1sin(ωT)ω0(cos(ωT)1)ω0cos(ωT)0sin(ωT)0(1cos(ωT))ω1sin(ωT)ω0sin(ωT)0cos(ωT)]
(61)

where ω is the turn rate and T is the sampling interval. The right turn rate is defined as −3°, and the left turn rate is 3°.

The measurement equation of the system is:

Z=[10000010]+R
(62)

where R is the measurement noise of the system.

The initial state X0=[1000m,200 m/s,1000m,200 m/s]T, initial associate covariance is P0=diag([1000,10,1000,10]), process noise Q~N(0,q), q=[10,0;0,10], process noise weight matrix is G=[T22,0;T,0;0,T22;0,T]. The measure noise R~N(0,r), with r=diag([20,0.1]).

The simulation time simTime=100s, the step time T=1s. The target turns right during 20s~40s, turns left during 60s~80s, and maintains uniform motion during the other time. The model transition probability is:

pij=[0.90.050.050.10.80.10.050.150.8]
(63)

The root-mean square error (RMSE) of position and velocity are used to contrast the performance of the filtering algorithms. The RMSE defined in state vector X at k is:

RMSE=n=1n1kk=1k(Xk,nX^k,n)2n
(64)

Figure 2 shows the target trajectory after 100 Monte Carlo simulations, from which it can be found that all the algorithms could track the trajectory of the target. Figure 3 and Figure 4 show that the estimated RMSEs in position and velocity of IMM5CKF, IMMCKF, IMMUKF, 5CKF and OMTM-IMM respectively. From Figure 3 and Figure 4, it can be found that all the algorithms exhibit stable characteristics, and there are no error divergence during the simulation time. In addition, the results show that the RMSEs of IMM5CKF are less than those of the other algorithms and the performance is more stable. In Figure 3 and Figure 4, the RMSEs of 5CKF is the largest, which means a single model algorithm cannot adapt to changeable target tracking problems. In [21], authors had proved that OMTM-IMM performs better than traditional IMM algorithm. In Figure 3 and Figure 4, it can be seen that the accuracy of OMTM-IMM is better than 5CKF, but worse than that of the other algorithms which are based on improved nonlinear filters.

Figure 2
Target Trajectory.
Figure 3
RMSEs of (a) X-position and (b) Y-position.
Figure 4
RMSEs of (a) X-velocity and (b) Y-velocity.

The RMSEs of the IMM5CKF, IMMCKF, IMMUKF, 5CKF and OMTM-IMM are shown in Table 1. The data shows that the tracking accuracy of IMM-5CKF is better than that of the other algorithms with increasing computational load.

Table 1
The RMSEs of the different target tracking algorithms.

Figure 5, Figure 6 and Figure 7 show the model probabilities of IMM5CKF, IMMCKF, IMMUKF and OMTM-IMM.

Figure 5
Model probabilities of model 1.
Figure 6
Model probabilities of model 2.
Figure 7
Model probabilities of model 3.

Figure 5, Figure 6 and Figure 7 demonstrate that IMM5CKF, IMMCKF, IMMUKF and OMTM-IMM can effectively track the model characteristics of a maneuvering target. It is also found that the IMM-5CKF can capture the kinematics of maneuvering in time once the motion state changes at time t=20s, t=40s, t=60s and t=80s. The simulation results show that IMM5CKF has an obvious advantage over the other algorithms in target tracking problems.

5. Conclusions

In this paper, IMM5CKF is proposed to enhance the tracking accuracy, model estimation accuracy and response sensitivity of nonlinear maneuvering target tracking problems. The algorithm introduces a five degree cubature Kalman filter into interacting multiple models which simultaneously disposes of all the models through a Markov Chain. A classical target tracking problem is utilized to demonstrate that the IMM5CKF can indeed improve the quick response sensitivity of target tracking algorithm, and it exhibits more accurate than IMMCKF, IMMUKF, CKF and OMTM-IMM. In our future research, the study may focus on multisensor navigation and positioning systems. The proposed algorithm should be suitable for the complex real environments according to the analysis.

Acknowledgments

The authors would like to thank all the reviewers for helping improve the clarity of the presentation of this paper. This work is supported by the National Natural Science Foundation (61571148), China Postdoctoral Science Foundation Grant (2014M550182), Heilongjiang Postdoctoral Special Fund (LBH-TZ0410) and Innovation of Science and Technology Talents in Harbin (2013RFXXJ016).

Author Contributions

Author Contributions

Wei Zhu and Wei Wang conceived, designed and performed the experiments; Wei Zhu and Wei Wang analyzed the data; Gannan Yuan contributed the analysis tools; Wei Zhu wrote the paper.

Conflicts of Interest

Conflicts of Interest

The authors declare no conflict of interest.

References

1. Read J., Achutegui K., Miguez J. A distributed particle filter for nonlinear tracking in wireless sensor networks. Signal Process. 2014;98:121–134. doi: 10.1016/j.sigpro.2013.11.020. [Cross Ref]
2. Li W., Jia Y., Du J., Zhang J. PHD filter for multi-target tracking with glint noise. Signal Process. 2014;94:48–56. doi: 10.1016/j.sigpro.2013.06.012. [Cross Ref]
3. Meyer F., Hlinka O., Hlawatsch F. Sigma point belief propagation. IEEE Signal Process. Lett. 2014;21:145–149. doi: 10.1109/LSP.2013.2290192. [Cross Ref]
4. Zhang T., Wu R. Affinity propagation clustering of measurements for multiple extended target tracking. Sensors. 2015;15:22646–22659. doi: 10.3390/s150922646. [PMC free article] [PubMed] [Cross Ref]
5. Morelande M.R., Garcia-Fernandez A.F. Analysis of Kalman filter approximations for nonlinear measurements. IEEE Trans. Signal Process. 2013;66:5477–5484. doi: 10.1109/TSP.2013.2279367. [Cross Ref]
6. Bugallo M.F., Xu S., Djurić P.M. Performance comparison of EKF and particle filtering methods for maneuvering targets. Digit. Signal Process. 2007;17:774–786. doi: 10.1016/j.dsp.2006.10.001. [Cross Ref]
7. Jwo D.J., Wang S.H. Adaptive fuzzy strong tracking extended Kalman filtering for GPS navigation. IEEE Sens. J. 2007;7:778–789. doi: 10.1109/JSEN.2007.894148. [Cross Ref]
8. Frogerais P., Bellanger J.J., Senhadji L. Various ways to compute the continuous–discrete extended Kalman filter. IEEE Trans. Autom. Control. 2012;57:1000–1004. doi: 10.1109/TAC.2011.2168129. [Cross Ref]
9. Julier S., Uhlmann J., Durrant-Whyte H.F. A new method for the nonlinear transformation of means and covariances in filters and estimators. IEEE Trans. Autom. Control. 2000;45:477–482. doi: 10.1109/9.847726. [Cross Ref]
10. Arasaratnam I., Haykin S. Cubature Kalman filters. IEEE Trans. Autom. Control. 2009;54:1254–1269. doi: 10.1109/TAC.2009.2019800. [Cross Ref]
11. Arasaratnam I., Haykin S., Hurd T.R. Cubature Kalman filtering for continuous–discrete systems: Theory and simulations. IEEE Trans. Signal Process. 2010;58:4977–4993. doi: 10.1109/TSP.2010.2056923. [Cross Ref]
12. Sun F., Tang L.J. Estimation precision comparison of Cubature Kalman filter and Unscented Kalman filter. Control Decis. 2013;28:303–308.
13. Blom H.A., Bar-Shalom Y. The interacting multiple model algorithm for systems with markovian switching coefficients. IEEE Trans. Autom. Control. 1998;33:780–783. doi: 10.1109/9.1299. [Cross Ref]
14. Cui N., Hong L., Layne J.R. A comparison of nonlinear filtering approaches with an application to ground target tracking. Signal Process. 2005;85:1469–1492. doi: 10.1016/j.sigpro.2005.01.010. [Cross Ref]
15. Gao L., Xing J., Ma Z., Sha J., Meng X. Improved IMM algorithm for nonlinear maneuvering target tracking. Procedia Eng. 2012;2:4117–4123. doi: 10.1016/j.proeng.2012.01.630. [Cross Ref]
16. Zhang Y., Guo C., Hu H., Liu S., Chu J. An Algorithm of the Adaptive Grid and Fuzzy Interacting Multiple Model. J. Mar. Sci. Appl. 2014;13:340–345. doi: 10.1007/s11804-014-1266-6. [Cross Ref]
17. Li W., Jia Y. Location of mobile station with maneuvers using an IMM-based cubature Kalman filter. IEEE Trans. Ind. Electron. 2012;59:4338–4348. doi: 10.1109/TIE.2011.2180270. [Cross Ref]
18. Wan M., Li P., Li T. Tracking maneuvering target with angle-only measurements using IMM algorithm based on CKF; Proceedings of the 2010 International Conference on Communications and Mobile Computing; Shenzhen, China. 12–14 April 2010.
19. Lee S.J., Motai Y., Choi H. Tracking human motion with multichannel interacting multiple model. IEEE Trans. Ind. Inform. 2013;9:1751–1763.
20. Himberg H., Motai Y., Bradley A.P. A multiple model approach to tracking head orientation with delta quaternions. IEEE Trans. Cybern. 2013;43:90–101. doi: 10.1109/TSMCB.2012.2199311. [PubMed] [Cross Ref]
21. Barrios C., Motai Y., Huston D. Intelligent forecasting using dead reckoning with dynamic errors. IEEE Trans. Ind. Inform. 2015 doi: 10.1109/TII.2015.2514086. [Cross Ref]
22. Zhou W., Cai J., Sun L., Shen C. An improved interacting multiple model algorithm used in aircraft tracking. Math. Probl. Eng. 2014;2014:813654. doi: 10.1155/2014/813654. [Cross Ref]
23. Jia B., Xin M., Cheng Y. High-degree cubature Kalman filter. Automatica. 2013;49:510–518. doi: 10.1016/j.automatica.2012.11.014. [Cross Ref]

Articles from Sensors (Basel, Switzerland) are provided here courtesy of Multidisciplinary Digital Publishing Institute (MDPI)