自适应粒子群优化粒子滤波运动目标跟踪方法

摘要

本发明公开了一种自适应粒子群优化粒子滤波运动目标跟踪方法，属于图像处理与智能视频监控技术领域。本发明方法在用粒子滤波方法进行运动目标的跟踪过程中，利用粒子群优化方法对粒子的位置进行优化；在利用粒子群优化方法对粒子的位置进行优化时，根据全局最优粒子的位置变化情况对粒子的数量进行自适应调整。相比现有技术，本发明不但可有效减轻粒子群优化中的局部最优现象，提高目标跟踪的准确度，同时又具有算法复杂度低，实时性好的优点。

说明书

技术领域

本发明涉及一种运动目标跟踪方法，尤其涉及一种自适应粒子群优化粒子滤波运动 目标跟踪方法，属于图像处理与智能视频监控技术领域。

背景技术

运动目标跟踪是图像处理和智能视频监控技术领域研究的热点，也是机器人导航、 精确制导等领域的关键技术，具有广泛应用。例如：捕获实验中目标运动的轨迹和姿态， 对交通公路流量的检测，重要场合的视频监控和分析等。因此，运动目标的跟踪具有非 常重要的研究意义。运动目标的跟踪包括目标的检测、特征提取以及匹配跟踪等几个部 分技术组成。其中，目标的检测、目标的特征提取需要一定的先验知识，然后再根据一 定的算法，利用之前的已知信息预测下一时刻目标运动信息(位置、速度等)，实现运 动目标跟踪。一个良好的跟踪算法应该具有可靠性高、实时性好、准确性精确等特性。

关于运动目标的跟踪已经提出了很多有效的算法，其中，建立在卡尔曼滤波理论基 础上的目标跟踪技术受到了很大关注。但是卡尔曼滤波只适用于线性系统，为此， Sunahara、Buey等人将卡尔曼滤波进一步应用到非线性领域并提出扩展卡尔曼滤波 (EKF)，但是这种方法运算复杂度大大增加了，因此现实中没有得到广泛应用。另一 类常用的方法是均值漂移算法——Mean-shift算法[D.Comaniciu,V.Ramesh and P.Meer, "Real-time tracking of non-rigid objects using Mean Shift",Proceedings of IEEE Computer  Society Conference on Computer Vision and Pattern Recognition,2:142-149,2000]，它是一 类基于核函数的无参数估计算法，不需要先验知识，而且收敛速度比较快，但是对于快 速运动和非高斯噪声环境下有局限性。粒子滤波(PF:Particle Filtering)算法近年来在 目标跟踪领域越来越受到重视，它既不受限于线性系统，也不要求噪声服从高斯分布， 而且在目标出现遮挡时也可以实现可靠跟踪。但是，粒子滤波存在粒子贫化和计算量大 的问题是实际应用的重要障碍。

为了解决粒子滤波运动目标跟踪所存在的粒子贫化的问题，很多学者选择将粒子群 优化算法(Particle Swarm optimization，简称PSO)应用到粒子滤波当中，形成粒子群 优化粒子滤波算法(简称PSOPF)，从而使得粒子的多样性得以保障，但是现有PSOPF 算法中粒子群优化算法容易使得粒子陷入局部最优点，从而导致对目标的位置信息定位 不够准确。

针对该问题，一些自适应粒子群优化粒子滤波算法被提出，例如，有研究者提出一 种新型邻域自适应调整的动态粒子群优化粒子滤波算法.该算法考虑了粒子的邻域信息, 利用多样性因子、邻域扩展因子和邻域限制因子共同对粒子的邻域粒子数量进行自适应 调整，控制粒子对邻域的影响,减轻局部最优现象，达到收敛速度和寻优能力的最佳平 衡；也有研究者提出对各粒子赋予不同的权值，并在迭代过程中对粒子权值进行自适应 调整。这些方法虽然不同程度地能够解决PSOPF算法中粒子群优化算法容易使得粒子 陷入局部最优点的问题，但均存在算法复杂、计算量大的不足，运动目标跟踪的实时性 难以令人满意。

发明内容

本发明所要解决的技术问题在于克服现有粒子群优化粒子滤波运动目标跟踪技术 所存在的定位不够准确、计算量较大的不足，提供一种自适应粒子群优化粒子滤波运动 目标跟踪方法，在准确提高运动目标跟踪准确度的同时，其计算复杂度更低，目标跟踪 实时性更好。

本发明具体采用以下技术方案：

自适应粒子群优化粒子滤波运动目标跟踪方法，在用粒子滤波方法进行运动目标的 跟踪过程中，利用粒子群优化方法对粒子的位置进行优化；在利用粒子群优化方法对粒 子的位置进行优化时，根据全局最优粒子的位置变化情况对粒子的数量进行自适应调 整，具体如下：如全局最优粒子的位置在连续M1次迭代中始终变化，则减少粒子数量； 如全局最优粒子的位置在连续M2次迭代中始终不变，则增加粒子数量；M1、M2为预 设的大于等于3的整数。

M1与M2可以相等也可以不等。

相比现有技术，本发明具有以下有益效果：

本发明将自适应粒子群优化(APSO)技术与粒子滤波(PF)相结合，对运动目标 进行跟踪，可有效克服粒子贫化现象，并进一步在利用粒子群优化方法对粒子的位置进 行优化时，根据全局最优粒子的位置变化情况对粒子的数量进行自适应调整，从而可有 效减轻粒子群优化中的局部最优现象，提高目标跟踪的准确度，同时又具有算法复杂度 低，实时性好的优点。

附图说明

图1为粒子滤波算法的基本流程示意图；

图2为粒子群优化算法的基本流程示意图；

图3为本发明自适应粒子群优化粒子滤波运动目标跟踪方法的流程示意图；

图4为分别采用本发明方法和传统粒子滤波方法对Browse1视频序列进行运动目标 跟踪的效果对比。

具体实施方式

下面结合附图对本发明的技术方案进行详细说明：

本发明的思路是针对现有粒子群优化粒子滤波运动目标跟踪技术所存在的定位不 够准确、计算量较大的不足，对其进行改进，即在利用粒子群优化方法对粒子的位置进 行优化时，根据全局最优粒子的位置变化情况对粒子的数量进行自适应调整：在粒子迭 代更新的过程中，全局最优点如果连续多次都更新，则说明当前粒子群处于不断开发新 的状态的过程，此时适当减少粒子数目；反之，如果全局最优点连续多次都没有更新， 此时粒子群处于一个收敛的状态，有可能陷入局部最优点而无法跳出来，即目标位置有 可能跟踪的不准确，这时候需要增加粒子数目，从而帮助粒子群跳出这个点，扩展搜索 的范围。

为了便于公众理解本发明的技术方案，下面首先对本发明所涉及的粒子滤波及粒子 群优化技术进行简单介绍。

图1显示了粒子滤波算法的基本流程。粒子滤波(PF:Particle Filtering)的思想是 基于蒙特卡罗方法，利用粒子集来表示概率的问题，可以用在任何形式的空间模型上。 它的核心思想是通过从后验概率中抽取随机状态的粒子来表达它的分布，是一种顺序重 要性采样方法。简单来说，就是通过寻找一组在状态空间传播的随机样本对概率密度函 数进行近似，以样本均值来代替积分的运算，从而获得使状态实现最小方差分布的过程。

一般情况下，粒子滤波的状态空间模型可以描述为：

x_k＝f(x_k-1)+u_k-1

y_k＝h(x_k)+w_k

x_k为系统在k时刻的状态值，y_k为系统状态x_k的量测值，u_k-1,w_k分别为非线性系 统的过程噪声和量测噪声值。

粒子滤波目标跟踪的基本步骤如下：

1.初始化：初始跟踪帧k，然后根据先验分布p(x_k)，采样初始粒子集

2.For k＝1,2,...

a)重要性采样：从建议分布采样粒子集，

b)重要性加权：

重要性加权公式为：

$w_t^i=w_{t-1}^i\frac{p\left(y_t\right|x_t^i)p\left(x_t^i\right|x_{t-1}^i)}{q\left(x_t^i\right|x_{t-1}^i,y_t)},$

再接着对粒子的权重进行归一化即：

$w_t^i=\frac{w_t^i}{\underset{j=1}{\overset{N}{\Sigma }}{w}_t^j}$

c)重采样：如果N_eff＜N_th则进行重采样对于从而得到新的粒子集：如果不满足条件则不需要进行重采样步骤。

3.状态的估计：有了粒子的位置和权重，就可以估计目标的位置了。

4.接下来判断是不是结束帧，如果是则跟踪结束，如果不是则进入下一个状态的 跟踪过程，转到步骤2。

图2表示了粒子群优化算法的基本框架。粒子群优化(Particle Swarm Optimization， PSO)中所有粒子都有一个被优化的函数决定的适应值，每个粒子有一个速度决定他们 飞翔的方向和位置。然后所有粒子都趋向于当前的最优粒子靠近。PSO通过初始化一 群随机粒子，然后通过跟踪当前粒子极值和全局极值点来不断迭代更新自己。具体步骤 为：首先选定种群规模N，将第i个粒子表示为一个N维的向量 x_i＝(x_i1,x_i2,...,x_iN),i＝1,2,...,m,即第i个粒子在N维搜索空间中的位置为x_i将其带入目标 函数就可以计算其适应值，从而衡量出x_i的优劣。第i个粒子的速度也是一个N维的 向量，记为v_i＝(v_i1,v_i2,...,v_iN),速度决定了自理在搜索空间中收敛的速度。第i个粒子迄 今搜索到的最优位置为p_i＝(p_i1,p_i2,...,p_iN),整个粒子群迄今搜多到的最优点为 p_g＝(p_g1,p_g2,...p_gN)。

接着根据方程来更新粒子的速度和位置：

v_i＝w*v_i+c1*rand1*(p_i-x_i)+c2*rand2*(p_g-x_i)

x_i+1＝x_i+v_i

更新粒子的位置以后，不断来更新当前粒子的最优点和全局最优点。再一次迭代结 束以后需要根据最新的目标估计状态来判定当前目标状态的最适应值是否满足条件，如 果满足则跳出迭代过程，结束寻找最优点过程，否则继续迭代。

虽然粒子滤波算法可以解决非线性非高斯的问题，但是该算法仍然存在一些问题。 其中最主要的是需要用大量的样本数量才能很好地接近系统的后验概率密度，因此计算 量也就很大，而且重采样阶段会造成样本有效性和多样性的损失，导致样本的贫化现象。 对于粒子群优化来说经常会遇到对于多峰值问题粒子陷入局部最优点无法跳出来的问 题，因此无法得到全局最优点，进而影响跟踪效果。因此本发明将两者结合起来，同时 在粒子群优化过程中全局最优粒子的位置变化情况对粒子的数量进行自适应调整，从而 一方面克服了传统粒子滤波方法计算量大、粒子贫化的问题，另一方面克服了陷入局部 最优所导致的跟踪结果不准确问题。同时，相比现有各种自适应粒子群优化粒子滤波算 法，例如，现有的邻域自适应调整的动态粒子群优化粒子滤波算法需要计算多样性因子、 邻域扩展因子和邻域限制因子来对粒子的邻域粒子数量进行自适应调整，本发明方法仅 需要根据迭代过程中全局最优值的连续更新情况即可实现粒子数的自适应调整，其计算 复杂度更低，实时性更好。

图3为本发明自适应粒子群优化粒子滤波运动目标跟踪方法的基本流程示意图，其 具体算法流程如下：

首先读入视频序列初始帧k帧，选定要跟踪的目标，并对选取的区域建立基于颜色 信息的颜色直方图特征p(x_k)，初始化系统跟踪的方程，粒子数目N，跟踪过程中噪声R_k， 并且粒子的初始位置是服从以初始化的目标区域的几何中心为中心的高斯函数分布。

状态转移：当视频序列运动到下一帧时刻，根据设定的参数，粒子运动到某一位置， 然后根据第i个粒子的位置计算当前粒子的颜色信息直方图为通过计算其与初 始帧的颜色直方图特征的巴氏距离得到两者之间的相似度关系，进而得到当前粒子的权 重，对N个粒子统计以后需要进行权值归一化，并根据权重和位置关系得 到预测的目标位置。

再接着就进入到自适应粒子群优化的步骤中：

初始化跳出粒子群优化的迭代次数阈值T_m。之后根据粒子群优化的速度和位置方 程来不断更新粒子的速度和位置，这里极值p是否进行更新，是根据巴氏距离的函数结 果来判定的，如果相似度高，则相应的极值就进行更新。p_i是当前粒子i的个体极值， p_g为整个粒子群的全局极值。每次粒子都更新以后需要重新判定看预测的目标位置与 初始的目标相似度是否达到设定阈值，如果达到阈值则可以跳出粒子群优化过程，如果 迭代T_m次都没有达到，也跳出粒子群优化的过程。

预先设定两个大于等于3的整数M1、M2，如果在不断迭代更新的过程中，全局最 优点p_g连续M1次迭代都更新，则说明当前粒子群处于不断开发新的状态的过程，则 适当的减少粒子数目，例如将粒子数目减1；反之，如果全局最优点连续M2次迭代都 没有更新，此时粒子群处于一个收敛的状态，有可能陷入局部最优点而无法跳出来，即 目标位置有可能跟踪的不准确，这时候需要增加粒子数目，例如将粒子数目加1，从而 帮助粒子群跳出这个点，扩展搜索的范围，当满足粒子估计状态阈值以后或者满足最大 迭代次数阈值以后即跳出粒子群优化过程。M1和M2的值可根据实际情况设定，两者 可以相同也可以不同，本实施例中两者的值相同，均为T。

跳出自适应粒子群优化以后：

需要对粒子重新计算权重，并对权重进行归一化的处理。

状态的估计：根据粒子的位置和权重，估计目标的位置。并将估计目标位置显示出 来，以便识别。接下来判断是不是结束帧，如果是则跟踪结束，如果不是则进入下一个 状态的跟踪过程，转到状态转移步骤。

根据以上描述可以看出，在本发明的自适应粒子群优化粒子滤波算法中，重采样是 不需要的，因为经过粒子群优化以后粒子都趋向于最优点的位置，不会出现权重集中在 某几个粒子的上面。

为了验证本发明的效果，进行了以下验证实验：选取三段不同的视频序列 (Browse1,Fight_RunAway1来源于http://homepages.inf.ed.ac.uk/rbf/CAVIARDATA1, Aircraft为常用的飞机跟踪序列)，分别采用200个粒子的粒子滤波算法和30个粒子本 发明方法对其进行目标跟踪，并进行跟踪处理的时间统计(即平均处理一帧所花费的时 间)。所得到的实验结果如表1所示，其中PF表示粒子滤波算法，APSOPF表示本发明 方法。

表1验证实验的结果比较

视频序列 PF(200个粒子) APSOPF(30个粒子) 时间节省 Browse1 0.3284s 0.2120s 35.44％ Fight_RunAway1 0.3946s 0.2429s 38.44％ Aircraft 0.3735s 0.2264s 39.38％

图4显示了两种方法所估计出的跟踪目标在Browse1视频序列中的位置坐标(以像素 为单位)随时间变化的曲线与实际状态曲线之间的对比。从图4中可以看出，本发明方 法的目标跟踪准确性明显优于传统的粒子滤波目标跟踪方法。