在线判别式超像素跟踪算法

刘雨情， 肖 嵩， 李 磊

(西安电子科技大学 综合业务网理论及关键技术国家重点实验室，陕西 西安 710071)

基于视频序列的目标跟踪技术，一直以来都是计算机视觉领域的核心问题，在智能交通、军事航天以及人机交互领域都有着广泛的应用．国内外学者通过不断研究也提出了许多有效的目标跟踪算法[1-5]．

近年来，超像素特征作为一种新兴的中层视觉特征，被广泛研究和应用于各种计算视觉任务中，如图像分割、人体姿态估计和目标识别等．2014年，文献[5]将超像素用于目标跟踪中，提出了一种鲁棒性的超像素跟踪(robust SuperPixel Tracking，SPT)算法．该算法能出色解决目标跟踪中的挑战性难题，如复杂背景、非刚性形变和快速运动等，并在PASCAL VOC tests上取得了比跟踪学习检测(Tracking Learning Detection，TLD)算法[3]、视觉跟踪分解(Visual Tracking Decomposition，VTD)算法[7]等主流目标跟踪算法更好的跟踪性能．但由于该算法每次在更新外观模型时积累了海量的超像素信息(平均达上千个)，采用MeanShift方法进行聚类对外观建模非常耗时，达不到实时性要求．此外，该算法在目标遮挡时易出现跟踪漂移，具有一定的局限性．

1 在线判别式超像素跟踪方法

针对SPT[5]算法建模速度慢的缺陷，笔者提出了一种新的表观模型构建机制，创新性地将超像素特征和超限学习机相结合，用于处理超大样本集的快速特征学习问题，将收集到的大量带标签的目标前景-背景数据集结合超限学习机的监督型学习算法，训练得到一个超像素前景-背景分类器，实现前景-背景粗分类．在此基础上，结合k-d树实现快速K近邻(K-Nearest Neighbor，KNN)聚类，对前景和背景特征空间进行细分割，精确构建目标前景和背景的外观模型(即特征词典)．笔者所改进的这种从粗到精的前景-背景建模方法显著降低了表观建模的时间开销，将每次模型构建时间从原来的几十秒控制在 1 s 以内．最后，算法结合粒子滤波和相关滤波实现了鲁棒性的目标跟踪．文中所提算法的框架如图1所示．

图1 目标跟踪方法训练和跟踪过程框架图

1.1 基于超像素分割的目标前景和背景特征提取

由于颜色统计特征在目标发生非刚性形变、旋转和快速运动时具备不变性，但不具备光照不变性．而方向梯度直方图(Histogram of Oriented Gradient，HOG)特征对光照、尺度等具备不变性，但却不适应非刚性形变和快速运动．文中算法将颜色统计特征和HOG特征相结合，取得对目标更强的描述能力．

设第t帧目标的状态St={Xt,Yt,Wt,Ht}，其中，{Xt,Yt}表示目标的中心位置，{Wt,Ht}表示目标的宽和高．在训练阶段如图1(a)所示，收集前几帧的目标和背景信息，然后将每个训练帧分割为Nt个超像素s(r,t)，r=1,2,…,Nt，其中，s(r,t)为第t帧的第r个超像素．统计每个超像素中属于目标框和不属于目标框的像素个数，将与目标框重合的超像素标记为前景,其余情况全部标记为背景．第r个超像素的标签l(r)可表示为

(1)

在得到超像素信息后，提取每个超像素的颜色特征构成该超像素块的特征．

1.2 构建前景-背景特征词典

针对SPT[5]算法建模耗时大的问题，笔者用超像素特征训练超限学习机学习前景和背景表观特征，结合KNN聚类减少建模耗时．文中所提算法在跟踪中对一定区域内的超像素依据训练好的超限学习机进行前景-背景特征的分类，之后，依据超像素块的置信值来收集超限学习机的更新训练数据．

1.2.1 训练超限学习机

超限学习机(Extreme Learning Machine，ELM)[6]是一种含单个隐藏层的前馈型神经网络，在1.1节中通过超像素分割和特征提取获得大量带有标记的超像素训练样本(Xj,tj),j=1,2,…,N，Xj= (x1,x2,…,xn)T∈Rn，为提取的超像素特征向量，tj为每个特征对应的类别．假设隐藏层节点数为L，需训练得到一个超限学习机最小化网络预测标签与训练数据标签间的差值:

其中，σ1>0，σ2>0，u，v=2，H为隐藏层输出矩阵(随机初始化的矩阵)，β为隐藏层与输出层的连接权矩阵．网络的前向预测输出fL(X)为

(3)

其中，ai为隐藏层神经元的输入权值，bi为偏置，βi为隐藏层与输出层的连接权值，Gi(·)为隐藏层神经元的特征映射函数．例如，在映射函数为径向基函数的情况下，隐藏层节点的响应为

(4)

在目标跟踪的初始训练阶段，由于在训练样本集中采用区域规划策略采集到大量的负样本，冗余的负样本会影响ELM的分类性能．为此在训练过程中采用困难负样本挖掘策略将负样本分组，每次迭代求解ELM时仅将后一组中的假正样本加入到前面组组成的背景特征集，学习到更具区分性的负样本集，从而提高超限学习机的分类准确率．

1.2.2 KNN聚类

在收集到目标表观特征池，Ft= {s(i,t)|l(i)=1}，Fb= {s(i,t)|l(i)=0} 的基础上，在特征池内部采用k-d树实现快速KNN聚类，分割前景和背景特征空间，构建带置信度的前景-背景特征词典．在聚类中将近邻的参数设置为常数(近邻的参数设置过高会降低跟踪的准确度，过低会影响算法的实时运行速度，为了兼顾跟踪的速度与准确度，通过大量实验仿真将近邻的参数设置为经验值10)，并将距离小于固定值的近邻聚为一类．记C(j)为每类的置信度，则有

C(j)=S+(i)-S-(i)S+(i)+S-(i) ，i=1,2,…,Nt,(7)

其中，S+(i)和S-(i)分别为属于和不属于目标框的像素数．在特征空间中，与目标框重合度高的类其前景置信度就越高(置信值越趋近于1)；相反，与目标框重合度低的类其背景置信度就越高(置信值越趋近于 -1)．

1.3 目标位置估计

跟踪过程中，文中算法在一定的搜索区域Pt内，依据目标的大小变化先进行变尺度超像素分割，搜索区域Pt以{Xt-1,Yt-1}为中心，以λd{Wt-1,Ht-1}为大小．随后提取每个超像素的特征并输入到超限学习机，对超像素进行前景-背景分类，之后，通过模块匹配快速找到其最近邻和所属的类j．每个超像素的前景-背景置信度由其所属类的置信度C(j)和其最小类内距计算得出，即

(8)

∀l=1,2,…,N．(9)

1.4 目标尺度估计

(10)

在频域表示内，对式(10)中的H进行逐元素求偏导，最终得所需滤波器H*的解析解为

(11)

在当前目标中心位置{Xt,Yt}处，利用所得相关滤波器搜索目标的尺寸，搜索尺寸设置为尺度金字塔的m个尺度级数．当新的一帧到来时，提取不同尺度目标图像块的HOG特征并求得其频域为Z，利用得到的滤波器计算每个尺度的相关响应，求得相关得分为

yi=F-1(H*⊙Zi) ,i=1,2,…,m．(12)

从中将响应值最大的尺度和粒子滤波的结果进行加权处理后，作为当前帧的尺度S，后续依据固定的学习速率对滤波器进行更新．

2 实验分析

文中所提算法仿真的实验环境配置为3.30 GHz Intel(R) Core(TM)i3-3220 CPU的台式机，软件环境为Matlab R2016b (64 bit)．

(1) 算法耗时分析．文中选取4个典型的视频序列，通过平均聚类样本数、外观建模时间和平均跟踪速度3项对比分析了SPT[5]算法和文中所提算法，具体数据如表1所示．SPT[5]算法在4个视频序列中聚类的样本数每次均达到 4 000 以上，每次的聚类耗时最少的为Bird2序列达到了 22.68 s．SPT[5]算法在外观模型聚类上的耗时导致算法每帧的跟踪用时至少为 2 s，达不到实时要求．文中所提算法将表观建模时间降至 1 s 以内，每帧的处理时耗降至 0.15 s 左右，显著提高了目标跟踪的速度．

表1 算法时间性能对比分析表

(2) 算法性能验证．SPT[5]算法针对12个测试视频进行了性能分析，由于原算法需由作者根据视频序列目标的运动信息预先人工设定不同的运动参数(共6个)，所以笔者基于这12个视频序列和原算法以及一些主流跟踪算法进行比较，包括TLD算法[3]、核结构输出(Structured output kernels，Struck)算法[1]、VTD算法[7]．算法针对各个测试视频的跟踪性能采用中心位置误差(Center Location Error，CLE)和成功跟踪帧数(Successfully Tracked Frames，STF)指标表示，其中，CLE表示跟踪算法预测出的目标中心与真实目标中心的像素距离值在每个序列上的平均值，STF表示序列中跟踪算法预测出的目标框与真实目标框的重合率在50%以上的总帧数．

由表2可知，文中所提算法在9个测试视频上具有稳定的跟踪效果，且算法的总体平均性能优于TLD算法[3]、Struck算法[1]和VTD算法[7]的性能．

表2 算法对于测试视频序列的CLE、STF性能指标

(3) 算法性能分析．为了进一步验证算法的性能，选取另外一些测试视频并将算法与一些跟踪算法进行了跟踪结果的比较，部分视频序列的跟踪结果如图2所示．比较算法包括TLD算法[3]、稀疏联合模型(Sparsity-based Collaborative Model，SCM)算法[8]和核关联滤波(Kernelized Correlation Filters，KCF)算法[4]．

图2 不同算法的跟踪结果

3 结 束 语

笔者在超像素分割的基础上提出了一种新的目标跟踪算法，算法利用超像素分割和特征提取分别获取大量前景和背景模板，之后利用ELM和KNN聚类分别构建目标和背景的判别式外观模型，实现前景和背景建模的分离，并结合粒子滤波得到目标的最优位置；最后，结合相关滤波策略对目标进行尺度估计．在大量测试视频序列上，通过定量的实验分析，证明了文中所提算法在处理速度上优于原算法，并针对目标的遮挡、快速移动、形变以及尺度变化，均具有良好的鲁棒性．

[1] HARE S, GOLODETZ S, SAFFARI A, et al. Struck: Structured Output Tracking with Kernels[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2016, 38(10): 2096-2109.

[2] 张浪, 侯志强, 余旺盛, 等. 利用快速傅里叶变换的双层搜索目标跟踪算法[J]. 西安电子科技大学学报, 2016, 43(5): 153-159.

ZHANG Lang, HOU Zhiqiang, YU Wangsheng, et al. Two-level Searching Tracking Algorithm Based on Fast Fourier Transform[J]. Journal of Xidian University, 2016, 43(5): 153-159.

[3] KALAL Z, MIKOLAJCZYK K, MATAS J. Tracking-learning-detection[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 34(7): 1409-1422.

[4] LI Y, ZHU J. A Scale Adaptive Kernel Correlation Filter Tracker with Feature Integration[C]//Lecture Notes in Computer Science: 8926. Heidelberg: Springer Verlag, 2014: 254-265.

[5] YANG F, LU H, YANG M H. Robust Superpixel Tracking[J]. IEEE Transactions on Image Processing, 2014, 23(4): 1639-1651.

[6] KWON J, LEE K M. Visual Tracking Decomposition[C]//Proceedings of the 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Piscataway: IEEE, 2010: 1269-1276.

[7] TANG J, DENG C, HUANG G B. Extreme Learning Machine for Multilayer Perceptron[J]. IEEE Transactions on Neural Networks and Learning Systems, 2016, 27(4): 809-821.

[8] ZHONG W, LU H, YANG M H. Robust Object Tracking via Sparsity-based Collaborative Model[C]//Proceedings of the 2012 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Piscataway: IEEE, 2012: 1838-1845.