基于粒子群算法和卡尔曼滤波的运动目标跟踪算法

1、2011年4月15日第34卷第8期ModernElectronicsTechnique现代电子技术Apr.2011Vol.34No.8基于粒子群算法和卡尔曼滤波的运动目标跟踪算法窦永梅,冀小平,杜肖山(太原理工大学信息工程学院,山西太原 030024)摘 要:针对目前一些常用的运动目标跟踪算法存在跟踪精度不高、实时性低、对遮挡问题处理不佳等问题,提出一种粒子群算法与卡尔曼滤波相结合的新的运动目标跟踪方法。利用卡尔曼滤波预测目标中心在下一帧图像中的位置,从而极大减少了搜索范围,并以该位置为中心建立目标搜索区域。然后以目标的灰度统计特征对目标模板和候选区域进行匹配,确保跟踪准确性。为了有效减少搜索

2、匹配次数、提高实时性,利用粒子群算法在搜索区域找到和目标模板最相似的区域,从而找到最优中心位置,并以该位置作为卡尔曼滤波的观测值,进行下一帧跟踪。仿真实验结果表明新算法显著提高了跟踪的实时性、精确性,并对部分遮挡能较好地处理。关键词:粒子群算法;卡尔曼滤波;运动目标跟踪;灰度统计特性中图分类号:TN911 34;TP391.41 文献标识码:A 文章编号:1004 373X(2011)08 0133 04TrackingAlgorithmofMovingObjectBasedonParticleSwarmOptimizationandKalmanFilterDOUYong mei,JIXiao

3、 ping,DUXiao shan(CollegeofInformationEngineering,TaiyuanUniversityofTechnology,Taiyuan030024,China)Abstract:Aimingattheinaccuracy,lowreal timeandpoortreatmentofcommonlyusedtrackingalgorithmofmovingob ject,anewtrackingalgorithmofmovingobjectbasedonparticleswarmoptimization(PSO)andKalmanfilterispropo

4、sed.ThepossiblepositionofmovingtargetcenterinthenextframeimageispredictedbyKalmanfilter,whichreducedthesearchscopegreatlyandsetsearchregionoftargetwhichisgeneratedaroundthecenterposition.Thenmatchingthetargettemplateandthecandidateregionswiththegraystatisticalcharacteristicstoensurethetrackingaccura

5、cy.Inordertoreducethesearchformatchingandimprovereal timeperformance,PSOisutilizedtosearchthebestareawhichismostsimilartothetargettemplateinthesearchregion,asaresult,theoptimalcenterisfoundandthebestpositionisusedasanobservedvalueofKalmanfilterfornextprediction.Theexperimentalresultsshowthatthenewme

6、thodiseffectiveandrobustandcanhandlepartialocclusionbetter.Keywords:particleswarmoptimization(PSO);Kalmanfilter;trackingofmovingobject;graystatisticalcharacteristic0 引 言计算机视觉领域中,运动目标跟踪是关键问题之一,其在视频编码、视频监控、军事、交通等领域有着重要而广泛的应用1。目标跟踪,就是在一段图像序列的每幅图像中找到所感兴趣的运动目标所处的位置,从而达到跟踪的目的。跟踪算法的实时性取决于匹配搜索策略和滤波预测算法,跟踪算法

7、的精度和鲁棒性很大程度上取决于对运动目标的表达和相似性度量的定义。但迄今为止,运动目标跟踪算法的鲁棒性、准确性和实时性的统一仍是尚未解决好和正在努力追求的目标。目前常用的跟踪算法如均值漂移算法(Meanshift)在目标跟踪过程中没有利用目标在空间中的运动方向和运动速度信息,当周围环境存在干扰(如光线、遮挡)或运动速度过快时容易丢失目标。连续自适应均值漂移算法(Camshift)在均值漂移算法的基础上虽结合目标色彩信息进行了改进,但需在开始前由人工指定跟踪目标2。粒子滤波算法在非线性、非高斯系统取得了较好的跟踪效果但计算量相对较大,实时性有待提高。而Kalman滤波算法可以方便地预测目标的位置

8、和速度,具有稳定、计算量小的特点,但是单纯使用Kalman滤波跟踪准确性不高。文献3中提出了一种基于遗传算法和卡尔曼滤波的运动目标跟踪算法,取得较好的效果。粒子群算法是一种高效的搜索算法,具有实现方便、收敛速度快、参数设置少的优点。与遗传算法比较,所有的粒子在大多数情况下可能更快的收敛于最优值4。综合以上考虑,本文提出了粒子群算法和卡尔曼相结合的新的运动目标跟踪算法。利用卡尔曼滤波预测目标中心在下一帧图像中的位置,并以该位置为中心建立目标搜索区域。然后以目标的灰度统计特征对目标,134现代电子技术2011年第34卷群算法在搜索区域找到和目标模板最相似的区域,粒子所在的位置即为最优中心位置,并以

9、该位置作为卡尔曼滤波的观测值,进行下一帧跟踪。1 算法原理依据1.1 卡尔曼滤波卡尔曼滤波是由一系列递推数学公式描述。其信号模型是由离散的状态方程和观测方程组成的5。设离散时间过程状态变量x R,状态方程可描述为:xk=Axk-1+Buk-1+wk-1(1)式中:xk是在k时刻系统的n维状态矢量;A是系统从k-1时刻到k时刻的n n一步状态转移矩阵;n l阶矩阵B代表可选的控制输入u Rl的增益;wk-1为k-1时刻时的过程激励噪声。设观测变量z R,得到观测方程:zk=Hxk+vkm n阶观测矩阵;vk是观测噪声。离散卡尔曼滤波器的工作原理,算法的具体实现是由时间更新方程和测量更新方程来实现

10、。具体形式如下:离散卡尔曼滤波器的时间更新方程:xkk-1=Axk-1+Buk-1T5mn一只鸟可以看作是每一个优化问题的解,也就是 粒子 ,所有的粒子都有一个被优化的适应值,每一个粒子还有一个速度v来确定它们飞行的方向和距离。然后,粒子们像鸟群在离食物最近的鸟周围搜索一样,追随当前最优粒子(离食物最近的鸟)在解空间中搜索7。PSO在每次的搜索过程中,粒子通过跟踪两个极值来更新自己:一个为粒子自身所找到的最优解,称为个体极值Pbest,另一个为整个种群当前找到的最优解,称为全局极值Gbest。例如,在一个D维的目标搜索空间中,每个粒子看成是空间内的一个点,设群体由m个粒子构成。设zi=(zi1

11、,zi2, ,ziD)为第i个粒子(i=1,2, ,m)的D维位置根据设定的矢量,根据设定的适应值函数计算zi当前的适应值,可衡量粒子位置的优劣;vi=(vi1,vi2, ,vid, ,viD)为粒子i的飞行速度,即粒子移动的距离;pb=(pb1,pb2, ,pbd, ,pbD)为粒子迄今为止搜索到的最优位置;pg=(pg1,pg2, ,pgd, ,pgD)为整个粒子群迄今为止搜索到的最优位置。在每次迭代中,粒子根据以下式子更新速度和位置:1kkvk+id=wvkid+c1r1(pbd-zid)+c2r2(pgd-zid)(8)zid=zid+vid(9)式中:i=1,2, ,m;d=1,2,

12、 ,D;k为迭代次数,r1和r2为0,1之间的随机数;c1和c2为学习因子;由于粒子群算法中没有实际的机制来控制粒子的速度,所以有必要对速度的最大值进行限制,设其为vmax,位置zi的取值范围为zminzmax;w为惯性权重,它起着权衡局部最优能力和全局最优能力的作用。大量实验表明,不把惯性权重设为定值,而是设为一个随时间线性减少的函数效果更好,惯性权重的函数形式通常为:maxmink(10)w=wmax-itermax式中:wmax为初始权重;wmin为最终权重;k为当前迭代次数;itermax为最大迭代次数2 算法的具体实现过程2.1 目标灰度特征和粒子群适应度函数目标灰度特征对目标的形变

13、、旋转等不敏感,具有良好的稳定性。在目标图像和候选图像匹配过程中,采用图像的灰度特征进行匹配8。设图像灰度级为L(0L-1),一般L为256。为加快运算速度,提高跟踪实时性,把灰度级映射为m级,如m=8,即把灰度级划分为8个级别。则目标模板直方图特征可表示为:q=qu,u=0,1,2, ,m-1。qu=i=14k+1kk+1(2)式中:zk是k时刻的m维观测信号矢量;H是k时刻的(3)式中:xk|k-1Pk|k-1=APk-1A+Q(4)为状态一步预测矢量,即向前推算状态变量;xk-1为k-1时刻的状态滤波值;Pk|k-1为一步预测均方误差阵,即向前推算误差协方差;Pk-1为k-1时刻的滤波均

14、方误差阵,由上可知时间更新方程主要完成预测。离散卡尔曼滤波器的测量更新方程为:Kk=Pk|k-1H(HPk|k-1H+R)xk=xk|k-1+Kk(zk-Hxk|k-1)Pk=(I-KkH)Pk|k-1TT-1(5)(6)(7)。式中:Kk为滤波增益矩阵;zk为观测值,它联合增益矩阵Kk来修正一步预测值xk|k-1,即由观测变量更新估计;Pk用来更新误差协方差。1.2 粒子群算法粒子群算法最早是在1995年由Eberhart和Ken nedy共同提出的,其基本思想源于对鸟类群体行为的研究6。假设一个场景:一群鸟在某一区域搜索食物,但是它们都不知道食物的具体位置,而知道当前的位置离食物到底有多远

15、,这样,找到食物最有效的方法就是搜索当前离食物最近的鸟的周围区域。PSO就是基于 b(x)-inu,u=0,1,2, ,m-1。其中b(xi)是第8期窦永梅等:基于粒子群算法和卡尔曼滤波的运动目标跟踪算法135位于点xi灰度值特征映射函数,设该点灰度值为g,则b(xi)=g;x表示取不大于x的整数; ( )为LKroneckerdelta函数;n是目标模板的像素总数。相应的,假设中心点在y点,则候选目标的灰度特征可以表示为p(y)=pu(y),u=0,1,2, ,m-1。其中pu(y)=n9i=1b(x)-i3nu,u=0,1,2, ,m-1,。采用Bhattacharyya系图2 程序流程图

16、xi是候选目标区域的像素点数来度量目标模板与候选目标区域的相似性,其定义为:m-13 实验结果与分析该算法实现都在Matlab7.0.1环境下,采用CAVIAR数据集中WalkByShop1front和OneLeave ShopReenter2cor两段视频测试序列为实验对象。视频序列的分辨率都为384 288,第一段视频序列中的跟踪目标为视频中出现的一个行人,跟踪从820帧开始到900帧结束,在820帧中由人工选定模板,大小为50 130像素,用矩形框来定位表示,实验中目标搜索区域的宽w设为32个像素,高h也设为32个像素。卡尔曼滤波的初始化为10:R=0.2845,0.0045 ,0.00

17、45,0.0455 ;Q=0.01*eye(4);P0=100*eye(4);A=1,0,0,0 ,0,1,0,0 ,dt,1,0,0 ,0,dt,0,1 ;H=1,0 ,0,1 ,0,0 ,0,0 (y)= p(y)q=u=0u(y)qu(11)于是,跟踪过程中的目标定位问题转化成了求使上式取得极大值的候选目标区域的问题。当 (y)越接近1,表示目标与候选区域越相似;当 (y)=1时,表示目标和候选区域完全相似。式(11)是作为粒子群算法采用的适应度函数。2.2 粒子群与卡尔曼滤波的结合利用Kalman滤波可以预测跟踪目标在下一帧图像的位置,其中心点设为(x0,y0),以该点为中心,取宽度为

18、w,高度为h的区域为搜索区域(如图1所示),也就是要在该区域找到和目标模板最相似的候选区域中心点。为了使用粒子群算法和卡尔曼滤波相结合,在该区域中心点(x0,y0)的周围撒一些粒子,如图1所示,再以每个粒子为中心,分别建立宽度为w,高度为h的搜索区域,这样就形成了m(粒子群规模)个候选区域,而以上知道粒子群的适应度函数为目标模板和候选区域的灰度特征相似性,这样就可以应用粒子群算法求一个最优解,即与目标模板最相似的运动目标中心(pg1,pg2),将这个最优解赋值给式(6)中的zk,再与Hxk|k-1做差,得到的差值结合增益Kk来修正卡尔曼的状态一步预测值xk|k-1,得到当前时刻的状态滤波值xk

19、,得到的xk再代入式(3)进行下一步的预测。具体的程序流程图如图2所示。矩阵A中dt=1,粒子群算法的种群大小设定为8,其中初始种群中一个点为卡尔曼预测的目标区域中心位置点,其他七个点在其周围随机选定。粒子群迭代总代数为30,c1=c2=1.4962,惯性权重中wmax=0.9,wmin=0.4。设在一代群体中,如果适应度最高的个体其适应度函数值大于设定的阈值0.88就停止迭代,表示已搜索到目标。当粒子群算法迭代次数达到最大迭代次数时,如果所有个体适应度函数值较小,可推测目标被部分遮挡,当最优个体适应度函数值低于0.65,则可推测目标被严重遮挡,在这两种情况下,直接把卡尔曼滤波的预测结果作为最

20、优值来处理。因文中采用的粒子群算法为连续优化算法,而图像像素位置为整数值,所以迭代过程中用floor函数对粒子的位置进行近似取整以对其候选区域精确化。实验表明此处理并不影响跟踪效果,结果如图3所示。从图3可以看出跟踪目标与图像背景比较相似,这种情况下利用本文的算法还是取得了较好的跟踪效果,只是在处理部分帧的情况下需要一定的运算时间,但是在实验中,平均每秒可以处理10帧左右的图像,可以基本满足跟踪实时性的要求。本文的粒子群与卡尔曼结合的算法还能有效处理,帧,从图1 候选目标中心搜索区域136中挑选几帧跟踪实验结果如图4所示。现代电子技术2011年第34卷跟踪效果,一般当运动目标运动速度快,方向变

21、换频繁时,搜索区域设置要大。4 结 语本文运用卡尔曼滤波预测运动目标中心在下一帧中可能出现的位置,结合目标灰度统计特性,以候选区域与目标模板的相似度作为粒子群算法的适应值函数,实行精确搜索,使运算速度大大加快,基本满足了跟踪的实时性和鲁棒性,并能处理部分遮挡以及短暂的全部遮挡。如何解决多目标跟踪,以及更加复杂的遮挡问题,进一步提高跟踪实时性是本文下一步的研究方向。图3 WalkByShop1front测试序列跟踪结果参 考 文 献1COLLNSR,LIPTONA,KANADEANDT.AsystemforvideosurveillanceandmonitoringVSAMfinalreportR.CarnegieMellonUniversity,2000.2李洪海.一种改进的CAMShift目标跟踪算法J.现代电子技术,2010,33(16):106 108.3胡建华,徐健健.一种基于遗传算法和卡尔曼滤波的运动目标跟踪方法J.计算机应用,2007,27(4):916 918.4纪震,廖惠莲,吴青华.粒子群算法及应用M.北京:科学出版社,2009.5赵树杰,赵建勋.信号检测与估计理论M.北京:清华大学出版社,2008.图4 OneLeaveShopReenter2cor测试序列跟踪结果6胡炜薇,杨雷,杨莘元,等.粒子群算法在多传感器多目标跟踪