改进的粒子群优化目标跟踪方法

郭巳秋，许廷发，王洪庆，张一舟，申子宜

（北京理工大学光电学院光电成像技术与系统教育部重点实验室，北京100081）

改进的粒子群优化目标跟踪方法

郭巳秋，许廷发*，王洪庆，张一舟，申子宜

（北京理工大学光电学院光电成像技术与系统教育部重点实验室，北京100081）

针对粒子群优化算法应用在目标跟踪时,其惯性权重调节机制的局限性,提出了改进的粒子群优化目标跟踪方法。首先,对目标及粒子群算法中相应参数进行初始化；接着,引入粒子进化率的概念,对惯性权重调节机制进行改进,根据每代每个粒子的不同状态及时调整惯性权重；然后,在更新粒子的速度和位置的同时,更新个体最优解和全局最优解,进行下一次迭代；最后,比较粒子的适应度,选择相似性函数值最大的区域为目标。实验结果表明,该方法与使用自适应惯性权重调节机制的粒子群优化目标跟踪方法相比,减少了获取相同适应度所需的迭代次数,运算效率提高了42.9％。实现了目标在相似性函数出现“多峰”情况下的准确定位,对目标出现部分遮挡的情况具有很好的适应性。

目标跟踪；粒子群优化；粒子进化率；惯性权重

1 引言

近年来,目标跟踪技术一直是计算机视觉领域的研究热点,目前主要使用的目标跟踪方法有质心跟踪法、相关跟踪法、波门跟踪法、光流法和Mean-Shift跟踪法等［1-5］。质心跟踪法和波门跟踪法实时性好,复杂度较低,但稳定性较差；相关跟踪法和光流法具有较好的稳定性,但实时性难以得到保证；Mean-Shift跟踪法比较容易受到背景的影响,在复杂环境中容易丢失目标。随着研究的不断深入,新的跟踪算法不断涌现。粒子群优化算法（Particle Swarm Optimization,PSO）容易实现且简单有效,同时,由于算法具有很好的多峰搜索能力,可以快速遍历搜索空间,迅速收敛,使其在解决目标跟踪过程中出现部分遮挡,即相似性函数出现“多峰”的跟踪问题时具有一定的优势［6］。

1995年,美国学者Kennedy和Eberhart在鸟群觅食行为的启发下提出了粒子群优化算法［7］。算法提出之后,受到了国内外研究学者的广泛关注,并将其用于解决优化问题［8-10］。算法的运行需要一些参数的选择,如惯性权重等,参数一般是通过实验确定的,其好坏直接影响粒子群的优化效果［11］。1998年,Eberhart与Shi首次提出了惯性权重的概念［12］,通过实验发现,当惯性权重为0.729 8、加速系数为1.496 18时,算法具有较好的收敛性。2006年,Chatterjee和Siarry提出一种非线性递减的调节机制［13］,根据迭代次数对惯性权重进行调节,惯性权重由最大值非线性递减到最小值。2011年,Alfi提出了一种自适应的调节机制,依靠返回值调节惯性权重［14］。2013年, Pluhacek提出一种新的自适应惯性权重调节机制,对粒子适应度排序划分粒子等级,根据粒子等级作为返回值调节惯性权重［15］。

但是,以上文献中提出的惯性权重调节机制都存在一定的局限性：（1）恒定或随机的惯性权重调节机制,不具有普遍适用性；（2）线性或非线性的惯性权重调节机制,仅仅依靠迭代次数进行调节,没有考虑到每个粒子的状态；（3）自适应的惯性权重调节机制,一般依靠返回值进行调节,但这一返回值本身并不能够作为评价惯性权重适应性的可靠标准。

针对这些问题,本文引入粒子进化率的概念以改进惯性权重的调节,充分考虑每一代中每个粒子的不同情况,精确地根据粒子的状态及时调整惯性权重,优化求解目标相似性度量函数,减少目标跟踪过程中达到相同适应度所需的迭代次数,提高运算效率,实现部分遮挡的目标跟踪。

2 改进的粒子群优化方法

2.1 粒子群优化方法

粒子群算法首先生成初始种群（即初始解）,就是在解空间里随机的初始化一群粒子（Particle）,每个粒子都是优化问题的一个可行解,并由目标函数为每个粒子确定一个适应度（Fitness Value）。每个粒子将在解空间中运动,并由一个速度决定其方向和距离。粒子追随当前时刻最优粒子运动,经过逐代搜索最后得到最优解。

粒子群优化算法的数学表达式如下［16］,设在一个n维搜索空间中,由PopSize个粒子组成的种群X=｛x1,…xi,…xPopSize｝,其中第i个粒子位置为xi=（xi1,xi2,…xin）T,其速度为υi=（υi1,υi2,…υin）T,它的个体极值为pbesti=（pbesti1,pbesti2,…pbestin）T,种群全局极值为gbest=（gbest1,gbest2,…gbestn）T。粒子按照式（1）、式（2）更新速度与位置：

其中d=1,2,…n,i=1,2,…PopSize,PopSize为种群规模,t为当前迭代的代数,rand1和rand2为［0, 1］均匀分布随机数,c1与c2为加速常数（Acceleration Coefficients）,ω为惯性权（Inertia）。式（1）第一部分为粒子的动量,表示粒子自身运动的惯性,可以避免粒子在搜索方向上的摆动；第二部分为“个体认知（Self Cognition）”部分,表示粒子自身对环境适应的自然倾向；第三部分为“社会认知（Social Cognition）”部分,表示粒子与邻域群体的信息共享［17］。

2.2 改进的粒子群优化算法

研究表明［13］,当惯性权重较大时,粒子群优化算法具有较好的全局收敛能力,而较小的惯性权重则有利于局部收敛。基于惯性权重对粒子群优化算法搜索性能的重要影响,很多研究者通过改变惯性权重进而改进算法的优化性能。目前,改进方法大致可分为固定或随机的惯性权重调节机制、线性或非线性惯性权重调节机制、自适应惯性权重调节机制等。

为了进一步探讨惯性权重ω对粒子群优化的影响,下面把问题简化为一个单峰函数优化的情况,并且设定种群只有两个粒子。对于简化后种群粒子可能出现的两种情况,首先定义,这两个粒子中更接近最优解的粒子为全局最优粒子或是个体最优粒子,当只存在两个粒子时,把更接近最优解的粒子简称为最优粒子,另一个粒子称为次优粒子。

图1（a）与（b）中,虚线区域表示次优粒子下次可能会出现的区域,实线区域表示整个种群能够取得更接近最优解的区域,称为提升区域。粒子适应度由粒子离最优解的实际距离决定。粒子离最优解越近,表示其适应度越高,即算法得到的解越精确。显然提升区域的大小由最优粒子离最优解的距离决定。

对于图1（a）中的情况,两个粒子离最优解的距离相较于两个粒子彼此间的距离很大,粒子需要迭代多次才能靠近最优解。在这种情况下,对于最优粒子,由于它需要以很大的速度向最优解靠近,所以需要比较大的ω值来进行调节；对于次优粒子,它的速度是由粒子原来的速度和它与最优粒子之间的距离共同决定的,即次优粒子也需要较大的ω值。

对于图1（b）中的情况,最优粒子离最优解很近,次优粒子也在最优解附近区域运动。当次优粒子以较大速度向最优解靠近时,其会在下一时刻冲过提升区域,不断在虚线区域震荡,无法进入提升区域。在这种情况下,为了提高解的精确度,需要降低粒子的速度,即需要较小的ω值来进行调节,让粒子可以缓慢地靠近最优解。

需要注意的是,两个粒子向最优解靠近的过程中,次优粒子的适应度可能会超越最优粒子,这时两个粒子的角色发生交替,次优粒子成为最优粒子,最优粒子成为次优粒子。这一情况在运行过程中不断发生。当种群粒子数不止两个的时候,全局最优粒子即可认为是模型中的最优粒子,任何一个其它粒子都可以认为是次优粒子,这时,上述简化模型同样适用。

在算法运行过程中,上述两种情况都可能会发生。由于粒子离最优解的实际距离可能很大也可能很小,因此对应的粒子适应度也可能很大或很小。显然,固定或随机的惯性权重调节机制是不合适的。单纯依靠粒子迭代次数线性或非线性地调节惯性权重的方法,是用一个适中的惯性权重使优化达到较好的效果,没有充分考虑到每代粒子中每个粒子的不同情况。自适应惯性权重调节机制是根据返回值来调节惯性权重的,通常这一返回值会选用适应度或是其派生值。但是,适应度本身并不是一个评价惯性权重的可靠标准。当粒子的适应度高时,由于粒子所处情况不同,可能会需要不同的惯性权重来进行调节；当适应度低时,同样可能对惯性权重有不同的需求。

为解决上述问题,本文提出了一种改进的惯性权重调节机制,引入粒子进化率的概念,作为粒子状态的描述。当粒子进化率较低时,表明粒子都集聚在一个离最优解较远的位置,并且整个种群都在缓慢向最优解靠近,即图1（a）所示情况；当粒子进化率比较高时,表明粒子在最优解附近震荡,即图1（b）所示情况。

定义：第t代中第i个粒子的粒子进化率为：

式中,pbest1（t）表示第t代粒子中第i个粒子当前找到的个体最优解。结合粒子进化率公式,整个种群的进化情况可以描述为：

当第i个粒子的第t代个体最优解比第t-1代更优时,式（3）值为0,当所有粒子的粒子进化率都为0时,计算可得De（t）最小值Dmin为0.5,反之,计算可得De（t）最大值Dmax为2。对式（4）进行归一化处理得：

2.3 改进的粒子群目标跟踪方法

本文改进的粒子群优化目标跟踪方法,在充分考虑到每代每个粒子所处情况的同时,结合粒子进化率的概念计算出整个种群的进化概率,进一步使用种群的进化概率调节惯性权重,使惯性权重的调节更加合理,提高算法效率。

算法的主要步骤如下：

（1）对粒子群参数进行初始化,设定加速常数c1和c2,最大迭代代数Tmax,设定粒子群体的数目PopSize,参数的初始化与实际跟踪精度有关；

（2）读取图像,确定目标特征描述与相似度；

（3）读取下一帧图像,初始化当帧粒子个体、个体最优、全局最优；

（4）计算粒子的适应度,比较粒子与个体最优解pbesti的适应度,如果当前值比pbesti更优,则置pbesti为当前值,并记录当前适应度为pbesti对应适应度；

（5）比较粒子与种群最优解gbest（t）的适应度,如果当前值比gbest（t）更优,则置gbest（t）为当前粒子值及对应适应度；

（6）根据引入粒子进化率概念的惯性权重式（6）调节式（1）、式（2）,更新粒子的速度与位置,产生新种群X（t+1）；

（7）检查结束条件（一般为t≥Tmax或评价误差小于给定精度）,若满足,则结束寻优,退出,跳转至步骤3,否则t=t+1,跳转至步骤4。

3 实验与分析

本实验是在Windows 7操作系统、MATLAB环境下,使用Intel Core i3 2.93GHz处理器,内存为4GB的计算机进行的。实验对分辨率720× 576,帧频25 fps的原始视频图像序列进行处理。

3.1 目标跟踪效果

实验1：对于目标跟踪过程中无遮挡的情况,采用行驶中的车辆作为测试图像序列,部分跟踪结果如图2所示。整个跟踪过程准确稳定,并能保证跟踪的实时性,单帧图像处理速度优于23 ms。

实验2：对于目标跟踪过程中出现少量遮挡的情况,采用汽车过杆作为测试图像序列,跟踪结果如图3所示。目标从第35帧图像开始被少量遮挡,直到第47帧图像目标开始脱离遮挡。在整个跟踪过程中,跟踪窗基本可以完整包含目标,跟踪稳定,单帧图像处理速度优于30 ms。

实验3：对于目标跟踪过程中遮挡较多的情况,为了充分体现本文方法在相似性函数出现“多峰”情况下的优势,使用工程中较为常用的MAD算法（平均绝对差分算法）和本文方法进行了实验对比。采用汽车过遮挡牌作为测试图像序列,该图像获取时摄像机静止,第14帧目标（白色SUV）进入遮挡区（指示牌）；第22帧目标开始被大量遮挡,第30帧目标穿过遮挡区。

图4为使用MAD算法的跟踪结果。第22帧目标被大量遮挡时,该方法开始丢失目标,直到第28帧跟踪效果开始恢复,第30帧目标基本穿过遮挡区后,才重新实现了对目标的跟踪,单帧图像处理速度超过70 ms。

图5为本文方法的跟踪结果。从第14帧目标开始被遮挡到第30帧目标脱离遮挡,整个过程中跟踪窗基本可以包含目标,跟踪稳定。即在目标出现较多遮挡时,改进的粒子群跟踪算法依旧可以实现目标的准确跟踪,单帧图像处理速度优于40 ms。

通过图4与图5的对比可以看出,在跟踪过程中,当目标出现较多的遮挡时,使用MAD算法的跟踪效果较差,并且由于算法的运算量较大,难以满足实时性的需求。而使用改进的粒子群优化算法进行的目标跟踪,则具有较好的抗遮挡能力,并基本可以保证运算的实时性。

3.2 算法效率比较

为了说明本文改进的粒子群优化目标跟踪方法相比其他粒子群优化目标跟踪方法,在达到相同的适应度时,具有迭代次数少,跟踪效率高的特点,分别使用非线性惯性权重调节机制（由于线性和非线性惯性权重调节机制比较相似,本文用非线性调节机制作为两者代表）、自适应惯性权重调节机制和改进的惯性权重调节机制,对上一节中的3组视频图像序列进行了实验对比,最终选用比较有代表性的第3组视频图像序列获得的实验数据进行分析。

设置最大迭代次数MAXIT为100,在适应度即相似性函数值达到0.98的情况下,对比使用以上3种不同惯性权重调节方法的跟踪效率。显然,在达到相同的相似性函数值的情况下,迭代次数越小算法越优,效率越高。图6是分别使用3种惯性权重调节方法进行实验,获得的平均迭代次数折线图,纵坐标为迭代次数,横坐标为图像帧数。

从上图中可以看出,改进方法的运算效率明显优于非线性方法。与自适应方法相比,从目标出现遮挡的第14帧开始,迭代次数产生明显差异,本文提出的根据每代每个粒子的不同情况调节惯性权重的方法可以更准确地满足算法的要求,并有效提高算法的运算效率。经计算,相较于自适应方法,使用改进方法的运算效率提高了42.9％。

4 结论

本文针对粒子群优化算法应用在目标跟踪时,其惯性权重调节机制存在的问题,提出了改进的粒子群优化目标跟踪方法。本方法结合粒子进化率的概念,在充分考虑了每代每个粒子不同情况的基础上,能够精确地根据粒子的状态及时调整惯性权重,更有效地完成寻优,大幅度减小运算量。实验结果表明,改进的粒子群优化目标跟踪方法以更小的迭代次数达到相同的适应度,实现了更快速的迭代,与自适应的粒子群目标跟踪方法相比,运算效率提高了42.9％,具有较好的实时性,很好地解决了目标部分遮挡的跟踪问题。

［1］王铭明，陈涛，王建立，等.Mean-shift跟踪算法及其在光电跟踪系统中的应用［J］.中国光学,2014,7（2）：332-338. WANGM M,CHEN T,WANG JL,etal..Mean-shift tracking algorithm and its application in optoelectronic tracking system［J］.Chinese Optics,2014,7（2）：332-338.（in Chinese）

［2］闫辉，许廷发，吴青青，等.多特征融合匹配的多目标跟踪［J］.中国光学,2013,6（2）：163-170. YAN H,XU T F,WU Q Q,et al..Multi-object tracking based onmulti-feature jointmatching［J］.Chinese Optics,2013, 6（2）：163-170.（in Chinese）

［3］薛陈，朱明，陈爱华.鲁棒的基于改进Mean-shift的目标跟踪［J］.光学精密工程,2010,18（1）：234-239. XUE CH,ZHU M,CHEN A H.Robustobject tracking based on improved Mean-shift algorithm［J］.Opt.Precision Eng., 2010,18（1）：234-239.（in Chinese）

［4］龚俊亮，何昕，魏仲慧，等.采用改进辅助粒子滤波的红外多目标跟踪［J］.光学精密工程,2012,20（2）：413-421. GONG J L,HE X,WEIZH H,et al..Multiple infrared target tracking using improved auxiliary particle filter［J］.Opt. Precision Eng.,2012,20（2）：413-421.（in Chinese）

［5］王万国，王滨海，王振利，等.Mean-shift跟踪算法中核函数参数的评估与分析［J］.光学与光电技术,2012,10（2）：80-92. WANGW G,WANG B H,WANG ZH L,et al.Evaluation and analysis of the kernel function parameters in Mean-shift tracking algorithm［J］.Optics and Optoelectronic Technology,2012,10（2）：80-92.（in Chinese）

［6］尹宏鹏，刘兆栋，罗显科，等.一种基于粒子群优化的目标跟踪特征选择算法［J］.计算机工程与应用,2013,49（17）：164-168. YIN H P,LIU ZH D,LUOX K,etal.Target tracking feature selection algorithm based on particle swarm optimization［J］. Computer Engineering and Applications,2013,49（17）：164-168.（in Chinese）

［7］KENNEDY J,EBERHART R.Particle swarm optimization［J］.IEEE,1995,4：1942-1948.

［8］CHEN J.PSO algorithm with stochastic inertia weight and its application in clustering［J］.IEEE,2011,2：59-62.

［9］邹德旋，王鑫，陈传虎，等.基于改进粒子群的虹膜定位算法［J］.光学精密工程,2014,22（4）：1056-1063. ZOU D X,WANG X,CHEN CH H,etal..Iris location algorithm based on improved particle swarm optimization［J］.Opt. Precision Eng.,2014,22（4）：1056-1063.（in Chinese）

［10］许廷发，赵思宏，周生兵，等.DSP并行系统的并行粒子群优化目标跟踪［J］.光学精密工程,2009,17（9）：2236-2240. XU T F,ZHAO SH,ZHOU SH B,etal..Particle swarm optimizer tracking based on DSP parallel system［J］.Opt.Precision Eng.,2009,17（9）：2236-2240.（in Chinese）

［11］张超，李擎，陈鹏，等.一种基于粒子群参数优化的改进蚁群算法及其应用［J］.北京科技大学学报,2013,35（7）：955-960. ZHANG CH,LIQ,CHEN P,et al..Improved ant colony optimization based on particle swarm optimization and its application［J］.J.Uniυersity of Science and Technology Beijing,2013,35（7）：955-960（in Chinese）

［12］SHIY,EBERHART R.Amodified particle swarm optimizer［C］.Proceedings of the IEEE International Congress on Evolutionary Computation,Anchorage,May 4-9,1998：69-73.

［13］CHATTERJEE A,SIARRY P.Nonlinear inertiaweight variation for dynamic adaption in particle swarm optimization［J］. Computer and Operations Research,2006,33（3）：859-871.

［14］ALFIA.PSO with adaptive mutation and inertia weight and its application in parameter estimation of dynamic systems［J］.Acta Automatica Sinica,2011,37（5）：541-549.

［15］PLUHACEK M,SENKERIK R,DAVENDRA D,et al..On the behavior and performance of chaos driven PSO algorithm with inertia weight［J］.Computers＆Mathematicswith Applications,2013,66（2）：122-134.

［16］秦华，韩克祯，类成新.用粒子群算法校正三片镜系统的像差［J］.中国光学,2013,6（1）：64-72. QIN H,HAN K ZH,LEICH X.Correction of aberration for three-lens system by particle swarm optimization algorithm［J］.Chinese Optics,2013,6（1）：64-72.（in Chinese）

［17］DOCTOR S,VENAYAGAMOORTHY G K.Improving the performance of particle swarm optimization using adaptive critics designs［C］.IEEE Swarm Intelligence Symposium,Pasadena,CA,USA,June 8-10,2005：393-396.

郭巳秋（1989-）,女,吉林长春人,硕士研究生,2012年于北京理工大学获得学士学位,主要从事目标检测、跟踪算法方面的研究。E-mail：guo_qiuqiu@126. com

许廷发（1968-）,男,黑龙江肇东人,博士,教授,博士生导师,1992年、2000年于东北师范大学分别获得学士、硕士学位,2004年于中国科学院长春光学精密机械与研究所获得博士学位,2006年于华南理工大学电子与信息学院博士后出站,主要从事光电成像探测与识别等方面的研究。E-mail：xutingfa@163.com

张一舟（1990-）,女,山西太原人,硕士研究生,2012年于南京理工大学获得学士学位,主要从事红外图像非均匀性校正方面的研究。E-mail：tyzyz163@163. com

申子宜（1989-）,女,陕西西安人,硕士研究生,2012年于西安工业大学获得学士学位,主要从事图像配准、亚像元方面的研究。E-mail：ziyishen@126.com

王洪庆（1987-）,男,吉林长春人,博士研究生,2012年于北京理工大学获得硕士学位,主要从事光电成像探测与识别等方面的研究。E-mail：wang_ hongqing@126.com

Object trackingmethod based on improved particle swarm optim ization

GUO Si-qiu,XU Ting-fa*,WANG Hong-qing,ZHANG Yi-zhou,SHEN Zi-yi
（Key Laboratory of Optoelectronics Imaging Technology and System of Ministry of Education, School of Optoelectronics,Beijing Institute of Technology,Beijing 100081,China）
*Corresponding author,E-mail：xutingfa@163.com

To overcome the limitations of inertiaweightadjustmentmechanism when the particle swarm optimization algorithm is applied to object tracking,an improved particle swarm optimization object tracking algorithm is proposed.Firstly,the object and the parameters in particle swarm optimization algorithm are initialized.Secondly,the inertia weight adjustmentmechanism is improved by using the evolution rate of particle, and the inertiaweight is achieved by taking the conditions of different particles in each generation into consideration.Then the speed,the position,the individual optimum and the global optimum of the particles are updated simultaneously while the next iteration is proceeding.Finally,the area which has the largest similarity function value is defined as the object by comparing the fitness value of each particle with the others.Experimental results indicate that themethod reduces the iterations to obtain the same fitness value,and improves the operation efficiency by 42.9％in comparison with the particle swarm optimization object tracking method which uses self-adapted inertia weight adjustmentmechanism.The accurate positioning of the object is a-chieved in the case of the similarity function presenting“multimodal”,and themethod iswell adapted to the situation when partial occlusion occurs in object tracking.

object tracking；particle swarm optimization；evolution rate of particle；inertia weight

TP391.41

A

10.3788/CO.20140705.0759

2095-1531（2014）05-0759-09

2014-06-18；

2014-08-16

国家自然科学基金资助项目（No.61172178,No.61371132）；国家国际科技合作专项资助项目（No. 2014DFR1096）；高等学校博士学科点专项科研基金资助项目（No.20121101110022）