粒子濾波(PF: Particle Filter)算法起源于20世紀50年代Poor Man's Monte Carlo問題的研究，但第一個具有應用性的粒子濾波算法于1993年由Gordon等提出（“A novel Approach to nonlinear/non-Gaussian Bayesian State estimation”）。它是利用粒子集來表示機率，可以用在任何形式的狀态空間模型上。其核心思想是通過從後驗機率中抽取的随機狀态粒子來表示其分布情況，是一種順序重要性采樣法(Sequential Importance Sampling)。
粒子濾波的應用非常廣泛，尤其是在目标跟蹤（“A probabilistic framework for matching temporal trajectories”）等視覺任務方面。粒子濾波算法有許多不同的改進方式。針對不同的問題，PF算法被改造以适應更好的問題。本文主要側重于目标跟蹤方面的應用。以人臉跟蹤為例，下圖展示了粒子濾波的跟蹤結果。下面介紹下粒子濾波的基本過程：初始化、機率轉移、權重重計算和重采樣四個階段。
圖1 人臉跟蹤
1.初始化階段
跟蹤區域初始化。在使用粒子濾波算法進行目标跟蹤前需要選擇要跟蹤的目标物體。這個過程可以用人工劃定方法和自動識别方法。使用人工的方法可以通過滑鼠在圖像區域标記出一個感興趣矩形；使用自動的方法就是利用自動的目标檢測技術，初步檢測出圖像中要跟蹤物體的大緻位置。以人臉跟蹤為例，人工方法就是滑鼠劃定視訊第一幀中人臉的區域；自動方法就是可以使用人臉檢測算法檢測出人臉的初始位置。
粒子初始化。對于本文人臉檢測的示例，粒子就是圖像中的矩形區域，主要由矩形中心(x,y)和寬高(w,h)四個變量表示。粒子初始化的步驟，就是在圖像中選擇指定數量的粒子（矩形），比如N=100個粒子。粒子初始化過程就是在圖像中随機或指定方式放粒子。比如說，我們可以指定100個粒子初始狀态和跟蹤區域一緻，即粒子參數和跟蹤區域的(x,y,w,h)相等。
2.狀态轉移階段
使用粒子濾波算法來對目标進行跟蹤，即是通過前一次的先驗機率來估算出目前環境下的後驗機率密度，這個過程也是由粒子來完成的。具體來說，即根據上一幀中粒子的狀态(x,y,w,h)t-1，來估計出本幀中各個粒子的狀态(x,y,w,h)t。從上一幀圖像的粒子狀态轉變為目前幀粒子的狀态，這個變異過程就叫作轉移（transmission）。粒子濾波的轉移方程跟Kalman濾波的差不多：
（1）
上面的是狀态轉移方程，下面的為觀測方程， wk 和 vk 是高斯噪聲。在本文示例中， x k = ( x,y,w,h ) t 。變量 x , y , w , h 可以依據公式（1）分别更新。在不同的算法中， f 采用的函數也不相同。如果 xk=xk-1+wk ， 則狀态轉移方程其實是随機遊走過程； 如果 xk=A x k-1 +w k ，狀态轉移方程則為一階自回歸方程；如果 xk=A 1 x k-1 +A2xk-2+w k ， 則狀态轉移方程為二階自回歸方程。
3.權重重計算階段
轉移階段将上一幀中粒子的位置進行了轉移，得到目前幀中新的位置。但并不是所有粒子的作用都有用。也就是有些粒子并不是跟蹤區域所要所移動的位置。是以，在此階段，粒子濾波算法将對每個粒子進行打分，将得分較低的粒子删除，将得分多的粒子生成更多的粒子（重采樣過程完成）。具體打分的方法根據不同的需求會不同，例如人臉跟蹤方法中使用距離作為衡量的标準。将每個粒子與跟蹤區域進行相似度計算（在這裡，分别提取粒子和跟蹤區域的視覺特征進行計算，比如顔色直方圖），使用相似度作為相應粒子的權重。每一個粒子都需要計算其權重，并且需要将其歸一化。該階段其實也是後驗機率進行更新的過程。
4.重采樣階段
粒子濾波算法會淘汰權值低的粒子，讓權值高的粒子來産生出更多的粒子，這就使得算法朝着權值高的地方收斂。假設有100個粒子，1号粒子的權重為0.02而2号粒子的權重為0.003。于是在重采樣階段，1号粒子生孩子的名額是0.02×100=2，2号粒子的名額是0.003×100=0.3，可以發現，1号粒子除了剛産生的粒子外還要再額外的産生一個粒子，而2号粒子就被鏟除了。如此，最後得到的100個粒子即為所求，然後取個權重平均就得到了目标的狀态值。
參考：
1. http://www.cnblogs.com/yangyangcv/archive/2010/05/23/1742263.html