Particle filter

A particle filter is a recursive Bayesian estimation method that approximates the probability distribution of a changing state, such as the position and orientation of a camera, head or hand, with a set of random samples ("particles") and associated weights. In their 2002 tutorial in IEEE Transactions on Signal Processing, M. Sanjeev Arulampalam, Simon Maskell, Neil Gordon and Tim Clapp describe particle filters as sequential Monte Carlo methods based on point mass representations of probability densities that "can be applied to any state-space model" and that generalize traditional Kalman filtering. The same family of algorithms has been published under several names, including bootstrap filtering, the condensation algorithm, interacting particle approximations and "survival of the fittest".

Arnaud Doucet and Adam M. Johansen date the introduction of particle filtering to 1993, when N. J. Gordon, D. J. Salmond and A. F. M. Smith published the bootstrap filter. Unlike the Kalman filter, a particle filter does not assume linear dynamics or Gaussian noise, and it can represent a distribution with several peaks, for example several competing hypotheses about where a contour lies in a cluttered image. The price is computation: Doucet and Johansen describe the methods as computationally expensive, and by 2008 they described particle methods as routinely used in fields including computer vision, robotics and navigation. Research on augmented reality (AR) and virtual reality (VR) systems has applied them to head motion prediction, camera pose tracking, hand tracking and multi-user localization.

Reviewed 19 October 2026. Claims checked against the full texts of Gordon et al. (1993), Arulampalam et al. (2002), Doucet and Johansen (2008), Isard and Blake (1998), Dellaert et al. (1999), Montemerlo et al. (2002), Elfring et al. (2021), Ababsa et al. (2003), Pupilli and Calway (2005), Klein and Murray (2006) and Miller et al. (2021), and the abstracts of Bray et al. (2004), Ababsa and Mallem (2011), Lee (2014) and Bicho et al. (2019); bibliographic data for all cited papers, including Kitagawa (1996), Isard and Blake (1996) and Liu and Chen (1998), confirmed via Crossref, OpenAlex and HAL. About review dates.

How it works

A particle filter works on a state-space model with two parts: a system model that describes how the hidden state changes from one time step to the next, and a measurement model that relates noisy observations to the state. From a Bayesian point of view, the tracking problem is to compute, at each time step, the posterior probability density of the state given all measurements received so far. This is done recursively in two stages. The prediction stage uses the system model to move the density forward in time, and the update stage applies Bayes' theorem to the newest measurement. Only in restricted cases, such as linear models with Gaussian noise, does this recursion have an exact closed-form solution.

The particle filter approximates the posterior density with a finite set of samples and normalized weights. Arulampalam and colleagues state the key idea as representing the posterior "by a set of random samples with associated weights" and computing estimates from them; as the number of samples becomes very large, the representation approaches the true posterior. Gordon, Salmond and Smith noted that moments such as the mean and covariance can be read directly from the samples, and that the samples concentrate naturally in regions of high probability, so no grid over the state space has to be defined.

A basic filtering cycle has three steps:

• Predict. Each particle is propagated through the system model, with random process noise, to give a sample of the predicted state.
• Weight. Each particle's weight is updated in proportion to how well it explains the new measurement, using the likelihood from the measurement model, and the weights are normalized.
• Resample. Particles are drawn again, with replacement, in proportion to their weights, so that unlikely particles are discarded and likely ones are duplicated.

Degeneracy and resampling

The general algorithm without resampling, sequential importance sampling (SIS), suffers from what Arulampalam and colleagues call the degeneracy phenomenon: after a few iterations, all but one particle have negligible weight. Because the variance of the importance weights can only increase over time, degeneracy cannot be avoided, and much of the computation is wasted on particles that contribute almost nothing. The effective sample size, estimated from the normalized weights, is a common measure of how severe the degeneracy is. The tutorial names two remedies besides simply using more particles: a good choice of importance density (the distribution from which new particles are drawn) and resampling. The authors write that the choice of importance density is "the crucial design step" of a particle filter.

Resampling can be done at every step or only when the effective sample size falls below a threshold. Arulampalam and colleagues preferred systematic resampling, which they credit to Genshiro Kitagawa, because it is simple to implement and minimizes Monte Carlo variation; they name stratified and residual sampling as alternatives. In a 2021 tutorial, Jos Elfring, Elena Torta and René van de Molengraft wrote that most particle filters use one of four algorithms (multinomial, residual, systematic or stratified resampling) and concluded that "there is no best resampling algorithm", since published comparisons disagree.

Resampling has its own costs. All particles must be combined, which limits parallelization, and repeatedly selecting high-weight particles reduces the diversity of the particle set. This loss of diversity, called sample impoverishment, is severe when process noise is small; with very small process noise all particles can collapse to a single point within a few iterations. Proposed countermeasures include the resample-move algorithm, which adds a Markov chain Monte Carlo step, and the regularized particle filter, which resamples from a continuous approximation of the posterior rather than from the discrete particle set. Gordon, Salmond and Smith had already used a roughening procedure that jitters the resampled values, and Elfring and colleagues describe roughening methods that add artificial noise after resampling or jitter to the process model.

Number of particles

More particles generally give a better approximation at a higher computational cost; in one AR study, the estimation error fell as the number of particles increased, while the computational burden depends on the particle count. Elfring and colleagues note that populating a state space of dimension n requires the number of particles to grow exponentially with n, and that real-time use limits the number of particles that can be afforded. They list Rao-Blackwellized particle filters, which handle part of the state analytically, and adaptive filters that change the particle count during operation as ways to reduce the burden. In that head-tracking study, Fakhr-eddine Ababsa and colleagues chose 100 particles after several experiments, so that computation stayed suitable for their real-time application.

Common variants

Variant	Main idea	Source
Sequential importance sampling (SIS)	General framework: particles are drawn from an importance density and their weights updated recursively; suffers from weight degeneracy
Sampling importance resampling (SIR) / bootstrap filter	Uses the state transition prior as the importance density and resamples at every time step; simple, but explores the state space without using the newest measurement, so it can be inefficient and sensitive to outliers
Auxiliary sampling importance resampling (ASIR)	Introduced by Pitt and Shephard; can be viewed as resampling at the previous time step based on point estimates, so that new particles are more likely to lie close to the true state given the current measurement
Regularized particle filter (RPF)	Resamples from a continuous kernel approximation of the posterior to reduce sample impoverishment
Rao-Blackwellized particle filter	Samples only part of the state and estimates the rest analytically, for example with one Kalman filter per landmark in FastSLAM
CONDENSATION	Particle-based propagation of conditional density with learned dynamical models, for tracking curves in cluttered video

Comparison with Kalman filters

For a linear system with Gaussian noise, the Kalman filter computes the exact posterior. Arulampalam and colleagues conclude that when the assumptions of the Kalman filter or of grid-based filters hold, "no other algorithm can outperform them". Most real tracking problems break those assumptions. The extended Kalman filter (EKF) linearizes the models and still approximates the density by a single Gaussian, which Gordon, Salmond and Smith described as possibly "a gross distortion of the true underlying structure" that may lead to filter divergence. Grid-based approximations become prohibitively expensive in high-dimensional state spaces.

A further practical difference is the ability to represent several hypotheses at once. Michael Isard and Andrew Blake wrote that Kalman filtering is inadequate for tracking curves in dense visual clutter because Gaussian densities, being unimodal, "cannot represent simultaneous alternative hypotheses". In robot localization, Frank Dellaert, Dieter Fox, Wolfram Burgard and Sebastian Thrun noted that a Kalman filter cannot represent ambiguities and cannot globally relocalize a robot that has lost track of its position. The two approaches are often combined rather than treated as rivals: the Rao-Blackwellized FastSLAM algorithm, for example, runs a separate Kalman filter for every landmark inside each particle.

History

Gordon, Salmond and Smith, working at the Defence Research Agency in Farnborough and Imperial College London, proposed the bootstrap filter in IEE Proceedings F in April 1993. The required density of the state vector is represented by random samples that the algorithm updates and propagates, and the method is "not restricted by assumptions of linearity or Gaussian noise". The authors named it after its key update step, in which Bayes' rule is applied as a weighted bootstrap. In their simulation of a bearings-only tracking problem, the authors reported that the performance of the bootstrap filter was "greatly superior to the standard extended Kalman filter".

Related sampling methods were published in statistics and computer vision over the following years. Genshiro Kitagawa published a Monte Carlo filter and smoother for non-Gaussian nonlinear state space models in the Journal of Computational and Graphical Statistics in 1996. In computer vision, Isard and Blake of the University of Oxford presented contour tracking by stochastic propagation of conditional density at ECCV 1996 and published the full CONDENSATION (conditional density propagation) algorithm in the International Journal of Computer Vision in 1998. They noted that the same sampling strategy had been developed elsewhere by Gordon and colleagues and by Kitagawa. Jun S. Liu and Rong Chen used the name "sequential Monte Carlo" in the title of a 1998 paper in the Journal of the American Statistical Association.

In robotics, Dellaert, Fox, Burgard and Thrun introduced Monte Carlo localization at ICRA 1999. It represents the robot's position estimate with randomly drawn samples, and the authors showed that it could localize a mobile robot without knowledge of its starting location and was faster, more accurate and less memory-intensive than earlier grid-based methods. At AAAI 2002, Michael Montemerlo, Sebastian Thrun, Daphne Koller and Ben Wegbreit presented FastSLAM, which uses a modified particle filter to estimate the posterior over robot paths, with each particle carrying Kalman filters for the landmark positions. EKF-based SLAM required time quadratic in the number of landmarks for each observation, while FastSLAM's tree-based implementation scaled logarithmically, and in simulation the authors ran it with as many as 50,000 landmarks.

In their 2008 survey, Doucet and Johansen described the February 2002 tutorial by Arulampalam, Maskell, Gordon and Clapp as the most popular of the earlier tutorials on the subject.

Year	Work	Contribution
1993	Gordon, Salmond and Smith, IEE Proceedings F	Bootstrap filter; sample-based recursive Bayesian filter compared with the EKF on bearings-only tracking
1996	Kitagawa, Journal of Computational and Graphical Statistics	Monte Carlo filter and smoother for non-Gaussian nonlinear state space models
1996	Isard and Blake, ECCV '96	Contour tracking by stochastic propagation of conditional density
1998	Isard and Blake, International Journal of Computer Vision	CONDENSATION algorithm for tracking curves in visual clutter
1998	Liu and Chen, Journal of the American Statistical Association	Sequential Monte Carlo methods for dynamic systems
1999	Dellaert, Fox, Burgard and Thrun, ICRA	Monte Carlo localization for mobile robots
2002	Arulampalam, Maskell, Gordon and Clapp, IEEE Transactions on Signal Processing	Tutorial unifying SIS, SIR, ASIR and regularized particle filters
2002	Montemerlo, Thrun, Koller and Wegbreit, AAAI	FastSLAM, a Rao-Blackwellized particle filter for SLAM

Applications in VR and AR

Tracking in VR and AR means estimating the pose of a head-mounted display, camera or hand from noisy sensor data, and AR registration must also compensate for system latency. The applications below are documented in research papers; they do not show which filters commercial headsets use.

Head motion prediction

In a paper at the ICAT 2003 conference in Tokyo, Fakhr-eddine Ababsa, Jean Yves Didier, Malik Mallem and David Roussel addressed the lag between a user's head movement and the display of virtual objects in an AR head-mounted display. They noted that the EKF was the filter most used to predict head motion, and proposed a sampling importance resampling particle filter instead, fusing inertial and vision sensor data to estimate and predict head pose. In simulation with synthetic data, the particle filter produced lower root mean square error than an EKF implemented under the same conditions, in the reported camera position and orientation results along the x axis. Prediction of this kind is the subject of predictive tracking.

Camera pose tracking for AR

Several research systems used particle filters to estimate the pose of a camera for AR registration. Mark Pupilli and Andrew Calway of the University of Bristol presented a particle filter for real-time tracking of a hand-held calibrated camera at BMVC 2005. They contrasted their approach with A. J. Davison's Kalman filter based single-camera SLAM system, arguing that a particle filter could cope better with non-linearities and non-Gaussian statistics. Their measurements were inlier and outlier counts of likely feature correspondences, and in their tests the filter recovered from loss of track and from severe occlusion. With 500 particles on a 3 GHz workstation, it processed 40 frames per second with four active scene points and 25 with eight, and tracking accuracy was assessed by placing augmented graphics on a kitchen table.

Georg Klein and David Murray of the University of Oxford described a full-3D edge tracker based on a particle filter at BMVC 2006, listing augmented reality among the applications of model-based camera tracking. Their system used graphics hardware to perform hidden line removal for each particle and to evaluate pose likelihoods directly on the graphics card, which allowed video-rate filtering with hundreds of particles on a standard workstation. Ababsa and Mallem published a particle filtering framework for camera pose estimation from point and line features in Machine Vision and Applications, aimed at real-time AR applications in which the camera is held by the user. They reported that it was more robust than Kalman filter based approaches and analyzed its sensitivity to outliers from incorrect feature matches. In a 2014 paper in the Journal of Electronic Imaging, Seok-Han Lee connected a particle filter based camera tracker to independent feature tracking filters, named AR among the motivating applications, and demonstrated the system in real time in a desktop environment.

Hand and head tracking

The 1998 CONDENSATION paper included a 10-second test sequence of a hand translating, rotating and flexing its fingers over a highly cluttered desk. Fully articulated 3D hand tracking has many more degrees of freedom, which makes plain particle filtering expensive. Matthieu Bray, Esther Koller-Meier and Luc Van Gool of ETH Zurich combined a particle filter with Stochastic Meta-Descent optimization in a "smart particle filter", reported at the 2004 IEEE International Conference on Automatic Face and Gesture Recognition. On 3D hand tracking sequences it needed far fewer samples than earlier methods and outperformed both Stochastic Meta-Descent alone and an annealed particle filter.

For head tracking without markers, Dylan Bicho and colleagues at the University of Coimbra presented a multi-camera system for several VR, AR and mixed reality users at the 2019 IEEE International Conference on Systems, Man and Cybernetics. It voxelizes dense point cloud data, and the head position of each detected user is tracked with a dedicated particle filter. Against annotated ground truth, the authors reported a mean 3D positioning error below 18 mm and a running time below 20 ms for four users.

Multi-user localization

Shared AR sessions need the devices to agree on each other's positions. In a 2021 preprint, John Miller and colleagues at Carnegie Mellon University described LocAR, which combines visual-inertial odometry from Apple's ARKit with ultra-wideband ranging between users. A collaborative 6DoF particle filter, using Rao-Blackwellized factorization to keep the number of particles tractable as users are added, estimates every device's pose relative to the others. The authors reported a median 3D error of less than 1 meter between five users walking freely across three floors of a 30,000 square foot area.

Localization and mapping

Monte Carlo localization and FastSLAM applied particle filters to mobile robot localization and to simultaneous localization and mapping (SLAM). Pupilli and Calway's AR camera tracker also added new scene points while tracking, estimating their depths in an auxiliary process outside the main particle filter, rather than relying only on a pre-built map.

See also

• Kalman filter
• Complementary filter
• Sensor fusion
• SLAM
• Loop closure
• Drift (tracking)
• Tracking
• Positional tracking
• Predictive tracking
• Hand tracking
• Computer vision