基于DE蝙蝠算法優(yōu)化粒子濾波的目標跟蹤①

李龍龍,周武能,閭斯瑤

(東華大學 信息科學與技術(shù)學院,上海 201620)

1 引言

目標跟蹤是計算機視覺中的一個重要主題,它具有許多真實世界的應用,包括流量管理[1],機器人定位[2]和人機界面[3].跟蹤系統(tǒng)由兩個主要部分組成: 視覺表示[4]和運動估計[5].在跟蹤的運動估計步驟中,對物體動態(tài)的不確定性或非線性進行建模,以在視頻序列中定位物體.跟蹤方法可以分為兩組,即運動估計的確定性[6]和隨機[7]方法.Meanshift算法是一個確定性的跟蹤器,它利用一個區(qū)域來迭代地最大化相似性度量.該算法可能在遮擋,前景和背景的相似顏色分布以及長視頻序列中漂移[8].相比之下,隨機跟蹤器采用統(tǒng)計來定位目標跟蹤的目標位置.卡爾曼濾波方法是針對線性和高斯觀測噪聲[9]而開發(fā)的,作為一種順序隨機方式,不能用于非線性運動.粒子濾波方法保持了視覺跟蹤中模型評估和分析步驟的非線性和不確定性[10].

但是標準粒子濾波方法(PF)存在權(quán)值退化的問題,標準粒子濾波在利用重采樣方法解決退化現(xiàn)象時,又會產(chǎn)生粒子貧化現(xiàn)象.針對該問題,文獻[11]提出了一種根據(jù)權(quán)值來進行選擇的粒子濾波方法,該算法在粒子群體中選取一些權(quán)值相對較大的粒子用于進行估計下一時刻的狀態(tài),這樣就能在一定程度上減輕粒子的貧化問題程度.文獻[12]提出了一種確定性的重采樣粒子濾波,該粒子濾波方法提出了一種重采樣的確定性優(yōu)化思想,這樣增加了粒子狀態(tài)的多樣性.文獻[13]提出了一種飽和粒子濾波方法,這種方法是按照系統(tǒng)的不同特性挑選出相應比較適合的重采樣方法,使得粒子更加貼近真實狀態(tài).但前面提出來的幾種方法仍然是在傳統(tǒng)重采樣思想的基礎上,并不能從源頭上解決粒子貧化的問題現(xiàn)象.

基于群智能優(yōu)化算法的粒子濾波是現(xiàn)代粒子濾波領域中一個較為新穎的發(fā)展方向[14].因為群智能算法改進粒子濾波主要是對粒子群體的分布狀態(tài)展開迭代并尋優(yōu)[15,16],其中沒有涉及到對權(quán)值較低的粒子進行直接舍棄,所以可以在源頭上來解決掉粒子的貧化現(xiàn)象.

文獻[17]通過融合蜂群算法建立箱式粒子貧化解決策略,結(jié)果較好.文獻[18]通過將粒子群算法和蟻群算法融合在粒子濾波算法中,實現(xiàn)粒子集間的信息共享,增強算法的全局尋優(yōu)能力.文獻[19]通過融合螢火蟲算法優(yōu)化粒子濾波,使用亮度和吸引度動態(tài)優(yōu)化粒子集.

蝙蝠算法(Bat Algorithm,BA)[20]在2010年被劍橋大學Yang教授提出,其實現(xiàn)智能尋優(yōu)的方法是模擬現(xiàn)實世界蝙蝠的捕食行為,類似于粒子群算法,蝙蝠算法同樣是一種基于群體的隨機策略進行搜索來尋優(yōu)的機制,不同點在于蝙蝠算法在隨機性擁有更強的優(yōu)勢.文獻[20]已證明,蝙蝠算法的綜合尋優(yōu)能力優(yōu)于粒子群算法、蟻群算法等主流群智能優(yōu)化算法.

文獻[21]提出的蝙蝠算法優(yōu)化粒子濾波,并驗證該算法優(yōu)于其它智能算法,但是帶來計算效率低下的問題.文獻[22]使用Lévy的飛行路線特征來改進蝙蝠算法優(yōu)化,增強了算法跳出局部極值的能力.文獻[23]使用拉丁正交策略構(gòu)建蝙蝠群位置初始策略,來使得搜索區(qū)間分散均衡,以提升性能.

上述的改進蝙蝠算法的過程中,更多考慮的是算法參數(shù)和初始化策略改進,能夠獲得一定的性能提升.與上述算法的改進策略不同,本文主要針對搜索區(qū)域進行策略調(diào)整.

本文在原有的蝙蝠優(yōu)化算法中加入差分進化算法,以改進算法的搜索能力,并將其用于基于粒子濾波器的目標跟蹤中,在執(zhí)行重采樣之前進行差分進化蝙蝠優(yōu)化搜索,可以避免重采樣本身的粒子貧化現(xiàn)象.

2 基本的粒子濾波算法

在標準的粒子濾波器中,在時間t下,目標狀態(tài)矢量為xt,考慮通過觀測狀態(tài)矢量為zt來找到目標狀態(tài).觀測器從第一幀到第t幀為z1:t.在粒子濾波器中,后驗分布可以使用查普曼-科莫{高洛夫方程的}近似模型來定義,粒子集表示為權(quán)重集為

其中,q是重要性密度函數(shù).前一次的后驗分布是其中δ(·)為一個狄拉克函數(shù),函數(shù)的約束條件是在前一時刻有且1≤i≤N.

3 蝙蝠算法

基于蝙蝠啟發(fā)式的元啟發(fā)式優(yōu)化算法,即蝙蝠算法,由Yang[20]基于蝙蝠的回聲定位的能力提出.在標準的蝙蝠算法中,蝙蝠的回聲定位特征抽象化為如下規(guī)則[20].

(1)蝙蝠種群都通過回聲定位來獲得距離,并使用某種特殊的方法“明白”目標和非目標兩者之間存在的不同特征點;

(2)蝙蝠在位置xi處伴隨著速度vi以一定的速度飛行頻率和響度來搜尋目標.他們可以自動調(diào)節(jié)發(fā)射脈沖的波長(或頻率),并根據(jù)目標的接近程度調(diào)節(jié)脈沖發(fā)射速率.

(3)雖然響度可以按照多種方式變化,但是通常是假設響度從大(正)A0變化到最小設定數(shù)Amin.

但是蝙蝠算法存在后期收斂速度較慢的、收斂精度不高、容易陷入局部最優(yōu)點等不足.本文提出的基于差分蝙蝠算法優(yōu)化粒子濾波(DEBA-PF),將差分算法融合到蝙蝠算法中,使蝙蝠種群個體之間具有變異、交叉、選擇機制,從而達到增加蝙蝠個體的多樣性,提高算法的全局尋優(yōu)能力和局部搜索能力,能夠避免陷入局部最優(yōu)從而得到全局最優(yōu).本文實驗結(jié)果也證明DEBA效果更佳.

4 蝙蝠算法融合差分進化算法DEBA

由于差分進化算法(DE)的有效性和簡單性,而使得差分進化算法獲得很多的關注.差分進化算法(DE)[24]的基本思想在于應用當前種群個體的差異來重組種群進而得到中間種群,然后應用父代個體與子代個體競爭來獲得下一代種群.DEBA算法的步驟如下:

Step 1.初始化DEBA算法各個參數(shù);

Step 2.根據(jù)蝙蝠個體適應度函數(shù)得到各個蝙蝠權(quán)重和初始種群當前最優(yōu)解;

Step 3.模擬蝙蝠種群的全局搜索尋優(yōu)行為,根據(jù)本文中的等式(4)-(6)更新各個蝙蝠個體的對應的位置和速度;

Step 4.模擬蝙蝠個體的局部搜索行為,以及對應生成一個均勻分布的隨機數(shù)rand,如果存在rand＞ri的情況,則下一步將進行式(7);

Step 5.生成另外一個獨立的隨機數(shù),若rand＜且則蝙蝠當前的位置為,否則蝙蝠的當前位置為xnew;

Step 6.對蝙蝠的局部搜索能力進行調(diào)整,利用式(9)更新脈沖頻率和響度;

Step 7.利用差分進化算法以每一個蝙蝠位置為初始點進行變異、交叉、選擇操作,得到新的蝙蝠位置;

Step 8.計算并對比適應度函數(shù)值,更新全局最優(yōu)值;

Step 9.當算法符合設定的精度閾值ε 時,或者迭代次數(shù)達到設定值時,這個時候就停止算法優(yōu)化過程,否則就要進入Step 3.

從上述的DEBA算法步驟可以看到,BA和DEBA不同點在于DEBA在每一次的進化過程中,通過進化之后的蝙蝠個體位置不是緊接著進行下一次的迭代操作,首先是在蝙蝠個體之間進行變異、交叉、選擇操作,獲得新的蝙蝠個體位置后,再進行下一次迭代.在本文的DEBA算法迭代的初期,由于種群中蝙蝠個體的差異較大,因此進行的變異操作可以使得算法擁有更強的全局搜索能力,當過程進入到了迭代的后期,趨于收斂的時候,種群中蝙蝠個體的差異就會變小,結(jié)果也使得算法擁有更強的局部搜索能力.綜合上述,DEBA將DE和BA的各自優(yōu)點結(jié)合在一起,使得DEBA算法同時擁有更強的全局和局部搜索能力,進而克服了BA后期收斂速度較慢的、收斂精度不高、容易陷入局部最優(yōu)點等不足.

5 本文算法目標灰度描述和目標函數(shù)設計

本文選用灰度分布進行目標的描述,建立系統(tǒng)觀測模型.設視頻圖像跟蹤區(qū)域的中心為X=(x,y),區(qū)域尺寸為跟蹤區(qū)域內(nèi)像素位置設為Xi=(xi,yi),因此,執(zhí)行核概率密度估計以執(zhí)行目標的灰度分布描述.假設目標灰度分布被離散化為B個bin區(qū)間,則定義灰度級量化函數(shù)b(Xi):R2→{1,···,B}表明將位置Xi處的像素灰度量化并分配給對應的灰度級bin中,這里B表示灰度的量化等級,由此定義目標的灰度分布為:

其中,δ(·)為Kronecker Delta 函數(shù);跟蹤區(qū)域內(nèi)的像素總數(shù)記為M,k(·)為所采用的高斯核函數(shù).

本文算法設計的目標函數(shù)式如下所表示:

6 DEBA-PF算法設計

6.1 DEBA-PF全局搜索最優(yōu)過程

對于每一個蝙蝠設為i,它的位置和速度定義在一個d維搜索空間中,并且在迭代期間隨后被更新.在迭代g中更新的解決方案和速度是通過使用全局搜索策略來計算的,公式如下:

其中,β∈[0,1]是一個從均勻分布中得到的隨機矢量.x?是 當前發(fā)現(xiàn)的全局最佳解決方案.頻率fmin和fmax的值取決于感興趣問題的域大小.

6.2 DEBA-PF局部搜索最優(yōu)過程

對于局部搜索部分,一旦從當前最佳解決方案中選擇了解決方案,則使用隨機游走模型在局部生成每個蝙蝠的新的解決方案,本文設置的局部搜索方法如下:

若rand＞ri,則

若rand＜ri,則

其中,ε ∈[-1,1]是 一個隨機數(shù),xold是當前最優(yōu)解決方案集中的解決方案,Ag=＜Agi＞ 是所有蝙蝠在迭代g時的平均響度.

6.3 DEBA-PF全局和局部搜索尋優(yōu)調(diào)整過程

通過響度Ai和脈沖率ri的更新以反映如果找到目標,那么蝙蝠就降低響度并增加脈沖率,通過下式計算:

其中,ri0是初始脈沖率,ω是脈沖頻率增加系數(shù),γ是脈沖幅度衰減系數(shù).對于任何0 ＜ω 和γ ＜1,我們有以下:

用差分進化算法以每個蝙蝠位置為初始點進行變異、交叉、選擇,得到新的蝙蝠位置.

變異操作過程: 從蝙蝠種群中隨機選取3個蝙蝠個體:xga(t)、xbg(t)、xgc(t),且 有a≠b≠c≠i,a,b,c∈{1,2,···,N} 中的隨機數(shù).F為縮放因子,F∈[0,2].

交叉操作過程: 交叉操作過程可以增多蝙蝠種群的多樣性,經(jīng)過下式對第g代蝙蝠種群和其變異中間個體進行蝙蝠個體之間的交叉操作.

在上式中,CR∈[0,1]表 示的是交叉概率,rand(1,n)∈[1,2,···,d] 的隨機數(shù),j=1,2,···,d.此交叉操作策略能夠保證(t)中 至少有一個分量是由vgi(t)貢獻.

7 本文算法步驟

Step 1.輸入初始的測試圖像,并設定所要進行跟蹤的目標對象;

Step 2.隨機生成N個蝙蝠個體{xi(0),i=1,···,N}作為算法的初始蝙蝠個體,初始化DEBA-PF算法參數(shù).xi(t)服從重要性密度函數(shù):

Step 3.計算蝙蝠個體的灰度直方圖特征;

Step 4.DEBA算法操作;

Step 5.計算重要性權(quán)值:

Step 6.進行歸一化:

Step 7.根據(jù)蝙蝠權(quán)值大小重采樣,得到N個新樣本;

Step 8.狀態(tài)輸出,對新樣本求平均確定跟蹤點:

上述算法過程充分利用了整個蝙蝠種群的有效信息,幫助蝙蝠個體跳出局部最優(yōu),避免了狀態(tài)值變化不大的情況下還會繼續(xù)進行迭代過程,使得算法終止優(yōu)化,更多地是因為算法達到設定精度停止閾值,從而降低算法直到達到設定的最高迭代次數(shù)才會終止下來的概率,提高算法計算效率.

8 仿真實驗和結(jié)果分析

8.1 性能測試分析

本文選取單變量非靜態(tài)增長模型,實驗測試對象的過程模型和觀測模型如下:

過程模型:

觀測模型:

上述等式中,net(t)和wet(t)為均值為零的高斯噪聲.在本文假定系統(tǒng)噪聲方差Q=1和Q=10,觀測噪聲方差R=10,濾波時間步數(shù)為50,初始化時脈沖響度為A0=0.5 ,初始化脈沖率r0=0.5,fmax=2,fmin=0,使用標準粒子濾波、粒子群優(yōu)化粒子濾波和本文算法差分進化蝙蝠算法優(yōu)化粒子濾波對該非線性系統(tǒng)進行狀態(tài)估計與跟蹤.

在本文算法中所使用的均方根誤差公式:

(1)當蝙蝠數(shù)為N=20、Q=10時,仿真結(jié)果如圖1所示.

(2)當蝙蝠數(shù)為N=50、Q=10時,仿真結(jié)果如圖2所示.

(3)當蝙蝠數(shù)為N=100、Q=10時,仿真結(jié)果如圖3所示.

(4)當蝙蝠數(shù)為N=20、Q=1時,仿真結(jié)果如圖4所示.

(5)當蝙蝠數(shù)為N=50、Q=1時,仿真結(jié)果如圖5所示.

(6)當蝙蝠數(shù)為N=100、Q=1時,仿真結(jié)果如圖6所示.

在下示仿真圖中,用x表示真實點,*表示BA估計點,○表示PF估計點,·表示PSO估計點,☆表示DEBA估計點,分別用實線連接.

圖1 N=20、Q=10時濾波狀態(tài)估計圖和誤差絕對值

圖2 N=50、Q=10時濾波狀態(tài)估計圖和誤差絕對值

從圖1～圖6可以看出,差分進化蝙蝠算法優(yōu)化粒子濾波具有更高的狀態(tài)值預測精度,這是因為差分進化算法優(yōu)化粒子濾波的在粒子濾波的基礎上,模擬蝙蝠個體和種群搜索目標的過程中,可以對全局搜索和局部尋優(yōu)能力進行精確控制,同時融合了差分進化算法使得本文算法能夠較大幅度提高算法的收斂速度、魯棒性和尋優(yōu)能力.

圖3 N=100、Q=10時濾波狀態(tài)估計圖和誤差絕對值

圖4 N=20、Q=1時濾波狀態(tài)估計圖和誤差絕對值

圖6 N=100、Q=1時濾波狀態(tài)估計圖和誤差絕對值

從表1中可以看出,在高噪聲的影響下,差分進化蝙蝠算法粒子數(shù)N=20時精度依然比標準粒子濾波中粒子數(shù)N=100時的精度高,這樣即表明,本文所用的差分進化算法在非線性、高噪聲的環(huán)境會較標準的粒子濾波更好的跟蹤目標.

8.2 目標跟蹤測試

為了測試本研究算法的性能,本文在多個測試視頻上進行了對比實驗,如圖7至圖12所示.

表1 實驗結(jié)果均方根誤差對比

圖7 標準粒子濾波跟蹤結(jié)果1(第50、60、70、80、90、100幀)

圖8 差分進化蝙蝠算法跟蹤結(jié)果1(第50、60、70、80、90、100幀)

圖9 標準粒子濾波算法跟蹤結(jié)果2(第20、30、40、50、60、70幀)

圖10 差分進化蝙蝠算法跟蹤結(jié)果2(第20、30、40、50、60、70幀)

圖11 標準粒子濾波跟蹤結(jié)果3(第50、60、70、80、90、100幀)

圖12 差分進化蝙蝠算法跟蹤結(jié)果3(第50、60、70、80、90、100幀)

從以上實驗結(jié)果可以看到,在非線性下、高斯噪聲環(huán)境下,標準粒子濾波算法跟蹤效果較差,魯棒性能不佳,而本文所采用的差分進化蝙蝠算法在總體上來說具有良好的跟蹤效果和魯棒性.

9 結(jié)語

本文提出了一種基于差分進化蝙蝠算法智能優(yōu)化粒子濾波的目標跟蹤方法,同時具備全局搜索和局部搜索能力,提高跟蹤算法的跟蹤性能.測試視頻圖像的實驗結(jié)果也表明,本文方法在復雜背景下的跟蹤具有較好的魯棒性和準確性.在后面工作中,將對其它信號源圖像的目標跟蹤問題進行深入研究,對跟蹤過程中的模板更新、目標遮擋等問題做進一步優(yōu)化.