信 科

（濱州學(xué)院 信息工程系，濱州256600）

引 言

Mean Shift算法[1]是一種基于密度梯度的無參數(shù)估計方法，是模板匹配跟蹤算法中的一種主流算法，在2003年由Comaniciu D引入到目標(biāo)跟蹤領(lǐng)域，因其收斂速度快、計算量小、實時性好引起了人們的廣泛關(guān)注。它利用圖像中像素建立加權(quán)直方圖作為目標(biāo)特征，具有一定的抗遮擋、抗形變的能力，但對尺度變化目標(biāo)的跟蹤性能不佳。目前的研究多基于軟件仿真[2-4]，對于硬件實現(xiàn)的研究并不多。

目前的實現(xiàn)方法是基于DSP＋FPGA設(shè)計[5]，以DSP為主、FPGA為輔。在參考文獻[5]中，DSP完成算法主流程的計算，F(xiàn)PGA僅負責(zé)算法直方圖統(tǒng)計部分和外圍電路。因為Mean Shift算法基于浮點運算，不利于FPGA編程實現(xiàn)，F(xiàn)PGA＋DSP協(xié)同實現(xiàn)時，系統(tǒng)的處理時間最快達到20 ms左右，無法滿足實時性更高的場合，如幀頻為100 fps的高速信號處理系統(tǒng)。

本文提出一種基于SOPC實現(xiàn)Mean Shift算法的新方法，在單片F(xiàn)PGA上利用SOPC技術(shù)搭建算法的硬件平臺，軟硬件協(xié)同工作實現(xiàn)算法給出了實驗分析和結(jié)論。

1 Mean Shift算法簡介

Mean Shift算法是一種半自動的目標(biāo)跟蹤算法，其跟蹤框圖如圖1所示。在起始幀手動標(biāo)定跟蹤窗的中心和位置，計算得到核函數(shù)加權(quán)的直方圖分布（即目標(biāo)模板）；在當(dāng)前幀保持上一幀的跟蹤位置不變，計算得到候選目標(biāo)模板；以目標(biāo)模板和候選模板的最相似為原則，使目標(biāo)窗口沿偏移矢量（即梯度變化最大的方向）移動，最終定位目標(biāo)的真實位置。

圖1 Mean Shift算法的跟蹤框圖

Mean Shift算法主要包括下面4個計算步驟。

1.1 核函數(shù)k（x）的計算

其中，｛zi｝i＝1...n表示跟蹤窗口內(nèi)的任一像素點（xi，yi），z0表示窗口中心 （xcenter，ycenter）。

1.2 目標(biāo)模型或候選模型的建立

或

其中，沖激函數(shù)δ[b（zi）-u]的作用是判斷b（zi）的灰度值是否屬于第u個量化值，為歸一化常數(shù)以保證所有量化值的概率和為1。

1.3 偏移矢量的權(quán)重

由權(quán)重計算公式可以得出下面的結(jié)論：每個像素點zi對應(yīng)的偏移矢量的權(quán)重，由其對應(yīng)的量化值在目標(biāo)模型和候選模型中的概率決定，與zi的位置無關(guān)。

1.4 偏移矢量

[6]證明了Mean Shift迭代過程對于目標(biāo)跟蹤的應(yīng)用具有空域位置上的收斂性，表示目標(biāo)下一個跟蹤位置相對當(dāng)前跟蹤位置的偏移矢量。

2 改進的Mean Shift目標(biāo)跟蹤算法

由Mean Shift算法的計算步驟可以看出，其采用浮點運算，不利于用FPGA實現(xiàn)。下面主要介紹對各步驟的優(yōu)化。

2.1 核函數(shù)k（x）的優(yōu)化

從核函數(shù)的表達式可以看出，對于位于帶寬內(nèi)的像素點，k（x）與相對距離的平方成反比；帶寬外的像素點，k（x）為0。核函數(shù)計算中涉及浮點數(shù)據(jù)的平方運算，單個時鐘周期內(nèi)不可能完成，因此，進行下面的改進，保證單個時鐘周期能完成計算過程。

因為：

所以有：

由變化后的公式可以看出，對跟蹤窗口的帶寬32等分和對相似距離求近似后，浮點運算變?yōu)檎芜\算。因為k1的取值范圍已知，k21的取值可以事先求得，而1/1024為所有k（x）公因子，可以先不考慮，則在計算過程中只涉及比較和減法運算，F(xiàn)PGA能在單個時鐘周期內(nèi)完成計算。與列積分直方圖加權(quán)類似，在核函數(shù)優(yōu)化過程中采取了近似，使浮點運算變?yōu)檎芜\算。表1給出了使用帶寬不同的核函數(shù)時，近似對匹配度的影響。其中，hx、hy為帶寬，相似系數(shù)表示核函數(shù)分別采用浮點運算和整數(shù)運算求得的兩個加權(quán)直方圖的匹配度?？梢钥闯?，經(jīng)近似后匹配度仍保持在0.999以上。

表1 整形近似后的相似系數(shù)

2.2 模型的優(yōu)化

目標(biāo)模型和候選模型的計算步驟完全一致，在此，以目標(biāo)模型為例進行介紹，候選模型的優(yōu)化與此類似。

目標(biāo)模型的公式為：

可以看到，計算結(jié)果qu是與量化等級u對應(yīng)的函數(shù)，是所有量化等級為u的像素點對應(yīng)的核函數(shù)的和與所有像素點對應(yīng)的核函數(shù)的和的比值。為便于硬件實現(xiàn)，將其分解為兩步進行：第一步，核函數(shù)統(tǒng)計算法核包括近似后的核函數(shù)k（x）、各量化值對應(yīng)的核函數(shù)和qsumu和所有核函數(shù)的和第二步，直方圖歸一化（即將qsumu歸一化），得到核函數(shù)加權(quán)的直方圖。第一步計算過程經(jīng)核函數(shù)變化后只涉及加法運算，第二步計算過程涉及整數(shù)的除法運算。

2.3 偏移矢量的優(yōu)化

由上面的分析可以看出，偏移矢量的計算可以分兩步進行：第一步坐標(biāo)偏移統(tǒng)計核，負責(zé)計算xu、nu，只涉及加法運算；第二步坐標(biāo)偏移和加權(quán)，利用權(quán)重系數(shù)加權(quán)，求得偏移矢量，涉及浮點乘、除運算。與原算法相比，此過程為全等運算，只是改變了運算規(guī)則，并沒有進行近似。

2.4 尺度更新

Mean Shift算法在跟蹤過程中無窗口更新機制，對尺度變化目標(biāo)的跟蹤效果不好。為了適應(yīng)尺度變化目標(biāo)的跟蹤及算法實時性，采用參考文獻[7]中連通域標(biāo)記方法提取目標(biāo)面積，按照參考文獻[8]中所述的方法進行尺度更新。

3 系統(tǒng)的硬件結(jié)構(gòu)及軟件實現(xiàn)

3.1 系統(tǒng)的硬件結(jié)構(gòu)及軟硬件劃分

設(shè)計采用下面的嵌入式平臺實現(xiàn)Mean Shift算法，其硬件結(jié)構(gòu)框圖如圖2所示。

圖2 嵌入式系統(tǒng)的硬件結(jié)構(gòu)框圖

由硬件結(jié)構(gòu)框圖可以看出，整個算法基于單片F(xiàn)PGA，利用SOPC技術(shù)實現(xiàn)，并將跟蹤結(jié)果經(jīng)ADV7213 D/A轉(zhuǎn)換后輸出給監(jiān)視器。利用硬件編程實現(xiàn)核函數(shù)統(tǒng)計算法核、坐標(biāo)偏移統(tǒng)計核和目標(biāo)面積提取算法核；利用軟件編程實現(xiàn)Mean Shift的相關(guān)處理，包括直方圖歸一化、坐標(biāo)偏移和加權(quán)、偏移權(quán)重和迭代判決。硬件部分采用硬件編程語言VHDL并行流水實現(xiàn)，并將計算結(jié)果寫入雙端口RAM中，觸發(fā)CPU進行軟件操作。軟件操作流程圖略——編者注。首先，CPU從雙端口RAM中讀取FPGA的計算結(jié)果，計算目標(biāo)模型或候選模型；其次，CPU計算各量化值對應(yīng)的權(quán)重，同時從雙端口RAM中讀取FPGA統(tǒng)計的各量化值計算結(jié)果，求得目標(biāo)新的中心位置；最后，CPU計算迭代是否滿足終止條件，若滿足條件，則將計算結(jié)果輸出到監(jiān)視器上，并讀取面積結(jié)果更新跟蹤窗的尺度，若不滿足，則將新位置通知FPGA，由FPGA重新統(tǒng)計目標(biāo)區(qū)域的特征并送入CPU重新計算。

3.2 軟件優(yōu)化

在介紹軟件優(yōu)化前，先介紹一下本設(shè)計選用的CPU的基本配置。CPU選用快速的NIOS II/f型處理器，具有6級流水結(jié)構(gòu)，帶指令和數(shù)據(jù)緩存；CPU主時鐘采用100 MHz；CPU開辟的數(shù)據(jù)與指令Cache均為32 KB；構(gòu)建哈佛結(jié)構(gòu)的處理器，程序存儲器和數(shù)據(jù)存儲器分開，程序存儲器和數(shù)據(jù)存儲器均采用片上RAM實現(xiàn)，大小為64 KB。

（1）NIOS II軟件配置的優(yōu)化[9]

減少代碼量：使用裁減后的小封裝驅(qū)動庫，勾選庫屬性中的reduce device drivers選項；使用基本的C語言庫，勾選庫屬性small C library選項。經(jīng)勾選后，軟件代碼由76 KB減少到23 KB。

（2）自定義浮點指令[10]的應(yīng)用

自定義指令是指將復(fù)雜的運算或需要很多時鐘周期才能完成的運算采用獨立的硬件來實現(xiàn)，將這些硬件按一定的接口時序封裝集成到CPU中。系統(tǒng)生成時，將為每條用戶指令產(chǎn)生一個宏，可以在應(yīng)用程序中調(diào)用這個宏代替原來軟件實現(xiàn)部分，使系統(tǒng)的運算能力大大提升。由前面的分析可以看出，Mean Shift運算過程中用到大量的浮點加、減、乘、除和開平方運算，在CPU的Custom Instructions里添加Floating Point Hardware并勾選硬件除法器選項，CPU在實現(xiàn)時自動將浮點加、減、乘、除運算用自定義指令實現(xiàn)。自己編寫浮點開方指令altfp＿sqrt＿top，并添加到Custom Instructions選項中，CPU調(diào)用其對應(yīng)的宏實現(xiàn)浮點開平方運算。各自定義指令的硬件加速情況如表2所列。

4 試驗與分析

系統(tǒng)硬件平臺的核心為FPGA，選取Altera公司的FP2S180F1020I4，實驗中采用的紅外視頻圖像分辨率為352×288。

表2 浮點自定義指令的硬件加速比

4.1 尺度變化目標(biāo)實驗

實驗以天空中的飛機視頻序列為測試對象，測試算法對目標(biāo)尺度變化、旋轉(zhuǎn)狀態(tài)下的跟蹤能力。跟蹤序列在第15幀、115幀和215幀的跟蹤圖像略——編者注。在目標(biāo)發(fā)生較大尺度變化和旋轉(zhuǎn)時仍能準(zhǔn)確的跟蹤目標(biāo)。

分別應(yīng)用本文提出的兩條優(yōu)化措施對算法進行優(yōu)化加速，其優(yōu)化效果如表3所列。

表3 算法的優(yōu)化效果

跟蹤飛機視頻序列的處理時間如圖3所示，實驗中，目標(biāo)尺度從15×10逐漸增大到90×60，其平均計算時間為3.42 ms，最大處理時間小于4 ms，可滿足對大部分紅外視頻序列的實時跟蹤。

圖3 嵌入式系統(tǒng)的處理時間

4.2 算法處理時間對比

應(yīng)用本文提出的方法和參考文獻[5]中采用FPGA＋DSP實現(xiàn)方法對比，可以看出，參考文獻[5]中改進的方法隨著目標(biāo)尺度變化，處理時間迅速增加；而本文方法處理的跟蹤時間，受目標(biāo)尺度變化的影響很小。這是因為通過軟硬件劃分后，軟件的處理時間不受目標(biāo)尺度的影響，硬件處理時間與目標(biāo)尺度成線性關(guān)系，但因為采用流水并行實現(xiàn)，所以處理時間的增加很少。算法的不同實現(xiàn)方式處理時間的對比如表4所列。

表4 算法的不同實現(xiàn)方式處理時間的對比

結(jié) 語

本文利用SOPC原理對均值漂移算法進行軟硬件劃分，降低了算法實現(xiàn)的復(fù)雜度，使其適合在FPGA上實現(xiàn)；又結(jié)合FPGA的硬件特點，提出了實時整數(shù)運算核，并行流水提取相應(yīng)的目標(biāo)信息；最后，結(jié)合NIOS II CPU的特點，對軟件實現(xiàn)部分進行優(yōu)化，提高算法的執(zhí)行效率。實驗結(jié)果表明，該系統(tǒng)實時性強，能在4 ms內(nèi)完成對目標(biāo)的跟蹤，對目標(biāo)的尺度變化具有自適應(yīng)性。

編者注：本文為期刊縮略版，全文見本刊網(wǎng)站www.mesnet.com.cn。

參考文獻

[1]Comaniciu D，Ramesh V，Meer P.Kernel-based object tracking[J].IEEE Trans.on Pattern Analysis and Machine Intelligence，2003，25（5）：564-577.

[2]Anbang Yao，Guijin Wang，Xinggang Lin，et al.An incremental Bhattacharyya dissimilarity measure for particle filtering[J].Pattern Recognition，2010，43（4）：1244-1256.

[3]R Venkatesh Babu，S Suresh，Anamitra Makur.Online adaptive radial basis function networks for robust object tracking[J].Computer Vision and Image Understanding，2010（3）：297-310.

[4]Leichter Ido，Lindenbaum Michael，Rivlin Ehud.Mean Shift tracking with multiple reference color histograms[J].Computer Vision and Image Understanding，2010（3）：400-408.

[5]孫航，韓紅霞，郭勁，等.基于均值偏移快速算法的紅外目標(biāo)跟蹤[J].儀器儀表學(xué)報，2012，33（5）：1122-1127.

[6]Comaniciu D.Nonparametric robust methods for computer vision[D].New Jersey：The State University of New Jersey，2000.

[7]Liu Qing，Tang Linbo，Zhao Baojun，et al.A fast target tracking algorithm basted on connected component labeling and grey value statistics[C]//ICCASM，2012：1267-1270.

[8]劉晴，唐林波，趙保軍.跟蹤窗自適應(yīng)的Mean Shift目標(biāo)跟蹤算法[J].系統(tǒng)工程與電子技術(shù)，2012，34（2）：409-412.

[9]葉有時，趙保軍，唐林波，等.多目標(biāo)實時跟蹤可編程片上系統(tǒng)的軟件優(yōu)化[J].光學(xué)精密工程，2011，19（3）：681-689.

[10]Altera.Embedded Design Handbook，2010.