Resampling methods for particle filtering: identical distribution, a new method, and comparable study*

Li Tian-cheng; Villarrubia Gabriel; Sun Shu-dong; Corchado M.; Bajo Javier

doi:10.1631/FITEE.1500199

Your Location：

Home >

Browse articles >

Resampling methods for particle filtering: identical distribution, a new method, and comparable study*

Electrical & Electronic Engineering | Updated：2022-06-06

- Resampling methods for particle filtering: identical distribution, a new method, and comparable study*
- 粒子滤波重采样：同分布原则、一种新方法以及综合对比
- Frontiers of Information Technology & Electronic Engineering Vol. 16, Issue 11, Pages: 969-984(2015)
- Affiliations：
  
  1.BISITE Group, Faculty of Science, University of Salamanca, C/Espejo s/n, Salamanca 37008, Spain
  2.School of Mechanical Engineering, Northwestern Polytechnical University, Xi’an 710072, China
  3.Department of Artificial Intelligence, Technical University of Madrid, Calle Ramiro de Maeztu 7, Madrid 28040, Spain
  4.Osaka Institute of Technology, Asahi-ku Ohmiya, Osaka 535-8585, Japan
- Author bio：
  
  †E-mail:t.c.li@usal.est.c.li@mail.nwpu.edu.cn
- Funds：
- DOI：10.1631/FITEE.1500199
  CLC：
- Received：24 June 2015，
  
  Revised：2015-09-10，
  
  Accepted：01 September 2015，
  
  Published：2015-11
- Accepted：
Scan QR Code
Li Tian-cheng, Villarrubia Gabriel, Sun Shu-dong, et al. Resampling methods for particle filtering: identical distribution, a new method, and comparable study*[J]. Frontiers of Information Technology & Electronic Engineering, 2015, 16(11): 969-984.
DOI：

Li Tian-cheng, Villarrubia Gabriel, Sun Shu-dong, et al. Resampling methods for particle filtering: identical distribution, a new method, and comparable study*[J]. Frontiers of Information Technology & Electronic Engineering, 2015, 16(11): 969-984. DOI： 10.1631/FITEE.1500199.

摘要

目的

重采样方法是粒子滤波设计的重要环节，也是避免或克服“权值退化”和“多样性匮乏”这一对粒子滤波难点问题的关键。当前研究领域已有几十余种重采样方法，然而尚缺乏一个基础性的重采样设计原则以及对这些方法的综合性能对比。针对于此，本文提出重采样“同分布”设计原则，并在此基础上，提出一种能够最大程度满足同分布原则的最优重采样方法。本文希望所提出的重采样同分布原则以及新方法有利于进一步的新方法设计或已有方法的工程选用。

创新点

理论上严格定义了同分布原则作为重采样方法设计的普遍性原则，给出三种同分布测度方法；提出了一种最小采样方差（MSV: minimum sampling variance）最优重采样方法，在满足渐近无偏性的前提下获得最小采样方差。

方法

给出三种“重采样同分布”测度方法：Kullback-Leibler偏差

Kolmogorov-Smirnov统计和采样方差（sampling variance）。所提出的最小采样方差重采样放宽了无偏性条件，仅满足渐近无偏，但获得了最小采样方差（参见定理2-4论证以及仿真性能对比）。

结论

重采样前后粒子的概率分布应该统计上一致（即“同分布”）是重采样方法设计的一个重要原则。明确这一基本原则有利于规范化重采样新方法的设计与工程选用。所提出的MSV重采样新方法渐近无偏，并具有最小采样方差的优异理论特性，即最优地满足同分布原则。算法性能分析表明：大多数无偏或者渐近无偏重采样方法在滤波精度上差异较小，但是在采样方差、计算效率方面差异较大。另一方面，基于一些特殊规则或者问题模型设计的重采样方法可能具有特别优势。

Abstract

Resampling is a critical procedure that is of both theoretical and practical significance for efficient implementation of the particle filter. To gain an insight of the resampling process and the filter

this paper contributes in three further respects as a sequel to the tutorial (Li et al.

2015

). First

identical distribution (ID) is established as a general principle for the resampling design

which requires the distribution of particles before and after resampling to be statistically identical. Three consistent metrics including the (symmetrical) Kullback-Leibler divergence

Kolmogorov-Smirnov statistic

and the sampling variance are introduced for assessment of the ID attribute of resampling

and a corresponding

qualitative ID analysis of representative resampling methods is given. Second

a novel resampling scheme that obtains the optimal ID attribute in the sense of minimum sampling variance is proposed. Third

more than a dozen typical resampling methods are compared via simulations in terms of sample size variation

sampling variance

computing speed

and estimation accuracy. These form a more comprehensive understanding of the algorithm

providing solid guidelines for either selection of existing resampling methods or new implementations.

关键词

Keywords

references

W Adiprawita , AS Ahmad , J Sembiring , 等 . New resampling algorithm for particle filter localization for mobile robot with 3 ultrasonic sonar sensor . 2011 . Proc. Int. Conf. on Electrical Engineering and Informatics . 1 - 6 . DOI: 10.1109/ICEEI.2011.6021733 http://doi.org/10.1109/ICEEI.2011.6021733 .

MS Arulampalam , S Maskell , N Gordon , 等 . A tutorial on particle filters for online nonlinear/non-Gaussian Bayesian tracking . IEEE Trans Signal Process , 2002 . 50 ( 2 ): 174 - 188 . DOI: 10.1109/78.978374 http://doi.org/10.1109/78.978374 .

AS Bashi , VP Jilkov , XR Li , 等 . Distributed implementations of particle filters . 2003 . Proc. 6th Int. Conf. on Information Fusion . 1164 - 1171 . DOI: 10.1109/ICIF.2003.177369 http://doi.org/10.1109/ICIF.2003.177369 .

A Beskos , D Crisan , A Jasra . On the stability of sequential Monte Carlo methods in high dimensions . Ann Appl Probab , 2014 . 24 ( 4 ): 1396 - 1445 . DOI: 10.1214/13-AAP951 http://doi.org/10.1214/13-AAP951 .

M Bolić , PM Djurić , S Hong . New resampling algorithms for particle filters . 2003 . Proc. IEEE Int. Conf. on Acoustics, Speech and Signal Processing . 589 - 592 . DOI: 10.1109/ICASSP.2003.1202435 http://doi.org/10.1109/ICASSP.2003.1202435 .

O Cappé , SJ Godsill , E Moulines . An overview of existing methods and recent advances in sequential Monte Carlo . 2007 . Proc. IEEE . ( 5 ): 899 - 924 . DOI: 10.1109/JPROC.2007.893250 http://doi.org/10.1109/JPROC.2007.893250 .

Y Chen , J Xie , JS Liu . Stopping-time resampling for sequential Monte Carlo methods . J R Stat Soc B , 2005 . 67 ( 2 ): 199 - 217 . DOI: 10.1111/j.1467-9868.2005.00497.x http://doi.org/10.1111/j.1467-9868.2005.00497.x .

GM Choe , T Wang , F Liu , 等 . An advanced integrated framework for moving object tracking . J Zhejiang Univ-Sci C (Comput & Electron) , 2014 . 15 ( 10 ): 861 - 877 . DOI: 10.1631/jzus.C1400006 http://doi.org/10.1631/jzus.C1400006 .

GM Choe , T Wang , F Liu , 等 . Particle filter with spline resampling and global transition model . IET Comput Vis , 2015 . 9 ( 2 ): 184 - 197 . DOI: 10.1049/iet-cvi.2014.0106 http://doi.org/10.1049/iet-cvi.2014.0106 .

D Crisan , A Doucet . A survey of convergence results on particle filtering methods for practitioners . IEEE Trans Signal Process , 2002 . 50 ( 3 ): 736 - 746 . DOI: 10.1109/78.984773 http://doi.org/10.1109/78.984773 .

D Crisan , T Lyons . A particle approximation of the solution of the Kushner-Stratonovitch equation . Probab Theory Related Fields , 1999 . 115 ( 4 ): 549 - 578 . DOI: 10.1007/s004400050249 http://doi.org/10.1007/s004400050249 .

D Crisan , P Del Moral , T Lyons . Discrete Filtering Using Branching and Interacting Particle Systems. Markov Process . Related Fields , 1998 . 5 ( 3 ): 293 - 318 . .

SK Das , C Mazumdar . Priori-sensitive resampling particle filter for dynamic state estimation of UUVs . 2013 . Proc. 8th Int. Workshop on Systems, Signal Processing and Their Applications . 384 - 389 . DOI: 10.1109/WoSSPA.2013.6602396 http://doi.org/10.1109/WoSSPA.2013.6602396 .

P Del Moral , P Hu , L Wu . On the concentration properties of interacting particle processes . Found Trends Mach Learn , 2012 . 3 ( 3-4 ): 225 - 389 . DOI: 10.1561/2200000026 http://doi.org/10.1561/2200000026 .

PM Djurić , J Miguez . Assessment of nonlinear dynamic models by Kolmogorov-Smirnov statistics . IEEE Trans Signal Process , 2010 . 58 ( 10 ): 5069 - 5079 . DOI: 10.1109/TSP.2010.2053707 http://doi.org/10.1109/TSP.2010.2053707 .

PM Djurić , JH Kotecha , J Zhang , 等 . Particle filtering . IEEE Signal Process Mag , 2003 . 20 ( 5 ): 19 - 38 . DOI: 10.1109/MSP.2003.1236770 http://doi.org/10.1109/MSP.2003.1236770 .

R Douc , O Cappé . Comparison of resampling schemes for particle filtering . 2005 . Proc. 4th Int. Symp. on Image and Signal Processing and Analysis . 64 - 69 . DOI: 10.1109/ISPA.2005.195385 http://doi.org/10.1109/ISPA.2005.195385 .

R Douc , E Moulines , J Olsson . Long-term stability of sequential Monte Carlo methods under verifiable conditions . Ann Appl Probab , 2014 . 24 ( 5 ): 1767 - 1802 . DOI: 10.1214/13-AAP962 http://doi.org/10.1214/13-AAP962 .

A Doucet , N de Freitas , N Gordon . Sequential Monte Carlo Methods in Practice , 2001 . Springer, New York, USA , DOI: 10.1007/978-1-4757-3437-9 http://doi.org/10.1007/978-1-4757-3437-9 .

B Efron , D Rogosa , R Tibshirani . Resampling methods of estimation . Wright, J.D , 2015 . (Ed.), International Encyclopedia of the Social & Behavioral Sciences (2nd Ed.). Elsevier, Oxford , 492 - 495 . DOI: 10.1016/B978-0-08-097086-8.42165-3 http://doi.org/10.1016/B978-0-08-097086-8.42165-3 .

P Fearnhead , P Clifford . On-line inference for hidden Markov models via particle filters . J R Stat Soc Ser B , 2003 . 65 ( 4 ): 887 - 899 . DOI: 10.1111/1467-9868.00421 http://doi.org/10.1111/1467-9868.00421 .

P Fearnhead , Z Liu . On-line inference for multiple changepoint problems . J R Stat Soc Ser B , 2007 . 69 ( 4 ): 589 - 605 . DOI: 10.1111/j.1467-9868.2007.00601.x http://doi.org/10.1111/j.1467-9868.2007.00601.x .

D Fox . Adapting the sample size in particle filters through KLD-sampling . Int J Robot Res , 2003 . 22 ( 12 ): 985 - 1003 . DOI: 10.1177/0278364903022012001 http://doi.org/10.1177/0278364903022012001 .

S Godsill , J Vermaak , W Ng , 等 . Models and algorithms for tracking of maneuvering objects using variable rate particle filters . 2007 . Proc. IEEE . ( 5 ): 925 - 952 . DOI: 10.1109/JPROC.2007.894708 http://doi.org/10.1109/JPROC.2007.894708 .

N Gordon , D Salmond , AFM Smith . Novel approach to nonlinear/non-Gaussian Bayesian state estimation . 1993 . IEE Proc. F . ( 2 ): 107 - 113 . DOI: 10.1049/ip-f-2.1993.0015 http://doi.org/10.1049/ip-f-2.1993.0015 .

F Gustafsson . Particle filter theory and practice with positioning applications . IEEE Aeros Electron Syst Mag , 2010 . 25 ( 7 ): 53 - 82 . DOI: 10.1109/MAES.2010.5546308 http://doi.org/10.1109/MAES.2010.5546308 .

JD Hol , TB Schon , F Gustafsson . On resampling algorithms for particle filters . 2006 . Proc. IEEE Nonlinear Statistical Signal Processing Workshop . 79 - 82 . DOI: 10.1109/NSSPW.2006.4378824 http://doi.org/10.1109/NSSPW.2006.4378824 .

S Hong , Z Shi , J Chen , 等 . A low-power memory-efficient resampling architecture for particle filters . Circ Syst Signal Process , 2010 . 29 ( 1 ): 155 - 167 . DOI: 10.1007/s00034-009-9117-4 http://doi.org/10.1007/s00034-009-9117-4 .

XL Hu , TB Schon , L Ljung . A general convergence result for particle filtering . IEEE Trans Signal Process , 2011 . 59 ( 7 ): 3424 - 3429 . DOI: 10.1109/TSP.2011.2135349 http://doi.org/10.1109/TSP.2011.2135349 .

RE Kalman . A new approach to linear filtering and prediction problems . J Basic Eng , 1960 . 82 ( 1 ): 35 - 45 . DOI: 10.1115/1.3662552 http://doi.org/10.1115/1.3662552 .

G Kitagawa . Monte Carlo filter and smoother and non-Gaussian nonlinear state space models . J Comput Graph Stat , 1996 . 5 ( 1 ): 1 - 25 . DOI: 10.1080/10618600.1996.10474692 http://doi.org/10.1080/10618600.1996.10474692 .

A Kong , JS Liu , WH Wong . Sequential imputations and Bayesian missing data problems . J Am Stat Assoc , 1994 . 89 ( 425 ): 278 - 288 . DOI: 10.1080/01621459.1994.10476469 http://doi.org/10.1080/01621459.1994.10476469 .

S Kullback , RA Leibler . On information and sufficiency . Ann Math Stat , 1951 . 22 ( 1 ): 79 - 86 . DOI: 10.1214/aoms/1177729694 http://doi.org/10.1214/aoms/1177729694 .

N Kwak , GW Kim , BH Lee . A new compensation technique based on analysis of resampling process in FastSLAM . Robotica , 2008 . 26 ( 2 ): 205 - 217 . DOI: 10.1017/S0263574707003773 http://doi.org/10.1017/S0263574707003773 .

H Lang , T Li , G Villarrubia , 等 . An adaptive particle filter for indoor robot localization . 2015 . Proc. 6th Int. Symp. on Ambient Intelligence . 45 - 55 . DOI: 10.1007/978-3-319-19695-4_5 http://doi.org/10.1007/978-3-319-19695-4_5 .

HW Lenstra . Integer programming with a fixed number of variables . Math Oper Res , 1983 . 8 ( 4 ): 538 - 548 . DOI: 10.1287/moor.8.4.538 http://doi.org/10.1287/moor.8.4.538 .

T Li , S Sun . Double-resampling based Monte Carlo localization for mobile robot . Acta Autom Sin , 2010 . 36 ( 9 ): 1279 - 1286 . DOI: 10.3724/SP.J.1004.2010.01279 http://doi.org/10.3724/SP.J.1004.2010.01279 .

T Li , TP Sattar , S Sun . Deterministic resampling: unbiased sampling to avoid sample impoverishment in particle filters . Signal Process , 2012 . 92 ( 7 ): 1637 - 1645 . DOI: 10.1016/j.sigpro.2011.12.019 http://doi.org/10.1016/j.sigpro.2011.12.019 .

T Li , TP Sattar , D Tang . A fast resampling scheme for particle filters . 2013 . Proc. Constantinides Int. Workshop on Signal Processing . 1 - 4 . DOI: 10.1049/ic.2013.0002 http://doi.org/10.1049/ic.2013.0002 .

T Li , S Sun , TP Sattar . Adapting sample size in particle filters through KLD-resampling . Electron Lett , 2013 . 46 ( 2 ): 740 - 742 . DOI: 10.1049/el.2013.0233 http://doi.org/10.1049/el.2013.0233 .

T Li , S Sun , TP Sattar , 等 . Fight sample degeneracy and impoverishment in particle filters: a review of intelligent approaches . Expert Syst Appl , 2014 . 41 ( 8 ): 3944 - 3954 . DOI: 10.1016/j.eswa.2013.12.031 http://doi.org/10.1016/j.eswa.2013.12.031 .

T Li , M Bolic , PM Djurić . Resampling methods for particle filtering: classification, implementation, and strategies . IEEE Signal Process Mag , 2015 . 32 ( 3 ): 70 - 86 . DOI: 10.1109/MSP.2014.2330626 http://doi.org/10.1109/MSP.2014.2330626 .

T Li , S Sun , M Bolic , 等 . Algorithm design for parallel implementation of the SMC-PHD filter . Signal Process , 2016 . 119 115 - 127 . DOI: 10.1016/j.sigpro.2015.07.013 http://doi.org/10.1016/j.sigpro.2015.07.013 .

JS Liu , R Chen . Sequential Monte Carlo methods for dynamic systems . J Am Stat Assoc , 1998 . 93 ( 443 ): 1032 - 1044 . DOI: 10.1080/01621459.1998.10473765 http://doi.org/10.1080/01621459.1998.10473765 .

JS Liu , R Chen , T Logvinenko . A Doucet , N de Freitas , N Gordon . A theoretical framework for sequential importance sampling and resampling . Sequential Monte Carlo Methods in Practice , 2001 . Springer, USA , 225 - 246 . DOI: 10.1007/978-1-4757-3437-9_11 http://doi.org/10.1007/978-1-4757-3437-9_11 .

IS Mbalawata , S Särkkä . Moment conditions for convergence of particle filters with unbounded importance weights . Signal Process , 2016 . 118 133 - 138 . DOI: 10.1016/j.sigpro.2015.06.018 http://doi.org/10.1016/j.sigpro.2015.06.018 .

J Míguez , MF Bugallo , PM Djurić . A new class of particle filters for random dynamical systems with unknown statistics . EURASIP J Adv Signal Process , 2004 . 15 2278 - 2294 . DOI: 10.1155/S1110865704406039 http://doi.org/10.1155/S1110865704406039 .

MR Morelande , AM Zhang . A mode preserving particle filter . 2011 . Proc. IEEE Int. Conf. on Acoustics, Speech and Signal Processing . 3984 - 3987 . DOI: 10.1109/ICASSP.2011.5947225 http://doi.org/10.1109/ICASSP.2011.5947225 .

L Murray . GPU acceleration of the particle filter: the Metropolis resampler . 2012 . arXiv:1202.6163v1 . .

F Nielsen . A family of statistical symmetric divergences based on Jensen’s inequality . 2010 . arXiv:1009.4004 . .

CJ Pérez , J Martín , MJ Rufo , 等 . Quasi-random sampling importance resampling . Commun Stat Simul Comput , 2005 . 34 ( 1 ): 97 - 112 . DOI: 10.1081/SAC-200047112 http://doi.org/10.1081/SAC-200047112 .

CP Robert , G Casella . Monte Carlo Statistical Methods , 1999 . Springer, New York , DOI: 10.1007/978-1-4757-4145-2 http://doi.org/10.1007/978-1-4757-4145-2 .

DB Rubin . The calculation of posterior distribution by data augmentation: Comment: a noniterative sampling/ importance resampling alternative to the data augmentation algorithm for creating a few imputations when fractions of missing information are modest: the SIR algorithm . J Am Stat Assoc , 1987 . 82 ( 398 ): 543 - 546 . DOI: 10.2307/2289460 http://doi.org/10.2307/2289460 .

BG Sileshi , C Ferrer , J Oliver . Particle filters and resampling techniques: importance in computational complexity analysis . 2013 . Proc. Conf. on Design and Architectures for Signal and Image Processing . 319 - 325 . .

A Simonetto , T Keviczky . Recent developments in distributed particle filtering: towards fast and accurate algorithms . 2009 . Proc. 1st IFAC Workshop on Estimation and Control of Networked Systems . 138 - 143 . DOI: 10.3182/20090924-3-IT-4005.00024 http://doi.org/10.3182/20090924-3-IT-4005.00024 .

PM Stano , Z Lendek , R Babuška . Saturated particle filter: almost sure convergence and improved resampling . Automatica , 2013 . 49 ( 1 ): 147 - 159 . DOI: 10.1016/j.automatica.2012.10.006 http://doi.org/10.1016/j.automatica.2012.10.006 .

S Sutharsan , T Kirubarajan , T Lang , 等 . An optimization-based parallel particle filter for multitarget tracking . IEEE Trans Aeros Electron Syst , 2012 . 48 ( 2 ): 1601 - 1618 . DOI: 10.1109/TAES.2012.6178081 http://doi.org/10.1109/TAES.2012.6178081 .

F Topsoe . Some inequalities for information divergence and related measures of discrimination . IEEE Trans Inform Theory , 2000 . 46 ( 4 ): 1602 - 1609 . DOI: 10.1109/18.850703 http://doi.org/10.1109/18.850703 .

Y Wang , PM Djurić . Sequential estimation of linear models in distributed settings . 2013 . Proc. 21st European Signal Processing Conf . 1 - 5 . .

N Whiteley . Stability properties of some particle filters . Ann Appl Probab , 2013 . 23 ( 6 ): 2500 - 2537 . DOI: 10.1214/12-AAP909 http://doi.org/10.1214/12-AAP909 .

R Zhi , T Li , MF Siyau , 等 . Applied technology in adapting the number of particles while maintaining the diversity in the particle filter . Adv Mater Res , 2014 . 951 202 - 207 . DOI: 10.4028/www.scientific.net/AMR.951.202 http://doi.org/10.4028/www.scientific.net/AMR.951.202 .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

Visual-feature-assisted mobile robot localization in a long corridor environment

Related Author

Gengyu GE

Yi ZHANG

Wei WANG

Lihe HU

Yang WANG

Qin JIANG

Related Institution

School of Computer Science and Technology, Chongqing University of Posts and Telecommunications

School of Advanced Manufacturing Engineering, Chongqing University of Posts and Telecommunications

School of Information Engineering, Zunyi Normal University

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰