基于均值漂移的快速模板匹配算法

段亮弟, 宋平, 陳眾, 趙鵬

(63870部隊(duì), 陜西 華陰 714200)

目標(biāo)跟蹤是計(jì)算機(jī)視覺的一個(gè)重要分支,其在軍事偵察、精確制導(dǎo)、火力打擊、戰(zhàn)場評(píng)估以及安防監(jiān)控等諸多方面均有廣泛的應(yīng)用前景。目標(biāo)的不定向運(yùn)動(dòng)改變了目標(biāo)和場景的外觀模式、非剛性目標(biāo)結(jié)構(gòu),目標(biāo)間及目標(biāo)與場景間的遮擋、攝像機(jī)的運(yùn)動(dòng)等情況使目標(biāo)跟蹤任務(wù)變得更加困難。

跟蹤單目標(biāo)最常用的方法是模板匹配方法,它一直以算法簡單、易于實(shí)現(xiàn)等優(yōu)點(diǎn)被廣泛應(yīng)用于光電吊艙的目標(biāo)跟蹤器中。但模板匹配算法是一種窮盡搜索,當(dāng)目標(biāo)運(yùn)動(dòng)過快時(shí),需要加大搜索波門,模板匹配的計(jì)算量會(huì)成倍增加,對(duì)工程應(yīng)用來說實(shí)時(shí)性難以保證;另外,模板匹配算法對(duì)目標(biāo)形變敏感,當(dāng)目標(biāo)發(fā)生旋轉(zhuǎn)、變形等姿態(tài)變化時(shí),目標(biāo)特征受到很大影響,會(huì)發(fā)生中心點(diǎn)漂移現(xiàn)象,導(dǎo)致跟蹤不準(zhǔn)確。為此,可以采用對(duì)旋轉(zhuǎn)、變形不敏感的均值漂移算法進(jìn)行目標(biāo)跟蹤。Comaniciu等提出的均值漂移算法是一種非參數(shù)估計(jì)方法,采用顏色特征和核函數(shù)直方圖進(jìn)行建模和匹配,具有特征穩(wěn)定、計(jì)算速度快和跟蹤效果好等諸多優(yōu)勢,但是以顏色為特征的均值漂移算法在光照、顏色變化及有相似顏色干擾時(shí),跟蹤結(jié)果往往會(huì)出現(xiàn)偏差,甚至丟失目標(biāo)。

為了適應(yīng)環(huán)境變化,提高跟蹤算法的魯棒性,本文聯(lián)合顏色和邊緣2個(gè)特征,在模板匹配算法之前加入均值漂移算法來預(yù)測目標(biāo)位置,縮小整幅圖像上目標(biāo)檢測的搜索范圍,滿足目標(biāo)跟蹤的實(shí)時(shí)性;最后采用快速模板匹配算法尋找最佳匹配位置,以及利用模板匹配結(jié)果自適應(yīng)地更新目標(biāo)模板。仿真實(shí)驗(yàn)結(jié)果表明,算法能夠隨著目標(biāo)位置的變化自動(dòng)調(diào)整目標(biāo)模板,進(jìn)行穩(wěn)定和實(shí)時(shí)的跟蹤,當(dāng)目標(biāo)被物體遮擋時(shí)仍能有效地跟蹤目標(biāo)。

1 均值漂移預(yù)測算法

均值漂移[1]算法是一種基于核密度直方圖的非參數(shù)估計(jì)方法,漂移向量(迭代向量)即密度梯度上升方向。算法通過確定目標(biāo)模型,再選擇候選模型計(jì)算其與目標(biāo)模型的相似度以及下一次的迭代坐標(biāo),并在最大迭代次數(shù)內(nèi)進(jìn)行迭代運(yùn)算,直到目標(biāo)模型和候選目標(biāo)模型的相似度滿足一定條件時(shí)(大于設(shè)定閾值)停止迭代。算法經(jīng)過不斷的迭代運(yùn)算得到的坐標(biāo)點(diǎn)即是算法最終確定的當(dāng)前目標(biāo)中心點(diǎn)。

利用傳統(tǒng)的均值漂移算法,在建立目標(biāo)模型區(qū)域的加權(quán)直方圖時(shí),被跟蹤目標(biāo)圖像像素與背景圖像像素都會(huì)對(duì)目標(biāo)直方圖的分布產(chǎn)生影響。當(dāng)目標(biāo)模型區(qū)域中包含的背景區(qū)域像素較少時(shí),傳統(tǒng)的均值漂移算法可以得到較好的跟蹤效果,但在目標(biāo)模型區(qū)域中包含背景圖像像素較多或者背景不斷變化的情況下,容易造成候選區(qū)域直方圖與目標(biāo)模型區(qū)域直方圖的最佳匹配位置有所偏差,尤其對(duì)于快速運(yùn)動(dòng)目標(biāo)的跟蹤,容易導(dǎo)致目標(biāo)丟失[2-4]。

為減少背景像素對(duì)目標(biāo)預(yù)測產(chǎn)生的影響,本文對(duì)目標(biāo)模型采用背景加權(quán)的方法[5]。如果某特征值在背景模型直方圖中所占權(quán)值較大,在建立目標(biāo)模型時(shí)對(duì)此特征值賦予較小權(quán)重,相反如果某特征值在背景直方圖中所占權(quán)值較小,則在建立目標(biāo)模型時(shí)對(duì)此特征值賦予較大權(quán)重。利用此方法可以有效抑制背景像素對(duì)目標(biāo)跟蹤產(chǎn)生的影響,實(shí)現(xiàn)對(duì)均值漂移預(yù)測算法準(zhǔn)確性的有效改進(jìn),具體實(shí)現(xiàn)方法如下所示。

1.1 計(jì)算背景區(qū)域直方圖

首先計(jì)算目標(biāo)模型以外一定區(qū)域的背景模型直方圖,如(1)式所示

(1)

(2)

1.2 計(jì)算背景加權(quán)系數(shù)

通過ou可以計(jì)算得到背景加權(quán)系數(shù)λu(u=1,…,m),如(3)式所示

(3)

式中,omin是ou中最小的非零值。

1.3 計(jì)算背景加權(quán)后的目標(biāo)模型和候選目標(biāo)模型

定義被跟蹤目標(biāo)為“目標(biāo)模型”,在得到背景加權(quán)系數(shù)vu后,即可計(jì)算背景加權(quán)后的目標(biāo)模型。首先需要對(duì)目標(biāo)模型進(jìn)行描述,確定被跟蹤目標(biāo)模型的特征空間并計(jì)算該區(qū)域的加權(quán)直方圖,通過n級(jí)核加權(quán)直方圖來表示目標(biāo)模型的特征分布,如(4)式所示

(4)

(5)

目標(biāo)模型建立后,運(yùn)動(dòng)目標(biāo)在第2幀和以后每幀中可能包含目標(biāo)的區(qū)域稱為候選目標(biāo)區(qū)域。令yi(i=1,…,n)表示像素在候選目標(biāo)區(qū)域中的位置,其中心位置設(shè)為y0,與(4)式相似,以y0為中心的候選目標(biāo)模型可表示成pu(y),如(6)式所示

(6)

1.4 相似性度量

在利用均值漂移算法預(yù)測運(yùn)動(dòng)目標(biāo)位置時(shí),需要相似性函數(shù)度量目標(biāo)模型和候選模型的匹配程度,即pu(y)與qu的相似程度。本文使用Bhattacharyya系數(shù)作為相似性函數(shù),如(7)式所示

(7)

Bhattacharyya系數(shù)的值在0～1之間。ρ′(y)越大,表示候選目標(biāo)與模板目標(biāo)越匹配,那么對(duì)應(yīng)的中心y越有可能是被跟蹤目標(biāo)在當(dāng)前幀圖像中的位置,目標(biāo)預(yù)測的過程即是尋找最優(yōu)的y,使得Bhattacharyya系數(shù)最大。

1.5 預(yù)測位置定位

均值漂移算法目標(biāo)預(yù)測的過程是利用計(jì)算得到的均值向量反復(fù)迭代,不斷更新核函數(shù)窗口的中心位置,直到滿足判斷條件,算法主要分為以下幾個(gè)步驟:

1) 計(jì)算當(dāng)前窗口內(nèi)各像素點(diǎn)的權(quán)重

(8)

2) 計(jì)算候選目標(biāo)的下一個(gè)新位置

(9)

式中,g(x)=-k′(x)。

3) 判斷是否需要繼續(xù)計(jì)算

首先判斷是否‖yi-y0‖<ε,如不等式成立,則停止計(jì)算,得到被預(yù)測目標(biāo)的位置信息,否則將yi替y0返回到目標(biāo)預(yù)測定位過程的第一步,繼續(xù)尋找滿足判斷條件的候選目標(biāo)位置。由于光電跟蹤系統(tǒng)對(duì)實(shí)時(shí)性具有較高的要求,所以實(shí)際應(yīng)用中設(shè)定迭代次數(shù)最多是15次。

2 快速模板匹配算法

模板匹配是一種原理簡單的跟蹤算法,我們要把跟蹤的目標(biāo)保存好,稱為目標(biāo)模板,然后在每一幀到來時(shí),按照某個(gè)指定的判定準(zhǔn)則將目標(biāo)模板和搜索區(qū)域內(nèi)的每一個(gè)目標(biāo)模板規(guī)模大小的圖像作相似性比較,相似性最大的位置視為模板在搜索窗內(nèi)的正確匹配點(diǎn)。

傳統(tǒng)的模板匹配算法雖然原理簡單,但是計(jì)算量大,從跟蹤器工程應(yīng)用的實(shí)時(shí)性考慮,本文采用一種改進(jìn)的快速模板匹配機(jī)制。在模板匹配階段,結(jié)合上一節(jié)提到的均值漂移算法預(yù)測的目標(biāo)位置生成搜索窗口的邊緣圖像,將目標(biāo)的邊緣模板與搜索窗口的邊緣圖像進(jìn)行由粗到精的快速匹配,并找出最大匹配系數(shù)所在的位置對(duì)目標(biāo)進(jìn)行定位,再由模板匹配的輸出結(jié)果控制更新過程以更新目標(biāo)的邊緣模板,最終完成對(duì)目標(biāo)的快速穩(wěn)定跟蹤。

如果只使用邊緣特征本身在搜索波門內(nèi)進(jìn)行快速匹配跟蹤,在目標(biāo)運(yùn)動(dòng)速度快的情況下需要很大的搜索窗,從而加大了計(jì)算量,并容易受局部極點(diǎn)干擾,若首先使用均值漂移方法預(yù)測目標(biāo)位置,然后在預(yù)測位置區(qū)域很小范圍內(nèi)使用邊緣特征進(jìn)行快速模板匹配,可有效提高模板匹配的效率。

3 基于均值漂移預(yù)測的快速模板匹配目標(biāo)跟蹤方案設(shè)計(jì)

3.1 算法流程

本文聯(lián)合顏色和邊緣2個(gè)特征,結(jié)合2種跟蹤算法的優(yōu)缺點(diǎn),形成一種組合的跟蹤策略,在模板匹配算法之前加入均值漂移算法來預(yù)測目標(biāo)位置。假設(shè)在第(k-1)幀跟蹤得到的目標(biāo)位置為(x(k-1),y(k-1)),且經(jīng)過更新后的目標(biāo)模板為Tk,那么在第k幀圖像輸入后,算法需要在該幀中對(duì)目標(biāo)進(jìn)行跟蹤,具體步驟如下:

1) 人工指示目標(biāo)的方式得到目標(biāo)初始位置,并根據(jù)實(shí)際場景設(shè)定轉(zhuǎn)換閾值ε。

2) 根據(jù)初始位置建立初始目標(biāo)核直方圖模型、初始背景核直方圖模型和初始搜索窗口,獲取目標(biāo)的邊緣模板T0。

3) 第2幀結(jié)合第(k-1)幀跟蹤得到的目標(biāo)位置,利用均值漂移算法預(yù)測當(dāng)前幀圖像中目標(biāo)的可能位置,并以預(yù)測位置中心定義搜索圖像S(k)。

4) 開始快速模板匹配,模板Tk在搜索圖像S(k)的邊緣圖像上平移，將模板Tk與待搜索子圖進(jìn)行由粗到精的匹配,計(jì)算最大互相關(guān)系數(shù)R1,如果匹配度R1大于閾值ε,則將匹配的結(jié)果作為第k幀圖像的跟蹤結(jié)果,否則,以均值漂移算法預(yù)測的目標(biāo)位置作為第k幀圖像的跟蹤結(jié)果。

5) 根據(jù)快速模板匹配的輸出結(jié)果對(duì)目標(biāo)模板和目標(biāo)核直方圖模型以及背景核直方圖模型進(jìn)行更新,至此,第k幀的跟蹤結(jié)束。

整個(gè)算法流程圖見圖1。

3.2 算法實(shí)現(xiàn)

在實(shí)際跟蹤系統(tǒng)中,由于對(duì)圖像處理的實(shí)時(shí)性要求很高,因此均值漂移預(yù)測可以在FPGA中實(shí)現(xiàn),當(dāng)FPGA預(yù)測完當(dāng)前幀的目標(biāo)位置后,通過中斷觸發(fā)的方式把預(yù)測目標(biāo)位置的坐標(biāo)值傳送給DSP,由DSP完成快速模板匹配。實(shí)現(xiàn),當(dāng)FPGA預(yù)測完當(dāng)前幀的目標(biāo)位置后,通過中斷觸發(fā)的方式把預(yù)測目標(biāo)位置的坐標(biāo)值傳送給DSP,由DSP完成快速模板匹配。

圖1 基于均值漂移預(yù)測的快速模板匹配算法流程圖

4 實(shí)驗(yàn)結(jié)果與分析

為驗(yàn)證本文方法的效果,需要進(jìn)行目標(biāo)跟蹤實(shí)驗(yàn),測試3種跟蹤算法的跟蹤效果。采用VS2010軟件編寫了實(shí)驗(yàn)程序,為了驗(yàn)證均值漂移算法對(duì)顏色特征的魯棒性,本文采用2組彩色圖片序列來測試3種跟蹤算法的效果,如圖2所示。圖3是均值漂移算法跟蹤結(jié)果,圖4是快速模板匹配算法跟蹤結(jié)果,圖5是基于均值漂移預(yù)測的快速模板匹配算法跟蹤結(jié)果。

圖2 輸入圖像

圖4 快速模板匹配算法跟蹤結(jié)果

圖5 基于均值漂移預(yù)測的快速模板匹配算法跟蹤結(jié)果

從上圖可以看出,對(duì)于basketball圖像序列,從圖3、圖5可直觀看出,均值漂移算法和基于均值漂移預(yù)測的快速模板匹配算法跟蹤效果較好,在每幀圖像內(nèi)都能穩(wěn)定跟蹤到目標(biāo)人物(綠色球衣運(yùn)動(dòng)員),特別是在遇到遮擋時(shí)(2位穿白色球衣運(yùn)動(dòng)員)依然能保持穩(wěn)定跟蹤,抗遮擋能力較好,而從圖4可看出,利用快速模板匹配算法跟蹤時(shí)在第11幀圖像中由于目標(biāo)人物(綠色球衣運(yùn)動(dòng)員)受到2位白色球衣運(yùn)動(dòng)員的干擾和遮擋,在第15幀出現(xiàn)錯(cuò)誤跟蹤現(xiàn)象,一直到第70幀始終處于目標(biāo)丟失狀態(tài),不能重新捕獲到目標(biāo),故可知快速模板匹配算法的抗遮擋能力較差;對(duì)于people圖片序列,目標(biāo)人物的大小和姿態(tài)一直在不斷變化,背景圖像也在緩慢變化,快速模板匹配算法在第177幀發(fā)生跟蹤丟失現(xiàn)象,之后一直處于丟失狀態(tài),相比起來,均值漂移算法和基于均值漂移預(yù)測的快速模板匹配算法則有較好的表現(xiàn),能穩(wěn)定跟蹤目標(biāo)人物,說明均值漂移算法對(duì)目標(biāo)的形狀和姿態(tài)變化具有較好的魯棒性。

表1是對(duì)這2組圖片序列的跟蹤效果統(tǒng)計(jì),從該表可以看出,對(duì)于這2組圖片序列,本文提出的基于均值漂移預(yù)測的快速模板匹配算法跟蹤效果最好。在快速模板匹配算法之前加入均值漂移算法對(duì)目標(biāo)位置進(jìn)行預(yù)測,既能保證搜索波門的合理性和可預(yù)測性,又能避免在目標(biāo)受到遮擋時(shí)因快速模板匹配算法的失效而導(dǎo)致跟蹤丟失現(xiàn)象的發(fā)生,此時(shí)可將均值漂移算法預(yù)測的目標(biāo)位置作為當(dāng)前幀的跟蹤結(jié)果,保證在下一幀圖像到來時(shí)能穩(wěn)定跟蹤目標(biāo)。

表1 3種跟蹤算法跟蹤效果比較

表2 3種跟蹤算法平均運(yùn)行時(shí)間比較 ms

表2是對(duì)3種跟蹤算法在VS2010上的平均運(yùn)行時(shí)間比較,從該表可以看出,在時(shí)間性能上,快速模板匹配算法耗時(shí)最多,均值漂移算法運(yùn)行時(shí)間最短,改進(jìn)算法雖然是前2種算法的組合,實(shí)時(shí)性卻比快速模板匹配算法要好,因?yàn)楦倪M(jìn)算法增加了預(yù)測機(jī)制,搜索波門比快速模板匹配算法的搜索波門小,故改進(jìn)算法滿足實(shí)時(shí)性要求,后期可將均值漂移預(yù)測算法放在并行性較高的FPGA中去做,以緩解DSP的計(jì)算壓力。

5 結(jié) 論

給出了均值漂移方法和快速模板匹配跟蹤算法的原理,針對(duì)均值漂移和模板匹配算法各自的優(yōu)缺點(diǎn)將兩者很好地結(jié)合在一起,提出了一種基于顏色和邊緣特征的目標(biāo)跟蹤算法。實(shí)驗(yàn)驗(yàn)證結(jié)果表明:所提算法在目標(biāo)無遮擋時(shí),采用均值漂移算法對(duì)目標(biāo)位置進(jìn)行預(yù)測以提供較可靠的搜索區(qū)域,繼而通過模板匹配方法對(duì)目標(biāo)進(jìn)行快速定位和跟蹤;在目標(biāo)發(fā)生遮擋時(shí)使用均值漂移算法對(duì)目標(biāo)在下一幀中的位置進(jìn)行預(yù)測,能夠?qū)δ繕?biāo)進(jìn)行穩(wěn)定跟蹤。

與只使用單一顏色特征的均值漂移跟蹤算法或單一邊緣特征的快速模板匹配跟蹤算法比較,本文算法綜合了顏色特征對(duì)旋轉(zhuǎn)、變形不敏感的優(yōu)點(diǎn)和邊緣特征對(duì)光照、顏色變化不敏感的優(yōu)點(diǎn)。從直觀跟蹤效果和跟蹤誤差定量分析兩方面可以看出,本文算法能夠在光照變化以及目標(biāo)發(fā)生旋轉(zhuǎn)、變形條件下實(shí)現(xiàn)穩(wěn)定跟蹤,提高了模板匹配算法的魯棒性。