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

1、基于方向直方圖的Mean shift 目標(biāo)跟蹤新算法秦臻1,2,曹劍中1(1.中國科學(xué)院西安光學(xué)精密機械研究所,陜西西安710119;2.中國科學(xué)院研究生院北京100039摘要:Mean shift 算法是一種非參數(shù)密度估計算法,可以實現(xiàn)快速的最優(yōu)匹配。為了有效地將Mean shift 算法應(yīng)用到灰度圖像中,使用空間分布和紋理信息作為匹配信息,提出了一種基于空間方向直方圖的Mean shift 跟蹤新算法。利用卡爾曼濾波器來獲得每幀目標(biāo)的起始位置,再利用Mean shift 算法得到跟蹤位置。實驗結(jié)果證明,該算法在目標(biāo)運動較快,目標(biāo)尺度變化的情況下仍能穩(wěn)定、實時、高效地跟蹤目標(biāo)。關(guān)鍵詞:圖像處

2、理;目標(biāo)跟蹤;Mean shift ;卡爾曼濾波;方向直方圖中圖分類號:TP751文獻(xiàn)標(biāo)識碼:A文章編號: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 th

3、e Chinese Academy of Sciences ,Beijing 100039,China 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 Me

4、an shift based on orientation histogram is proposed.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 si

5、ze ,experiment results show that the object can be 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稿件編號:201104069作者簡介:秦臻(1986,男,陜西西安人,碩士研究生。研究方向:圖像壓縮處理。目標(biāo)的實時跟蹤在計算機

6、視覺跟蹤領(lǐng)域有著非常重要的應(yīng)用,近年來在目標(biāo)跟蹤領(lǐng)域提出了很多好的算法,然而很多算法由于計算復(fù)雜,都未能應(yīng)用到對實時性要求較高的場合。Dorin Comaniciu 將Mean shift 算法引入到目標(biāo)跟蹤領(lǐng)域1-2,極大地減少了跟蹤算法的計算量。Dorin Comaniciu 提出的算法是以彩色直方圖作為特征來實現(xiàn)目標(biāo)的識別與定位,而灰度直方圖所包含的圖像信息單一,使得Mean shift 算法很難應(yīng)用于灰度圖像,限制了Mean shift 算法的適應(yīng)環(huán)境。經(jīng)典的Mean shift 算法要求相鄰兩幀間目標(biāo)模板區(qū)域必須重疊,在目標(biāo)較快運動的情況下容易跟丟目標(biāo);在目標(biāo)出現(xiàn)尺度變化的復(fù)雜條件下

7、,其跟蹤結(jié)果往往出現(xiàn)偏差,甚至跟蹤失敗。筆者提出了基于空間方向直方圖的Mean shift 跟蹤算法,使用空間統(tǒng)計信息作為匹配信息,結(jié)合卡爾曼濾波預(yù)測目標(biāo)位置。實驗結(jié)果表明,該算法在目標(biāo)運動較快,光照變化和尺度縮放等情況下可以對目標(biāo)準(zhǔn)確的跟蹤,具有良好的魯棒性和效率。1Mean shift 算法概述Mean shift 算法是一種非參數(shù)概率密度估計算法3,可以通過迭代,快速地收斂于概率密度函數(shù)的局部極大值。算法的跟蹤過程就是不斷尋找概率密度局部最大值的過程,其步驟如下。1.1目標(biāo)模型的描述在首幀圖像中確定被跟蹤的目標(biāo)區(qū)域,可通過手工選擇矩形框的方式來確定目標(biāo)區(qū)域。目標(biāo)模型可以描述為在目標(biāo)區(qū)域上

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

9、1.3相似性函數(shù)相似性函數(shù)用于描述目標(biāo)模型和候選模型的相似性度量,可使用Bhattacharyya 5系數(shù)作為相似性函數(shù),即(y =(p (y ,q =mu =1p u (y q u姨(3 其值在01之間。(y 的值越大,表示兩個模型越相似。1.4目標(biāo)定位為使(y 0最大,應(yīng)當(dāng)先將當(dāng)前幀的目標(biāo)中心定位為前一幀中目標(biāo)中心的位置y 0,在y 0鄰域內(nèi)尋找局部最優(yōu)目標(biāo)位置y 1。定位時,先在(y 0處對函數(shù)式(3進(jìn)行泰勒展開,相似性函數(shù)可近似為:(p (y ,q =12mu =1p u (y 0q 姨+C h2n hi =1ik (y -x i/h2姨姨(4其中:i =mu =1q up u (y

10、0姨b (x i -u (5令f n ,h =n hi =1C h i k(y -x i/h 2姨姨(6可以看出,求相似性函數(shù)最大就是要求式(6最大,通過對相似性函數(shù)求最大值,即可計算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ū)域即可由初始位置逐步移動到真實的目標(biāo)位置。根據(jù)式(4可知,相似性函數(shù)(y 0在處先進(jìn)行泰勒展開,而泰勒展開要求是在鄰域內(nèi)展開,這就限制了起始點y 0和y 的距離不能太大。2基于方向直方圖的跟蹤

11、2.1方向直方圖給定一組灰度圖像I ,定義像素的梯度方向角為=arctan墜f /墜y 墜f /墜x(8式中墜f /墜y 和墜f /墜x 分別是該像素處沿y 和x 方向的梯度,可以通過梯度算子來獲得。梯度方向角的取值范圍為02。為了獲得方向編碼,需要對方向角進(jìn)行量化。方向角量化的間距為,于是方向編碼可按式(9計算:c ij =ij /墜f /墜x +墜f /墜y >Tm其姨他(9如果方向編碼被量化成m 個,則c ij 的取值為0,1,2,m -1。對于墜f /墜x +墜f /墜y 小于閾值T 的像素來說,定義其方向編碼為m ,由于此區(qū)域很難計算出穩(wěn)定的梯度方向角,因而閾值T 可根據(jù)經(jīng)驗來

12、選擇。如果采用的量化方向為16個,方向編碼的間距取/8。用Mean shift 跟蹤目標(biāo)模型和候選模型時,在跟蹤區(qū)域用方向編碼來描述目標(biāo)。方向編碼示意圖如圖1所示。2.2跟蹤算法流程1預(yù)測跟蹤坐標(biāo)利用前一幀圖像中目標(biāo)的位置信息來預(yù)測在當(dāng)前幀中目標(biāo)的位置信息。先驗估計計算公式6如下:x k =A x k -1+B k -1(10P k =A P k -1A T +Q(11x k 為在已知第k 步以前狀態(tài)情況下第k 步的先驗狀態(tài)估計;x k 為第k 步的后驗狀態(tài)估計;隨機信號k 表示觀測噪聲;矩陣A 將上一時刻的狀態(tài)線性映射到當(dāng)前時刻的狀態(tài);B 代表可選的控制輸入的增益。P k 是先驗估計誤差的協(xié)

13、方差;P k 是后驗估計誤差的協(xié)方差。Q 是過程激勵噪聲協(xié)方差矩陣。2獲得當(dāng)前幀的跟蹤坐標(biāo)以1預(yù)測得到的跟蹤坐標(biāo)為起始搜索位置,應(yīng)用基于方向直方圖的Mean shift 跟蹤算法,得到當(dāng)前幀目標(biāo)實際的跟蹤坐標(biāo)Z k (x K ,y K 。3校正跟蹤坐標(biāo)根據(jù)2得到的實際測量值Z k ,利用后驗估計公式,計算得到新的后驗估計坐標(biāo)值,返回到1,進(jìn)行下一幀參數(shù)的預(yù)測。后驗估計計算公式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 為觀測噪聲協(xié)方差矩陣;K k 為卡爾曼增益

14、;H 表示狀態(tài)變量x k 對測量變量Z k 的增益矩陣。3實驗結(jié)果與分析本文利用灰度圖像序列來驗證新算法的跟蹤效果8-9。圖2為圖像跟蹤區(qū)域的灰度直方圖和方向統(tǒng)計直方圖。圖3是汽車圖像序列的跟蹤結(jié)果。3.1直方圖的對比方向直方圖簡化了目標(biāo)的表述方式,減少了Meanshift匹配時的bins 的個數(shù),因而降低了跟蹤過程中的匹配復(fù)雜度,有利于提高跟蹤速度,并且利用了目標(biāo)運動的方向特性,跟蹤時對目標(biāo)方向變化不敏感。圖1運動方向編碼示意圖Fig.1Coding schemes of movementdirection電子設(shè)計工程2011年第12期 3.2序列圖像跟蹤結(jié)果 在圖3中,圖(a 、(b 、(

15、c 為原算法的跟蹤結(jié)果;圖(d 、(e 、(f 為新算法的跟蹤結(jié)果。原跟蹤算法中,在汽車運動較快的情況下,跟蹤過程中目標(biāo)存在部分出框的問題;而新算法在目標(biāo)運動速度過快和目標(biāo)尺度變化的情況下仍然可以穩(wěn)定的跟蹤到目標(biāo)。表1和圖4是Mean shift 算法和新算法的跟蹤效率對比分析。圖(a 是兩組算法迭代次數(shù)對比。圖(b 是兩組算法跟蹤耗時對比?？梢钥闯?由于卡爾曼濾波算法的計算量很小,卡爾曼濾波器平穩(wěn)運行后,新的算法能夠減少每幀內(nèi)Mean shift 的迭代次數(shù),而且每幀的計算時間相對減少,表明新算法有效地提高了跟蹤的效率。4結(jié)論本文提出了一種基于空間方向直方圖的Mean shift 跟蹤新算法

16、。該算法利用卡爾曼濾波器預(yù)測當(dāng)前幀目標(biāo)的可能位置,利用空間直方圖來描述目標(biāo),能夠在一定復(fù)雜條件下對目標(biāo)進(jìn)行準(zhǔn)確、有效、實時的跟蹤。實驗結(jié)果表明,該算法可以較好的適應(yīng)光線變化,目標(biāo)尺度縮放或色彩質(zhì)量很差等圖像序列中的目標(biāo)跟蹤,改善了傳統(tǒng)基于色彩方向直方圖的局限性,提高了跟蹤算法的效率。圖2汽車運動區(qū)域直方圖Fig.2Histogram of motor movement region圖3跟蹤汽車圖像序列Fig.3Image sequence of tracking car圖4兩組算法跟蹤效率對比Fig.4Tracking performance comparison of two groupsa

17、lgorithm表1Mean shift 和改進(jìn)算法的對比Tab.1Contrast between Mean shift and improved algorithm算法對比平均每幀耗時平均每幀迭代次數(shù)原算法0.3920s 4.4次新算法0.2768s 3.6次新算法效率提高(%41%22%-170-variation minimization and oscillating patterns in image processingJ.Journal of Scientific Computing ,2003,19(1:553-572.3Meyer Y.Oscillating pattern

18、s in image processing and nolinear evolution equationsD.AMS university Lecture Series ,2002.4Potlapalli H ,Luo R C.Fractal -based classification of natural texturesJ.IEEE transanctions on Industrial Electronics ,1998,45(1:142-150.5Cisi A ,Perez P ,Toyama K.Object removal by exemplar -based inpaintin

19、gC/Proceedings of Euro ,2003.6馮志剛,周宏偉.圖像的分形維數(shù)計算方法及其應(yīng)用J.江蘇理工大學(xué)學(xué)報,2001,22(6:92-96.FENG Zhi -gang ,ZHOU Hong -wei.Compute method and appliactiong of image 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

20、 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 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 seek

21、ing ,and clustering J.IEEE Transactions on Pattern Analysis and Machine Intelligence ,1995,17(8:790-799.4Comaniciu D ,Ramesh V ,Meer P.The variable bandwith Mean shift and data -driven scale selectionJ.Eighth IEEE International Conference on Computer Vision ,2001:438-445.5PENG Ning -song ,YANG Jie ,

22、LIU Zhi.Mean shift blob tracking with kernel histogram filtrering and hypothesis testingJ.Pattern Recognition Letters ,2005,26(5:605-614.6田綱,胡瑞敏,王中元.一種基于運動矢量分析的Mean shift目標(biāo)跟蹤算法J.中國圖象圖形學(xué)報.2010,15(1:85-90.TIAN Gang ,HU Rui -min ,WANG Zhong -yuan.A Mean shift target tracking algorithm based on motion v

23、ectoranalysisJ.Journal of Image and Graphics ,2010,15(1:85-90.7詹建平,黃席樾,沈志熙,等.基于均值漂移和卡爾曼濾波的目標(biāo)跟蹤方法J.重慶理工大學(xué)學(xué)報:自然科學(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 filter J.Journal of Chongqing University of Technology :Natural Science

24、,2010,24(3:76-80.8王寶榮,楊華,王一程,等.基于卡爾曼濾波與均值漂移算法的目標(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 濾波和邊緣直方圖的實時目標(biāo)跟蹤J.清華大學(xué)學(xué)報:自然科學(xué)版,2008,48(7:1104-1107.

25、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頁!Avago Technologies 推出市場上首個WiMAX 共存前端模塊Avago Technologies 宣布推出一個完整射頻前端模塊(FEM,用于手機或便攜電腦中的WiMAX 。這款新的AFEM-S257模塊專用于WiMAX 和其他蜂窩式無線及WiFi 無線在同一設(shè)備中共存的應(yīng)用。此模塊為5×7×1毫米小型封裝,擁有兩個接收端口和一個獨立發(fā)