0 引言

目标跟踪正在社会科技发展和国民经济中发挥着巨大的作用, 其研究具有重要的应用价值和广阔的发展前景, 然而, 照明变化^[1-3]、外观变化^[4-5]、形状变化^[6-7]和遮挡^[8-10]这些因素仍然是目标跟踪的巨大挑战。

根据跟踪目标的相似性度量方法以及表示的不同, 将跟踪算法归类为基于模型的、基于轮廓的、基于区域统计特性的和基于特征的跟踪算法等。

基于模型的跟踪对于目标的运动轨迹分析比较准确, 即便目标在被跟踪的过程中有姿态变化也能跟踪到目标, 但在实际的跟踪系统中, 如果没有先验知识就很难得到目标模型。对刚体目标如汽车^[11]进行跟踪时, 首先通过已知的先验信息得到汽车的3D结构, 然后通过视频序列获取3D模型的参数, 继而得到跟踪目标的瞬时运动参数; 但是, 实际中很难保证几何模型的精确, 同时3D模型的相关算法也比较耗时, 使得这种算法在运用中有了一定的局限性。基于轮廓的跟踪, 在对目标进行跟踪时采用先分割后提取边缘, 这种方法对外形有变化的目标有较好的跟踪效果, 如对运动细胞的跟踪, 但当运动的目标被全部或部分遮挡时, 这种算法将受到很大的局限。基于区域统计特性的跟踪方法由于利用目标的全局描述信息, 难以准确定位, 同时, 受到存在其他区域统计特性相似的影响, 跟踪算法也会失效^[12]。基于特征的跟踪算法的关键是进行特征提取, 常见的方法有Harris角点检测^[13]、SUSAN(Smallest Univalue Segment Assimilating Nucleus)^[14]、Hessian-Laplace^[15]、强角点检测^[16-17]等。但是它们的缺点是不能适应图像的尺度变化, 对于不同尺度的图像, 无法建立相应特征点的对应关系。近几年, 目标跟踪更关注于基于特征的目标跟踪算法, 如在实际复杂多变的场景中目标在跟踪过程中往往会出现形变、遮挡等问题, 当前利用其他方法很难有效解决这些问题, 而通过特征点匹配, 不断更新特征点最终可以实现目标的跟踪^[18]。加速鲁棒特征(Speeded Up Robust Feature, SURF)^[19]是一种尺度不变和旋转不变的特征, 与传统的跟踪算法相比, SURF是一种很好的局部特征, 并且这种特征具有尺度不变、图像旋转不变和视角不变性, 以及良好的特征提取速度。因此, 本文针对目标的尺度变化选用了SURF特征, 同时由于多示例学习(Multi-Instance Learning, MIL)是若干个样本构成的样本包取代单个样本, 通过此办法可以解决正样本很难确定的情况, 对目标被部分短时遮挡的情况具有很好的效果。本文提出了基于SURF特征和MIL的目标跟踪算法。

1 目标特征的提取 1.1 SURF特征的提取

本文提出的目标跟踪算法提取目标区域及其周围的SURF^[20]特征, 如图 1所示。

第一步进行特征点检测, 主要利用Hessian矩阵的行列式判断图像上某点是否为极值点, 如式(1)所示：

$ \boldsymbol{H}\left( {f\left( {x,y} \right)} \right) = \left[ {\begin{array}{*{20}{c}} {\frac{{{\partial ^{\text{2}}}f}}{{\partial {x^2}}}}&{\frac{{{\partial ^2}f}}{{\partial x\partial y}}} \\ {\frac{{{\partial ^2}f}}{{\partial x\partial y}}}&{\frac{{{\partial ^2}f}}{{\partial {y^2}}}} \end{array}} \right] $

(1)

其行列式为:

$ {\text{det}}\boldsymbol{H} = \frac{{{\partial ^2}f}}{{\partial {x^2}}}\frac{{{\partial ^2}f}}{{\partial {y^2}}} - {\left( {\frac{{{\partial ^2}f}}{{\partial x\partial y}}} \right)^2} $

(2)

若行列式小于零, 即此矩阵的特征值不同号, 就可判断出(x, y)是非局部极值点；反之, 若行列式大于零, 即此矩阵的特征值同号, 就可判断出(x, y)是极值点。

第二步确定主方向, 构造SURF特征描述子向量。提取SURF特征的算法如图 2所示。

1.2 潜在语义特征的提取

将目标区域及其周围的SURF特征继续构造其潜在语义特征^[21], 主要涉及到用提取的SURF特征形成多示例包, 通过聚类构造视觉字典, 生成图像区域的词-文档矩阵, 进而获得关于目标及其周围区域的潜在语义特征。

首先构造词-文档矩阵, 把训练集的全部包相对应的向量按列放在一起：

$ {\boldsymbol{A}_{K \times N}} = [{\boldsymbol{B}_1},{\boldsymbol{B}_2}, \cdots ,{\boldsymbol{B}_N}] = \left[ {\begin{array}{*{20}{c}} {{w_{1,1}}}&{{w_{1,2}}}& \cdots &{{w_{1,N}}} \\ {{w_{2,1}}}&{{w_{2,2}}}& \cdots &{{w_{2,N}}} \\ \vdots & \vdots &{}& \vdots \\ {{w_{K,1}}}&{{w_{K,2}}}& \cdots &{{w_{K,N}}} \end{array}} \right] $

(3)

在这里A_K×N每一行代表一个“视觉字”, 它的每列代表一个多示例包, 而多示例包是由目标及周围区域的SURF特征所对应视觉字的权重构成。

然后, 对词-文档矩阵A_M×N进行奇异值分解：

$ {\boldsymbol{A}_{K \times N}} = {\boldsymbol{U}_{K \times n}}{\boldsymbol{S}_{n \times n}}({\boldsymbol{V}_{N \times n}})' $

(4)

其中：K表示以前特征空间的维数, N表示文档的个数, n=min(K, N)。

本文对A_K×N进行降维, 得到：

$ \boldsymbol{{\overline A} _{T \times N}} = {\boldsymbol{S}_{T \times T}}({\boldsymbol{V}_{N \times T}})' $

(5)

将特征空间从K维降为T维, 则得到全部包的“潜在语义特征”, 即A_T×N里的每一列。

当新来一个多示例包：

$ \boldsymbol{B} = [{w_1},{w_2}, \cdots ,{w_k}]' $

(6)

可得出其潜在语义特征为:

$ \boldsymbol{\overline B} = \varphi (\boldsymbol{B}) = ({\boldsymbol{U}_{K \times T}})'\boldsymbol{B} $

(7)

式(7)中U_K×T的T个列向量可看作是原来空间的压缩, 潜在语义空间的基为U_K×T里的T个列向量。

2 分类器的构造

虽然本文算法用到的分类器是支持向量机(Support Vector Machine, SVM), 但是其基于多示例框架的, 所以本文算法对整个包提取其潜在语义特征, 而不是用多示例包中的单个示例即SURF描述子作为SVM的训练样本，因此本文算法在训练SVM时是提取多示例包的潜在语义特征, 用包的潜在语义特征和这个包相应的标记组成训练样本来训练SVM, 同样, 当得到SVM模型后, 用SVM识别多示例包, 输出多示例包的正负标记。

3 基于多示例学习的目标跟踪 3.1 多示例学习框架

本文在训练SVM以及提取特征时都是把包作为单个训练样本, 即用到了MIL中对训练样本中的包标记的思想, 而不是单个示例的思想。

该算法首先提取包的SURF特征, 通过聚类形成视觉字典, 然后将这些多示例包中的SURF特征都一一对应成视觉字典中的视觉字, 再次通过计算, 得出每一个视觉字在多示例包中的重要程度, 接下来由多示例的列向量构成“词-文档矩阵”, 提取包的潜在语义特征, 然后训练SVM。

在后续帧中, 多示例包都是未标记的, 先对新来帧提取多示例包的潜在语义特征, 然后用训练好的SVM对多示例包进行识别并给出目标的位置, 同时更新视觉字典, 重新训练SVM, 跟踪算法如下所示。

输入    视频数据根据相同视觉特征可形成的视觉字的种类N和视频数据集;

输出    跟踪算法的精度和速率。

步骤1    利用第1章中的方法提取SURF特征。

步骤2    构造“视觉词汇表”。将提取到的SURF描述子利用K-means方法聚成K类, 把各个类中心称之为“视觉字”, 这K个“视觉字”称作“视觉词汇表”, 表示成R。

步骤3    生成“词-文档矩阵”。把训练集中的各个包中的各个示例对照成步骤3中生成的R中的“视觉字”；

步骤4    潜在语义特征提取。对“词-文档”矩阵进行奇异值分解, 然后降维, 训练集中的每个多示例包的“潜在语义特征”就是降维后的“词-文档”矩阵中的每一列。

步骤5    初始化训练样本集TS=Ø, 将生成的已知的正负包的潜在语义特征表示成φ(B_i), 将(φ(B_i), y_i)加入TS。

步骤6    训练SVM分类器, 由TS训练SVM分类器。

步骤7    对后续帧的每一个新包计算出它的潜在语义特征, 再用前面训练好的SVM分类器进行识别, 生成正、负包。

重复步骤1~步骤7, 直到最后一帧。

3.2 跟踪过程中的更新机制

为了自适应目标的外观和姿态的变化, 所提出的跟踪算法每5帧更新一次SVM。更新时首先对每一帧新来的图像进行多示例包的划分, 并提取SURF特征；然后将5帧提取到的所有SURF特征进行聚类形成新的视觉字典；再用5帧积累的多示例包构造新的“词-文档”矩阵；最后提取新的多示例包的潜在语义特征来更新分类器。

3.3 跟踪算法

本文算法主要思想是先进行特征点检测, 生成SURF描述子, 然后利用聚类方法对当前提取到的全部SURF描述子聚类, 构建视觉词汇表, “词-文档矩阵”是按视觉字在包中的重要程度构建的。接下来采用潜在语义分析(Latent Semantic Analysis, LSA)得到包的潜在语义特征, 把MIL变成规范的有监督学习, 最后用支持向量机进行识别。

4 实验结果与分析

本文的实验环境为Intel Core2 Duo CPU E7500 2.93 GHz、2.94 GHz和4.00 GB的内存以及Matlab R2011a。收集了50个标准测试视频序列^[22]以及2个手工录制的视频。

实验中用到的对比算法有：跟踪学习检测(Tracking Learning Detection, TLD)^[23]、多示例学习跟踪MILTrack^[24]、压缩跟踪(Compressive Tracking, CT)^[25]。视频数据里包含目标尺度变化、姿态变化和短时遮挡。实验中, 先验信息为前5帧的目标的初始位置和目标的大小, 同时, 在更新视觉字典时, 采用的是每5帧更新1次。

4.1 实验定性分析

实验一    尺寸变化。图 3是Dog1上运行的跟踪结果。MILTrack对于目标的大小的变动, 尽管可以达到跟踪的要求, 不过此算法对目标大小缩放的情形不能适应。本算法可以适应目标的尺度缩放。

实验二    遮挡情况。在跟踪的过程中正样本可能会出现不好确定的问题, 为了解决这种问题采用了MIL的方式, 其让含有若干样本的多示例包取代用独个样本作为训练集。这样对于跟踪过程中目标的漂移能够做到一定的减少, 让跟踪的目标更加稳定。本文选用一组具有短时遮挡的视频序列来测试所提算法和其他算法的跟踪效果, 然后进行对比。图 4是被短时遮挡过脸的视频(FaceOcc2)序列的每种算法的跟踪效果。

从图 4中可以看到, 当目标受到遮挡, MILTrack算法产生了漂移, 而本文算法却有较好的效果, 不过本文算法对于目标被长时间全部遮挡这种情况也是没有鲁棒的跟踪效果。对于本文算法对短时局部遮挡有较好的效果是因为本文算法使用了局部特征SURF。

实验三    光照、外观变化等情况。本文算法在其他方面(光照、外观变化、旋转)也能满足跟踪的要求, 如图 5~7所示。

1) 光照变化，如图 5所示。

2) 外观变化，如图 6所示。

3) 快速移动、旋转以及短时遮挡，如图 7所示。

4.2 定量分析实验

本文算法和其他算法的对比结果如表 1所示, 结果的运算是对50个基准视频数据的精度的平均值, 本文算法都具有较好的跟踪性能。

几种算法在跟踪时的位置误差曲线如图 8所示。

5 结语

本文提出了一个基于SURF和MIL的目标跟踪算法。算法提取了图像的SURF特征, 利用MIL训练包的性质, 用户仅需对划分的多示例包给定一个标号, 而不必对其中的每一个关键点进行标注, 使得训练集的初始化工作量大幅减少。未来, 我们将致力于更加高效的目标外观表达方式的研究。