一种基于多样性优化的视频目标跟踪方法

刘 剑 郭文博 李凌燕 许帅宏

(沈阳建筑大学信息与控制工程学院 辽宁 沈阳 110168)

一种基于多样性优化的视频目标跟踪方法

刘 剑 郭文博 李凌燕 许帅宏

(沈阳建筑大学信息与控制工程学院 辽宁 沈阳 110168)

针对粒子滤波算法在视频目标跟踪过程中出现的粒子退化问题，提出一种新的基于多样性优化的粒子滤波跟踪算法。融入基于莱维飞行机制的布谷鸟搜索优化算法，扩大了搜索范围，充分保留了有效粒子的数量和粒子的多样性。在MATLAB 7.0运行环境下进行仿真实验，将该算法与原始粒子滤波算法及基于粒子群优化的粒子滤波改进算法进行状态估计实验对比以及运动目标跟踪实验对比。实验结果表明：该算法具有良好的运行效果，改善了粒子退化与匮乏现象，对视频运动目标可获得较理想的跟踪精度及良好实时性和鲁棒性。

粒子滤波 粒子退化 运动目标跟踪 粒子多样性优化

0 引 言

运动目标跟踪是计算机视觉领域中重要研究方向之一，运动目标的跟踪就是在视频图像的每一幅图像中确定出感兴趣的运动目标的位置，并把不同帧中同一目标对应联系起来。粒子滤波算法[2]利用粒子集来表示概率，通过从后验概率中抽取的随机状态粒子来表达其分布，本质是一种基于贝叶斯推理[3]和蒙特卡洛方法的一种统计滤波方法，是一种顺序采样法，可以用在任何形式的状态空间模型上。随着视频运动目标跟踪研究的热门化，对运动目标跟踪的要求也变得复杂化，不仅仅是跟踪到目标，对跟踪的质量以及准确性有着更高的要求。

原始的粒子滤波算法在实现过程中会出现粒子退化与匮乏的现象，对视频运动目标的跟踪精度也会由此而逐渐下降，严重影响了运动目标的跟踪效果。常用的优化算法有遗传算法、萤火虫算法[4]和粒子群算法等。但是它们各有缺点，效果不佳。针对传统粒子滤波所出现的粒子退化与匮乏问题，研究了一种新的基于多样性优化的粒子滤波的视频运动目标跟踪方法。

1 融入莱维飞行机制的布谷鸟搜索优化算法

在自然界中，一些动物总是以一种随机或拟随机的方式进行觅食。动物的觅食路径实际上属于一种空间随机漫步的行为，其步长服从于幂率分布[5]。并且该动物接下来的状态以及行动是由该动物的当前位置以及状态转移概率所决定的，这种觅食行为被科学家们称为“莱维飞行”。1996年，Viswanathan等人发现了信天翁在觅食过程中，其飞行距离间隔服从于幂率分布，并由此发表了一系列相关论文。同时也引发了众多学者对生态学的研究[6-7]，如Reynolds等人对蜜蜂和果蝇的觅食行为研究以及驯鹿和众多浮游微生物等觅食行为均符合莱维飞行机制。将其融入智能优化算法中，不但能扩大算法的搜索范围，增加了种群的多样性，同时还能够解决某些优化算法陷入局部最优的问题。

布谷鸟搜索优化CS是由Yang等人在2009年提出的一种元启发式优化算法[8-9]。该算法融入了布谷鸟的繁殖策略思想，并引入了其他种群普遍具有的随机飞行行为，即莱维飞行机制。布谷鸟算法的仿生思想是：将自己所产的卵寄居在与自己食性、身体颜色、形状都相似的宿主巢内，从而在一定程度上保留了自己卵的存活几率。如若被宿主发现，宿主或将布谷鸟所产的卵“丢弃”，或舍弃鸟巢重建新窝。因此，布谷鸟所寄居卵的的存活概率高低往往是由其寄居宿主巢的优劣所决定[10-11]。

布谷鸟搜索算法充分体现了物种自然选择的优化机制，该算法主要遵循三个原则：

(1) 每一个布谷鸟一次仅可产一颗卵，并将其寄宿在随机选择的宿主巢中。

(2) 若所寄居巢的宿主与布谷鸟的习性具有高相似性，那么布谷鸟的卵具有高存活率，并产生布谷鸟的下一代。

(3) 宿主巢的数量是固定的，设宿主发现布谷鸟所寄宿的卵的发现概率为pa∈(0,1)，若此情况发生时，宿主或将布谷鸟的卵扔出，或舍弃该巢重建新巢。

设原宿主巢内的卵代表一个解，布谷鸟随机寄宿的卵则为一个新的解。该算法最终的优化目标则是通过选取布谷鸟寄宿在巢内的最好的卵来代替原巢内的卵，进而产生一个新的最优解。为了充分地实施上述三个原则，该算法的数学模型建立如下：

(1) 应用莱维飞行机制表达宿主巢更新算式为：

(1)

Levy(λ)～v=t-λ1≤λ≤3

(2)

因此，引入了莱维飞行机制，充分加快了算法的搜索速度，同时也确保避免解陷入局部最优。

(2) 通过宿主的发现概率以及与布谷鸟与种群的相似程度来更新宿主巢的位置：

(3)

其中，xj、xk为两个随机选择的不同的解，H(..)为Heaviside函数，ε表示搜索精度，并服从于均匀分布，s表示步长。

CS算法的优化过程如下：

Step1 初始时，布谷鸟随机选择一定数量的宿主巢并产卵，并评估这些宿主巢且保留当前最好的巢从而使得下一代得以存活；

Step2 根据式(1)或式(2)来更新巢的位置；

Step3 优胜劣汰机制：布谷鸟所产的卵若被宿主发现(发现概率为pa)，宿主则丢弃布谷鸟所产下的卵或者丢弃鸟巢重建新巢；

Step4 对所有的宿主巢进行评估，获得当前最佳的宿主巢所在位置，若该位置优于初始时的最佳位置，则进行替换；

Step5 若当前的搜索精度大于所设定的最大搜索次数T,则输出最优值；反之,则重复Step2 ，继续下一代的搜索。

2 基于布谷鸟算法的多样性优化的粒子滤波跟踪算法

系统目标状态估计的精准度与粒子数量的选择有着密切直接的关系。随机抽取的粒子数量越多，系统的后验概率密度分布估计就越准确。但选择过多的粒子进行状态的估计不仅会无限增加算法的计算复杂度，且在很大程度上降低了算法的实时性，同时还会将算法陷入局部最优。而在基于粒子多样性优化的粒子滤波算法中融入了布谷鸟搜索优化，在布谷鸟搜索过程中仅选择少量的最优粒子即可，从而缩小了算法计算的复杂难度。

该算法实现运动目标跟踪的基本思路是：由每一个粒子表示一个宿主巢，并执行巢的位置更新的莱维飞行机制，最后集合所有的巢并选择出一个最优的宿主巢来完成状态输出，从而对跟踪性能进行优化来实现对运动目标的跟踪。且粒子滤波器在新的测量值到来后，通过递推方式来对权值进行更新[12]。算法的运动目标跟踪步骤如下：

Step2 根据式(1)、式(2)建立系统状态模型；

Step3 序列重要性采样、权值更新：由系统的先验概率分布和当前观测值，建立粒子的颜色分布直方图，并通过与目标模板进行匹配，通过式(4)更新每个粒子的权值：

(4)

Step4 重采样判定：计算当前有效粒子个数：

(5)

根据Ne≤NT判定原则，判断是否需要重采样，若满足判定原则则进行下一步,否则返回Step2；

Step5 布谷鸟搜索优化选择。把当前的粒子看作布谷鸟算法中的宿主的“巢”Fi={x1,x2,…,xN}，宿主的发现概率为pa，步长α，搜索精度ε，搜索最大次数为S；布谷鸟通过式(2)莱维飞行机制随机选择一个巢使布谷鸟产卵Fj，并随机与相邻的任意一个巢中的卵Fk进行比较，当Fj>Fk时，则布谷鸟产的卵将替代原先的卵而被保留，即被选的这个巢为最佳的巢而保留下来；当布谷鸟的卵被宿主发现(概率为pa)，该巢则被视为劣巢而被舍弃，并通过式(1)、式(3)建立新的宿主巢；最后对所有的巢进行评估，选出最优的巢的位置，即最优的目标状态估计；

Step6 若当前搜索次数大于最大搜索次数S，则输出最优结果；反之返回Step2。

基于多样性优化的粒子滤波跟踪实现流程如图1所示。

图1 基于多样性优化的粒子滤波跟踪实现

3 实验结果与分析

为了验证基于多样性优化的粒子滤波算法在解决目标跟踪时粒子退化与匮乏问题的有效性，通过MATLAB7.0的仿真环境，在一维非稳态、非线性的环境下，将基于多样优化的粒子滤波算法分别与原始粒子滤波算法以及当前较为先进的基于粒子群优化的粒子滤波改进算法进行目标状态估计实验与视频运动目标跟踪对比实验，分析其在实际的运动目标跟踪中的跟踪性能。

3.1 状态估计实验

将本文所提出的算法与原始的粒子滤波算法以及基于粒子群优化的改进粒子滤波算法(PSO-PF)[13]进行目标状态估计结果的比较。

设k时刻下目标模型的状态转移模型如下：

(6)

系统的观测模型为：

(7)

其中ωk、vk属于高斯白噪声，且设定ωk～N(0,10)，vk～N(0,1)；最初的目标状态值为x1=1，系统目标状态的先验概率分布p(x0∶k|z1∶k)～N(0,2)，随机抽取粒子的数量为N=500，由于目标模型为虚拟模型，没有明确的时间单位，本实验设定时刻k的取值范围为1～50。

目标状态估计仿真比较结果如图2-图4所示。

图2 传统粒子滤波算法状态估计图

图3 PSO-Particle Filter算法状态估计图

图4 基于多样性优化的粒子滤波的状态估计图

由于实验设定了50个时刻k值，从而每个算法在本次实验中共进行了50次的状态估计。可以看出，采用粒子滤波(PF)进行状态估计时，估计的状态与真实状态之间存在着很大的误差；而粒子群优化的粒子滤波算法(PSO-PF) 的目标状态的估计虽较粒子滤波有了一定程度的改进，但与本文提出的算法相比，仍存在较大的误差，因而本文提出的算法对目标的状态估计更能够接近于真实的状态分布。

对本实验中的三种算法进行对比分析, 表1说明了运行时间及均方根误差比较情况。

表1 算法运行时间及均方根误差值

由表1可以看出，本文算法相对于PF算法和PSO-PF算法，在目标状态估计时能够产生较小的误差，算法运行时间适中，失误率小，有着更精准的状态估测率和良好的实时性。

3.2 视频运动目标跟踪实验

3.2.1 单目标运动物体视频目标跟踪

运动目标跟踪实验的视频选取从CVDatasets人体行为数据库中截取视频，通过MATLAB7.0仿真工具所截取到的部分视频帧如图5所示。

图5 单移动目标部分视频序列图像

对所截取50帧视频序列图像实现运动目标的跟踪。设定初始采集跟踪粒子的数量为N=500。分别对基于多样性优化的粒子滤波算法以及粒子滤波算法和基于粒子群优化的改进粒子滤波算法对运动目标的跟踪结果进行对比，部分跟踪结果如图6所示。

图6 单移动目标视频运动目标跟踪比较结果

由图6所示的视频运动目标跟踪的比较结果可知，黑色框代表的是粒子滤波算法的跟踪情况，白色框代表的是基于粒子群优化的粒子滤波算法的跟踪情况，灰色框则表示本文算法的目标跟踪情况。实验表明：本文所提出的算法在目标的跟踪性能及跟踪精度上较粒子滤波算法有着较大程度的改进与提高。

按照本实验的系统模型参数设置，在运动目标跟踪过程中，针对粒子数量的退化程度进行仿真实验，如图7所示。其中(a)为粒子滤波算法在各个状态下所剩余粒子的数量；(b)所示为基于粒子群优化的改进粒子滤波算法在各个状态下剩余粒子的数量；(c)所示为基于多样性优化的粒子滤波算法在各个状态下的有效粒子数量。

图7 目标状态估计时不同算法产生的有效粒子数量

由图7可以看出，采用粒子滤波算法进行运动目标跟踪时粒子退化的现象明显。在目标状态估计的许多情况下，粒子的数量少于200，粒子退化程度明显，有效粒子数量不能持续地保持在一个相对稳定的状态下，使得算法在跟踪过程中时而失效，不能很好地估测出真实的目标状态，从而不能进行精准的跟踪。而基于粒子群优化的改进粒子滤波算法在粒子有效数量上虽较原始粒子滤波算法有所增加，有效粒子数量基本保持在200～400之间，但与本文提出的算法对比仍存在一定的差距。基于多样性优化的粒子滤波算法的有效粒子数量在多数状态下几乎趋近于初始粒子数量，有效粒子数量的变化相对呈一个稳定的状态。由此可见，本文提出的基于多样性优化的粒子滤波算法能够更好地保持着粒子的数量，同时充分地保留了粒子的多样性，更有效地对目标状态进行估计，实现对运动目标更精准的跟踪。

表2是各个算法的时间效率的比较。可以看出，本文算法在对单目标跟踪的几帧中处理时间较粒子滤波算法和基于粒子群优化的改进粒子滤波算法都短。这样与单一的粒子滤波相比，可节省大量时间。

表2 单目标跟踪各算法运行时间 ms

3.2.2 多目标运动物体视频目标跟踪

为了验证本文算法的优越性，还需在视频中对多目标运动物体进行跟踪。本视频是在实验室环境下拍摄的。通过MATLAB 7.0仿真工具所截取到的部分视频帧如图8所示。

图8 多目标移动部分视频序列图像

从中选取200帧图像序列实现对多目标运动物体的跟踪。设定初始采集跟踪粒子的数量为N=800。分别对基于多样性优化的粒子滤波算法以及粒子滤波算法和基于粒子群优化的改进粒子滤波算法对运动目标的跟踪结果进行对比，部分跟踪结果如图9所示。

图9 多目标移动视频运动目标跟踪比较结果

黑色框代表的是粒子滤波算法的跟踪情况，白色框代表的是基于粒子群优化的粒子滤波算法的跟踪情况，灰色框则表示本文算法的目标跟踪情况。实验表明：本文所提出的算法能够实现对多目标的跟踪，并且同样具有较高的跟踪精度。

表3是多目标跟踪时各个算法的时间效率的比较。可以看出，本文算法在对多目标跟踪的几帧中处理时间较粒子滤波算法和基于粒子群优化的改进粒子滤波算法都短。但是与跟踪单目标相比，三种算法运行时间都较长。

表3 多目标跟踪各算法运行时间 ms

4 结 语

针对视频监控中的移动目标跟踪问题，本文提出了一种基于布谷鸟算法的多样性优化的粒子滤波跟踪算法。通过与传统PF算法以及PSO-PF算法在目标的状态估计、运行时间以及产生的均方根误差比较得出，本文所提出的算法进行状态估计更能够接近目标的真实状态，有着较高的状态估测效率，在较小误差下，保留了粒子的多样性以及粒子样本数量；同时具有实时性和对运动目标实现较完整跟踪，并具有良好的跟踪精准度。

[1] 陈远祥，林庆.视频图像运动目标跟踪技术的研究[D].江苏大学,2010.

[2] 王法胜,鲁明羽,赵清杰,等.粒子滤波算法[J].计算机学报，2014,37(8):1679-1694.

[3] Prakash J,Gopaluni R B,Patwardhan S C,et al.Nonlinear Bayesian state estimation:Review and recent trends[C]//Proceedings of 2011 15thIEEE International Conference on Advanced Control of Industrial Process,2011:450-455.

[4] 刘长平,叶春明.一种新颖的仿生群智能优化算法：萤火虫算法[J].计算机应用研究,2011，28(9):3295-3297.

[5] Reible D,Mohanty S.A levy flight—random walk model for bioturbation[J].Environmental Toxicology and Chemistry,2002,21(4):875-881.

[6] Barthelemy P,Bertolotti J,Wiersma D S.A Lévy flight for light[J]. Nature,2008,453(7194):495-498.

[7] Senthilnath J,Das V，Omkar S N,et al.Clustering Using Levy Flight Cuckoo Search[C]//Proceedings of Seventh International Conference on Bio-Inspired Computing :Theories and Applications,2012:65-75.

[8] Mohamad A,Zain A M,Bazin N E N, et al.Cuckoo Search Algorithm for Optimization Problems-A Literature Review [J].Applied Mechanics and Materials,2013,421:502-506.

[9] Panigrahi B K,Suganthan P N,Das.Swarm,Evolutionary,and Memetic Computing[M].Springer International Publishing,2011:515-526.

[10] 宋玉坚,叶春明,黄佐钘.多资源均衡优化的布谷鸟算法[J].计算机应用,2014,34(1):189-193.

[11] Yang X S. Cuckoo Search and Firefly Algorithm[M]. Springer International Publishing,2014:49-62.

[12] 王国良,刘金国.基于粒子滤波的多自由度运动目标跟踪[J].光学精密工程,2011,19(4):864-869.

[13] Bagheri A, Peyhani H M, Akbari M.Financial forecasting using ANFIS networks with Quantum-behaved Particle Swarm Optimization[J].Expert Systems with Applications,2014,41(14):6235-6250.

A VIDEO TARGET TRACKING METHOD BASED ON DIVERSITY OPTIMISATION

Liu Jian Guo Wenbo Li Lingyan Xu Shuaihong

(FacultyofInformationandControlEngineering,ShenyangJianzhuUniversity,Shenyang110168,Liaoning,China)

Aiming at the particle degradation problem of particle filter algorithm happening in the process of video target tracking, a new particle filter tracking algorithm is proposed based on diversity optimisation, integrated into cuckoo search optimisation algorithm based on levy flight mechanism. The algorithm expands the search scope as well as fully retains the amount of effective particles and the diversity of particles. Under the environment of MATLAB 7.0 operation, the simulation experiment is conducted, comparing the proposed algorithm with original particle filter algorithm and the improved particle filtering algorithm based on particle swarm optimisation by state estimation experiment and moving target tracking experiment. The results of the experiment show that the proposed algorithm operates well, improving the phenomenon of particle degradation and deficiency, and obtains high tracking accuracy, good real-time performance and robustness for video moving targets.

Particle filter Particle degeneracy Moving target tracking Particle diversity optimisation

2015-07-23。国家自然科学基金项目(61272253)；辽宁省科学技术研究项目(2014231001)；辽宁省教育厅科学研究项目(L2015443)。刘剑，教授，主研领域：视觉图像识别，智能控制，电梯优化调度等。郭文博，硕士生。李凌燕，硕士生。许帅宏，硕士生。

TP391

A

10.3969/j.issn.1000-386x.2017.01.025