基于粒子滤波和在线训练支持向量机的目标跟踪新方法

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于粒子滤波和在线训练支持向量机的目标跟踪新方法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：序列图像中运动目标跟踪的有效性和鲁棒性是一个非常富有挑战性的课题。为提高在运动背景条件下视觉目标跟踪的性能，克服复杂环境对跟踪算法准确性的影响，提出了一种基于粒子滤波和在线训练支持向量机的目标跟踪新方法。从目标的特征描述和提取着手，引入了积分直方图快速提取特征的方法，加快粒子滤波器运行速度，满足一定的实时性要求。同时，分析了运动背景条件下具有代表性的跟踪算法的本质和特性，结合目标识别创新性地提出在线训练支持向量机的方法，通过在线识别信息和跟踪信息的融合保证算法具备较强的鲁棒性。实验结果表明，该算法能有效的解决动态背景条件下遮挡、光照变化和运动模糊等复杂情况下，对目标进行准确、有效、近乎实时的跟踪。

关键词：目标跟踪；粒子滤波；支持向量机；积分直方图

中图分类号：TP391文献标识码：A文章编号：1009-3044(2008)32-1190-04

New Target Tracking Algorithm Based on Particle Filter and On-line Training Support Vector Machines

ZHENG Jian-bin

(School of Software Engineering,Tongji University, Shanghai 201804, China)

Abstract: It is a challenging task to track the object effectively and robustly in sequence image. In order to improve the performance of target tracking under moving background circumstance, and get over the influence of veracity of tracking algorithm under intricate conditions, This paper presents a new target tracking algorithm based on particle filter and on-line training support vector machines. This paper begins with object feature description and extraction; introduce some quick feature extraction ways to improve the speed of particle filter, thus achieving almost real-time performance. Meanwhile we discusses essence and speciality ofsome classical object tracking algorithms under moving background circumstance, we also guarantee the robustlyof the new algorithm by combining the classification information which from online-training Support Vector Machine and the tracking information. Experiments proved the new algorithm can deal with intricate conditions, such as occlusion, luminance changing, and abrupt motion blur happen, and track objects accurately, effectively and real time.

Key words: target tracking; particle filter; support vector machines; integral histograms

1 引言

序列图像中进行运动目标的跟踪是计算机视觉中一个必不可少的关键技术，一直以来备受人们关注。目标跟踪技术被广泛用于军事、科技、工程和经济等多个领域。然而目标跟踪检测存在两大难点：其一是观测模型和目标的概率分布的非线性和非高斯性，其二是遮挡和模糊现象。最常用的序列图像目标跟踪多采用卡尔曼滤波。虽然先后出现了广义卡尔曼滤波(EKF)和无迹卡尔曼滤波(UKF)，但都因为他们不能对实际非线性函数或概率分布进行精确的描述，或是要求目标状态必须满足高斯分布而导致对于复杂背景或是有遮挡等造成的非高斯和非线性问题的性能表现不佳。另一种常用的非线性滤波方法是粒子滤波(Particle Filter,简称PF)[1]。该方法根据目标性质所生成的概率统计来跟踪目标，而不受场景中具有相似性质的其它物体运动的影响。因而被广泛应用到航空导航、机器学习和视频监控等领域。除计算量大而导致实时性能差外，样本贫化现象是PF的最大缺点。减轻该缺陷影响的最简单方法是加大样本集，但这将降低系统的实时性能。

本文针对PF的实时性差和样本贫化提出了基于粒子滤波和在线训练支持向量机的目标跟踪新方法。该方法将在线训练支持向量机(SVM)和粒子滤波相结合，从而获取目标的识别和跟踪信息的联合数据分布图，并采用积分直方图方法进行快速的目标区域的直方图提取。大量的实验表明，该方法在保持了原有跟踪鲁棒性的前提下，很好的解决了样本退化问题和不佳的实时性能，同时在出现遮挡和模糊复杂情况下也具有非常良好的鲁棒性。

2 粒子滤波

粒子滤波是贝叶斯估计基于抽样理论的一种近似算法，它将蒙特卡罗和贝叶斯理论结合在一起。其基本思想是用一组带有相关权值的随机样本的加权和来表示后验概率[2]。当样本数目非常大时，这种概率估计将等同于后验概率密度。其运作过程描述如下：

其中，权值wjk通过重要采样法，从重要密度函数q(Xk|Z1:k)中采样选择。如果样本Xjk可以由重要密度q(Xk|Z1:k)取得，则第i个粒子的权值可以定义为：

如果重要密度函数可以做如下的分解：

q(Xk|Z1:k)=q(Xk|Xk-1,Z1:k)q(Xk-1|Z1:k-1)

若满足q(Xk|Xk-1,Z1:k)=q(Xk|Xk-1,Zk)，即重要密度函数仅依赖于Xk-1和Zk，则只需存储样本Xik，而不需要存储样本Xik-1及过去的观测值Z1:k-1，从而可以极大地减少计算存储量。

此时权值修正为：

所以，粒子滤波算法主要是由重要密度函数获取样本，并随着测量值的依次到来迭代求得相应的权值，最终以其加权和的形式表征后验概率密度，得到状态的估计值。

3 特征选取

3.1 Haar特征

Haar型特征是P．Viola 在文献[3]中提出的一种简单矩形特征,因类似于Haar小波而得名。Haar型特征的定义是黑色矩形和白色矩形在图像子窗口中对应的区域的灰度级总和之差,它反映了图像局部的灰度变化。这些特征原形在x和Y方向独立的缩放整数倍数，组成新的特征，一直放大x和Y方向到24。每一个特征在窗口每一个位置计算。故如此多的特征数对采样很多的局部区域时效率是很低的。好的特征选取方法是分类的关键，本文引入了积分直方图快速提取特征的方法。

3.2 积分直方图算法

对于Haar小波特征的来说，Viola等在文献[3]中提出的积分图已经被证明为切实有效的快速提取算法。而本文所提的积分直方图算法是基于积分图算法的而提出的。以下加以说明：

首先建立全局的积分直方图，即对于一定区域内的全局目标建立直方图的累加直方图，建立方法同文献[1]中的积分图建立方法，只需要将灰度值的总和换成需要的直方图的特征级数的总和，直方图的类型可以是上文叙述的多种中的某种，然后在计算局部区域的特征时采用积分图中使用的查找表的方法，通过简单的加减方式就可以得到目标区域的直方图。这种方法在一张较大的图像上需要采样很多的局部区域时具有非常明显的节约计算时间的优势，因为只要计算一次全局的积分直方图之后便可以通过查找的方式得到每一个图像中的局部细节的直方图。

积分直方图建立查找表快速提取直方图的方法的如下：

1）对于全图或者目标周围区域建立积分直方图，将积分直方图存入内存中。

2）确定目标的区域，在内存中积分直方图中查找得到使用四块矩形区域的内存位置

3）通过四块矩形区域的加减运算得到目标区域的直方图。

利用该方法，粒子滤波器的抽样特性便能迅速地提取所抽样的目标区域的直方图。

3.3 基于主成分分析方法的特征降维

特征提取的目的是希望通过变换把原来的特征变换到新的特征空间，使得特征的可分性更好。提取特征后希望能对原始特征进行降维压缩，用尽量少的数据来表示尽量多的信息，在保证特征数据不失真的前提下起到减少计算量的作用。本文采用主成分分析方法[4] (Principle Component Analysis ,PCA)，数据压缩和降维中的一种最优正交变换，是一种基于目标统计的方法。其目的是基本思想是通过变换，将实测的多个指标，推导出新的变量，用新的潜在的相互独立的变量线性组合来表示原多个实测指标的主要信息。这些新的变量成分按重要性降序排列，是原始变量的线性组合而且互不相关，当使用这些新变量去重建原始变量时使得均方误差最小。这就导致了用较少维数的近似表示原来的对象，起到数据降维的效果，以此在特征的提取阶段产生时间上的优势。

利用主成分分析的方法提取目标特征的步骤如下：

首先，设xi为初步得到的目标的特征参数，共有p个，记为X(x1,x2,…,xp)；

其次，计算X的协方差矩阵∑，计算∑的特征值及相应的正交单位化特征向量分别为：λ1≥λ2≥λ3≥,…λp≥0和e1,e2,e3,…ep。

本文进行特征降维时使用将得到的原始特征值进行压缩，使得降维后的数据满足跟踪算法的实时性需要。

4 在线训练支持向量机

4.1 支持向量机

在20世纪90年代，统计学理论的创立人之一，AT&T 实验研究中心的Vapnik创立了支持向量机(SVM)学习理论[5]。它是一种分类器，和传统的分类器如神经网络相比，它从理论上解决了神经网络难以控制自身推广能力的问题。SVM是统计学习理论中最年轻，也是最实用的部分，正处于发展阶段。

支持向量机的基本思想是通过非线性变换将输入空间的变换到一个高维的特征空间，然后在这个新的高维特征空间中求取最优分类超平面。所谓最优分类超平面就是要求分类线不能将两类样本无错误的分开，而且要使两类之间的距离最大。设线性可分样本集为(xi,yi), i=1,2,…,n, x∈Rd, y∈{+1,-1}是类别标号。SVM的判别函数(分类器)表达式为：

式中：k(xi・x)为核函数，用以实现非线性变换，常用的核函数有以下几种:

1）线性内积函数K(x,y)=x・y

2）多项式内积函数K(x,y)=[(x・y)+1]d

3）径向基内积函数K(x,y)=exp{-|x-y|2/σ2 }

4）二层神经网络内积函数K(x,y)=tanh(k(x・y)+c)

ai为每个样本对应的Lagrange系数。两类样本中离分类面最近的点且平行于最优分类面的超平面上的训练样本就称为支持向量(Support Vectors)，即少量不为零的ai对应的样本xi，将最终影响划分结果。

由于SVM本质上是一个非负的二次型优化问题，在理论上可以得到全局最优解，因此SVM不存在局部最优化问题。另外，SVM的重要特征之一就是解的稀疏性，即需要少量样本就可以构成最优分类器，这使得有用的样本数据将大大压缩。因此，支持向量机在解决小样本、非线性及高维模式识别问题中表现出许多特有的优势，并且能够推广到函数逼近和概率密度估计等其他机器学习问题中。本文采用Platt提出的SMO(Sequential Minimal Optimization)算法训练SVM。

4.2 在线训练

在线训练和识别信息的跟踪思想是阶段目标跟踪邻域内研究的热点，通过分类器训练跟踪过程中的目标模板，一方面提供实时的数据更新，另外能为跟踪过程提供识别和检测的信息，使得跟踪中目标分布获取更为真实可信。

本文在传统支持向量机离线训练跟踪目标的基础上，提出了在线训练这一思想。采用C-SVM算法对目标特征数据进行在线训练，其训练流程如图1所示。

通过在线的训练分类器，可以不断的对于目标模板的识别进行更新，另外也可以为跟踪提供识别的打分依据，最终要的是通过不断的训练和在线的更新模板在时间序列中不断自适应变化，使得算法在目标处于光照变化，复杂背景干扰等情况下能够继续稳定地运行。

5 基于粒子滤波和在线SVM目标跟踪算法

5.1 算法设计流程

本文提出了一种基于在线识别和训练的动态背景下的目标跟踪算法是称为基于粒子滤波和在线SVM的目标跟踪算法。所使用的方法和工具包括前面介绍和分析的积分直方图，主成分分析降维，粒子滤波器算法，支持向量机等。

整个跟踪算法的设计分析如下:

首先，假设已经得到了需由此查找得到各个抽样目标区域的直方图，通过特征提取和降维获取候选目标的特征，对于每个抽样目标运行支持向量机进行判别，给出正负打分和其类属。将上述两个打分分布进行联合，获取一个联合分布，作为粒子滤波器的粒子加权，然后结合加权的粒子位置给出目标在本帧中的最终区域。

在此过程中，每隔一定帧数对于支持向量机进行训练更新，获得更新好的支持向量，用于模板的更新和提供更为适合当前条件的识别打分。要跟踪目标的初始位置，完成了各类初始化工作，从图像或视频序列的第一帧开始运行整个算法。

然后对于该初始位置运行粒子滤波器进行随机抽样，计算目标区域周围的积分直方图。最终将得到识别和跟踪信息的联合数据分布，从而对目标模板进行更新，进而通过粒子加权获取目标定位。整个算法的流程设计如图2所示。

5.2 识别和跟踪信息的融合

支持向量机，也就是使用的分类器其实给出的定量判断数据是对于当前得到的目标样本的打分，该打分体现了样本近似某一类物体的程度，所以当跟踪中的特征由于算法不鲁棒等情况出现位置偏移真实目标不能提供准确目标信息时，识别的打分给出一个反馈，告诉跟踪系统当前的目标位置出现异常、偏离。所以融合跟踪中的目标信息和识别检测的打分信息，对于提高跟踪算法的鲁棒性极为重要。

基于粒子滤波和在线SVM的目标跟踪算法的设计思路是利用了支持向量机对于目标的打分分布来实现的，注意到了支持向量机在给出目标识别判断的同时给出了一个定量的识别打分，该打分为正值和负值时分别说明目标的两类所属，打分越大说明目标越“像”某类物体。在此处利用了该打分原理，将其改造为结合了粒子滤波器的观测概率分布的一个联合分布，在跟踪的过程中加入了检测和识别的信息，使得目标的观测分布更为合理准确。

具体的方法为是将所有的粒子候选目标的SVM打分进行归一化处理，通过如下公式使其成为(0,1)范围内的分布：

其中SvmSco[i]为各个粒子的支持向量机原始打分，SvmMin为其中的最小打分，SvmMax为最大值，λ为经验系数，这里选取7。

然后使用如下公式了来对于各个目标的SVM打分和粒子滤波的特征加权系数进行统一：

其中，SvmSco[i]为各个粒子的支持向量机归一化打分，TempHist[i]为模板的直方图打分，PtlHist[i]为粒子的直方图打分，经过试验测试，当经验系数取20时，色彩直方图的打分和SVM的打分能在算法中发挥最佳的效果，使其既包含了跟踪信息，又包含了检测和识别的信息。

通过在线识别信息和跟踪信息的融合保证算法具备较强的鲁棒性。

6 实验结果

本实验主要观测和分析基于粒子滤波和在线训练SVM目标跟踪算法的跟踪性能。本文在同一硬件系统和相同粒子数目条件下，分别对传统粒子滤波器和本文完成的算法，针对实时性和跟踪的鲁棒性做了测试。测试的结果如图3，图4和图5所示。

由图3可见，本文的算法在训练的间隔能稳定在每秒12到14帧。本文的算法的实时性基本达到视频目标跟踪可以接受的速度，相对于传统的粒子滤波算法每秒4到6帧的速度，本文结合在线检测和识别的设计有了较大的改进，满足了实时性要求。

图4是目标真实运动轨迹、本文算法跟踪轨迹和传统PF算法跟踪轨迹的对比图。如图所示，传统PF虽然跟踪效果也不错，但随着时间的推移产生了一定的漂移，而本文算法却始终能准确的跟踪到目标。

图5给出了部分图片的检测结果。跟踪目标为一辆轿车，方框区域为使用算法得到的目标的位置。其中绿色方框为本文算法，红色方框为标准粒子滤波算法的。结果表明本文算法具有较强的鲁棒性，对于不同的复杂场景都具有较强的适应性。

从实验结果看，因为只要计算一次全局的积分直方图之后便可以通过查找的方式得到每一个图像中的局部细节的直方图，故明显提高了算法的实时性能。同时将跟踪中的目标信息和识别检测的打分信息相融合，使算法在复杂背景下的跟踪性能更具鲁棒性。

7 结论

本文提出了一种基于粒子滤波和在线训练SVM的目标跟踪算法，该算法能够在一些复杂条件下对目标进行准确、有效、实时的跟踪。实验结果表明，该算法可以较好的适应光线变化、被部分遮挡或色彩质量很差等复杂背景条件下的图像序列中的目标跟踪，改善了标准粒子滤波算法的局限性，提高了跟踪算法的鲁棒性。

参考文献：

[1] PACHTER M,CHANDLER P R. Universal Linearization Concept for Extended Filters[J].IEEE Trans on Aerospace and Elec-Tronic System,1993,29(3):946-961.

[2] Doucet A, Freitas J F G, Gordon N J. An introduction to sequential Monte Carlo methods,in Sequential Monte Carlo Methods in Practice[C].New York:Springer-Verlag,2001.

[3] Viola P, Jones M. Rapid Object Detection using a Boosted Cascade of Simple Features[A]. In: IEEE Proceedings International Conference on Computer Vision and Pattern Recognition, Hawaii, USA, 2001:511-518.

[4] Keren T, Chen S C. Adaptively weighted sub-pattern PCA for face recognition[J]. Neurocomputing, 2005,(64):505-511.

[5] Richard O, Duda Peter E. David G. 模式分类[M].2版.李宏东,姚天翔,译.北京：机械出版社,2003.