第4卷第6期 智能系统学报 Vol.4.12 2009年12月 CAAI Transactions on Intelligent Systems Dec.2009 doi:10.3969/i.i8sn.1673-4785.2009.06.012 粒子滤波的视频目标跟踪算法研究 刘清，吴志刚，窦琴，熊燕 (武汉理工大学自动化学院，湖北武汉430063) 摘要：目标跟踪是计算机视觉和图像处理的一个重点课题，在视频监控、机器人视觉导航以及智能交通控制中具 有广泛的应用前景.通过粒子滤波技术，研究了如何整合颜色特征、前景信息和积分图运算等技术实现视频目标跟 踪的粒子滤波算法.在对目标进行分割中采用了混合高斯背景建模方法；同时结合积分直方图的计算方法对颜色特 征进行分段统计及相互遮挡的判断，实现基于粒子滤波的目标跟踪算法的优化，解决跟踪中诸如遮挡、光照变化、背 景干扰、尺寸变化等难以解决的问题.实验结果表明提出的方法达到了预期目标. 关键词：目标跟踪；粒子滤波；积分图；前景分割；视频 中图分类号：TP18:TP391.4文献标识码：A文章编号：16734785(2009)06053806 A particle filtering algorithm for tracking moving objects in videos LIU Qing,WU Zhi-gang,DOU Qin,XIONG Yan (School of Automation,Wuhan University of Technology,Wuhan 430063,China) Abstract:Tracking moving objects across video sequences is a key subject in computer vision and image process- ing.It is required for fields as diverse as video surveillance,robotic vision,navigation,and intelligent traffic con- trol.After studying particle filter technology,a moving object tracking algorithm based on a particle filter was de- veloped,integrating foreground information,color features and an integral image method.Gaussian mixture models (GMM)were employed for object foreground segmentation.By using an integral histogram algorithm,data for the color features in different sections were derived.Based on the features integral histogram,occlusion could then be analyzed and judged.The method presented can resolve occlusion caused by objects appearing among obstacles or with other objects,and to some extent overcome problems caused by changes in illumination,background and ap- parent size.Experimental results when tracking moving objects agreed well with predicted results. Keywords:object tracking;particle filter;integral image;foreground segmentation;video 近年来通过粒子滤波技术解决任何非线性模型间上得到一组粒子，每一个粒子都对应一个重要权 和非高斯噪声的目标跟踪成为研究的热点.粒子滤 值，最后对这些粒子加权求和来获得状态后验概率密 波的基本思想早在20世纪50年代就被提出，由于粒 度的估计3].而且A-Doucet等人还证明了当抽样粒 子数匮乏和计算量大等问题，应用受到制约.直到 子足够多时，粒子滤波算法是收敛的，收敛速度不受 1993年由英国学者Gordon等提出了一种新的基于顺 状态维数的限制.这些工作为粒子滤波的研究奠定了 序重要采样(sequential importance sampling,SIS)的 坚实的基础，并且高性能计算机的出现更进一步推动 Bootstrap非线性滤波方法「21，粒子滤波算法开始得到 了粒子滤波算法的发展和应用， 发展.2000年，A-Doucet等人又给出了基于SIS的粒 目前，将粒子滤波技术应用于目标跟踪领域的 子滤波通用描述，即采用蒙特卡罗方法求解贝叶斯估 研究已有一些研究成果.如在视频监控方面将改进 计中的多重积分运算，并利用SIS技术在动态状态空 的颜色直方图应用到粒子滤波技术中，来跟踪视频 中的运动目标4].其方法是将颜色统计信息即传 收稿日期：20090921 基金项目：高等学校博士学科点专项科研基金资助项目(20060497017)： 统的颜色直方图和颜色空间分布信息结合起来应用 湖」北省自然科学基金资助项目(2009CDB403). 于粒子滤波中，从而避免了跟踪过程中相似性背景 通信作者：刘清.E-mai:qi2000@163.com. 的干扰，减少计算的复杂性，使系统的目标跟踪更稳
第6期 刘清，等：粒子滤波的视频目标跟踪算法研究 ·539· 定.也有将信息融合技术和粒子滤波相结合的处理 E(g(xo:k)）=g(xo:k)p(ok1a:k)d山xo:k（4) 方法[6]，即将状态估计和信息融合技术相结合应用 于视频中多目标的跟踪，利用观测数据对状态估计 可以近似为 进行实时更新，力图解决复杂背景下多目标的交替 E(g(xo:)）=∑oig(x:k) (5) 出现的问题？-1o 1.2粒子滤波的目标跟踪算法实现 本文针对智能视频中的目标跟踪问题，研究并 本文以粒子滤波为基础，结合SIS方法和粒子 采用粒子滤波算法实现视频中人体的跟踪，同时通 重采样方法实现粒子滤波技术在目标跟踪上的应 过整合颜色特征和前景信息以及速度预测算法的优 用.其实现步骤如下： 化，在一定程度上来解决跟踪中难以解决的背景干 1)粒子的初始化 扰、遮挡、光照变化、尺寸变化等问题， 目标检测完成后得到目标的初始位置X。,在X。 1粒子滤波的目标跟踪算法 附近随机分布N个粒子，本文中N取为300. 2)粒子权重的获取. 1.1粒子滤波器原理 粒子滤波，也称顺序的蒙特卡罗方法(sequen- 假设系统处于X1,X2,…,X.等状态，对任意i= 1,2,…,n,称每个X:为一个粒子，要估计目标A的 tial Monte Carlo,SMC),是指通过寻找一组在状态空 准确位置X,需要对X的一些粒子X:进行运算，每 间中传播的随机样本对概率密度函数p(xe/久)进 行近似，以样本均值代替积分运算，从而获得状态最 个粒子X对应一个矩形框，将矩形框中前景的颜色 小方差估计的过程，这些样本即称为“粒子”. 进行统计，可以得到一个大小为16维颜色直方图向 设系统模型为 量H,其中目标的模板颜色直方图H也是一个16 k=f(xk-1)+"k-1,t∈N, (1) 维的单位矢量，作为历史跟踪信息.那么，H:的权重 zk=h(xk)+ng,t∈N. (2) W:可以理解为H和H:的内积，然后根据W:= 式中：∫是系统非线性状态方程，x是系统状态向 exp(10*)分别计算X1,X2,…,Xm,的权 量，'是独立于系统状态向量的系统噪声，hk是非 重W1,W2,…,W,其中表示内积运算 3)更新当前状态，得到新的位置值 线性观测方程，z:为系统的观测向量，是与状态 向量以及系统噪声无关的观测噪声向量.用数学语 将得到的X,X2,…,Xn和对应的权重W1,W2, 言描述粒子滤波：对于平稳的随机过程，假定k-1 …,W。,对系统状态进行估计.采用加权平均的方 时刻系统的后验概率密度为p(xk-1/久k-1),依据一 法：X=X1*W1+X2*W2+…+Xn*W这里X表 定原则选取个随机样本点，k时刻获得测量信息 示目标的位置点，计算得到的X是近似的后验概率 后，经过状态和时间更新过程，n个粒子的后验概率 估计即目标的当前位置 4)粒子重采样. 密度可近似为p(x/z.).随着粒子数目的增加，粒子 由于粒子的权重不同，进行处理的帧数越多时， 的概率密度函数逐渐逼近状态的概率密度函数，粒 权重就会越来越集中在小部分粒子上，大部分的粒子 子滤波估计即达到了最优贝叶斯估计的效果 权重很小，再进入下一步预测之前，需要让粒子的权 用{xk,w},表示系统后验概率密度函数 重相同，即每个粒子同样重要.这就是实现对粒子进 p(okk)的粒子集合，其中{奶k,i=1,…,N}是支 行重采样，即重新生成N个粒子1，X,…,X 持样本集，相应的权值为{w6,i=1,…,N},且满足 5)下一帧到来，状态转移，对粒子进行更新 含0=1，而={乡j=0,…,k}表示到时刻k系 进入下一个时刻预测时，需要对粒子进行更新， 统所有状态的集合，所以时刻k的后验密度可以近 即将X更新为X”,更新的原则是：变成X”的概率 似表示为 等于实际系统从状态！转移到状态X!的概率 p(x/xk-1),即根据式(6)对粒子进行更新： p(x0:kI1:)≈∑0i6(x0:k-k）. (3) X"=X'+v(k)+n, (6) 于是就有了一种表示真实后验密度p(o:k1 其中速度预测的方法为：记录目标前n帧的位置 :k)的离散加权近似表示，而那些关于数学期望的 (当frame<n时，n=frame),可以算出目标的平均 复杂计算，特别是带有复杂的积分运算就可以简化 速度vmen,平均速度与当前帧速度Vourmeet线性求和得 为和运算.如： 到目标的当前速度：
·540 智能系统学报 第4卷 )=（n-1)u+m 高跟踪的准确性.在目标模板与候选目标进行相似 (7) 度计算时，同时考虑上、下半身的相似度.以变量 6)重复回到第2)步 curRegion来标识上、下半身：curRegion=0,表示上 2 粒子滤波的目标跟踪算法优化 半身；curRegion=1表示下半身.例如，SumB[curRe- gion]、BH[bin][curRegion]表示B分量亮度的半身 粒子滤波是一个没有条件限制的大平台，可以 统计和B分量的半身直方图统计 整合各种各样的技术，本文以粒子滤波为基础，整合 2.4目标的互遮挡判断 颜色特征、前景信息、速度预测等多种技术，同时采 目标间是否发生互遮挡需要通过目标的互相关 用积分图运算方法对基于粒子滤波的目标跟踪算法 性信息来确定.如果2个目标的互相关性小，表示目 进行了优化. 标间不存在互遮挡或互遮挡的面积小；否则，要对2 2.1积分图运算提高算法的效率 个目标进行位置上的判断，通过空间位置上的重叠 积分图是一种用区域和来表示、便于快速计算 来判断目标是否真的存在互遮挡：当2个框的位置 的中间运算图.积分图中的像素点(x',y)的特征值 在x方向的重叠部分不少于coverRatio*Width且在 代表原图中对应像素点(x,y)左上角所有像素点的 y方向的重叠部分不少于coverRatio*Height时，判 特征值的和.那么采用积分图方式表达某一区域 断为相互遮挡.这里coverRatio为遮挡比例. R(x',y';x”,y”)的特征值则可表示为 2.5颜色直方图亮度补偿 R(x',y';x",y"）=Ⅱ(x",y")-Ⅱ(x',y") 目标跟踪中会发生图像整体亮度突变的情况， Ⅱ(x",y)+Ⅱ(x',y) (8) 比如天气的变化或是摄像头性能参数发生变化.如 由式(8)可见，只要将全局区域的特征进行积 果不对跟踪区域进行亮度上的补偿，相邻帧统计出 分值统计，要获得该区域内的任何子区域的特征统 来的同一目标的颜色直方图会有很大的不同.直方 计值，无论区域大小，只需要2次减法操作和一次加 图与模板直方图的相关性小，导致粒子权重小，影响 法操作即可.特别是对于粒子滤波这类算法，每一帧 跟踪结果.根据亮度差异的不同，将亮度补偿到直方 图片要取上百个粒子进行计算，常规的运算方法是 图的不同的bin中.亮度补偿的结果是相邻帧的同 每个粒子所代表的区域都要进行梯度、颜色的统计， 一目标直方图相似度得到提高 这样的运算量是很大的，积分图能大大降低计算量. 当粒子数增加时计算的代价也不大.在程序实现中 3实验及结果分析 也多次用到了：三颜色分量的亮度积分图、三颜色分 基于VC++6.0设计的视频跟踪试验平台上进 量的积分直方图、图像的梯度积分图等多种积分图 行跟踪试验，输人352*288大小、AVI格式的视频， 运算 按本文算法对运动中的人体进行大量的跟踪实验， 2.2前景在目标跟踪中的应用 实验的视频都是在人体衣服、姿态和光照等变化大， 采用混合高斯建模(GMM)方法分割前景不仅是 复杂场景、有大面积遮挡或目标间互遮挡等场景下 为了进行目标检测，将分割出来的前景应用到目标跟 进行的.对跟踪结果截图得到图像序列，抽取其中的 踪中也是很好的解决背景干扰的一个方法.前景点进 几组图片进行效果对比分析，体现粒子滤波优化算 行统计可以用来判断目标是否被障碍物遮挡，如果目 法的跟踪效果的优越性. 标被遮挡则该区的特征统计都为零，直接跳入下一个 3.1粒子滤波算法跟踪效果 区域.这既提高了算法效率，也避免了障碍物颜色与 为了验证粒子滤波跟踪的效果，选取不同场景 目标颜色相似参与统计会干扰跟踪结果的问题，同时 下的视频分别采用Mean-shift算法与粒子滤波算法 还避免了目标框跟踪到背景或障碍物上 对目标进行跟踪比较」 2.3目标的分段直方图表征 图1是光照变化情况下分别给出了第35、61、 在视频分析算法中，目标特征的选择对于目标 81、95、127帧采用Mean-shi讥算法的跟踪情况.在图 检测、分类是至关重要的.好的目标特征表达应当能 像序列中，目标从暗处走向光线强烈处.第61帧跟 很好地代表目标，具有鲁棒性强、计算量低以及能应 踪框开始漂移，第81、95帧目标框继续远离目标，第 用到高效的算法中等特点， 127帧显示目标框与目标全部分开，发生了失跟踪. 目标的分段直方图表征是将目标分为上、下半 显见，Mean-shift方法在跟踪的鲁棒性方面不足，在 身分别统计，这样的直方图更为准确地描述目标，提 复杂场景下易发生错误的跟踪
第6期 刘清，等：粒子滤波的视频目标跟踪算法研究 ·541· 对同样的情况采用粒子滤波算法进行跟踪，得 将亮度补偿到直方图的不同的bin中，这样使相邻 到的效果如图2所示.显见粒子滤波跟踪算法在这 帧的同一目标直方图相似度得到提高，所以较 种情况下能很好地跟踪人体.因为在粒子滤波跟踪 Mean-shit方法具有更强的鲁棒性。 中，当图像整体亮度突变时，根据亮度差异的不同， 图1光照变化下Mean-hi近算法跟踪 Fig.1 Mean-shift algorithm for tracking in the light changes 图2光照变化下的粒子滤波算法跟踪 Fig.2 Particle filter algorithm for tracking in the light changes 3.2粒子滤波优化算法的跟踪效果 比说明优化后的效果. 通过试验显示单纯依靠基本的粒子滤波算法还 图3给出的是背景干扰场景下的跟踪效果图， 是不能很好地解决复杂场景、大面积遮挡和目标间 分别是视频的第109、132、230、401、455帧.该图像 互遮挡等难点问题.本文对基本的粒子滤波跟踪算 序列是要验证前景解决跟踪中背景干扰的问题. 法进行了多方面的优化，下面抽取2组图片序列对 (a)未加入前景的跟踪效果图 (b)加入前景优化的跟踪效果图 图3背景干扰场景中的对比跟踪效果图 Fig.3 Comparative tracking effect pictures in the background interference scene 图3(a)是未加入前景的跟踪效果图，在第230 化的跟踪效果图，非前景点不参与直方图统计，背景 帧处跟踪框开始出现漂移，目标逐渐离开复杂背景， 相似对目标跟踪不造成干扰，如图所示目标始终被 到第401帧时目标框大部分还是停留在背景上，因 稳定地跟踪。 为该背景处的颜色直方图与目标模板更为相似.到 图4给出的是场景中出现遮挡物的跟踪效果 第455帧时目标彻底跟丢.图3(b)是加入了前景优 图，分别是视频的第50、78、115、119、145帧.该试验
542. 智能系统学报 第4卷 验证了通过直方图分段统计和前景应用优化的共同 跟踪框远离目标，发生了失跟踪.而通过统计前景点 作用在解决遮挡问题时的有效性。 的颜色，并针对下半身进行统计，并与模板的下半身 图4(a)是对跟踪框内的点进行整体统计并未 进行相似度计算，可以准确匹配目标.图4(b)是加 加入前景的跟踪效果图.由于篮球框的大面积遮挡， 入了前景和分段统计优化的跟踪效果图，当目标被 而且目标衣服颜色与篮球框颜色相似，在第115帧 严重遮挡时，该区域的特征统计都为零，直接跳入下 目标进入遮挡区域后，跟踪框开始停留在篮球框上 一个区域，即除去遮挡部分的统计并对对应的区域 面.目标逐渐离开篮球框的遮挡区域后跟踪框始终 进行匹配，目标能被跟踪住.目标走出遮挡区域后， 在篮球框上面来回移动，第145帧时人走出遮挡区， 也能被稳定地跟踪 (a)整体颜色统计的跟踪效果图 (b)分段和加入前景的统计的跟踪效果图 图4不同目标特征统计的对比跟踪效果图 Fig.4 Comparative tracking effect pictures of statistics characteristics of different objects (a)未经过互遮挡处理的跟踪效果图 (b)经过互遮挡优化的跟踪效果图 图5目标间发生互遮挡的对比跟踪效果图 Fig.5 Occurred inter-cover between the objects for comparative tracking effect pictures 图5是多目标跟踪效果.该视频中有2个跟踪 始，跟踪框开始逐渐漂移到对方的目标上；在第181 目标，在跟踪过程中发生了互遮挡，图像序列分别是 帧时2个搜索框几乎重叠在2个目标的中间；第 视频的第112、167、181、190、215帧.图5(a)是未经 190帧目标开始分开，搜索框才又开始向各自的目 过互遮挡处理的跟踪效果图，2个目标在行走当中 标移动. 发生了互遮挡，虽然目标在分开后又重新分别跟踪 图5(b)是经过了互遮挡处理跟踪效果图.通过 上.但是在逐步发生互遮挡的过程中，从第167帧开 目标的互相关性计算判断目标间进行了互遮挡，通过
第6期 刘清，等：粒子滤波的视频目标跟踪算法研究 ·543· 位置判断黑衣目标被白衣目标遮挡，在对黑衣目标进 Application 2008,Shanghai,2008:477-480. 行统计时除去被遮挡的部分，这样可以更准确地表达 [5]ZHUANG Yan,WANG Wei,XING Ruizhi.Target tracking 和匹配目标，如图5(b)所示，跟踪框能始终准确地跟 in colored image sequence using weighted color histogram 踪各自的目标 based particle filter[C//IEEE Interational Conference on 由以上实验结果表明，基于优化后的粒子滤波算 Robotics and Biomimetics 2006,Kunming,17-20:1488- 1493. 法在跟踪时取得了较好的效果，在一定程度上能解决 [6]LOZA A,PATRICIO M A,GARCIA J,MOLINA J M.Ad- 背景干扰、光照变化、遮挡等跟踪的难点问题， vanced algorithms for real-time video tracking with multiple 4结束语 targets[C]//Interational Conference on Control,Automa- tion,Robotics,and Vision.Hanoi,Vietnam,2008,17- 随着智能视频监控的广泛兴起，目标跟踪问题 20:125-131. 已成为计算机视觉领域中的热点问题.本文通过对 [7]陆军，李凤玲，姜迈.摄像机运动下的动态目标检测 粒子滤波技术的探讨，研究复杂背景下的运动目标 与跟踪[J].哈尔滨工程大学学报，2008,29(8)：831 的跟踪问题，实现了视频序列中基于粒子滤波的人 835. 体目标跟踪；而且通过对算法进行优化改进，在解决 LU Jun,LI Fengling,JIANG Mai.Detection and tracking of 背景干扰、光照变化、遮挡等跟踪的难点问题上有一 moving targets with a moving camera[J].Journal of Harbin Engineering University,2008,29(8):831-835. 定的成效，研究的跟踪算法达到了预期的效果.但是 [8]焦安霞，姜弢.视频序列中动目标快速跟踪新算法的 对粒子滤波理论的深入研究，尤其是重要性函数的 研究[J].应用科技，2008,35(12)：7-10. 选取以及粒子的重采样方式直接影响粒子滤波性能 JIAO Anxia,JIANG Tao.A fast tracking algorithm for video 的高低，如何更有效地选取合适的重要性函数和重 sequence moving object[J].Applied Science and Technolo- 采样方式是提高基于粒子滤波的跟踪算法性能的关 g8,2008,35(12):7-10. 键，是目前粒子滤波跟踪算法研究的重点；同时如何 [9]邓文坛，张三同，余纯.一种改进的粒子滤波跟踪算法 更好地将粒子滤波方法和其他方法相结合来解决跟 的研究[J].自动化技术与应用，2008,27(3)：84-87. 踪中的难点问题，以达到更好的跟踪效果也是值得 DENG Wentan,ZHANG Santong,YU Chun.A modified 深人研究的 particle filtering algorithm for tracking[J].Techniques of Automation and Applications,2008,27(3):84-87. 参考文献 [10]王健，金永镐，董华春，权太范.进化粒子滤波算法 在雷达目标跟踪中的应用[J].现代防御技术，2007,36 [1]GORDON N.A hybrid bootstrap filter for target tracking in (2):115-118. clutter[J].IEEE Trans on AES,1997,33 (1):353-358. WANG jian,JIN Yonghao,DONG Huachun,QUAN Tai- [2]GORDON N,SALMOND D,SMITH A.Novel approach to fan.Evolutionary particle filter algorithm in radar target nonlinear non-Gaussian Bayesian state estimation[J].IEEE tracking[J].Modern Defence Technology,2007,36(2): Proceedings on Radar and Signal Processing,1993,140: 115-118 107-113. 作者简介： [3]GODSILL D S,ANDRIE C.On sequential Monte Carlo 刘清，女，1966年生，教授，博士， sampling methods for Bayesian filtering[J].Statistics and 主要研究方向为智能控制技术、智能移 Computing,2000,10(3):197-208. 动机器人、智能视频监控、计算机实时 [4]XU Dongbin,HUANG Lei,LIU Changping.Object tracking u- 控制和信息系统集成。 sing particle filter based on color correlogram[C]//Second In- ternational Symposium on Intelligent Information Technology