基于压缩传感的多样本目标跟踪算法

2014-07-03陈茜，狄岚

计算机与现代化 2014年7期

陈茜，狄岚

(江南大学数字媒体学院，江苏无锡 214122)

0 引言

随着计算机软硬件的持续快速发展，各种基于视频图像的应用软件开始涌入人们的视野，极其便利的操作方便了用户的日常生活。但目前主要的应用局限于视频的初级阶段(采集、编码、传输、播放等)，有针对性的高级应用较少;另外有越来越多的摄像头，出现在生活的各个角落，尤其是安防领域，公司、学校、住宅区，这些摄像头通常会产生数据量庞大的实时视频数据，需要大量人力监控以及极大的存储设备。作为视频应用的高级阶段，视频目标检测与跟踪成为了目前国内外计算机视觉领域中持续的热点方向。

现阶段已有众多的跟踪算法被提出，且取得了一些成功(行人识别[1]，3D 物体检测[2]等)，但是在真实环境中仍旧有未解决的问题(位置、光照、遮挡和运动等的外观改变等)，限制了这些最先进算法应用于商业领域(例如摄像头监视[3])。最近，视频目标跟踪中分类器被成功地应用，这种方法的基本思路是:用训练分类器将被检测对象从背景中区分出来，这也是本文的研究目的。目前大多数方法会采用不同的特征表示结合不同的学习方法，组成不同分类器适应实际运用需求[4]。文献[5]的作者设计了一种在线学习的boosting框架，在目标发生剧烈外观变化时具有良好的跟踪适应性。其主要工作是通过选择不同特征，把目标从背景中区分出来，分类器通过自身学习进行更新。但是该方法很容易产生跟踪框漂移，且由于学习特征维数巨大，对于商用电脑的配置，帧速率很低，达不到实时检测的效果。而文献[6]提出了一种优于半监督学习的方法用于解决boosting漂移问题。

最近，压缩采样理论作为研究热点，被用到目标跟踪中[6-8]。压缩采样理论的概念由Donoho在2006年正式提出[9]。文献[7]提出l1跟踪器，稀疏表示被跟踪物体及其它样本。然而其计算复杂度较高，限制了在实时检测中的应用。文献[8]将文献[7]中的分类方法进一步改进，用正交匹配算法(Orthogonal Matching Pursuit，OMP)有效解决了最优化问题。从被检测目标周边选取正、负样本，构造成投影矩阵，新目标位置为矩阵中正样本所对应的系数最大的位置。但由于训练的正负样本单一，要建立投影矩阵不太容易。为此，文献[10]提出了压缩传感跟踪算法，通过宽松规则生成稀疏的投影矩阵，将稀疏后的数据直接作为目标的特征来使用。该算法的优点在于快速地提取特征，能够达到实时跟踪检测目标的目的。但由于该算法采用的目标描述特征，没有考虑不同特征对不同目标的分类效果不同，在目标纹理、运动或光照变化剧烈时容易产生漂移，甚至跟丢。文献[11]对文献[10]进行了改进，引进多特征联合的算法，解决了单一特征跟踪不稳定、易丢失的问题。用多个矩阵作为压缩感知中的投影矩阵，将压缩后的数据作为不同特征来提取。但由于该算法采用的朴素贝叶斯分类方法将特征分类结果直接相加，没有考虑不同特征的分类效果差异，在目标运动和光照变化大时容易丢失目标。

在这种背景下，本文提出一种视频目标跟踪方法，该方法基于Adaboost框架，利用压缩感知特征，且融合了多个正负样本。

1 压缩传感跟踪算法基本理论

压缩采样理论(也被广泛译为压缩传感或CS，Compressive Sense)，是一种新颖的采样模式，和传统方法相比，CS理论可以从更少的样本或测量中恢复一定的信号和图像[9]。

文献[10]提出了压缩传感跟踪算法，但该算法并不是直接提取样本的特征，而是在提取选择特征的基础上，利用压缩传感算法压缩所选择的特征，其算法公式如下:

其中 X∈Rn×1为原始特征，R∈Rk×n(k ＜＜ n)为测量矩阵，V∈Rk×1为压缩后的数据。文献[10]中，V 为最后所得特征，X为一维的原始特征(二维目标候选区域转换成一维)，R为特征提取矩阵。公式(1)中R十分重要，若R为稀疏阵，则可以消减大量的计算量并减轻内存消耗，故文献[10]中的矩阵R为稀疏的随机测量矩阵，R的定义如下:

其中a为在2到4中通过随机选取的整数。

由公式(2)得知实际特征(即原始特征的加权和[10])提取如下:

其中S为在待检区域随机选取的图块，NR为图块数目，其值在2～4间随机选取，Ri，k的值按照公式(2)计算为1或者－1，其值在同一图块中是不变的。特征生成如图 1 所示，图中∑jRi，jxj=vi，i=1，2，…，k。

图1 特征生成示意图

2 基于压缩传感的多样本目标跟踪算法

2.1 基于压缩传感的多特征提取

由于压缩传感跟踪算法在目标纹理快速变化时易发生漂移或丢失目标，针对此问题，本文对其特征进行了分析并提出了改进的跟踪算法。

由特征提取公式(3)可知，Ri中只存在l或只存在－l的概率为29%[10]。由概率计算结果可知，在71%的情况下，1和－1同时存在。特征表现为NR块区域的加权和，当特征表现为图像灰度均值，此时Ri都为1或－1;当特征表现为目标的纹理特征，此时Ri中既有1也有－1。可知压缩传感跟踪算法中大约7成的特征都表现为纹理特性，而纹理特性并不稳定，特别是环境或目标纹理变化的时候。

为加强跟踪的稳定性，本文改进了特征提取矩阵R。根据公式(3)随机生成R1，再基于R1结合灰度特征和纹理特征的特点，生成新的随机测量矩阵R2。新的特征提取矩阵的公式如下:

通过概率计算可知，R2i中的分布特性与R1i中的分布特性正好互补，使得R1和R2提取的特征形成互补的纹理特征和灰度均值特征，且比例一致。这2种特征在不同情况下的稳定性不同，从而使跟踪效果更鲁棒。R2的特征提取公式如下:

其中 Si，k为第 k 个图像块，R2i，k为权值，V2i为新的特征。

2.2 在线多样本的检测

基于在线的boosting方法，采用多实例样本包的方法[12]，集合为已贴标签样本集，定义为:

其中 Ai={x1，x2，…，xnA}是包含 nA个样本的包，yi∈{0，1}是包的二值标签，包中实例的标签在训练过程中是未知的，故boosting所用的似然函数不适用于多样本学习，可以采用本文提出的适合多样本检测的在线boosting方法，其对数似然函数定义如下:

其中yF(x)代表样本x在分类器中的边界，F(x)为与预测最大边界值有关的分类器。在boosting的逐级梯度下降中，对弱分类器fm(x)进行修改:

并调整权重w:

则对于包的多样本对数似然函数定义为[13]:

则正样本包的概率为正样本概率的几何平均:

结合公式(8)，优化后带有标签的样本可以表示为:

其中aij为正样本包中每一个样本的负梯度，表示为

2.3 在线多样本的加权跟踪

采用多样本检测，且有多个目标的特征需要加权，由特征提取的公式(3)可知，候选目标的每个特征是被检目标的概率如下:

通过公式(10)评估特征对训练样本的分类结果。设定k为判别正负样本的阈值，如果pi(i)＞k，认为样本为正，反之认为样本为负，本文中选取k=0。

设定特征的权值为wi，且会在得到训练样本的分类结果后重置，每个特征的权值计算方式如下:

上式中tpi为正样本被正确分类的个数，tni为负样本被正确分类的个数，fpi为正样本被错误分类的个数，fni为负样本被错误分类的个数。

通过使用多种特征，目标特征在各种情况下稳定性提高，从而提高跟踪效果，同时需要对公式(12)中条件分布p(vi|y=1)、p(vi|y=0)进行重定义:

通过调整特征的wi，分类效果好的特征权值wi增加，就可以得到新的分类器Hn(v)，同时根据加权过的特征寻找目标在下一帧的位置。

结合公式(14)，所得判断目标下一帧位置公式如下:

3 实验结果与分析

在实验时，前一帧图像中去掉跟踪区域作为背景图像。目标跟踪实例使用了来自公共数据库序列的自然视频序列David、Sylvester、Girl和笔者视频序列进行测试。其中遮挡实例来源于Girl和笔者。本文跟踪算法与压缩传感跟踪算法、OBT算法进行了比较，实验中压缩传感跟踪算法选取特征的个数为100个，OBT算法中强分类器50个，包含100个弱分类器，算法都采用Haar-like特征，在主频为2.83 GHz，内存为4 GB，Windows 7操作系统下Matab 2012b平台上进行了对比实验。当目标大小为60像素×90像素，搜索半径为24像素时，本文算法达到20帧/s跟踪速度，基本满足实时性要求。

目标跟踪结果如图2、图3所示，目标遮挡的跟踪结果如图4、图5所示，其中灰色实线框、黑色实线框及白色虚线框分别代表OBT算法、本文算法及压缩传感跟踪算法。实时性分析表如表1所示。

图2 David视频序列跟踪结果

由图2可知，在David视频序列中，压缩传感跟踪算法在目标的纹理、光照变化较少的情况下跟踪效果良好，但在David的第227、379帧中，因为目标快速运动，跟踪检测的视频序列中出现了目标漂移问题。OBT算法因其特征可以学习更新，容易产生不理想的特征，特别是当目标快速运动时，经常出现目标漂移甚至丢失的情况。在跟踪误差曲线图6中，OBT算法在第120到180帧之间出现目标丢失的情况。本文算法的跟踪最稳定，或跟压缩传感跟踪算法的跟踪效果基本相同。

图3 Sylvester视频序列跟踪结果

由图3可知，在Sylvester视频序列中，由于目标运动迅速，纹理、光照变化明显，压缩传感跟踪算法和OBT算法在其中都出现了目标漂移的情况。压缩传感跟踪算法在第246、676、1160帧中发生目标丢失的情况，这是由于压缩传感跟踪算法采用的特征大部分为纹理特征，而其在目标环境和目标运动变化剧烈的情况下不够稳定，从而导致跟踪效果的起伏。OBT算法在第246、676、1108到1300帧均出现了目标漂移甚至第945帧以后完全丢失目标的情况，从图7中也可以看出跟踪误差起伏很大，这是由于其特征更新速率快的特点，导致了错误累加。本文算法在目标纹理出现变化较大的情况下，因采用纹理特征和灰度均值特征相结合的方法，且依据不同特征的不同稳定性进行加权，对Sylvester视频序列跟踪稳定。

由图4可知，在Girl视频序列中出现了相似目标时，从第439帧可以看出，压缩传感跟踪算法和OBT算法会在相似的目标间产生漂移。由于压缩传感跟踪算法和OBT算法都没有对遮挡情况作处理，故当目标被持续或大面积遮挡时，会发生目标漂移甚至丢失的情况。本文算法和OBT算法在第445帧时，最先找回目标，而压缩传感跟踪算法产生了漂移。

图4 Girl人脸遮挡和相似目标跟踪结果

图5 人脸不同程度遮挡的跟踪结果

由图5可知，本文算法在检测目标被遮挡时依然能够进行跟踪。在第1行右图，在目标被部分遮挡时，压缩传感跟踪算法和OBT算法产生了漂移现象。第2行左图，本文算法在目标被遮挡恢复后，正确找回目标，而压缩传感跟踪算法和OBT算法已经丢失目标。在第3行的2图中，本文算法跟踪依旧准确，压缩传感跟踪算法发生漂移和丢失，OBT算法已丢失目标。

图6 David视频序列的跟踪误差曲线图

图7 Sylvester视频序列的跟踪误差曲线图

本文方法4种视频序列的实时性分析如表1所示。

表1 本文方法4种实例的实时性分析

由表1可以得知，本文的方法实时性达到了在线跟踪的需求，受不同视频分辨率和跟踪目标的变化，帧速率略有差异。

本文方法与OBT算法以及压缩传感跟踪算法的实时性对比如表2所示。

表2 实时性对比

由表2可以得知，本文的方法实时性优于OBT算法，与压缩传感跟踪算法相当。

4 结束语

本文算法是在压缩传感跟踪算法的基础上提出的，通过实验可以看出本文算法的跟踪速度优于在线boosting跟踪方法，继承了压缩传感跟踪算法实时跟踪的优越性。通过增加新的压缩感知特征，融合多个正负样本，有效提高特征跟踪的稳定性。结合boosting学习方法更新特征权值和置信图估计，解决跟踪目标被遮挡的问题，能有效抗干扰，并寻回目标。

实验结果表明，本文算法在目标运动、纹理或环境变化的情况下跟踪稳定性有所提高，对漂移现象具有一定的遏制。下一步的研究会着重于目标发生严重遮挡时引入运动估计[14-16]加以改进，在目标大小发生变化时采用三角流等算法[17-19]解决。但这些方法的引入必然导致跟踪帧速率的下降，如何更好地解决这些问题是本文后续研究的方向。

[1] 马俊.基于图像和深度信息融合的目标跟踪[J].计算机与现代化，2013(9):91-94.

[2] 徐培智，徐贵力，王彪，等.基于立体视觉的非合作目标位姿测量[J].计算机与现代化，2013(8):85-91.

[3] Dee H，Velastin S.How close are we to solving the problem of automated visual surveillance?[J].Machine Vision and Applications，2008，19(5-6):329-343.

[4] 刘国营，陈秀宏，庄甘霖.检测识别跟踪分离的在线多样本视频目标跟踪[J].计算机工程，2012，38(23):194-197.

[5] Grabner H，Bischof H.On-line boosting and vision[C]//Proceedings of the 2006 IEEE Conference on Computer Vision and Pattern Recognition.2006，1:260-267.

[6] Stalder S，Grabner H，Van Gool L.Beyond semi-supervised tracking:Tracking should be as simple as detection，but not simpler than recognition[C]//Proceedings of the 12th IEEE International Conference on Computer Vision Workshops.2009:1409-1416.

[7] Li Hanxi，Shen Chunhua，Shi Qinfeng.Real-time visual tracking using compressive sensing[C]//Proceedings of the 2011 IEEE Conference on Computer Vision and Pattern Recognition.2011:1305-1312.

[8] Mei Xue，Ling Haibin.Robust visual tracking and vehicle classification via sparse representation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2011，33(11):2259-2272.

[9] Donoho D L.Compressed sensing[J].IEEE Transactions on Information Theory，2006，52(4):1289-1306.

[10] Zhang Kaihua，Zhang Lei，Yang Ming-Hsuan.Real-time compressive tracking[C]//Proceedings of the 13th European Conference on Computer Vision.2012:866-879.

[11] 朱秋平，颜佳，张虎，等.基于压缩感知的多特征实时跟踪[J].光学精密工程，2013，21(2):437-443.

[12] Viola P，Jones M.Rapid object detection using a boosted cascade of simple features[C]//Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition.2001，1:511-518.

[13] Babenko B，Yang Ming-Hsuan，Belongie S.Visual tracking with online multiple instance learning[C]//Proceedings of the 2009 IEEE Conference on Computer Vision and Pattern Recognition.2009:983-990.

[14] 顾幸方，茅耀斌，李秋洁.基于Mean Shift的视觉目标跟踪算法综述[J].计算机科学，2012，39(12):16-24.

[15] Patras I，Hancock E R.Coupled prediction classification for robust visual tracking[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2010，32(9):1553-1567.

[16] Olson C F.Maximum-likelihood template matching[C]//Proceedings of the 2000 IEEE Conference on Computer Vision and Pattern Recognition.2000，2:52-57.

[17] Glocker B，Heibel T H，Navab N，et al.TriangleFlow:Optical flow with triangulation-based higher-order likelihoods[C]//Proceedings of the 11th European Conference on Computer Vision.2010:272-285.

[18] Lin Zhe，Hua Gang，Davis L S.Multiple instance feature for robust part-based object detection[C]//Proceedings of the 2009 IEEE Conference on Computer Vision and Pattern Recognition.2009:405-412.

[19] Fang Jiang-xiong，Yang Jie，Liu Hua-xiang.Efficient and robust fragments-based multiple kernels tracking[J].International Journal of Electronics and Communications，2011，65(11):915-923.