在SOPC上實現Mean Shift的改進算法※＊

信 科

（濱州學院 信息工程系，濱州256600）

引 言

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

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

本文提出一種基于SOPC實現Mean Shift算法的新方法，在單片FPGA上利用SOPC技術搭建算法的硬件平臺，軟硬件協同工作實現算法給出了實驗分析和結論。

1 Mean Shift算法簡介

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

圖1 Mean Shift算法的跟蹤框圖

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

1.1 核函數k（x）的計算

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

1.2 目標模型或候選模型的建立

或

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

1.3 偏移矢量的權重

由權重計算公式可以得出下面的結論：每個像素點zi對應的偏移矢量的權重，由其對應的量化值在目標模型和候選模型中的概率決定，與zi的位置無關。

1.4 偏移矢量

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

2 改進的Mean Shift目標跟蹤算法

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

2.1 核函數k（x）的優化

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

因為：

所以有：

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

表1 整形近似后的相似系數

2.2 模型的優化

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

目標模型的公式為：

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

2.3 偏移矢量的優化

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

2.4 尺度更新

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

3 系統的硬件結構及軟件實現

3.1 系統的硬件結構及軟硬件劃分

設計采用下面的嵌入式平臺實現Mean Shift算法，其硬件結構框圖如圖2所示。

圖2 嵌入式系統的硬件結構框圖

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

3.2 軟件優化

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

（1）NIOS II軟件配置的優化[9]

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

（2）自定義浮點指令[10]的應用

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

4 試驗與分析

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

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

4.1 尺度變化目標實驗

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

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

表3 算法的優化效果

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

圖3 嵌入式系統的處理時間

4.2 算法處理時間對比

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

表4 算法的不同實現方式處理時間的對比

結 語

本文利用SOPC原理對均值漂移算法進行軟硬件劃分，降低了算法實現的復雜度，使其適合在FPGA上實現；又結合FPGA的硬件特點，提出了實時整數運算核，并行流水提取相應的目標信息；最后，結合NIOS II CPU的特點，對軟件實現部分進行優化，提高算法的執行效率。實驗結果表明，該系統實時性強，能在4 ms內完成對目標的跟蹤，對目標的尺度變化具有自適應性。

編者注：本文為期刊縮略版，全文見本刊網站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]孫航，韓紅霞，郭勁，等.基于均值偏移快速算法的紅外目標跟蹤[J].儀器儀表學報，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]劉晴，唐林波，趙保軍.跟蹤窗自適應的Mean Shift目標跟蹤算法[J].系統工程與電子技術，2012，34（2）：409-412.

[9]葉有時，趙保軍，唐林波，等.多目標實時跟蹤可編程片上系統的軟件優化[J].光學精密工程，2011，19（3）：681-689.

[10]Altera.Embedded Design Handbook，2010.