Abstract
Particle filters are essential for non-linear tracking but suffer from high variance due to random sampling. This paper introduces Lattice Particle Filters (LPF), which utilize deterministic Quasi-Monte Carlo lattice rules to place particles more effectively. Results demonstrate that LPFs achieve comparable accuracy to standard filters while requiring significantly fewer particles, particularly in high-dimensional state spaces.
Introduction
Particle Filters (PFs) are a staple in robotics and computer vision for tracking objects in complex state spaces. Despite their versatility in handling non-linear dynamics and non-Gaussian noise, standard PFs rely on stochastic Monte Carlo sampling. This inherent randomness often leads to high estimation variance, requiring a large number of particles to ensure stability and accuracy, which increases computational overhead. This paper proposes the Lattice Particle Filter (LPF), a method that replaces random sampling with deterministic particle placement to improve efficiency and reliability.
Methodology: From Randomness to Lattices
The core innovation of the LPF is the transition from standard Monte Carlo (MC) integration to Quasi-Monte Carlo (QMC) methods. Instead of scattering particles randomly, the LPF utilizes a shifted Korobov lattice rule to distribute particles more uniformly across the state space.
To maintain the statistical properties of a Bayesian filter, such as being an unbiased estimator, the authors employ Randomized QMC. This involves applying a random shift and permutation to the lattice at each time step. Theoretically, while standard MC methods converge at a rate of $O(N^{-1/2})$, QMC methods can achieve a significantly faster rate of $O(N^{-1} \log^s N)$, where $s$ is the dimensionality of the state space.
Experimental Evaluation
The LPF was tested against standard "Bootstrap" particle filters in two distinct scenarios:
- 2D Disk Tracking: A synthetic task involving a disk moving in a noisy environment, allowing for controlled testing across 1,000 simulated sequences.
- 10D Human Motion Tracking: A high-dimensional problem recovering 3D lower-body poses (hips, knees, ankles) from 2D marker projections.
Key Results and Efficiency Gains
The experiments revealed that the LPF consistently outperforms standard PFs, particularly when particle counts are low relative to the state space dimensionality.
- Reduced Variance: In the 10D tracking task, the LPF showed a 5% to 20% reduction in variance, leading to more stable tracking.
- Computational Efficiency: In the disk tracking task, the LPF achieved approximately 20% lower error than a standard PF with the same number of particles.
- Particle Savings: Most notably, a standard PF required 50% to 60% more particles to match the accuracy of an LPF.
Conclusion
Lattice Particle Filters offer a robust alternative to traditional stochastic filtering. By leveraging deterministic lattice structures, they provide a significant reduction in estimation variance and computational requirements. While the relative advantage of LPFs diminishes as the number of particles becomes extremely large, they remain highly effective for high-dimensional tracking problems where computational resources are constrained.
Summary updated