基于加强粒子群优化的粒子滤波目标跟踪方法

摘要

本发明公开了一种基于加强粒子群优化的粒子滤波目标跟踪方法，主要解决粒子滤波视频跟踪算法在跟踪过程中出现的粒子匮乏问题。其实现步骤是：1.在粒子滤波框架下，通过目标状态预测得到候选目标；2.通过提取候选目标的局部二值特征LBP统计直方图作为候选目标特征；3.通过计算候选目标特征与模板之间的距离，得到对应权值；4.通过加强粒子群优化算法对预测粒子进行优化；5.对优化后的粒子进行重采样；6.将重采样后的粒子进行融合得到目标的状态估计值，实现对目标的可靠跟踪。本发明能有效提高粒子对目标状态的描述能力，增加粒子多样性，解决了粒子滤波过程中的粒子匮乏问题，可用于智能视频监控、机器人导航、道路交通管制系统。

说明书

技术领域

本发明属于目标跟踪技术领域，特别涉及一种视频目标跟踪方法，可用于智能视频监控、机器人导航、道路交通管制系统。

背景技术

在视频跟踪研究中，基于粒子滤波的目标跟踪方法由于其在解决非线性问题方面的优异特性，以及相对开放的跟踪框架对各种特征描述方法的兼容能力，在视频跟踪中得到了广泛的应用。然而，粒子滤波算法在跟踪过程中会出现粒子匮乏现象，一旦出现粒子匮乏，粒子的多样性将大幅度降低，这将对跟踪算法的跟踪精度与计算效率造成很大的影响。因此，如何解决粒子滤波算法中的粒子匮乏问题，已成为视频跟踪研究中的难点。

粒子群优化PSO算法是Kennedy和Eberhart博士于1995年提出的,粒子群优化起源于对一个简单社会模型的仿真，从鸟类觅食行为模型中得到启示，并用于解决优化问题。.在粒子群优化算法中，每个优化问题的潜在解都是搜索空间中的一只鸟，称之为“粒子”。所有的粒子都有一个由优化函数决定的适应值，每个粒子还有一个决定它们转移方向和位移的速度。然后粒子们就追随当前的最优粒子在空间中搜索。粒子群优化算法能以较大的概率找到问题的全局最优解，且计算效率比传统随机方法高，一经提出立刻引起了演化计算领域研究者的广泛关注，并在短短几年时间里涌现出大量的研究成果，其中包括加强粒子群优化算法ELPSO、混合规划算法GAPSO等。

目前，典型的目标跟踪方法有：均值漂移，普通粒子滤波等，其中：

均值漂移方法，虽然简单易实现，计算量小，但因具有局部收敛特性容易陷入局部最优解而产生明显的跟踪滞后效应，对快速移动的大动态范围目标易产生失跟；

普通粒子滤波方法，其跟踪性能较大程度依赖于所用的粒子数，并且重采样过程中经过若干次迭代，所有粒子都趋向于同一个粒子，导致粒子的多样性丧失，粒子匮乏问题严重，使得对目标的状态进行估计有很大偏差，甚至导致跟踪失败，同时大部分粒子的权值将变得很小，使得大量的运算时间都浪费在权值较小的粒子上，降低了计算效率。

发明内容

本发明的目的在于针对上述已有技术中的不足，提出一种基于加强粒子群优化的粒子滤波目标跟踪方法，以解决粒子滤波算法在目标跟踪中出现的粒子匮乏问题，从而增加目标跟踪的精度，提高计算效率。

实现本发明的技术关键是：利用加强粒子群优化算法ELPSO对粒子滤波跟踪算法中的粒子进行优化，即在粒子滤波框架中，通过加强粒子群优化算法ELPSO优化粒子在状态空间中的分布，使得粒子分布趋向于高似然区域，从而提高粒子对目标状态的表达能力，增加粒子的多样性，解决粒子匮乏问题。其实现步骤包括如下：

(1)初始化：

(1a)读入k-1时刻的图像I_k-1，根据目标的初始状态X₀，初始化k-1时刻的粒子集其中，表示k-1时刻第i个粒子的状态区间，i为粒子序号，取值为1,2,…,N，N表示粒子总数，k表示时刻，初始时刻为k＝1；

(1b)初始化目标跟踪窗：B_k-1＝(r_k-1,c_k-1)^T，其中r_k-1和c_k-1分别表示k-1时刻目标跟踪窗的长度和宽度值，T表示向量转置运算；

(1c)初始化目标的局部二值特征LBP统计直方图M作为特征模板；

(2)目标状态预测：

(2a)读入k时刻的图像I_k，通过对k-1时刻粒子集的传递，得到k时刻预测粒子集其中为k时刻第i个粒子的状态预测值；

(2b)根据k时刻预测粒子集和目标跟踪窗B_k-1，确定k时刻候选目标集其中为k时刻第i个候选目标，表示以为中心、B_k-1为长宽所界定出的矩形区域；

(3)提取候选目标集中候选目标对应的特征集其中V_i表示第i个候选目标对应的特征；

(4)求取候选目标特征集与特征模板M之间的距离集并根据距离集计算候选目标的权值集其中d_i表示第i个候选目标特征与特征模板M之间的距离，ω_i表示第i个候选目标的权值；

(5)粒子群优化：

(5a)初始化待优化粒子集个体最优值p_id＝R_i、群体最优值p_gd＝R_max和迭代次数T＝1，设置最大迭代次数T_max，其中对应的速度集为权值集为R_max为中权值最大的粒子，其对应权值为ω_max；

(5b)判断迭代次数T是否满足T＜＝T_max，若是，从步骤(5c)开始进行第T次迭代，否则，直接转到步骤(6)；

(5c)根据个体最优值p_id和群体最优值p_gd将待优化粒子集中每一个粒子R_i进行优化得到优化粒子Q_i，并组成优化粒子集优化粒子集

(5d)更新优化粒子集中每一个优化粒子Q_i对应的权值ω_i，并更新个体最优值p_id；

(5e)更新群体最优值p_gd：

(5f)通过增强搜索，对群体最优值p_gd进行更新；

(5h)判断迭代次数T是否满足T＞T_max，若是，则粒子群优化结束，否则，令T＝T+1、令待优化粒子集其对应权值集为并返回步骤(5b)；

(6)对候选目标的权值集进行归一化，并根据归一化后的结果对k时刻优化粒子集进行重采样，得到k时刻的粒子集其中表示k时刻第i个粒子的状态区间；

(7)根据k时刻的粒子集估计k时刻的目标状态X_k，并确定k时刻的目标估计范围Target；

(8)检查下一时刻的信息是否到达，若是，令k＝k+1，返回步骤(2)，否则，目标跟踪过程结束。

本发明由于利用加强粒子群优化算法ELPSO对粒子滤波过程中的粒子进行优化，从而增强了粒子对目标状态的描述能力，增加了粒子的多样性，解决了粒子匮乏问题；同时由于增强了粒子对目标状态的描述能力，因而在跟踪中可以用更少的粒子对目标进行准确描述，从而提高了计算效率。

附图说明

图1是本发明的整体流程图；

图2是用本发明及现有方法对行人视频序列进行跟踪的实验结果图；

图3是用本发明及现有方法对红外行人视频序列进行跟踪的实验结果图；

图4是用本发明及现有方法对玩具视频序列进行跟踪的实验结果图。

具体实施方式

参照图1，本发明的具体实施过程包括以下步骤：

步骤1.初始化。

1.1)令初始时刻k＝1，根据目标的初始状态X₀，初始化k-1时刻的粒子集

1.1.1)根据目标的初始状态X₀，产生k-1时刻第i个粒子其中，i为粒子序号，取值为1,2,…,N，N表示粒子总数，服从均值为X₀方差为Ψ的高斯分布，X₀为目标的初始状态，Ψ为过程噪声方差；

1.1.2)用步骤1.1.1)所得的N个粒子，组成粒子集

${\left\{S_{k-1}^i\right\}}_{i=1}^N=\{S_{k-1}^1,S_{k-1}^2,\mathrm{...},S_{k-1}^3,\mathrm{...},S_{k-1}^N\};---<1>$

1.2)初始化目标跟踪窗：B_k-1＝(r_k-1,c_k-1)^T，其中r_k-1和c_k-1分别表示k-1时刻目标跟踪窗的长度和宽度值，T表示向量转置；

1.3)初始化目标的局部二值特征LBP统计直方图M作为特征模板。

步骤2.目标状态预测。

2.1)读入k时刻的图像I_k，通过对k-1时刻图像中粒子集的传递，得到k时刻的预测粒子集

${\left\{q_k^i\right\}}_{i=1}^N=\{q_k^1,q_k^2,\mathrm{...},q_k^i,\mathrm{...},q_k^N\},---<2>$

其中表示k时刻第i个预测粒子，其通过对k-1时刻第i个粒子传递得到，传递公式如下：

$q_k^i=S_{k-1}^i+w^i,---<3>$

其中，wⁱ为状态噪声，服从均值为方差为Ψ的高斯分布；

2.2)根据k时刻的预测粒子集和目标跟踪窗B_k-1，确定k时刻候选目标集

${\left\{q_k^i\right\}}_{i=1}^N=\{q_k^1,q_k^2,...,q_k^i,...,q_k^N\},---<4>$

其中表示k时刻第i个预测粒子对应的候选目标，其确定公式如下：

$P_k^i=\left\{(x,y)\right||x-{\upsilon }_k^i|\le \frac{r_{k-1}}{2},|y-{\nu }_k^i|\le \frac{c_{k-1}}{2}\},---<5>$

其中，和分别表示k时刻第i个预测粒子的横坐标和纵坐标，r_k-1和c_k-1分别表示k-1时刻目标跟踪窗B_k-1的长度和宽度值。

步骤3.提取候选目标特征集。

常用的目标特征有灰度特征、颜色特征、纹理特征、形状特征等。

现有的提取目标特征的方法中针对颜色特征的提取方法有颜色直方图法、颜色矩法、颜色相关图法等；针对纹理特征的提取方法有局部二值特征LBP统计直方图法、梯度法、灰度共生矩阵法、自回归纹理模型法、小波变换法等；针对形状特征的提取方法有边界特征法、傅里叶形状描述符法、几何参数法等。

本实例使用但不限于现有方法中的局部二值特征LBP统计直方图法作为目标特征，其步骤如下：

3.1)计算候选目标集中每一个候选目标各个像素点的局部二值特征LBP值：

${\mathrm{LBP}}_i\left(P_c\right)=\underset{n=0}{\overset{p-1}{\Sigma }}[s(g_n-g_c)·2^n],---<6>$

其中，g_c代表中心点p_c的灰度值，g_n代表中心点p_c的邻域像素点的灰度值，p表示中心像素点周围邻域内的p个像素点，n为p个像素点的序号，s(g_n-g_c)是一个函数，其表示形式为：

$s(g_n-g_c)=\left(\begin{array}{cc}1,& g_n-g_c\ge 0\\ 0,& g_n-g_c<0\end{array}\right);---<7>$

3.2)根据步骤3.1)中所得的结果，计算候选目标集中各个候选目标的局部二值特征LBP统计直方图V_i：

$V_i=h_i\left(u\right)=\underset{x,y}{\Sigma }I\left(f\right(x,y)=1),u=0,1,\mathrm{...},m-1,---<8>$

其中，m代表局部二值特征LBP的编码长度，m＝2^p，I(f(x,y)＝i)是一个函数，其表示形式为：

$I\left(f\right(x,y)=i)=\{\begin{array}{cc}1,& f(x,y)=i\\ 0,& f(x,y)\ne i\end{array};---<9>$

3.3)用步骤3.2)中所求的N个候选目标的特征，组成候选目标特征集

${\left\{V_i\right\}}_{i=1}^N=\{V_1,V_2,...,V_i,...V_N\}.---<10>$

步骤4.计算权值集。

4.1)计算候选目标特征集与特征模板M之间的距离集

${\left\{d_i\right\}}_{i=1}^N=\{d_1,d_2,...,d_i,...d_N\},---<11>$

其中d_i表示第i个候选目标特征与特征模板之间的距离，ρ_i是第i个候选目标特征与特征模板的之间的巴氏系数，

4.2)根据距离集计算候选目标权值集

${\left\{{\omega }_i\right\}}_{i=1}^N=\{{\omega }_1,{\omega }_2,...,{\omega }_i,...{\omega }_N\},---<12>$

其中ω_i表示第i个候选目标的权值，其计算公式为：

${\omega }_i=\frac{1}{\sqrt{2\pi R}}\exp \{-\frac{{\left(d_i\right)}^2}{2R}\},---<13>$

其中，d_i表示第i个候选目标特征与特征模板之间的距离，R为特征观测噪声方差。

步骤5.粒子群优化。

5.1)初始化待优化粒子集个体最优值p_id＝R_i、群体最优值p_gd＝R_max、迭代次数T＝1，设置最大迭代次数T_max，其中对应的速度集为权值集为R_max为中权值最大的粒子，其对应的权值为ω_max；

5.2)判断迭代次数T是否满足T＜＝T_max，若是，从步骤5.3)开始进行第T次迭代，否则，直接转到步骤6；

5.3)根据个体最优值p_id和群体最优值p_gd将待优化粒子集中每一个粒子R_i进行优化得到优化粒子Q_i，并组成优化粒子集优化粒子集

5.3.1)更新待优化粒子集中粒子R_i的速度v_i：

v_i＝w·v_i+c₁·r₁·(p_id-R_i)+c₂·r₂·(p_gd-R_i)，>

其中，w为惯性权值，c₁为与个体最优值有关的学习因子，c₂为与全局最优值有关的学习因子，r₁和r₂为(0,1)之间两个不同的随机数；

5.3.2)用步骤5.3.1)得到的速度v_i更新待优化粒子集中的粒子R_i,得到优化粒子Q_i：

Q_i＝R_i+v_i；>

5.3.3)用步骤5.3.2)得到的N个优化粒子组成优化粒子集

${\left\{Q_i\right\}}_{i=1}^N=\{Q_1,Q_2,...,Q_i,...,Q_N\},---<16>$

其对应的权值集为

5.4)更新优化粒子集中每一个优化粒子Q_i对应的权值ω_i，并更新个体最优值p_id：

5.4.1)计算优化粒子Q_i的临时权值ω_new：

${\omega }_{new}=\frac{1}{\sqrt{2\pi R}}\exp \{-\frac{{\left(d_{new}\right)}^2}{2R}\},---<17>$

其中d_new表示优化粒子Q_i对应的候选目标特征与特征模板之间的距离；

5.4.2)根据步骤5.4.1)得到的临时权值ω_new更新优化粒子Q_i对应的权值ω_i，并更新个体最优值p_id：

如果ω_new＞ω_i，则更新优化粒子Q_i对应权值ω_i＝ω_new，更新个体最优值p_id＝Q_i，否则ω_i值不变，p_id值不变；

5.5)更新群体最优值p_gd：

如果优化粒子Q_i对应权值ω_i满足ω_i＞ω_max，则更新群体最优值p_gd＝Q_i，其对应的权值ω_max＝ω_i，否则p_gd值不变，其对应权值ω_max不变；

5.6)通过增强搜索，对群体最优值p_gd进行更新：

5.6.1)对群体最优值p_gd进行第一步搜索，得到一次搜索结果p_g1：

p_g1＝p_gd+(X_max-X_min)·Gaussin(0,h)，>

其中，X_max代表决策向量的上界，X_min代表决策向量的下界，Gaussin(0,h)是一个均值为零，标准差为h的高斯分布，h根据规律h＝h-_{1/Tmax做线性递减；}

5.6.2)对群体最优值p_gd进行第一次更新：

如果p_g1对应的候选目标的权值ω_g1满足ω_g1＞ω_max，则更新群体最优值p_gd＝p_g1，其对应权值ω_max＝ω_g1，否则p_gd值不变，其对应权值ω_max不变；

5.6.3)对群体最优值p_gd进行第二步搜索，得到二次搜索结果p_g2：

p_g2＝p_gd+(X_max-X_min)·Cauchy(0,s)，>

其中Cauchy(0,s)是一个峰值参数为零，尺度参数为s的柯西分布，s根据规律s＝s-1/T_max做线性递减；

5.6.4)对群体最优值p_gd进行第二次更新：

如果p_g2对应的候选目标的权值ω_g2满足ω_g2＞ω_max，则群体最优值p_gd＝p_g2，其对应权值ω_max＝ω_g2，否则p_gd值不变，其对应权值ω_max不变；

5.7)令T＝T+1，令待优化粒子集其对应权值集为并返回步骤5.2)。

步骤6.重采样。

现有的重采样方法有多项式重采样、系统重采样、残差重采样等，本实例使用但不限于现有方法中系统重采样方法对优化粒子集进行重采样，其步骤如下：

6.1)对候选目标的权值集进行归一化，得到归一化后的权值集

${\left\{{\omega }_i^{\prime }\right\}}_{i=1}^N=\{{\omega }_1^{\prime },{\omega }_2^{\prime },...,{\omega }_3^{\prime },...{\omega }_N^{\prime }\}---<20>$

其中，ω_i'为ω_i对应的归一化结果，

6.2)根据步骤6.1)得到的归一化后的权值集对k时刻优化粒子集进行重采样，得到k时刻的粒子集其中表示k时刻第i个粒子的状态区间。

步骤7.目标状态更新。

7.1)根据k时刻的粒子集估计k时刻的目标状态X_k：

$X_k=\frac{1}{N}\underset{i=1}{\overset{N}{\Sigma }}{S}_k^i,---<21>$

其中，N表示粒子总数，表示k时刻第i个粒子的状态估计值；

7.2)根据k时刻的目标状态X_k和目标跟踪窗B_k，确定k时刻的目标估计范围Target：

$T\arg et=\left\{(x,y)\right||x-x_k|\le \frac{r_k}{2},|y-y_k|\le \frac{c_k}{2}\},---<22>$

其中，x_k和y_k分别表示k时刻目标状态X_k的横坐标和纵坐标，r_k和c_k分别表示k时刻目标跟踪窗的长度和宽度值。

步骤8检查下一时刻的信息是否到达，若是，则令k＝k+1，返回步骤2，否则，目标跟踪过程结束。

本发明的效果可通过以下仿真实验进一步说明：

1.仿真条件。

仿真环境：计算机采用Intel Pentium D CPU 2.8Ghz，1GB内存，软件采用Matlab7.4仿真实验平台。

2.仿真方法：本发明方法、现有的均值漂移方法、普通粒子滤波方法。

3.仿真内容与结果。

仿真1：用所述三种方法，对行人视频序列进行跟踪，结果如图2所示，其中：

图2(a)为用本发明对行人视频序列第27、39、86帧进行跟踪的结果图；

图2(b)为用均值漂移方法对行人视频序列第27、39、86帧进行跟踪的结果图；

图2(c)为用普通粒子滤波方法对行人视频序列第27、39、86帧进行跟踪的结果图。

从图2中可以看出，本发明在出现部分遮挡情况下，跟踪效果优于方法2和方法3。

仿真2：用所述三种方法，对红外行人视频序列进行跟踪，结果如图3所示，其中：

图3(a)为用本发明对红外行人视频序列第45、57、69、81帧进行跟踪的结果图；

图3(b)为用均值漂移方法对红外行人视频序列第45、57、69、81帧进行跟踪的结果图；

图3(c)为用普通粒子滤波方法对红外行人视频序列第45、57、69、81帧进行跟踪的结果图。

从图3中可以看出，在目标遇到相似背景时，方法2出现误跟，本发明跟踪结果明显优于方法3。

仿真3：用所述三种方法，对玩具视频序列进行跟踪，结果如图4所示，其中：

图4(a)为用本发明对玩具视频序列第21、26、30、32帧进行跟踪的结果图；

图4(b)为用均值漂移方法对玩具视频序列第21、26、30、32帧进行跟踪的结果图；

图4(c)为用普通粒子滤波方法对玩具视频序列第21、26、30、32帧进行跟踪的结果图。

从图4中可以看出，在目标进入复杂背景时，本发明跟踪效果明显优于方法2和方法3。

对图2～图4中的场景分别进行100次蒙特卡罗实验，统计平均跟踪误差Err和平均每帧运行时间RT，结果如表1所示：

表1

由表1中的统计数据可以看出：在跟踪误差方面，本发明对三组视频序列的跟踪结果比均值漂移方法分别降低了21％、76％和19％，比普通粒子滤波方法分别降低了42％、64％和85％；在 运行时间方面，由于本发明增加了粒子对目标的描述能力，可以用较少的粒子实现较准确地跟踪，因此比普通粒子滤波方法分别降低了36％、24％和25％，均值漂移方法用时最少。

综上可以得出，虽然均值漂移方法用时最少，但在复杂情况下无法实现对目标的准确跟踪，而本发明在跟踪精度和运行时间方面均优于普通粒子滤波方法。