基于多特征的退火粒子滤波视觉目标跟踪算法

2015-05-30 19:04赵迎春郭强
软件工程 2015年7期
关键词:粒子滤波模拟退火

赵迎春 郭强

摘 要:提出了一种新的融合多特征的基于改进模拟退火粒子滤波跟踪算法。首先,针对重要性采样粒子滤波算法中重要性抽样密度函数未考虑最近观测值,不能有效逼近真实后验密度函数的问题,通过采用改进的模拟退火(SA)方法优化重要抽样密度函数,并利用不同温度下扰动函数和Metropolis准则克服粒子匮乏缺陷;同时,针对SA方法在粒子滤波视觉跟踪应用上效率不高的缺陷,对经典模拟退火算法进行改进,降低了参数选择的敏感性,保持了原算法全局寻优的优点,提高了算法的速度。

关键词:视觉跟踪;粒子滤波;模拟退火;多特征融合;粒子匮乏

中图分类号:TP391.41 文献标识码:A

1 引言(Introduction)

视觉跟踪是对视频序列中目标进行观测、推理获得目标的运动参数,如位置、速度、加速度,以及运动轨迹。目标跟踪的难点主要在于杂波环境、复杂背景、遮挡、姿态及光照变化情况下,如何有效提取区分性和稳健性较好的目标视觉特征并进行稳定的跟踪[1]。当前许多跟踪算法被提出,如distribution fields[2],基于时空上下文跟踪算法[3],MIL跟踪算法[4]等,最新研究综述见[5,6]。视觉特征如颜色、纹理、边缘和轮廓等至关重要,单一特征已很难取得满意的跟踪性能,因此多视觉特征融合跟踪被广泛采用[7]。同时设计一个实时、鲁棒性和跟踪精度高的跟踪算法仍然具有挑战性。

粒子滤波是一种比较有效的跟踪算法,它通过蒙特卡洛抽样与贝叶斯推理以适当运算量实现了状态估计,但由于复杂背景、物体遮挡等原因,跟踪问题的观测似然模型往往呈现为多峰值的非线性、非高斯系统的状态估计,在实际情况下很难从后验概率分布抽样。常用的粒子滤波利用重要性采样(SIR)方法通过选取建议分布得到后验概率分布的带权粒子,具有易于计算递推权重、建议概率密度容易被采样等优点,但缺点是没有考虑最新观测信息导致权值方差较高且无法处理高维状态空间大计算量和粒子退化等问题。

在上述分析基础上,本文在粒子滤波视频跟踪框架下融入改进的非常快速模拟退火算法(称为ISAPF),用该退火算法动态改进了重要抽样密度函数,使粒子避免陷入局部区域解,并利用颜色特征似然函数和边缘特征似然函数实现了对目标的稳定跟踪。

2 粒子滤波算法(Particle filter algorithm)

粒子滤波算法采用序贯蒙特卡洛模拟经重要性采样得到一组带相关权值的粒子以近似表示目标后验概率密度函数(PDF),假设系统的递归过程符合马尔科夫假设,则公式如下:

(1)

式中,表示粒子或随机状态,即可能的目标状态;表示到k时刻所有状态的样本集;表示粒子的权重;表示观测值;推导权重公式如下

(2)

因在实际情况下很难得到PDF,故利用建议分布(重要性概率密度函数)函数近似后验分布,为似然概率分布,为转移概率分布。SIR重要性重采样算法将建议分布采用先验密度,即:。

3 模拟退火粒子滤波算法(Simulated annealing

particle filter)

模拟退火算法(Simulated Annealing,SA)作为局部搜索算法的扩展,利用概率函数有概率的接受较差的扰动解为新解,使其避免了传统梯度搜寻法往往陷入区域解的缺点,而使模拟退火法有机会跳脱区域解,让粒子种群往似然函数全局最佳解收敛。

3.1 模拟退火算法

退火的基本思想从将温度升到足够高,再让其逐渐降温。加温时,固体内部粒子随温升变为无序状,内能增大,而徐徐冷却时粒子渐趋有序,在每个温度都达到平衡态,最后在常温时达到基态,内能减为最小。从某一初始温度开始,伴随温度的不断下降,利用以概率接受新状态的Metropolis准则,结合概率突跳特性在解空间中随机寻找得到全局最优解。

3.2 改进模拟退火算法(ISAPF)

传统SA虽然有较强的寻优能力、初值鲁棒性强、简单通用等有点,但是模拟退火算法存在的主要问题是运行时间太长。其次,模拟退火算法的性能对参数及初始值的选取十分敏感,比如:较高的初始温度、缓慢的退火降温速率、大量的迭代次数及同一温度下足够的扰动次数导致了优化过程较长。不同的参数可能导致算法性能的巨大差异,而优化参数设置和具体的问题是密切相关的,这些方面都限制了模拟退火算法的应用效果。

(1)SA中模型扰动通常采用高斯分布或均匀分布,而VFSA采用依赖于温度的Cauchy分布法:即

(3)

(4)

式中,为[0,1]内均匀分布的随机数;[,]为x的随机扰动取值范围;该模型在高温下搜索范围大,在低温时搜索仅在当前模型附近。因为该分布有平坦的“尾巴”,使搜索易于跳出局部极值。加快了SA的收敛速度。是随机扰动变量。

(2)退火降温函数为,为退火率;为迭代次数。

4 实验与性能分析(Experiments and performances

analysis)

仿真实验采用典型的一维单变量非静态增长模型,此一维模型具有很强的非线性,本文的方法,充分考虑了运动边缘信息和新的建议分布,因此既保证了目标不受静止复杂背景的影响,又能够很好地捕捉目标的边缘和轮廓信息,跟踪窗口准确地捕捉到目标的瞬间变化,能实现遮挡下的准确跟踪。一维模型具有很强的非线性,其状态递推方程和观测方程如下:

(5)

(6)

其中,、分别为系统的过程噪声和观测噪声;~,~。进行100个时刻的仿真,横坐标代表时刻,纵坐标代表粒子状态,可以简化为跟踪目标位置。

图1 PF、模拟退火算法、ISAPF三种算法100粒子

目标跟踪仿真比较结果

Fig.1 Results of three algorithms on target tracking

by using 100 particles

5 结论(Conclusion)

本文针对退火算法搜索全局最优解收敛速度较慢以及初始参数敏感,不利于结合粒子滤波进行目标跟踪的问题,提出了一种新的融合多特征的改进退火粒子滤波算法。该算法通过对算法要素中采用的退火降温函数、回火升温等方面进行优化,并结合民主融合策略自适应地调节

特征在跟踪中的权重,使得粒子集中向高似然区,保证了粒子的多样性,在算法的实时性和鲁棒性间取得了平衡,得到更好的追踪性能。

仿真实验表明改进算法比退火粒子滤波算法能更快的收敛到全局最优粒子,提高了实时性,虽然比标准粒子滤波算法增加了少量计算时间,但在可接受范围内,并提高了跟踪精度。在变化的实际场景测试也表明,本文算法能较好地适应背景干扰、部分遮挡等复杂环境,并可应用于其他跟踪环境,具有广泛应用前景。

参考文献(References)

[1] K.Zhang,H.Song.Real-Time Visual Tracking via Online Weighted Multiple Instance Learning[J].Pattern Recognition, vol.46,2013:397-411.

[2] Sevilla-Lara,L.Erik.Distribution fields for tracking[J].Computer Vision and Pattern Recognition,USA,June 2012:1910-1917

[3] K.Zhang,L.Zhang,Q.Liu,D.Zhang,M.H.Yang.Fast Visual Tracking via Dense Spatio-Temporal Context Learning[J].in Proceedings of the 13th European Conference on Computer Vision (ECCV),2014:127-141.

[4] B.Boris,M.H.Yang,S.Belongie.Visual tracking with online multiple instance learning[J].Computer Vision and Pattern Recognition,2009:983-990.

[5] H.Yang,Shao.L,F.Zheng,L.Wang and Z.Song.Recent advances and trends in visual tracking:A review.Neurocomputing, Vol.74,2011:3823-3831.

[6] A.Smeulders,D.Chu,R.Cucchiara,S.Dehghan,M.Shah.Visual Tracking:An Experimental Survey.IEEE Transactions on Pattern Analysis and Machine Intelligence,Vol.1,2013.

[7] Zhenjun Han,Qixiang Ye,Jianbin Jiao.Combined feature evaluation for adaptive visual object tracking [J].Computer Vision and Image Understanding,2011,115:69-80.

作者简介:

赵迎春(1980-)男,硕士,工程师.研究领域:软件开发.

郭 强(1980-)男,博士,工程师.研究领域:模式识别.

猜你喜欢
粒子滤波模拟退火
结合模拟退火和多分配策略的密度峰值聚类算法
模拟退火遗传算法在机械臂路径规划中的应用
基于智能粒子滤波的多传感器信息融合算法
基于重采样粒子滤波的目标跟踪算法研究
基于模拟退火剩余矩形算法的矩形件排样
基于模糊自适应模拟退火遗传算法的配电网故障定位
复杂场景中的视觉跟踪研究
一种针对海面弱小目标的检测方案
SOA结合模拟退火算法优化电容器配置研究
基于遗传-模拟退火算法的城市轨道交通快慢车停站方案