粒子濾波跟蹤算法

1、粒子濾波跟蹤算法：以下分三步理解粒子跟蹤算法，第一種理解是先從形象化理解粒子算法。第二種理解是編寫簡單的粒子算法。附有有源碼，可結合源碼理解。第三種理解是從數(shù)學角度理論地理解粒子算法。第一種理解：我們看下形象化的粒子濾波跟蹤算法。（以下段落為轉載）1）初始化階段-提取跟蹤目標特征該階段要人工指定跟蹤目標，程序計算跟蹤目標的特征，比如可以采用目標的顏色特征。具體到Rob Hess的代碼，開始時需要人工用鼠標拖動出一個跟蹤區(qū)域，然后程序自動計算該區(qū)域色調(Hue)空間的直方圖，即為目標的特征。直方圖可以用一個向量來 表示，所以目標特征就是一個N*1的向量V。2）搜索階段-放狗好，我們已經(jīng)掌握了目標

2、的特征，下面放出很多條狗，去搜索目標對象，這里的狗就是粒子particle。狗有很多種放法。比如，a)均勻的放：即在 整個圖像平面均勻的撒粒子(uniform distribution)；b)在上一幀得到的目標附近按照高斯分布來放，可以理解成，靠近目標的地方多放，遠離目標的地方少放。Rob Hess的代碼用的是后一種方法。狗放出去后，每條狗怎么搜索目標呢？就是按照初始化階段得到的目標特征(色調直方圖，向量V)。每條狗計算它所處的位置 處圖像的顏色特征，得到一個色調直方圖，向量Vi，計算該直方圖與目標直方圖的相似性。相似性有多種度量，最簡單的一種是計算sum(abs(Vi- V).每條狗算出相似

3、度后再做一次歸一化，使得所有的狗得到的相似度加起來等于1.3）決策階段我們放出去的一條條聰明的狗向我們發(fā)回報告，“一號狗處圖像與目標的相似度是0.3”,“二號狗處圖像與目標的相似度是0.02”,“三號狗處圖像 與目標的相似度是0.0003”,“N號狗處圖像與目標的相似度是0.013”.那么目標究竟最可能在哪里呢？我們做次加權平均吧。設N號狗的圖像像 素坐標是(Xn,Yn),它報告的相似度是Wn,于是目標最可能的像素坐標X = sum(Xn*Wn),Y = sum(Yn*Wn).4）重采樣階段Resampling既然我們是在做目標跟蹤，一般說來，目標是跑來跑去亂動的。在新的一幀圖像里，目標可能在

4、哪里呢？還是讓我們放狗搜索吧。但現(xiàn)在應該怎樣放狗呢？讓 我們重溫下狗狗們的報告吧?！耙惶柟诽巿D像與目標的相似度是0.3”,“二號狗處圖像與目標的相似度是0.02”,“三號狗處圖像與目標的相似度是 0.0003”,“N號狗處圖像與目標的相似度是0.013”.綜合所有狗的報告，一號狗處的相似度最高，三號狗處的相似度最低，于是我們要重新分布 警力，正所謂好鋼用在刀刃上，我們在相似度最高的狗那里放更多條狗，在相似度最低的狗那里少放狗，甚至把原來那條狗也撤回來。這就是Sampling Importance Resampling，根據(jù)重要性重采樣(更具重要性重新放狗)。(2)-(3)-(4)-(2)如是反

5、復循環(huán)，即完成了目標的動態(tài)跟蹤。根據(jù)我的粗淺理解，粒子濾波的核心思想是隨機采樣+重要性重采樣。既然我不知道目標在哪里，那我就隨機的撒粒子吧。撒完粒子后，根據(jù)特征相似度計算 每個粒子的重要性，然后在重要的地方多撒粒子，不重要的地方少撒粒子。所以說粒子濾波較之蒙特卡洛濾波，計算量較小。這個思想和RANSAC算法真是不謀 而合。RANSAC的思想也是(比如用在最簡單的直線擬合上)，既然我不知道直線方程是什么，那我就隨機的取兩個點先算個直線出來，然后再看有多少點符合 我的這條直線。哪條直線能獲得最多的點的支持，哪條直線就是目標直線。想法非常簡單，但效果很好。第二種理解：簡單的粒子算法實現(xiàn)如下：1、 如

6、果要跟蹤多個對象，首先要給出第一張圖，在其中把這些對象用方框圈出。用顏色直方圖來描述這些方框中圖像特征。譬如有個跟蹤對象，則對應有個方框，以及個顏色直方圖信息。2、 假設，此時我們用個粒子去跟蹤這個對象。那么每個對象分配個粒子。、所有對象的跟蹤方法是一樣的，所以我們只研究一個對象的跟蹤。一個對象有5個粒子，那什么叫粒子呢？且聽我道來。剛開始所有粒子其實就是跟對象方框一樣大小的矩形檢測器。這5個矩形檢測器的位置跟對象方框重疊。假設檢測開始，（1）這5個矩形檢測器，會利用二階自回歸模型計算出新的位置，新的位置都是圍繞在對象中心點周圍。（2）新位置計算出來后，計算各個矩形檢測器里面的圖像的顏色直方圖

7、，和對象的顏色直方圖做比較，根據(jù)相似度來度量5個檢測器的權值，相似度越高，權值越大。（3）用權值歸一法把5個權值歸一。如，5個權值的值是：0.016，0.02，0.04，0.01，0.014。權值歸一就是讓5個權值加起來等于1，但兩兩比例不變歸一后的權值是：0.16，0.2，0.4，0.1，0.14。（4）權值歸一后，就得進行重采樣，也就是把權值低（不重要的）的檢測器移到權值高的位置去檢測。做法是，把權值為0.1和0.14的兩個權值最低的檢測器，移到跟權值為0.4的檢測器一樣的位置。 （5）跳到（1）去，重復（1）- （4）步驟。4、算法到此結束。 這里有些疑問。（1） 為什么二階自回歸模型可

8、以計算出新的位置。答案是：自回歸過程是一種通過歷史數(shù)據(jù)來預測目前狀態(tài)的時間序列建模策略. 在這個模型里,目前的狀態(tài)xt 是一個依賴于以前狀態(tài)的確定性函數(shù)并加上隨機干擾,假如確定性函數(shù)是線性的,則目前的狀態(tài)依賴于以前的p 個狀態(tài),模型可以寫成其中： 是自回歸系數(shù);t 是隨機干擾,一般情況下是白噪聲. 自回歸系數(shù)既可通過學習的方法得到 ,也可以特別的方式指定 . 鑒于運動員在比賽中的慣性影響,采用持續(xù)速度模型更為適合一些,這里采用二階自回歸模型其中: A , B , C 是自回歸系數(shù), N (0 ,) 是零均值、標準方差為1 的Gaussian 噪聲. 在試驗中,指定系數(shù)為A = 2 , B =

9、- 1 , C = 3. （2）為什么要進行重采樣？答案是：因為如果沒進行重采樣，則有些粒子（檢測器）權值會越來越小，最后只有一個檢測器的權值比較大。這種現(xiàn)象叫退化。它意味著要花很多時間去計算哪些權值較低的檢測器，這是不希望看到的。5、算法評價（個人想法）： 該算法借鑒了粒子過濾器的思想，但比正真的粒子過濾要簡單很多，其跟蹤準確率相對較低，而且如果物體移動速度快的話，該算法將跟蹤失敗。附注：了解粒子算法，可以看下我修改過的粒子過濾跟蹤算法源碼工程FSTrace，該工程是別人編寫，原先只能在LINUX下編譯通過，我稍微改動下，現(xiàn)可以在Windows下編譯通過并執(zhí)行。第三種理解粒子算法加深。以下只

10、是個人理解。粒子人臉跟蹤算法其實是一種基于概率抽樣的算法。（1）人臉跟蹤其實就是根據(jù)現(xiàn)在的人臉位置預測下一時刻人臉的位置。 那怎么預測下一時刻的人臉位置呢？ 如果能找到一個概率分布密度函數(shù)，那事情就容易辦了？該函數(shù)輸入?yún)?shù)是被檢測窗口任一點的位置，輸出是這點存在人臉的概率。 這意味著概率最大的點最有可能存在人臉，可直接把這一點作為下一時刻的人臉位置。概率密度函數(shù)表達式是：p(Xk | Dk)。Xk表示點信息（可以包含速率信息）。Dk是表示檢測窗口所有像素點值的向量。（2）所以關鍵是找到概率密度函數(shù)。 對于該密度概率函數(shù)，我們要撒下一些粒子才能求到。一個N*N像素點陣就是粒子。（3） 怎么計算該

11、概率密度函數(shù)呢？我們假設檢測窗口為100*100，粒子的尺寸是5*5，那么粒子數(shù)量是20 * 20 = 400。剛開始（為第一時刻，此時還沒有任何影像輸入）所有粒子的位置遍布整個檢測窗口。它們的概率是都是1 / 400。概率密度函數(shù)是一條直線，輸出也都是1 / 400。（4）此時要預測下一時刻（這時影像開始輸入）的概率密度函數(shù)怎么辦？我們先讓所有粒子隨機走動，隨機走動的算法，可由以下公式表示：譬如， 。系統(tǒng)噪聲Wk是零均值的高斯白噪聲，輸入的是X(k-1)，表示前一時刻的粒子位置、速度值，輸出是X(k)，表示隨機走動后的位置、速度值。（5） 這里有個問題，以上公式的系統(tǒng)噪聲Wk的值怎么求得呢？

12、（注：該Wk值不同于粒子權值的Wk值。）它是在粒子周圍產(chǎn)生的隨機偏差。（6）粒子隨機走動到新位置后，我們的任務就是求得下一時刻的粒子概率密度函數(shù)：p(Xk | Dk)。用以下公式我們可以近似求得， （注：該Wk值不同于粒子權值的Wk值。）這公式怎么理解呢？Wk表示粒子的權值，剛開始都相等。我們假設它們都等于1。此時，計算所有粒子和Xk對應的矩陣的相似度加權和，加權和越大，說明粒子移動到該位置的概率越大。那Xk對應的矩陣是什么呢？它是以檢測窗口任一點為中心的5*5矩陣。所以公式的意義是這樣的：給定檢測窗口的任意一點，計算所有粒子和該點對應5*5矩陣的相似度的加權和。加權和就是目標物體（5*5像素

13、矩陣點）移動到該位置的概率。為什么要用到Wk呢？主要是考慮到上一時刻的粒子和目標物體的相似度，相似度越大Wk越大，粒子移動這時刻的Xk位置的概率越大。所以用上一時刻的歷史經(jīng)驗Wk乘于粒子和Xk的相似度更合乎貝葉斯概率的原理（詳見貝葉斯概率相關資料），也更合乎實際。（7）既然知道目標物體移動到檢測窗口任一點的概率，那p(Xk | Dk)即被求得。此時從p(Xk | Dk)中隨機抽出400個粒子，重復（4）-（7）步驟。注意：抽出來的400個粒子權值高的占多數(shù)，所以不用進行重采樣。因為權值高的容易被抽出來。但是重采樣又是怎么回事？其實在實際的編程中并不會按照（1）-（7）那樣進行，而是按照上面“第

14、二種理解”的方法進行。所以重采樣不可避免。以上描述的只是數(shù)學理論，理論過程跟實際過程有差異。（8） 到此似乎還有問題，權值Wk一直不變的嗎？肯定不是，在第7步同時要對粒子權值進行求解。 A、如果知道粒子的理論概率分布，則可以按照以下求得Wk值。請看以下公式，表示一個狀態(tài)（k時刻）下一個粒子的權值。粒子實際的概率。粒子對應直方圖和參考對象直方圖的相似度越大，該值越大。粒子理論的概率。即重要性密度函數(shù)。如果粒子實際的概率越接近理想的概率，則的值越大。圖（1）如圖（1）粒子1的概率是0.9，粒子2的概率是0.1，粒子3的概率是0.1，粒子4的概率是0.3，粒子4的概率是0.4。假設這是理想的概率分布，由函數(shù)求得粒子概率。而用求得的實際的概率分布如下，粒子1的概率是0.68，粒子2的概率是0.09，粒子3的概率是0.09，粒子4的概率是0.29，粒子4的概率是0.39。