粒子濾波總結（摘來總結）

OpenCV中實作了粒子濾波的代碼，位置在opencv\cv\src\cvcondens.cpp檔案

粒子濾波跟蹤器的資料結構：

typedef struct CvConDensation

{

int MP; // 測量向量的維數： Dimension of measurement vector

int DP; // 狀态向量的維數： Dimension of state vector

float* DynamMatr; // 線性動态系統矩陣：Matrix of the linear Dynamics system

float* State; // 狀态向量： Vector of State

int SamplesNum; // 粒子數： Number of the Samples

float** flSamples; // 粒子向量數組： array of the Sample Vectors

float** flNewSamples; // 粒子向量臨時數組： temporary array of the Sample Vectors

float* flConfidence; // 每個粒子的置信度(譯者注：也就是粒子的權值)：Confidence for each Sample

float* flCumulative; // 權值的累計： Cumulative confidence

float* Temp; // 臨時向量：Temporary vector

float* RandomSample; // 用來更新粒子集的随機向量： RandomVector to update sample set

CvRandState* RandS; // 産生随機向量的結構數組： Array of structures to generate random vectors

} CvConDensation;

與粒子濾波相關的幾個函數：

cvCreateConDensation：用于構造上述濾波器資料結構

cvReleaseConDensation：釋放濾波器

cvConDensInitSampleSet：初始化粒子集

cvConDensUpdateByTime：更新粒子集

前期準備：

人工指定跟蹤目标，程式計算跟蹤目标的特征，比如可以采用目标的顔色特征。比如開始自動計算該區域色調(Hue)空間的直方圖，即為目标的特征。直方圖可以用一個向量來表示，是以目标特征就是一個N*1的向量V。

 原理：

對任意如下的狀态方程

x(t)=f(x(t-1),u(t),w(t))

y(t)=h(x(t),e(t))

其中的x(t)為t時刻狀态，u(t)為控制量，w(t) 和e(t)分别為模型噪聲和，觀測噪聲。

前一個當然是狀态轉移方程，後一個是觀測方程。那麼對于這麼一個問題粒子濾波怎麼來從觀測y(t)，和x(t-1),u(t) 濾出真實狀态x(t)呢？

濾波的預估階段：粒子濾波首先根據x(t-1) 和他的機率分布生成大量的采樣，這些采樣就稱之為粒子。那麼這些采樣在狀态空間中的分布實際上就是x(t-1) 的機率分布了。好，接下來依據狀态轉移方程加上控制量可以對每一粒子得到一個預測粒子。所有的預測粒子就代表了涉及哪些參數化的東西。

進入校正階段來：有了預測粒子，當然不是所有的預測粒子都能得到我們的時間觀測值y對不，越是接近真實狀态的粒子，當然獲得越有可能獲得觀測值y對吧。于是我們對所有的粒子得有個評價了，這個評價就是一個條件機率P(y|xi),直白的說，這個條件機率代表了假設真實狀态x(t)取第i個粒子xi時獲得觀測y的機率。令這個條件機率為第i個粒子的權重。如此這般下來，對所有粒子都進行這麼一個評價，那麼越有可能獲得觀測y的粒子，當然獲得的權重越高。好了，預測資訊融合在粒子的分布中，觀測資訊又融合在了每一粒子的權重中。

最後采用重采樣算法，去除低權值的粒子，複制高權值的粒子。所得到的當然就是我們說需要的真實狀态x(t)了，而這些重采樣後的粒子，就代表了真實狀态的機率分布了。

下一輪濾波，再将重采樣過後的粒子集輸入到狀态轉移方程中，直接就能夠獲得預測粒子了。

（

對于重采樣的目的，是為了解決序列重要性采樣（SIS）存在的退化現象，即幾步疊代之後，許多粒子的權重變得很小，大量的計算浪費在小權值的粒子上。解決退化問題的一般辦法就是重采樣原理，基本思想就是對後驗機率密度再采樣，保留複制權重大的粒子，剔除權重小的粒子。

有許多重采樣（resampling）方法，它決定了粒子濾波算法的計算複雜度。

經過幾次疊代,除一個粒子以外,所有的粒子隻具有微小的權值,稱為退化問題。退化現象意味着大量的計算工作都被用來更新那些對的估計幾乎沒有影響的粒子上。減小這一不利影響的首要方法是增加粒子數目。因為粒子濾波的實質是大數定理,取足夠多的樣本就可以使樣本均值以機率1趨于數學期望。在實際應用中,為了獲得對後驗分布更高的逼近精度,需要适當地增加粒子個數。降低該現象影響的最有效方法是選擇重要性函數和采用重采樣方法。 （1）重要性函數選擇        選取好的重要性機率密度函數可以有效抑制退化問題,進而減小需要的粒子數目,提高運作速度。出于降低重要性權值的方差、提高抽樣效率的目的,重要性機率密度函數應盡可能地接近系統狀态後驗機率。選取重要性函數的準則是使重要性權重的方差最小。 （2）重采樣        重采樣算法是降低粒子匮乏現象的另一種方法,其思想是通過對粒子和相應權表示的機率密度函數重新采樣,增權重值較大的粒子數。其方法是 對後驗密度的離散近似表示式（6）再進行一次采 樣,生成一個新的粒子集,該粒子集構成後驗密度離 散近似的一個經驗分布。在采樣總數仍保持為的情 況下,權值較大的樣本被多次複制,進而實作重采樣過程。顯然,重采樣過程是以犧牲計算量和魯棒性來降低粒子數匮乏現象。

）

初始狀态的問題： 咱們一開始對x(0)一無所知對吧，那咱們就認為x(0)在全狀态空間内平均分布呗。于是初始的采樣就平均分布在整個狀态空間中。然後将所有采樣輸入狀态轉移方程，得到預測粒子。嘿嘿再評價下所有預測粒子的權重，當然我們在整個狀态空間中隻有部分粒子能夠獲的高權值咯。馬上重采樣算法來了，去除低權值的，将下一輪濾波的考慮重點立馬縮小到了高權值粒子附近。

 a)均勻的放：即在整個圖像平面均勻的撒粒子(uniform distribution)；b)在上一幀得到的目标附近按照高斯分布來放，可以了解成，靠近目标的地方多放粒子，遠離目标的地方少放粒子。

粒子濾波的核心思想是随機采樣+重要性重采樣。既然我不知道目标在哪裡，那我就随機的撒粒子吧。撒完粒子後，根據特征相似度計算每個粒子的重要性，然後在重要的地方多撒粒子，不重要的地方少撒粒子。是以說粒子濾波較之蒙特卡洛濾波，計算量較小。這個思想和RANSAC算法真是不謀而合。RANSAC的思想也是(比如用在最簡單的直線拟合上)，既然我不知道直線方程是什麼，那我就随機的取兩個點先算個直線出來，然後再看有多少點符合我的這條直線。哪條直線能獲得最多的點的支援，哪條直線就是目标直線。缺點：嚴重依賴于對初始狀态的估計。可能很快收斂或者很快發散（由于僅在似然方程中用到了觀測值）

粒子濾波分類：

1.經典粒子濾波（Sampling Importance Resampling，SIR)

         補充：序貫重要性采樣（sequential importance sampling，SIS)是重要性采樣的擴充。

2.正則粒子濾波(Regularized Particle Filter，RPF)

        是為了解決由重采樣引入的新問題而提出的一種改進的粒子濾波。當通過序貫重要性采樣後引起粒子退化問題時，前面提到可以用重采樣的方法來減小退化的影響，但是引入重采樣政策同時也引入了新的問題，即粒子匮乏問題，經過若幹次疊代之後，所有粒子都趨向于同一個粒子，導緻粒子的多樣性喪失。這是因為在重采樣過程中，粒子是從離散分布中采樣取得的，而不是從連續分布中采樣得到的。

正則粒子濾波正是為了解決上述問題而提出的。它與SIR粒子濾波的差別在于：在重采樣過程中，SIR從離散近似的分布中重采樣，而正則粒子濾波則從連續近似的分布中重采樣。

根據正則化在選擇步驟之前還是之後，RPF分為Post-RPF和Pre-RPF。

3.輔助粒子濾波(Auxiliary Particle Filter, APF)

        Pitt和Shephard在标準SIR濾波算法的基礎上提出了輔助粒子濾波。與标準序列重要性重采樣(SIR)算法相比，APF也是以序列重要性采樣(SIS)算法為基礎，隻是選擇了不同的重要性密度函數。

        與SIR濾波算法相比，輔助粒子濾波算法的優勢在于它在k-1時刻的樣本集合上随機抽取了一些點，抽取時以目前的觀測資料為條件，這樣可以更加接近真實的狀态。

4.高斯粒子濾波(Gaussian Particle Filter，GPF)

        Jayesh和Petar提出的，将高斯濾波和粒子濾波結合，稱為高斯粒子濾波。該方法的前提是用高斯分布來近似後驗分布，它比其它的高斯濾波方法适用性更強，能處理更多非線性動态系統問題；而與一般的粒子濾波相比，因為GPF用高斯分布近似後驗分布，是以隻要所用的高斯分布是正确的，就不會産生粒子退化問題，就不需要對粒子進行重采樣，進而使算法的計算量降低，複雜度也降低。

        高斯粒子濾波比其它高斯濾波有更好的性能，而與一般的粒子濾波相比計算量大大減小，複雜度降低。但是高斯濾波在後驗分布不能用高斯分布近似的非線性動态空間模型或者非線性系統非加性高斯噪聲模型時，濾波性不能令人滿意。

5.邊緣化粒子濾波（Marginalized Particle Filter，MPF）