白 俊 郭贺彬

(北京京北职业技术学院机电工程系，北京 101400)

这些年来，粒子滤波算法的应用主要在于视频追踪方面［1-2］。粒子滤波算法可以有效处理非线性、非高斯状态估计的问题，适合在环境复杂的情况下对目标的跟踪。粒子跟踪算法在应用中常见问题如下:

(1)粒子滤波跟踪算法需要很长的运算时间，难以满足实时性的要求。

(2)粒子滤波算法的另一个缺点是退化现象［1］。经过多次迭代后，大量的粒子只集中了较小的权值，它们对后验概率的估计不起作用，这样浪费了大量的计算时间。

为了解决退化现象问题并缩短计算时间，本文提出了一种改进的粒子滤波算法。改进之处说明如下:

(1)对每个原始粒子，比较其本身和对该粒子进行均值漂移搜索调整后得到的新粒子的特征，选择其中更接近目标原始分布特征的粒子作为调整后的分布粒子，提高收敛速度。

(2)原算法中使用直方图进行统计工作，新算法中用粒子所在的矩形区域4个顶点的积分直方图进行加减运算，从而避开重复的计算，节省运算时间。

1 标准的粒子滤波算法流程

粒子滤波算法的步骤如下:

步骤1 粒子初始化:

采样x0i～p( x0)，即根据p( x0)分布采样得到x0i，i=1，2，…，N。

步骤2 重要性权值计算:

设定k=k+1

步骤3 重采样:

步骤4 输出:

状态估计:

方差估计:

步骤5 判断跟踪是否结束，若跟踪结束则退出本算法，否则返回步骤2。

2 均值漂移算法与视频目标跟踪

均值漂移是一种基于非参数的核密度估计理论，是在概率空间中求解概率密度极值的优化算法。均值漂移算法已广泛应用于目标跟踪领域［3-7］。Dorin Comaniciu等人以加权颜色直方图作为目标特征，表示相似度的Bhattacharyya距离最大，等价于求概率密度极值，从而将均值漂移算法应用于目标跟踪领域［8］。

3 改进的算法

3.1 粒子的均值漂移采样调整

在本文算法中，均值漂移算法被用来调整采样粒子的位置。粒子的均值漂移采样调整算法的流程如下:

步骤1 初始化:

步骤3 计算Bhattacharyya系数:

步骤4 计算权值:{wi}i=1，…，nh

其中b(xi)表示颜色xi对应的直方图bin。

步骤5 计算新位置:

步骤6 计算Bhattacharyya系数:

步骤7 更新粒子位置:

步骤8 迭代:

3.2 图像的积分直方图表达

图像的积分直方图匹配算法如下:

3.3 算法描述

3.3.1 运动模型

在本文中，对运动目标用一个矩形窗口来表示，目标的状态定义为:

式中:u，v—表示矩形的中心位置;w，h— 表示矩形的长和宽。

常规的视频序列中的目标运动通常是非线性的，例如，行人可能在前进的时候突然停下或者转弯。为了使状态估计具有通用性，本文采用随机游走模型描述目标的运动。

式中:Wk-1是一个多变量高斯噪声且各个变量相互独立。

3.3.2 观测模型

将颜色分布做观测模型。目标区域的颜色分布用离散化的颜色柱状图表示，柱状图分割(bin)取为B。假设候选目标区域的状态变量为X，中心坐标y=(u，v)，{x(i)}i=1，…，n是区域内像素点的位置，bin(xi)表示xi在直方图中的颜色索引值，那么区域颜色概率分布(X)={(X)，b=1，…，B}计算为

其中δ表示Delta函数。

目标区域的颜色分布也可以按照上述步骤求出，表示为 ^q={qb，b=1，…，B}。我们用 Bhattacharryya系数来定义候选区域和目标区域的相似程度，两个颜色分布的Bhattacharryya系数定义为:

相似度函数定义为:

3.3.3 算法描述

本文提出的基于积分直方图和均值漂移采样的粒子滤波跟踪算法如下:

步骤1 初始化:k=0

(1)计算图像目标的普通直方图{qu}u=1，…，m

(2)FOR l=1，…，N

从先验概率p(x0)中采样{x(l)0}

END FOR

步骤 2 FOR k=1，2，…

(1)图像积分的直方图的计算

(2)粒子均值漂移采样FOR l=1，…，N

①重要性采样x(l)k～p(xk|x(l)k-1)

②根据x(l)k的4个顶点的积分直方图，计算普通直方图 {pu}u=1，…，m

④均值漂移采样调整，对x(l)k进行均值漂移调整，得到x'(l)k

⑤根据x'(l)k的4个顶点的积分直方图，计算普通直方图 {p'u}u=1，…，m

⑦如果ρ'＜ρ，则令x(l)k=x'(l)k

END FOR

(3)计算重要性权值FOR l=1，…，N

END FOR

(4)归一化重要性权值FOR l=1，…，N

END FOR

(5)粒子重采样FOR l=1，…，N

从{x(i)k|i=1，2，…，N}集合中根据权值重新采样得到新的N个粒子的集合{|i=1，2，…，N}，并重新分配粒子权值==1/N。

END FOR

3.4 实验结果及分析

3.4.1 均值漂移采样调整

图1是对PETS2001视频库中的一段视频的跟踪，以说明均值漂移操作对粒子分布的影响。通过对比，可以看出，均值漂移后，粒子集中到目标周围。

图1 均值漂移前后粒子的分布对比图

3.4.2 积分直方图和普通直方图计算耗时的对比1(粒子数固定)

使用Highway II采集的视频，对该视频分别使用积分直方图和普通直方图方法进行跟踪，比较它们在跟踪过程中直方计算的时间。跟踪用的计算机CPU为双核Intel Xeon 3 GHz，内存为2 G。

首先，固定粒子数为100，不同大小的目标对计算消耗时间的影响见表1。为简单起见，假设所有粒子的大小都相同。

表1 普通直方图和积分直方图计算耗时对比1

通过对比普通直方图的计算耗时(第二列)和积分直方图的计算耗时(第五列)可以看出，粒子较小时，普通直方图比积分直方图的耗时稍短一些;粒子较大时，普通直方图的耗时约是积分直方图的10倍;粒子很大时，积分直方图计算耗时比普通直方图计算耗时要少很多。

3.4.3 普通直方图和积分直方图计算耗时的对比2(粒子大小固定)

在粒子大小(37×46)固定的条件下，积分直方图和普通直方图计算耗时的对比见表2。当粒子数从20增加到1 000时，普通直方图的计算耗时急剧增加;而积分直方图的计算耗时变化较小。

上述分析表明，粒子越大，粒子数越多，粒子可能出现的区域就越大，采用积分直方图计算的优势越明显。

表2 普通直方图和积分直方图计算消耗时间对比2

3.4.4 本文算法与传统粒子滤波跟踪算法的效果对比

图2是对ATON视频库的Highway II视频的第118帧的跟踪结果。采用本文算法，使用较少的粒子数(20)就可以得到较好的效果。

4 结语

通过对粒子的均值漂移采样调整，在标准粒子滤波跟踪算法的基础上，提出基于均值漂移采样调整和积分直方图表达的粒子滤波跟踪算法，使得粒子集中于其邻近的局部极大值区域内，减少退化现象的发生。

图2 不同粒子数对原算法和本文算法的影响对比

通过图像的积分直方图表达方法，可以减少在计算大量粒子的直方图中产生的冗余，将粒子的直方图计算变为对粒子位置的4个顶点的积分直方图的线性组合。实验表明，改进后的算法比标准粒子滤波算法效率更高，收敛速度更快。随着粒子数增多，粒子所在区域面积越大，本算法的优势越明显。

［1］Arulampalam M，Maskell S，Gordon N.A Tutorial on Particle Filters for Online Nonlinear/non-gaussian Bayesian Tracking ［J］.IEEE Transactions on Signal Processing，2002，50(2):174-188.

［2］Gunnarsson F，Bergman N.Particle Filter for Positioning，Navigation，and Tracking［J］.IEEE Transactions on Signal Processing，2002，50(2):425-437.

［3］单勇.复杂条件下视频运动目标检测和跟踪［D］.长沙:国防科技大学，2006.

［4］卢晓鹏.视频序列中目标跟踪技术研究［D］.北京:中国科学院研究生院，2007.

［5］李安平.复杂环境下的视频目标跟踪算法研究［D］.上海:上海交通大学，2006.

［6］贾静平.图像序列中目标跟踪技术研究［D］.西安:西北工业大学，2006.

［7］张波.基于粒子滤波的图像跟踪算法研究［D］.上海:上海交通大学，2007.

［8］Comaniciu D，Ramesh V，Meer P.Real-time Tracking of Non-rigid Objects Using Mean Shift［C］.Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.Hiltom Head，SC，USA，2000:142-149.