特征粒子范文（精选7篇）
特征粒子 第1篇
关键词：粒子滤波,多实例学习,梯度增强,特征选取
近些年来, 视频跟踪算法在计算机视觉领域得到广泛的研究, 在视频监控、人机交互以及交通管制方面都有着广泛的用途。尽管在背景环境简单目标物不变的情况下, 目标跟踪算法已取得了很多成功, 但跟踪未知的物体仍然存在非常大的挑战。导致跟踪困难的因素有很多, 比如目标物本身存在形变以及突然消失在视野, 以及环境背景存在光照、遮挡的影响以及存在尺度变化等影响。
为提高跟踪的精度, 近年来很多视频跟踪算法都把跟踪视为跟踪与检测两个过程。基于这种模型视频跟踪可看成表现模型与运动模型两部分。由于跟踪序列中目标往往存在变化, 寻找一种自适应的表现模型越来越重要。依据不同的表现模型, 跟踪算法可分为两类:生成模型和判别模型。生成模型从统计的角度观察数据总体分布, 学习一种能表示目标的模型, 然后利用最小重建误差在图像区域内搜素目标。在IVT[1]中, 一种增长的子空间模型被用来学习并搜索目标。通过在线学习机制, 不断更新跟踪模块中显著特征点和检测模块相关模型, TLD[2]算法的精度将会随视频序列的变化不断累加。
与生成模型不同, 判别模型把视频跟踪问题视为一个二值分类任务, 通过寻找分类器的最优决策面进行判断以选取目标。Collins[3]证明了以在线方式选取判别特征会改善跟踪算法的性能。同时, Boosting方法[4]通过结合若干个弱分类器组合成强分类器, 可以显著改善分类器的性能。这些算法中, 以Online Ada Boost (OAB) [5]跟踪算法最为著名。但这些视频跟踪算法只利用观测值附近唯一的正实例, 一旦视频跟踪过程有噪声的引入, 都会遇到目标漂移问题。Babenko提出了一种基于多实例学习的跟踪方法MILTrack[6], 跟踪时以实例集合的形式表示并判断后验概率, 能有效克服跟踪过程中样本的漂移问题。
本文提出的算法能够改善以上提到跟踪算法的漂移问题, 算法的主要贡献有:
①将粒子滤波的运动模型与多实例学习的分类器更新策略相结合, 提出了一种基于粒子滤波运动框架的多实例学习的跟踪算法。运用多实例学习更新分类器模型, 并在下一帧使用粒子滤波运动模型生成所需的样本, 求得每个样本的响应。
②采用粒子滤波的运动模型, 并分解基本运动模型为不同的子运动模型。考虑到粒子滤波运动变化的随机性, 通过构建基于不同方差的运动剧烈情况, 实验跟踪的精度与鲁棒性将会提高。
③提出了一种新的在线特征选取策略。与原始MIL中提到的损失函数不同, 本文在实例水平上主动选取需要的特征, 直接将分类器的权值与样本的重要性相匹配, 并使用梯度增强法搜索目标。
本文提出的算法称为基于在线判别特征选取的粒子滤波跟踪算法, 后文简写为PFFS。算法首先在前一帧的目标周围分别采样半径为α与β (α<β) 正负样本, 通过后文提到的在线主动特征选取方案在上述两个集合中分别抽取特征, 然后在M个弱分类器组成的分类器池中依次迭代选取K个弱分类器, 这些弱分类器线性结合组成强分类器;下一帧到来时, 运用粒子滤波不同的运动模型生成不同的样本集合, 运用强分类器分别求得每个样本不同的响应, 其中最大的响应即为本帧中预测的目标, 重复这一过程即完成视频序列的跟踪。
本文将粒子滤波的运动模型与多实例学习的更新模型相结合, 提出了一种基于粒子滤波框架的在线判别特征选择的跟踪算法 (PPFS) 。后文中, 前两部分将分别讨论粒子滤波运动模型与在线判别特征的选取原理, 第三部分讨论了在线判别特性选取的具体实现细节, 第四部分将以不同的实验环境证明本文提出算法的实际跟踪效果。
1 粒子滤波运动模型
粒子滤波[7]是一种基于蒙特卡洛方法的递归算法。它的基本思想是用一组带权重的随机粒子来近似贝叶斯估计, 进而预测下一时刻的后验概率密度。由于其运动的状态对于非高斯非线性过程没有很严格的约束, 尤其适合视频跟踪。
假定t时刻的状态值为Xt, 直到t时刻的观察值为Y1:t。粒子通过以下的贝叶斯模型预测后验概率p (Xt|Y1:t) :
其中, p (Yt|Xt) 为观测模型, 它用来表示目标对象在t时刻与观测值相似度。p (Xt|Xt-1) 描述的是转移模型, 又称为运动模型, 它表示基于前一时刻的运动状态推算下一时刻运动状态的概率。目标物在t时刻的状态就可以通过最大后验概率估计 (MAP) 求取, 上述概率达到最大值的样本 (粒子) 即为需要预测的状态:
其中, Xt (l) 为状态Xt的第1个样本。
这样, 粒子滤波通过观测与状态模型, 就把运动目标的跟踪问题转化为系统状态的估计问题。值得注意的是, MIL跟踪[6]并没有在每帧中都维护运动分布函数, 下一帧的采样中心点即为上一帧目标物的坐标点, 这样限制了采样目标的随机性。考虑到视频跟踪中, 每一帧的运动变化剧烈程度不同, 本文提出了一种运动模型分解策略。通过把基本的运动模型p (Xt|Xt-1) 分解成若干个子运动模型, 在新的一帧到来时, 分别求取不同子运动模型的最大后验概率p (Xt|Y1:t) , 并在所有运动模型中选取最好的粒子。
假设子运动模型为pm (Xt|Xt-1) , 其中m为运动模型的索引, 并假设实验共选取M个运动模型, 那么每一种特定的运动模型都可以用不同方差σm2的高斯分布来描述:
其中, G表示的是均值为Xt-1, 方差为σm2的高斯分布。
一般来说, 运动的剧烈程度跟方差的取值有关, 方差σm2越小说明选取的样本越集中, 运动就越平滑, 反之亦然。考虑到粒子的运动模型越复杂, 粒子数目也会过剩的原因, 本文中每五帧才更新一次运动模型。
通过不同的运动模型, 实验生成了权值不同的粒子。下一步需要确定每个粒子的权值, 取响应最大的粒子作为视频跟踪的目标位置。第三部分将更详细讨论后验概率的估计方法, 响应结果需转化为概率形式:
其中, 分类器HK由K个弱分类hK构成。
最后, 目标点的位置可由所有粒子中响应最大的粒子决定:
2 在线判别特征选取
与MILTrack[6]中介绍的损失函数不同, 本文提到的在线判别特征直接在实例水平上选取特征。假设样本空间分为两部分R+={x, y=1}以及R-={x, y=0}, 选取这两个样本中置信度平均值之差作为边界函数, 并使用梯度增强的方法选取最优的分类器。边界函数可定义为:
其中, |R+|与|R-|分别表示正负样本集合的基数。正样本集合R+={xi}i=0N-1含有N个样本, 负集合R-={xi}i=NN+L-1含有L样本 (L≈N) 。替换上式中积分为求和公式, 得到:
候选的弱分类器共有M个, h∈{h1, …, hM}, 在M个弱分类器中一次迭代选得到K个弱分类器。为了使Emargin最大, 这里采用了一种贪婪策略:
其中, Hk-1为最先选得的前k-1个弱分类器的线性组合。
为了提高分类器的性能, 使分类器对后一帧更有区分度, 本文使用了一种梯度提升 (Gradient Boosting) 的方法[8], 也称为最速下降方法。利用最速下降法, 可以求得式 (8) 中目标函数的最速下降方向:
其中
若要使得边界函数最大, 可以选取与gk-1最不相关的K个弱分类器, 来限制梯度与弱分类器的关系。利用文献[8]中提到的回归树方法, 对于每个样本求弱分类器的平均值, 并求梯度方向的平均, 可以得到:
。弱分类输出为正实例的平均值, 而不是单一的正实例样本, 考虑多个正实例就可以减轻实验漂移的现象。
3 算法的实现
可以将样本x中特征向量表示为f (x) = (f1 (x) , …, fK (x) ) T, 假设每个x中元素是独立分布的。则分类器H (x) 可以由一个朴素贝叶斯分类器表示成:
其中, 即为弱分类器, 并假设p (y=1) =p (y=0) 。
分类器HK由K个弱分类hK构成。当取得每个正负样本中的特征值后, 就可以更新每个弱分类器hK (x) 的参数。式 (12) 中, 假设每个弱分类器hK条件概率p (fk (x) |y=1) 及p (fk (x) |y=0) 满足高斯分布, 即:
当弱分类器得到新的样本数据后, 使用以下的更新策略是:
得到弱分类器方差与均值参数后, 选取得到的分类器即可用于下一帧, 以求得粒子滤波产生的样本特征值的响应值。值得注意的是, 与MILTrack不同, 这种基于在线判别特征选取的更新模型是基于实例水平构建的, 直接把样本的重要性与分类器权值匹配在一起, 可以简化多实例学习的构建过程并减少实验的计算量。判别特征选取主要步骤可总结如下:
输入:训练的数据集合{xi, yi}N+L-1i=0, 其中yi∈{0, 1}。
①用数据集合{xi, yi}N+L-1i=0更新弱分类器h∈{h1, …, hM}。
②分别计算式 (17) 中正负样本的平均弱分类器输出, m=1, …, M。
③初始化H0 (xi) =0, Hk (xi) 为前k个弱分类器组成的强分类器, 这里初始化第一个强分类器为0。
④从1增长到K的循环, K为选择器的个数。从M个候选弱分类器中依次选择K个分类器, 最后把这些分类器线性组合成强分类器。
⑤依次更新gk-1 (xi) =-σ (hk-1 (x) ) (1-σ (hk-1 (x) ) ) 。
⑥从1增长到M的循环, M为候选的弱分类器的总数。主动特征选取将会在这些弱分类器中寻找K个最优弱分类器以用于下一帧。
⑧m次的循环结束。
⑨选取使得边界函数达到最大值的弱分类器, m*=arg maxm (Em) , 并更新hk, hk←hm*。
⑩把前k个弱分类器依次相加, 线性组合成强分类器, 即, 并归一化。
11 K次循环完成。至此为止, K个弱分类器均已选出。
输出:强分类器HK (x) =∑Kk=1hk (x) 以及置信图函数P (y=1|x) =σ (hK (x) ) 。
4 实验结果分析与讨论
4.1 初始化参数配置
本文使用的特征为文献[6]中提到的类Haar特征, 可以使用积分图减少实验的计算量。实验使用的Haar为随机分布生成的线性组合, 这样能保持图像中特征点原来的区分度同时降低实验的计算量。本文所用的跟踪对比算法是:在线Ada Boost跟踪 (OAB) , 在线多实例跟踪 (MILTrack) 。实验中用到的算法参数都进行了优化, 每种跟踪方法都能达到最佳性能。实验使用的类Haar特征fk由2到6个随机选取的带权值矩阵组成。其中, 本文的算法和MILTrack算法采样的正实例样本半径α设为4, 均使用45个的正样本。作为对比, OAB算法只选取1个正样本。实验中负样本集Xζ, β使用的样本半径β=50, 并在其中随机采样65个样本。弱分类器的学习率η=0.85。最后, 弱分类器候选集的数目M设为250, 需要选取的弱分类器个数K设置为50。实验所用的编程环境为:CPU四核3.2GHz;内存4GB;仿真环境VS2010以及MATLAB7.0。
4.2 实验结果分析
针对不同的场景变化, 本文采用四组不同的对比实验。实验所用的图像序列都处理为灰度图像, 真实数据通过大量的人工标定求平均获得。所用的图像序列来自于MILTrack论文。图1显示了不同算法的中心点误差的变化曲线图。实验同样测试了三种算法平均每秒的视频传输量 (FPS) , 其中PFFS最快为每秒32帧, MILTrack为每秒19帧, OAB为每秒26帧。
实验分析了不同环境对三种算法影响, 其中包括目标物本身的尺度, 姿态, 旋转变化, 存在相似物遮挡以及光照等环境因素。图2展示了不同的背景环境下, 三种算法的实验跟踪对比图。图2 (a) 为经典的david视频序列, 视频序列存在多尺度以及光照变化。第180帧时, 图像背景尺度突然缩小, OAB算法跟踪发生严重漂移。345帧时场景光照突然发生变化, MILTrack跟踪目标也产生了漂移。图2 (b) 为tiger1序列, 此序列由于目标物尺度经常发生旋转, MILTrack和OAB算法都很难准确跟踪, 198帧之后两者丢失了目标。图2 (c) 与图2 (d) 分别为cliffbar与faceocc2序列, 视频序列分别测试了存在目标相似物以及遮挡情况下, 不同的实验结果。通过不同帧目标物的跟踪对比, 可以看到cliffbar序列230帧以及faceocc2序列492帧及720帧MILTrack与OAB均存在均存在漂移情况, 本文提出的算法相对比较稳定。
5 结束语
文中提出了一种新型的基于在线判别特征选取的粒子滤波跟踪算法。通过改进的多实例的学习模型构建更新模型分别采样正负样本集合, 并使用在线特征选取过程来构建强分类器。在新的一帧中, 基于不同子运动模型的粒子滤波生成了不同权值与运动趋势的粒子, 强分类器用于求取每个粒子的响应值, 最后完成整个视频的跟踪过程。实验结果显示, 本文提出的算法在光照变化、目标物发生部分遮挡以及目标物自身形变和姿态发生变化时, 都具有很好的跟踪精度与非常高的实时性。
参考文献
[1]Ross D, Lim J, Lin R-S, et al.Incremental learning for robust visual tracking[J].Int.J.Comput.Vis., 2008, 77 (1) :125-141.
[2]Kalal Z, Matas J, Mikolajczyk K.P-N learning:bootstrapping binary classifier by structural constraints[C]∥Proc.IEEE Conf.Comput.Vis.Pattern Recognit., 2010:45-56.
[3]Collins R, Liu Y, Leordeanu M.Online selection of discriminative tracking features[J].IEEE Trans.Pattern Anal.Mach.Intell., 2005, 27 (10) :1631-1643.
[4]Avidan S.Ensemble tracking[J].IEEE Trans.Pattern Anal.Mach.Intell., 2007, 29 (2) :261-271.
[5]Grabner H, Grabner M, Bischof H.Real-time tracking via on-line boosting[C]∥BMVC, 2006:47-56.
[6]Babenko B, Yang M-H, Belongie S.Robust object tracking with online multiple instance learning[J].IEEE Trans.Pattern Anal.Mach.Intell., 2011, 33 (8) :1619-1632.
[7]Isard M, Blake A.CONDENSATION-Conditional Density Propagation for Visual Tracking[J].Int.Journal of Computer Vision, 1998, 29 (1) :5-28.
特征粒子 第2篇
序列图像运动目标跟踪在安全监控[1]、人机交互接口[2]、基于内容的图像处理[3]以及军事等领域有着广泛的应用,是计算机视觉重要研究内容之一。近年来,基于概率的跟踪方法受到广泛的关注,粒子滤波[4]由于其良好的特性而被成功应用到许多算法中[5,6,7]。
粒子滤波为跟踪算法提供了一个统一的框架,算法的效果往往与所选取的特征密切相关。颜色是目标的重要特征之一,文献[8]用颜色直方图来描述目标,将其与Mean Shift算法相结合,取得了良好的跟踪效果,但由于Mean Shift算法采用梯度上升法寻找最优点,所以容易陷入局部极小值。文献[6]在粒子滤波的框架下实现了基于颜色特征的目标跟踪,并自适应更新颜色直方图,跟踪的精度和鲁棒性更好。颜色直方图计算简单,便于实现,但由于没有考虑像素的空间信息,所以在背景有相似颜色情形下容易导致跟踪失败。梯度同样是目标的重要信息,文献[5]利用轮廓来描述目标,跟踪的精度很高,但需要预先知道目标的轮廓模板,不利于算法的实际应用。
方向梯度直方图具有良好的特征表示功能。SIFT[11]就是用方向梯度直方图来描述特征点,最终形成128维的鲁棒性特征描述子。文献[9]中计算每个点的邻域的方向梯度直方图,并将其作为该点的特征用于行人检测,取得了比Harr小波更好的检测效果。方向梯度直方图在某种程度上可以看作是对目标纹理的一种表示,其中带有一定的结构信息,而颜色直方图是对目标的全局描述,而恰恰缺少结构信息,所以本文将二者在粒子滤波框架下相结合,并在跟踪过程中自适应更新颜色和方向梯度直方图,获得了鲁棒的跟踪效果。
2 粒子滤波
粒子滤波是一种基于递归Bayes估计思想的统计模拟方法,它的核心思想是用一些离散随机采样点(粒子)来近似系统随机变量的概率密度函数,以样本均值代替积分运算,从而获得状态最小方差估计。
目标跟踪问题可以看作是对目标状态的估计。假设动态系统可表示为
xk表示k时刻目标状态,yk表示k时刻目标状态的量测,vk、kw为独立同分布的系统状态噪声和观测噪声。假设xk服从一阶Markov过程且量测值之间相互独立,初始状态x0的先验分布为p(x0),设Xk={x 0,x1,,xk},Yk={y 1,y2,,yk},由Bayes公式有
迭代关系式(3)和式(4)构成了最优Bayes解,但其解析解只在有限的模型条件下存在。由于直接从后验概率采样的困难,在k-1时刻,粒子滤波算法从一个容易采样的重要性分布函数q(xk|xk-1,Yk)中采样,独立抽取N个样本,通过(3)和式(4)对粒子进行位置和权值更新,得到k时刻状态的后验概率密度:
权值计算公式为
3 颜色直方图与方向梯度直方图
3.1 颜色直方图
首先根据量化级数将不同颜色通道的像素值加以量化,然后根据量化系数确定每个像素的量化级,从而建立颜色直方图。基于颜色直方图的目标表示方法对目标形变、旋转以及部分遮挡有较强的鲁棒性。通常,为增加直方图描述的鲁棒性,加入表示空间信息的核函数计算加权直方图,使离目标中心近的像素具有较高权值,而离目标中心远的因其可靠性降低,分配较小的权值。本文在RGB空间计算颜色直方图,每个通道量化级为8,那么总的量化级数为8×8×8,以y0为中心的目标区域归一化直方图为
其中:b(xi)为xi处像素点对应直方图的索引值,δ为Kronecker delta函数,xi为各像素点位置,h为跟踪窗尺度(包括长度和宽度),C为归一化常数。
3.2 方向梯度直方图
本文中不计算每个点的方向梯度直方图,而是对目标区域计算一个方向梯度直方图,用来描述该区域的特征。方向梯度直方图的计算方法为:首先计算目标所在区域每个像素点的梯度幅值和方向,然后对这些点的梯度幅值进行加权,离中心点越远的加权值越小,最后统计每个方向上的梯度幅值,形成方向梯度直方图。具体过程如图1所示,其中最左边图中黑色箭头表示梯度幅值和方向,蓝色圆圈表示按离中心点距离进行幅值加权,中间图表示统计后在8个方向上梯度幅值,最右边图表示方向梯度直方图。
本文将0~360°量化为20级,即每18°一个间隔,采用与颜色直方图相同的核函数加权,梯度幅值和方向计算公式为
3.3 距离度量
通常采用Bhattacharyya系数[10]来描述两个分布p(u)和q(u)之间的相似性:
归一化直方图可看作是对特征的离散概率描述,那么两个直方图p={pu}u=,1,m和q={qu}u=,1,m之间的相似性可表示为
Bhattacharyya距离为
4 基于特征融合的粒子滤波跟踪算法
本文通过矩形框来定位目标,因此状态参数应包括矩形的中心点位置x,y和矩形宽度cx和高度cy,状态变量X=(x,y,cx,cy)。采用布朗运动模型,即
∑k-1为系统状态噪声,我们假定其为对角阵,数值根据具体实验确定。
每个粒子通过状态方程进行传递后,必须根据粒子的似然性来确定权重。由于我们采用了两个直方图,所以每个粒子会得到两个Bhattacharyya距离dcolor和dgrad,粒子的权重通过下式得到:
其中:σc和σg分别为颜色直方图和方向梯度直方图对应的噪声方差,α和β用来调整二者加权值。
为了适应目标本身的形变以及光照等外部因素的影响,本文算法在跟踪过程中自适应更新颜色直方图和方向梯度直方图。假设当前模板为q,当前估计位置的直方图为p,那么当它们之间的Bhattacharyya距离小于一定阈值T时,才对模板q进行更新,否则认为受外部点影响较大,不予更新。更新方法如下:
多特征融合的粒子滤波跟踪算法具体步骤如下:
1)手动获取目标在第一帧中的位置,设定目标初始状态变量X、噪声Σ以及α、β、σc、σg、T、η,获取颜色直方图和方向梯度直方图,初始化粒子;
2)读入下一帧,将上一时刻粒子通过式(13)传递,得到当前时刻粒子si,i=1…N;
3)根据式(14)计算粒子权重wi,i=1…N;
4)计算当前估计值:X∧=∑ni=1w isi;
5)自适应更新颜色直方图和方向梯度直方图;
6)重采样粒子,返回步骤2)。
5 实验与分析
本文测试数据来自http://homepages.inf.ed.ac.uk/rbf/CAVIAR/。第一个序列中,我们的跟踪目标与背景有相近的颜色,而且运动过程中受到光照变化的影响,测试结果如图2所示。参数设置为α=0.1,β=0.9,σc=0.02,σg=0.006,η=0.05,颜色直方图和方向梯度直方图的更新阈值分别为0.1和0.2,粒子数目为100。为便于对比,图3为相应帧基于颜色的粒子滤波的跟踪结果。从图中可以看出,单纯基于颜色的粒子滤波跟踪方法容易受到背景干扰,从301帧开始有较大偏差,最后丢失目标。该实验中,目标的方向梯度直方图变化不大,而且与背景差异较大,所以融合梯度信息后,本文算法始终较好的跟踪目标。
第二个实验我们测试本文算法在目标受遮挡情形下的跟踪性能,参数设置为α=0.7,β=0.3,其余与实验一相同,测试结果如图4所示。在目标发生遮挡时,由于与遮挡物在结构上的相似,方向梯度直方图会受到较大影响,所以此时颜色直方图的权重α较大。从图中可以看出,虽然在遮挡时跟踪精度下降,但由于采用了合适的自适应更新策略,遮挡结束后能恢复正确的跟踪,具有较强的鲁棒性。
从以上两个实验可以发现,颜色特征和梯度特征在很多情况下是互为补充的,在目标颜色特征与背景相差较大时以颜色特征为主,在梯度特征明显时以梯度特征为主,所以算法能适应较复杂情形下的跟踪,但如果两种特征都与背景相差不大,则可能会导致跟踪失败。
6 结论
本文提出了一种基于粒子滤波的运动目标跟踪算法,通过将颜色特征和梯度特征相融合,并自适应更新这些特征,来实现复杂背景下目标的跟踪。实验结果表明,该算法优于基于颜色的粒子滤波算法,并能在干扰较强时正确跟踪目标,具有很强的鲁棒性。本文算法的参数是通过实验确定,而且没有更新,如何自适应改变这些参数需作进一步的研究。
摘要：针对单纯的基于颜色的跟踪方法在复杂背景下会导致跟踪失败的问题,本文提出一种基于粒子滤波的特征融合跟踪算法。颜色直方图是对目标的全局描述,而方向梯度直方图包含了一定的结构信息,二者可以互为补充,因此本文算法同时用颜色直方图和方向梯度直方图来描述目标,在粒子滤波框架下将目标颜色和梯度信息有机结合,并自适应更新。实验表明,本文算法不仅提高了跟踪精度,而且具有较强的鲁棒性。
关键词：跟踪算法,粒子滤波,颜色直方图,方向梯度直方图,特征融合
参考文献
[1]Beymer D,McLauchlan P,Coifman B,et al.A Real-time Computer Vision System for Measuring Traffic Parameters[C]//Computer Vision and Pattern Recognition.San Juan,IEEE Computer Society,1997:495–501.
[2]Black M,Jepson A.A Probabilistic Framework for Matching Temporal Trajectories:Condensation-Based Recognition of Gestures and Expressions[C]//European Conference on Computer Vision.Frieburg:Springer,1998:909–924.
[3]Menser B,Brunig M.Face Detection and Tracking for Video Coding Applications[C]//Asilomar Conference on Signals,Systems,and Computers.Pacific Grove:IEEE,2000:49–53.
[4]Gordon N J,Salmond D J,Smith A F M.Novel approach to nonlinear/non-Gaussian Bayesian state estimation[J].IEE Proc.Radar and Signal Processing,1993,140(2):107-113.
[5]Isard M,Blake A.Condensation-conditional density propagation for visual tracking[J].International Journal of Computer Vision,1998,29(1):5-28.
[6]Nummiaro K,Koller-Meier E,Van Gool L.An Adaptive Color-Based Particle Filter[J].Journal of Image and Vision Computing,2003,21(1):99-110.
[7]Perez P,Hue C,Vermaak J,et al.Color-Based Probabilistic Tracking[C]//ECCV.Copenhagen:Springer,2002:661-675.
[8]Comaniciu D,Ramesh V,Meer P.Real-Time Tracking of Non-Rigid Objects using Mean Shift[C]//Computer Vision and Pattern Recognition.Hilton Head Island:IEEE Computer Society,2000:142-149.
[9]Dalal N,Triggs B.Histogrames of Oriented Gradients for Human Detection[C]//Computer Vision and Pattern Recognition.San Diego:IEEE Computer Society,2005:886-893.
[10]Thacker N,Aherne F,Rockett P.The Bhattacharyya Metric as an Absolute Similarity Measure for Frequency Coded Data[J].Kybernetika,1997,34(4):363-368.
特征粒子 第3篇
关键词：粒子系统,火焰模拟,LOD,视觉重要度
0 引言
在高质量图形的实时生成要求下，如何从软件方面着手减少图形画面的复杂度，已成为VR图形生成的主要目标。研究人员提出多种图形生成加速方法，细节层次（Levers of Detail, LOD）模型就是其中一种主要方法。传统几何建模中，一般的LOD技术的原理是根据物体距离视点的远近来决定所建模型的顶点数目[2]。对于粒子系统，我们可以结合LOD技术，进行物体模拟，即当视点较近时，每次产生较多的粒子，视点较远时，则可以产生较少的粒子，从而对粒子模拟进行简化，减少系统计算量，提高绘制效率。丁强等人提出的基于LOD技术的火焰模拟[3]，能够在减少计算量的基础上，对火焰进行较好地模拟，但是，简化后的图像并没有根据视觉特征效果对粒子系统进行精简，据此，本文基于火焰几何模型中粒子的视觉重要度，对该技术进行了改进，在模拟火焰燃烧方面，能够达到更好的效果。
1 粒子系统属性设置
1.1 初始属性设置
对粒子属性的初始化设置一般可以通过简化的随机过程来控制[4]，对于每一个属性首先确定其变化范围，然后在该范围内随机地确定它的值，随机性效果可以通过具有一定的概率分布随机函数来产生，进而影响粒子系统的整体外观轮廓，属性的变化范围则由给定的平均期望值和最大方差来确定，其基本表达式为：
(1）式中Value为任意一个需要随机确定的粒子属性值；MeanVlaue为该属性的平均值；Rand（）为[-1, 1]中的随机数函数；VarValue为方差，即属性在平均值附近的变化范围。在火焰粒子系统中初始的位置、初始的运动速度、受力都可以由式（1）式来直接生成。
1.2 属性变化
粒子的属性变化构成了粒子的运动变化，对于透明度和颜色、生命值、粒子大小等属性，通过式（2）[5]进行控制：
式中，ValueStart为粒子系统该属性的初始值，ValueEnd为此粒子终止时的属性值，LifeTime为粒子的寿命值，TimeDelta则为此帧与上一帧的时间跨度值。某一帧粒子的位置可以由其速度和上一帧的位置得到。
(3） (4）式中P为位置，V为速度，A为加速度。计算粒子系统的总体受力算法[6]如下：
I：计算当前粒子各个方向受力情况；
II：根据受力求出加速度；
III：利用（3） (4）式求出速度与位置的改变。
2 粒子系统更新
2.1 新生粒子数量
在粒子生成步骤中，结合LOD（层次细节）模型，对粒子系统产生新粒子的数目值设置为：
上式中，N0表示没有进行简化的原始几何模型的顶点数，Nm表示第m级简化模型的顶点数。粒子系统中，在距离Lm产生的粒子数均值作为Nm。即当视点较近时，每次产生较多的粒子，视点较远时，则产生数量线性较少的粒子，这样就降低了很多计算机处理的时间，提高了系统的绘制效率。
2.2 视觉平坦点剔除
上述方法实现了计算量的降低，但是，并没有对粒子的视觉重要程度进行判断，只是线性地根据距离减少粒子的生成数量。顶点视觉重要度决定了顶点的凹凸几何特性，在三维场景渲染中，凹凸性高的点更多能够决定场景的真实度[7]。
顶点的视觉重要度的确定由顶点视觉特征因子和顶点曲度特征因子共同决定[8]，根据法曲率可以计算顶点曲度特征因子，法曲率反映了曲面在一点处沿指定方向的弯曲程度和弯曲方向，可以对曲面在一点处沿任意方向的弯曲性量化。高斯曲率和平均曲率共同确定法曲率，进而确定了顶点曲度特征因子。
通过对顶点视觉重要度的计算，在粒子系统更新时可根据视觉重要度为零的点进行剔除，可以使顶点的重要视觉特征得以最大保持，并最大程度地降低系统的渲染时间。即在粒子系统中首次渲染场景时，对粒子进行扫描并记录每个粒子的视觉重要程度，在后续的更新粒子过程中，对记录中平坦点位置的粒子不进行渲染，以减少渲染量。
3 火焰模拟的效果分析
利用OpenGL图形开发库，在VC++6.0环境下，对火焰粒子系统进行模拟，并将粒子的LOD简化策略及平坦点剔除加入了火焰粒子系统的实现。系统中采用的帧率为32，即每帧所用渲染时间为0.03125s，设置初始L0=50, N0=10；采用线性LOD简化模型。
由实验数据可知，引入平坦点剔除后，为达到相同的视觉效果，系统产生新粒子数量减少约20%-25%左右，即在引用LOD技术进行线性降低粒子发射量的基础上，结合考虑粒子系统中每个粒子的视觉重要程度，对视觉凹凸性低的点予以剔除，能够在保持视觉效果的基础上，给系统减少计算负担，提高渲染效率。
参考文献
[1]Revees W T.Particle Systems:A Technique for Modeling a Class of Fuzzy Objects[C]∥Proc of ACM SIGGRAPH’83, 1983, 17 (3) :359-376.
[2]郭阳明, 翟正军, 陆艳红.虚拟场景生成中的LOD技术综述[J].计算机仿真, 2005, 12 (22) :180-185.
[3]丁强, 陈青林, 左福强.基于LOD的火焰粒子生成技术[J].计算机应用, 2005 (25) :257-258.
[4]彭群生, 鲍虎军, 金小刚.计算机真实感图形的算法基础[M].北京:科学出版社, 2003.
[5]陈志伟, 马小虎.基于粒子系统和纹理绘制的火焰模拟[J].计算机工程与科学.2010, 1 (32) :71-73.
[6]DANIEL SANCHEZ2CRESPO DALMAU.游戏核心算法编程内幕[M].邱仲潘, 译.北京:中国环境科学出版社, 2004.
特征粒子 第4篇
视频目标跟踪[1]是计算机视觉领域的前沿方向之一, 它在国防制导、智能安保、视觉导航、医学诊断等许多领域有着广泛的应用前景。在视频跟踪过程中, 一个亟待解决的难点就是如何准确地描述目标特征并适应目标形态或背景的变化。因此, 寻找一种稳健、实时性和鲁棒性较高的算法已成为目标跟踪的研究重点。
粒子滤波[2]利用离散的带权粒子集合来近似表示待求解问题概率密度函数的数值, 对环境的适应能力很强, 不仅解决了传统高斯背景模型、卡尔曼滤波等方法无法解决的非高斯非线性问题, 而且提高了跟踪的精度, 具有简单实用的特点。针对粒子滤波因计算量较大存在实时性问题, 将均值偏移嵌入到粒子滤波算法框架[3], 在系统的动态模型产生粒子之后, 利用均值偏移算法[4]进行粒子聚类, 提高了粒子的利用率, 减少粒子数量同样达到实时准确跟踪的良好效果。多目标特征的融合描述能够极大地提高目标跟踪的效果, 常用的目标特征是颜色信息和方向梯度信息, 两者相互补足, 有效地解决单一颜色特征易受类似颜色的干扰而导致跟踪失败的问题, 提高算法的鲁棒性。
基于以上分析, 本文提出了融合颜色特征和方向梯度特征的均值偏移粒子滤波自适应跟踪算法, 并对颜色特征模型、方向梯度特征模型和特征融合方法进行改进。实验结果表明, 该方法可鲁棒地跟踪到遮挡、形态变化或背景变化的目标。
1 基于均值偏移粒子滤波算法的目标跟踪
1.1 均值偏移粒子滤波算法
提出的算法在粒子滤波算法基本步骤、粒子状态转移、粒子权值更新等过程之间, 加入了均值偏移算法对粒子进行聚类, 提高粒子的利用率。均值偏移粒子滤波算法如图1所示。
(1) 粒子采样
已知初始位置为x0, 取粒子数为N, 其权值初始值为1/N, 所有粒子的权值之和为1, 每个粒子代表目标的一个可能的运动状态。
初始目标模型方框中第一帧包含像素用{xi}, i=1, 2, …, n表示, 特征值bin的个数为m个。目标模型的特征值u=1, 2, …, m的初始目标模型表示为:
式中, δ (x) 是Delta函数, δ[b (xi) -u]的作用是判断像素{xi}是不是属于第u个bin, 若属于, 则函数值为1, 否则为0。
(2) 粒子状态转移
系统动态模型通过粒子的传播来表示目标状态的更新过程, 而粒子传播是一种随机运动过程, 可采用下列一阶或二阶ARP方程:
(3) 粒子均值偏移收敛
粒子预测方程为:
式中, xit+1表示t时刻第i粒子xit+1在t+1时刻最可能出现的位置。
均值偏移是一个自适应搜索峰值的过程, 通过均值偏移搜索可以得到各个粒子的局部最大值[5], 使粒子在传播半径的领域内收敛到一个稳定点。在迭代过程中, 每次从y0迭代至一个新的位置y1为:
式中, g (x) =-k' (x) , 均值偏移对每个粒子迭代一次, 得到一组Bhattacharyya系数 (巴氏系数) , 分别与观测过程中的巴氏系数比较, 如果大于它, 就将粒子转到均值位置。
(4) 粒子权值更新
从第二帧开始, 由于核函数窗口宽h可能会改变 (比如物体的形变) , 之后的每一帧中可能包含的像素用{xi}, i=1, 2, …, nh表示, 所以在中心点yi处的候选目标模型表示为:
其中, j=1, 2, …, N。
相似性函数描述目标模型与候选模型的相似度, 本文使用最优相似性函数巴氏系数表示, 其定义为:
则巴氏距离为:
计算出观察值的概率密度函数[6]为:
(5) 计算目标位置
利用加权准则求所有粒子的加权均值作为最终目标位置, 表示为:
(6) 重采样
判断粒子退化情况, 根据有效粒子数的值判断是否进行粒子重采样, 如果Neff
融合Mean Shift的粒子滤波算法比经典粒子滤波算法多了一个Mean Shift迭代阶段, 由于Mean Shift[7]的收敛性, 使粒子迭代后更接近于目标实际位置, 粒子的有效性大大加强, 通过减少粒子数量同样能很好地估计粒子的系统状态。
1.2 特征描述
(1) 颜色特征描述
本文选择8byte×8byte×8byte的HSV空间颜色加权直方图作为目标的颜色模型, 提取图像模型中的H分量, 构造带有核函数的颜色分布直方图为:
均值偏移跟踪算法的核窗宽一般取固定值, 对于形变物体无法自适应, 目标变大变小引起跟踪窗口不能完整地描述目标信息或混入许多背景信息, 导致目标跟踪失败。因此, 自动更新跟踪窗的大小是改进跟踪算法的关键。
传统尺度自适应增减法通常采用三个不同的核窗宽进行迭代, ±10%的增量调整内核窗口大小的方法虽然简单易行, 但是在目标尺度不断增大甚至超出带宽范围的情况下, 容易导致空间定位出现偏差。在此基础上, 本文对均值偏移跟踪算法的HSV颜色候选模型[8]进行改进, 构造带有核函数的颜色分布直方图为:
式中, ε是一个预定的阈值, 用来剔除目标跟踪框内概率低的像素, 采用统计方法计算得归一化系数为:
算法中相应的权重系数为:
候选区域以改进的候选模型进行建模, 跟踪窗口以原核窗宽增减10%进行调整后进行均值偏移迭代, 计算目标位置, 最后取经过三次收敛后巴氏系数较大的核窗宽作为新的核窗宽。
(2) 方向梯度特征描述
遮挡或光照不稳定情况下, 基于单一颜色特征的粒子滤波算法不能很好的解决遮挡、相似颜色干扰的情况。方向梯度模型[9]对于光线的变化和局部形变具有较强的鲁棒性, 并能反映一定的空间结构信息, 所以选用梯度信息对颜色信息进行补充。
首先利用梯度算子[-101]T和[-101]T与人体目标区域逐帧做卷积, 得到像素点I (x, y) 的梯度幅值G (x, y) 和梯度方向θ (x, y) 为:
将方向角0°~360°等分为m个区间, 人体目标梯度概率分布表示为:
式中, u=1, 2, …, m, Cgrad为归一化系数, k (x) 为核函数。根据金字塔加速算法原理, 本文对区域划分单位以级数级递减的方式, 即80°、40°、20°和10°进行实验运算, 实验表明使用m=18, 即以20°为单位将区域划分时, 在保证跟踪精度的前提下, 实时性得到了大幅提高。
(3) 颜色和方向梯度的特征融合
传统目标的多特征融合通常使用乘性融合或加权融合[10]的方法, 乘性融合可能对噪声进行放大, 基于置信比重调整权值系数的加性融合, 对噪声不敏感, 但不能提高跟踪的可信度。
本文分别建立目标特征的子模型, 以降低特征维数, 从而大大减少了运算量。同时, 按照每个子模型观测准确度高低赋予相应权值。最后将颜色特征和方向梯度特征子模型之间相似度通过加权求和获得总相似度。
设目标与模板之间第i个特征的相似度为ρ, 将其归一化得到各个特征的权值为:
则总相似度为:
1.3 跟踪算法流程
基于改进的颜色及方向梯度融合的Mean Shift粒子滤波跟踪算法流程为:
步骤1粒子初始化初始化颜色粒子和方向梯度粒子, 提取目标的颜色和方向梯度特征, 建立目标颜色直方图和方向梯度直方图。
步骤2目标状态预测在正常情况下和遮挡情况下分别利用系统动态模型的计算式 (2) 和式 (3) 预测当前帧的目标位置。
步骤3利用式 (4) 均值偏移聚类粒子。
步骤4粒子权值更新分别利用颜色特征和方向梯度特征的相似性度量计算目标与候选模型巴氏距离, 然后利用式 (9) 更新各自粒子权值。
步骤5目标定位利用式 (10) 分别对各特征粒子做加权平均, 得到颜色特征和方向梯度特征各自的跟踪结果。
步骤6目标特征融合以巴氏系数表示的颜色和方向梯度之间相似度通过式 (18) 和式 (19) 加权求和获得总相似度, 得到最终结果。
步骤7目标遮挡的处理目标在严重遮挡或目标丢失后再次寻找目标时, 采用巴氏系数ρ (y) 来衡量目标的遮挡和丢失程度[11]。当0.2≤ρ (y) <0.4时, 判定目标被短时间遮挡;当ρ (y) <0.2时, 判定目标被长时间遮挡或者丢失。
目标被短时间遮挡时, 直接用系统动态模型式 (2) 和式 (3) 产生的粒子集更新目标的状态;目标被长时间遮挡或者丢失时, 启用搜索策略[11]重新找回目标, 直到目标摆脱遮挡为止。
步骤8重采样如果Neff
2 仿真实验
本文算法在Intel Core Duo i7-2.3GHZ CPU、4GB DDR3内存的PC机上用Visual C++6.0和Open CV 1.0编程实现的, 采用两段长为210帧、106帧, 分辨率为640×480的行人测试视频为实验对象进行验证。
实验1图2和图3所示为在人体跟踪目标遮挡场景下, 文献[2]传统粒子滤波算法和本文研究算法的跟踪比较结果。图2显示了采用传统粒子滤波算法的跟踪效果, 在第20帧人体被大树遮挡时, 部分粒子分布到了树的周围, 模板吸收了错误信息, 跟踪窗口发生偏移;在第33帧人体穿过遮挡物后, 跟踪窗口失效。图3显示了采用本文研究的算法的跟踪效果, 在第18帧人体被大树遮挡时, 算法迅速启用遮挡判断方式, 利用系统粒子动态模型或搜索策略重新找回人体目标。两种特征融合的互补作用减弱了场景变化的影响, 均值偏移的聚类作用加强了跟踪的实时性, 仅需要传统粒子滤波算法50%的粒子就能对目标实现精确的跟踪。实验结果表明, 本文提出的算法能更好地处理遮挡问题, 跟踪稳健。
实验2图4和图5所示为在人体运动目标尺度逐渐变化情况下, 文献[4]传统均值偏移算法、本文研究算法的跟踪比较结果。图4显示了传统均值偏移算法的跟踪效果, 在人体尺度逐渐变大或逐渐变小的过程中, 第15帧、第21帧和第34帧, 算法仅能跟踪到局部区域, 有丢失目标的可能性。图5显示了采用带宽自适应策略的均值偏移粒子滤波算法的跟踪效果, 从第3帧到第36帧, 在人体尺度明显增大或者逐步缩小的过程中, 算法都能根据目标宽高自动对窗口大小进行增减, 将人体目标锁定在矩形框内。实验结果表明, 本文提出的算法能准确地跟踪尺度变化目标。
3 结语
本文提出一种融合颜色特征和梯度方向特征的均值偏移粒子滤波自适应跟踪算法, 能够很好地解决动态背景下目标的非线性运动问题, 同时加入了相应的遮挡策略, 能够解决短时遮挡问题。算法的优点是简单实用, 具有较好的准确性、鲁棒性与实时性, 缺点是对检测到的人体行为只是进行简单的跟踪和提取, 对于多目标快速运动和严重遮挡问题适应能力差。因此, 基于复杂环境下多摄像机多运动目标的跟踪以及多特征的融合将作为下一步的研究重点。
参考文献
[1]周敬兵.复杂背景下的目标检测与跟踪技术研究[D].南京:南京理工大学, 2007.
[2]Nummiaro K, Koller M E, Gool L V.An adaptivecolor-based particle filter[J].Image and Vision Computing, 2003, 21 (1) :99-110.
[3]Shan C, Wei Y, Tan T, et al.Real time hand tracking by combining particle filtering and mean shift[C]//Proceedings of the 6th IEEE International Conference on Automatic Face and Gesture Recognition, 2004:669-674.
[4]Cheng Y.Mean shift, mode seeking, and clustering[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 1995, 17 (8) :790-799.
[5]Comaniciu D, Ramesh V, Meet P.Kernel-based object tracking[J].IEEE Trans on Patten Analysis and Machine intelligence, 2003, 25 (5) :564-575.
[6]朱胜利.Mean Shift及相关算法在视频跟踪中的研究[D].杭州:浙江大学, 2006.
[7]Yizong Cheng.Mean Shift mode Seeking and Clustering[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 1995, 17 (8) 6-10.
[8]朱长锋, 刘玉树.一种新的Mean-Shift对象跟踪方法[J].光电工程, 2008, 35 (3) :26-29.
[9]Dalai N, Triggs B.Histograms of oriented gradients for human detection[C].Computer Society Conference on Computer Vision and Pattern Recognition, 2005:886-893.
[10]陶杰, 毕笃彦.一种基于粒子滤波的特征融合跟踪算法[J].光电工程, 2008, 35 (11) :13-17.
特征粒子 第5篇
运动目标跟踪是指利用目标的显著特征, 比如颜色, 形状, 边缘, 根据一定的匹配算法, 在视频序列中搜索与目标特征最相符的位置。它是计算机视觉中的一个重要而备受关注的研究内容, 能够广泛地应用于智能交通, 视频监控, 人机接口以及人体的行为识别等领域。
现有的大多数跟踪算法都能够被描述为一个使用确定性方法或者随机性方法的最优化过程。确定性方法是使用梯度下降法来搜索代价函数的最小值。比如, mean shift[1]算法, 它最初用来估计概率密度函数的梯度, Comaniciu[2,3]第一次将其引入目标跟踪领域, 利用mean shift的迭代过程, 通过寻找目标颜色直方图与候选目标颜色直方图之间Bhattacharyya距离的极小值来跟踪定位目标。一般来说, 确定性方法计算复杂度小, 但是它搜索到的极值很有可能只是局部极值而不是全局极值。与确定性方法相比, 随机性方法更具有鲁棒性但是计算复杂度较高。粒子滤波算法[4]是随机性方法中的典型代表, 它是用一系列带有权值的随机粒子来估计目标状态的后验概率密度, 其中每一个粒子表示对目标状态的一种假设, 粒子的权值表示粒子的状态是目标真实状态的概率。目标状态的最优估计表示为所有粒子状态的加权平均。
选择哪种特征对目标进行描述决定着跟踪的成败。传统的粒子滤波器以目标的颜色直方图作为特征。颜色直方图是应用最广泛的特征, 它具有提取简单和旋转不变形性, 并且对局部遮挡不敏感等优点。但是颜色特征对光照敏感, 并且当背景中有与目标颜色相似的对象时, 利用颜色特征进行跟踪可能会导致跟踪失败。已经有很多人选择采用更具有独特性的特征[5,6]或者将颜色特征与其他特征结合起来[7,8]对目标进行描述来改善只采用颜色特征带来的缺陷。尺度不变特征变换[9]SIFT是一种提取局部特征的算法, 利用该算法提取的特征点对图像平移、旋转、缩放、甚至仿射变换保持不变性。文献[6]中将目标的SIFT特征用于粒子滤波, SIFT特征独特性强, 能够分辨颜色相近的不同对象, 当背景中有与目标颜色相似的对象时也能成功地对目标进行跟踪。然而, 在目标太小或者目标纹理几乎一致的情况下, 由于不存在足够多的有效特征点, 因此无法利用SIFT特征点描述目标。
本文针对只采用颜色特征和只采用SIFT特征带来的不足, 将目标的颜色特征和SIFT特征结合起来对目标进行描述。让两种特征相互补充来弥补彼此的不足。这样粒子的权值就由两种特征共同确定, 即利用目标模型和候选区域中SIFT特征点的匹配数目以及相应的颜色直方图之间的Bhattacharyya距离对粒子的权值进行更新。
目标在跟踪过程中由于自身运动及外界环境的影响, 其特征也在不断的变化, 所以要对目标模板进行更新。在传统的粒子滤波跟踪算法中, 当跟踪结果的颜色直方图与目标模板之间的相似度大于一定的阈值时, 表示跟踪结果较可靠, 可以用跟踪结果的颜色直方图对目标模板进行更新[10]。然而, 当算法跟踪到背景中与目标颜色相近的对象或者目标被颜色相似的对象所遮挡时, 两者之间的相似度也有可能大于阈值, 这时用错误对象的颜色直方图对目标模板进行更新, 就会造成目标模板与真实目标之间出现偏差, 最终造成跟踪的失败。因为SIFT特征具有很高的独特性, 能够区别颜色相近的不同对象, 所以SIFT特征比颜色特征更可靠。本文提出的模板更新算法将跟踪结果中提取的SIFT特征点与SIFT目标模板中的特征点进行匹配。当匹配点的数目大于前几帧匹配数目的平均值时, 说明跟踪结果较可靠, 此时用跟踪结果的颜色直方图对颜色目标模板进行更新, 否则不更新颜色目标模板。
1 基于颜色的粒子滤波算法
粒子滤波器的核心思想是:在给定直到k时刻的所有观测值Z1∶k={Z1, Z2, …, Zk}的情况下, 用一组带有权值的粒子{Xik, wik}Ni=1估计k时刻目标状态Xk的后验概率密度, 这里N表示粒子的数目。每一个粒子Xik代表了目标状态的一个假设, 相应的粒子权值wik表示粒子状态是目标真实状态的概率。用粒子滤波算法对目标进行跟踪需要设计好两个模型:系统转移模型和系统观测模型。
1.1 系统转移模型
系统转移模型描述了目标的状态随时间的转移过程, 所以系统转移模型也描述了粒子状态的传播过程。粒子的状态可以用一个矩形来表示, 即:
其中, xki、yki表示矩形中心的位置, wki、hki表示矩形的宽和高。这样, 每一个粒子就可以确定一个目标的候选区域。
我们这里选择二阶自回归模型作为系统转移模型。即:
其中, wt-1是t-1时刻的系统噪声, 它是服从高斯分布的随机向量, 而B是一个常量。由式 (2) 可以看出:在假设当前帧目标状态的转移速度与前一帧相同时, 目标状态的转移过程实际可以看成一个受随机加速扰动的直线运动。
目标的初始化以人机交互方式进行, 用一个矩形框包含跟踪目标, 矩形的中心以及矩形的长和宽即为目标的初始状态。同时将N个粒子的初始状态设置为与目标的初始状态相一致, 而粒子的权值设置为1/N。
1.2 系统观测模型
系统观测模型用来更新粒子的权值。粒子的权值表示粒子所代表的状态是目标真实状态的可能性。所以, 利用系统观测模型对接近目标真实状态的粒子赋予较大的权值, 反之则赋予较小的权值。
Nummiaro等在文献[10]中率先使用了颜色直方图之间的Bhattacharyya距离作为系统观测模型, 颜色特征提取简单, 对旋转和部分遮挡具有鲁棒性。在背景简单的情况下, 很适合对目标进行描述。
在初始帧, 设目标的中心为x0, {xi}ni=1表示目标区域中像素的位置, 则目标区域的颜色直方图中第u个颜色区间的值 (u=1, 2, …, m) 为:
目标区域的颜色直方图构成了初始时刻的颜色目标模板。
在第k帧中。每一个粒子可以确定一个候选区域, 同样计算每个粒子候选区域中的颜色直方图。用yi表示第i个粒子候选区域的中心, 表示位于这个候选区域的所有像素的位置, 则第i个粒子候选区域的颜色直方图中第u个颜色区间的值为:
使用Bhattacharyya系数作为相似性函数, 计算第i个粒子对应的颜色直方图与颜色目标模板的相似度:
ρ越大, 两个直方图越相似。对于两个相同的颜色直方图, ρ=1。定义Bhattacharyya距离如式 (6) 所示, 两个直方图越相似, Bhattacharyya距离越小。
利用颜色目标模板与粒子候选区域的颜色直方图之Bhattacharyya距离作为系统观测模型, 定义为:
这样, k时刻第i个粒子的权值更新为:
k时刻系统的状态可以估计为:
2 基于SIFT特征和模板更新的粒子滤波算法
SIFT特征对图像平移、旋转、缩放, 甚至仿射变换保持不变性。在高斯差分尺度空间中寻找图像域和尺度域上的极值点, 从而保证特征点对缩放和平移具有不变性。利用特征点周围邻域内像素的梯度直方图为每个特征点分配一个主方向, 从而保证特征点对旋转具有不变性。将图像的坐标轴旋转为特征点的主方向后, 利用特征点邻域内像素的梯度为每一个特征点建立一个128维的描述子, 这样每一个特征点就可以用一个128维的特征向量来表示。
当背景中有与目标颜色相近的对象时, 仅利用颜色特征不足以对目标进行描述。SIFT特征具有很高的独特性, 能够将目标与其他颜色相近的对象分开, 并且SIFT特征对亮度, 尺度和旋转具有不变性, 将SIFT特征融入到基于颜色的粒子滤波中, 可以使两种特征相互补充, 使算法更具有鲁棒性。
2.1 粒子权值修正
在基于SIFT特征和模版更新的粒子滤波算法中, 粒子的权值由颜色特征和SIFT特征共同决定。基于颜色特征的粒子权值由式 (8) 计算, 下面仅介绍基于SIFT特征的权值计算方法。
在初始帧, 用矩形框包含要跟踪的目标之后, 提取矩形框中目标的SIFT特征。假设目标包含m个SIFT特征, 则这些特征就构成了SIFT目标模板T, 即T={fi}mi=1, 其中fi表示一个SIFT特征点的特征向量。
在任意时刻k, 每一个粒子能够确定一个候选区域, 同样提取每一个粒子候选区域中的SIFT特征。Tki表示k时刻第i个粒子候选区域中的SIFT特征向量集合。将每个粒子候选区域中的特征向量与SIFT目标模板中的特征向量进行匹配。匹配的特征向量数目越多, 粒子越有可能是真实目标。所以利用SIFT目标模板与候选区域中特征向量的匹配数目来描述粒子状态与真实状态之间的相似程度, 由此定义系统观测模型为:
其中, fj∈T, match (fj) 是与fj相匹配的特征向量。M (match (fj) ) 函数的定义如式 (11) 所示, 表示与fj相匹配的特征向量是否位于k时刻第i个粒子候选区域的SIFT特征向量集合中。
由于目标存在形变或者目标可能被遮挡, 在任意时刻k, SIFT目标模板中的特征向量在当前帧中不都存在相匹配的特征向量, 所以SIFT目标模板中特征向量的重要性是不同的。在整个视频序列中, 匹配次数较多的特征向量更稳定, 其重要性必然要比匹配次数较少的特征向量高。所以为SIFT模板中的每一个特征向量引入一个权值, 权值的大小表示特征向量重要性的高低, 即表示存在匹配特征向量次数的多少。
要判断第k帧中是否存在与fj相匹配的特征向量, 理论上是在整个第k帧图像上提取特征向量进行匹配。但实际上这样会使算法的计算复杂度大大提高。这里假设目标的状态是连续变化的, 即所有粒子候选区域的并集包含了目标的真实区域。所以, 我们可以只在所有粒子的候选区域中提取特征向量, 然后判断其中是否存在与fj相匹配的特征向量。令特征向量权值的初始值为1。k时刻, 特征点fj的权值定义为:
其中, β是一个0到1之间的数。目标变化快时, β取较大的值。当目标变化慢时, β取较小的值。Mjk的定义如式 (13) 所示, 表示第k帧中是否存在与fj相匹配的特征向量。
跟踪过程更依赖于权值较大的特征点, 为了提高算法的鲁棒性, 将特征点的权值融合到系统的观测模型中, 将观测模型重新定义为:
基于SIFT特征的粒子权值为:
粒子的最终权值由基于颜色的权值和基于SIFT特征的权值共同决定。因此, 粒子的最终权值为:
其中, α为0到1之间的数, 它表示了两种不同特征的权值所占的比重, 根据具体的场景来选择。当场景复杂时, 即场景中存在光照变化, 遮挡以及与目标颜色相似的对象时, 这时颜色特征不可靠, SIFT特征应占主导地位, 此时令α取一个较小的值。当想要跟踪的目标较小且纹理单一时, 目标本身不存在足够多的SIFT特征点, 利用SIFT特征不足以对目标进行描述, 这时颜色特征应该占主导地位, 令α取一个较大的值。
k时刻系统的状态可以估计为:
2.2 目标模板更新
在目标跟踪过程中, 由于目标自身的运动, 视角的变化以及环境条件的改变, 目标的颜色特征和SIFT特征也在不断变化。因此, 需要对颜色目标模板和SIFT目标模板进行即时动态更新, 以适应目标的变化。
在基于颜色的粒子滤波器中, 当跟踪结果的颜色直方图与目标模板之间的相似度大于一定的阈值时, 表示跟踪结果较可靠, 可以将跟踪结果的颜色直方图融入到目标模板中对目标模板进行更新。然而, 算法可能跟踪到背景中与目标颜色相近的对象或者目标被颜色相似的对象所遮挡, 此时的颜色直方图与目标模板之间的相似度也有可能大于阈值, 这时用错误对象的颜色直方图对目标模板进行更新, 就会造成目标模板与真实目标之间出现偏差, 最终造成跟踪的失败。
因为SIFT特征具有很高的独特性, 能够区分颜色相近的不同对象, 所以SIFT特征比颜色特征更可靠。本文提出的模板更新算法不是以颜色直方图之间的相似度作为颜色模板更新的依据, 而是将跟踪结果中的SIFT特征点与SIFT目标模板中的特征点之间的匹配数目作为更新依据。当匹配特征点的数目大于前几帧匹配数目的平均值时, 说明跟踪结果较可靠, 此时用跟踪结果的颜色直方图对颜色目标模板进行更新, 否则不更新颜色目标模板, 仅利用文献[6]中的方法对SIFT目标模板进行更新。
(1) 颜色目标模板的更新
当跟踪位置不准确或者目标被遮挡时, 此时不应该对颜色目标模板进行更新, 以免造成目标模板与真实目标之间的偏差。利用跟踪结果中的特征向量与SIFT目标模板中的特征向量的匹配数目N作为是否进行颜色模板更新的依据。当匹配数目小于前m帧中匹配点的平均数目Nav时, 说明跟踪结果不太准确或者目标被遮挡, 此时不对颜色目标模板进行更新。否则, 则更新颜色目标模板, 即:
其中, qu表示更新前颜色目标模板中第u个颜色区间的值表示更新后颜色目标模板中第u个颜色区间的值, pu表示当前帧跟踪结果中颜色直方图的第u个颜色区间的值。
2.3 SIFT目标模板的更新
采用文献[6]中的方法对SIFT目标模板进行更新。主要包括删除特征点, 增加特征点两个环节。
(1) 删除特征点
如果SIFT目标模板中的某个特征点在连续几帧中都不存在与之相匹配的特征点, 就认为在下一时刻特征点出现匹配点的概率为0。这时将这个特征点从SIFT目标模板中删去。从目标模板中删去这些不必要的特征点能够提高算法的速度。算法中用特征的权值πi来表示特征点存在匹配点次数的多少。当πi小于一个预先规定的阈值时, 即πi
(2) 增加特征点
在获得k时刻的跟踪结果后, 还要将跟踪结果中存在的新特征点加入到SIFT目标模板中。为了防止将不属于目标的特征点也加入到目标模板中, 首先在跟踪结果的矩形框中构建一个包含所有匹配特征点的最小矩形框, 然后只将最小矩形框内的特征点加入到SIFT目标模板中。
3 算法描述
下面对基于SIFT特征和模板更新的粒子滤波目标跟踪算法的跟踪流程进行描述。
步骤1在初始帧中, 提取目标的颜色直方图和SIFT特征, 形成颜色目标模板和SIFT目标模板, 对粒子的状态和权值进行初始化。
步骤2利用式 (2) 转移粒子的状态, 提取粒子候选区域中的颜色直方图和SIFT特征点, 根据式 (8) 和式 (15) 分别计算基于颜色的粒子权值和基于SIFT特征的粒子权值, 根据式 (16) 对两种粒子权值进行加权。
步骤3利用式 (17) 估计当前帧目标的状态。
步骤4提取当前帧跟踪结果中的SIFT特征并与SIFT目标模板进行匹配, 如果匹配的SIFT特征点的数目大于前m帧匹配的平均数目, 则利用式 (18) 对颜色目标模板进行更新。对SIFT目标模板进行更新。
步骤5根据粒子的权值对粒子进行重采样。
步骤6若视频没有处理完, 转步骤2。否则, 算法结束。
基于SIFT特征和模板更新的粒子滤波目标跟踪算法的流程如图1所示。
4 实验结果分析和比较
为了验证基于SIFT特征和模板更新的粒子滤波目标跟踪算法的有效性, 本文用PETS2001数据库中不同场景下的视频对算法进行测试, 并将实验结果与文献[4]中传统的粒子滤波算法, 文献[6]中仅适用SIFT特征的粒子滤波算法进行比较。算法的程序是用VC++6.0在Intel i5的CPU, 4GB内存的电脑上实现的。所有的实验中, 粒子滤波器的粒子数为100。为了使算法对光照不敏感, 颜色直方图是在量化等级为10×10×10的HSV颜色空间中计算的。在视频的初始帧, 用矩形框包含跟踪目标。
第一个视频用来验证当背景中存在与目标颜色相近的对象时本文算法的有效性。取α=0.45, β=0.7, γ=0.8, 如图2所示, 图中选取的4帧图像依次为第1帧, 第40帧, 第126帧和第204帧。从图中可以看出, 传统的粒子滤波器不能正确的跟踪目标, 因为目标的颜色与背景中其他对象的颜色相似, 所以跟踪框不停地在目标和另一对象之间跳动, 如第40帧, 126帧。随着目标越来越靠近路边停放的一排黑色汽车, 传统的粒子滤波器又跟踪到了黑色汽车上, 如第204帧。文献[6]的算法也不能较好的对目标进行跟踪, 主要原因是:目标较小, 纹理较单一, 提取不到足够的SIFT特征点对目标进行描述。基于SIFT特征和模板更新的粒子滤波器结合了颜色特征和SIFT特征, 弥补了两种算法的不足之处, 能够在整个视频中对目标进行成功的跟踪。
为了定量地比较算法的性能, 表1统计了视频1的总帧数, 正确跟踪的帧数, 正确跟踪率以及平均每帧所用时间。可以看到, 本文提出算法的正确跟踪率远高于其他两种算法。由于传统的粒子滤波算法仅使用颜色特征, 所以实时性较好。本文算法的实时性与文献[6]中的实时性相差不大, 但是跟踪的正确率要远高于文献[6]中的算法。
第二个视频主要用来验证本文提出的模版更新算法的有效性。取α=0.4, β=0.7, γ=0.8, 如图3所示, 图中选取的4帧图像依次为第87帧, 第94帧, 第99帧和第102帧。目标从第87帧开始被路灯遮挡, 从第102帧开始远离遮挡。在这个过程中, 基于颜色的粒子滤波器一直将路灯和另一个与目标颜色相近的对象也认为是目标, 将其与真实目标一起包含到了矩形框内。这是因为基于颜色的粒子滤波器不能区分目标和背景中颜色相近的对象, 所以在整个跟踪过程, 跟踪框或者跟踪到另一个颜色相近的对象上, 或者将两个人一起都包含到跟踪框中。在更新目标模板时, 由于路灯和另一个对象都与目标颜色相近, 从跟踪框中提取的颜色直方图与颜色目标模板之间的相似性会大于模板更新的阈值, 从而导致目标模板被错误地更新, 所以在遮挡的整个过程中将路灯和另一个对象也认为是目标。
基于SIFT特征和模板更新的粒子滤波器在目标被遮挡的过程中能成功地对目标进行跟踪。这是因为当目标被遮挡时, 目标的SIFT特征虽然减少, 但是仍然有一部分SIFT特征可见。可以利用可见的SIFT特征来区分目标与另一个颜色相近的对象。另外, 由于采用了3.3节所讲的模板更新方法, 由于目标被遮挡, 导致目标SIFT特征的匹配点数少于前m帧匹配点的平均值, 所以目标的颜色模板没有更新, 保证了目标模板的正确性, 从而能够获得正确的目标状态。由于目标在走路的过程中会发生形变, 所以应对颜色模板和SIFT模板进行即时更新, 否则跟踪的精度会受到影响。
表2统计了视频2的总帧数, 正确跟踪的帧数以及正确跟踪率。从表2中可以看出, 去掉模板更新后, 跟踪的正确率会下降。
5 结语
本文提出了一种将颜色特征和SIFT特征一起融合到粒子滤波器中的跟踪算法。提取目标的颜色直方图和SIFT特征点分别建立颜色目标模板和SIFT目标模板。在跟踪过程中, 利用颜色直方图之间的Bhattacharyya距离和SIFT特征点之间的匹配数目分别计算基于颜色的粒子权值和基于SIFT特征的粒子权值, 并将两部分权值按照各自的重要性结合起来形成粒子的最终权值。在更新目标模板时, 利用跟踪结果中的特征点与SIFT目标模板中的特征点的匹配数目N是否大于前几帧匹配的平均数目作为是否进行颜色模板更新的依据。通过对不同场景下的目标进行跟踪, 验证了算法的有效性和鲁棒性。
然而, SIFT特征的提取和匹配算法复杂度较高, 所以本文提出的算法在一定范围内是以牺牲算法的实时性来提高算法的鲁棒性。在以后的研究中, 可以采用最近出现的一些提高SIFT运算效率的算法, 比如SURF[11]算法, 来提高SIFT特征点的提取效率, 还可以采用积分颜色直方图[12]算法来提高颜色直方图的计算效率, 从而弥补在提取SIFT特征点时消耗的计算量。
参考文献
[1]Fukunaga K, Hostetler L.The estimation of the gradient of a density function, with applications in pattern recognition[J].Information Theory, IEEE Transactions on, 1975, 21 (1) :32-40.
[2]Comaniciu D, Ramesh V, Meer P.Kernel-based object tracking[J].Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2003, 25 (5) :564-577.
[3]Comaniciu D, Ramesh V, Meer P.Real-time tracking of non-rigid objects using mean shift[C]//Computer Vision and Pattern Recognition, 2000.Proceedings.IEEE Conference on.IEEE, 2000, 2:142-149.
[4]Isard M, Blake A.Condensation—conditional density propagation for visual tracking[J].International journal of computer vision, 1998, 29 (1) :5-28.
[5]Zhao Y, Pei H.Object tracking based on particle filter with discriminative features[J].Journal of Control Theory and Applications, 2013, 11 (1) :42-53.
[6]牛长锋, 陈登峰, 刘玉树.基于SIFT特征和粒子滤波的目标跟踪方法[J].机器人, 2010, 32 (2) :241-247.
[7]Fan Z, Li M, Liu Z.An adaptive particle filter tracking algorithm based on multi-information fusion[C]//Signal Processing (ICSP) , 2012IEEE 11th International Conference on.IEEE, 2012, 2:1092-1095.
[8]Xiaowei Z, Hong L, Xiaohong S.Object Tracking with an Evolutionary Particle Filter Based on Self-Adaptive Multi-Features Fusion[J].Int J Adv Robotic Sy, 2013, 10 (61) .
[9]Lowe D G.Distinctive image features from scale-invariant keypoints[J].International journal of computer vision, 2004, 60 (2) :91-110.
[10]Nummiaro K, Koller-Meier E, Van Gool L.Color features for tracking non-rigid objects[J].ACTA Automatica Sinica, 2003, 29 (3) :345-355.
[11]Bay H, Tuytelaars T, Van Gool L.Surf:Speeded up robust features[M]//Computer Vision–ECCV 2006.Springer Berlin Heidelberg, 2006:404-417.
特征粒子 第6篇
所谓目标跟踪,就是在视频序列的每一帧找出初始时刻选取的兴趣区域,它的关键是建立一个好的目标模板,而建立一个好的目标模板则离不开好的特征提取算法。文献[1]和文献[2]基于颜色特征对目标进行描述,该类算法的速度相对较快,但抗干扰能力相对较差,在背景颜色相近情况下跟踪准确度不高。对多种算法进行融合是一种有效提高算法性能的办法,文献[3]研究了基于SIFT特征的粒子滤波目标跟踪算法,在粒子权值更新阶段,粒子的权值更新由SIFT特征和颜色直方图特征共同决定,该算法虽然比单使用颜色直方图特征时的跟踪准确率更高,但由于SIFT算法本身计算量较大,导致该算法的速度不会很快。还有一些算法通过融合具有不同特点的跟踪算法来实现分步跟踪,如文献[4]就是Mean Shift和粒子滤波两种算法的融合,事先手动设置一个阈值,满足阈值条件时选择Mean⁃Shift跟踪,否则利用粒子滤波进行跟踪,这种算法虽然一定程度上缓解了局部遮挡的问题、提高了运算速度,但由于这两种算法本身的局限性,使得该算法也存在相应局限,且手动设置阈值具有人为主观性。
文献[5]提出了一种新的特征描述方法,即CBLID算法。CBLID特征算法是在SIFT特征提取的基础上进行了优化改进,并且在描述符生成阶段借鉴了DAISY描述符的思想,从而减少了运算,提高了效率。它继承了SIFT特征的优点,对众多干扰都具有很好的免疫力,同时也因卷积方向图的运用提高了速度,所以将CBLID特征算法融入到粒子滤波跟踪算法中,将目标的颜色直方图特征和CBLID特征结合起来对目标进行描述,实现算法的改进。
1 粒子滤波跟踪算法步骤
20 世纪80 年代,伴随计算机视觉的发展,提出了粒子滤波的概念[6],它是一种能够有效解决局部遮挡、抗干扰能力较强的算法,它的这些优势使得它经常被运用到目标跟踪领域。简单来说,所谓粒子滤波就是利用一组带有权值的随机样本来近似预测目标某一时刻的状态,这里的样本即被形象化为“粒子”。粒子滤波跟踪算法的基本步骤如下:
(1)重采样。为了避免粒子退化现象,需要进行重采样,当粒子的权值低于阈值即被淘汰,剩余的粒子被复制。
(2)粒子传播。对所有粒子的状态按照一定的规则进行随机扩散。
(3)权值更新。K时刻粒子权值 ωki由k-1 时刻粒子权值 ωik - 1生成为
其中,ρi为第i个粒子与目标模板的相似度。
(4)位置估计。对粒子加权得到目标位置估计,如下式
2 基于CBLID特征的粒子滤波
彩色二进制局部不变特征[5]是一种用于描述彩色图像局部特征的算法,它的基本思路是先定义一个对尺度缩放、光照变化、背景干扰都不敏感的颜色不变量H,然后在特征点提取阶段采用CDo FAST快速特征点检索方法:以某候选点为中心,R为半径,等间隔在圆周上采8 个样本点,计算这8 个采样点与中心点灰度值的差,并计算大于阈值的点的数目N,若N大于阈值,则定义该中心点为FAST角点。此处R为手动设定,通常取3 个像素大小。然后将检测到的FAST角点作为候选特征点,再找出FAST角点三维空间邻域的DOG极值点,作为最终的CDo FAST特征点。CBLID特征描述符生成阶段,利用卷积方向图为每一个CDo FAST特征点建立一个192维的CBLID描述子。
将CBLID特征融入粒子滤波器以提高算法的跟踪稳定性。该算法的核心思想在于采用了两种特征共同决定粒子权值的更新,并且可根据实际场景目标的情况来自适应调整两种特征所占权重,增强了目标跟踪在某些场景下的鲁棒性。而在目标模板的更新部分,相应的也要分别建立颜色直方图模板和CBLID模板,当前帧跟踪结果与CBLID目标模板特征点匹配数大于前几帧匹配均值时,更新颜色目标模板和CBLID模板,否则不更新颜色模板,仅更新CBLID模板。
2.1 粒子权值更新
将粒子权值更新阶段分为两个部分,即基于颜色直方图特征的粒子权值和基于CBLID特征的粒子权值。基于颜色直方图特征的粒子权值计算依据式(1),其中相似度利用颜色直方图的Bhattacha⁃ryya距离计算。而基于CBLID特征的粒子权值计算方法是,首先在初始帧确定一个目标区域,提取目标区域的CDo FAST特征点i,并生成对应特征描述子fi,构成目标模板G,即,m表示特征点数,然后提取粒子候选目标区域中的CDo FASTt特征点,并计算其特征向量,最后与目标模板进行匹配,匹配数越多的粒子权值越大。定义似然函数为
其中,fj∈ G ,match( fj) 是当前帧跟踪结果与fj相匹配的特征向量。 M(match( fj)) 由式(4)计算。
其中,Gki为k时刻第i个粒子区域中的特征点集。
在目标模板中,有的CDo Fast特征点成功匹配次数多,有的成功匹配的次数少,有的甚至没有成功匹配过。所以每一个CDo FAST特征点的地位是不同的,故而引入CDo FAST特征点权值。 每个CDo FAST特征点的权值由上一帧权值和当前状态两部分构成。当目标运动较快的时候,目标相邻两帧位移较大,上一帧权值的可靠性较小,此时当前状态对权值影响所占比重较大。因此,第k帧某CDo FAST特征点j的权值定义为
其中,β是一自适应数,与目标速度有关,介于0~1;速度越快β越大。取,Vt是目标移动速度;V0是个常数,其中,St是t-1 时刻到t时刻目标在视频中移动的距离;t为视频一帧耗时。 Mjk由式(6)计算。
其中,表示N个粒子候选区域的并集,只要并集中存在与fj相匹配的特征向量,那么Mjk就为1。
由于定义了特征点权值,故而需要把式(3)重新定义为
故而基于CBLID特征的粒子权值可以写为
从而粒子权值的最终表达式为
式中,是基于颜色直方图特征计算出的粒子权值;α是一自适应数,介于0~1,与目标提取的特征点数有关,特征点越多α越小。,m为目标模板包含的CBLID特征点数;N0为一个常数。第k帧目标的位置估计由式(10)计算。
2.2 目标模板更新
在目标跟踪的过程中,目标本身和周围环境是不断变化的,目标的颜色特征和CBLID特征也在不断变化。因此,需要对目标模板进行实时更新。
2.2.1颜色直方图模板更新
通常,粒子滤波跟踪中,目标颜色直方图模板的更新是依据跟踪结果的颜色直方图与目标模板之间的相似度,当相似度大于一定的阈值时,进行更新,这种更新方式的抗干扰能力较差,容易导致跟踪失败。
文中算法更新目标颜色模板的方法是:当目标CBLID模板与跟踪结果中的CBLID特征点匹配数目大于前几帧匹配数目的均值时,目标颜色模板值qx更新,更新后模板值由下式计算
其中,Na表示CDo FAST特征点匹配数目;Nav表示前几帧匹配平均数;px为某一时刻跟踪结果;x是颜色直方图区间号;γ是一常数。
2.2.2 目标CBLID特征模板的更新
CBLID模板的更新包含以下两个部分[7]。
(1)删除特征点
随着跟踪不断进行,有些CBLID模板中的特征点可能会长时间不存在与之匹配的特征点,显然这些点就不属于CBLID模板,需要删除。当某一特征点权值 πi< Fth时即满足删除条件。其中,Fth是阈值;πi是该CBLID特征点的权值。
(2)增加特征点
每一帧的跟踪都可能会提取到新的特征点,如果这些特征点属于目标CBLID模板,就需要把它们加入到目标CBLID模板中。简单来说,就是要将属于目标范围内的新提取特征点加入到CBLID模板中。
3 算法流程
文中跟踪算法步骤如下:
(1)选取目标。分别提取两种特征构建目标模板,粒子初始化;
(2)粒子传播。提取粒子的两种特征,再分别根据式(1)和式(8)计算相应特征的粒子权值,根据式(9)对两种粒子权值进行加权;
(3)利用式(10)估计当前帧目标的位置;
(4)利用式(11)对目标颜色和CBLID模板分别进行更新;
(5)对粒子进行重采样;
(6)获取视频图像,转步骤(2)。
跟踪算法流程图如图1。
4 实验结果分析对比
为了验证文中提出的跟踪算法的性能,采用了STELLAR数据库中的两个视频的进行实验。算法是在VS2013,Intel i7CPU,8G内存的环境下实现的。通过实验确定的参数为:γ=0.8,V0=80,N0=8,粒子数为75。视频1 主要用来比较传统粒子滤波与文中算法在遇到颜色相近干扰时的跟踪准确性,视频2 主要用来比较基于SIFT特征和基于CBLID特征的两种粒子滤波跟踪算法的实时性和准确性。
图2给出实验一中部分跟踪结果。
图2 为实验视频1 的第20 帧、42 帧、161 帧和241 帧文献[8]与文中算法的跟踪对比结果。显而易见,文献[8]所用的基于颜色直方图的粒子滤波跟踪算法在有颜色相近干扰物时的跟踪效果非常差,在第42 帧出现了明显的跟踪偏差。反观文中算法在各帧的跟踪结果都比较理想,抗干扰能力表现出色。文中针对视频1 部分进行定量分析,如表1 所示。
由于融入了CBLID特征,与仅使用颜色直方图特征的粒子滤波算法相比较,在时间上要稍慢,但是在跟踪正确率上要明显高于前者。
图3给出实验二中部分跟踪结果。
图3为实验视频2的第74帧、86帧、108帧文献[3]与文中算法的跟踪对比结果,虽然两种算法在准确性上相近,但是从第86帧可以明显看出文中算法的准确度要略高于基于SIFT特征的粒子滤波算法,跟踪更为准确。同时在观察了跟踪时间后可以得出,文中的算法速度更快。结果如表2所示。
5 结论
提出了一种将彩色二进制局部不变特征融入到传统粒子滤波的跟踪算法。以CBLID和颜色直方图两种特征共同描述目标建立目标模板,充分发挥两种特征各自优势,并且在粒子权值更新阶段做到了对两种特征权值所占比重的自适应。而在模板更新阶段令颜色特征模板的更新依赖于CBLID特征模板,使得算法的鲁棒性得到了提高。通过对不同场景目标进行跟踪实验,验证了文中算法的鲁棒性和时效性。
由于文中采用了两种计算量相对来说都比较大的算法,所以在速度上虽然比基于SIFT特征的粒子滤波算法更快,但是相对一些其他跟踪算法要稍慢,在日后的工作中还可以进行优化提速。
摘要：当背景与目标颜色相近时,传统基于颜色直方图的粒子滤波跟踪算法容易被干扰发生错误跟踪。彩色二进制局部不变特征(CBLID)具有旋转、尺度缩放和光照不变性等特点,将CBLID特征应用到粒子滤波跟踪算法中,以提高跟踪算法的抗干扰能力。考虑到纹理少的目标的CBLID特征点较少,仅仅依据CBLID特征进行跟踪不稳定,提出一种结合CBLID特征与颜色直方图特征的粒子滤波跟踪算法。该算法依据颜色直方图的Bhattacharyya距离以及CBLID特征点匹配数目确定粒子的权值,并根据当前帧跟踪结果及CBLID目标模板中特征点匹配数来决定是否对目标颜色模板进行更新。实验结果表明,当目标出现遮挡或者背景颜色相近时,该方法能够有效地提高跟踪精度,同时它比基于SIFT特征的粒子滤波算法速度快。
关键词：目标遮挡,颜色相近,CBLID特征,粒子滤波
参考文献
[1]朱志宇.粒子滤波算法及其应用[M].北京:科学出版社,2010.
[2]王绍钰,蔡自兴,陈爱斌.改进的粒子滤波器目标跟踪方法[J].智能系统学报,2008,3(3):189-194.
[3]曹正洁,王汇源,张元元,等.基于SIFT特征和模板更新的粒子滤波目标跟踪算法[J].计算机应用与软件,2014(12):298-302.
[4]李红波,曾德龙,吴渝.基于Mean-Shift和粒子滤波的两步多目标跟踪方法[J].重庆邮电大学学报:自然科学版,2010,22(1):112-117.
[5]王灿进,孙涛,王锐,等.基于彩色二进制局部不变特征的图像配准[A].中国激光,2015,42(1):0109001-1-0109001-9.
[6]陈家波,赵勋杰,许峥.基于梯度方向直方图特征和粒子滤波算法融合的目标跟踪[A].小型微型计算机系统,2012,33(8):1821-1824.
[7]牛长锋,陈登峰,刘玉树.基于SIFT特征和粒子滤波的目标跟踪方法[J].机器人,2010,32(2):241-247.
特征粒子 第7篇
随着分布式可再生能源、非线性负荷与电力电子设备的大量接入,电能质量(Power Quality,PQ)问题日益受到电力工作人员的重视[1]。PQ问题多表现为电压质量问题,包括电压暂升、电压暂降、电压中断、电压闪变、暂态振荡和谐波等。而在实际系统中,还经常发生含有多种扰动的复合扰动。
准确分类PQ信号是治理PQ问题的前提和基础。分类时,需先对原始扰动信号进行变换与处理,提取出表征扰动信号特点的分类特征。常用的方法有S变换(S-Transform,ST)[2]、小波变换(Wavelet Transform,WT)[3]和短时傅里叶变换(Short Time Fourier Transform,STFT)[4]等。ST分析中采用的高斯窗口的高度和宽度是动态变化的,其具有良好的时-频特性与抗噪能力,可以提取丰富的时-频特征用于分类PQ信号[5,6]。但是过多的特征也会造成分类器维度过高、分类效率与准确率下降的缺陷。因此,需要对原始特征集合进行特征选择,以降低特征集合维度与分类器复杂度,提高分类效率。
PQ信号分类方法主要包括支持向量机[2]、BP神经网络[7]和概率神经网络[8]等。这些方法具有良好的鲁棒性,但是参数设置复杂,时间或空间复杂度较高,实现困难。极限学习机(Extreme Learning Machine,ELM)需要优化的参数少,实现起来简单、迅速,能够满足PQ信号分类问题的要求。
为简化PQ信号分类器结构,提高分类效率与准确率,本文提出一种基于粒子群优化算法(Particle Swarm Optimization,PSO)与ELM的PQ信号特征选择与分类方法。首先利用S变换对原始扰动信号进行时-频分析,并根据变换结果提取原始扰动特征;其次,将PSO和ELM相结合,以ELM分类精度和选择特征个数构建适应度函数,并以适应度函数值最大为准则,在特征空间中进行寻优,以降低特征维数;然后,使用最优特征子集构成ELM的输入向量,训练ELM;最后,采用该模型识别包含2种复合扰动在内的8类PQ信号,并通过仿真实验验证新方法的有效性。
2 S变换与特征提取
2.1 S变换原理
ST是在连续快速傅里叶变换(Successive Fast Fourier Transform,SFFT)和WT的基础上发展而来,相较其他方法具有更好的抗噪能力和特征表现能力,因而广泛地应用于PQ扰动信号识别。
设输入信号为h(t),其连续ST为:
式中
式中,w(τ-t,f)为高斯窗口;t为时间;τ是一个参数,控制高斯窗口在时间轴上位置;f为频率。ST的逆变换为:
由式(1)和(2)可得到离散ST,表达形式如下:
式中,j=1,2,…,N,表示时间指数;N为采样点数;T为采样时间间隔;为h(t)的离散傅里叶变换结果;G(m,n)为高斯窗的傅里叶频谱。ST的变换结果为二维时-频矩阵,其行对应不同频率,列对应不同采样点,矩阵值为对应时-频点幅值。对其结果求模可获得ST模矩阵(ST Modular Matrix,STMM)。针对STMM各行、列开展针对性分析可获得大量特征用于扰动识别。
2.2 扰动信号的S变换
参考文献[2]构建电压暂降(C1)、电压暂升(C2)、电压中断(C3)、电压闪变(C4)、暂态振荡(C5)、谐波畸变(C6)、谐波含电压暂降(C7)和谐波含电压暂升(C8)八类PQ信号模型,通过MATLAB仿真生成PQ信号,信号采样率3.2k Hz,基频50Hz。扰动信号模型见表1。
2.3 特征提取
从经过ST处理的仿真信号中提取25种特征用于构建原始特征集合。所有特征的具体描述如下。
特征1(F1):STMM各列最大幅值中的最大值。
特征2(F2):STMM各列最大幅值中的最小值。
特征3(F3):STMM各列最大幅值的均值(Mean)。
特征4(F4):STMM各列最大幅值的标准差(STD)。
特征5(F5):STMM各列最大幅值的归一化幅值因数(Af)。
特征6(F6):100Hz以上各频率对应最大幅值曲线的标准差。
特征7(F7):100Hz以上各频率对应最大幅值曲线的最大差。
特征8(F8):100Hz以上各频率对应最大幅值曲线的最小差。
特征9(F9):100Hz以上各频率对应最大幅值曲线的最大值与最小值的差。
特征10(F10):高频部分曲线偏度(Skewness)。
特征11(F11):高频部分曲线峭度(Kurtosis)。
特征12(F12):各个频率对应最大幅值曲线的标准差。
特征13(F13):各个频率对应最大幅值曲线的均值。
特征14(F14):各个频率对应幅值标准差曲线的均值。
特征15(F15):各个频率对应幅值标准差曲线的标准差。
特征16(F16):低频部分对应幅值标准差曲线的标准差。
特征17(F17):高频部分对应幅值标准差曲线的标准差。
特征18(F18):谐波总含量(THD)。
特征19(F19):原始信号1/4周期能量跌落幅度。
特征20(F20):原始信号1/4周期能量上升幅度。
特征21(F21):基频幅值的标准差。
特征22(F22):中频部分最大值。
特征23(F23):700~1000Hz高频段能量。
特征24(F24):形态学去噪后高频频段能量。
特征25(F25):FFT功率谱中频段80~470Hz能量。
设xi为扰动样本向量X中某一个采样点的电压幅值,1≤i≤N,N为扰动样本所包含的采样点数。特征相关计算公式如下:
在计算能量相关的特征时,设xij为矩阵中第i行第j列的元素,N1≤i≤N2,M1≤j≤M2,N1、N2、M1和M2分别为计算相关能量特征时所需子矩阵的起始行、终止行、起始列和终止列。相关能量特征计算公式如下:
3 极限学习机
极限学习机是一种单隐含层前馈神经网络(Single-hidden Layer Feedforward Neural Network,SLFN)。与传统神经网络训练算法不同,ELM输入层与隐含层的连接权重以及隐含层各神经元节点的偏置是随机产生的,训练过程中无需调整改变。ELM需要调整的参数少,分类效率、准确率高,适用于PQ信号分类。典型的单隐含层前馈神经网络的结构如图1所示。
给定一组数据:S={(x1,y1),…,(xp,yp)},其中xi∈Rn为训练样本输入,yi∈Rm为训练样本值,i=1,2,…,p,则包含有l个隐含层神经元,且激活函数为g(x)的ELM数学模型为:
式中,αi为输入节点与第i个隐含层节点的连接权值向量;βi为第i个隐含层节点与输出节点的连接权值向量;bi为第i个隐含层节点的偏置。
式(5)可以化简为:
式中,T=[t1,t2,…,tp]T;H为隐含层输出矩阵:
Huang等人[9]证明,若隐含层神经元个数l等于训练集样本数,则对于任意的α和b,SLFN将以零误差逼近训练样本,即:
当样本数p过大时,为了降低计算复杂度,隐含层神经元个数l取值一般小于样本数p,此时SLFN的训练误差将小于任意ε>0,即:
隐含层与输出层的连接权值β的求解如下:
其最小二乘解为:
式中,为H的Moore-Penrose广义逆。
4 基于PSO的ELM特征选择
4.1 PSO算法原理
PSO首先在解空间中初始化一群粒子,每个粒子代表一个潜在的最优解,且由位置、速度和适应度值三个参数表征。粒子通过跟踪个体极值Pbest和群体极值Gbest来更新上述三个参数,并根据新粒子的适应度值更新Pbest和Gbest。
假设搜索空间为D维,粒子群共含有N个粒子,其中第i个粒子表示为Xi=(xi1,xi2,…,xiD),即粒子i在搜索空间中的位置;Vi=(vi1,vi2,…,viD)表示粒子i的速度;记Pi=(Pi1,Pi2,…,PiD)为粒子i的个体极值;群体极值则记为Pg=(Pg1,Pg2,…,PgD)。迭代过程中,通过式(12)和式(13)更新粒子的速度和位置:
式中,w为惯性权重;d=1,2,…,D;i=1,2,…,N;k为当前迭代次数;c1、c2称为加速度因子,是非负的常数;r1、r2为随机数,取值范围为[0,1]。每个粒子的位置和速度都被限制在一定的范围内,超过该范围则取其边界值,避免粒子的盲目搜索。
4.2 PSO-ELM特征选择
将PSO与ELM相结合,进行PQ信号特征选择。由于特征选择可以简化为一个“0-1”组合优化问题,所以在初始化粒子时,将每一维特征对应的粒子位置随机初始化为“0”或者“1”,“0”表示该维特征被淘汰,“1”则表示特征被选中。粒子每次更新位置后,按如下规则调整位置向量中元素:
因为特征选择的目标是在选择尽可能少的特征的条件下,获得尽可能高的分类准确率,因此PSO适应度函数应同时考虑选择特征的个数和分类精度,且更加侧重分类精度。新方法适应度函数设计如下:
式中,rate为分类准确率;n为特征子集维度。
采用新方法特征选择过程如下:
(1)初始化粒子;
(2)根据适应度函数计算每一个粒子的适应度值,确定个体极值Pbest和群体极值Gbest;
(3)根据Pbest和Gbest更新粒子位置与速度,将每一个粒子所表示的特征子集作为ELM的输入向量,并检验该ELM在测试集上的分类精度;
(4)重复步骤(2)和步骤(3),直至达到最大迭代次数。
整个特征选择过程中,以采用不同特征组合后,分类具有随机噪声与随机参数值的样本集的整体准确率为特征分类效果评判标准,而不必考虑具体特征对特定类型扰动的分类效果,这样降低了特征选择方法的复杂度。算法流程如图2所示。
5 实验仿真
实验所用数据均由MATLAB7.10产生。为获得能够满足不同噪声环境分类需要的最优特征子集,分别仿真生成含30~50d B随机噪声的训练样本,每种扰动信号500组,用于特征选择;选用信噪比分别为50d B、40d B和30d B的测试集,每类各100组,验证特征选择结果的分类效果。为提高方法的鲁棒性,全部实验过程中,训练集与测试集中样本参数均采用覆盖相关参数范围的随机值,以验证方法在不同参数条件下的有效性。
实验中,PSO最大迭代次数为300次,粒子速度更新公式中c1=c2=1.49445,速度边界值分别为vmax=0.5、vmin=-0.5。
由于PSO算法中粒子规模会对适应度值有所影响,因此,分别分析不同规模下PSO算法的适应度值,如图3所示。由图3可知,适应度值最高点出现在粒子规模为4的时候,此时选择出的特征子集为FS1={F2,F5,F6,F9,F17,F19,F20,F21},含8个特征;具有次优适应度值的粒子规模为11,特征子集为FS2={F2,F5,F7,F13,F14,F17,F18,F19,F21,F22,F23},含11个特征。上述2个特征子集在不同信噪比下的分类精度如表2所示。由表2可知,FS1的分类准确率优于FS2,且特征数更少。可见,具有最优适应度值的选择结果最适于PQ信号分类,而冗余特征的加入不仅会增加分类器时间和空间复杂度,还会影响分类器分类准确率。
此外,ELM的激活函数选为Sigmoid时,新方法根据分类准确率,确定隐含层神经元个数l。不同噪声环境下,l对分类精度的影响如图4所示。由图4可见,当l为75时,分类准确率达到最高,且趋于稳定。而训练的时间代价则随着l的增加而不断提升,因此,新方法取l=75。
为进一步验证新方法的有效性,采用与表2所用相同试验样本,与其他三种方法[10,11,12]进行对比,结果如表3所示,其中,MFST为多分辨率快速S变换,DT为决策树,RVM为相关向量机,PNN为概率神经网络。由表3可知,新方法在处理特定信噪比下实验样本时,准确率高于文献[10]与文献[11]方法,略低于文献[12]方法。
为客观分析新方法的扰动识别效果,将三类对比方法的识别的扰动种类均设为本文使用的八类。
考虑到实际分类环境下信号信噪比无法预知,因此,具有随机噪声水平的信号更能够验证方法的实际应用效果。因此,对比试验中训练分类器时,采用具有30~50d B随机噪声的训练样本,每类各500组;测试时,使用具有随机噪声信噪比为30~50d B的测试信号,每类各300组,验证各种方法的分类精度。在随机噪声环境下,四种方法的扰动识别效果如表4所示。
由表4可见,随机噪声环境下,新方法具有最好的扰动识别效果,相较于采用决策树分类的文献[12]方法,具有更好的泛化能力,且新方法更加适合噪声水平未知的实际PQ扰动信号分类需求。
6 结论
本文提出一种基于PSO与ELM的新型PQ信号特征选择和识别方法。新方法将特征维度由25维缩减到8维,极大降低了训练分类器所耗费的时-空代价,相较现有方法,新方法在分类具有随机噪声的测试集时,具有最高的分类准确率,更适合实际环境工作需要。
摘要：高效准确地分类电能质量扰动信号是处理电能质量问题的关键。为降低特征计算量,提高分类器分类效率,本文提出一种基于粒子群与极限学习机的电能质量特征选择与识别方法。首先,通过S变换对电能质量扰动信号进行重构与变换,并在此基础上提取特征;然后,以极限学习机的分类精度和选择特征个数作为适应度函数,通过粒子群算法在高维特征空间中寻优,剔除不相关和冗余的特征,保留对扰动识别有效果的特征,由此,确定最优分类子集;最后,使用最优特征子集构成极限学习机的输入向量,训练分类器,并采用优化后的分类器分类电能质量信号。仿真实验表明,新方法能够将维度为25的原始特征集合缩减到8维,且在不同噪声环境下保持综合分类准确率为99.33%。
关键词：电能质量,S变换,粒子群算法,极限学习机,特征选择
参考文献
[1]白鸿斌,王瑞红,王真,等(Bai Hongbin,Wang Ruihong,Wang Zhen,et al.).风电场接入电网的电能质量分析方法研究及案例分析(Analysis method of power quality with the integration of wind power and case study)[J].东北电力大学学报(自然科学版)(Journal of Northeast Dianli University Natural Science Edition),2008,28(6):33-37.
[2]黄南天,徐殿国,刘晓胜(Huang Nantian,Xu Dianguo,Liu Xiaosheng).基于S变换与SVM的电能质量复合扰动识别(Identification of power quality complex disturbances based on S-transform and SVM)[J].电工技术学报(Transactions of China Electrotechnical Society),2011,26(10):23-30.
[3]欧阳森,王建华,耿英三,等(Ouyang Sen,Wang Jianhua,Geng Yingsan,et al.).基于小波和神经网络的电能质量辨识方法(Power quality classification based on wavelet transform and neural network)[J].电工电能新技术(Advanced Technology of Electrical Engineering and Energy),2003,22(3):32-36.
[4]徐永海,赵燕(Xu Yonghai,Zhao Yan).基于短时傅里叶变换的电能质量扰动识别与采用奇异值分解的扰动时间定位(Identification of power quality disturbance based on short-term Fourier transform and disturbance time orientation by singular value decomposition)[J].电网技术(Power System Technology),2011,8(8):174-180.
[5]吕干云,冯华君,汪晓东,等(Lv Ganyun,Feng Huajun,Wang Xiaodong,et al.).基于S变换和人工神经网络的电能质量扰动识别(PQ disturbances identification based on S-transform and ANN)[J].仪器仪表学报(Chinese Journal of Scientific Instrument),2006,27(S3):2281-2283.
[6]Naik C A,Kundu P.Power quality disturbance classification employing S-transform and three-module artificial neural network[J].International Transactions on Electrical Energy Systems,2014,24(9):1301-1322.
[7]欧阳森(Ouyang Sen).改进遗传算法和神经网络在电能质量扰动识别中的应用(Improved genetic algorithm and neural network’s application in the recognition of power quality disturbances)[J].电工电能新技术(Advanced Technology of Electrical Engineering and Energy),2005,24(3):13-17.
[8]Lee C Y,Shen Y X.Optimal feature selection for powerquality disturbances classification[J].IEEE Transactions on Power Delivery,2011,26(4):2342-2351.
[9]Huang G B,Zhu Q Y,Siew C K.Extreme learning machine:Theory and applications[J].Neurocomputing,2006,70(1-3):489-501.
[10]赵立权,谢妮娜(Zhao Liquan,Xie Nina).基于小波变换和改进的RVM的电能质量扰动分类(Classification of power quality disturbances based on wavelet transform and improved RVM)[J].电工电能新技术(Advanced Technology of Electrical Engineering and Energy),2013,32(4):74-78.
[11]唐求,王耀南,郭斯羽,等(Tang Qiu,Wang Yaonan,Guo Siyu,et al.).基于S变换与PNN的电能质量多扰动检测(Power quality disturbance detection based on S-transform and PNN)[J].仪器仪表学报(Chinese Journal of Scientific Instrument),2009,30(8):1668-1673.