一种基于自适应粒子滤波和稀疏表示的目标跟踪算法

摘要

本发明提出了一种基于自适应粒子滤波和稀疏表示的目标跟踪算法，使用改进的自适应粒子滤波技术作为跟踪算法框架，并且利用分块稀疏表示模型建立目标的观测相似度模型，利用自适应分块技术对目标进行分块，构建当前目标状态的结构稀疏直方图，以计算当前目标状态的观测相似度，利用遮挡检测机制检测遮挡，更新目标/背景字典模板以及目标模板直方图，以捕获跟踪过程中目标的外形改变以及环境的变化，利用可变方向乘子法解决稀疏表示中的L1优化问题，提升所述目标跟踪算法的执行速度。本发明对跟踪目标姿态变化，环境光照变化以及遮挡等情况具有很强的鲁棒性。

说明书

技术领域

本发明属于计算机视觉领域，具体涉及智能监控领域，特别涉及一种基于自适应粒子滤波和分块稀疏表示模型的复杂环境下的目标跟踪算法。

背景技术

基于视觉的目标跟踪技术在许多计算机视觉应用领域，诸如机器人技术、视频监控、医学图像分析等起到重要的作用。尽管在最近几十年基于视觉的目标跟踪技术取得了一定的发展，但是在一些复杂的环境下，譬如有复杂背景、光照变化剧烈、目标外形改变等场合，现有的视觉跟踪技术仍不能很好地完成跟踪任务。考虑到跟踪任务的复杂性，如何设计一个鲁棒性较强的跟踪算法，同时在实时性方面有较好的表现，是计算机视觉领域一个重要的课题。

目前常见的视觉跟踪算法主要有两大类：基于创成式的方法和基于分类的方法。基于创成式的跟踪算法主要通过寻找下一帧与目标相似度最高的区域进行跟踪，可以使用单外表模型和多外表模型计算相似度。常见的单外表模型包括使用颜色、纹理以及形状等信息进行描述，颜色外表模型有：RGB直方图特征，如文献“Huang, T., Russell, S.. Object identification in a Bayesian context [C]. International Joint Conferences on Artificial Intelligence, 1997: 1276-1283.”纹理外表模型有：LBP纹理特征，如文献“陈远，陈锻生. 一种融合LBP纹理特征的多姿态人脸跟踪方法[J].华侨大学学报，2010，Vol.31,No.3.”多外表模型尝试用多种单外表模型的结合，以提高模型的鲁棒性，如使用HOG颜色特征和LAB纹理特征来进行跟踪，如文献“Yang, B., Lin, G.Y. Integration of Lab model and EHOG for human appearance matching across disjoint camera views [J]. Journal of Southeast University (English Edition), v 28, n 4, p 422-427, December 2012.”一些经典的基于创成式跟踪算法主要包括：特征根跟踪器、均值漂移跟踪器以及协方差跟踪器等。

基于分类的跟踪方法将目标跟踪问题转变为一个目标分类问题，通过将某个区域分类为目标或背景来实现持续跟踪。使用分类来进行跟踪通常涉及到分类器的学习，可以通过监督或半监督的方式来学习分类器，进而进行目标跟踪。根据分类器的不同，常见的基于分类的跟踪方法包括：使用支持向量机（SVM）进行分类跟踪，如文献“S. Avidan. “Support vector tracking”. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(8):1064-1072, 2004.”使用多示例训练器（MIL）进行分类跟踪，如文献“S. Avidan. “Support vector tracking”. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(8):1064-1072, 2004.”其他常见的训练器还包括稀疏贝叶斯分类器以及P-N学习分类器等等。

稀疏跟踪算法是近年来发展比较迅速的一种新兴跟踪算法，属于创成式跟踪方法。由于算法是基于一系列的模板库得到的最终结果，因此对于光照变化、复杂环境以及姿态改变等都具有较好的鲁棒性，如文献“X. Mei and H. Ling. “Robust visual tracking using L1 minimization”. 12th International Conference on Computer Vision, Kyoto ,Japan, 2009(1436-1443).”但是，由于模板库往往采用目标的整体模板作为特征，因此对目标遮挡的情况处理效果不佳。同时，在解稀疏系数时需要解L1优化问题，具体解法的计算量较大，往往影响了算法的实际使用。

因此，对稀疏跟踪算法进行改进优化，是其在原有的强鲁棒性的基础上，增加对遮挡情况的处理能力以及提高算法的执行速度，具有显著的现实意义。

发明内容

本发明的目的在于提出一种基于自适应粒子滤波和稀疏表示的目标跟踪算法，此方法对跟踪目标姿态变化，环境光照变化以及遮挡等情况具有很强的鲁棒性。

为解决上述技术问题，本发明采用的一个技术方案是：

提供一种基于自适应粒子滤波和稀疏表示的目标跟踪算法，具体为：

使用改进的自适应粒子滤波技术作为跟踪算法框架，利用目标的运动信息来确定采样所需要的粒子数目和采样范围；

利用分块稀疏表示模型建立目标的观测相似度模型，首先构建目标/背景字典模板以及目标模板直方图，利用自适应分块技术对目标进行分块，利用目标的分块信息并且结合分块的身份信息以及位置信息，构建当前目标状态的结构稀疏直方图，利用巴氏距离计算当前目标状态的结构稀疏直方图和目标模板直方图之间的距离，从而计算当前目标状态的观测相似度；利用遮挡检测机制检测遮挡，利用遮挡信息更新目标/背景字典模板以及目标模板直方图，以捕获跟踪过程中目标的外形改变以及环境的变化。

在本发明一个较佳实施例中，所述的基于自适应粒子滤波和稀疏表示的目标跟踪算法使用改进的自适应粒子滤波技术作为跟踪算法框架，主要步骤如下：

110）采样参考点的确定

利用目标前一帧的状态以及前一帧的预测速度得到目标当前时刻的采样参考点，提出的自适应运动模型定义为：

，

其中x_k-1+ v*_k-1即为目标当前时刻的采样参考点，x_k-1是目标前一帧的状态，v*_k-1是前一帧的预测速度；

120）采样范围的确定

采样范围由步骤110）中的Σ_k决定，Σ_k可由目标的标准化速度向量V以及运动信息矩阵D来计算（Σ_k=VDV^-1），其中运动信息矩阵D由目标的速度峰值ρ_k以及可调参数γ决定，D=diag(ρ_k, γρ_k), γ∈[0,1]，γ权衡了采样的有效性和非线性；当γ=0时，仅考虑采样的非线性，此时提出的采样方法和普通的各向异性高斯采样相同；当γ=1时，仅考虑采样的有效性，即认为目标在做线性运动；γ由目标之前一段时间内的运动方向一致性以及加速度信息决定，定义如下：

，

其中，d(k)表示方向的一致性，a(k)表示加速度信息，C是归一化常数，μ表示加速度信息对可调参数γ的贡献；

130）采样粒子数目的确定

利用可调参数γ以及采样粒子数目的上下限来动态地调整采样的粒子数目，定义如下：

，

其中，J_min 表示采样粒子数目的下限，J_max表示采样粒子数目的上限。

在本发明一个较佳实施例中，所述的基于自适应粒子滤波和稀疏表示的目标跟踪算法使用自适应分块稀疏表示模型作为目标的观测模型，主要步骤如下：

210）目标/背景字典模板的建立

根据第一帧的目标信息分别建立目标与背景的分块字典模板：首先手动选取目标矩形区域，并将目标矩形区域周围一定范围的区域作为背景区域，利用滑动的小块分别在目标区域和背景区域重叠的采样，并对采集的样本进行k均值聚类计算，将各自得到的k个具有典型性的样本分别作为目标和背景的字典模板，目标/背景字典模板在跟踪过程中需要不断地进行更新；

220）目标自适应分块

利用目标小块的身份信息对目标进行自适应分块：对于每个目标小块，利用欧氏距离计算该目标小块与模板小块的相似度，挑选出与其最相似的p个模板小块，并利用这p个模板小块的身份来判断该目标小块的身份信息，根据这p个模板小块中目标成分和背景成分的多少，将该目标小块归于目标、背景或者不确定状态；

当得到所有目标小块的身份信息后，就可以对目标进行自适应分割，在分割目标时，首先进行粗略划分，分别判断每个目标小块的身份，然后依据所有目标小块的身份信息判断分割是否有效，分割的有效性E_S定义为：

，

其中N_T表示属于目标的目标小块的数目，N_U表示属于不确定状态的目标小块数目；若分割有效性大于给定阈值，则认为该分割满足跟踪需要；否则，将目标进行更细的分割，并计算其分割有效性判断分割是否满足要求；

230）观测相似度计算

利用自适应分块稀疏表示来计算目标的外表相似度：根据稀疏原理，对于某个观测值y_i，可以利用解L1优化问题得到它的稀疏系数x_i，L1优化问题定义如下：

，

其中，D表示目标模板，对于分块稀疏表示问题，得到每一个目标小块的稀疏系数，并将它们按照结构信息和身份信息组合起来，就能够得到当前目标状态的结构稀疏直方图，定义如下：

，

其中h_i表示目标某个目标小块的稀疏直方图，P_i表示该目标小块的身份信息，k(d_i)是一个各向同性的核，用来表示距离的影响；

   在第一帧使用同样的直方图提取方法可以得到目标模板直方图，利用巴氏距离计算当前目标状态的稀疏直方图和目标模板稀疏直方图的距离，就能够得到当前目标状态的观测相似度，即当前目标状态是真实目标状态的概率；

240）更新策略

稀疏表示中的目标/背景字典模板和目标模板直方图都需要不断地更新，以适应变化的场景；目标/背景字典模板通过在当前跟踪结果重采样进行更新，采样方法和步骤210）相同，通常目标/背景字典模板每隔10帧就重采样一次，当检测到遮挡的时候，目标字典模板停止更新，背景字典模板仍需要更新；

目标模板直方图需要更新以捕捉目标在跟踪过程中的外形变化，通过加权的方式，将当前目标状态的结构稀疏直方图逐渐的融合到目标模板直方图中，定义如下：

，

其中H_n表示新的目标模板直方图，H_f表示旧的目标模板直方图，H_c表示当前目标状态的结构稀疏直方图，φ是学习因子；

250）遮挡检测机制

利用目标小块的身份信息建立遮挡检测机制：因遮挡一般发生在边缘，定义目标的最外层的小块区域为遮挡检测区域，如果在所述遮挡检测区域内的任意一条边或者两条相邻的边上，被判断为属于背景的小块数目与小块总数之比大于预定阈值，就认为发生了遮挡。

在本发明一个较佳实施例中，所述的基于自适应粒子滤波和稀疏表示的目标跟踪算法利用可变方向乘子法解决稀疏表示中的L1优化问题。

本发明的有益效果是：本发明一种基于自适应粒子滤波和稀疏表示的目标跟踪算法，对稀疏跟踪算法进行改进优化，增加了对遮挡情况的处理能力以及提高了算法的执行速度，对跟踪目标姿态变化，环境光照变化以及遮挡等情况具有很强的鲁棒性。

附图说明

图1是本发明基于自适应粒子滤波和稀疏表示的目标跟踪方法的系统流程图；

图2是本发明中采用的采样模型示意图；

图3是本发明中采样区域示意图；

图4 是本发明中目标自适应分割示意图；

图5 是本发明中遮挡检测区域示意图。

具体实施方式

下面结合附图对本发明的较佳实施例进行详细阐述，以使本发明的优点和特征能更易于被本领域技术人员理解，从而对本发明的保护范围做出更为清楚明确的界定。

图1给出了基于自适应粒子滤波和稀疏表示的目标跟踪方法的系统流程图：使用改进的自适应粒子滤波技术作为跟棕算法的框架，主要工作是建立自适应运动粒子滤波模型以及用于计算观测相似度的自适应分块稀疏表示模型。建立自适应运动粒子滤波模型主要包括三个方面的工作，即确定采样参考点、确定采样范围以及确定采样粒子数目。利用目标前一帧的状态以及前一帧的预测速度可以得到目标当前时刻的采样参考点，采样范围由目标的运动速度、运动方向一致性以及加速度等诸多因素决定，采样的粒子数目与采样范围有关，一般采样范围大的话，需要的采样粒子数目也比较大。建立自适应分块稀疏表示模型主要有三个方面的工作，即自适应分块、建立基于分块的结构稀疏直方图以及使用可变方向乘子法解L1优化问题。自适应分块是通过计算目标小块与目标/背景字典模板的相似度，从而确定目标小块的身份，进而通过分割有效性来对目标进行合理的分块。通过对每个目标小块计算稀疏系数，并结合该小块的身份信息以及结构信息，可以构建基于分块的结构稀疏直方图，从而通过比较其与目标模板直方图的巴氏距离来计算当前目标状态的观测相似度。可变方向乘子法用来解决求解稀疏系数时遇到的L1优化问题，可以显著地提高算法的执行速度。

本发明的具体操作步骤：

1）建立自适应采样模型

粒子滤波是常见的目标跟踪算法框架，其中粒子采样模型决定了跟踪的效率和精度。常见的是利用各向异性高斯分布进行采样，但是这种方式采样效率偏低，没有充分利用目标自身的信息。本发明提出了一种自适应采样模型，合理地利用了目标的运动信息，提高了采样的效率以及精度。自适应采样模型定义如下：

，

其中，x_k-1+ v*_k-1即为目标当前时刻的采样参考点，x_k-1是目标前一帧的状态，v*_k-1是前一帧的预测速度。Σ_k决定了采样范围，它由目标的标准化速度向量V以及运动信息矩阵D来计算（Σ_k=VDV^-1）。其中运动信息矩阵D由目标的速度峰值ρ_k以及可调参数γ决定，D=diag(ρ_k, γρ_k), γ∈[0,1]。本发明使用之前数帧的运动一致性以及加速度信息自适应地确定γ，定义如下：

，

其中，d(k)表示方向的一致性，a(k)表示加速度信息，C是归一化常数，μ表示加速度信息对确定γ的贡献。本发明使用的采样模型示意图如图2所示，分别对应了线性运动的采样、非线性运动的采样以及线性运动中突然遭遇转向时候的采样。

2）确定采样粒子数目

采样粒子的数目受到采样范围大小的影响，一般采样范围越大，所需要的采样粒子数目就越多。本发明利用1）中提到的可调参数γ来确定采样粒子数目，定义如下：

，

其中，J_min 表示采样粒子数目的下限，J_max表示采样粒子数目的上限。

3）构建目标/背景的稀疏字典模板

使用稀疏表示模型来计算目标状态的观测相似度，首先要构建目标/背景的稀疏字典模板，通常在第一帧完成目标/背景稀疏字典模板的构建工作。首先手动选取目标矩形区域，并将目标矩形区域周围一定范围的区域作为背景区域。利用滑动的小块（此小块的面积等于目标分块后各小块的面积）分别在目标区域和背景区域重叠的采样，并对采集的样本进行k均值聚类计算，各得到k个具有典型性的样本作为目标和背景的字典模板。目标/背景采样区域示意图如图3所示。

4）对目标进行自适应分块

在跟踪过程中，遮挡会对跟踪的效果产生很大的影响，往往导致跟踪漂移。遮挡发生时，部分目标会被遮住导致其信息无法利用，但是可以利用目标可见部分的信息进行持续跟踪，通常采用分块的方法处理遮挡情况。本发明提出一种自适应分块技术，对于目标分割后的每个小块，利用欧氏距离计算该小块与模板（包括目标模板和背景模板）小块的相似度，挑选出与其最相似的p个模板小块，并利用这p个模板小块的身份来判断目标小块的身份。根据这p个模板小块属于目标的小块多还是属于背景的小块多，可以将目标的某个小块的身份归为目标、背景或者不确定状态。在得到了某个目标所有小块的身份信息后，可以利用分割有效性来对目标进行分块：首先进行粗分，计算该次分割的分割有效性，如果大于给定阈值，分割结束；否则，进行进一步细分。通常至多5*5的分割就可以满足表示目标的需要，图4为本发明中目标自适应分割示意图，分别给出了对目标的分割情况以及对应每次分割的分割有效性。

5）计算目标当前状态的观测相似度

计算目标当前状态的观测相似度，是实现准确跟踪的前提。观测相似度计算步骤如下：

①计算稀疏系数

根据稀疏原理，对于某个观测值y_i，可以通过解L1优化问题得到它的稀疏系数x_i，L1优化问题定义如下：

，

其中，D表示目标模板。本发明使用可变方向乘子法来解决L1优化问题，显著地提高了算法的执行速度。

②建立结构稀疏直方图

得到了每个目标小块的稀疏系数以及目标小块的身份信息后，就能够建立结构稀疏直方图来表示当前的候选目标状态。每个小块的结构稀疏直方图定义为：

，

其中h_i表示目标某小块的稀疏直方图，P_i表示该小块的身份信息，如果该小块属于背景的话，那么它很有可能被遮挡了，因此也就不会用来表示目标信息（P_i=0）。k(d_i)是一个各向同性的核，用来表示距离的影响，离目标中心较远的小块有比较小的权重。将所有目标小块的稀疏直方图串联起来，就得到了当前目标状态的结构稀疏直方图。

注意，需要在第一帧中使用相同的方法建立目标的模板直方图。

③计算观测相似度

利用巴氏距离计算当前目标状态的结构稀疏直方图与目标的模板直方图之间的距离，就能够计算出当前目标状态的观测相似度，即当前目标状态是目标真实状态的可能性。

6）检测遮挡情况

在目标跟踪过程中，如果发生遮挡时进行了错误的跟踪，就会将非目标信息错当成目标信息，最终导致跟踪失败。同时，当目标被遮挡时，如果利用此时目标的信息进行更新，就会将错误的信息引进来，导致目标外表模型失效。因此，能够有效检测跟踪过程中遇到的遮挡至关重要。本发明利用所有边缘目标小块的身份信息建立了一个遮挡检测机制：由于遮挡一般首先发生在目标边缘，定义目标的最外层的小块区域为遮挡检测区域，如果任意一条边或者两条相邻的边上，被判断为属于背景的小块数目与这些边包含的小块总数之比大于一定阈值，就认为发生了遮挡。遮挡检测区域示意图如图5所示。

7）更新目标/背景字典模板以及模板稀疏直方图

稀疏表示中的目标/背景字典模板和目标模板直方图都需要不断地更新，以适应跟踪过程中目标外形的改变以及背景的变化。目标/背景字典模板通过在当前跟踪结果处重采样进行更新，采样方法和步骤1）提到的方法一致。通常目标/背景字典模板每隔10帧就重采样一次，当检测到遮挡的时候，目标字典模板停止更新，背景字典模板仍需要更新。

目标模板直方图需要不断更新以捕捉目标在跟踪过程中的外形变化。本发明通过加权的方法，将当前目标状态的结构稀疏直方图逐渐融合到目标模板直方图中，定义如下：

，

其中H_n表示新的目标模板直方图，H_f表示旧的目标模板直方图，H_c表示当前目标状态的结构稀疏直方图，φ是学习因子，用来调节当前目标状态的结构稀疏直方图对新的目标模板直方图的贡献。

以上所述仅为本发明的实施例，并非因此限制本发明的专利范围，凡是利用本发明说明书及附图内容所作的等效结构或等效流程变换，或直接或间接运用在其他相关的技术领域，均同理包括在本发明的专利保护范围内。