第14卷第4期 智能系统学报 Vol.14 No.4 2019年7月 CAAI Transactions on Intelligent Systems Jul.2019 D0:10.11992/tis.201805049 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20180709.1438.010html 用于目标跟踪的智能群体优化滤波算法 许奇，王华彬，周健，陶亮 (安徽大学计算智能与信号处理教育部重点实验室，安徽合肥230031) 摘要：针对目标跟踪中的状态估计，提出一种智能群体优化滤波算法。算法在贝叶斯滤波的基础上，运用智 能群体优化的3种运动模型估计目标的后验状态，其中内聚运动在保持了粒子多样性的情况下增加了样本的 权值，分离运动和排列运动相协调能够更加准确地预测下一时刻目标的先验状态。实验结果表明：与标准粒子 滤波相比，该算法能够更加准确地估计非线性系统中的后验状态，在复杂多变的场景环境中，表现出更高的跟 踪准确性。 关键词：目标跟踪；视觉跟踪；滤波算法；贝叶斯滤波：粒子滤波；运动模型；后验状态；智能群体优化 中图分类号：TP391.41文献标志码：A文章编号：1673-4785(2019)04-0697-11 中文引用格式：许奇，王华彬，周健，等.用于目标跟踪的智能群体优化滤波算法.智能系统学报，2019,14(4)：697-707. 英文引用格式：XUQi,WANG Huabin,.ZHOU Jian,et al.Swarm intelligence filtering for robust object tracking J.CAAI transac- tions on intelligent systems,2019,14(4):697-707. Swarm intelligence filtering for robust object tracking XU Qi,WANG Huabin,ZHOU Jian,TAO Liang (Key Laboratory of Intelligent Computing and Signal Processing of Ministry of Education,Anhui University,Hefei 230031,China) Abstract:To estimate the state of target in object tracking,a novel algorithm named swarm intelligence filter(SIF)is proposed in this paper.Based on the Bayesian filter,the algorithm could estimate the posterior state using three move- ments of swarms.The cohesion movement could add the weight by maintaining the diversity of the sample,and the co- ordination of separation and permutation movements could more accurately predict the state of the next moment com- pared with the conventional algorithm.The experimental results show that compared with the conventional particle fil- ter,our algorithm could more accurately predict the posterior state in nonlinear systems and more accurately estimate the state of the object in complex environment. Keywords:object tracking;visual tracking;filtering algorithm;Bayesian filter;particle filter;motion model;posterior state;swarm intelligence optimization 滤波算法是一种能在非线性离散时间内估计 (particle filter,.PF)等。KF算法只能用来解决线性 后验状态的算法。在目标跟踪中，滤波算法是在 问题，而在目标跟踪中大多数情况下都是非线性 贝叶斯滤波(Bayesian filter)框架下，给定当前时 问题，因而适用度不高四。EKF算法将非线性系 刻的观测信息，估计目标的后验状态并预测下一 统局部线性化，对于较弱的非线性系统可以获得 时刻的先验状态。当前应用广泛且较为成熟的滤 很好的滤波效果，但对于较强非线性系统，效果并 波算法有卡尔曼滤波(Kalman filter,KF)、扩展卡 不理想。UKF算法采用无极变换和EKF算法框 尔曼滤波(extended Kalman filter,,EKF)、无迹卡尔 架，其思想是近似高斯分布比近似非线性方程要 曼滤波(unscented Kalman filter,.UKF)和粒子滤波 容易；UKF算法虽然能够得到三阶矩的后验均值 收稿日期：2018-05-31.网络出版日期：2018-07-10. 及协方差估计，但由于其与EKF一样，假设非线 基金项目：国家自然科学基金项目(61371217)：安徽省自然科 性系统的后验状态服从高斯分布，因而对一般的 学基金项目(1708085MF151). 通信作者：王华彬.E-mail:wanghuabin@ahu.edu.cn 模型仍不适用，因此并不适用于目标跟踪
DOI: 10.11992/tis.201805049 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20180709.1438.010.html 用于目标跟踪的智能群体优化滤波算法 许奇，王华彬，周健，陶亮 （安徽大学 计算智能与信号处理教育部重点实验室，安徽 合肥 230031） 摘 要：针对目标跟踪中的状态估计，提出一种智能群体优化滤波算法。算法在贝叶斯滤波的基础上，运用智 能群体优化的 3 种运动模型估计目标的后验状态，其中内聚运动在保持了粒子多样性的情况下增加了样本的 权值，分离运动和排列运动相协调能够更加准确地预测下一时刻目标的先验状态。实验结果表明：与标准粒子 滤波相比，该算法能够更加准确地估计非线性系统中的后验状态，在复杂多变的场景环境中，表现出更高的跟 踪准确性。 关键词：目标跟踪；视觉跟踪；滤波算法；贝叶斯滤波；粒子滤波；运动模型；后验状态；智能群体优化 中图分类号：TP391.41 文献标志码：A 文章编号：1673−4785(2019)04−0697−11 中文引用格式：许奇, 王华彬, 周健, 等. 用于目标跟踪的智能群体优化滤波算法 [J]. 智能系统学报, 2019, 14(4): 697–707. 英文引用格式：XU Qi, WANG Huabin, ZHOU Jian, et al. Swarm intelligence filtering for robust object tracking[J]. CAAI transactions on intelligent systems, 2019, 14(4): 697–707. Swarm intelligence filtering for robust object tracking XU Qi，WANG Huabin，ZHOU Jian，TAO Liang (Key Laboratory of Intelligent Computing and Signal Processing of Ministry of Education, Anhui University, Hefei 230031, China) Abstract: To estimate the state of target in object tracking, a novel algorithm named swarm intelligence filter (SIF) is proposed in this paper. Based on the Bayesian filter, the algorithm could estimate the posterior state using three movements of swarms. The cohesion movement could add the weight by maintaining the diversity of the sample, and the coordination of separation and permutation movements could more accurately predict the state of the next moment compared with the conventional algorithm. The experimental results show that compared with the conventional particle filter, our algorithm could more accurately predict the posterior state in nonlinear systems and more accurately estimate the state of the object in complex environment. Keywords: object tracking; visual tracking; filtering algorithm; Bayesian filter; particle filter; motion model; posterior state; swarm intelligence optimization 滤波算法是一种能在非线性离散时间内估计 后验状态的算法。在目标跟踪中，滤波算法是在 贝叶斯滤波 (Bayesian filter) 框架下，给定当前时 刻的观测信息，估计目标的后验状态并预测下一 时刻的先验状态。当前应用广泛且较为成熟的滤 波算法有卡尔曼滤波 (Kalman filter，KF)、扩展卡 尔曼滤波 (extended Kalman filter，EKF)、无迹卡尔 曼滤波 (unscented Kalman filter，UKF) 和粒子滤波 (particle filter，PF) 等。KF 算法只能用来解决线性 问题，而在目标跟踪中大多数情况下都是非线性 问题，因而适用度不高[1]。EKF 算法将非线性系 统局部线性化，对于较弱的非线性系统可以获得 很好的滤波效果，但对于较强非线性系统，效果并 不理想。UKF 算法采用无极变换和 EKF 算法框 架，其思想是近似高斯分布比近似非线性方程要 容易；UKF 算法虽然能够得到三阶矩的后验均值 及协方差估计，但由于其与 EKF 一样，假设非线 性系统的后验状态服从高斯分布，因而对一般的 模型仍不适用[2] ，因此并不适用于目标跟踪。 收稿日期：2018−05−31. 网络出版日期：2018−07−10. 基金项目：国家自然科学基金项目 (61371217)；安徽省自然科 学基金项目 (1708085MF151). 通信作者：王华彬. E-mail：wanghuabin@ahu.edu.cn. 第 14 卷第 4 期 智 能 系 统 学 报 Vol.14 No.4 2019 年 7 月 CAAI Transactions on Intelligent Systems Jul. 2019
·698· 智能系统学报 第14卷 在目标跟踪中用于估计后验状态的最著名的 滤波算法，本文算法能够有效地应对粒子退化问 方法为粒子滤波算法(particle filter,.PF)。PF算法 题，提高跟踪算法的准确度。 采用序贯蒙特卡洛方法(sequential Monte Carlo methods,.SMC),采用一组样本（即粒子）近似表示 1贝叶斯滤波理论 非线性系统的后验分布，再使用这一近似表示估 给定离散时间动态系统的状态空间模型(dy 计系统的状态。与其他几种算法相比，P℉算法更 namic state-space model,DSSM)可描述为 适用非线性系统，适用范围更广，实际效果也较 好。在当前主流的视觉跟踪算法中，如L1APG算 =f(x-1,g-1) (1) k=h(xk,nk) 法倒、CNT算法和IOPNMF算法等皆是以粒 式中：f和h分别为非线性的状态转移函数和观 子滤波为框架的跟踪算法。然而粒子滤波算法无 测函数；%∈R"和4∈Rm分别为系统的过程噪声 法避免粒子退化现象，这是因为粒子权值的方 和观测噪声；代表k时刻的状态向量，在状态的 差会随着时间而递增。为解决退化问题，一般有 初始分布p(xo)给定的情况下，通过状态转移概率 两种措施：1)增加采样数量，2)重采样)方法。 密度p(xx-)按照时间传播；为k时刻的观测 增加采样数量会相应地增加计算量，降低算法的 向量，在给定状态情况下可根据似然函数p() 运行效率。重采样的思想是舍弃权值较小的粒 产生。贝叶斯滤波分为预测阶段和更新阶段，预 子，繁殖权值较大的粒子。然而过度地重采样会 测阶段是通过系统状态模型预测下一个时刻系统 产生新的问题：由于大权值粒子被反复地选择， 状态的先验概率密度，更新阶段则是利用当前时 粒子多样性很快丧失，导致样本贫化问题。粒 刻的观测值修正先验概率密度，进而得到后验概 子滤波算法存在的另一个问题是要求在状态转移 率密度p(xo1),在目标跟踪中，所要求解的就是 过程中，进化后的粒子需要能够涵盖目标所有的 后验滤波概率密度p(x1)。 可能状态，否则跟踪的结果就会逐渐偏离目标的 假设k-1时刻的后验滤波概率密度p(x-1k-) 真实位置，导致跟踪失败。解决的方法一般有两 已知，贝叶斯估计估计的过程如下。 种：1)增加粒子数，显然这种方法会增加计算量， 1.1 导致算法的实时性降低；2)设计合适的状态转移 预测过程 方程，以提高每个粒子对于状态预测的准确率。 由px-k-)得到系统在k时刻状态的先验 智能群体（又称为群智能，swarm intelli- 滤波概率密度p(x): gence,SI)是一类仿生物行为计算技术，源于生物 p,x-i1k-i）=p(x-1,1k-1)p(-il1k-i)= p(xx-1)p(x) (2) 群体的行为规律。例如观察蚂蚁、蜜蜂、鸟类、鱼 等式两端对x-1积分，得到： 群等社会性群居动物可以发现，它们分工合作 各司其职像有思维有意识一样地筑巢、觅食。同 p(x)=p(xlx-1)p(x--)dx-1 (3) 时人们也观察到不同生物群体有着不同的行为特 式中：p(xxk-)为系统状态转移概率密度，由系统 征，例如，鱼群会向有食物源的地方聚集；蜂群在 状态模型所决定。 离开蜂巢寻找食物时会向周围分离；而蚁群则会 1.2更新过程 共同地搬动食物并排列运送至蚁巢。在对这些行 在获得k时刻的测量值后，根据贝叶斯公 为特征总结归纳后发现这些群体行为具有群集共 式更新先验滤波概率密度p(x51k-),得到后验滤 性©。动物的群集共性给人们解决新问题带来启 波概率密度p(x): 发，例如，Cheng等利用群智能优化分析大数 p4）=pEpp,p= 据，并设计出一个更加有效的数据分析算法； p(21k) p2k,21k-1) (4) Xia21利用群智能优化解决网络覆盖优化问题， pe1k-1,x)p(1k-i） p(221k-1) 提高了无线传感器网络(wireless sensor network) 若观测是相互独立的，则只与x相关，与 的网络覆盖率；Devi等)将群智能优化技术用于 k时刻之前的观测值无关，则式(4)可化简为 增强语音计算技术，相比于传统的梯度算法，提 高了语音系统的信噪比。 p()= pex)px1k-） (5) p(2x1k-1) 在目标跟踪中，后验概率估计的准确度直接 式中：p(x)为似然概率密度函数，由系统的观 影响到跟踪结果的精确度。因此，本文将贝叶斯 测方程决定。而p(k-1)为归一化常数： 滤波理论与智能群体优化算法结合，提出一种新 (6) 颖的智能群体优化滤波算法。相比于传统的粒子 p(51k-1)= p(lxe)p(x-)dxe
在目标跟踪中用于估计后验状态的最著名的 方法为粒子滤波算法 (particle filter，PF)。PF 算法 采用序贯蒙特卡洛方法 (sequential Monte Carlo methods，SMC)，采用一组样本 (即粒子) 近似表示 非线性系统的后验分布，再使用这一近似表示估 计系统的状态。与其他几种算法相比，PF 算法更 适用非线性系统，适用范围更广，实际效果也较 好。在当前主流的视觉跟踪算法中，如 L1APG 算 法 [3] 、CNT 算法[4] 和 IOPNMF 算法[5] 等皆是以粒 子滤波为框架的跟踪算法。然而粒子滤波算法无 法避免粒子退化[6] 现象，这是因为粒子权值的方 差会随着时间而递增。为解决退化问题，一般有 两种措施：1) 增加采样数量，2) 重采样[7] 方法。 增加采样数量会相应地增加计算量，降低算法的 运行效率。重采样的思想是舍弃权值较小的粒 子，繁殖权值较大的粒子。然而过度地重采样会 产生新的问题：由于大权值粒子被反复地选择， 粒子多样性很快丧失，导致样本贫化问题[8]。粒 子滤波算法存在的另一个问题是要求在状态转移 过程中，进化后的粒子需要能够涵盖目标所有的 可能状态，否则跟踪的结果就会逐渐偏离目标的 真实位置，导致跟踪失败。解决的方法一般有两 种：1) 增加粒子数，显然这种方法会增加计算量， 导致算法的实时性降低；2) 设计合适的状态转移 方程，以提高每个粒子对于状态预测的准确率。 智能群体（又称为群智能[ 9 ] , swarm intelligence，SI）是一类仿生物行为计算技术，源于生物 群体的行为规律。例如观察蚂蚁、蜜蜂、鸟类、鱼 群等社会性群居动物可以发现，它们分工合作、 各司其职像有思维有意识一样地筑巢、觅食。同 时人们也观察到不同生物群体有着不同的行为特 征，例如，鱼群会向有食物源的地方聚集；蜂群在 离开蜂巢寻找食物时会向周围分离；而蚁群则会 共同地搬动食物并排列运送至蚁巢。在对这些行 为特征总结归纳后发现这些群体行为具有群集共 性 [10]。动物的群集共性给人们解决新问题带来启 发，例如，Cheng 等 [11] 利用群智能优化分析大数 据，并设计出一个更加有效的数据分析算法； Xia[12] 利用群智能优化解决网络覆盖优化问题， 提高了无线传感器网络 (wireless sensor network) 的网络覆盖率；Devi 等 [13] 将群智能优化技术用于 增强语音计算技术，相比于传统的梯度算法，提 高了语音系统的信噪比。 在目标跟踪中，后验概率估计的准确度直接 影响到跟踪结果的精确度。因此，本文将贝叶斯 滤波理论与智能群体优化算法结合，提出一种新 颖的智能群体优化滤波算法。相比于传统的粒子 滤波算法，本文算法能够有效地应对粒子退化问 题，提高跟踪算法的准确度。 1 贝叶斯滤波理论 给定离散时间动态系统的状态空间模型 (dynamic state-space model，DSSM) 可描述为 { xk = f (xk−1 , vk−1) zk = h(xk ,nk) (1) f h vk ∈ R n nk ∈ R m xk p(x0) p(xk |xk−1) zk p(zk |xk) p(x0:k |z1:k) p(xk |z1:k) 式中： 和 分别为非线性的状态转移函数和观 测函数； 和 分别为系统的过程噪声 和观测噪声； 代表 k 时刻的状态向量，在状态的 初始分布 给定的情况下，通过状态转移概率 密度 按照时间传播； 为 k 时刻的观测 向量，在给定状态情况下可根据似然函数 产生。贝叶斯滤波分为预测阶段和更新阶段，预 测阶段是通过系统状态模型预测下一个时刻系统 状态的先验概率密度，更新阶段则是利用当前时 刻的观测值修正先验概率密度，进而得到后验概 率密度 ，在目标跟踪中，所要求解的就是 后验滤波概率密度 。 假设 k−1 时刻的后验滤波概率密度 p(xk−1|z1:k−1) 已知，贝叶斯估计估计的过程如下。 1.1 预测过程 p(xk−1|z1:k−1) p(xk |z1:k) 由 得到系统在 k 时刻状态的先验 滤波概率密度 ： p(xk , xk−1|z1:k−1) = p(xk |xk−1,z1:k−1)p(xk−1|z1:k−1) = p(xk |xk−1)p(xk−1 |z1:k−1) (2) 等式两端对 xk−1 积分，得到： p(xk |z1:k−1) = ∫ p(xk |xk−1)p(xk−1 |z1:k−1)dxk−1 (3) p(xk 式中： |xk−1) 为系统状态转移概率密度，由系统 状态模型所决定。 1.2 更新过程 zk p(xk |z1:k−1) p(xk |z1:k) 在获得 k 时刻的测量值 后，根据贝叶斯公 式更新先验滤波概率密度 ，得到后验滤 波概率密度 ： p(xk |z1:k) = p(z1:k |xk)p(xk) p(z1:k) p(zk ,z1:k |xk)p(xk) p(zk ,z1:k−1) = p(zk |z1:k−1 , xk)p(xk |z1:k−1) p(zk |z1:k−1) (4) 若观测是相互独立的，则 zk 只与 xk 相关，与 k 时刻之前的观测值无关，则式 (4) 可化简为 p(xk |z1:k) = p(zk |xk)p(xk |z1:k−1) p(zk |z1:k−1) (5) p(zk |xk) p(zk |z1:k−1) 式中： 为似然概率密度函数，由系统的观 测方程决定。而 为归一化常数： p(zk |z1:k−1) = ∫ p(zk |xk)p(xk |z1:k−1)dxk (6) ·698· 智 能 系 统 学 报 第 14 卷
第4期 许奇，等：用于目标跟踪的智能群体优化滤波算法 ·699· 2智能群体优化滤波算法 式中：w)=w/∑w)为归一化权值。 由以上推导可知，在贝叶斯滤波中，求得后验 贝叶斯滤波方法主要分为更新和预测两个阶 滤波概率密度之前，可以根据最新的观测信息， 段。更新的目的是为了利用最新观测值对先验滤 结合智能群体优化方法，通过粒子分层后，将权 波概率密度进行修正，得到后验滤波概率密度， 值较低的粒子移动到高似然区，即将粒子移动到 预测的目的则是根据当前状态预测下一时刻先验 权值更大的区域，再结合蒙特卡洛模拟产生可靠 滤波概率密度。由于式(3)和式(6)的积分难以 的重要性密度函数，进行重要性采样，即可估计 计算，所以按照经典蒙特卡洛模拟方法：将后验 出后验状态。 概率密度转化为累积概率密度分布，然后在区间 [0,1]中随机抽取N个数值，每个值对应一个目标 2.1粒子分层 状态，由此得到N个独立同分布的样本，i=1,2,…,N。 通过设定的阈值T,T将粒子集中，粒子依据 则后验滤波概率密度可以近似计算为 权值的大小来分层，从而可根据不同层中的粒子 数量来更新粒子的位置。可表示为 px1)≈ (7) ∈山a,w)≥T layer(x) ∈山m,Th>w(x)≥T (13) 然而实际应用时，真实的后验概率密度是无 ∈，t>w(x) 法知道的，因此通过CDF采集样本是不现实的。 2.2 粒子运动 这启发了我们可以结合实际情况有选择的采样， 群集共性表现在3个方面：内聚、分离和排 即结合智能群体优化方法，充分利用最新的观测 列。内聚运动时，各成员朝着一个平均的中心位 信息，将移动粒子至高似然区，得到可靠的建议 置进行聚合；分离运动时，各成员远离一个平均 分布作为重要性密度函数进行重要性采样4。假 的中心位置；排列运动时，各成员朝着一个平均 设经过智能群体优化后的建议分布为q(x),则 的方向共同运动，如图1所示。 根据蒙特卡洛模拟方法有： g() 6x-)w() (8) 其中： 内聚 分离 排列 wi(=()p() (9) 图1群集共性示意图 q(xFx) Fig.1 Sketch of swarm intelligence 为k时刻第ⅰ个粒子所对应的权值，由相应的观 2.2.1内聚运动 测模型的求出。则后验滤波概率密度： 根据已有粒子的权值，让权值较低的粒子移 p）=gpx_9上uwx (10) 动至权值较大的区域，从而产生更可靠的重要性 g(xk) p() 又因为： 密度函数。为了提高鲁棒性，粒子的移动方法如下： coh():=-1+(a+(b-a)Xrand)×(x-1-x)(14) p31)= p(1k,x)dx= 式中：为粒子在k时刻的位置状态；x-1为前一 pelp9d4≈ 时刻的位置状态；x为平均的中心位置，由相应 g) 的更新准则决定。rand为0~l随机数。a和b为 wi∫-0au= (11) 预设常数，其中a≤1≤b,b-a的值越小，内聚速 度越快，但粒子多样性越差，反之，b-a的值越 ∑ 大，内聚速度越慢，但粒子多样性越好。 2.2.2分离运动 联立式(8)、式(10)、式(11)，可得： 在当前时刻无法准确确定目标位置时，让所 w)i0-为 有粒子进行分离运动，目的是为了下一时刻能够 尽可能多地涵盖目标的可能状态。粒子的移动方 p(x1)= 法如下： (12) spa():x=-l+1××rand×(xe--i) (15) 式中：为粒子在k时刻的位置；-1为前一时刻 的位置；x为平均的中心位置，由相应的更新准 则决定；下为目标的平均位移；1为预设常数，可
2 智能群体优化滤波算法 x i k ,i = 1,2,··· ,N 贝叶斯滤波方法主要分为更新和预测两个阶 段。更新的目的是为了利用最新观测值对先验滤 波概率密度进行修正，得到后验滤波概率密度， 预测的目的则是根据当前状态预测下一时刻先验 滤波概率密度。由于式 (3) 和式 (6) 的积分难以 计算，所以按照经典蒙特卡洛模拟方法：将后验 概率密度转化为累积概率密度分布，然后在区间 [0，1] 中随机抽取 N 个数值，每个值对应一个目标 状态，由此得到N个独立同分布的样本 。 则后验滤波概率密度可以近似计算为 p(xk |z1:k) ≈ 1 N ∑N i=1 δ(xk − x i k ) (7) q(xk |z1:k) 然而实际应用时，真实的后验概率密度是无 法知道的，因此通过 CDF 采集样本是不现实的。 这启发了我们可以结合实际情况有选择的采样， 即结合智能群体优化方法，充分利用最新的观测 信息，将移动粒子至高似然区，得到可靠的建议 分布作为重要性密度函数进行重要性采样[14]。假 设经过智能群体优化后的建议分布为 ，则 根据蒙特卡洛模拟方法有： q(xk |z1:k) ≈ ∑N i=1 δ(xk − x i k )w ∗ k ( x i k ) (8) 其中： w ∗ k (x i k ) = p(z1:k |x i k )p(x i k ) q(x i k |z1:k) (9) 为 k 时刻第 i 个粒子所对应的权值，由相应的观 测模型[15] 求出。则后验滤波概率密度： p(xk |z1:k) = q(xk |z1:k)p(xk |z1:k) q(xk |z1:k) = q(xk |z1:k)w ∗ k (xk) p(z1:k) (10) 又因为： p(z1:k) = ∫ p(z1:k , xk)dxk = ∫ p(z1:k |xk)p(xk)q(xk |z1:k) q(xk |z1:k) dxk ≈ w ∗ k (xk) ∑N i=1 ∫ w ∗ k (x i k )δ(xk − x i k )dxk = w ∗ k (x i k ) ∑N i=1 w ∗ k (x i k ) (11) 联立式 (8)、式 (10)、式 (11)，可得： p(xk |z1:k) = w ∗ k (xk) ∑N i=1 w ∗ k (x i k )δ(xk − x i k ) w ∗ k (x i k ) ∑N i=1 w ∗ k (x i k ) = ∑N i=1 δ(xk − x i k )wk(x i k ) (12) wk(x i k ) = w ∗ k (x i k )/ ∑N i=1 w ∗ k (x i k 式中： ) 为归一化权值。 由以上推导可知，在贝叶斯滤波中，求得后验 滤波概率密度之前，可以根据最新的观测信息， 结合智能群体优化方法，通过粒子分层后，将权 值较低的粒子移动到高似然区，即将粒子移动到 权值更大的区域，再结合蒙特卡洛模拟产生可靠 的重要性密度函数，进行重要性采样，即可估计 出后验状态。 2.1 粒子分层 通过设定的阈值 τh，τl 将粒子集中，粒子依据 权值的大小来分层，从而可根据不同层中的粒子 数量来更新粒子的位置。可表示为 layer(xk) : x i k ∈ ψh, w ∗ k (x i k ) ⩾ τh x i k ∈ ψm, τh > w ∗ k (x i k ) ⩾ τl x i k ∈ ψl , τl > w ∗ k (x i k ) (13) 2.2 粒子运动 群集共性表现在 3 个方面：内聚、分离和排 列。 内聚运动时，各成员朝着一个平均的中心位 置进行聚合；分离运动时，各成员远离一个平均 的中心位置；排列运动时，各成员朝着一个平均 的方向共同运动，如图 1 所示。 内聚 分离 排列 图 1 群集共性示意图 Fig. 1 Sketch of swarm intelligence 2.2.1 内聚运动 根据已有粒子的权值，让权值较低的粒子移 动至权值较大的区域，从而产生更可靠的重要性 密度函数。为了提高鲁棒性，粒子的移动方法如下： coh(xk) : xk = xk−1 +(a+(b−a)×rand)×(xk−1 − xc) (14) xk xk−1 xc a ⩽ 1 ⩽ b b−a b−a 式中： 为粒子在 k 时刻的位置状态； 为前一 时刻的位置状态； 为平均的中心位置，由相应 的更新准则决定。rand 为 0~1 随机数。a 和 b 为 预设常数，其中 ， 的值越小，内聚速 度越快，但粒子多样性越差，反之， 的值越 大，内聚速度越慢，但粒子多样性越好。 2.2.2 分离运动 在当前时刻无法准确确定目标位置时，让所 有粒子进行分离运动，目的是为了下一时刻能够 尽可能多地涵盖目标的可能状态。粒子的移动方 法如下： spa(xk) : xk = xk−1 +λ×v¯ ×rand×(xc − xk−1) (15) xk xk−1 xc v¯ λ 式中： 为粒子在 k 时刻的位置； 为前一时刻 的位置； 为平均的中心位置，由相应的更新准 则决定； 为目标的平均位移； 为预设常数，可 第 4 期 许奇，等：用于目标跟踪的智能群体优化滤波算法 ·699·
·700· 智能系统学报 第14卷 取1≤1,1的值越大，分离程度越大，全局搜索能 计以下4条准则自适应地更新粒子状态。 力越强，但局部搜索能力越弱，相反，入的值越小， 准则1当高权值粒子集山中粒子数量较多 分离程度越小，全局搜索能力越差，但局部搜索 (length(wa)>threshold)时，表明在当前时刻，粒子集 能力越强。 能充分确认目标的位置状态，为理想的跟踪效 2.2.3排列运动 果。则根据GMMSE准则，计算出中心位置。在 排列运动目的是在当前时刻能够准确估计目 生成建议分布时，考虑到粒子多样性，保留高权 标位置的情况下，预测下一时刻目标位置。采用 值粒子和中权值粒子的位置状态，只对低权值粒 状态转移概率密度作为排列运动的运动模型，即 子集，中的粒子进行内聚运动。 x~p(xxk) (16) 准则2当高权值粒子集.中的粒子数量较 在实际运用于目标跟踪中，系统状态转移的 少但大于一个阈值(threshold>length(wa)>mpts>O), 运动模型有很多种，诸如匀速运动模型，自由漫 并且中权值粒子集山m中的粒子数量较多(length(wm)> 步运动模型和匀加速运动模型等。这里采用匀速 threshold)时，表明在当前状态下，跟踪效果良好， 运动模型，它的优点是计算简单高效： xk=xk-l+入x rand× 但高权值粒子的周围可能拥有更高的权值。则根 (17) 2.3状态估计 据LMMSE准则，对高权值粒子集山a里的粒子局 可根据最小均方误差(minimum mean squared 部加权，计算出中心位置。其中阈值mpts之所以 error,,MMSE)准则或极大后验(maximum A pos- 要大于0，是为了防止跟踪算法所提取的特征] terior,.MAP)准则，即将条件均值或具有极大后验 不能充分表示目标的状态，即可能出现极个别粒 概率密度的状态作为系统状态的估计值。MAP 子并不能表示目标位置状态，但是依据观测模型 准则计算公式为 所计算出的权值却较大。在生成建议分布时，保 arg max p(x)arg max wa(x) (18) 留中权值粒子的位置状态，只对低权值粒子集 中的粒子进行内聚运动。 式中：w(x)为粒子集中每个粒子对应的归一化 准则3当高权值粒子集山中的粒子数量较 权值。MMSE准则又分为以下两种： 少但大于一定阈值(threshold>length(wa)>mpts>0), I)局部最小均方误差(local minimum mean 并且中权值粒子集山m中的粒子数量较少(threshold> squared error,LMMSE)准则。 length(wm)时，则根据LMMSE准则，对高权值粒 通过设定一个范围R,计算该范围内的粒子 数M,在对目标状态后验估计时，仅对范围内的 子集里的粒子局部加权，计算出中心位置。在生 粒子样本进行加权求和，其计算公式为 成建议分布时，对中权值粒子集山m和低权值粒子 集，中的粒子同时进行内聚运动。 xxp(x)dx= (19) 准则4当高权值粒子集山中的粒子数量极 = 少(mpts>length(a),并且中权值粒子集山m中的 式中：w()为k时刻粒子集中第i个粒子对应的 粒子数量较多(length(wm)>threshold)时，表明此时 归一化权值。 跟踪效果一般，但是占据较多数量的中权值粒子 2)全局最小均方误差(global minimum mean 仍然可以近似表示目标的位置状态。则根据 squared error,,GMMSE)准则。 对总数为N的粒子集中所有粒子整体加权求 LMMSE准则，对中权值粒子集山m里的粒子局部 和.计算公式为 加权，计算出中心位置。在生成建议分布时，只 对低权值粒子集山，中的粒子进行内聚运动。 xp(x1k)dx= 20) 2.5状态预测 式中：w(x)为k时刻粒子集中第i个粒子对应的 预测的目的是为了下一时刻能更准确地估计 归一化权值。 目标的状态，即设计出合适的先验分布函数。在 2.4状态更新 SF算法中，遵循以下两条准则： 更新的目的是要充分利用当前时刻粒子的位 准则5若当前时刻满足更新准则的条件， 置和权值信息，找出目标最可能的状态，即生成 表明当前时刻能够判断目标的位置状态。则根 合适的建议分布，从而准确地估计目标在当前时 据GMMSE准则估计目标的后验状态，再将粒子 刻的位置。虽然权值较高的粒子比权值较低的粒 集进行排列运动预测下一时刻的先验状态。 子更能充分表示目标的位置状态，但当高权值粒 准则6若当前时刻不满足更新准则中的任 子数量较少时，容易陷入局部最优解。因此，设 条件，即当高权值粒子集山中的粒子非常少(mps>
λ ⩽ 1 λ λ 取 ， 的值越大，分离程度越大，全局搜索能 力越强，但局部搜索能力越弱，相反， 的值越小， 分离程度越小，全局搜索能力越差，但局部搜索 能力越强。 2.2.3 排列运动 排列运动目的是在当前时刻能够准确估计目 标位置的情况下，预测下一时刻目标位置。采用 状态转移概率密度作为排列运动的运动模型，即 xk ∼ p(xk |xk−1) (16) 在实际运用于目标跟踪中，系统状态转移的 运动模型有很多种，诸如匀速运动模型，自由漫 步运动模型和匀加速运动模型等。这里采用匀速 运动模型，它的优点是计算简单高效： xk = xk−1 +λ×rand×v¯ (17) 2.3 状态估计 可根据最小均方误差 (minimum mean squared error, MMSE) 准则或极大后验 (maximum A posterior，MAP) 准则，即将条件均值或具有极大后验 概率密度的状态作为系统状态的估计值。MAP 准则计算公式为 xˆ MAP k = argmax xk p(xk |z1:k) = argmax xk wk(xk) (18) 式中： wk(xk) 为粒子集中每个粒子对应的归一化 权值。MMSE 准则又分为以下两种： 1) 局部最小均方误差 (local minimum mean squared error，LMMSE) 准则。 通过设定一个范围 R，计算该范围内的粒子 数 M，在对目标状态后验估计时，仅对范围内的 粒子样本进行加权求和，其计算公式为 xˆ LMMSE k = ∫ xk p(xk |z1:k)dxk = ∑M i=1 ( x i kwk(x i k ) ) ∈ R (19) wk(x i k 式中： ) 为 k 时刻粒子集中第 i 个粒子对应的 归一化权值。 2) 全局最小均方误差 (global minimum mean squared error，GMMSE) 准则。 对总数为 N 的粒子集中所有粒子整体加权求 和，计算公式为 xˆ GMMSE k = ∫ xk p(xk |z1:k)dxk = ∑N i=1 x i kwk(x i k ) (20) wk(x i k 式中： ) 为 k 时刻粒子集中第 i 个粒子对应的 归一化权值。 2.4 状态更新 更新的目的是要充分利用当前时刻粒子的位 置和权值信息，找出目标最可能的状态，即生成 合适的建议分布，从而准确地估计目标在当前时 刻的位置。虽然权值较高的粒子比权值较低的粒 子更能充分表示目标的位置状态，但当高权值粒 子数量较少时，容易陷入局部最优解。因此，设 计以下 4 条准则自适应地更新粒子状态。 ψh (length(ψh) > threshold) ψl 准则 1 当高权值粒子集 中粒子数量较多 时，表明在当前时刻，粒子集 能充分确认目标的位置状态，为理想的跟踪效 果。则根据 GMMSE 准则，计算出中心位置。在 生成建议分布时，考虑到粒子多样性，保留高权 值粒子和中权值粒子的位置状态，只对低权值粒 子集 中的粒子进行内聚运动。 ψh (threshold > length(ψh) >mpts > 0) ψm (length(ψm) > ψh ψl 准则 2 当高权值粒子集 中的粒子数量较 少但大于一个阈值 ， 并且中权值粒子集 中的粒子数量较多 threshold) 时，表明在当前状态下，跟踪效果良好， 但高权值粒子的周围可能拥有更高的权值。则根 据 LMMSE 准则，对高权值粒子集 里的粒子局 部加权，计算出中心位置。其中阈值 mpts 之所以 要大于 0，是为了防止跟踪算法所提取的特征[15] 不能充分表示目标的状态，即可能出现极个别粒 子并不能表示目标位置状态，但是依据观测模型 所计算出的权值却较大。在生成建议分布时，保 留中权值粒子的位置状态，只对低权值粒子集 中的粒子进行内聚运动。 ψh (threshold > length(ψh) > mpts > 0) ψm length(ψm)) ψm ψl 准则 3 当高权值粒子集 中的粒子数量较 少但大于一定阈值 ， 并且中权值粒子集 中的粒子数量较少 (threshold > 时，则根据 LMMSE 准则，对高权值粒 子集里的粒子局部加权，计算出中心位置。在生 成建议分布时，对中权值粒子集 和低权值粒子 集 中的粒子同时进行内聚运动。 ψh (mpts > length(ψh)) ψm (length(ψm) > threshold) ψm ψl 准则 4 当高权值粒子集 中的粒子数量极 少 ，并且中权值粒子集 中的 粒子数量较多 时，表明此时 跟踪效果一般，但是占据较多数量的中权值粒子 仍然可以近似表示目标的位置状态。则根据 LMMSE 准则，对中权值粒子集 里的粒子局部 加权，计算出中心位置。在生成建议分布时，只 对低权值粒子集 中的粒子进行内聚运动。 2.5 状态预测 预测的目的是为了下一时刻能更准确地估计 目标的状态，即设计出合适的先验分布函数。在 SIF 算法中，遵循以下两条准则： 准则 5 若当前时刻满足更新准则的条件， 表明当前时刻能够判断目标的位置状态。则根 据 GMMSE 准则估计目标的后验状态，再将粒子 集进行排列运动预测下一时刻的先验状态。 ψh 准则 6 若当前时刻不满足更新准则中的任 一条件，即当高权值粒子集 中的粒子非常少 (mpts > ·700· 智 能 系 统 学 报 第 14 卷
第4期 许奇，等：用于目标跟踪的智能群体优化滤波算法 ·701· length(wa),并且中权值粒子的数量也较少(threshold> 2)fork=1,2,…,T length(也m),则根据极大后验准则估计目标的后验 3)由观测函数计算每个粒子的权值w()并 状态，并根据MAP准则确定中心位置，再对所有 分层：x4~layer(x) 粒子进行分离运动预测下一时刻的先验状态。 4)状态更新 2.6算法流程 if (length()>threshold) 本文算法的流程如图2所示，其具体实现步 a=∑) 骤如算法1所示。 elseif(length()>mpts 图像序列 &&length()>threshold) 立=∑（(n(》.e 第一帧 elseif(length()>mpts &&length()<threshold) 初始化 最后帧 a=∑m(),e 山m~coh(元) else 状态更新阶段 跟踪结束 计算所有粒子 a=∑(w(》e中 权值并归一化 endif ~coh() 粒子分层 5)重新计算粒子的权值w(x)并估计后验 状态： 根据更新准则 更新粒子状态 6)状态预测 if(length()<mpts 状态估计阶段 &&length()threshold) 重新计算粒子 x~spa() 权值并归一化 else x4~p(xx-1) endif 整体加权确定 7)endfor 当前帧的位置 注：A~B表示A从B中采样或A服从B的分布。 输出目标位置 3实验结果与分析 为了证明本文算法的理论可靠性和实际可行 性，分别进行了仿真实验和目标跟踪模拟实验， 状态预测阶段 实验平台为IntelCore3.2GHz,2GB内存，MAT- 根据预测准则 LAB2014a。 预测下一帧 3.1仿真模拟实验 为了说明智能优化滤波算法在非线性系统中 图2智能群体优化滤波算法流程 估计后验状态的性能，选择文献[16]中广泛使用 Fig.2 Algorithm flow of SIF 的一维非静态增长模型进行模拟仿真实验，此模 算法1智能群体优化滤波算法 型状态的后验分布具有双峰特征且非线性很强， 输入图像序列共T帧，初始位置： 是标准的验证模型。其状态空间模型定义如下： 输出跟踪位置。 (=f(-1,k)+V- 1)初始化：设定粒子数N,阈值为mpts, (21) threshold,threshold;~p(xo),i=1,2,....N 20+n
length(ψh)) length(ψm)) ，并且中权值粒子的数量也较少 (threshold > ，则根据极大后验准则估计目标的后验 状态，并根据 MAP 准则确定中心位置，再对所有 粒子进行分离运动预测下一时刻的先验状态。 2.6 算法流程 本文算法的流程如图 2 所示，其具体实现步 骤如算法 1 所示。 N N Y N 第一帧 初始化 最后帧 粒子分层 根据更新准则 更新粒子状态 计算所有粒子 权值并归一化 状态估计阶段 重新计算粒子 权值并归一化 整体加权确定 当前帧的位置 图像序列 跟踪结束 状态预测阶段 根据预测准则 预测下一帧 输出目标位置 状态更新阶段 图 2 智能群体优化滤波算法流程 Fig. 2 Algorithm flow of SIF 算法 1 智能群体优化滤波算法 输入 图像序列共 T 帧，初始位置； 输出 跟踪位置。 x i ∼ p(x0),i = 1,2,··· ,N 1) 初始化：设定粒子 数 N，阈值 为 mpts， threshold，threshold； 2) for k = 1,2,··· ,T wk(xk) xk ∼ layer(xk) 3) 由观测函数计算每个粒子的权值 并 分层： 4) 状态更新 if( length(ψh) > threshold) xˆk = ∑N i=1 x i kwk ( x i k ) elseif(length(ψh) > mpts &&length(ψm) > threshold) xˆk = ∑M i=1 ( x i kwk ( x i k ))x i k ,∈ ψh elseif(length(ψh) > mpts &&length(ψm) < threshold) xˆk = ∑M i=1 ( x i kwk ( x i k ))x i k ,∈ ψh ψm ∼ coh(xˆk) else xˆk = ∑M i=1 ( x i kwk ( x i k )), x i k ∈ ψm endif ψl ∼ coh(xˆk) 5) 重新计算粒子的权值 wk (xk) 并估计后验 状态： x˜k = ∑N i=1 x i kwk ( x i k ) 6) 状态预测 i f(length(ψh) < mpts &&length(ψm) < threshold) xk ∼ spa (x˜k) else xk ∼ p(xk |xk−1 ) endif 7) endfor 注： A ∼ B 表示 A 从 B 中采样或 A 服从 B 的分布。 3 实验结果与分析 为了证明本文算法的理论可靠性和实际可行 性，分别进行了仿真实验和目标跟踪模拟实验， 实验平台为 IntelCore3.2 GHz，2 GB 内存，MATLAB2014a。 3.1 仿真模拟实验 为了说明智能优化滤波算法在非线性系统中 估计后验状态的性能，选择文献 [16] 中广泛使用 的一维非静态增长模型进行模拟仿真实验，此模 型状态的后验分布具有双峰特征且非线性很强， 是标准的验证模型。其状态空间模型定义如下： xk = fk(xk−1, k)+vk−1 zk = x 2 k 20 +nk (21) 第 4 期 许奇，等：用于目标跟踪的智能群体优化滤波算法 ·701·