用于目標跟蹤的智能群體優(yōu)化濾波算法

許奇，王華彬，周健，陶亮

（安徽大學 計算智能與信號處理教育部重點實驗室，安徽 合肥 230031）

濾波算法是一種能在非線性離散時間內(nèi)估計后驗狀態(tài)的算法。在目標跟蹤中，濾波算法是在貝葉斯濾波(Bayesian filter)框架下，給定當前時刻的觀測信息，估計目標的后驗狀態(tài)并預測下一時刻的先驗狀態(tài)。當前應用廣泛且較為成熟的濾波算法有卡爾曼濾波(Kalman filter，KF)、擴展卡爾曼濾波 (extended Kalman filter，EKF)、無跡卡爾曼濾波(unscented Kalman filter，UKF)和粒子濾波(particle filter，PF)等。KF算法只能用來解決線性問題，而在目標跟蹤中大多數(shù)情況下都是非線性問題，因而適用度不高[1]。EKF算法將非線性系統(tǒng)局部線性化，對于較弱的非線性系統(tǒng)可以獲得很好的濾波效果，但對于較強非線性系統(tǒng)，效果并不理想。UKF算法采用無極變換和EKF算法框架，其思想是近似高斯分布比近似非線性方程要容易；UKF算法雖然能夠得到三階矩的后驗均值及協(xié)方差估計，但由于其與EKF一樣，假設非線性系統(tǒng)的后驗狀態(tài)服從高斯分布，因而對一般的模型仍不適用[2]，因此并不適用于目標跟蹤。

在目標跟蹤中用于估計后驗狀態(tài)的最著名的方法為粒子濾波算法(particle filter，PF)。PF算法采用序貫蒙特卡洛方法(sequential Monte Carlo methods，SMC)，采用一組樣本(即粒子)近似表示非線性系統(tǒng)的后驗分布，再使用這一近似表示估計系統(tǒng)的狀態(tài)。與其他幾種算法相比，PF算法更適用非線性系統(tǒng)，適用范圍更廣，實際效果也較好。在當前主流的視覺跟蹤算法中，如L1APG算法[3]、CNT算法[4]和IOPNMF算法[5]等皆是以粒子濾波為框架的跟蹤算法。然而粒子濾波算法無法避免粒子退化[6]現(xiàn)象，這是因為粒子權(quán)值的方差會隨著時間而遞增。為解決退化問題，一般有兩種措施：1)增加采樣數(shù)量，2)重采樣[7]方法。增加采樣數(shù)量會相應地增加計算量，降低算法的運行效率。重采樣的思想是舍棄權(quán)值較小的粒子，繁殖權(quán)值較大的粒子。然而過度地重采樣會產(chǎn)生新的問題：由于大權(quán)值粒子被反復地選擇，粒子多樣性很快喪失，導致樣本貧化問題[8]。粒子濾波算法存在的另一個問題是要求在狀態(tài)轉(zhuǎn)移過程中，進化后的粒子需要能夠涵蓋目標所有的可能狀態(tài)，否則跟蹤的結(jié)果就會逐漸偏離目標的真實位置，導致跟蹤失敗。解決的方法一般有兩種：1)增加粒子數(shù)，顯然這種方法會增加計算量，導致算法的實時性降低；2)設計合適的狀態(tài)轉(zhuǎn)移方程，以提高每個粒子對于狀態(tài)預測的準確率。

智能群體（又稱為群智能[9], swarm intelligence，SI）是一類仿生物行為計算技術(shù)，源于生物群體的行為規(guī)律。例如觀察螞蟻、蜜蜂、鳥類、魚群等社會性群居動物可以發(fā)現(xiàn)，它們分工合作、各司其職像有思維有意識一樣地筑巢、覓食。同時人們也觀察到不同生物群體有著不同的行為特征，例如，魚群會向有食物源的地方聚集；蜂群在離開蜂巢尋找食物時會向周圍分離；而蟻群則會共同地搬動食物并排列運送至蟻巢。在對這些行為特征總結(jié)歸納后發(fā)現(xiàn)這些群體行為具有群集共性[10]。動物的群集共性給人們解決新問題帶來啟發(fā)，例如，Cheng等[11]利用群智能優(yōu)化分析大數(shù)據(jù)，并設計出一個更加有效的數(shù)據(jù)分析算法；Xia[12]利用群智能優(yōu)化解決網(wǎng)絡覆蓋優(yōu)化問題，提高了無線傳感器網(wǎng)絡(wireless sensor network)的網(wǎng)絡覆蓋率；Devi等[13]將群智能優(yōu)化技術(shù)用于增強語音計算技術(shù)，相比于傳統(tǒng)的梯度算法，提高了語音系統(tǒng)的信噪比。

在目標跟蹤中，后驗概率估計的準確度直接影響到跟蹤結(jié)果的精確度。因此，本文將貝葉斯濾波理論與智能群體優(yōu)化算法結(jié)合，提出一種新穎的智能群體優(yōu)化濾波算法。相比于傳統(tǒng)的粒子濾波算法，本文算法能夠有效地應對粒子退化問題，提高跟蹤算法的準確度。

1 貝葉斯濾波理論

給定離散時間動態(tài)系統(tǒng)的狀態(tài)空間模型(dynamic state-space model，DSSM)可描述為

1.1 預測過程

1.2 更新過程

2 智能群體優(yōu)化濾波算法

貝葉斯濾波方法主要分為更新和預測兩個階段。更新的目的是為了利用最新觀測值對先驗濾波概率密度進行修正，得到后驗濾波概率密度，預測的目的則是根據(jù)當前狀態(tài)預測下一時刻先驗濾波概率密度。由于式(3)和式(6)的積分難以計算，所以按照經(jīng)典蒙特卡洛模擬方法：將后驗概率密度轉(zhuǎn)化為累積概率密度分布，然后在區(qū)間[0，1]中隨機抽取N個數(shù)值，每個值對應一個目標狀態(tài)，由此得到N個獨立同分布的樣本則后驗濾波概率密度可以近似計算為

然而實際應用時，真實的后驗概率密度是無法知道的，因此通過CDF采集樣本是不現(xiàn)實的。這啟發(fā)了我們可以結(jié)合實際情況有選擇的采樣，即結(jié)合智能群體優(yōu)化方法，充分利用最新的觀測信息，將移動粒子至高似然區(qū)，得到可靠的建議分布作為重要性密度函數(shù)進行重要性采樣[14]。假設經(jīng)過智能群體優(yōu)化后的建議分布為則根據(jù)蒙特卡洛模擬方法有：

其中：

為k時刻第i個粒子所對應的權(quán)值，由相應的觀測模型[15]求出。則后驗濾波概率密度：

又因為：

聯(lián)立式 (8)、式 (10)、式 (11)，可得：

由以上推導可知，在貝葉斯濾波中，求得后驗濾波概率密度之前，可以根據(jù)最新的觀測信息，結(jié)合智能群體優(yōu)化方法，通過粒子分層后，將權(quán)值較低的粒子移動到高似然區(qū)，即將粒子移動到權(quán)值更大的區(qū)域，再結(jié)合蒙特卡洛模擬產(chǎn)生可靠的重要性密度函數(shù)，進行重要性采樣，即可估計出后驗狀態(tài)。

2.1 粒子分層

2.2 粒子運動

群集共性表現(xiàn)在3個方面：內(nèi)聚、分離和排列。 內(nèi)聚運動時，各成員朝著一個平均的中心位置進行聚合；分離運動時，各成員遠離一個平均的中心位置；排列運動時，各成員朝著一個平均的方向共同運動，如圖1所示。

圖 1 群集共性示意圖Fig. 1 Sketch of swarm intelligence

2.2.1 內(nèi)聚運動

根據(jù)已有粒子的權(quán)值，讓權(quán)值較低的粒子移動至權(quán)值較大的區(qū)域，從而產(chǎn)生更可靠的重要性密度函數(shù)。為了提高魯棒性，粒子的移動方法如下：

2.2.2 分離運動

在當前時刻無法準確確定目標位置時，讓所有粒子進行分離運動，目的是為了下一時刻能夠盡可能多地涵蓋目標的可能狀態(tài)。粒子的移動方法如下：

2.2.3 排列運動

排列運動目的是在當前時刻能夠準確估計目標位置的情況下，預測下一時刻目標位置。采用狀態(tài)轉(zhuǎn)移概率密度作為排列運動的運動模型，即

在實際運用于目標跟蹤中，系統(tǒng)狀態(tài)轉(zhuǎn)移的運動模型有很多種，諸如勻速運動模型，自由漫步運動模型和勻加速運動模型等。這里采用勻速運動模型，它的優(yōu)點是計算簡單高效：

2.3 狀態(tài)估計

可根據(jù)最小均方誤差(minimum mean squared error, MMSE)準則或極大后驗(maximum A posterior，MAP)準則，即將條件均值或具有極大后驗概率密度的狀態(tài)作為系統(tǒng)狀態(tài)的估計值。MAP準則計算公式為

1)局部最小均方誤差(local minimum mean squared error，LMMSE)準則。

通過設定一個范圍R，計算該范圍內(nèi)的粒子數(shù)M，在對目標狀態(tài)后驗估計時，僅對范圍內(nèi)的粒子樣本進行加權(quán)求和，其計算公式為

2)全局最小均方誤差(global minimum mean squared error，GMMSE)準則。

對總數(shù)為N的粒子集中所有粒子整體加權(quán)求和，計算公式為

2.4 狀態(tài)更新

更新的目的是要充分利用當前時刻粒子的位置和權(quán)值信息，找出目標最可能的狀態(tài)，即生成合適的建議分布，從而準確地估計目標在當前時刻的位置。雖然權(quán)值較高的粒子比權(quán)值較低的粒子更能充分表示目標的位置狀態(tài)，但當高權(quán)值粒子數(shù)量較少時，容易陷入局部最優(yōu)解。因此，設計以下4條準則自適應地更新粒子狀態(tài)。

準則1當高權(quán)值粒子集中粒子數(shù)量較多時，表明在當前時刻，粒子集能充分確認目標的位置狀態(tài)，為理想的跟蹤效果。則根據(jù)GMMSE準則，計算出中心位置。在生成建議分布時，考慮到粒子多樣性，保留高權(quán)值粒子和中權(quán)值粒子的位置狀態(tài)，只對低權(quán)值粒子集中的粒子進行內(nèi)聚運動。

準則2當高權(quán)值粒子集中的粒子數(shù)量較少但大于一個閾值并且中權(quán)值粒子集中的粒子數(shù)量較多threshold)時，表明在當前狀態(tài)下，跟蹤效果良好，但高權(quán)值粒子的周圍可能擁有更高的權(quán)值。則根據(jù)LMMSE準則，對高權(quán)值粒子集里的粒子局部加權(quán)，計算出中心位置。其中閾值mpts之所以要大于0，是為了防止跟蹤算法所提取的特征[15]不能充分表示目標的狀態(tài)，即可能出現(xiàn)極個別粒子并不能表示目標位置狀態(tài)，但是依據(jù)觀測模型所計算出的權(quán)值卻較大。在生成建議分布時，保留中權(quán)值粒子的位置狀態(tài)，只對低權(quán)值粒子集中的粒子進行內(nèi)聚運動。

準則3當高權(quán)值粒子集中的粒子數(shù)量較少但大于一定閾值并且中權(quán)值粒子集中的粒子數(shù)量較少 (threshold ＞時，則根據(jù)LMMSE準則，對高權(quán)值粒子集里的粒子局部加權(quán)，計算出中心位置。在生成建議分布時，對中權(quán)值粒子集和低權(quán)值粒子集中的粒子同時進行內(nèi)聚運動。

準則4當高權(quán)值粒子集中的粒子數(shù)量極少并且中權(quán)值粒子集中的粒子數(shù)量較多時，表明此時跟蹤效果一般，但是占據(jù)較多數(shù)量的中權(quán)值粒子仍然可以近似表示目標的位置狀態(tài)。則根據(jù)LMMSE準則，對中權(quán)值粒子集里的粒子局部加權(quán)，計算出中心位置。在生成建議分布時，只對低權(quán)值粒子集中的粒子進行內(nèi)聚運動。

2.5 狀態(tài)預測

預測的目的是為了下一時刻能更準確地估計目標的狀態(tài)，即設計出合適的先驗分布函數(shù)。在SIF算法中，遵循以下兩條準則：

準則5若當前時刻滿足更新準則的條件，表明當前時刻能夠判斷目標的位置狀態(tài)。則根據(jù)GMMSE準則估計目標的后驗狀態(tài)，再將粒子集進行排列運動預測下一時刻的先驗狀態(tài)。

準則6若當前時刻不滿足更新準則中的任一條件，即當高權(quán)值粒子集中的粒子非常少 (mpts ＞并且中權(quán)值粒子的數(shù)量也較少 (threshold ＞則根據(jù)極大后驗準則估計目標的后驗狀態(tài)，并根據(jù)MAP準則確定中心位置，再對所有粒子進行分離運動預測下一時刻的先驗狀態(tài)。

2.6 算法流程

本文算法的流程如圖2所示，其具體實現(xiàn)步驟如算法1所示。

圖 2 智能群體優(yōu)化濾波算法流程Fig. 2 Algorithm flow of SIF

算法1 智能群體優(yōu)化濾波算法

輸入圖像序列共T幀，初始位置；

輸出跟蹤位置。

1) 初始化：設定粒子數(shù)N，閾值為mpts，threshold，threshold；

4) 狀態(tài)更新

6) 狀態(tài)預測

3 實驗結(jié)果與分析

為了證明本文算法的理論可靠性和實際可行性，分別進行了仿真實驗和目標跟蹤模擬實驗，實驗平臺為IntelCore3.2 GHz，2 GB內(nèi)存，MATLAB2014a。

3.1 仿真模擬實驗

為了說明智能優(yōu)化濾波算法在非線性系統(tǒng)中估計后驗狀態(tài)的性能，選擇文獻[16]中廣泛使用的一維非靜態(tài)增長模型進行模擬仿真實驗，此模型狀態(tài)的后驗分布具有雙峰特征且非線性很強，是標準的驗證模型。其狀態(tài)空間模型定義如下：

式中：

圖 3 Monte Carlo仿真結(jié)果Fig. 3 Results of Monte Carlo simulations

定義狀態(tài)估計的均方根誤差(root mean squared error，RMSE)為用來定量衡量狀態(tài)估計的準確度。

表1列出了兩種算法的RMSE誤差和運行時間。由表中數(shù)據(jù)可以看出，SIF算法狀態(tài)估計的RMSE誤差值小于PF-SIR算法，但是運行時間要多與PF-SIR算法。這是因為本文算法充分考慮到當前時刻的觀測信息，在更新過程中，將權(quán)值較低的粒子進行內(nèi)聚運動，并且更新后重新計算了權(quán)值。因此所花費時間要比PF-SIR算法多。

表 1 Monte Carlo仿真的RMSE誤差和運行時間Table 1 RMSE and runtime of Monte Carlo simulations

3.2 智能群體優(yōu)化濾波算法用于目標跟蹤

為了證明SIF算法在目標跟蹤中實際應用價值，將智能提群體優(yōu)化濾波算法分別嵌入到IVT[17]算法和IOPNMF[5]算法中。出于定性的比較，保留IVT算法和IOPNMF算法所采用的特征和模型更新[15]，將兩種算法的運動模型由粒子濾波算法改成智能群體優(yōu)化濾波算法。分別在David3、Faceocc1、Faceocc2、Singer、Girl_head、Basketball、Liquor1、ShopAssistant2cor (以下簡稱SA2c)和EnterExitCrossingPaths1cor (以下簡稱EECP1c)視頻集中進行比較，以上前7個視頻集都來源于ObjectTrackingBenchmark[18]，而SA2c和EECP1c視頻集來源于標準數(shù)據(jù)庫PETS2004。上述視頻序列涵蓋了的光照變化、平面內(nèi)外旋轉(zhuǎn)、快速運動、尺度變化、運動模糊、背景干擾及遮擋等復雜干擾情況，具體情況如表2所示。

表 2 各視頻集中的主要干擾因素Table 2 Main challenges in each sequences

為了充分比較算法的總體性能，除了將改進后的SIF_IOPNMF算法和SIF_IVT算法與原算法比較外，還與 L1APG[3]、CNT[4]、ASLA[19]、LOT[20]、MTT[21]算法進行比較，以上5種經(jīng)典的目標跟蹤算法皆是基于粒子濾波框架下。定義中心誤差為

9種算法在各視頻集中逐幀的中心誤差如圖4所示，其左上角標簽欄為平均中心誤差。定義重疊率(Overlap rate)為

圖 4 9種算法在各視頻集上的中心誤差Fig. 4 Center error of 9 algorithms in each sequences

表 3 9種算法在各視頻集中的平均重疊率(最優(yōu)值加粗表示)Table 3 Average overlap rate of 9 algorithms in each sequences

由圖4中的標簽欄和表1中數(shù)據(jù)可以看出，嵌入SIF算法后的SIF_IVT與SIF_IOPNMF算法與原算法相比，每個視頻集中的平均中心誤差皆有所降低，平均重疊率皆有所提高。其中在Faceocc2、Singer和Faceocc1這3個視頻序列中，IVT算法總體表現(xiàn)較好。在David3、Faceocc1、Singer和Faceocc2這4個視頻序列中，IOPNMF算法跟蹤效果總體表現(xiàn)良好。表2列出了這幾個視頻集的主要干擾因素，從中可以看出，IVT算法所采用的特征適合處理部分遮擋和小尺度旋轉(zhuǎn)等干擾因素，而IOT與SIFPNMF算法的模型更新準則適合處理部分遮擋和光照變化等干擾因素。此時嵌入SIF算法后的SIF_IVT和SIF_IOPNMF算法與原算法相比，跟蹤效果略有上升。由實驗結(jié)果可知：在目標跟蹤中，所選取的特征和模型更新起著重要作用；當所提取的特征和模型更新適合應對一些簡單的跟蹤環(huán)境時，采用智能群體優(yōu)化濾波的算法與采用粒子濾波的算法跟蹤效果相當。

圖5列出9種算法在部分視頻集中實驗結(jié)果部分幀截圖。在 Girl_head、Liquor1、Basketball、SA2c及EECP1c這5個視頻序列中，采用粒子濾波的IOPNMF和IVT算法都出現(xiàn)了漂移和跟蹤失敗的情況，而采用智能群體優(yōu)化濾波的SIF_IOPNMF和SIF_IVT算法跟蹤效果有著明顯的進步。圖5列出了視頻序列中部分幀的實驗結(jié)果截圖，從圖中可以看出，Girl_head視頻序列(圖5(a))中，由于目標在80幀后出現(xiàn)了平面內(nèi)旋轉(zhuǎn)、平面外旋轉(zhuǎn)和尺度變化等干擾因素，IOPNMF、IVT和LOT算法皆出現(xiàn)了漂移，SIF_IOPNMF和SIF_IVT通過準則2，忽略低權(quán)值粒子集，擇取高權(quán)值粒子集估計目標的位置，因而避免了漂移現(xiàn)象。在Liquor(圖5(b))視頻序列中，目標在330幀后出現(xiàn)快速移動、運動模糊和尺度變化等干擾因素，此時IOPNMF、IVT、L1APG和LOT算法皆跟蹤失敗；SIF_IOPNMF和SIF_IVT通過準則6將粒子集進行分離運動，能夠有效地增加粒子多樣性，并根據(jù)最大后驗準則成功地估計了目標的后驗狀態(tài)。在Basketball(圖5(c))視頻序列中，在20幀之后，由于目標出現(xiàn)大幅度遮擋，IOPNMF算法出現(xiàn)了漂移；SIF_IOPNMF通過準則3對高權(quán)值粒子集里的粒子進行局部加權(quán)，有效地處理了遮擋問題。在85幀左右，目標出現(xiàn)快速移動，此時CNT算法跟蹤失敗；在250幀之后，由于目標出現(xiàn)大尺度平面外旋轉(zhuǎn)，此時MTT和L1APG算法皆出現(xiàn)漂移；而在480幀之后，由于目標大尺度的非剛性變形，只有SI_IOPNMF、SI_IVT和LOT算法仍未丟失目標。在David3(圖5(e))視頻序列中，20幀左右時，跟蹤目標出現(xiàn)小幅度遮擋，此時MTT算法跟蹤失??；在110幀后，目標出現(xiàn)大尺度平面內(nèi)旋轉(zhuǎn)，L1APG和ASLA算法皆出現(xiàn)漂移；在200幀左右時，由于出現(xiàn)了背景干擾和大幅度遮擋，IVT和CNT算法皆丟失目標。SIF_IVT通過準則4對中權(quán)值粒子集進行局部加權(quán)計算出中心位置，能夠應對大幅度遮擋導致的局部最優(yōu)化，再對低權(quán)值粒子集進行內(nèi)聚運動，有效地處理了背景干擾問題。SA2c(圖5(d))和EECP1c(圖5(f))兩個視頻序列中，目標皆出現(xiàn)大幅度遮擋和尺度變換，只有SI_IOPNMF、SIF_IVT、CNT和ASLA算法跟蹤效果良好，CNT和ASLA由于利用了局部特征模塊，對遮擋有著良好的魯棒性，而SI_IOPNMF和SIF_IVT則通過結(jié)合內(nèi)聚運動和局部加權(quán)準則，增加了算法的遮擋和尺度變化的適應性。由以上實驗結(jié)果可以看出，在所提取的特征和更新準則不能很好地應對復雜多變的跟蹤環(huán)境時，采用智能群體優(yōu)化濾波算法比采用粒子濾波算法更加適應多變的跟蹤環(huán)境。

圖 5 9種算法在部分視頻集中的實驗結(jié)果截圖Fig. 5 Sampling tracking results of 9 trackers in some sequences

4 結(jié)束語

針對目標跟蹤的運動模型，本文提出了一種智能群體優(yōu)化濾波(SIF)算法。在貝葉斯濾波的基礎(chǔ)上，本文提出的算法融入了智能群體優(yōu)化中的3種智能群體優(yōu)化思想，即內(nèi)聚、分離和排列運動。在當前時刻能夠準確地估計后驗狀態(tài)的情況下，內(nèi)聚運動是將權(quán)值較低的粒子聚合在高權(quán)值粒子周圍，以增加其權(quán)值并保留了粒子多樣性，再結(jié)合排列運動準確地預測下一時刻的先驗狀態(tài)，能夠有效地增加算法對遮擋和形變的適應性。分離運動是在當前時刻無法準確估計后驗狀態(tài)的情況下，通過擴大搜索范圍來增加粒子多樣性，能夠有效處理快速移動和運動模糊導致的粒子權(quán)值退化問題，提高了下一時刻的先驗濾波概率密度。

實驗結(jié)果表明，相比于廣泛使用的粒子濾波算法，智能群體優(yōu)化濾波算法更能準確地估計后驗狀態(tài)，當實際運用在目標跟蹤中，更加有效地應對復雜多變的跟蹤環(huán)境。同時本文提出的算法思想還可以使用在任何基于采樣的跟蹤算法中，因此該算法具有很好的適用性。本文的實驗只將算法應用到了IPONMF算法和IVT算法中，為了進一步提高跟蹤效果，下一步的工作將考慮將智能群體優(yōu)化濾波算法應用到其他的跟蹤算法中。