基于方向直方圖的Meanshift目標(biāo)跟蹤新算法

1、基于方向直方圖的Mean shift 目標(biāo)跟蹤新算法秦臻1,2,曹劍中1摘要:Mean shift 算法是一種非參數(shù)密度估計(jì)算法,可以實(shí)現(xiàn)快速的最優(yōu)匹配。為了有效地將Mean shift 算法應(yīng)用到灰度圖像中,使用空間分布和紋理信息作為匹配信息,提出了一種基于空間方向直方圖的Mean shift 跟蹤新算法。利用卡爾曼濾波器來(lái)獲得每幀目標(biāo)的起始位置,再利用Mean shift 算法得到跟蹤位置。實(shí)驗(yàn)結(jié)果證明,該算法在目標(biāo)運(yùn)動(dòng)較快,目標(biāo)尺度變化的情況下仍能穩(wěn)定、實(shí)時(shí)、高效地跟蹤目標(biāo)。關(guān)鍵詞:圖像處理;目標(biāo)跟蹤;Mean shift ;卡爾曼濾波;方向直方圖中圖分類號(hào):TP751文獻(xiàn)標(biāo)識(shí)碼:A文章

2、編號(hào):1674-6236(201112-0168-04New Mean shift tracking algorithm based on orientation histogramQIN Zhen 1,2,CAO Jian -zhong 1(1.Xi an Institute of Optics and Precision Mechanics Chinese Academy of Sciences ,Xi an 710119,China ;2.Graduate University of the Chinese Academy of Sciences ,Beijing 100039,Chin

3、a Abstract:The Mean shift algorithm is a nonparametric density estimation method.The fast and optimal mode matching can be achieved by this method.In order to apply Mean shift algorithm on gray -level image effectively ,a new tracking algorithm of Mean shift based on orientation histogram is propose

4、d.It uses space spread and vein as matching information.The starting position of target is found with Kalman filter in every frame ,and then Mean shift is utilized to track the target position.In the situation of target moving fast and changing of size ,experiment results show that the object can be

5、 tracked steadily ,effectively and real -time by using the proposed algorithm.Key words:image processing ;tracking object ;Mean shift ;Kalman filter ;orientation histogram收稿日期:2011-04-14稿件編號(hào):201104069作者簡(jiǎn)介:秦臻(1986,男,陜西西安人,碩士研究生。研究方向:圖像壓縮處理。目標(biāo)的實(shí)時(shí)跟蹤在計(jì)算機(jī)視覺(jué)跟蹤領(lǐng)域有著非常重要的應(yīng)用,近年來(lái)在目標(biāo)跟蹤領(lǐng)域提出了很多好的算法,然而很多算法由于計(jì)算復(fù)雜,都

6、未能應(yīng)用到對(duì)實(shí)時(shí)性要求較高的場(chǎng)合。Dorin Comaniciu 將Mean shift 算法引入到目標(biāo)跟蹤領(lǐng)域1-2,極大地減少了跟蹤算法的計(jì)算量。Dorin Comaniciu 提出的算法是以彩色直方圖作為特征來(lái)實(shí)現(xiàn)目標(biāo)的識(shí)別與定位,而灰度直方圖所包含的圖像信息單一,使得Mean shift 算法很難應(yīng)用于灰度圖像,限制了Mean shift 算法的適應(yīng)環(huán)境。經(jīng)典的Mean shift 算法要求相鄰兩幀間目標(biāo)模板區(qū)域必須重疊,在目標(biāo)較快運(yùn)動(dòng)的情況下容易跟丟目標(biāo);在目標(biāo)出現(xiàn)尺度變化的復(fù)雜條件下,其跟蹤結(jié)果往往出現(xiàn)偏差,甚至跟蹤失敗。筆者提出了基于空間方向直方圖的Mean shift 跟蹤算法

7、,使用空間統(tǒng)計(jì)信息作為匹配信息,結(jié)合卡爾曼濾波預(yù)測(cè)目標(biāo)位置。實(shí)驗(yàn)結(jié)果表明,該算法在目標(biāo)運(yùn)動(dòng)較快,光照變化和尺度縮放等情況下可以對(duì)目標(biāo)準(zhǔn)確的跟蹤,具有良好的魯棒性和效率。1Mean shift 算法概述Mean shift 算法是一種非參數(shù)概率密度估計(jì)算法3,可以通過(guò)迭代,快速地收斂于概率密度函數(shù)的局部極大值。算法的跟蹤過(guò)程就是不斷尋找概率密度局部最大值的過(guò)程,其步驟如下。在首幀圖像中確定被跟蹤的目標(biāo)區(qū)域,可通過(guò)手工選擇矩形框的方式來(lái)確定目標(biāo)區(qū)域。目標(biāo)模型可以描述為在目標(biāo)區(qū)域上的所有特征值的概率值,用目標(biāo)模型的特征值估計(jì)的概率密度為:q u =C ni =1K(x 0-x i/h 2b (x i

8、 -u (1其中,K (x 為核函數(shù)的輪廓函數(shù);b (x i 是表示像素x i 屬于哪類特征值;h 表示核函數(shù)的帶寬4;b (x i -u 是用于判斷目標(biāo)區(qū)域中的任意像素x i 的顏色值是否等于第u 個(gè)特征值;候選模型的描述類似式(1,計(jì)算當(dāng)前幀中,搜索窗口的特征值的概率密度為:p u (y =C n n hi =1K(y -x i/h 2b (x i -u (2電子設(shè)計(jì)工程Electronic Design Engineering-168-相似性函數(shù)用于描述目標(biāo)模型和候選模型的相似性度量,可使用Bhattacharyya 5系數(shù)作為相似性函數(shù),即(y =(p (y ,q =mu =1p u

9、(y q u姨(3 其值在01之間。(y 的值越大,表示兩個(gè)模型越相似。為使(y 0最大,應(yīng)當(dāng)先將當(dāng)前幀的目標(biāo)中心定位為前一幀中目標(biāo)中心的位置y 0,在y 0鄰域內(nèi)尋找局部最優(yōu)目標(biāo)位置y 1。定位時(shí),先在(y 0處對(duì)函數(shù)式(3進(jìn)行泰勒展開(kāi),相似性函數(shù)可近似為:(p (y ,q =12mu =1p u (y 0q 姨+C h2n hi =1ik (y -x i/h2姨姨(4其中:i =mu =1q up u (y 0姨b (x i -u (5令f n ,h =n hi =1C h i k(y -x i/h 2姨姨(6可以看出,求相似性函數(shù)最大就是要求式(6最大,通過(guò)對(duì)相似性函數(shù)求最大值,即可計(jì)算

10、Mean shift 向量y 1-y 0。如式(7所示:y 1-y 0=n hi =1x i i g(y -x i/h 2姨姨n hi =1ig (y -x i/h 2姨姨-y 0(7其中g(shù) (x =-k (x ,這樣目標(biāo)區(qū)域即可由初始位置逐步移動(dòng)到真實(shí)的目標(biāo)位置。根據(jù)式(4可知,相似性函數(shù)(y 0在處先進(jìn)行泰勒展開(kāi),而泰勒展開(kāi)要求是在鄰域內(nèi)展開(kāi),這就限制了起始點(diǎn)y 0和y 的距離不能太大。2基于方向直方圖的跟蹤方向直方圖給定一組灰度圖像I ,定義像素的梯度方向角為=arctan墜f /墜y 墜f /墜x(8式中墜f /墜y 和墜f /墜x 分別是該像素處沿y 和x 方向的梯度,可以通過(guò)梯度算

11、子來(lái)獲得。梯度方向角的取值范圍為02。為了獲得方向編碼,需要對(duì)方向角進(jìn)行量化。方向角量化的間距為,于是方向編碼可按式(9計(jì)算:c ij =ij /墜f /墜x +墜f /墜y >Tm其姨他(9如果方向編碼被量化成m 個(gè),則c ij 的取值為0,1,2,m -1。對(duì)于墜f /墜x +墜f /墜y 小于閾值T 的像素來(lái)說(shuō),定義其方向編碼為m ,由于此區(qū)域很難計(jì)算出穩(wěn)定的梯度方向角,因而閾值T 可根據(jù)經(jīng)驗(yàn)來(lái)選擇。如果采用的量化方向?yàn)?6個(gè),方向編碼的間距取/8。用Mean shift 跟蹤目標(biāo)模型和候選模型時(shí),在跟蹤區(qū)域用方向編碼來(lái)描述目標(biāo)。方向編碼示意圖如圖1所示。1預(yù)測(cè)跟蹤坐標(biāo)利用前一幀圖

12、像中目標(biāo)的位置信息來(lái)預(yù)測(cè)在當(dāng)前幀中目標(biāo)的位置信息。先驗(yàn)估計(jì)計(jì)算公式6如下:x k =A x k -1+B k -1(10P k =A P k -1A T +Q(11x k 為在已知第k 步以前狀態(tài)情況下第k 步的先驗(yàn)狀態(tài)估計(jì);x k 為第k 步的后驗(yàn)狀態(tài)估計(jì);隨機(jī)信號(hào)k 表示觀測(cè)噪聲;矩陣A 將上一時(shí)刻的狀態(tài)線性映射到當(dāng)前時(shí)刻的狀態(tài);B 代表可選的控制輸入的增益。P k 是先驗(yàn)估計(jì)誤差的協(xié)方差;P k 是后驗(yàn)估計(jì)誤差的協(xié)方差。Q 是過(guò)程激勵(lì)噪聲協(xié)方差矩陣。2獲得當(dāng)前幀的跟蹤坐標(biāo)以1預(yù)測(cè)得到的跟蹤坐標(biāo)為起始搜索位置,應(yīng)用基于方向直方圖的Mean shift 跟蹤算法,得到當(dāng)前幀目標(biāo)實(shí)際的跟蹤坐標(biāo)

13、Z k (x K ,y K 。3校正跟蹤坐標(biāo)根據(jù)2得到的實(shí)際測(cè)量值Z k ,利用后驗(yàn)估計(jì)公式,計(jì)算得到新的后驗(yàn)估計(jì)坐標(biāo)值,返回到1,進(jìn)行下一幀參數(shù)的預(yù)測(cè)。后驗(yàn)估計(jì)計(jì)算公式7如下:K k =P k -H T (H P k -H T +R -1(12x k =x k +K k (Z k -H x k (13P k =(I -K k H P k(14R 為觀測(cè)噪聲協(xié)方差矩陣;K k 為卡爾曼增益;H 表示狀態(tài)變量x k 對(duì)測(cè)量變量Z k 的增益矩陣。3實(shí)驗(yàn)結(jié)果與分析本文利用灰度圖像序列來(lái)驗(yàn)證新算法的跟蹤效果8-9。圖2為圖像跟蹤區(qū)域的灰度直方圖和方向統(tǒng)計(jì)直方圖。圖3是汽車圖像序列的跟蹤結(jié)果。方向直方

14、圖簡(jiǎn)化了目標(biāo)的表述方式,減少了Meanshift匹配時(shí)的bins 的個(gè)數(shù),因而降低了跟蹤過(guò)程中的匹配復(fù)雜度,有利于提高跟蹤速度,并且利用了目標(biāo)運(yùn)動(dòng)的方向特性,跟蹤時(shí)對(duì)目標(biāo)方向變化不敏感。圖1運(yùn)動(dòng)方向編碼示意圖Coding schemes of movementdirection電子設(shè)計(jì)工程2011年第12期 在圖3中,圖(a 、(b 、(c 為原算法的跟蹤結(jié)果;圖(d 、(e 、(f 為新算法的跟蹤結(jié)果。原跟蹤算法中,在汽車運(yùn)動(dòng)較快的情況下,跟蹤過(guò)程中目標(biāo)存在部分出框的問(wèn)題;而新算法在目標(biāo)運(yùn)動(dòng)速度過(guò)快和目標(biāo)尺度變化的情況下仍然可以穩(wěn)定的跟蹤到目標(biāo)。表1和圖4是Mean shift 算法和新算法

15、的跟蹤效率對(duì)比分析。圖(a 是兩組算法迭代次數(shù)對(duì)比。圖(b 是兩組算法跟蹤耗時(shí)對(duì)比?？梢钥闯?由于卡爾曼濾波算法的計(jì)算量很小,卡爾曼濾波器平穩(wěn)運(yùn)行后,新的算法能夠減少每幀內(nèi)Mean shift 的迭代次數(shù),而且每幀的計(jì)算時(shí)間相對(duì)減少,表明新算法有效地提高了跟蹤的效率。4結(jié)論本文提出了一種基于空間方向直方圖的Mean shift 跟蹤新算法。該算法利用卡爾曼濾波器預(yù)測(cè)當(dāng)前幀目標(biāo)的可能位置,利用空間直方圖來(lái)描述目標(biāo),能夠在一定復(fù)雜條件下對(duì)目標(biāo)進(jìn)行準(zhǔn)確、有效、實(shí)時(shí)的跟蹤。實(shí)驗(yàn)結(jié)果表明,該算法可以較好的適應(yīng)光線變化,目標(biāo)尺度縮放或色彩質(zhì)量很差等圖像序列中的目標(biāo)跟蹤,改善了傳統(tǒng)基于色彩方向直方圖的局限性

16、,提高了跟蹤算法的效率。圖2汽車運(yùn)動(dòng)區(qū)域直方圖Fig.2Histogram of motor movement region圖3跟蹤汽車圖像序列Fig.3Image sequence of tracking car圖4兩組算法跟蹤效率對(duì)比Fig.4Tracking performance comparison of two groupsalgorithm表1Mean shift 和改進(jìn)算法的對(duì)比Tab.1Contrast between Mean shift and improved algorithm算法對(duì)比平均每幀耗時(shí)平均每幀迭代次數(shù)0.2768s 3.6次新算法效率提高(%41%22%-

17、170-variation minimization and oscillating patterns in image processingJ.Journal of Scientific Computing ,2003,19(1:553-572.3Meyer Y.Oscillating patterns in image processing and nolinear evolution equationsD.AMS university Lecture Series ,2002.4Potlapalli H ,Luo R C.Fractal -based classification of

18、natural texturesJ.IEEE transanctions on Industrial Electronics ,1998,45(1:142-150.5Cisi A ,Perez P ,Toyama K.Object removal by exemplar -based inpaintingC/Proceedings of Euro ,2003.6馮志剛,周宏偉.圖像的分形維數(shù)計(jì)算方法及其應(yīng)用J.江蘇理工大學(xué)學(xué)報(bào),2001,22(6:92-96.FENG Zhi -gang ,ZHOU Hong -wei.Compute method and appliactiong of im

19、age fractal demensionJ.Journal of Jiangsu University of Science and Technology ,2001,22(6:92-96.參考文獻(xiàn):1Comaniciu D ,Ramesh V ,Meer P.Kernel -based object tracking J.IEEE Transactions on Pattern Analysis and Machine Intelligence ,2003,25(5:564-577.2Comaniciu D ,Ramesh V ,Meer P.Real -time tracking of

20、non -rigid objects using Mean shift C/Proc IEEE Coference on Computer Vision and Pattern Recognition ,2000:142-149.3CHENG Yi -zong.Mean shift ,mode seeking ,and clustering J.IEEE Transactions on Pattern Analysis and Machine Intelligence ,1995,17(8:790-799.4Comaniciu D ,Ramesh V ,Meer P.The variable

21、bandwith Mean shift and data -driven scale selectionJ.Eighth IEEE International Conference on Computer Vision ,2001:438-445.5PENG Ning -song ,YANG Jie ,LIU Zhi.Mean shift blob tracking with kernel histogram filtrering and hypothesis testingJ.Pattern Recognition Letters ,2005,26(5:605-614.6田綱,胡瑞敏,王中元

22、.一種基于運(yùn)動(dòng)矢量分析的Mean shift目標(biāo)跟蹤算法J.中國(guó)圖象圖形學(xué)報(bào).2010,15(1:85-90.TIAN Gang ,HU Rui -min ,WANG Zhong -yuan.A Mean shift target tracking algorithm based on motion vector的目標(biāo)跟蹤方法J.重慶理工大學(xué)學(xué)報(bào):自然科學(xué),2010,24(3:76-80.ZHAN Jian -ping ,HUANG Xi -yue ,SHEN Zhi -xi ,et al.Target tracking based on Mean -shift and kalman filt

23、er J.Journal of Chongqing University of Technology :Natural Science ,2010,24(3:76-80.法的目標(biāo)跟蹤J.激光與紅外,2009,39(11:1233-1236.WANG Bao -rong ,YANG Hua ,WANG Yi -cheng ,et al.Target tracking algorithm based on Kalman filter and meanshiftJ.Laser and Infrared ,2009,39(11:1233-1236.9劉惟錦,章毓晉.基于Kalman 濾波和邊緣直方圖的

24、實(shí)時(shí)目標(biāo)跟蹤J.清華大學(xué)學(xué)報(bào):自然科學(xué)版,2008,48(7:1104-1107.LIU Wei -jin ,ZHANG Shu -jin.Edge -color -histogram and Kalman filter -based real -time object trackingJ.Journal of Tsinghua University :Science and Technology ,2008,48(7:1104-1107.(上接第162頁(yè)!Avago Technologies 推出市場(chǎng)上首個(gè)WiMAX 共存前端模塊Avago Technologies 宣布推出一個(gè)完整射頻前端模塊(FEM,用于手機(jī)或便攜電腦中的WiMAX 。這款新的AFEM-S257模塊專用于WiMAX 和其他蜂窩式無(wú)線及WiFi 無(wú)線在同一設(shè)備中共存的應(yīng)用。此模塊為5×7×1毫米小型封裝,擁有兩個(gè)接收端口和一個(gè)獨(dú)立發(fā)射端口,非常適用于頻率范圍在2.52.7GHz 頻率