始於「Monte Carlo 蒙地卡羅法」
基於「Bayesian recursion」
「Particle Filter」的主要思想
「SIS Particle Filter 」
「SIS Particle Filter」的流程
實際的應用-視覺追蹤
「Particle Filter」的問題及其它
前言，看了很多次的Particle Filter(不能說很久，因為這東西一直沒深入…)
一直是懵懂
但還是想寫一下這篇
此篇可能是架構最散的一篇了…
真的不知該怎麼有順序的講解這東西
如果從前面開始看有一種搞不懂什麼是什麼的情況
可以先看一下實際應用中x和z的對應
另外對於數學式的轉換感到厭煩
可以直接看SIS和SIR的流程
始於「Monte Carlo 蒙地卡羅法」
Monte Carlo是一種利用採樣去評估目標未知事物(曲線、面積、分佈…)的一種方法
以圖講解
為了方便講解這裡使用一維的曲線來做說明
圖A 為我們要評估的曲線
事實上這條曲線是未知的
為了得知曲線實際的樣子
Monte Carlo利用有限個隨機採樣點來採樣整個曲線空間 (圖B)
並且取得這些採樣點的數值 (圖C)
最後利用這些採樣點來評估我們要求得的曲線 (圖D 綠色曲線)
事實上這個方法求得的曲線和實際的曲線會誤差存在
但如果我們利用任意多個採樣點的話
我們最終可以完全近似要得到的曲線
基於「Bayesian recursion」
Bayesian recursion是一種評估方法的機率模型
公式可以寫成如下
x：代表狀態
z：代表觀測值
k：代表時間k
而上面的公式簡單的說明如下
後驗機率 = 似然率 x 先驗機率 / 正規化項
先驗機率 = 上個時間的後驗機率 x 轉移機率
其中
fk定義為Xk-1到Xk的轉換過程
h為觀測函式
vk-1和nk分別代表noise
「Particle Filter」的主要思想
Particle Filter利用Monte Carlo的方法來解決Bayesian recursion
利用有限個具有權重的粒子來近似後驗分佈
而每個粒子的權重為
分母的pi為重要性分佈
事實上我們利用這個重要性分佈來決定採樣點的位置
「SIS Particle Filter 」
SIS Particle Filter 全名為 Sequential importance sampling Particle Filter
讓我們先回到PF(Particle Filter)中粒子的權重計算為
如果讓重要性函數成為遞迴型式
我們可以得到
在這個公式下我們得知時間k的權重和時間k-1相關
而SIS PF假設重要性分佈等於轉移分佈
則可以得到
讓權重的計算簡化
時間k的權重 = likelihhod * 上個時間k-1的權重
「SIS Particle Filter」的流程
SIS PF的流程如下
整個SIS PF的步驟非常簡單
- 利用重要性分佈採樣粒子
- 計算每個粒子的權重
- 正規化權重
實際的應用-視覺追蹤
上面講了一大堆
每個東西在應到實際的問題中倒底代表什麼?
以下利用視覺追蹤來講解
首先說明一下視覺追蹤的問題
給定要追蹤的樣板
template
要尋找的序列影像
t t+1
....
t+n
要求得的問題為在影像t中template的位置、大小…等資訊
這邊先簡化問題
假定只有位置會改變
其它如大小…等資訊都為固定
那Xk = {x,y} 為template在影像k中x,y位置
而Zk = 影像k中位置x,y的觀測值 (特徵值) (大小和樣板大小相同，x到x+w，y到y+h整個矩形的資訊)
likelihood為任一種template和觀測值的相似度評估方式
「SIS Particle Filter」的問題
-
SIS PF假定
然而這樣會忽略Zk的資訊 -
經過幾次的疊代後粒子會有退化的現象
少部份的粒子具有較大的權重
其它的粒子的權重很低
這意味著大部份的粒子的採樣都是不重要的 (浪費計算時間的行為)
對於第2個問題可以用SIR PF (Sequential importance resampling Particle Filter)解決
加入重採樣步驟
利用
來判斷粒子權重的平衝性
如果該值小於一個閥值則重新採樣
流程為
-
-
-
-
-
if Neff < Th
重採樣
而重採樣的方式則是在具有較高權重的地方
採樣較多的點，如圖
「Particle Filter」的問題及其它
問題?
就我所知PF的問題有幾個
- 重要性分佈的選擇
- 粒子的退化問題
- 粒子的貧化問題 (利用SIR PF後粒子會只往權重高的地方採樣，造成粒子的多樣性不足)
- 多維度的近似需要非常多的粒子才有較小的誤差
非線性非高斯?
另外網路上許多資料常說PF的優點是非線性非高斯的濾波器
在這邊就我的理解說明一下什麼是非線性非高斯
非線性即為
過程轉移fK和觀測函數h是非線性的
而非高斯指的是
Vk-1和nk兩個noise的分佈不為高斯
事實上這樣的假定比較適用於實際的應用
如果已知過程程轉移為線性和noise分佈為高斯
則Kalman Filter則是最佳的濾波器
其它的PF
Unscented particle filter
Auxiliary particle filter
Rao–Blackwellized particle filter
Adaptive particle filter
當然還有很多不同類型的PF就提一下我看了覺得滿有趣的
參考資料
- A Tutorial on Particle Filters for Online Nonlinear/Non-Gaussian Bayesian Tracking
- 粒子滤波算法综述
- Particle Filter Wiki
新手發文如有錯誤，煩請指正！