基于方向直方图的Meanshift目标跟踪新算法

1、基于方向直方图的Mean shift 目标跟踪新算法秦臻1,2,曹剑中1摘要:Mean shift 算法是一种非参数密度估计算法,可以实现快速的最优匹配。为了有效地将Mean shift 算法应用到灰度图像中,使用空间分布和纹理信息作为匹配信息,提出了一种基于空间方向直方图的Mean shift 跟踪新算法。利用卡尔曼滤波器来获得每帧目标的起始位置,再利用Mean shift 算法得到跟踪位置。实验结果证明,该算法在目标运动较快,目标尺度变化的情况下仍能稳定、实时、高效地跟踪目标。关键词:图像处理;目标跟踪;Mean shift ;卡尔曼滤波;方向直方图中图分类号:TP751文献标识码:A文章

2、编号: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稿件编号:201104069作者简介:秦臻(1986,男,陕西西安人,硕士研究生。研究方向:图像压缩处理。目标的实时跟踪在计算机视觉跟踪领域有着非常重要的应用,近年来在目标跟踪领域提出了很多好的算法,然而很多算法由于计算复杂,都

6、未能应用到对实时性要求较高的场合。Dorin Comaniciu 将Mean shift 算法引入到目标跟踪领域1-2,极大地减少了跟踪算法的计算量。Dorin Comaniciu 提出的算法是以彩色直方图作为特征来实现目标的识别与定位,而灰度直方图所包含的图像信息单一,使得Mean shift 算法很难应用于灰度图像,限制了Mean shift 算法的适应环境。经典的Mean shift 算法要求相邻两帧间目标模板区域必须重叠,在目标较快运动的情况下容易跟丢目标;在目标出现尺度变化的复杂条件下,其跟踪结果往往出现偏差,甚至跟踪失败。笔者提出了基于空间方向直方图的Mean shift 跟踪算法

7、,使用空间统计信息作为匹配信息,结合卡尔曼滤波预测目标位置。实验结果表明,该算法在目标运动较快,光照变化和尺度缩放等情况下可以对目标准确的跟踪,具有良好的鲁棒性和效率。1Mean shift 算法概述Mean shift 算法是一种非参数概率密度估计算法3,可以通过迭代,快速地收敛于概率密度函数的局部极大值。算法的跟踪过程就是不断寻找概率密度局部最大值的过程,其步骤如下。在首帧图像中确定被跟踪的目标区域,可通过手工选择矩形框的方式来确定目标区域。目标模型可以描述为在目标区域上的所有特征值的概率值,用目标模型的特征值估计的概率密度为:q u =C ni =1K(x 0-x i/h 2b (x i

8、 -u (1其中,K (x 为核函数的轮廓函数;b (x i 是表示像素x i 属于哪类特征值;h 表示核函数的带宽4;b (x i -u 是用于判断目标区域中的任意像素x i 的颜色值是否等于第u 个特征值;候选模型的描述类似式(1,计算当前帧中,搜索窗口的特征值的概率密度为:p u (y =C n n hi =1K(y -x i/h 2b (x i -u (2电子设计工程Electronic Design Engineering-168-相似性函数用于描述目标模型和候选模型的相似性度量,可使用Bhattacharyya 5系数作为相似性函数,即(y =(p (y ,q =mu =1p u

9、(y q u姨(3 其值在01之间。(y 的值越大,表示两个模型越相似。为使(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 0姨b (x i -u (5令f n ,h =n hi =1C h i k(y -x i/h 2姨姨(6可以看出,求相似性函数最大就是要求式(6最大,通过对相似性函数求最大值,即可计算

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 (x =-k (x ,这样目标区域即可由初始位置逐步移动到真实的目标位置。根据式(4可知,相似性函数(y 0在处先进行泰勒展开,而泰勒展开要求是在邻域内展开,这就限制了起始点y 0和y 的距离不能太大。2基于方向直方图的跟踪方向直方图给定一组灰度图像I ,定义像素的梯度方向角为=arctan坠f /坠y 坠f /坠x(8式中坠f /坠y 和坠f /坠x 分别是该像素处沿y 和x 方向的梯度,可以通过梯度算

11、子来获得。梯度方向角的取值范围为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 可根据经验来选择。如果采用的量化方向为16个,方向编码的间距取/8。用Mean shift 跟踪目标模型和候选模型时,在跟踪区域用方向编码来描述目标。方向编码示意图如图1所示。1预测跟踪坐标利用前一帧图

12、像中目标的位置信息来预测在当前帧中目标的位置信息。先验估计计算公式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 是先验估计误差的协方差;P k 是后验估计误差的协方差。Q 是过程激励噪声协方差矩阵。2获得当前帧的跟踪坐标以1预测得到的跟踪坐标为起始搜索位置,应用基于方向直方图的Mean shift 跟踪算法,得到当前帧目标实际的跟踪坐标

13、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 为卡尔曼增益;H 表示状态变量x k 对测量变量Z k 的增益矩阵。3实验结果与分析本文利用灰度图像序列来验证新算法的跟踪效果8-9。图2为图像跟踪区域的灰度直方图和方向统计直方图。图3是汽车图像序列的跟踪结果。方向直方

14、图简化了目标的表述方式,减少了Meanshift匹配时的bins 的个数,因而降低了跟踪过程中的匹配复杂度,有利于提高跟踪速度,并且利用了目标运动的方向特性,跟踪时对目标方向变化不敏感。图1运动方向编码示意图Coding schemes of movementdirection电子设计工程2011年第12期 在图3中,图(a 、(b 、(c 为原算法的跟踪结果;图(d 、(e 、(f 为新算法的跟踪结果。原跟踪算法中,在汽车运动较快的情况下,跟踪过程中目标存在部分出框的问题;而新算法在目标运动速度过快和目标尺度变化的情况下仍然可以稳定的跟踪到目标。表1和图4是Mean shift 算法和新算法

15、的跟踪效率对比分析。图(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 groupsalgorithm表1Mean shift 和改进算法的对比Tab.1Contrast between Mean shift and improved algorithm算法对比平均每帧耗时平均每帧迭代次数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冯志刚,周宏伟.图像的分形维数计算方法及其应用J.江苏理工大学学报,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.参考文献: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、.一种基于运动矢量分析的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 vector的目标跟踪方法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 filt

23、er J.Journal of Chongqing University of Technology :Natural Science ,2010,24(3:76-80.法的目标跟踪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、实时目标跟踪J.清华大学学报:自然科学版,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页!Avago Technologies 推出市场上首个WiMAX 共存前端模块Avago Technologies 宣布推出一个完整射频前端模块(FEM,用于手机或便携电脑中的WiMAX 。这款新的AFEM-S257模块专用于WiMAX 和其他蜂窝式无线及WiFi 无线在同一设备中共存的应用。此模块为5×7×1毫米小型封装,拥有两个接收端口和一个独立发射端口,非常适用于频率范围在2.52.7GHz 频率