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

2、理;目標跟蹤;Mean shift ;卡爾曼濾波;方向直方圖中圖分類號:TP751文獻標識碼: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,男,陜西西安人,碩士研究生。研究方向:圖像壓縮處理。目標的實時跟蹤在計算機

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

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

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

9、1.3相似性函數相似性函數用于描述目標模型和候選模型的相似性度量,可使用Bhattacharyya 5系數作為相似性函數,即(y =(p (y ,q =mu =1p u (y q u姨(3 其值在01之間。(y 的值越大,表示兩個模型越相似。1.4目標定位為使(y 0最大,應當先將當前幀的目標中心定位為前一幀中目標中心的位置y 0,在y 0鄰域內尋找局部最優目標位置y 1。定位時,先在(y 0處對函數式(3進行泰勒展開,相似性函數可近似為:(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可以看出,求相似性函數最大就是要求式(6最大,通過對相似性函數求最大值,即可計算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 (x =-k (x ,這樣目標區域即可由初始位置逐步移動到真實的目標位置。根據式(4可知,相似性函數(y 0在處先進行泰勒展開,而泰勒展開要求是在鄰域內展開,這就限制了起始點y 0和y 的距離不能太大。2基于方向直方圖的跟蹤

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

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

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

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

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

16、。該算法利用卡爾曼濾波器預測當前幀目標的可能位置,利用空間直方圖來描述目標,能夠在一定復雜條件下對目標進行準確、有效、實時的跟蹤。實驗結果表明,該算法可以較好的適應光線變化,目標尺度縮放或色彩質量很差等圖像序列中的目標跟蹤,改善了傳統基于色彩方向直方圖的局限性,提高了跟蹤算法的效率。圖2汽車運動區域直方圖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 和改進算法的對比Tab.1Contrast between Mean shift and improved algorithm算法對比平均每幀耗時平均每幀迭代次數原算法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馮志剛,周宏偉.圖像的分形維數計算方法及其應用J.江蘇理工大學學報,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.參考文獻: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目標跟蹤算法J.中國圖象圖形學報.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詹建平,黃席樾,沈志熙,等.基于均值漂移和卡爾曼濾波的目標跟蹤方法J.重慶理工大學學報:自然科學,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王寶榮,楊華,王一程,等.基于卡爾曼濾波與均值漂移算法的目標跟蹤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 濾波和邊緣直方圖的實時目標跟蹤J.清華大學學報:自然科學版,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 無線在同一設備中共存的應用。此模塊為5×7×1毫米小型封裝,擁有兩個接收端口和一個獨立發