基于Struck的在线学习和相似度匹配的双重更新跟踪算法

3

(1.山东科技大学 电气与自动化工程学院，山东 青岛 266590； 2.山东省机器人与智能技术重点实验室，山东 青岛 266590；3.山东大学 控制科学与工程学院，山东 济南 250061)

视觉目标跟踪不仅是人工智能应用中不可或缺的技术手段，同时也是计算机视觉发展的重要一环。虽然广泛应用于人工智能机器人、航空航天技术、智能视频监控、医学影像处理、智能交通系统和虚拟现实等多种技术平台[1]，但研究人员依然面临视频序列中对图像目标处理的局部或全部遮挡(occlusion，OCC)、照明变化(illumination variation，IV)、比例变化(scale variation，SV)、变形(deformation，DEF)、运动模糊(motion blur，MB)、快速运动(fast motion，FM)、平面内旋转(in-plane rotation，IPR)、平面外旋转(out-of-plane rotation，OPR)、背景杂波(background clutter，BC)、超出视野(out of view，OV)、低分辨率(low resolution，LR)等公认复杂场景的挑战[2-3]。

目标跟踪的方式通常是在图像序列的初始帧以矩形框的形式对目标位置和大小进行人工标定，之后跟随目标的运动而跟踪目标，并记录位置信息。近年来，解决视觉目标跟踪的问题基本上有两种思路：第一种思路是依赖于跟踪目标的先验知识，对目标进行建模，之后在测试的序列中找到相对应的目标，既可以使用单一特征，也可以采用多特征叠加，这其中包括目标的边缘、形状、色彩、轮廓、纹理和光线等视觉特征[4-5]，直方图(如灰度、颜色等)和图像矩的统计特征、代数空间特征(K-L变换)、尺度不变特征(scale invariant feature transform, SIFT)等[6]，也是当下主流的算法思想；第二种思路是不依赖于目标的先验知识，直接对测试序列进行运动检测，将目标从变换的背景图像中识别出来，并检测目标位置达到跟踪的效果，参照被检测物与摄像机之间的关系，可以分为静态背景下的目标跟踪和动态背景下的目标跟踪。

Struck算法依赖目标的先验知识对目标进行跟踪[7-9]。示例观察发现，Struck算法在遇到遮挡，特别是目标被完全遮挡时，学习者会将遮挡物的负样本纳入到学习框架中，从而失去对目标的有效判断。示例观察还发现，丢失目标后，矩形框位置将不再发生变化，当目标再次移动到矩形框所在位置时，根据学习者正样本的累计训练，跟踪器方能继续跟踪目标，从而验证了跟踪器在丢失目标后不能主动进行目标检测的问题。当相同或类似的遮挡物再一次出现在目标的矩形框中，可能是遮挡目标，也可能是作为背景被目标小范围遮挡时，跟踪器同样会丢失跟踪目标。这是因为遮挡物在遮挡目标的时候学习者将遮挡物作为正样本学习了一部分，使得跟踪器误认为是目标，从而再次发生目标丢失问题。本研究引入相似度匹配更新策略，与Struck算法的在线学习更新策略相结合，得到基于Struck的在线学习和相似度匹配的双重更新跟踪算法(下文中简称双重更新跟踪算法)，以适应目标被完全遮挡的场景，在目标丢失后能够依据相似度匹配的方式重新搜索到目标，并继续完成跟踪。

1 Struck算法的在线学习更新

Struck算法在图像序列中使用Haar特征[10-12]提取目标特征，通过在线学习的方式不断更新目标的特征数据，并使用结构化支持向量机[13-16]对数据样本做出最优分类，能够适应IV、MB、IPR、LR等场景，但对OCC、OV、SV、DEF场景的适应性不够理想。其在线学习更新过程为：

1) 通过一个预测函数f:χ→γ对帧间转换进行直接估计，对目标图像块做标签(x,y)，其中x是样本，y是目标期望的转换。建立一个判别函数

F(x,y)=〈w,Φ(x,y)〉

(1)

用于评判目标与学习后正样本的相似度，其中Φ(x,y)是联合内核映射(输入空间到特征空间的一种转换)。预测目标的位置函数定义为：

(2)

其中，跟踪目标的位置更新为pt=pt-1(yt)。

2) 在给定的目标集合中，寻找超平面的最优目标函数为：

(3)

3) 基于目标边界框重叠度定义损失函数：

(4)

4) 设计存储系数

(5)

5) 通过使用拉格朗日公式的对偶性以及参数化将公式(3)简化为：

(6)

(7)

2 相似度匹配更新

选择Haar特征为特征描述算子表示图像，使用边缘特征模板对灰度化的图像进行处理，将模板中的白色矩形区域的像素和减去黑色矩形区域的像素和，计算得出目标图像块的特征值，并保存初始模型的特征值。定义一个基于Haar特征检测目标区域与初始模型的相似函数

(8)

其中，T0是初始模型目标区域特征值，Tz为当前帧目标区域特征值。

在获得目标的位置估计后，将目标位置所在的图像块根据相似函数计算得到的值，与初始模型的特征进行相似度判别，符合阈值要求的图像块作为正样本，添加到在线学习对正样本的学习过程中。由于样本使用的是在线学习的方式，所以最初的正样本仅仅是一个初始模板，随着图像序列一帧帧的跟进，每帧中符合阈值要求的图像块都被当作正样本加入到学习过程中。因为图像序列中连续帧之间的目标是缓慢变化的，在线学习的方式也具有渐进性，相邻帧间的目标变化较小，特征的差异也不大，所以在学习过程中容易受到影响，从而易使正样本的学习偏离原来的目标。这就是Struck算法在遇到遮挡后不能再次搜索到目标的原因，也是设立相似函数的目的。通过相似函数计算当前帧的目标相似度，可以避免跟踪目标的特征在学习中与初始目标的特征出现较大差异，不至于因渐进的学习而造成负样本的误学习，保证了正样本学习的稳定性，对目标的判断始终保持一个高度相似的水平，进而能够稳定跟踪目标。

阈值的选取可自由设定，根据公开数据集的测试结果，选取80%作为设定的阈值可以取得最佳的效果。当η≥80%时，作为正样本被学习者学习；当η<80%时，不作为学习者的正样本更新。当连续5帧的目标都丢失后，在下一帧图像中采用滑动窗口的形式，遍历搜索目标图像所在位置，以相似度判别为依据，在自设的搜索半径内搜索相似度η≥50%的矩形框，选择其中相似度最高的图像块作为目标继续跟踪。这里阈值选择为50%是因为弱分类器在对目标进行判别时，概率一般选取为大于50%，为了更好地寻找目标位置，设置了相对较低的阈值，放宽对目标搜索的条件。经过大量的视频序列测试，选择相似度η≥50%的矩形框作为候选目标框的分类标准，便可以判断目标所在位置。但同样可能出现误判的情况，比如在球场上对球员的跟踪，球员身着统一的服装，对整个球员跟踪的话，相同队内的成员之间特征值的差异比较小。但这并不影响对目标的跟踪，因为在放宽条件的情况下找到目标后，依然如上述步骤与初始模板的特征进行比较。如果出现误判，那么在接下来的5帧图像中，正样本不会被更新，将再次重新搜索目标，以达到对目标的循环搜索。如果搜索完成后没有满足相似度要求的图像块，视为没有发现目标，对下一帧图像继续做遍历搜索处理，直到找到目标或者到达图像序列最后一帧图像为止。双重更新跟踪算法的流程如图1所示。

算法:双重更新跟踪算法输入:图像序列并在首帧标定目标位置根据判别函数F预测第t帧目标位置yt计算yt位置图像块的相似度ηif η≥80%then 对正样本进行在线学习并输出目标位置else 停止更新正样本并输出上一帧目标位置if 连续5帧不更新正样本then 对下一帧图片进行遍历搜索目标end ifend if

图1 双重更新跟踪算法流程

Fig.1 Process of dual update tracking algorithm

由于Struck算法的速度较慢，对其跟踪框架进行整体优化。Struck算法的在线学习更新需要不断学习正样本来适应目标的特征变化，对支持向量的需求比较大，通常设为100。虽然Struck算法中限制了支持向量的无限增长，但仍然允许保持相当的数量，从而降低了算法的跟踪速度。而本研究设计的相似函数和在线学习作为双重更新策略，不需要很多的支持向量来维持在线学习中正样本的有效性，减少了跟踪框架中对支持向量的需求，支持向量个数设为50，为程序的运行释放出更多的缓存空间。在对图像进行遍历搜索时，滑动窗口由1×1像素扩大为3×3像素，步长为1个像素，目的在于弱化边缘像素点的特征，强化中心点的特征。滑动窗口只有1个，输出的通道数为1。在对图像的特征提取时，Haar特征首先对图像进行灰度化处理，弱化颜色特征对目标辨识的影响，输入的通道数由原来的RGB颜色空间的3通道减少为灰度图像的1通道。通过设计相似函数改变参数设置，从而达到提高双重更新跟踪算法运行速度的目的。

3 测试和实验分析

3.1 测试环境

测试的硬件环境为64位Intel CORE i7 3.4 GHz处理器和16 GB内存的计算机，调试实验的软件平台为Visual Studio 2013，程序用C++语言编写。测试结果所用的Girl视频图像序列来源于OTB100的公开数据集，Cup视频图像序列是以课题组实验室为背景自行拍摄的数据集。

3.2 定性分析

为了直观地展示两种算法的跟踪表现，将实验序列的跟踪表现进行对比，其结果如图2所示，代表双重更新跟踪算法，灰色代表Struck算法。

由图2可以看出，在室外场景中，Girl视频(640×480)存在SV、OCC、BC、DEF、LR等复杂场景，目标小女孩在被成年人完全遮挡时，目标在视频中消失，双重更新跟踪算法在目标特征明显出现时，可以再次捕捉到目标位置并继续跟踪。而Struck算法目标被遮挡时已经丢失目标，其正样本的在线学习过程中引入了负样本的误学习。在室内场景中，Cup视频(1 280×720)存在SV、OCC、LR、MB等复杂场景，目标杯子在运动的过程中，遇到障碍物对其完全遮挡，消失于图像范围之内，当目标具有的明显特征再次出现时，双重更新跟踪算法能够重新捕捉到目标，并继续跟踪。而Struck算法在遮挡时丢失目标，当目标再次出现时不能自动寻找到目标，只有在目标重新出现在丢失位置时，才能继续跟踪，对于实际跟踪的场景中具有很大的局限性。

3.3 定量分析

为了更直观地对比两种算法的跟踪性能，对视频序列进行了成功率、跟踪速度和中心位置误差的对比。此处，成功率是指成功跟踪到目标的帧数与图像序列总帧数的比值。

从表1可以看出，双重更新跟踪算法的跟踪成功率均比Struck算法要高，在全部遮挡的Girl视频序列中，比Struck算法高出41.5%。在长时间遮挡的Cup视频序列中，虽然双重更新跟踪算法成功率只有81%，但在总共100帧的序列中目标杯子有13帧被完全遮挡，没有杯子的明显特征，不能跟踪目标。从表1中可以看出，双重更新跟踪算法比Struck算法在Girl视频序列中快7.7 FPS，在Cup视频序列中快8.3 FPS，通常人的视觉感官对于视频的播放速率要求在15 FPS以上，双重更新跟踪算法可以满足实时性的要求。

图2 视频序列的测试结果

目标跟踪算法跟踪成功率/%Girl序列Cup序列跟踪速度/FPSGirl序列Cup序列Struck算法54.536.019.418.2双重更新跟踪算法95.081.027.126.5

跟踪过程中的目标偏移程度如图3所示。Girl视频序列中，Struck算法在120帧处,由于遮挡的原因已经跟踪失败，当目标被完全遮挡再次出现在视野中时，不能恢复对原目标的跟踪；双重更新跟踪算法利用双重更新策略，可以继续跟踪目标。Cup视频序列中，从第26帧到48帧目标被完全遮挡，消失在视野中，两种算法均无法捕获目标特征，在第54帧目标再次出现并具有明显特征时，双重更新跟踪算法可以再次获取目标位置，继续跟踪目标；而Struck算法仅在第90帧目标重新运动到被完全遮挡前的位置时，才可以继续跟踪目标。

图3 双重更新跟踪算法与Struck算法视频序列中心位置误差对比

4 结论

本研究的双重更新策略目标跟踪算法是对结构化内核框架跟踪算法的改进，通过增加初始模型特征值相似度匹配与样本的在线学习作为双重更新策略，降低了非目标物对正样本学习的影响，增强了正样本模板学习的有效性。通过对公开数据集和实际拍摄数据集的测试结果表明，双重更新跟踪算法可以有效的处理MB、SV、OCC、BC、OV、LR等跟踪方面的复杂场景，并在该类场景下具有较小的跟踪误差，特别是对于目标被严重遮挡的场景，能够重新搜索到目标位置并继续跟踪。虽然双重更新跟踪算法取得了良好的效果，但在DEF等场景中仍需进一步改进，而且跟踪速度有所降低的问题也需要解决，这是下一步研究的方向。