Computer Engineering andApplications计算机工程与应用 基于空间直方图的粒子滤波目标跟踪算法 张楠,蔡念,张海员 ZHANG Nan,CAI Nian,ZHANG Haiyuan 广东工业大学信息工程学院,广'kl・I 5 10006 School of Information Engineering,Guangdong University of Technology,Guangzhou 5 1 0006,China ZHANG Nan。CA1 Nian,ZHANG Haiyuan.Target tracking using particle filters based on spatiograms.Computer Engi— neering and Applications,2011.47(21):210—213. Abstract:Spatiograms outperform the traditional color histogram,which contain color information and spatial layout of these colors for the target.In particle filters framework,a normal random drift model is utilized to describe the state model;a simi— larity function of spatiograms is used as the probability model for observation.A target tracking algorithm is proposed using particle filters based on spatiograms.Experimental results indicate that the proposed algorithm has better robustness than the traditional particle filters based on color histogram. Key words:spatiograms;particle filters;target tracking 摘要:空间直方图融合了目标的颜色信息和颜色的空间分布信息,比传统的颜色直方图更具有目标鉴别能力。在基于粒子滤 波算法的目标跟踪系统框架中,采用简单的随机漂移模型表示系统状态模型,通过空间直方图的相似度定义来建立系统观测概 率模型,提出一种基于空间直方图的粒子滤波目标跟踪算法。实验结果表明,相比传统的基于颜色直方图的粒子滤波算法,提出 的算法具有更好的鲁棒性。 关键词:空间直方图;粒子滤波;目标跟踪 DOI:10.3778/j.issn.1002.8331.2011.21.055 文章编号:1002—8331(2011)2l一02l0.04 文献标识码:A 中I矧分类 :TP391 1引言 目标跟踪是计算机视觉领域的重要的研究课题之一,在 视频监控、视频压缩编码、运动捕获、机器人定位等领域得到 广泛的应用。卡尔曼滤波及其改进方法是一类非常有效的目 粒子滤波算法采用非参数化的蒙特卡洛模拟方法来实现 递推的贝叶斯滤波,精度可逼近最优估汁,是解决非高斯、非 线性状态估计的有效技术,是一种稳健的跟踪方法,现已广泛 应用于各类甘标跟踪问题中 。文献【8】提出一种粒子滤波和 空间直方图相结合的目标跟踪算法,其状态转移模型采用二 阶自回归模型,引入了摄像机运动凶子。该凶子预测摄像机 运动,通过计算连续帧图像检测的目标特征相似度,利用重要 性采样原则采样得出,其计算过程与sitf特征相类似 1。摄像 机运动因子的引入,提高了跟踪的精度,对于摄像机不断运动 且运动不规律的目标运动场景有优势。然而,对于多数场景 来说,目标运动不剧烈,摄像机运动缓慢,采用简单的随机漂 标跟踪方法n。 ,但这些方法只适用于目标状态的概率分布是 高斯的情况。而在复杂场景中,多模式的视觉特征、复杂的目 标运动和严重的图像杂波等因素使得目标状态是非线性的和 非高斯的,从而该类目标跟踪算法很难稳健地跟踪目标。 颜色分布特征具有持久的稳定性,对物体姿态变化和非 刚性物体的变形都不敏感,具有旋转和尺度不变性的优点,因 此不少目标跟踪方法采用颜色直方图作为视觉特征之一 。 但如果场景中含有与目标颜色分布相类似的物体时,容易丢 失目标。为了解决这个问题,文献[4】提出空间直方图的概念, 并将空间直方图与mean shit算法相结合应用到目标跟踪 f中。空间直方图包含每个直方图区间的像素位置的均值向量 和协方差矩阵。这种空间信息不仅允许一般的变换,而且在 目标跟踪中比普通的直方图能获得更丰富的特征描述n1。但 移模型亦能到达精度要求,而计算摄像机运动 子复杂度显 然非常大,加大了整个算法的汁算复杂度,从而影响了跟踪算 法的实时性。凶此,提出一种基于空间直方图的粒子滤波跟 踪算法。在粒子滤波跟踪算法的系统框架基础上,首先采用 简单的随机漂移模型表示系统状态模型,并通过空问直方图 的相似度定义来建立系统观测概率模型。出于空问信息的引 由于mean shift算法在场景杂乱或目标遮挡时容易陷入局部 极值点,不能保证搜索结果的总体最优 。 用,相似度的定义更加严格,提高了相似度的可靠性,进而提 高了算法在目标跟踪中的鲁棒性,有效解决了遮挡问题。 基金项目:国家自然科学基金(the National Natural Science Foundation of China under Grant No.30600121);广东省自然科学基金(No.07301038, No.9451009001002667)。 作者简介:张楠(1985一),女,硕士研究生,主要研究方向为图像处理,模式识别等;蔡念(1976~),男,副研究员/博士后,硕士生导师;张海员 (1984一),男,硕士研究生。E—mail:xiaonan39@163.corn 收稿日期:2010 O1—13;修回日期:2010—05—11 张楠,蔡念,张海员:基于空间直方图的粒子滤波目标跟踪算法 2粒子滤波理论基础 2.1最优贝叶斯估汁 假没动态系统可以表示为: =3基j:窄问 图的粒子滤波算法 3.1 H标模 的构建。.j观测权值的计算 颜色特征是EI标跟踪的基本特征,其对目标的部分遮挡、 【1) F( U ), =H( , ) 旋转及尺度变化都是稳定的。颜色特征的统汁描述方法很 多,其中基于核的统汁描述是一种广泛应用的有效的方法 。 假设将视觉目标的颜色分布离散化为B级,B是颜色量化 等级,且定义颜色量化函数6(, ): {1,2,…, },表示把位 置, 处的像素颜色值量化并将其分配到颜色分布相应的颜色 其中, 表示k时刻目标状态向量, 为目标观测向量, 为系统噪声, 为观测噪声。F(・)为状态转移模型,近似描 述目标运动;H(・)为观测模型。如果对目标状态向量进行k 次观测,得到观测序列zl ={zl,z2,…, },那么目标跟踪问 题就是要求根据整个观测zl ,求得在k时刻目标状态向量 的一个最优估汁量 )。当目标状态转移模型和观测模型 概率化为状态转移概率p( 。)和观测概率p( ),那么 目标跟踪问题就可转化为递推计算后验概率p( : )的贝叶 斯状态估计问题。 若状态的初始概率密度函数为p( lzo)=p(Xo),则状态 预测方程为: p( : )=J ( 一,)p( 一 【z )dXk一 (2) 状态更新方程为: = (3) p( )=J p( )p( l : )dXk (4) 式(2)~(4)描述了最优 叶斯估计的基本思想,而对于非 线性、非高斯的动态系统,一般很难求得式(2)和式(3)的贝叶 斯最优解,但可用粒子滤波算法求得次优贝叶斯解。 2.2序贯莺要抽样算法 序贯重要抽样算法是一种蒙特卡罗方法,其核心思想是 利用一组带有相关权值的随机样本的加权和表示后验概率密 度p( :),得到状态估计值 。当样本数非常大时,这种概 率估算将等同于后验概率。 令{ , (Ⅳ为粒子数目)表示后验概率p( lz: )的 随机粒子,其由重要性函数g( : JzI: )产生。重要性函数是指 概率分布与p( lzI: )相同,概率密度分布g( : : )已知并 且容易从中采样的分布函数。重要性函数的概率密度分布 g( z )可作如下分解: g( : Zl: )=q(Xk .., : )・g( 。IZ,: ) (5) 假设状态符合马尔可夫过程,观测量条件独立,则权值递 推公式为: W t OC p( )p( t..—————— — ——— — ———————— ——— ————)p( 一。————————一lz ) = g( zl: )g( 一 IZi: ) W i 。㈦ q( 暇 zl :) 权值 归一化 W i:— (7) ∑ 从而后验概率密度可表示为: P(Xk[Z,: ) ∑ ( 一 ) (8) 当Ⅳ 时,估计值式(8)接近于后验概率密度p( IZi ) 真实值 级。凶此,给定目标状态 ,则其颜色分布P ={、 p } “=1.2. ,B 定 义为 : M I1 1 1 I1 =c∑尼m 1 (III ’ 1 06(, )~ (9) 其中,,表示视觉目标的中心,由目标状态 确定;M表示视觉 目标区域的总像素数,而h= + i表示目标区域的大小; k(・)表示核函数(一般选择高斯核函数); (.)为Kronecker Delta函数;C为归一化常数: C= .————————— ——_—一 M TlImlI) (1O) 没参考目标的颜色分布为{g } ,目标状态 的 . . 第i个采样 所对应的图像区域颜色分布为{p“} ,样 . .. 本 表示目标在第k帧的一个假定状态。从而样本 与参 考目标 的相似性度量,可利用其颜色分布的相似性度量建 立。Bhattacharyya系数是建立两概率分布相似性度量的有效 工具。样本 与参考目标的颜色分布的Bha ̄acharyya系数 定义为 】: B—— p =∑√p“矿 (11) “=l 相似性度量函数为: D ,g)=√1一P[P“,q“] (12) 由式(12)可知,该相似性度量函数仅是利用颜色信息,当 目标与背景颜色相近或被颜色相近的物体遮挡时,会作出错 误判断从而影响到跟踪结果。为解决上述问题,本文采用的 相似性度量函数在传统颜色直方图的基础上,融合了目标颜色 分布的空间信息,利用空间直方图的相似性进行相似性度量。 传统直方图可视为零阶空问直方图 ,二阶空问直方图包 括直方图每个bin的空间均值和协方差。这种空间信息能获 取目标更丰富的特征描述,从而提高了跟踪的鲁棒性 。 图像的空间直方图定 :—幅图像是—个二维映射I:x v, 像素 = , r对应值v。这些值的意义是随意的,可以是原始 灰度强度或像素颜色值或是预处理结果(量化、彩色空间变 换、小波系数等)。 一幅图像的二阶空间直方图可表示为一 : (6)=< 6, , >(b=l,2,…, (13) 其中,n 表示落入区间b的像素的个数, 和 分别是处于 区间b的像素的坐标的均值向量和协方差矩阵, 表示直方图 的区间个数。图像的普通的直方图,即零阶空间直方图可表 示为: (6)=,2^(6=1,2,・一, ) (14) 两空间直方图的相似度可由两直方图的相似f生的加权和 Computer Engineering andApplications计算机工程与应用 表刁 : 标颜色分布的颜色量化等级为l6,状态采样数为50,使用两段 p(h, :∑ P n3 为取自高斯分布(j , ,(15) 视频对本文的算法进行验证。 视频1序列图像数150,图像分辨率大小320x240,其环境 与目标的颜色信息差别较大。由图1可看出,基于颜色直方图 的粒子滤波跟踪算法和基于空问直方图的粒子滤波跟踪算法 在遮挡前后都能够跟踪到目标。 对于零阶空问直方图, =1;对于二阶空间直方图,没 : 6=F/exp{-l(u6一 茸‘( ^一 } (16) 其中叩是高斯标准化常数, ’= ’+ ) );求和值为两个 马氏距离(Mahalanobis distance)的平均值,两马氏距离分别 为X与x。之间的距离和 ’与 之问的距离; (” ,n3为直方 图区间的相似度,其计算方法很多。本文采用Bhattacharyya 系数: r ——● ): (17) f(∑ )(∑ ) I J l 由此可看出,式(15)与式(12)相比,由于空间直方图的相 似度量函数融入了空间信息,因此基于空间直方图的相似性度 量比传统基于颜色直方图相似性度量的定义更严格,更可靠。 对于颜色空间的选择,考虑到HIS颜色空间比RGB颜色 空间跟符合人的视频特性,并有效地广泛应用于图像处理和 计算机视觉领域中。本文采用HIS颜色空间,颜色量化等级 B=16x 16x 16。 3.2算法实现 本文的方法是在基于HIS颜色直方图的粒子滤波目标跟 踪算法基础上,融合了目标颜色的空间信息,-一l~●一l一提出基于空间直 方图的粒子滤波目标跟踪算法,实现对目标的跟踪。算法的 具体流程如下: (1)粒子初始化:初始时刻(后:0),在初始帧手动选取参考 目标,计算其颜色分布{矿) .:.…, ,统计空间信息,计算落入 每个区间的像素位置的均值向量和协方差矩阵。并根据先验 ●一_~_一分布t ̄Xo)建立初始状态样本集{矗, } .。 (2)粒子状态转移:在时刻七( 0),根据随机漂移模型和 粒子 一.,预测粒子 的状态。 (3)粒子权值计算:根据式(15)~(17)计算粒子权值并进 行归一化处理: =W i/∑ 。 (4)目标状态估计输出:计算k时刻目标状态的最小均方 误差估计: =∑ 。 (5)重采样“ :根据样本的权值 从样本集{ , ) 重 新抽取Ⅳ个样本,具体步骤如下: ①计算样本集{ , } .的累积权值, = + 。 ②在【0,1】上产生均匀分布的随机数c。 ③在样本集中搜索使 C的最,JV,并令 = 。 ④形成新的粒子集{ ,w2} .={X i',l/Ⅳ} 。 (6)令七= l,返回步骤(2)。 4实验结果及对比分析 本文 AMD Athlon 2800+CPU 1.6 Hz和内存512 MB 的Pc ̄_E使用Visual c++6.0与Opencv 数库编程实现。待 跟踪目标的参考目标模型在图像序列的第一帧手动选取,目 易对目标造成干扰,_ Frame 11 5 Frame 130 特别是遮挡物与目标颜色相近。图2中,l~叠一Fmme 145 (b)基于空间直方图的粒子滤波跟踪算法实验结果 图l视频1两种跟踪算法实验对比图 视频2序列图像数150,图像分辨率大小640x480,其环境 譬 I一墨一 第1帧和第l0帧为遇到遮挡前的跟踪结果,两种方法的跟踪 效果都不错;第70帧为部分遮挡的跟踪结果,通过对比,可看 Frame l00 Frame l20 Frame 140 (b)基于空间直方图的粒子滤波跟踪算法实验结果 图2视频2两种跟踪算法实验对比图 张楠,蔡念,张海员:基于空间直方图的粒子滤波目标跟踪算法 Frame Index I冬I3视频1跳踪洪左对比图 到此时基于颜色直方图的粒子滤波跟踪算法在跟踪qJ已出现 偏差,而基于空间直方图的粒子滤波跟踪算法仍能准确跟踪 到目标;第100帧为全部遮挡时的跟踪结果,两种方法都进行 了模板更新,继续跟踪目标;第120帧和第140帧为遮挡后的 跟踪结果,基于颜色直方图的粒子滤波跟踪算法目标丢失,跟 踪错误,而本文的算法,基于空间直方图的粒子滤波跟踪算法 始终能准确跟踪到目标,达到非常好的跟踪效果,进一步验证了 该算法的有效性与稳健性。这是凶为本文的算法不仅考虑目标 的有效特征,而且还考虑了特征的空间信息,其相似度测量函 数比传统颜色直方图Bhattacharyya系数具有更高的目标鉴别 能力,并结合粒子滤波的自身优点,从而能稳健地跟踪目标。 由以上两个实验结果对比可看出,本文的算法对于环境颜 色与目标颜色相差较大的场景和环境颜色与目标颜色相近的场 景,都能准确跟踪到目标,并有效解决了遮挡问题。为进一步 验证本文算法的有效性与稳健性,对基于空间直方图的粒子 滤波跟踪算法和基于颜色直方图的粒子滤波跟踪算法进行了 跟踪误差比较分析。本文采用的误差f”1为每帧真实目标中心位 r————■r—■———1 置z与跟踪的目标位置z’之间的距离e= 、 一r3。+【、,fl /J—f=J1 。。 图3显示了视频l对于两种方法的跟踪误差比较,可看出 基于颜色直方图的粒子滤波算法跟踪误差较大,波动较大;在 第ll5帧,目标出现全遮挡情况,基于空间直方图的粒子滤波 算法跟踪误差达到最大,但与基于颜色直方图的粒子滤波算 法跟踪误差相比较小,并且整个跟踪过程较为稳健。因此,对 于环境颜色与目标颜色相差较大的场景,虽然两种方法都能 跟踪到目标,但由跟踪误差对比可知,基于空间直方图的粒子 滤波算法与基于颜色直方图的粒子滤波算法具有较强的优 势。图4为两种方法对视频2的跟踪误差对比,可看出,基于 空间直方图的粒子滤波算法与基于颜色直方图的粒子滤波算 法具有明显的优势。这是因为空间直方图能够更有效描述目 标的特征。因此基于空间直方图的粒子滤波算法对于目标颜 色相差较大的场景和环境颜色与目标颜色相近的场景跟踪亦 能稳健跟踪,跟踪误差较小,有效解决了遮挡的问题。 5结论 空间直方图包含每个直方图区间的像素位置的均值向量 和协方差矩阵,比传统的直方图能获得更丰富的特征描述。 因此,在分析传统的基于颜色直方图的粒子滤波算法的基础 重 毒 Frame Index 图4视频2跟踪误座比较I冬l 上,在粒子滤波跟踪算法的系统框架基础上,提出了一种基于 空问直方图的粒子滤波目标跟踪算法。分别采用两个视频对 该算法进行了验证与对比。实验结果表明,该算法能够稳健 可靠地跟踪目标,尤其对于在场景颜色与目标颜色信息相近 且具有部分遮挡以及全遮挡等复杂的非线性、非高斯情况下, 亦具有良好的跟踪性能,优于传统的基于颜色直方图的粒子 滤波跟踪算法。 参考文献: 【1】Maybeck P S,Mercier D E.A target tracker using spatially dis— tributed infrared measurements[J].IEEE Tram on Automatic Con— trol,1980,25(2):222—225. 【2】Maybeck P S,Jensen R L,Hamly D A.An adaptive extended Kal— mall filter for target image tracking[J].IEEE Trans on Aerospace and Electronic Systems。1981,17(2):173.18O. 【3】Nummiaro K,Koller-Meier E,Van Gool L.An adaptive color- based particle filter[J].Image and Vision Computing,2003。21(1): 99.110. 【4】Birchfield S T,Rangarajan S.Spatiograms venus histograms for region—based traeking[C]//IEEE CVPR,San Diego,CA,USA,2005: ll58一l】63. 【5】Comaniciu D,Meer EMean shift:a robust approach toward lea— ture space analysis[J].IEEE Trnas on PAMI,2002,24(5). [6】Gordon N,Salmond D,Smith A.Novel approach to nonlniear and non—Gaussina Bayesina state estimation[J].1EE Proc F,2002,140 (2):107.113. 【7】Sanjeev M,Maskell S.A tutorial on particle filters for on-lnie non- lniear/non-Gaussian Bayesian tracking[J].IEEE Trans on Signal Pro- cessing,2002,50(2):174一l88. 【81 del-Blanco C R,Garcia N,Salgado L,et a1.object tracking from unstabilized platforms by particle filtering with embedded cam— era ego motion[C]//Proeeedings of the 2009 6th IEEE Interna・ tional Conference Ol1_Advanced Video and Signal Based Surveil— lance,2009:400-405. 【9】Carlin B P,Poison N G.A monte Carlo approach to normor- mal and nonlinear state-space modeling[J].JASA,1992,87(418): 493.5o0. [10】程建,周越,蔡念,等.基于粒子滤波的红外目标跟踪[J】.红外与毫 米波学报,2006,25(2):113.117.