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

李龍龍,周武能,閭斯瑤

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

1 引言

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

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

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

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

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

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

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

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

2 基本的粒子濾波算法

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

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

3 蝙蝠算法

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

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

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

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

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

4 蝙蝠算法融合差分進(jìn)化算法DEBA

由于差分進(jìn)化算法(DE)的有效性和簡(jiǎn)單性,而使得差分進(jìn)化算法獲得很多的關(guān)注.差分進(jìn)化算法(DE)[24]的基本思想在于應(yīng)用當(dāng)前種群個(gè)體的差異來(lái)重組種群進(jìn)而得到中間種群,然后應(yīng)用父代個(gè)體與子代個(gè)體競(jìng)爭(zhēng)來(lái)獲得下一代種群.DEBA算法的步驟如下:

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

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

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

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

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

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

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

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

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

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

5 本文算法目標(biāo)灰度描述和目標(biāo)函數(shù)設(shè)計(jì)

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

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

本文算法設(shè)計(jì)的目標(biāo)函數(shù)式如下所表示:

6 DEBA-PF算法設(shè)計(jì)

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

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

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

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

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

若rand＞ri,則

若rand＜ri,則

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

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

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

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

用差分進(jìn)化算法以每個(gè)蝙蝠位置為初始點(diǎn)進(jìn)行變異、交叉、選擇,得到新的蝙蝠位置.

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

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

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

7 本文算法步驟

Step 1.輸入初始的測(cè)試圖像,并設(shè)定所要進(jìn)行跟蹤的目標(biāo)對(duì)象;

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

Step 3.計(jì)算蝙蝠個(gè)體的灰度直方圖特征;

Step 4.DEBA算法操作;

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

Step 6.進(jìn)行歸一化:

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

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

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

8 仿真實(shí)驗(yàn)和結(jié)果分析

8.1 性能測(cè)試分析

本文選取單變量非靜態(tài)增長(zhǎng)模型,實(shí)驗(yàn)測(cè)試對(duì)象的過(guò)程模型和觀測(cè)模型如下:

過(guò)程模型:

觀測(cè)模型:

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

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

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

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

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

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

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

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

在下示仿真圖中,用x表示真實(shí)點(diǎn),*表示BA估計(jì)點(diǎn),○表示PF估計(jì)點(diǎn),·表示PSO估計(jì)點(diǎn),☆表示DEBA估計(jì)點(diǎn),分別用實(shí)線連接.

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

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

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

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

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

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

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

8.2 目標(biāo)跟蹤測(cè)試

為了測(cè)試本研究算法的性能,本文在多個(gè)測(cè)試視頻上進(jìn)行了對(duì)比實(shí)驗(yàn),如圖7至圖12所示.

表1 實(shí)驗(yàn)結(jié)果均方根誤差對(duì)比

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

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

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

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

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

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

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

9 結(jié)語(yǔ)

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