基于DE蝙蝠算法优化粒子滤波的目标跟踪①

李龙龙,周武能,闾斯瑶

(东华大学 信息科学与技术学院,上海 201620)

1 引言

目标跟踪是计算机视觉中的一个重要主题,它具有许多真实世界的应用,包括流量管理[1],机器人定位[2]和人机界面[3].跟踪系统由两个主要部分组成: 视觉表示[4]和运动估计[5].在跟踪的运动估计步骤中,对物体动态的不确定性或非线性进行建模,以在视频序列中定位物体.跟踪方法可以分为两组,即运动估计的确定性[6]和随机[7]方法.Meanshift算法是一个确定性的跟踪器,它利用一个区域来迭代地最大化相似性度量.该算法可能在遮挡,前景和背景的相似颜色分布以及长视频序列中漂移[8].相比之下,随机跟踪器采用统计来定位目标跟踪的目标位置.卡尔曼滤波方法是针对线性和高斯观测噪声[9]而开发的,作为一种顺序随机方式,不能用于非线性运动.粒子滤波方法保持了视觉跟踪中模型评估和分析步骤的非线性和不确定性[10].

但是标准粒子滤波方法(PF)存在权值退化的问题,标准粒子滤波在利用重采样方法解决退化现象时,又会产生粒子贫化现象.针对该问题,文献[11]提出了一种根据权值来进行选择的粒子滤波方法,该算法在粒子群体中选取一些权值相对较大的粒子用于进行估计下一时刻的状态,这样就能在一定程度上减轻粒子的贫化问题程度.文献[12]提出了一种确定性的重采样粒子滤波,该粒子滤波方法提出了一种重采样的确定性优化思想,这样增加了粒子状态的多样性.文献[13]提出了一种饱和粒子滤波方法,这种方法是按照系统的不同特性挑选出相应比较适合的重采样方法,使得粒子更加贴近真实状态.但前面提出来的几种方法仍然是在传统重采样思想的基础上,并不能从源头上解决粒子贫化的问题现象.

基于群智能优化算法的粒子滤波是现代粒子滤波领域中一个较为新颖的发展方向[14].因为群智能算法改进粒子滤波主要是对粒子群体的分布状态展开迭代并寻优[15,16],其中没有涉及到对权值较低的粒子进行直接舍弃,所以可以在源头上来解决掉粒子的贫化现象.

文献[17]通过融合蜂群算法建立箱式粒子贫化解决策略,结果较好.文献[18]通过将粒子群算法和蚁群算法融合在粒子滤波算法中,实现粒子集间的信息共享,增强算法的全局寻优能力.文献[19]通过融合萤火虫算法优化粒子滤波,使用亮度和吸引度动态优化粒子集.

蝙蝠算法(Bat Algorithm,BA)[20]在2010年被剑桥大学Yang教授提出,其实现智能寻优的方法是模拟现实世界蝙蝠的捕食行为,类似于粒子群算法,蝙蝠算法同样是一种基于群体的随机策略进行搜索来寻优的机制,不同点在于蝙蝠算法在随机性拥有更强的优势.文献[20]已证明,蝙蝠算法的综合寻优能力优于粒子群算法、蚁群算法等主流群智能优化算法.

文献[21]提出的蝙蝠算法优化粒子滤波,并验证该算法优于其它智能算法,但是带来计算效率低下的问题.文献[22]使用Lévy的飞行路线特征来改进蝙蝠算法优化,增强了算法跳出局部极值的能力.文献[23]使用拉丁正交策略构建蝙蝠群位置初始策略,来使得搜索区间分散均衡,以提升性能.

上述的改进蝙蝠算法的过程中,更多考虑的是算法参数和初始化策略改进,能够获得一定的性能提升.与上述算法的改进策略不同,本文主要针对搜索区域进行策略调整.

本文在原有的蝙蝠优化算法中加入差分进化算法,以改进算法的搜索能力,并将其用于基于粒子滤波器的目标跟踪中,在执行重采样之前进行差分进化蝙蝠优化搜索,可以避免重采样本身的粒子贫化现象.

2 基本的粒子滤波算法

在标准的粒子滤波器中,在时间t下,目标状态矢量为xt,考虑通过观测状态矢量为zt来找到目标状态.观测器从第一帧到第t帧为z1:t.在粒子滤波器中,后验分布可以使用查普曼-科莫{高洛夫方程的}近似模型来定义,粒子集表示为权重集为

其中,q是重要性密度函数.前一次的后验分布是其中δ(·)为一个狄拉克函数,函数的约束条件是在前一时刻有且1≤i≤N.

3 蝙蝠算法

基于蝙蝠启发式的元启发式优化算法,即蝙蝠算法,由Yang[20]基于蝙蝠的回声定位的能力提出.在标准的蝙蝠算法中,蝙蝠的回声定位特征抽象化为如下规则[20].

(1)蝙蝠种群都通过回声定位来获得距离,并使用某种特殊的方法“明白”目标和非目标两者之间存在的不同特征点;

(2)蝙蝠在位置xi处伴随着速度vi以一定的速度飞行频率和响度来搜寻目标.他们可以自动调节发射脉冲的波长(或频率),并根据目标的接近程度调节脉冲发射速率.

(3)虽然响度可以按照多种方式变化,但是通常是假设响度从大(正)A0变化到最小设定数Amin.

但是蝙蝠算法存在后期收敛速度较慢的、收敛精度不高、容易陷入局部最优点等不足.本文提出的基于差分蝙蝠算法优化粒子滤波(DEBA-PF),将差分算法融合到蝙蝠算法中,使蝙蝠种群个体之间具有变异、交叉、选择机制,从而达到增加蝙蝠个体的多样性,提高算法的全局寻优能力和局部搜索能力,能够避免陷入局部最优从而得到全局最优.本文实验结果也证明DEBA效果更佳.

4 蝙蝠算法融合差分进化算法DEBA

由于差分进化算法(DE)的有效性和简单性,而使得差分进化算法获得很多的关注.差分进化算法(DE)[24]的基本思想在于应用当前种群个体的差异来重组种群进而得到中间种群,然后应用父代个体与子代个体竞争来获得下一代种群.DEBA算法的步骤如下:

Step 1.初始化DEBA算法各个参数;

Step 2.根据蝙蝠个体适应度函数得到各个蝙蝠权重和初始种群当前最优解;

Step 3.模拟蝙蝠种群的全局搜索寻优行为,根据本文中的等式(4)-(6)更新各个蝙蝠个体的对应的位置和速度;

Step 4.模拟蝙蝠个体的局部搜索行为,以及对应生成一个均匀分布的随机数rand,如果存在rand＞ri的情况,则下一步将进行式(7);

Step 5.生成另外一个独立的随机数,若rand＜且则蝙蝠当前的位置为,否则蝙蝠的当前位置为xnew;

Step 6.对蝙蝠的局部搜索能力进行调整,利用式(9)更新脉冲频率和响度;

Step 7.利用差分进化算法以每一个蝙蝠位置为初始点进行变异、交叉、选择操作,得到新的蝙蝠位置;

Step 8.计算并对比适应度函数值,更新全局最优值;

Step 9.当算法符合设定的精度阈值ε 时,或者迭代次数达到设定值时,这个时候就停止算法优化过程,否则就要进入Step 3.

从上述的DEBA算法步骤可以看到,BA和DEBA不同点在于DEBA在每一次的进化过程中,通过进化之后的蝙蝠个体位置不是紧接着进行下一次的迭代操作,首先是在蝙蝠个体之间进行变异、交叉、选择操作,获得新的蝙蝠个体位置后,再进行下一次迭代.在本文的DEBA算法迭代的初期,由于种群中蝙蝠个体的差异较大,因此进行的变异操作可以使得算法拥有更强的全局搜索能力,当过程进入到了迭代的后期,趋于收敛的时候,种群中蝙蝠个体的差异就会变小,结果也使得算法拥有更强的局部搜索能力.综合上述,DEBA将DE和BA的各自优点结合在一起,使得DEBA算法同时拥有更强的全局和局部搜索能力,进而克服了BA后期收敛速度较慢的、收敛精度不高、容易陷入局部最优点等不足.

5 本文算法目标灰度描述和目标函数设计

本文选用灰度分布进行目标的描述,建立系统观测模型.设视频图像跟踪区域的中心为X=(x,y),区域尺寸为跟踪区域内像素位置设为Xi=(xi,yi),因此,执行核概率密度估计以执行目标的灰度分布描述.假设目标灰度分布被离散化为B个bin区间,则定义灰度级量化函数b(Xi):R2→{1,···,B}表明将位置Xi处的像素灰度量化并分配给对应的灰度级bin中,这里B表示灰度的量化等级,由此定义目标的灰度分布为:

其中,δ(·)为Kronecker Delta 函数;跟踪区域内的像素总数记为M,k(·)为所采用的高斯核函数.

本文算法设计的目标函数式如下所表示:

6 DEBA-PF算法设计

6.1 DEBA-PF全局搜索最优过程

对于每一个蝙蝠设为i,它的位置和速度定义在一个d维搜索空间中,并且在迭代期间随后被更新.在迭代g中更新的解决方案和速度是通过使用全局搜索策略来计算的,公式如下:

其中,β∈[0,1]是一个从均匀分布中得到的随机矢量.x∗是 当前发现的全局最佳解决方案.频率fmin和fmax的值取决于感兴趣问题的域大小.

6.2 DEBA-PF局部搜索最优过程

对于局部搜索部分,一旦从当前最佳解决方案中选择了解决方案,则使用随机游走模型在局部生成每个蝙蝠的新的解决方案,本文设置的局部搜索方法如下:

若rand＞ri,则

若rand＜ri,则

其中,ε ∈[-1,1]是 一个随机数,xold是当前最优解决方案集中的解决方案,Ag=＜Agi＞ 是所有蝙蝠在迭代g时的平均响度.

6.3 DEBA-PF全局和局部搜索寻优调整过程

通过响度Ai和脉冲率ri的更新以反映如果找到目标,那么蝙蝠就降低响度并增加脉冲率,通过下式计算:

其中,ri0是初始脉冲率,ω是脉冲频率增加系数,γ是脉冲幅度衰减系数.对于任何0 ＜ω 和γ ＜1,我们有以下:

用差分进化算法以每个蝙蝠位置为初始点进行变异、交叉、选择,得到新的蝙蝠位置.

变异操作过程: 从蝙蝠种群中随机选取3个蝙蝠个体:xga(t)、xbg(t)、xgc(t),且 有a≠b≠c≠i,a,b,c∈{1,2,···,N} 中的随机数.F为缩放因子,F∈[0,2].

交叉操作过程: 交叉操作过程可以增多蝙蝠种群的多样性,经过下式对第g代蝙蝠种群和其变异中间个体进行蝙蝠个体之间的交叉操作.

在上式中,CR∈[0,1]表 示的是交叉概率,rand(1,n)∈[1,2,···,d] 的随机数,j=1,2,···,d.此交叉操作策略能够保证(t)中 至少有一个分量是由vgi(t)贡献.

7 本文算法步骤

Step 1.输入初始的测试图像,并设定所要进行跟踪的目标对象;

Step 2.随机生成N个蝙蝠个体{xi(0),i=1,···,N}作为算法的初始蝙蝠个体,初始化DEBA-PF算法参数.xi(t)服从重要性密度函数:

Step 3.计算蝙蝠个体的灰度直方图特征;

Step 4.DEBA算法操作;

Step 5.计算重要性权值:

Step 6.进行归一化:

Step 7.根据蝙蝠权值大小重采样,得到N个新样本;

Step 8.状态输出,对新样本求平均确定跟踪点:

上述算法过程充分利用了整个蝙蝠种群的有效信息,帮助蝙蝠个体跳出局部最优,避免了状态值变化不大的情况下还会继续进行迭代过程,使得算法终止优化,更多地是因为算法达到设定精度停止阈值,从而降低算法直到达到设定的最高迭代次数才会终止下来的概率,提高算法计算效率.

8 仿真实验和结果分析

8.1 性能测试分析

本文选取单变量非静态增长模型,实验测试对象的过程模型和观测模型如下:

过程模型:

观测模型:

上述等式中,net(t)和wet(t)为均值为零的高斯噪声.在本文假定系统噪声方差Q=1和Q=10,观测噪声方差R=10,滤波时间步数为50,初始化时脉冲响度为A0=0.5 ,初始化脉冲率r0=0.5,fmax=2,fmin=0,使用标准粒子滤波、粒子群优化粒子滤波和本文算法差分进化蝙蝠算法优化粒子滤波对该非线性系统进行状态估计与跟踪.

在本文算法中所使用的均方根误差公式:

(1)当蝙蝠数为N=20、Q=10时,仿真结果如图1所示.

(2)当蝙蝠数为N=50、Q=10时,仿真结果如图2所示.

(3)当蝙蝠数为N=100、Q=10时,仿真结果如图3所示.

(4)当蝙蝠数为N=20、Q=1时,仿真结果如图4所示.

(5)当蝙蝠数为N=50、Q=1时,仿真结果如图5所示.

(6)当蝙蝠数为N=100、Q=1时,仿真结果如图6所示.

在下示仿真图中,用x表示真实点,*表示BA估计点,○表示PF估计点,·表示PSO估计点,☆表示DEBA估计点,分别用实线连接.

图1 N=20、Q=10时滤波状态估计图和误差绝对值

图2 N=50、Q=10时滤波状态估计图和误差绝对值

从图1～图6可以看出,差分进化蝙蝠算法优化粒子滤波具有更高的状态值预测精度,这是因为差分进化算法优化粒子滤波的在粒子滤波的基础上,模拟蝙蝠个体和种群搜索目标的过程中,可以对全局搜索和局部寻优能力进行精确控制,同时融合了差分进化算法使得本文算法能够较大幅度提高算法的收敛速度、鲁棒性和寻优能力.

图3 N=100、Q=10时滤波状态估计图和误差绝对值

图4 N=20、Q=1时滤波状态估计图和误差绝对值

图6 N=100、Q=1时滤波状态估计图和误差绝对值

从表1中可以看出,在高噪声的影响下,差分进化蝙蝠算法粒子数N=20时精度依然比标准粒子滤波中粒子数N=100时的精度高,这样即表明,本文所用的差分进化算法在非线性、高噪声的环境会较标准的粒子滤波更好的跟踪目标.

8.2 目标跟踪测试

为了测试本研究算法的性能,本文在多个测试视频上进行了对比实验,如图7至图12所示.

表1 实验结果均方根误差对比

图7 标准粒子滤波跟踪结果1(第50、60、70、80、90、100帧)

图8 差分进化蝙蝠算法跟踪结果1(第50、60、70、80、90、100帧)

图9 标准粒子滤波算法跟踪结果2(第20、30、40、50、60、70帧)

图10 差分进化蝙蝠算法跟踪结果2(第20、30、40、50、60、70帧)

图11 标准粒子滤波跟踪结果3(第50、60、70、80、90、100帧)

图12 差分进化蝙蝠算法跟踪结果3(第50、60、70、80、90、100帧)

从以上实验结果可以看到,在非线性下、高斯噪声环境下,标准粒子滤波算法跟踪效果较差,鲁棒性能不佳,而本文所采用的差分进化蝙蝠算法在总体上来说具有良好的跟踪效果和鲁棒性.

9 结语

本文提出了一种基于差分进化蝙蝠算法智能优化粒子滤波的目标跟踪方法,同时具备全局搜索和局部搜索能力,提高跟踪算法的跟踪性能.测试视频图像的实验结果也表明,本文方法在复杂背景下的跟踪具有较好的鲁棒性和准确性.在后面工作中,将对其它信号源图像的目标跟踪问题进行深入研究,对跟踪过程中的模板更新、目标遮挡等问题做进一步优化.