结合尺度估计MST和粒子滤波的视频目标跟踪

2020-04-24孙新领

计算机工程与应用 2020年8期

孙新领，张皓，赵丽

1.河南工学院计算机科学与技术系，河南新乡453003

2.山西大学软件学院，太原030013

1 引言

视觉跟踪是计算机视觉中最重要的领域之一，已被应用于多个领域，例如监控和人机交互等。但是，当存在遮挡、外观和尺度变化情况下，仍然会引起各种问题[1-3]。在各种视觉跟踪算法中，均值漂移跟踪（Mean Shift Tracking，MST）算法[4-6]是最常用的方法之一，它具有易于实现且计算时间消耗较少的优点。MST方法的基础是非参数密度估计器，由于它是使用颜色直方图来表示模型，所以对部分遮挡和旋转具有鲁棒性。然而，MST 方法不能解决尺度变化、完全遮挡和模型改变等问题。此外，在外观和光照变化的条件下实现长期跟踪也十分困难[7-8]。

为了解决MST 的这些缺点，研究者已经提出了多种基于MST 的改进型跟踪方案。例如，文献[9]给出了一种改进的MST算法（EM-Shift），其同时估计局部模式的位置和描述局部模式近似形状的协方差矩阵。文献[10]利用自适应背景加权直方图（BWH）方法来改进MST算法，并尝试将轮廓直方图和空间直方图结合起来，使其可以利用背景信息，有效地减少背景对目标定位的干扰。但是，它无法处理对象的尺度变化。文献[11]提出了一种称为尺度和方向自适应MST 算法（SOAMST），使用加权图像作为密度分布函数的尺度和方向，使其可以在MST 框架下估计物体的尺度和方向。但是SOAMST 算法对于目标的遮挡问题也无法处理。为此，一些学者融入了卡尔曼滤波器。例如，文献[12]提出了一种将卡尔曼滤波与SOAMST 相结合的算法（KSOAMST），如果目标被部分遮挡，则直接使用SOAMST跟踪目标；如果完全遮挡，则使用卡尔曼滤波器估计目标下一帧的位置。但是，卡尔曼滤波的性能随着非线性强度变大会明显下降。文献[13]使用MST进行跟踪，并利用它的相似性来调整卡尔曼滤波器的协方差。这种方法可以在被遮挡的情况下追踪物体，但当物体移动速度变化较大时，无法跟踪物体。

在本文中，提出了一种结合MST算法、探测器和粒子滤波器的目标跟踪方法。主要创新点为：提出一种具有半监督学习能力的探测器来在线更新目标模型，自适应校正目标尺度，以此解决传统MST 方法无法应对尺度变化的缺陷。此外，在发生完全遮挡时采用粒子滤波器估计目标的位置，以此改善MST 无法处理完全遮挡的问题。实验结果表明，该方法能够成功跟踪复杂环境中的目标。

2 目标跟踪方法的框架

本文所提出的目标跟踪方法的流程图如图1所示，主要包括MST、探测器和粒子滤波器。首先，通过MST算法跟踪对象，基于Bhattacharyya系数来确定是否跟踪成功。如果该系数值低于特定阈值，则判定未成功跟踪对象。此时，使用探测器重新初始化MST 的目标位置和尺度。这个过程是基于模型匹配和学习过程。学习过程会不断更新目标模型，以加强探测器的性能。另外，粒子滤波器还可以准确地估计目标的位置，在发生完全遮挡时，通过目标的先前行为来预测目标的位置，以此解决经典MST算法的缺点。

图1 所提出跟踪算法的流程图

在发生完全遮挡的情况时，MST 和探测器都无法找到目标。如果跟踪器和探测器的相似性快速降低，则确定已发生完全遮挡，并且启动粒子滤波器预测目标的位置。在所提出的方法中，假设目标在x 和y 方向上以相同的速度移动。这种假设是合理的，因为完全遮挡通常会在短时间内发生，因此目标遵循几乎恒定的速度模型。粒子滤波器可以根据目标的先前行为估计目标的位置和速度。在离开遮挡情况之后，再次由探测器找到目标并继续跟踪。

3 均值漂移跟踪器

3.1 均值漂移算法

在经典的MST算法中，用户在第一帧中选择目标，并且使用归一化的颜色直方图来表示目标模型[14]。目标区域中的归一化像素位置由确定，其中n 表示像素的数量。目标模型由下式计算得到：

其中：

式（5）中的第一项与位置y 无关，所以最大化相似性与最大化式（5）中的第二项相同。将式（5）对y 求导数，并使其等于零，得到迭代优化过程，称为均值漂移迭代。在均值漂移迭代中，估计的目标从y0移动到新位置y1。经典MST的最终迭代公式定义为：

MST 算法适用于跟踪通用对象。但是，当连续帧之间的目标位移相对较大时，它可能无法跟踪对象。类似地，如果目标与其他对象重叠（遮挡），则算法可能会收敛到局部最小值。为解决这个缺点，需要重新初始化或重新启动检测过程。此外，经典MST 的一个局限是尺度适应性。因为它不考虑目标的尺度，所以无法准确估计目标的位置。

3.2 跟踪器的模型更新

为了解决MST 的尺度问题，需要动态更新MST 跟踪器的目标模型，为此本文采用一种探测器来实现模型的更新。如果跟踪器无法跟踪目标，此时探测器能够以高可靠性找到目标，并更新目标模型。其以加权方式更新目标的颜色直方图，表示如下：

4 具备在线学习的探测器

探测器有助于重新初始化MST 的目标尺度和位置。当采用半监督P-N 学习[17]的在线学习过程跟踪物体时，探测器的性能得到有效改善。探测器基于滑动窗口方法[18]，由三个部分级联组成：方差滤波器部分、集成分类部分和模型匹配部分。为了实时执行提出的算法，探测器在验证区域中搜索目标，而不是执行穷举搜索。

4.1 方差滤波器

探测器执行的第一步是使用方差滤波器在图像中找到候选子窗口。通常，方差可以区分开结构良好的对象和均匀背景。在该阶段，将灰度值方差小于特定阈值σVF的所有子窗口都丢弃。这个阈值定义为初始目标模型中方差的一半，因为方差会根据目标而改变。为了减少计算时间和内存使用量，通过积分图像计算每个子窗口的方差。为了计算每个子窗口B 的方差，需要使用两个积分图像。其中一个是位置( x,y )处的积分图像I′，包含了图像中点（1，1）和( x,y )之间的所有像素值的总和，可以表述为：

另一个积分图像I″表示图像I 的平方值，表示如下：

使用这些积分图像，子窗口B 的方差可以表示为：

其中n 是图像中的像素数。

4.2 集成分类器

通过方差滤波器过滤掉背景以后，执行探测过程的第二步，即采用基于随机化的集成分类器，通过比较几个像素的强度值对像素进行分类。此阶段的输入是一组通过方差滤波器输出的子窗口。对于每个候选子窗口，计算一个概率，用于表示子块是否对应于正确标签。如果概率值小于0.5，则子窗口被拒绝。

集成分类器由M 个子分类器组成，每个子分类器都执行像素的强度值比较。在算法开始时，从均匀分布中随机提取像素的位置，并在跟踪目标期间固定像素的位置。每个子分类器的输出表示为：

其中，d1和d2是图像I 中的随机位置。最后，使用式（12）对每个子分类器的概率进行平均，当平均概率大于0.5时，集成分类器将子窗口分类为目标对象：

4.3 模型匹配

在通过分类器对目标像素进行分类后，执行探测器的最后一步，即使用模型匹配方法搜索目标。模型匹配过程会在探测图像与目标模型之间进行逐像素的比较，当两者相似性大于特定阈值时，判断该探测图像为探测器找到的目标模型。然后通过式（7）来更新MST 中的目标模型，获得尺度更新过的新目标模型

为了减少计算时间，将输入子窗口的大小调整为MtNt。在所提出的方法中，通过归一化相关系数(NCC)来测量相似性。子窗口T1和T2之间的NCC 表示如下：

其中μ1和μ2,σ1和σ2分别是T1和T2的均值和标准差。使用NCC，两个子窗口之间的距离计算如下：

在跟踪期间，更新正类和负类的标准化模型。给定输入子窗口Tin，正类和负类的距离表示为：

其中T+和T-分别是正类和负类的集合。那么，模型匹配概率的定义为：

该概率表示子窗口是否包括目标，如果概率大于特定阈值σTM，则确定相应的子窗口属于目标。

4.4 在线学习

P-N学习方法是一种半监督学习方法，其使用两种类型的约束从未标记数据中提取示例以增强训练集。一个是P 约束，它可以识别假阴性示例，然后将它们放入一个正类训练集中。另一个是N 约束，它可以识别假阳性示例，然后将它们添加到负类训练集中。P-N学习的目标是通过在标记数据中的学习分类，并将未标记的数据进行分类以扩充标记数据集。

为了学习分类器，使用了检测到的目标的反常子块。P 约束的功能是找到目标的新外观，以便于探测器的泛化。它基于跟踪器结果附近的子窗口将具有正标签的事实来搜索示例。也就是说，P 约束用于分类高度重叠的子块。相比之下，N 约束的目的是在背景中发现杂乱像素点，以便于探测器的目标检测。

5 基于粒子滤波的位置估计

由于传统MST 只会锁定领域内的局部最大值，当遇到大面积遮挡时，MST 锁定的目标位置会与真实位置有偏差。这个偏差会随着遮挡视频帧的增加而持续扩大，以致最后丢失目标。为此，在发生严重遮挡时，本文启动粒子滤波器，用来估计遮挡时的目标位置。在遮挡过后，根据所估计的位置，使MST 能够快速搜索到目标。

粒子滤波器能够为发生遮挡时的目标跟踪提供很强的鲁棒性，这是因为它既不受限于线性系统，也不要求噪声服从高斯分布。粒子滤波中，将目标可能的位置是真实位置的概率作为粒子。前一帧中的所有粒子会以状态传递函数的形式转换到当前帧，虽然粒子位置和权重都发生变化，但它仍能提供最近似实际位置的目标位置。

为了估计系统的后验状态，定义一个目标模型，如下所示：

式中，fm-1为目标状态的非线性函数；wm-1为白噪声序列，代表状态预测的不确定性。当前时间m(m ≥1)的在线离散预测zm由下式确定：

式中，hm为非线性函数，um为零均值的白噪声序列，表示预测中的误差。

粒子滤波的迭代过程分为两个部分：（1）预测；（2）更新。

在预测阶段，利用系统模型及m 时刻的初始概率密度，通过积分运算获得m-1 时刻的概率密度，表达式如下：

其中，zm={ }zi:i=1,2,…,m 为给定的在线观测序列。

在更新阶段，在给定先验概率密度p(x1|z0)≡p(x1)、状态函数形式(f)、外观模型(h)以及最终预测时刻的情况下，每一时间步长处估计后验密度p(x0:m|z1:m)表达式如下：

对于目标跟踪的应用，需要从初始给定的概率密度p(x1)中获取N 个观测样本。为了获得一致性的粒子观测值，需要为这些粒子样本分配一致性权重，表示如下：

由于假设目标状态变化为马尔可夫链，则后验概率可以描述为：

式中，δ(⋅)表示狄拉克δ 函数。

本文提出的实时目标跟踪方法的伪代码如算法1所示。

算法1 提出的目标跟踪算法

初始化：

1. 通过式（1）计算目标模型q̂，并初始化位置y0；

2. 初始化参数；

3. 基于在第一帧中的目标选择进行学习；

执行：

6. 确定是否目标跟踪成功

则通过式（16）计算跟踪器输出的子块和正类样本集中子块的相似性STM（模型匹配概率）；

如果(STM＞σTM)

则跟踪器提供正类和负面图像子块，并执行学习。

否则

通过粒子滤波，基于跟踪器中的目标位置来估计位置。

否则

通过粒子滤波预测目标的位置；

通过式（16）计算探测器探测的子块与正类样本集的相似性STM；

如果(STM＞σTM)

通过粒子滤波估计位置和尺度；

为跟踪器更新目标模型；

否则

通过粒子滤波预测目标的位置；

7. 返回到第4步骤；

输出：

估计的目标位置和尺度。

6 实验及分析

6.1 实验设定

实验使用的测试视频序列来自PETS 2009数据集，这些视频中包含了遮挡、背景杂乱和外观变化在内的各种环境。实验在具有英特尔酷睿i7-3.40 GHz CPU，8 GB RAM PC机上的MATLAB上编程执行。

使用这些视频序列进行性能评估，并与一些基于MST的改进方法进行比较，分别为经典MST跟踪器、文献[10]提出的结合自适应背景加权直方图的BWH-MST方法、文献[12]提出的卡尔曼滤波与SOAMST相结合的算法（K-SOAMST）。MST算法使用基于颜色直方图的目标模型迭代估计对象的位置。BWH-MST 使用背景加权直方图解决了背景复杂的问题。K-SOAMST算法改善了MST 在尺度估计和方向估计等方面存在的问题，并结合卡尔曼滤波提高对遮挡的应对能力。

对于基于均值漂移框架的跟踪器，使用RGB 颜色空间，并且每个通道被均等地分成16 个区域以表示目标和候选，而且都应用Epanechnikov内核。对于本文提出的算法，Bhattacharyya 系数的阈值σVF（用于确定跟踪是否成功）设置为0.65。粒子滤波器中的粒子数量设置为30。对于探测器，相似性的阈值σTM定义为0.6。用于更新目标模型的β 设置为0.9。这些值是通过多次实验结果确定的。

6.2 性能指标

为了评估跟踪算法性能，使用两个性能指标。第一个是中心位置误差（CLE），它可以测量估计物体的中心位置与实际数据之间的误差，定义如下：

其中，xe和ye表示跟踪结果的中心位置，xg和yg表示实况数据的中心位置。

第二个性能指标是成功率（SR），定义如下：

其中，Re是跟踪结果的边界框，Rg是实况数据的边界框。如果SR 大于0.5，则判定跟踪结果为成功。

6.3 性能评估

为客观地评估所提出的算法与其他基于均值漂移的跟踪算法（MST、BWH-MST 和K-SOAMST），选择了四个具有挑战性的视频序列来构建测试数据集，分别为Ball序列，Car1序列，Car2序列，和Person1序列。其中，Ball 序列存在目标快速移动，Car1 序列包含了遮挡情况，Car2序列包含了尺度变化情况，Person1序列存在光照变化。

图2 举例显示了在Car1 序列和Car2 序列上各种算法的跟踪结果。图2（a）显示了在存在完全遮挡情况下的跟踪情况。在完全遮挡之前，每个跟踪器都可以估计目标位置。然而，在经过完全遮挡之后，只有本文算法可以跟踪目标。K-SOAMST 也具有处理遮挡的能力，但是在该视频序列中，汽车目标移动较快，非线性较强，导致卡尔曼滤波的性能下降。在本文方法中，粒子滤波可以很好地应对非线性和非高斯环境，为此能够纠正跟踪过程。在图2（b）的序列中，目标发生了尺度变化。在这个视频序列中，所有算法都可以跟踪目标，其中本文算法和K-SOAMST 算法的尺度估计准确性较高，能够自适应调整目标的尺度。这是因为本文算法中融入了用于尺度调整的探测器过程。

图2 各种基于MST算法的跟踪结果

各种算法在4个视频序列上的平均CLE和SR性能指标如表1和表2所示。

表1 平均中心位置误差（CLE）

表2 平均跟踪成功率（SR） %

从表1 和表2 所示的结果可以看到，本文算法都获得了最佳结果。对于Ball 序列，目标快速移动，使得它在连续帧之间的位移很大。虽然MST算法无法跟踪目标，但本文算法在此序列上表现良好。这是因为粒子滤波器基于先前的目标运动轨迹，精确地估计目标位置，从而减少目标在连续帧之间的位移，这使得MST 算法能够成功地跟踪对象。此外，当MST 算法无法跟踪对象时，探测器会找到目标位置并重新初始化MST 算法。在Car1 序列中，目标在15 帧中经历完全遮挡。本文算法在目标重新出现后表现良好，这是因为粒子滤波器在目标完全遮挡时预测目标位置，并且当目标再次出现时，MST 算法可以使用所预测的目标位置成功跟踪目标。在Car2 序列中，目标的尺度变小。本文方法在探测器的帮助下估计目标尺度。在Person1 序列中，当目标模型由于光照变化而改变时，MST和BWH-MST算法无法跟踪目标。

另外，各种算法每帧目标跟踪的平均计算时间如表3所示。其中，基于MST的跟踪器最显著的优势在于可以在较短时间内跟踪目标，为此各种方法的计算时间都不是很高，都在15 ms 以内。其中，传统MST 算法计算时间最短为3.85 ms。尽管所提出的算法包含探测和学习过程，但本文在探测过程中调整了输入子窗口的大小，使其计算速度并没有增加太多，为11.55 ms。