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

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

(63870部隊, 陜西 華陰 714200)

目標跟蹤是計算機視覺的一個重要分支,其在軍事偵察、精確制導、火力打擊、戰場評估以及安防監控等諸多方面均有廣泛的應用前景。目標的不定向運動改變了目標和場景的外觀模式、非剛性目標結構,目標間及目標與場景間的遮擋、攝像機的運動等情況使目標跟蹤任務變得更加困難。

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

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

1 均值漂移預測算法

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

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

為減少背景像素對目標預測產生的影響,本文對目標模型采用背景加權的方法[5]。如果某特征值在背景模型直方圖中所占權值較大,在建立目標模型時對此特征值賦予較小權重,相反如果某特征值在背景直方圖中所占權值較小,則在建立目標模型時對此特征值賦予較大權重。利用此方法可以有效抑制背景像素對目標跟蹤產生的影響,實現對均值漂移預測算法準確性的有效改進,具體實現方法如下所示。

1.1 計算背景區域直方圖

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

(1)

(2)

1.2 計算背景加權系數

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

(3)

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

1.3 計算背景加權后的目標模型和候選目標模型

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

(4)

(5)

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

(6)

1.4 相似性度量

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

(7)

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

1.5 預測位置定位

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

1) 計算當前窗口內各像素點的權重

(8)

2) 計算候選目標的下一個新位置

(9)

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

3) 判斷是否需要繼續計算

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

2 快速模板匹配算法

模板匹配是一種原理簡單的跟蹤算法,我們要把跟蹤的目標保存好,稱為目標模板,然后在每一幀到來時,按照某個指定的判定準則將目標模板和搜索區域內的每一個目標模板規模大小的圖像作相似性比較,相似性最大的位置視為模板在搜索窗內的正確匹配點。

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

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

3 基于均值漂移預測的快速模板匹配目標跟蹤方案設計

3.1 算法流程

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

1) 人工指示目標的方式得到目標初始位置,并根據實際場景設定轉換閾值ε。

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

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

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

5) 根據快速模板匹配的輸出結果對目標模板和目標核直方圖模型以及背景核直方圖模型進行更新,至此,第k幀的跟蹤結束。

整個算法流程圖見圖1。

3.2 算法實現

在實際跟蹤系統中,由于對圖像處理的實時性要求很高,因此均值漂移預測可以在FPGA中實現,當FPGA預測完當前幀的目標位置后,通過中斷觸發的方式把預測目標位置的坐標值傳送給DSP,由DSP完成快速模板匹配。實現,當FPGA預測完當前幀的目標位置后,通過中斷觸發的方式把預測目標位置的坐標值傳送給DSP,由DSP完成快速模板匹配。

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

4 實驗結果與分析

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

圖2 輸入圖像

圖4 快速模板匹配算法跟蹤結果

圖5 基于均值漂移預測的快速模板匹配算法跟蹤結果

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

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

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

表2 3種跟蹤算法平均運行時間比較 ms

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

5 結 論

給出了均值漂移方法和快速模板匹配跟蹤算法的原理,針對均值漂移和模板匹配算法各自的優缺點將兩者很好地結合在一起,提出了一種基于顏色和邊緣特征的目標跟蹤算法。實驗驗證結果表明:所提算法在目標無遮擋時,采用均值漂移算法對目標位置進行預測以提供較可靠的搜索區域,繼而通過模板匹配方法對目標進行快速定位和跟蹤;在目標發生遮擋時使用均值漂移算法對目標在下一幀中的位置進行預測,能夠對目標進行穩定跟蹤。

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