一种改进的快速压缩跟踪算法

潘 磊，束 鑫，祁云嵩

(江苏科技大学计算机科学与工程学院，江苏镇江212003)

目标跟踪，也称视觉跟踪，是计算机视觉领域的一个热点问题，在视频监控、人机交互、视频压缩、行为分析等方面具有广泛的应用价值［1-2］.在跟踪过程中，首先通过人工在视频首帧选择出目标，其次对目标进行建模，然后利用预测或优化算法估计目标的下一帧位置，并对目标模型进行更新，从而进入迭代过程.传统的目标跟踪算法包括确定性方法和统计性方法，两者的代表分别为Mean Shift和粒子滤波.确定性方法计算量小，实时性高，但准确性相对较低;统计性方法计算量大，准确性高，但实时性相对较低［3-4］.

近年来，目标跟踪算法得到了众多的关注和研究.例如，文献［5］中提出一种基于超像素的鉴别外观模型，使用超像素中捕获的结构信息生成目标特征，较好解决了目标遮挡和漂移问题;文献［6］中将目标跟踪表达为结构化多任务稀疏学习问题，对目标遮挡、光照变化、姿态变形等具有较好的效果，并有效降低了粒子滤波计算的复杂度;文献［7］中将图像分割与目标跟踪相结合，采用像素空间与颜色特征，同时解决了跟踪与分割两类问题;文献［8］中提出一种基于压缩感知的跟踪算法，将目标高维特征投影到低维空间，提高了跟踪的实时性，并具有较高的准确性.虽然研究取得了较快的进展，但由于噪声、遮挡、光照、运动等不利因素的影响，解决目标跟踪问题仍然存在许多困难.

1快速压缩跟踪算法

1.1 压缩感知

不完备线性测量信号的重建与高维特征的降维一直是模式识别领域的基本研究方向.压缩感知［9-14］是近年来出现的一种新型采样理论，能够在远远小于奈奎斯特采样频率的条件下还原初始信号，得到了学术界的广泛关注.

高维信号采样的过程可以由式(1)表示:

式中:x为K稀疏的n维原始信号;y为m维的采样信号;Φ为m×n的观测矩阵.根据压缩感知理论，当n≫m时，如果Φ满足有限等距性质(restricted isometry property，RIP)，则采样y可以有很高的概率重建信号x，均匀分布矩阵、随机高斯矩阵、随机贝努利矩阵等都是满足有限等距性质的矩阵，然而，这些矩阵包含的非零元素较多，运算量较大，实际计算时，经常采用以下符合有限等距性质且具有稀疏特征的矩阵，如式(2)所示.

1.2 快速压缩跟踪算法

通过上文描述可以看出，压缩感知技术可以在降低信号维数的同时，基本保留原有信号的全部特性，从而能够在不降低计算精度的前提下，大大提高运算的效率.文献［8］中将压缩感知思想引入目标跟踪领域，首先按照下式构造各向异性的均值滤波器:

式中:w和h为目标的宽和高，将滤波器与目标进行卷积后，生成目标的高维特征，然后使用式(2)的观测矩阵将目标高维特征压缩到低维空间，生成对应的目标低维特征，最后，通过贝叶斯分类器对各候选目标进行分类，选择分类器输出最大值所对应的候选目标作为下一帧中的目标，并更新分类器.

实验中发现，在各向异性均值滤波器的使用中，将模板内的所有像素按照相同的重要性权值进行计算;而实际中，往往是靠近模板中心点的像素应该赋予更高的权值，远离模板中心点的像素赋予较低的权值，并且，当滤波器的尺度超出一定的范围时，滤波产生的新图像已失去原始图像的大部分信息，如图1所示，此时，将这些新图像作为目标特征，效果并不显著.

图1 多尺度滤波效果Fig.1 Results of multi-scale filtering

2 改进的快速压缩跟踪算法

2.1 利用多种多尺度滤波器生成目标高维特征

由上文分析可以看出，单纯使用各向异性均值滤波器产生目标高维特征存在一定的缺陷，不仅降低了模板临近中心点像素的权值，而且超过一定的尺度后，滤波产生的新图像失去了原始目标的大部分特征.针对以上问题，文中提出一种改进的策略，在目标高维特征生成过程中，不仅使用各向异性均值滤波器，同时增加圆形均值滤波器、中值滤波器、高斯滤波器、log滤波器对目标进行滤波，共同生成目标高维特征，并且，在滤波过程中，各滤波器的尺度限制在原始目标尺度的50%范围内，具体如式(4)所示:

式中:x为目标高维特征;F为滤波器;i和j分别为滤波器的宽和高;w和h分别为目标的宽和高;T为目标;符号“*”为卷积;符号“∪”为连接操作，用于将卷积后生成的新图像连接起来生成目标高维特征.

与文献［8］中单纯使用各向异性均值滤波器相比，改进的方法使用了5种滤波器，考虑了对模板像素临近中心点和远离点不同权值分配的衡量，能够对目标特征进行更加准确和全面的描述.通过控制滤波器的尺度，各种滤波器单独产生的滤波图像数量变为文献［9］中的25%，但由于采用了5种滤波器，滤波图像的总数量，即目标高维特征维数不降反升，超出了文献［8］中数量的25%，因此更多的保留了原始图像的信息.

2.2 基于压缩感知理论生成目标低维特征

得到目标高维特征后，采用压缩感知理论生成目标低维特征.文献［9］中证明，对于式(2)，采用ρ=能够获得较快的运算速度，且准确性几乎不会降低.然而，对目标图像经过多尺度滤波后生成的高维特征，n的数量级可以达到106以上，此时观测矩阵Φ中非零元的数量仍然较多.文中采用文献［8］中的方法，令ρ=n/lg n，此时虽然准确性会有所降低，但Φ中非零元的数量得到了指数级的下降，因此计算速度得到显著提升.

当n的数量级为10d时，Φ中非零元的数量约为md，即每行有d个非零元，实际计算时，只需记住这些非零元的位置和数值即可.因此，目标低维特征y的生成速度是相当快的.

2.3 目标与候选目标相似性度量

获得目标与候选目标的低维特征后，下一步的工作就是采用相似性度量比较目标与候选目标之间的差异.文献［8］中通过贝叶斯分类器进行判断，选择分类器最大响应值对应的候选目标作为下一帧的目标.然而，由于在高维特征构造过程中各向异性均值滤波器存在缺陷，分类器的分类效果受到一定的影响.针对此问题，引入Bhattacharyya系数进行改进.

首先，假设候选目标为正负样本的概率相同，采用贝叶斯分类器对候选目标进行分类计算，如式(5)所示.

式中:c+为正样本;c－为负样本.分类器的更新策略按照文献［8］的方法进行.

其次，采用Bhattacharyya系数计算目标与候选目标之间的相似度，如式(6)所示.

式中，y为目标;y^为候选目标;p和q分别为y和y^的概率分布.

得到候选目标的贝叶斯分类器输出及其与目标之间的Bhattacharyya相似度后，以两者的乘积作为目标与候选目标之间最终的相似程度，并选择最大值所对应的候选目标作为下一帧的目标，如式(7)和式(8)所示.

2.4 算法流程

根据以上描述，得到改进的快速压缩跟踪算法流程如下:①根据式(4)计算当前帧目标和下一帧对应位置的δ邻域范围内所有候选目标的高维特征;②利用式(2)的观测矩阵，通过式(1)将①中所有的高维特征投影到低维空间，得到对应的低维特征;③根据式(5～7)计算候选目标与目标之间的相似度，并按照式(8)取相似度最大的候选目标作为下一帧的目标;④更新分类器，进入下一次迭代.

3 实验结果与分析

实验在Intel Core i5 M480CPU，4GB内存的笔记本电脑进行，采用Matlab 2013b编程，测试的6段视频来源于 MILT视频库［15］和 LOT视频库［16］.采用 PASCAL 指标［8，16-17］衡量跟踪算法性能，如式(9)所示.

式中:TB为跟踪算法目标边界框;GT为真实目标边界框.当两者完全重叠时，Pr取值为1，当两者完全不重叠时，Pr取值为0，一般当Pr取值大于0.5时，认为跟踪成功.

改进算法的实验结果包括定性分析和定量分析两个部分.图2～5列举了算法在部分视频库上跟踪的定性结果.表1列举了算法在视频库上跟踪的定量结果以及与常用的 MILT［15］，TLD［18］和FCT［8］算法比较的结果.

由图2～5可以看出，文中提出的改进算法在光照、遮挡、运动、变形等不利因素的干扰下，能够较准确跟踪各种目标.表1中，粗体显示的数字表示对应视频中的跟踪效果最好.从表1的对比可以看出，文中算法与常用跟踪算法相比，在准确率上具有一定的优势，在5段视频的跟踪上取得最高的准确率;TLD算法在最后一个视频中取得最高的准确率.

图2 David序列部分跟踪结果Fig.2 Partial results of tracking David sequence

图3 Football序列部分跟踪结果Fig.3 Partial results of tracking Football sequence

图4 Girl序列部分跟踪结果Fig.4 Partial results of tracking Girl sequence

图5 Faceocc序列部分跟踪结果Fig.5 Partial results of tracking Faceocc sequence

表1 各算法PASCAL指标Table 1 PASCAL index of each algorithm

经分析发现，算法在目标发生较大遮挡、运动和形变时，容易出现跟踪错误的情况.例如，Football视频中从287帧开始，跟踪的目标产生严重遮挡，且遮挡物体的特征与目标的特征几乎完全相似，于是产生跟踪错误，跟踪的目标由原目标转移到了遮挡物体上，如图6所示;Sylv视频中从第896帧开始，跟踪的目标出现较大的运动和形变，跟踪逐步出现误差，直至929帧出现PASCAL指标低于0.5的情况，然而，随着运动与形变的逐渐减弱，从965帧开始PASCAL指标逐步恢复到0.5以上，并重新准确跟踪目标，如图7所示.

图6 Football视频跟踪错误的帧Fig.6 Falsely tracked frames in Football video

图7 Sylv视频跟踪错误的帧Fig.7 Falsely tracked frames in Sylv video

4 结论

根据快速压缩跟踪算法存在的问题，在目标高维特征生成过程中，引入多种多尺度滤波器与原始目标进行卷积，不仅保留了目标尽可能多的信息，并且通过限制滤波器尺度的范围，避免了无效信息对算法的影响，同时，由于多种滤波器的使用，目标有效信息的维数得到了一定的提高，为后续跟踪的准确进行奠定了基础.按照压缩感知理论，经过观测矩阵采样后生成的目标低维特征保留了目标几乎所有的信息，然后通过贝叶斯分类器输出与Bhattacharyya系数乘积的形式，完成下一帧目标位置的计算，在一定程度上抵消了分类器产生的误差.下一步的工作，将围绕高维特征模型展开，解决目前算法对较大遮挡、运动和形变敏感的缺点，这也是目标跟踪领域研究的主要困难之一.

References)

［1］ Li Xi，Hu Weiming，Shen Chunhua，et al.A survey of appearance models in visual object tracking［J］.ACM Transactions on Intelligent Systems and Technology，2013，4(4):58.

［2 ］ Guo Yanwen，Chen Ye，Tang Feng，et al.Object tracking using learned feature manifolds［J］.Computer Vision and Image Understanding，2014，118:128-139.

［3］ 王新红，王晶，田敏，等.基于空间边缘方向直方图的Mean Shift跟踪算法［J］.中国图象图形学报，2008，13(3):586-592.Wang Xinhong，Wang Jing，Tian Min，et al.Mean shift tracking algorithm based on spatial edge orientation histograms［J］.Journal of Image and Graphics，2008，13(3):586-592.(in Chinese)

［4］ 初红霞，谢忠玉，王君祥，等.空间相关背景加权直方图均值漂移目标跟踪［J］.控制与决策，2014，29(3):528-532.Chu Hongxia，Xie Zhongyu，Wang Junxiang，et al.Mean shift target tracking with spatiogram corrected background-weighted histogram［J］.Control and Decision，2014，29(3):528-532.(in Chinese)

［5］ Yang Fan，Lu Huchuan，Yang M H.Robust superpixel tracking［J］.IEEE Transactions on Image Processing，2014，23(4):1639-1651.

［6］ Zhang Tianzhu，Ghanem Bernard，Liu Si，et al.Robust visual tracking via structured multi-task sparse learning［J］.International Journal of Computer Vision，2013，101(2):367-383.

［7］ Papoutsakis K E，Argyros A A.Integrating tracking with fine object segmentation［J］.Image and Vision Computing，2013，31:771-785.

［8］ Zhang Kaihua，Zhang Lei，Yang M H.Fast compressive tracking［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2014，36(10):2002-2015.

［9］ Li P，Hastie T J，Church K W.Very sparse random projections［C］∥Proceedings of the 12th International Conference on Knowledge Discovery and Data Mining，［S.l.］:ACM，2006:287-296.

［10］ Strohmer T.Measure what should be measured:progress and challenges in compressive sensing［J］.IEEE Signal Processing Letters，2012，19(12):887-893.

［11］ Qaisar S，Bilal R M，Iqbal W，et al.Compressive sensing:from theory to applications，a survey［J］.Journal of Communications and Networks，2013，15(5):443-456.

［12］ Engelberg S.Compressive sensing［J］.IEEE Instrumentation ＆ Measurement Magazine，2012，15(1):42-46.

［13］ Donoho D L.Compressed sensing［J］.IEEE Transactions on Information Theory，2006，52(4):1289-1306.

［14］ Friedland S，Li Q，Schonfeld D.Compressive sensing of sparse tensors［J］.IEEE Transactions on Image Processing，2014，23(10):4438-4447.

［15］ Babenko B，Yang M H，Belongie S.Robust object tracking with online multiple instance learning［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2011，33(8):1619-1632.

［16］ Shaul O，Aharon B H，Dan L，et al.Locally orderless tracking［J］.International Journal of Computer Vision，2014.

［17］ Everingham M，Gool L，Williams C，et al.The Pascal visual object classes(VOC)challenge［J］.International Journal of Computer Vision，2010，88(2):303-338.

［18］ Kalal Z，Mikolajczyk K，Matas J.Tracking learning detection［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2012，34(7):1409-1422.