改進(jìn)mean shift算法在目標(biāo)跟蹤中的研究

周春云，丁偉，房偉，謝林柏

（1.國(guó)家高性能計(jì)算中心揚(yáng)州分中心，萬(wàn)方電子技術(shù)有限責(zé)任公司，揚(yáng)州 225006；2.揚(yáng)州大學(xué)；3.江南大學(xué)）

改進(jìn)mean shift算法在目標(biāo)跟蹤中的研究

周春云1，丁偉2，房偉3，謝林柏3

（1.國(guó)家高性能計(jì)算中心揚(yáng)州分中心，萬(wàn)方電子技術(shù)有限責(zé)任公司，揚(yáng)州 225006；2.揚(yáng)州大學(xué)；3.江南大學(xué)）

提出了一種融合紋理和顏色模型的改進(jìn)mean-shift算法，可以克服傳統(tǒng)目標(biāo)跟蹤方法中目標(biāo)特征單一的缺點(diǎn)。在傳統(tǒng)mean-shift算法的框架下，通過(guò)融合目標(biāo)信息的顏色模型和Contourlet變換后的紋理模型，從多角度建立匹配特征，并在嵌入式平臺(tái)上實(shí)現(xiàn)本文提出的算法。實(shí)驗(yàn)結(jié)果顯示，跟蹤效果得到明顯的改善。

目標(biāo)跟蹤；mean-shift算法；Contourlet變換；嵌入式系統(tǒng)

引 言

隨著科學(xué)技術(shù)的快速發(fā)展，計(jì)算機(jī)視覺(jué)的應(yīng)用范圍越來(lái)越廣，深深地影響人類(lèi)的生產(chǎn)和生活。目標(biāo)檢測(cè)與跟蹤是計(jì)算機(jī)視覺(jué)的重要研究課題，其涉及到圖像處理、人工智能以及模式識(shí)別等諸多領(lǐng)域。在無(wú)人駕駛、國(guó)防安全、智能視頻監(jiān)控、基于視頻的人機(jī)交互等領(lǐng)域都有廣泛的應(yīng)用，因此研究此課題很有意義。

視頻對(duì)象檢測(cè)與跟蹤技術(shù)［1］是計(jì)算機(jī)視覺(jué)中一個(gè)非常關(guān)鍵的技術(shù)，與之有聯(lián)系的應(yīng)用主要有：智能視頻監(jiān)控、基于視頻的人機(jī)交互、智能機(jī)器人、醫(yī)療診斷中的應(yīng)用。此外，目標(biāo)跟蹤在視覺(jué)控制［2］、國(guó)防安全［3］、農(nóng)業(yè)自動(dòng)化［4］、視覺(jué)重構(gòu)［5］等領(lǐng)域均有應(yīng)用。目標(biāo)跟蹤，即在一段視頻圖像中的每一幀圖像中找到感興趣的目標(biāo)所處的位置。一個(gè)好的視頻跟蹤算法一般要滿(mǎn)足兩個(gè)基本要求：實(shí)時(shí)性強(qiáng)和魯棒性強(qiáng)。

mean-shift概念最早是由Fukunaga［6］等提出，基于Lindeberg提出的尺度空間理論［7］。Collins提出了一種改進(jìn)的mean-shift算法，彌補(bǔ)了在運(yùn)動(dòng)目標(biāo)跟蹤中核函數(shù)帶寬不能實(shí)時(shí)變化的缺陷［8］。Zhao等簡(jiǎn)化Correlogram直方圖，同時(shí)考慮了目標(biāo)的三維信息，結(jié)合mean-shift算法對(duì)運(yùn)動(dòng)目標(biāo)進(jìn)行跟蹤［9］。Birchfield等提出一種空間直方圖模型，該模型不僅考慮運(yùn)動(dòng)目標(biāo)的顏色信息，同時(shí)考慮各個(gè)像素之間的空間位置關(guān)系。

基于傳統(tǒng)mean-shift算法，本文在融合目標(biāo)信息的顏色模型和Contourlet變換后的紋理模型基礎(chǔ)上，從多角度建立匹配特征，最終在特定的嵌入式平臺(tái)上實(shí)現(xiàn)了該算法。實(shí)驗(yàn)結(jié)果顯示，本文所提出的算法能夠在嵌入式平臺(tái)實(shí)現(xiàn)，而且在視頻圖像的目標(biāo)跟蹤中，與單一特征空間的目標(biāo)模型相比，本算法具有更好的魯棒性及有效性。

1 顏色直方圖的mean shift跟蹤算法

1.1 目標(biāo)參考模型

式中：k（·）是核函數(shù)；δ（·）是KroneckerΔ函數(shù)δ（·）；b）是指示函數(shù)，指示像素點(diǎn)所在直方圖段數(shù)。定義如下所示：

1.2 候選目標(biāo)模型

同上，歸一化常數(shù)ch如下所示：

1.3 基于相似性函數(shù)的測(cè)度

目標(biāo)候選模型和目標(biāo)參考模型之間的相似程度可以通過(guò)相似函數(shù)來(lái)描述，兩個(gè)模型的概率分布在理想情況下是相同的。通常使用Bhattacharyya系數(shù)作為相似性度量函數(shù)，用來(lái)描述候選模型和目標(biāo)模型之間的相似程度，定義如下所示：

式中，ρ值為0～1，ρ值越大，表示目標(biāo)模型和候選區(qū)域越相似。

1.4 位置更新

當(dāng)目標(biāo)模型確定后，候選區(qū)域在當(dāng)前幀內(nèi)移動(dòng)時(shí)，令其中心為y，則得到不同的Bhattacharyya系數(shù)ρ（y），跟蹤目標(biāo)的位置就在ρ（y）極大值處。令初始中心位置為y0，通過(guò)泰勒展開(kāi)，ρ（y）可近似為：

其中：

式（7）中只有第二項(xiàng)含有y，根據(jù)均值平移理論可知，只要核函數(shù)k（·）是單調(diào)的并且函數(shù)的曲線(xiàn)是凸的，令g（·）=-k（·），則根據(jù)均值平移理論，該概率密度估計(jì)的極值點(diǎn)可以從y0處遞歸得到，計(jì)算得到新的目標(biāo)位置y1為：

2 改進(jìn)mean-shift算法

2.1 Contourlet變換

Contourlet分解變換是通過(guò)兩個(gè)步驟實(shí)現(xiàn)的：方向?yàn)V波器組（Directional filter bank，DFB）濾波和拉普拉斯金字塔（Laplacian pyramid，LP）分解。將方向?yàn)V波器和金字塔分解結(jié)合起來(lái)，就實(shí)現(xiàn)了Coutourlet變換，單獨(dú)使用其中任何一步都不能很好地對(duì)圖像進(jìn)行描述。金字塔分解不具有方向性，對(duì)高頻部分不能很好地分解；而方向?yàn)V波器對(duì)高頻部分能很好地分解，但對(duì)低頻部分不行。二者的結(jié)合可以很好地描述圖像。

圖像經(jīng)過(guò)拉普拉斯塔形濾波器（LP）產(chǎn)生一個(gè)低通圖像以及原圖與低通逼近圖之間的差值，也就是得到了該層分解后的低頻子帶和高頻子帶。方向?yàn)V波器組再對(duì)高頻子帶進(jìn)行分解，則高頻子帶可被分解為2i個(gè)方向子帶（i為任意正整數(shù)）。對(duì)低頻子帶重復(fù)上述過(guò)程，實(shí)現(xiàn)了對(duì)圖像的多分辨率多方向分解。

2.2 紋理模型

在基于Contourlet變換的算法中，一般用子帶能量的均方差和平均值來(lái)表示分解后子帶的紋理。為了降低計(jì)算復(fù)雜度，本文采用子帶能量的平均值來(lái)提取各子帶紋理特征，即：

式中，M和N分別為各子帶系數(shù)的行列數(shù)，ai，j為Contourlet變換后各子帶的系數(shù)，C為歸一化因子，即滿(mǎn)足下式：

式中，Nsb表示子帶的個(gè)數(shù)。

進(jìn)行2級(jí)Contourlet分解得到的13個(gè)子帶分別用公式（11）對(duì)其進(jìn)行紋理信息提取，得到建模區(qū)域的Contourlet變換后的紋理模型：

2.3 信息融合的mean-shift算法

求得顏色特征空間和小波紋理特征空間的目標(biāo)模型后，對(duì)這兩個(gè)模型加權(quán)融合得到聯(lián)合特征空間的目標(biāo)模型。

3 目標(biāo)跟蹤算法實(shí)現(xiàn)

3.1 嵌入式系統(tǒng)

隨著智能手機(jī)、平板電腦、MP3等數(shù)碼產(chǎn)品的廣泛使用，嵌入式系統(tǒng)從工業(yè)控制領(lǐng)域的應(yīng)用滲透到人類(lèi)的生產(chǎn)生活中，從儀表儀器、制造工業(yè)到移動(dòng)通信以及數(shù)碼產(chǎn)品各個(gè)應(yīng)用領(lǐng)域，研究嵌入式系統(tǒng)有廣泛的應(yīng)用意義。本節(jié)交叉編譯基于顏色模型的mean-shift目標(biāo)跟蹤算法和本文改進(jìn)的mean-shift算法，把編譯成功后的二進(jìn)制碼傳輸?shù)介_(kāi)發(fā)板上，比較算法的優(yōu)缺點(diǎn)，同時(shí)為以后做基于嵌入式的視頻圖像檢測(cè)與跟蹤系統(tǒng)做鋪墊。

本文使用的是由飛思卡爾開(kāi)發(fā)的i.MX53Quick Start Board工程嵌入式平臺(tái)，基于MCIMX535DVV1B，可以支持Linux/Android/WinCE等操作系統(tǒng)，采用Cortex -A8架構(gòu)，可應(yīng)用于多種嵌入式設(shè)計(jì)領(lǐng)域。平臺(tái)的參數(shù)如表1所列。

表1 硬件參數(shù)配置

3.2 環(huán)境搭建

本文嵌入式的開(kāi)發(fā)采用宿主機(jī)-目標(biāo)機(jī)的形式。宿主機(jī)里裝有Windows XP和Linux雙操作系統(tǒng)，通過(guò)串口、USB、以太網(wǎng)口與開(kāi)發(fā)板相連。串口用來(lái)輸出調(diào)式信息，通過(guò)USB燒寫(xiě)B(tài)ootloader、根文件系統(tǒng)，網(wǎng)口用來(lái)傳輸文件和掛載。開(kāi)發(fā)環(huán)境硬件連接示意圖如圖1所示。

圖1 硬件環(huán)境示意圖

3.3 目標(biāo)跟蹤算法實(shí)現(xiàn)

本節(jié)主要用C++語(yǔ)言編寫(xiě)基于顏色直方圖的mean -shift跟蹤算法和本文提出的算法，然后用交叉編譯工具鏈編譯成開(kāi)發(fā)平臺(tái)可執(zhí)行的二進(jìn)制代碼。

本文提出的算法的偽代碼：

① 手動(dòng)選取第一幀的跟蹤區(qū)域。

② 分別建立目標(biāo)區(qū)域紋理和顏色模型，然后建立目標(biāo)區(qū)域的信息融合模型，如下所示：

③ 分別建立候選區(qū)域紋理和顏色模型，然后建立候選區(qū)域的信息融合模型，如下所示：

④ 迭代計(jì)算候選區(qū)域新位置。

⑤如果相似性函數(shù)遞增，則繼續(xù)執(zhí)行下面的流程。否則，更新值，更新后的值變?yōu)樾挛恢煤团f位置的中點(diǎn)，跳轉(zhuǎn)到步驟②，繼續(xù)執(zhí)行。

⑥ 如果新位置和舊位置的差的絕對(duì)值小于閥值，則收斂到最優(yōu)點(diǎn)，即找到目標(biāo)的質(zhì)心。否則，更新值取新位置，跳轉(zhuǎn)到步驟②，繼續(xù)執(zhí)行。

⑦收斂到最優(yōu)點(diǎn)。

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

本文的實(shí)驗(yàn)環(huán)境是基于Cortex-A8、主頻1GHz的嵌入式開(kāi)發(fā)平臺(tái)，平臺(tái)上運(yùn)行的系統(tǒng)是嵌入式Linux系統(tǒng)。實(shí)驗(yàn)所處理的視頻是分辨率為128×96的彩色圖像序列，是由斯坦福大學(xué)的實(shí)驗(yàn)室提供的，專(zhuān)門(mén)用于檢測(cè)人臉跟蹤算法的好壞。本實(shí)驗(yàn)視頻共有50幀，含有人臉旋轉(zhuǎn)、人臉不可見(jiàn)的情況。跟蹤效果圖如圖2和圖3所示。

圖2 基于顏色模型的mean-shift跟蹤效果圖

圖3 基于本文算法跟蹤效果圖

圖2是基于顏色模型的mean-shift跟蹤效果圖，從圖中可以看出，人臉姿態(tài)的變化引起視頻跟蹤結(jié)果的不準(zhǔn)確，當(dāng)人臉不可見(jiàn)時(shí)，跟蹤目標(biāo)丟失。圖3是基于本文算法的結(jié)果截圖，從圖中可以看出，跟蹤效果明顯得到改善，始終可以很好地跟蹤目標(biāo)，這得益于加入的紋理模型。

由表2可以看出，本文提出的算法耗時(shí)稍微高于基于顏色模型的mean-shift的耗時(shí)，但是滿(mǎn)足實(shí)時(shí)要求。

表2 兩種跟蹤算法的耗時(shí)比較

［1］侯志強(qiáng)，韓崇昭.視覺(jué)跟蹤技術(shù)綜述［J］.自動(dòng)化學(xué)報(bào)，2006，32（4）：603-617.

［2］Marchand N，Chaumette F.Task sequencing for high-level sensor-based control［J］.IEEE Trans on Robotics，2007，23（1）：60-72.

［3］Yang Yunpu.Research on the model and ambiguity property of a GSM passive radar signal［J］.Electronics Transactions，2005，33（6）：1048-1052.

［4］Lenain R，Thuilot B，Cariou C，et al.Model Predictive Control of Vehicle in presence of sliding Application to farm vehicles path tracking［C］//IEEE International Conference on Robotics and Automation，2005（4）：897-902.

［5］Kyriakoulis N，Gasteratos A.Color-based monocular visuoinertial 3-D pose estimation of A Volant robot［J］. IEEE Trans Instrum Meas，2010，59（10）：2706-2715.

［6］Fukunaga K，Hostetler L D.The estimation of the gradient of a density function，with applications in pattern recognition ［J］.IEEE Transactions on Information Theory，1975，21（1）：32-87.

［7］Lindeber T.Feature detection with automatic scale selection.International Journal of Computer Vision，1998，30（2）：194-203.

［8］Collins R T.Mean Shift blob tracking through scale space ［J］.IEEE Conf.on Computer Vision and Pattern Recongnition，2003（5）：234-240.

［9］Zhao Q，Tao H，Object tracking using color correlogram［C］// IEEE Workshop on Visual Surveillance and Performance Evaluation of Tracking and Surveillance，2005（3）：263-270.

周春云（工程師），主要研究方向?yàn)榍度胧较到y(tǒng)與并行體系結(jié)構(gòu)；丁偉、房偉（工程師），主要研究方向?yàn)榍度胧较到y(tǒng)；謝林柏（教授），主要研究方向?yàn)橛?jì)算機(jī)控制系統(tǒng)。

9在程序設(shè)計(jì)時(shí)，要慎用長(zhǎng)型。當(dāng)不得已使用長(zhǎng)型選擇因子時(shí)，如果選擇因數(shù)（case值）不是很多，選取if-thenlese的語(yǔ)句效果會(huì)更好。

許多參考文獻(xiàn)都在討論嵌入式軟件設(shè)計(jì)的運(yùn)行效率［4-8］。單片機(jī)程序的一個(gè)重要設(shè)計(jì)目標(biāo)是對(duì)硬件的控制，因此，用匯編語(yǔ)言設(shè)計(jì)程序可以取得較好的效果，但匯編語(yǔ)言程序較難掌握，對(duì)于較為抽象的算法，用匯編語(yǔ)言更難，并且其可讀性和可維護(hù)性較差，因此，用混合編程方法是一個(gè)好辦法。另外一個(gè)途徑就是，利用C語(yǔ)言先行設(shè)計(jì)，然后根據(jù)Keil編譯的結(jié)果進(jìn)行修改，也可以得到非常滿(mǎn)意的效果。

參考文獻(xiàn)

［1］牛洪濤.優(yōu)化C51程序的方法.微計(jì)算機(jī)應(yīng)用，1998（7）：237 -240.

［2］周敬利，卓越，余勝生.MCS51程序空間擴(kuò)展原理及編譯器優(yōu)化.計(jì)算機(jī)工程，2003（5）：183-185.

［3］侯濟(jì)恭，余堅(jiān).C語(yǔ)言開(kāi)關(guān)語(yǔ)句的自動(dòng)翻譯［J］.華僑大學(xué)學(xué)報(bào)：自然科學(xué)版，1995（1）：105-110.

［4］張開(kāi)便.C語(yǔ)言與匯編混合編程機(jī)理探析與應(yīng)用［J］.電腦開(kāi)發(fā)與應(yīng)用，2010，23（4）：28-30.

［5］楊加國(guó).單片機(jī)C語(yǔ)言與匯編語(yǔ)言混合編程［J］.成都大學(xué)學(xué)報(bào)：自然科學(xué)版，2008（9）：208-211.

［6］張志科，王振喜.基于Keil51匯編與C語(yǔ)言混合編程方法研究［J］.計(jì)算機(jī)與現(xiàn)代化，2010（10）：43-46.

［7］韓彩霞.單片機(jī)C語(yǔ)言編程中幾種常見(jiàn)問(wèn)題解析［J］.軟件導(dǎo)刊，2013（7）：47-49.

［8］阮海蓉.Keil C51中變量的使用［J］.單片機(jī)與嵌入式系統(tǒng)應(yīng)用，2011（5）：67-69.

（責(zé)任編輯：薛士然 收稿日期：2015-01-08）

Research on Target Tracking Based on lmproved mean-shift Algorithm

Zhou Chunyun1，Ding Wei2，F(xiàn)ang Wei3，Xie Linbo3
（1.National High Performance Computing Center at Yangzhou，Wanfang Electronic Technology Co.，Ltd.，Yangzhou 225006，China；2.Yangzhou University；3.Jiangnan University）

The improved mean-shift algorithm based on texture and color model is proposed，which can overcome the disadvantage of single target feature in the traditional target tracking.In the framework of traditional mean-shift algorithm，the system establishes the matching feature from multiple perspectives，by fusing color model and texture model obtained from Contourlet transform.The proposed algorithm has been realized on an embedded platform.The experimental results show that the tracking effect is improved.

target tracking；mean-shift algorithm；Contourlet transform；embedded system

TP273

A

??薛士然

2015-01-13）