带权分块压缩感知的预测目标跟踪算法

罗会兰钟宝康孔繁胜

①（江西理工大学信息工程学院 赣州 341000）

②（浙江大学计算机科学技术学院 杭州 310027）

带权分块压缩感知的预测目标跟踪算法

罗会兰*①钟宝康①孔繁胜②

①（江西理工大学信息工程学院 赣州 341000）

②（浙江大学计算机科学技术学院 杭州 310027）

针对矩形跟踪框在边缘处包含较多背景信息的问题，该文提出一种基于规范化梯度特征的带权分块压缩感知的目标特征提取方法。该方法将压缩感知测量矩阵转化为分块对角矩阵，且根据块的重要程度分配适当的权重，缩小测量矩阵规模，简化特征提取运算，弱化背景干扰。然后将提取的特征输入变先验概率的贝叶斯分类器，变先验概率的分类器充分利用已有的跟踪结果，从一定程度预测了目标的运动方向，减小候选目标的分类歧义性，使得每一帧的分类函数根据以往跟踪结果进行变化，提高了分类的准确度。实验在8个具有常见跟踪难度的序列中测试，并与目前较流行的4种目标跟踪算法在跟踪效果、成功率等方面进行比较，结果从多个角度表明，该文提出的目标跟踪算法具有较高的准确度和稳定性。

目标跟踪；分块压缩感知；贝叶斯分类器；变先验概率

1 引言

运动目标的跟踪是计算机视觉领域的核心问题［1］。由于目标变化的复杂性（如姿态、光照、遮挡、运动模糊等），给运动目标跟踪带来很大挑战。目前，目标跟踪问题一般采用3种思路解决：基于逐帧检测［24］-、基于预测［5，6］以及两者相结合［7］。

基于逐帧检测的目标跟踪算法在跟踪过程中有两个关键问题：样本特征的准确提取和分类器的设计。在样本特征提取方面，文献［8］发现在封闭目标的梯度空间图上，尽管目标发生形变、光照等变化，只要将目标归一化到相同的尺度，它们就变得惊人地相似，于是提出一种准确描述封闭目标的规范化梯度特征（Normed G radient， NG），应用于目标检测，取得非常好的效果。但是，目标跟踪与目标检测不同，目标跟踪要求对每一帧的检测都是实时进行的，且目标模型需要不断更新，因此目标跟踪中提取的特征应尽量简单有效。文献［8］提出的规范化梯度特征数量较多，这就需要对特征进行有效压缩，虽然文献［4］提出一种压缩感知方法用于压缩目标特征，但是由于图像本身信息量大，导致压缩感知中测量矩阵规模较大，运算复杂。文献［9］提出一种分块压缩感知方法可以使测量矩阵变成分块对角矩阵，在后续的感知过程中只需用小块的测量矩阵感知信号，通过这种方法可以使测量矩阵的规模迅速减小。在分类器设计方面，文献［4］采用简单有效的朴素贝叶斯分类器对候选目标的压缩特征进行分类，取得较好的分类效果，但是在使用朴素贝叶斯分类器的过程中简单地认为候选区域的目标和背景先验概率相等，忽略了候选目标先验概率对分类的影响，没有充分利用先验知识进行分类。

基于预测的目标跟踪算法，是根据已有跟踪结果利用数学知识直接求解目标位置。比如基于1e范式最小化的目标跟踪（L1）［5］，把目标跟踪问题当成稀疏逼近问题，在粒子滤波框架下将噪声、遮挡和其他跟踪难点当成碎片模板，然后将候选目标用目标模板基和碎片模板基进行稀疏表达，最后通过1e范式最小化求解，将最小错误投影当作目标位置，从而实现目标位置的预测。文献［7］中的跟踪学习检测（Tracking-Learning-Detection， TLD）算法则是结合了预测和检测算法，巧妙地把跟踪、学习、检测结合在一起。在运动目标部分可见的情况下，用跟踪器来预测目标在连续帧间的运动。检测器部分为一个高效的级联分类器，使用简单有效的图像特征对目标进行实时的检测，同时在必要的情况下纠正跟踪器。学习模块评估跟踪器和检测器的性能，通过生成有效的训练样本完成检测器的更新，消除检测器误差。虽然文献［5， 7］利用了已有的跟踪结果，但是对目标预测的计算都非常复杂，难以达到实时性的要求。

本文提出一种基于规范化梯度特征的带权分块压缩感知方法用于特征提取。给规范化梯度特征的每一分块分配权重，以减小边缘处背景信息干扰特征的影响。由于在大部分情况下，越靠近矩形框中心位置背景信息越少，因此权重的大小可以使用高斯分布，使得权值从矩形框中心位置向边缘处逐渐减小。这样提取的特征可以弱化背景干扰，提高特征的准确度。同时，本文提出一种基于线性贝叶斯分类器的变先验概率方法，用于分类器的设计，与文献［4］中判别目标和背景的线性贝叶斯分类器不同，本文提出的算法并不是默认候选目标先验概率相等，而是通过对已有的跟踪结果学习得到候选目标的先验概率。本文提出的变先验概率的贝叶斯分类器能充分利用已有的跟踪结果，增强分类器的分类准确性。在8个具有挑战性的视频序列上（其中5个是文献［3］中提供的标准测试序列；另外3个来自文献［10］）与4种目前较先进的算法进行比较，实验结果表明本文提出的带权分块压缩感知的预测目标跟踪算法能够弱化背景干扰，减小特征的歧义性。同时，基于跟踪结果的变先验概率计算能够增强分类的可信度，达到准确跟踪目标的目的。

文章的第2节详细论述了本文提出的算法，接下来是实验结果及分析，最后是结论。

2 带权分块压缩感知的预测目标跟踪算法

本文提出了一种基于规范化梯度特征和带权分块压缩感知的预测目标跟踪算法。通过对封闭目标具有准确表示的规范化梯度特征进行分块，然后给每一分块分配权重，提出基于规范化梯度特征的带权分块压缩感知特征提取方法，降低压缩感知测量矩阵规模，弱化背景干扰。在分类阶段，根据先前候选目标的反馈结果，提出一种变先验概率的贝叶斯分类器，用于预测目标运动方向，增强分类准确度。为方便描述，将本文提出的带权分块压缩感知的预测目标跟踪算法命名为带权分块压缩感知的预测目标跟踪算法（Tracking using Weighted B lock Compressed sensing and location Prediction，TWBCP）。

2.1 基于NG特征的带权分块压缩感知

文献［8］中指出在封闭目标的梯度空间图上，将图像规范化到相同的尺寸，目标非常相似，基于此提出规范化梯度（Norm ed G radient， NG）特征用于封闭目标检测。由于图像在梯度空间上是稀疏的［11］，因此可以对梯度空间特征进行压缩感知，降低特征维数。文献［9］采用相同的高斯测量矩阵对分块图像进行感知，提出一种分块压缩感知（B lock Compressed Sensing， B lock CS）方法，这种方法使得测量矩阵变成分块对角矩阵，在感知过程中只需利用小块的测量矩阵进行测量即可，能迅速降低测量矩阵的规模。考虑到在目标跟踪问题中，大多数目标都具有良好的封闭性，本文提出一种基于NG特征的带权分块压缩感知方法用于特征提取。

由于跟踪的目标常常是不规则的，矩形跟踪框边缘处通常包含较多背景信息。把背景特征当成目标特征进行学习会影响学习的准确性，并且会降低对于背景变化的鲁棒性，影响跟踪效果。因此，在基于NG特征的分块压缩感知特征提取阶段，给每个NG特征块进行权重分配。考虑到通常情况下越靠近跟踪框中心位置，背景信息越少，在分配权重时，给中心位置分配较大的权重，而边缘位置分配较小的权重，以弱化边缘处背景的干扰。将NG特征分成L块，第k块的权重函数定义为

式（2）中（corex，corey）和（kx， ky）分别表示分块的NG特征按照从左到右、从上到下的顺序生成的2维中心块位置坐标和第k块位置坐标。（σx，σy）表示（kx， ky）离中心块位置（corex，corey）的标准差。根据式（2）的定义，离中心块位置越近的块权重越大，表明其对特征的贡献越大，反之越小。通过给边缘处不重要的块分配较小权重，中心处重要的块分配较大权重的方法，可以减轻边缘处的背景信息对目标特征提取的干扰。

于是，基于NG特征的带权分块压缩感知特征计算为

2.2 变先验概率的贝叶斯分类器

将式（4）代入文献［12］提出的线性贝叶斯分类器整理得，第t帧第n个候选目标变先验概率的贝叶斯分类判别函数为

式（6）的分类函数表明，该分类函数在每一帧都会根据先前跟踪结果进行变化。对于每一个候选目标而言，如果正样本先验概率越大，分类函数中后半部分越大，从而影响候选目标的分类函数的值。式（6）定义的变先验概率的贝叶斯分类器在某种程度上有根据以往跟踪结果预测目标运动方向的作用，例如当目标向下运动时，会导致在目标下方的候选目标先验概率集体增大，从而使得分类器具有运动方向预测作用。通过式（6）计算的分类得分很好地结合了本帧检测和预测的结果。

2.3 算法流程

带权分块压缩感知的预测目标跟踪算法流程图如图1所示，算法在每跟踪一帧图像后都要重新更新相关参数，更新跟踪参数使跟踪算法能够适应目标状态的变化。在跟踪当前帧的过程中，先计算候选目标的带权分块压缩感知特征，然后将该特征输入变先验概率的贝叶斯分类器计算候选目标的分类得分。在所有候选目标分类得分计算完成后，取得分最大的候选目标作为本帧目标位置，完成本帧目标跟踪。

3 实验结果与分析

在8个具有代表性的数据集（序列）上实验比较了本文提出的算法（TWBCP）与目前比较流行的4种目标跟踪算法：多示例学习（M u ltip le Instance Learning， M IL）［3］、压缩跟踪（Com pressive Tracking，CT）［4］、基于1e范式最小化的目标跟踪（L1）［5］和跟踪学习检测跟踪（TLD）［7］。本文提出的跟踪算法TW BCP与多示例学习（M IL）［3］跟踪算法都是通过训练好的分类器判别候选目标的得分，选取得分最大者作为本帧跟踪位置，与M IL算法不同，本算法计算了候选目标位置的先验概率，使得分类器对候选目标位置具有记忆性，增强分类能力。在压缩感知方面，与CT算法不同，本算法采用分块的压缩感知方法减小了感知矩阵的规模，特征的提取比CT算法更简单有效。基于预测的目标跟踪算法（L1）以及基于检测与预测结合的目标跟踪算法（TLD）都是对目标具体位置进行预测，而本文提出的算法是通过候选目标位置的先验概率预测目标的运动方向。

3.1 实验数据集及参数设置

为了验证本文提出算法的有效性和稳定性，选择8个具有代表性的视频数据集进行测试。其中david， dollar， faceocc， faceocc2和surfer是文献［3］中提供的标准数据集；boy， mhyang和fish数据集来自文献［10］。这些数据集包含多种目标跟踪难点，如目标姿态变化、光照变化、遮挡、背景混乱、运动模糊、摄像头抖动等。

图1 带权分块压缩感知的预测目标跟踪算法流程图

3.2 跟踪效果比较

将本文提出的算法（TWBCP）与压缩跟踪（CT）、多示例学习（M IL）， TLD跟踪（TLD）和基于1e范式最小化的目标跟踪（L1）算法的跟踪结果绘制于每一帧图像，在dollar， faceocc2， faceocc和fish序列上的跟踪定性比较结果如图2所示。在算法的跟踪结果中如果出现跟踪丢失的现象，则跟踪框不显示在图像上。

图2 遮挡、光照变化对跟踪结果的影响

图2（a）dollar序列包含一个与目标非常相似的物体，由实验结果可知，本文提出的TWBCP算法在第132帧目标与相似物体分离的过程、第227帧目标在运动的过程和第254帧目标与相似物体靠近的过程都能够较准确地跟踪选定的目标，跟踪结果几乎与CT算法一致。这表明基于NG特征的带权分块压缩感知特征能够准确地表征目标，使得分类器在跟踪过程中能够根据特征准确跟踪目标。在包含遮挡、姿态变化的图2（b）faceocc2序列，本文提出的TWBCP算法在第265帧对于障碍物的遮挡适应性较好；在第422帧姿态变化和遮挡同时发生的情况下，TWBCP算法仍然能够准确跟踪人脸；甚至在第709帧脸部几乎被完全遮挡的情况下也没有丢失目标。而对于把目标跟踪问题当成稀疏逼近问题的L1算法，在第422帧和第709帧目标姿态变化和存在遮挡的情况下，都出现目标跟踪错误。

图2（c）faceocc序列中，不管是遮挡目标左部（第400帧）还是遮挡目标右部（第563帧），本文提出的TWBCP算法都能准确地定位目标位置；在后续目标在遮挡过后重现（第812帧）的情况下，本文提出的TWBCP算法跟踪结果没有被干扰，跟踪位置比直接利用朴素贝叶斯分类器的CT算法更准确。这表明尽管目标遮挡对特征的提取造成干扰，TWBCP算法提出的变先验概率的贝叶斯分类器充分利用已有跟踪结果，预测目标将要运动的方向，在目标被遮挡或者目标由遮挡重现的过程中，算法预测的目标方向能够帮助分类器正确分类。图2（d）fish序列是包含大量光照变化和摄像头抖动的序列，在第164帧光照突然变暗和第301帧光照突然变亮的前提下，本文提出的TWBCP算法定位的结果较为准确；TLD算法在301帧后直到跟踪结束，出现目标丢失现象，这表明摄像头抖动和光照对TLD算法影响较大。由于本文提出的TWBCP算法是基于梯度空间特征的，梯度特征对光照变化等具有很好的鲁棒性。

3.3 跟踪成功率比较

为了定量比较算法的跟踪准确性，参照文献［4］的做法，将跟踪目标与真实目标矩形框的交集除以它们的并集作为跟踪重合率，跟踪重合率大于0.5即认为是跟踪成功的，将跟踪成功的帧除以总帧数即得该序列的跟踪成功率。

本文提出的TWBCP算法与压缩跟踪（CT）、多示例学习（M IL）， TLD跟踪（TLD）和基于1e范式最小化的目标跟踪（L1）算法在8个序列上的跟踪成功率比较如表1所示。从表1中的实验结果可以看出，本文提出的TWBCP算法在6个序列中获得了最好的跟踪成功率，且在8个序列上的平均跟踪成功率高出次好的TLD算法22%。而且本文提出的TWBCP算法在相对简单的dollar序列和相对难的surfer序列都获得最好的跟踪成功率，这表明本文提出的TWBCP算法采用的基于NG特征的带权压缩感知特征对目标的描述准确，且变先验概率的贝叶斯分类器学习了以往的跟踪结果，使得分类算法对常见的跟踪难点鲁棒性较好，对序列的适应性较强，跟踪的结果不依赖于特定的序列。

表1 跟踪成功率（取整）比较（%）

3.4 实验分析

从上面实验对比结果可以看出，本文提出的算法在具有各种跟踪难点的序列中都具有较好的表现。从跟踪效果来看，在具有大量遮挡的faceocc序列和faceocc2序列、光照变化强烈的fish序列和背景相似物体干扰的dollar序列，本算法具有较好的跟踪效果（见图2）。从算法的跟踪成功率来看（见表1），本算法比性能优秀的结合预测和检测的TLD跟踪算法平均成功率高出22%，比其他算法高出更多。这些实验结果从各个方面充分证明本文提出的基于NG特征的带权分块压缩感知特征能较好地表达目标，同时变先验概率的贝叶斯分类器能根据以往跟踪结果预测目标的运动方向，实现准确跟踪。

4 结束语

本文将分块压缩感知应用于目标跟踪，提出一种基于NG特征的带权分块压缩感知用于目标特征提取，削弱了背景干扰，增强了特征的表达能力。在跟踪阶段，候选目标的先验概率是根据以往的跟踪结果计算得出的，并不是简单地认为正负样本先验概率相等，从某种程度上预测了目标的运动方向，提高了算法的准确度。实验结果从多个角度表明，本文提出的算法对常见的跟踪难度，如遮挡、光照变化、姿态变化具有较好的适应性。本文算法采用的特征是基于简单的图像梯度特征，对封闭目标有较好的效果。在后续的研究中尝试融合更加复杂的特征，如哈尔（Haar）特征［13］、尺度不变特征变换（Scale-Invariant Feature Transform， SIFT）特征［14］以及方向梯度直方图（Histogram of Oriented Gradient， HOG）特征［15］，从而使得算法对跟踪的目标有更宽松的要求。

［1］ Yilmaz A， Javed O， and Shah M. Ob ject tracking:a survey［J］. ACM Computing Surveys， 2006， 38（4）: 1-29.

［2］ Saffari A， Godec M， Pock T， et al.. On line multi-class LPBoost［C］. Preceed ings of the IEEE Conference on Com puter Vision and Pattern Recognition， San Francisco，USA， 2010: 3570-3577.

［3］ Babenko B， Yang M H， and Belongie S. Robust ob ject tracking w ith online multiple instance learning［J］. IEEE Transactions on Pattern Analysis and M achine Intelligence，2011， 33（8）: 1619-1632.

［4］ Zhang Kai-hua， Zhang Lei， and Yang M H. Real-time comp ressive tracking［C］. Preceedings of the European Conference on Computer Vision， Florence， Italy， 2012， 3: 864-877.

［5］ Mei Xue and Ling Hai-bin. Robust visual tracking and vehicle classification via sparse representation［J］. IEEE Transactions on Pattern Analysis and M achine Intelligence， 2011， 33（11）: 2259-2272.

［6］ 孙景乐， 唐林波， 赵保军， 等. 基于瑞利分布的粒子滤波跟踪算法［J］. 电子与信息学报， 2013， 35（4）: 763-769. Sun Jing-le， Tang Lin-bo， Zhao Bao-jun， et al.. A new particle filter tracking algorithm based on Ray leigh distribu tion［J］. Journal of Electron ics & Inform ation Techno logy， 2013， 35（4）: 763-769.

［7］ Kalal Z， M ikolajczyk K， and M atas J. Face-TLD: trackinglearning-detection applied to faces［C］. Preceedings of the IEEE International Conference on Image Processing， Hong Kong， China， 2010: 3789-3792.

［8］ Cheng M ing-m ing， Zhang Zi-ming， Lin Wen-yan， et al.. BING: binarized normed gradients for ob jectness estimation at 300fps［OL］. http://mm cheng.net/bing/， 2014.

［9］ Liu Gan. B lock com pressed sensing of natural im ages［C］. Preceed ings of the International Conference on Digital Signal Processing， Cardiff， B ritain， 2007: 403-406.

［10］ Wu Y， Lim J， and Yang M H. On line ob ject tracking: a benchmark［C］. Preceedings of the IEEE Conference on Com puter Vision and Pattern Recognition， Portland， USA，2013: 2411-2418.

［11］ 李然， 干宗良， 崔子冠， 等. 联合时空特征的视频分块压缩感知重构［J］. 电子与信息学报， 2014， 36（2）: 285-292. Li Ran， Gan Zong-liang， Cui Zi-guan， et al.. Block com p ressed sensing reconstruction of video combined w ith temporal spatial characteristic［J］. Journal of Electronics & Inform ation Techno logy， 2014， 36（2）: 285-292.

［12］ Ng Y A and Jordan I M. On discrim inative vs. generative classifier: a com parison of logistic regression and naive bayes［C］. Preceedings of the Advances in Neural Information Processing System s， W histler， Canada， 2002: 841-848.

［13］ Papageorgiou P C， Oren M， and Poggio T. A general fram ework for ob ject detection［C］. Preceedings of the International Conference on Com puter V ision， Bombay， India， 1998: 555-562.

［14］ 董文会， 常发亮， 李天平. 融合颜色直方图及SIFT特征的自适应分块目标跟踪方法［J］. 电子与信息学报， 2013， 35（4）: 770-776. Dong W en-hui， Chang Fa-liang， and Li T ian-p ing. Adaptive fragm ents-based target tracking m ethod fusing color histogram and SIFT features［J］. Journal of Electronics & Information Technology， 2013， 35（4）: 770-776.

［15］ Dalal N and Triggs B. Histogram s of oriented gradients for human detection［C］. Preceedings of the IEEE Conference on Com pu ter V ision and Pattern Recogn ition， San D iego， USA，2005， 1: 886-893.

罗会兰： 女，1974年生，博士，教授，研究方向为机器学习、模式识别.

钟宝康： 男，1988年生，硕士生，研究方向为目标跟踪、模式识别.

孔繁胜： 男，1946年生，博士生导师，教授，研究方向为人工智能与知识发现.

Tracking Using Weighted Block Com p ressed Sensing and Location Prediction

Luo Hui-lan①Zhong Bao-kang①Kong Fan-sheng②①（School of Information Engineering， Jiangxi University of Science and Techno logy， Ganzhou 341000， China）
②（College of Computer Science and Technology， Zhejiang University， Hangzhou 310027， China）

To reduce side effects of background in formation included in the outer parts of tracking rectangular boxes， a weighted b lock com pressed sensing feature extraction method is p roposed based on normalized gradient features. The com pressed sensing m easurem ent matrix is converted to a b lock diagonal m atrix. App rop riate weights are assigned to different blocks according to the im portance of the blocks. It aims to reduce the measurement matrix size， weaken background interference and sim plify feature extraction. Then the extracted features are inputted into Bayesian classifier w ith adaptive p riori probabilities， which is proposed to make full use of existing tracking resu lts. To some extent the classifier w ith variable p riori p robabilities can p redict the direction of the moving targets， and reduce the ambiguities of target candidates. Each frame classification function changes according to the results of the previous track to im prove the classification accuracy. In the experim ents com pared w ith four state-of-the-art tracking algorithms on 8 common ly used tracking test sequences， the proposed target tracking algorithm has higher accuracy and stability in term s of tracking results and success rate.

Ob ject tracking； B lock com pressed sensing； Bayes classifier； Variable p riori p robability

TP391

： A

：1009-5896（2015）05-1160-07

10.11999/JEIT140997

2014-07-25收到，2014-09-28改回

国家973计划项目（2010CB327900），国家自然科学基金（61105042，61462035）和江西省教育厅科技项目（GJJ13421）资助课题

*通信作者：罗会兰 luohuilan@sina.com