High-Performance Algorithm and Parallel Implementation Technique of Particle Filter
Date Issued
2012
Date
2012
Author(s)
Chu, Chun-Yuan
Abstract
Because of the robustness of the Particle Filter (PF) in nonlinear/non-Gaussian applications, the PF algorithm is now very widespread and has a significant impact in virtually all areas of signal and image processing concerned with Bayesian dynamical models. The PF uses samples (particles) and associated weights to represent the probability density function (PDF) of the state. The estimation of the state we are interested can be obtained with the PDF predicted by the PF.
Due to wide application of PF, it is important to make the PF algorithm feasible for practical systems. In other words, the PF algorithm should be efficient in hardware/software implementation. In this dissertation, a novel PF algorithm, multi-prediction PF (MP-PF), is proposed. The proposed MP-PF can significantly reduce the memory requirement without loss of estimation accuracy. Besides, the parallel implementation technique is a popular approach to reduce the execution time. Most operations of the PF algorithm are independent and can be executed in parallel. However, the sequential operations of PFs still limit the improvement from parallel implementation. In general, the complexity of the sequential task is proportional to the particle number. The proposed MP-PF can reduce the particle number, as well as the complexity of the sequential task. To verify the benefit of the proposed MP-PFs, we implement the proposed MP-PF on Nvidia multi-core GPUs, which has high efficiency to process many parallel local computations. For the classic BOT experiments, the maximum improvements of the proposed MP-PF are 25.1 times and 15.3 times faster than the SIR-PF with 10,000 and 20,000 particles respectively.
In addition to the development on the basic PF algorithm, this dissertation also applies the PF algorithm into the positioning system. [27] reduces the particle prediction uncertainty by using the map information, so the PF can use fewer particles. However, the strong constraints reduce the flexibility of propagation model which we need to compensate the unawareness of target''s true behavior of motion. Rather than using a simple/constrained particle transition model, this dissertation proposes a location estimation framework which integrates location constraints into particle filter, including invalid regions, walls, and turning regions for adjusting the motion model. In the proposed location-constrained PF (LC-PF), the combination of location-constrained weight updating and constrained propagation makes large accuracy improvement. Comparing with the basic PF, the LC-PF can give the error reduction around 68%.
Subjects
Particle filter
GPU
Indoor positioning system
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
index.html
Size
23.27 KB
Format
HTML
Checksum
(MD5):9f0ca215a631eb0f9047af671d8eac7f