在SOPC上實(shí)現(xiàn)Mean Shift的改進(jìn)算法※＊

信 科

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

引 言

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

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

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

1 Mean Shift算法簡(jiǎn)介

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

圖1 Mean Shift算法的跟蹤框圖

Mean Shift算法主要包括下面4個(gè)計(jì)算步驟。

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

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

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

或

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

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

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

1.4 偏移矢量

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

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

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

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

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

因?yàn)椋?/p>

所以有：

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

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

2.2 模型的優(yōu)化

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

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

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

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

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

2.4 尺度更新

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

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

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

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

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

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

3.2 軟件優(yōu)化

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

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

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

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

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

4 試驗(yàn)與分析

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

表2 浮點(diǎn)自定義指令的硬件加速比

4.1 尺度變化目標(biāo)實(shí)驗(yàn)

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

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

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

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

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

4.2 算法處理時(shí)間對(duì)比

應(yīng)用本文提出的方法和參考文獻(xiàn)[5]中采用FPGA＋DSP實(shí)現(xiàn)方法對(duì)比，可以看出，參考文獻(xiàn)[5]中改進(jìn)的方法隨著目標(biāo)尺度變化，處理時(shí)間迅速增加；而本文方法處理的跟蹤時(shí)間，受目標(biāo)尺度變化的影響很小。這是因?yàn)橥ㄟ^(guò)軟硬件劃分后，軟件的處理時(shí)間不受目標(biāo)尺度的影響，硬件處理時(shí)間與目標(biāo)尺度成線性關(guān)系，但因?yàn)椴捎昧魉⑿袑?shí)現(xiàn)，所以處理時(shí)間的增加很少。算法的不同實(shí)現(xiàn)方式處理時(shí)間的對(duì)比如表4所列。

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

結(jié) 語(yǔ)

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

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

參考文獻(xiàn)

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

[10]Altera.Embedded Design Handbook，2010.