基于粒子群优化算法的目标跟踪方法

高 翔 李志浩

（甘肃联合大学 电子信息工程学院，兰州 730000）

0 引言

在视频监控系统中，实现对目标物快速、准确的跟踪，首先必须提取到目标物区别于背景的明显特征。目标跟踪中，常提取的特征有颜色、纹理、形状，轮廓和运动等，它们各自有其特有的优缺点。传统的目标跟踪中，一般只提取目标物的单一特征来对其进行跟踪，有时很难实现准确的跟踪效果。本文拟采用颜色与运动特征相融合，建立多特征融合的观测模型，来克服提取单一特征所造成的跟踪失败。

常用的跟踪滤波算法是卡尔曼滤波以及扩展卡尔曼滤波，对于滤波假定的目标状态应该遵循高斯分布，因此通过卡尔曼滤波方程估计的均值向量和协方差矩阵能够完全刻画目标的行为。然而许多因素可能导致非线性、非高斯分布的出现，如复杂的目标运动模型和系统状态表示方式，而最常见的原因是由于图像中杂物的存在而导致观测密度是非线性的。本文所采用的粒子滤波其完全适用于非线性，非高斯的环境，可以克服卡尔曼滤波的缺点。基于蒙特卡罗方法和递推贝叶斯估计的统计滤波方法依据大数定理采用蒙特卡罗方法来求解贝叶斯估计中的积分运算是粒子滤波的基本原理。基本原理是：先根据系统状态向量的经验条件分布在状态空间产生一组随机样本的集合，样本被称为粒子，接着依据测量值调整粒子的权重和位置，通过调整后的粒子信息完善已经建立的经验条件分布。

尽管粒子滤波有着卡尔曼滤波无法比拟的优点，但它自身也存在着一定的缺点。如由于随着时间的延长重要性权重的方差逐渐递增，使粒子的权重慢慢集中到个别粒子上，也可能在经过几次递归后，系统中只剩一个粒子具有非零权值，其它粒子的权值太小，我们忽略不计，更新那些不起作用的粒子浪费了大量的计算工作，而产生实际的后验概率分布无法表达的退化问题；重采样技术被用来克服退化问题，我们复制权值较大的粒子，剔除权值较小的粒子时又使粒子的多样性特征降低，引来了粒子匮乏的问题。本文提出了一种基于粒子群优化算法的改进粒子滤波算法，这种算法驱动粒子向高似然区域迁移，克服粒子退化与匮乏问题有效方法就是增加粒子的多样性。

1 特征提取

对目标进行准确跟踪的前提是能够准确的检测到目标，如何准确检测到目标的核心问题是如何精确地提取到目标物区别与背景的独特特征。传统的目标跟踪系统中，一般只提取目标物单一特征来对其进行识别，当背景较为复杂或目标物被遮挡时往往很难把目标物提取出来。近些年来提取目标多个特征来对其进行跟踪成为科研者们研究的重点。

2 模型建立

2.1 状态转移模型

使用粒子滤波进行目标跟踪时，为了描绘目标在两帧之间的运动特性首先要针对目标建立一个系统模型即状态转移模型，模拟状态变量的进化规律。

目标运动状态 由目标在 平面上的位置和速度组成：

其中， 表示目标的中心， 表示目标的速度。

本文采用二阶自回归模型做为目标状态转移模型：

2.2 多特征融合的观测模型

对目标进行准备跟踪的前提是获取被跟踪目标的准备信息，并充分利用这些信息建立目标的模型。本文选用颜色与纹理信息构建系统的观测模型。那么如何衡量每个参考目标直方图 和候选目标直方图 之间的相似度呢?

Bhattacharyya(BH)距离测度系数[1]是一个很优的解决方案， Bhattacharyya系数可以定义为：

两个分布之间的距离为：

可定义颜色特征的距离为：

纹理距离为：

似然函数为：

得到序列图像的似然分布 是跟踪算法的关键，由于本文的跟踪算法使用了自适应的多特征融合，每个滤波粒子的观测值都由颜色和纹理两部分组成，自适应的融合两者的似然函数形成最终的观测似然函数 。

因为分布距离 越小相似度越高，我们得到的观测信息就越多，而特征能提供的信息就更精确，定义 为最小距离，则利用各个特征的最小距离定义分布系数：

3 粒子群优化算法原理

粒子群优化算法(Particle Swarm Op tim ization,PSO)是在1995年由Kennedy和Eberhart提出的[3]。它是一种模拟鸟群飞行觅食的行为，当一只鸟发现食物，并飞向食物时，其它鸟也跟随着这只鸟飞向食物，形成鸟群。PSO算法是一种有效的全局寻优算法，通过个体间的竞争与合作所产生的群体智能指导优化搜索。它把每个个体看作是在n维空间中飞行的没有体积和重量的微粒，其飞行速度由个体的飞行经验和整体的飞行经验进行调整。

我们可以描述PSO算法为，随机初始化一个粒子群(数量为 )，其中，第 个粒子在 维空间表示成：

速度为：

每一次迭代，通过下面两个极值来更新粒子的速度和所在位置：

第一个极值是粒子本身从开始到当前迭代次数搜索所产生的最优解，称为个体极值

第二个极值称为全局极值，是该种群当前最优解， 。时，算法局部搜索能力较强；大时，算法全局搜索能力较强。为[0,1]之间的随机数。

每个粒子根据找到的两个最优值，通过下式更新粒子速度和位置：

4 粒子群优化算法改进粒子滤波算法

众所周知粒子滤波算法本身无法克服粒子退化与粒子匮乏问题，在实际应用中有一定的局限性。由于没有考虑到当前的量测值产生粒子退化现象，真实后验概率密度采样得到的样本与重要性密度函数中取得的样本存在较大偏差，特别是当似然函数位于先验概率的尾部或呈尖峰状态时，这种偏差更明显[5]。粒子匮乏问题是因为引入了重采样方法来克服退化问题，这样的做法使系统复制权值较大的粒子，删除权值较小的粒子，最终让粒子的多样性减少。

本文将PSO算法引入到粒子滤波中，把采样种群中的粒子看成滤波粒子，向高似然区域驱动粒子的移动，可以增加有效的粒子数，从而提高粒子多样性，实现有效克服粒子退化与粒子匮乏问题的目的。算法具体实现步骤叙述如下：

Step1 取得量测值：

其中 为最新观测值， 为预测观测值[6]。

Step2 初始化：

重要性密度函数取转移先验概率：

Step3 重要性权值计算：

根据最新量测值更新当前粒子权值[7]：

根据下式利用粒子群优化算法来更新每个粒子的位置与速度，使粒子陆续向真实状态逼近[8]。

Step4 权值归一化：

Step5 重采样过程将

原来的带权粒子重采样[9]，得等权粒子：

Step6 状态估计：

PSOPF算法流程图如图1所示。

图1 PSOPF算法流程图

5 改进算法实验结果分析

为了客观验证本文给出的粒子群优化粒子滤波算法的优越性，本文对标准粒子滤波和粒子群优化粒子滤波进行了对比实验。本文采用Matlab对算法进行仿真，算法模型如下：

粒子数目设N=100，仿真中的量测噪声方差设R=1，过程噪声方差设Q=10，仿真次数设为50次，时间步长设为为50，最大迭代次数做为算法结束条件，设n=50次。

两种算法单次实验的仿真如图2所示，两种算法的残差变化情况如图3所示，表1给出了两种算法实验50次的数据平均值：

图2 PSOPF和PF单次仿真实验图 图3 PSOPF和PF残差图

表1 滤波数据统计表

通过图2所示的估计仿真图，比起PF算法，PSOPF算法实现了更精确描绘粒子真实状态的目的。如图3所示残差[10]图中显示，PSOPF的波动变化最小，说明它的估计值和真实量测值比较接近，也可以说PSOPF的估计精度是高于PF算法的。根据表1对实验数据的平均值统计，可看出两种算法的估计时间相差不大，因为PSOPF算法的标准误差最小，可证明PSOPF算法在估计时间没有太大变化的情况下，能够有效地提高算法精度。

6 仿真实验结果分析

为了验证PSOPF目标跟踪方法，本文选用校园散步者图像，通过四帧自拍图像序列做目标跟踪实验。实验在Pen tium(R) 4 CPU 2.6GHz、内存1G的PC机上实现，我们采用MATLAB 7.0软件平台。图4和图5为PF和PSOPF算法在第1帧、第43帧，第102帧和第168帧的跟踪情况。

由以上实验结果可以看出，传统的粒子滤波没有对采样粒子进行有效处理，在逼近目标状态时会产生较大误差，随着时间的推移系统所追踪的目标与真实目标逐渐偏离。本文给出的PSOPF算法通过不断更新粒子的速度与位置对其进行优化，有效地抑制了粒子的退化与匮乏现象，能够较好的覆盖跟踪区域，可以较好的提高跟踪性能。

图5 PSOPF算法的目标跟踪

7 结论

为了能够有效地克服粒子退化与粒子匮乏问题，我们利用粒子群算法把种群中的粒子看成滤波粒子，通过粒子群算法的快速收敛能力和全局搜优能力，为提高粒子多样性，驱动粒子向高似然区域移动，增加了有效粒子数。实验结果显示，本文所示的改进算法能够较好的覆盖跟踪区域，降低了计算时间，较明显的提高了跟踪准确程度。

[1] Pitt M K, Shephard N. Filtering via sim u lation:Auxiliary particle filters [J].J of the Am erican Statistical Association,1999,94(2):590-599.

[2] Belviken E,Acklam P J. Monte Carlo filters for non-linear state estim ation[J].Autom atica,2001,37(1):177-183.

[3] 孙俊.量子行为粒子群优化:原理及其应用[M].清华大学出版社.2011.

[4] 曾建潮,介婧,崔志华. 微粒群算法[M]. 科学出版社.2004.

[5] 王国宏.先验概率和似然函数未知时的分布式检测融合[J]. 电光与控制.2004.

[6] Kenned y J,Eberhart RC.Particle Sw arm Op tim izati onProcoftheIEEE ternational ConferenceonNeuraltworks[J].Perth,Australia,1995:1942-1948.

[7] 康健,张仲凯,芮国胜.基于均值漂移粒子滤波的目标跟踪算法研究[J].2009.

[8] Reyno lds C W. Flocks,Herds and Schools: A Distributed Behavioral Model. Com puterGraphics[J].1987,1(4):25-34.

[9] Angeline P J.Using Selection to Im p rove Particle Sw arm Op tim ization//Proc of the IEEE International Con ference on Evo lu tionary Com p u tation.An cho rage[J].USA,1998:84-89.

[10] 王敏.残差分析在统计中的应用[J].江苏统计.2000.