基于粒子分组优化的自适应跟踪算法

刘振涛， 王朝英， 刘卫群

(1.空军工程大学电讯工程学院，西安 710077; 2.中国人民解放军63751部队技术室，西安 710028)

0 引言

序列图像中运动目标跟踪技术是计算机视觉领域的一个重要课题，在视频监控、物体识别、人机界面等领域中有着广泛的应用前景［1］。运动目标跟踪的难点在于对复杂环境中非刚性运动目标的跟踪。目标的轮廓和所处背景复杂，目标发生旋转或被遮挡等都对跟踪造成不同程度上的影响［2］。

粒子滤波是一种基于蒙特卡罗仿真的递推贝叶斯估计方法，常用于解决非线性、非高斯噪声环境下的状态估计问题［3］。粒子滤波算法因其在目标跟踪领域中良好的鲁棒性，受到广大学者的关注，相应的改进算法层出不穷［4－6］。

粒子滤波算法中，系统状态的后验分布由一组带有权值的离散采样(称为粒子)来表达。经过若干帧跟踪后常常会出现粒子退化现象，而解决这一问题的有效方法之一就是对粒子进行重采样。但伴随而来的负面作用就是粒子衰竭，特别是当观测值比较准确或似然函数位于先验概率分布尾部时，在权值更新之后很多粒子的权值都变得很小［7］。导致个别具有较大权值的粒子在滤波过程中被多次选择，从而丧失了粒子的多样性［8］。因此如何防止粒子退化并保持粒子多样性就成为了解决重采样问题的关键。现有的重采样方法主要有:重要性重采样、残差重采样、分层重采样、优化组合重采样等等［9－11］。

针对上述问题，本文提出一种基于特征区分度量化分析和粒子分组优化的自适应粒子滤波跟踪算法。首先提出一种新的背景区分度量化分析准则，通过计算目标与背景的特征显著性和相似性二者间比值关系，提取出背景区分度较高的候选特征建立目标概率分布直方图。并针对每一帧所有粒子的不同分布情况，以其当前帧所得权值为度量标准，采用复制、线性组合、淘汰等不同形式对粒子进行分组重采样，实现对粒子数量和位置分布的自适应调整。使得粒子性能得到优化，提高算法的鲁棒性。

1 传统粒子滤波算法

粒子滤波算法的基本思想是蒙特卡罗模拟，其中状态的后验密度由一组具有权值的粒子来近似。除了初始化之外，对于图像序列中的每一帧，算法主要包括4步:采样、计算权值、输出和重采样［12］。具体算法如下所述。

1)初始化。当时刻k=0时，从先验密度函数p(x0)中提取N个样本点x(i)0，设置初始权值为

3)计算权值并归一化。计算粒子的权值为

权值归一化。

4)输出阶段。

6)k=k+1，若继续跟踪转到步骤2)，否则算法结束。

2 自适应粒子滤波算法

本文在传统粒子滤波算法的基础上，分别从特征直方图的建立和粒子重采样策略两个角度对原有算法进行改进。

2.1 特征直方图

在建立特征直方图的过程中，必须选取那些使得目标与背景之间具有良好区分度的特征［13］。本文综合考虑特征显著性与相似性两个因素建立一种新的区分度量化分析准则，选取两个区分度最大的候选特征，将二者的区分度量化所得数值作为权值，而该权值则决定了目标直方图中所选特征区间数。

2.1.1 特征区分度量化分析

对于一个给定的特征，假定Hobj(i)和Hbg(i)分别表示该特征下的目标和背景直方图，将其与对应的像素数相除后，得到下面两个概率分布函数为:p(i)=Hobj(i)/nobj和 q(i)=Hbg(i)/nbg，nobj和 nbg分别表示目标和背景区域内的像素数。对于每一个特征值i，采用式(5)的对数似然比值得到显著性函数，并采用相应的方差来衡量目标区域与背景区域之间的显著性［14］。式(5)中ε为接近于0的极小值，本文取0.0001，保证除数不会出现为0的情况，式(6)中E(·)表示求均值，var(·)表示求方差。

同时根据目标加权直方图和背景加权直方图的BH系数来判断目标与背景的相似性，选取BH系数小的候选特征建立模型进行跟踪［15］。类似于目标模型与目标候选模型的相似性计算方法，得到目标与背景的加权直方图的相似性计算公式为

其中:p(i)为目标加权直方图中i分量的概率分布函数;q(i)为背景加权直方图中i分量的概率分布函数。

为了提取出使得目标与背景显著性大、相似度小的候选特征，建立如式(8)所示的二者比值关系式。M值越大则说明待测特征的背景区分度越高，反之区分度越低。

2.1.2 确定特征区间数

在建立目标特征直方图的过程中，如果对特征区间数分得过细，会影响算法的实时性，特别是融合多特征建立直方图时，但是如果对特征区间分的过于稀疏，则违背了引入多特征进行跟踪的初衷［16］。本文以特征的目标与背景区分度作为权值，来决定所选特征的区间数。

由特征区分度量化分析可得两个M值最大的候选特征，将两者的M值作为权值，按式(9)、式(10)所示确定所选的区间数N1、N2为

其中，M1、M2分别为所选特征分量的区分度量化数值。

2.2 粒子重采样策略

在粒子重采样的过程中，对于粒子数量的选取以及粒子分布位置的调整是提高算法鲁棒性的关键［17］，既要防止粒子退化问题，同时又要保持粒子的多样性［18］，对于每一帧跟踪过程中的粒子不同分布情况，应相应采取不同的重采样策略。基于这一思想，本文提出一种新的粒子采样策略，通过预先设定的粒子数阈值来判定当前帧粒子分布情况，主要是分析当前帧具有较大权值粒子的数量，共分为大权值粒子数较多、适中和较小3种情况进行讨论，再把每个粒子权值与预先设定的粒子权值阈值进行比较，并采用复制、线性组合、淘汰等不同形式对该粒子进行调整。

首先设定当前帧粒子数为N，粒子权值阈值为ωpre、ωpre1、ωpre2，粒子数阈值为 npre1，npre2。再统计权值大于ωpre的粒子个数n，按照3种情况分别进行讨论。

粒子分布情况1，当n≥npre1时，此时大权值粒子较多。

1) 若 ωi＜ωpre1，淘汰该粒子。

2) 若 ωi≥ωpre1，得到该粒子复制数 ωi×N，分布位置不变。

粒子分布情况2，当npre2≤n＜npre1时，此时大权值粒子数量适中。

1)若ωi＜ωpre1，淘汰该粒子，并统计该组粒子数n1。

2) 若 ωpre1≤ωi＜ ωpre2，按照式(11)调整该粒子分布位置，并统计该组粒子数n2。

其中:xni为该粒子分布位置;xnj为第3组粒子的分布位置;n3为第3组粒子数。

粒子分布情况3，当n＜npre2时，此时大权值粒子较少。

1)若ωi≥ωpre1，粒子保留，但不复制，并统计该组粒子数n0。

2)若ωi＜ωpre1，按照式(12)调整该粒子分布位置。

其中:xni为该粒子分布位置;xnj为上一组粒子的分布位置。

2.3 算法具体流程

Step 1 在第一帧手动确定跟踪目标的中心位置;

Step 2 选取经由背景区分度分析所得的候选特征建立特征直方图，并初始化粒子集;

Step 3 从建议性分布采样得到新的粒子集，计算权值，并归一化;

Step 4 输出阶段，由各个粒子线性加权计算新的目标中心位置;

Step 5 按照2.2节重采样策略对粒子进行重采样;

Step 6 若继续跟踪则转到Step 3，否则算法结束。

3 仿真结果及分析

本文选取两段测试视频对给定的运动目标进行跟踪实验。首先，对颜色空间特征中的H(色调)分量、S(饱和度)分量、I(亮度)分量以及梯度特征、纹理特征的背景区分度进行量化分析，结果如表1、表2所示，实验1中颜色空间特征的H分量和梯度特征的M值较大，实验2中颜色空间特征的H分量和S分量的M值较大，因而选择相应的特征建立目标直方图。同时列出本文所用参数值表格，如表3所示。最后通过不同情况下的多组测试实验验证所提跟踪方法的有效性。

表1 实验1特征区分度分析表Table 1 Figure discrimination table of test 1

表2 实验2特征区分度分析表Table 2 Figure discrimination table of test 2

表3 本文参数表Table 3 Parameter table

实验1为办公室内人脸跟踪视频序列(500帧，像素大小为128*96)。第88帧时，跟踪目标发生旋转，第314帧时，视频中出现相似目标，如图1所示，本文算法利用新的粒子重采样策略优化了粒子分布，能够较好地定位跟踪目标，同时融合梯度特征建立目标直方图，提高算法对颜色相似目标的鉴别性。

图1 相似颜色目标跟踪结果Fig.1 Tracking result of similar color target

实验2为行人监控录像视频序列(120帧，像素大小为352*288)。如图2所示，第39帧、第57帧、第81帧目标被遮蔽物连续遮挡，本文算法中的重采样策略较好地保证了粒子的多样性，即使受到遮挡，当目标重新出现时也能够迅速准确地搜寻目标的正确位置。

图2 连续多帧遮挡情况下目标跟踪结果Fig.2 Tracking result of sequential multi-frame occlusion

4 结束语

针对粒子滤波算法中粒子退化问题，本文提出一种基于粒子分组优化的自适应跟踪算法。在传统粒子滤波算法的基础上，分别从特征直方图的建立和粒子重采样策略两个角度进行了改进。综合利用特征显著性和相似性对候选特征背景区分度进行量化分析，并以区分度为权值确定直方图中所选特征的区间数，提高算法的鲁棒性。同时通过分析每一帧粒子的具体分布情况，对粒子的数量和分布位置进行分组自适应调整。最后通过大量视频序列验证了本文算法对运动目标跟踪的精度。

［1］ WANG J Q，YA S S.Integrating shape and color features for adaptive real-time object tracking［C］//Proceedings of the 2006 IEEE International Conference on Robotics and Biomimetics，2006:1-6.

［2］ 李金，胡文广.基于颜色的快速人体跟踪及遮挡处理［J］.智能系统学报，2010，5(4):353-359.

［3］ 赵丰，汤磊，张武，等.一种高实时性粒子滤波重采样算法［J］.系统仿真学报，2009，21(18):5789-5793.

［4］ BOGDAN K.Finding location using a particle filter and histogram matching［C］//Poland:Proceedings of Artificial Intelligence and Soft Computing，2004:786-791.

［5］ 梁晓龙，冯金富，杨啸天，等.基于集群智能粒子滤波的弹道导弹跟踪［J］.电光与控制，2009，16(7):29-33.

［6］ BOLIC M，DJURIC P M，SANGJIN H.Resampling algorithms and architectures for distributed particle filters［C］//USA:IEEE Transactions on Signal Processing，2005:2442-2450.

［7］ 吴川，杨冬，郝志成.基于粒子滤波的彩色图像跟踪［J］.光学精密工程，2009，17(10):2542-2547.

［8］ 曾伟，朱桂斌，陈杰，等.多特征融合的鲁棒粒子滤波跟踪算法［J］.计算机应用，2010，30(3):643-646.

［9］ 刘杰，董育宁.基于预测和粒子滤波的运动目标跟踪算法［J］.计算机工程与科学，2009，31(10):30-32.

［10］ 夏克寒，许化龙，张朴睿.粒子滤波的关键技术及应用［J］.电光与控制，2005，12(6):1-4.

［11］ 张淼，胡建旺，周云锋，等.粒子滤波的重采样方法［J］.火力与指挥控制，2009，34(10):18-21.

［12］ 张涛，费树岷，李晓东，等.基于色彩相关直方图的粒子滤波跟踪算法［J］.系统仿真学报，2009，21(17):5422-5426.

［13］ COLLINS R T，LIU Y.Online selection of discriminative tracking features［J］.IEEE Trans on Pattern Analysis and Machine Intelligence，2005，27(10):1631-1643.

［14］ 尹宏鹏，柴毅，匡金骏，等.一种基于多特征自适应融合的运动目标跟踪算法［J］.光电子·激光，2010，21(6):917-923.

［15］ 汪沁，江淑红，张建秋，等.提高Mean-shift跟踪算法性能的方法［J］.复旦学报:自然科学版，2007，46(1):85-90.

［16］ 齐飞，罗予频，胡东成.基于均值漂移的视觉目标跟踪方法综述［J］.计算机工程，2007，33(21):24-27.

［17］ 云廷进，郭永彩，高潮.基于粒子Mean Shift迁移的红外人体目标跟踪算法［J］.计算机学报，2009，32(6):1222-1228.

［18］ 姚红革，雷松泽，齐华，等.基于自适应粒子滤波的红外目标跟踪［J］.光子学报，2009，38(6):1507-1511.