Resampling in particle filtering : comparison

• Autorzy: Kozierski P. , Lis M. , Ziętkiewicz J.

Warianty tytułu

PL

Resampling w filtracji cząsteczkowej : porównanie

• Języki publikacji: EN

Abstrakty

EN

The article presents over 20 different types and variants of resampling methods. Pseudo-code has been added for a description of each method. Comparison of methods has been performed using simulations (1,000 repetitions for each set of parameters). Based on the simulation results, it has been verified that among the methods for one processor implementation, the best working methods are those of Systematic resampling, one version of Stratified resampling and Deterministic Systematic resampling. The latter method does not require drawing numbers with uniform distribution. Among resampling methods for parallel computing, best quality is characterized by two variants of stratified resampling.

PL

W artykule przedstawiono ponad 20 różnych rodzajów i odmian metod resamplingu. Do opisu każdej metody dodano pseudokod. Porównanie metod wykonano na podstawie przeprowadzonych symulacji (1000 powtórzeń dla każdego zbioru parametrów). Na podstawie przeprowadzonych symulacji stwierdzono, ze wśród metod resamplingu przeznaczonych do implementacji na jednym procesorze, najlepiej działają Systematic resampling, jedna z odmian Stratified Resampling oraz Deterministic Systematic Resampling, przy czym ta ostatnia nie wymaga losowania liczb z rozkładu równomiernego. Wśród resamplingów przeznaczonych do obliczeń równoległych najlepszą jakością charakteryzowały się dwie odmiany Stratified resampling.

Słowa kluczowe

EN

resampling methods; parallel computing; systematic resampling; resampling

PL

metody resamplingu; obliczenia równoległe; resampling systematyczny; resampling

• Wydawca: Poznańskie Towarzystwo Przyjaciół Nauk
• Czasopismo: Studia z Automatyki i Informatyki
• Rocznik: 2013
• Tom: T. 38
• Strony: 35--64
• Opis fizyczny: Bibliogr. 19 poz., rys.

Twórcy

autor

Kozierski P.

• Poznan University of Technology, Faculty of Electrical Engineering, Institute of Control and Information Engineering, Piotrowo 3a street, 60-965 Poznan

autor

Lis M.

• Poznan University of Technology, Faculty of Electrical Engineering, Institute of Electrical Engineering and Electronics, Piotrowo 3a street, 60-965 Poznan

autor

Ziętkiewicz J.

• Poznan University of Technology, Faculty of Electrical Engineering, Institute of Control and Information Engineering, Piotrowo 3a street, 60-965 Poznan

Bibliografia

• [1] Arulampalam S., Maskell S., Gordon N., Clapp T., 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.
• [2] Bolic M., Djuric P. M., Hong S., New Resampling Algorithms for Particle Filters, Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing, Vol. 2, April 2003, pp. 589-592.
• [3] Candy J. V., Bayesian signal processing, WILEY, New Jersey 2009, pp. 237-298.
• [4] Carpenter J., Clifford P., Fearnhead P., Improved particle filter for nonlinear problems, IEE Proceedings – Radar, Sonar and Navigation, Vol. 146, No. 1, 2/1999, pp. 2-7.
• [5] Douc R., Cappe O., Moulines E., Comparison of Resampling Schemes for Particle Filtering, Proceedings of the 4th International Symposium on Image and Signal Processing and Analysis, September 2005, pp. 64-69.
• [6] Gordon N. J., Salmond D. J., Smith A. F. M., Novel approach to nonlinear/non-Gaussian Bayesian state estimation, IEE Proceedings F - Radar and Signal Processing, Vol. 140, No. 2, 1993, pp. 107-113.
• [7] Handeby G., Karlsson R., Gustafsson F., The Rao-Blackwellized Particle Filter: A Filter Bank Implementation, EURASIP Journal on Advances in Signal Processing, 2010, Article ID 724087, p. 10.
• [8] Heine K., Unified Framework for Sampling/Importance Resampling Algorithms, Proceedings of the 8th International Conference on Information Fusion, July 2005.
• [9] Hol J. D., Resampling in Particle Filters, report, Linkoping, 2004.
• [10] Kitagawa G., Monte Carlo Filter and Smoother for Non-Gaussian Nonlinear State Space Models, Journal of computational and graphical statistics, Vol. 5, No. 1, 1996, pp. 1-25.
• [11] Klaas M., De Freitas N., Doucet A., Toward Practical N2 Monte Carlo: The Marginal Particle Filter, arXiv preprint, arXiv:1207.1396, 2012.
• [12] Kozierski P., Lis M., Filtr cząsteczkowy w problemie śledzenia - wprowadzenie, Studia z Automatyki i Informatyki, Vol. 37, 2012, pp. 79-94.
• [13] Lee D. U., Luk W., Villasenor J. D., Zhang G., Leong P. H. W., A Hardware Gaussian Noise Generator Using the Wallace Method, Very Large Scale Integration (VLSI) Systems, IEEE Transactions on, Vol. 13, No. 8, 2005, pp. 911-920.
• [14] Murray L., GPU Acceleration of the Particle Filter: the Metropolis Resampler, arXiv preprint arXiv:1202.6163, 2012.
• [15] Murray L., Lee A., Jacob P., Rethinking resampling in the particle filter on graphics processing units, arXiv preprint, arXiv:1301.4019, 2013.
• [16] Simon D., Optimal State Estimation, WILEY-INTERSCIENCE, New Jersey 2006, pp. 461-484.
• [17] Soto A., Self Adaptive Particle Filter, Proceedings of the IJCAI, July 2005, pp. 1398-1406.
• [18] Straka O., Simandl M., Particle Filter with Adaptive Sample Size, Kybernetika, Vol. 47, No. 3, 2011, pp. 385-400.
• [19] Thrun S., Burgard W., Fox D., Probabilistic robotics, MIT Press, Cambridge, MA, 2005, pp. 67-90.