粒子濾波器之高效能演算法與平行化實現技術

High-Performance Algorithm and Parallel Implementation Technique of Particle Filter

朱峻源(Chun-Yuan Chu)

指導教授 ： 吳安宇

國立臺灣大學/電機資訊學院/電子工程學研究所/博士(2012年)

https://doi.org/10.6342/NTU.2012.02538

摘要

由於粒子濾波器在非線性/非高斯雜訊應用下的強健性，粒子濾波器演算法被廣泛應用在很多信號處理或影像處理領域中。粒子濾波器利用很多樣本（粒子）以及相對應的權重來表示待測狀態的機率分佈函數，由粒子濾波器得到此機率分佈函數後，便可對待測狀態進行估測。
由於粒子濾波器的廣泛應用，如何粒子濾波器有效地用軟/硬體來實現，是一個很重要的研究議題。本論文提出一新穎的粒子濾波器演算法–多預測粒子濾波器演算法。多預測粒子濾波器可以在不損失估測準確度的情況下，大量降低記憶體需求，提高粒子濾波器的可實現性。此外，對於加快執行時間，很常使用平行化實現的技巧，對粒子濾波器來說，大部分的運算都可以獨立平行執行，然而由於粒子濾波器中需要針對全域資料進行序列運算的部分，會使平行執行的效能降低，而這序列運算的複雜度和粒子數成正比，因此本論文提出的多預測粒子濾波器，不但可以降低所需的記憶體，還可以減少序列運算的複雜度。本論文把提出之多預測粒子濾波器實現在NVIDIA的多核心圖形處理器上，來驗證多預測粒子濾波器的好處。在我們的實驗中，多預測粒子濾波器和傳統粒子利波器演算法比較，可以達到十五到二十五倍的執行時間加快。
除了演算法上的改善，本論文亦將粒子濾波器應用在定位系統中。[27]利用地圖資訊來降低粒子預測時的不確定性，因此可降低粒子數，然而這樣的做法，也會限制粒子預測模型的彈性，不易追蹤目標的真實運動模式。而本論文整合地圖上各位置的限制到粒子濾波器中，例如：不可進入區域、牆、轉角等，來調整粒子的預測模型。本論文提出的位置限制粒子濾波器，和傳統粒子濾波器相比，可達到百分之六十八的錯誤降低。

關鍵字

粒子濾波器 ； 圖形處理器 ； 室內定位系統

並列摘要

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%.

並列關鍵字

Particle filter ； GPU ； Indoor positioning system

參考文獻

[1] R. E. Kalman, “A new approach to linear filtering and prediction problems,” J. Basic Eng., vol. 82, pp. 35–45, 1960.

[4] G. Welch, G. Bishop, An Introduction to the Kalman Filter,

[6] J. Handschin and D. Mayne, “Monte Carlo techniques to estimate the conditional expectation in multi-stage non-linear filtering,” Int. J. Control, vol. 9, pp. 547-559, 1969.

[7] N. J. Gordon, D. J. Salmond, and A. F. M. Smith, “Novel approach to nonlinear/non- Gaussian Bayesian state estimation,” IEE Proc. F: Radar Signal Process., vol. 140, no. 2, pp. 107–113, Apr. 1993.

[9] O. Capp’e, S. J. Godsill, and E. Moulines, “An overview of existing methods and recent advances in sequential Monte Carlo,” Proc. IEEE, vol. 95, no. 5, pp. 899–924, May 2007.