Particle filter based on iterated importance density function and parallel resampling

Abstract

The design, analysis and parallel implementation of particle filter (PF) were investigated. Firstly, to tackle the particle degeneracy problem in the PF, an iterated importance density function (IIDF) was proposed, where a new term associating with the current measurement information (CMI) was introduced into the expression of the sampled particles. Through the repeated use of the least squares estimate, the CMI can be integrated into the sampling stage in an iterative manner, conducing to the greatly improved sampling quality. By running the IIDF, an iterated PF (IPF) can be obtained. Subsequently, a parallel resampling (PR) was proposed for the purpose of parallel implementation of IPF, whose main idea was the same as systematic resampling (SR) but performed differently. The PR directly used the integral part of the product of the particle weight and particle number as the number of times that a particle was replicated, and it simultaneously eliminated the particles with the smallest weights, which are the two key differences from the SR. The detailed implementation procedures on the graphics processing unit of IPF based on the PR were presented at last. The performance of the IPF, PR and their parallel implementations are illustrated via one-dimensional numerical simulation and practical application of passive radar target tracking.

Keywords

particle filter / iterated importance density function / least squares estimate / parallel resampling / graphics processing unit

References

[1] GregW, GaryBAn introduction to the Kalman filter [R], 2006North Carolina, USADepartment of Computer Science, University of North Carolina

[2] SimonJ, JerrertU. Unscented filtering and nonlinear estimation [J]. Proceedings of the IEEE, 2004, 92(3): 401-422

[3] ArasaratnamI, HaykinS. Cubature Kalman filters [J]. IEEE Transactions on Automatic Control, 2009, 54(6): 1254-1269

[4] ArulampalamM S, MaskellS, GordonN, ClappT. A tutorial on particle filters for online nonlinear/non-Gaussian Bayesian tracking [J]. IEEE Transactions on Signal Processing, 2002, 50(2): 174-188

[5] LiH-w, WangJ. Particle filter for manoeuvring target tracking via passive radar measurements with glint noise [J]. IET Radar Sonar and Navigation, 2012, 6(3): 180-189

[6] SedaiS, BennamounM, HuynhD Q. A Gaussian process guided particle filter for tracking 3D human pose in video [J]. IEEE Transactions on Image Processing, 2013, 22(11): 4286-4300

[7] ZhouN, MengD, LuS. Estimation of the dynamic states of synchronous machines using an extended particle filter [J]. IEEE Transactions on Power Systems, 2013, 28(7): 4152-4161

[8] IsabellaS, MatthiasB. Advanced particle filtering for airborne vehicle tracking in urban areas [J]. IEEE Geoscience and Remote Sensing Letters, 2014, 11(3): 686-690

[9] GordonN, SalmondD J, SmithA F M. Novel approach to nonlinear/non-Gaussian Bayesian state estimation [J]. IEE Proceedings F: Radar and Signal Processing, 1993, 140(2): 107-113

[10] KitagawaG. Monte Carlo filter and smoother and non-Gaussian nonlinear state space models [J]. Journal of Computational and Graphical Statistics, 1996, 5(1): 1-25

[11] MerweR V D, DoucetA, FreitasN, EricWThe unscented particle filter [R], 2000Cambridge, EnglandEngineering Department, Cambridge University

[12] ZuoJ-y, JiaY-n, GaoQ-x. Simplified unscented particle filter for nonlinear/non-Gaussian Bayesian estimation [J]. Journal of Systems Engineering and Electronics, 2013, 24(3): 537-544

[13] ZuoJ-y, JiaY-n. Adaptive iterated particle filter [J]. Electronics Letters, 2013, 49(12): 556-557

[14] ZuoJ-y, JiaY-n, ZhangW, GaoQ-x. Particle filter with importance density function generated by updated system equation [J]. Journal of Central South University, 2013, 20(10): 2700-2707

[15] PittM K, ShephardN. Filtering via simulation: Auxiliary particle filters [J]. Journal of the American Statistical Association, 1999, 94(446): 590-599

[16] WanY-f, SunF-c, ZhangY-a, LiuH-p, MinH-b. Central difference particle filter applied to transfer alignment for SINS on missiles [J]. IEEE Transactions on Aerospace and Electronic Systems, 2012, 48(1): 375-387

[17] MalikM, TardiT. Gravity optimised particle filter for hand tracking [J]. Pattern Recognition, 2014, 47(1): 194-207

[18] BolicM, DjuricP M, HongS-j. Resampling algorithms and architectures for distributed particle filters [J]. IEEE Transactions on Signal Processing, 2005, 53(7): 2442-2450

[19] ChitchianM, SimonettoA, AmesfoortA S, KeyiczkyetT. Distributed computation particle filters on GPU architectures for real-time control applications [J]. IEEE Transactions on Control Systems Technology, 2013, 21(6): 2224-2238

[20] KyuyeonH, WonyongS. Load balanced resampling for real-time particle filtering on graphics processing units [J]. IEEE Transactions on Signal Processing, 2013, 61(2): 411-419

[21] LiT-c, BolicM, DjuricP M. Resampling methods for particle filtering [J]. IEEE Signal Processing Magazine, 2015, 32(3): 70-86

[22] BALASINGAM B, BOLIC M, DJURIC P M, MIGUEZ J. Efficient distributed resampling for particle filters [C]// IEEE International Conference on Acoustics, Speech and Signal Processing. Prague: IEEE, 2011: 3772–3775.

[23] LiT-c, SunS-d, SattarT P. Adapting sample size in particle filters through KLD-resampling [J]. Electronics Letters, 2013, 49(12): 740-742