基于稀疏表达特征选择的压缩感知目标跟踪算法

程中建 李康 谷懿 袁晓旭 王森

摘要：目标跟踪是计算机视觉领域重要研究方向之一。压缩感知跟踪速度快、精度高，但是跟踪被遮挡目标时使用被遮挡的哈尔特征构建分类器，导致分类器性能降低，目标容易丢失。为了解决该问题，提出了根据l1稀疏表示判断哈尔特征是否被遮挡，然后使用未被遮挡的特征构建贝叶斯分类器。首先对每一帧跟踪结果运用稀疏表示提取出未被遮挡特征的集合，在构建贝叶斯分类器时仅使用未被遮挡的特征。然后使用训练好的分类器对下一帧候选样本进行分类，选取具有最大分类响应的候選样本作为跟踪结果。实验结果表明，该算法在跟踪目标部分遮挡时相比CT算法有更高跟踪准确度，算法能够实时得到高效、准确的目标跟踪结果。

关键词：目标跟踪；哈尔特征；稀疏表示；贝叶斯分类器

DOI：10.11907/rjdk.181200

中图分类号：TP312

文献标识码：A文章编号：1672-7800（2018）007-0091-06

Abstract：Targettrackingisoneoftheimportantresearchdirectionsincomputervision.Compressedsensingtracking（CT）isfastandofhighprecision，buteasytolosetrackofthetargetswhichundergoocclusion.ThisismainlyduetouseofoccludedHaarfeaturesinthetrackingprocesstoconstructtheclassifier.Inordertosolvethisproblem，thispaperproposestojudgewhethertheHaarfeatureisoccludedaccordingtothesparserepresentation，andthenconstructtheBayesianclassifierusingthenon-occludedfeatures.Firstly，thesparserepresentationofeachframeisusedtoextracttheunobstructedfeaturesets，andonlytheunobstructedfeaturesareusedinconstructingtheBayesianclassifier.Thenthetrainedclassifierisusedtoclassifythecandidatesamplesofthenextframe，andthecandidatesamplewiththelargestclassificationresponseisselectedasthetrackingresult.TheexperimentalresultsshowthatthealgorithmhashighertrackingaccuracythantheCTalgorithmwhentrackingthetargetswithpartialocclusion，andthealgorithmcangetefficientandaccuratetargettrackingresultsinrealtime.

KeyWords：targettracking；Haarfeature；sparserepresentation；Bayesianclassifier

0引言

目标跟踪是计算机视觉的重要研究课题之一，在实时监控、人机互动、运动捕捉、医学成像等领域有广泛应用。近年来，国内外大量跟踪算法被开发出来[1-4]，但由于受到光照强度改变、目标外观变换、目标部分遮挡和目标信息不足等众多因素影响，开发出具有鲁棒性的跟踪算法仍有挑战。

现有目标跟踪算法按照外观模型分为两类：生成式模型和判别式模型。生成式算法模型[3-10]通过训练样本学习得到目标外观模型，然后在候选样本中选择重构误差最小的样本作为目标。Adam等[3]利用积分图计算多尺度强度直方图表示目标特征。Zhang等[4]将目标跟踪问题描述为多任务稀疏学习问题，设计出一种协同跟踪算法。与判别式跟踪算法相比，生成式算法跟踪精度较高，但是在跟踪环境较为复杂时结果不够鲁棒。

判别式算法模型[11-16]将目标跟踪视为分类问题，使用正负样本训练分类器分离目标与背景，然后在候选样本中选择具有最大分类响应的样本作为跟踪结果。Zhang等[1]根据压缩感知原理，利用稀疏矩阵对高纬度图像特征进行降维，然后训练贝叶斯分类器对候选目标进行分类。多实例目标跟踪（MIL）[11]使用在线Boosting算法训练分类器，能处理非线性分类问题，但算法需要在每一帧迭代地对弱分类器进行选择，降低了跟踪速度。判别式算法在跟踪复杂环境中的目标时结果较为鲁棒，但跟踪外观变化不大的目标时精度比生成式算法低。

近年来，CT算法因其快速跟踪能力受到科研工作者关注[17-21]，但是该算法在跟踪被部分遮挡的目标时，容易发生漂移，主要是因为跟踪过程中使用被遮挡的哈尔特征构建分类器降低了分类器性能，为了解决该问题，本文结合生成式模型和判别式模型的优点，在CT算法基础上使用稀疏表达对其特征进行选择，以提高分类器的性能，并提出基于稀疏表达的特征选择目标跟踪算法（FST）。

1压缩感知跟踪（CT）算法

由稀疏感知理论可知，一个满足RIP条件的稀疏矩阵在对一个高纬度的原始图像特征空间投影后，产生的低纬度空间会较好地保留原始高维图像空间的全部信息[1]。CT算法利用稀疏矩阵对多尺度卷积后的高纬度图像向量进行降维处理，然后使用在线训练的朴素贝叶斯分类器在降维后的特征上对候选样本分类，选取具有最大分类响应的样本作为跟踪结果，基于该跟踪原理，CT算法实现了鲁棒性的跟踪效果。

如图1、图2所示，CT算法在第t帧图像选定的目标周围不同范围内采集正样本和负样本，然后分别提取正负样本的低纬度特征更新分类器。对于每一个目标样本Z∈Rw×h，通过多尺度卷积核{h1，1，h1.2，h1，3，......，hw，h}卷积样本Z，其中hi，j定义为：

每一个卷积核卷积后将产生一个Rw×h维列向量。经wh个卷积核的卷积作用，原始图像可以由一个高纬度向量U=u1，u2，u1，...，umT表示，其中m=wh2。對于一张普通照片，n的规模通常为108～1012，如图3所示，为了降低计算复杂度，CT算法应用一个随机高斯矩阵R=Rn×m（该高斯矩阵非常稀疏），将高纬度向量Z转换为低纬度特征向量V，同时在该随机高斯矩阵满足RIP条件的情况下，V已包含了采样向量Z中的大部分信息。即：

且文献[15]指出向量V中所有元素vi均满足独立分布。为了从大量候选样本中分类出目标样本，CT算法建立朴素贝叶斯分类器。

2FST算法实现

具有较好分辨能力是鲁棒跟踪算法的必要条件[22]。CT运用稀疏矩阵压缩感知得到大量类哈尔特征，此方法虽然有效地对压缩域中的投影特征进行分类，避免计算时的维度灾难，但在一个特定阈值范围内，由增减稀疏矩阵行数带来的哈尔特征个数变化不会影响跟踪效果，例如，由100行和50行的稀疏矩阵投影后的哈尔特征集得到的跟踪效果相似[21]；另一方面，CT的哈尔特征中部分特征的遮挡情况会影响分类器性能，导致在跟踪被遮挡目标时容易发生漂移。基于该思想，本文通过稀疏表示选取哈尔特征集中未被遮挡的特征作为特征子集训练分类器，完成目标跟踪。

如图4、图5所示，本文算法结合了生成式模型和判别式模型的优点。在第t帧使用稀疏表示选取跟踪结果的哈尔特征集中了未被遮挡的特征，并在远离目标区域和靠近目标区域范围内采样得到正负样本并更新分类器。在t+1帧时通过压缩感知得到候选样本哈尔特征，然后使用第t帧未被遮挡的特征子集进行分类器分类，选取具有最大分类响应的样本作为跟踪结果，从而完成第t+1帧目标跟踪。

2.1基于哈尔特征子集的分类器

判别式模型通过建立分类器区分目标和背景，如式（3）所示，每个候选样本的分类响应值H（v）被近似定义为目标所有哈尔特征属于正样本特征的概率累加和值，最终选取具有最大分类响应值H（v）的候选样本作为跟踪目标。因此，选取的特征与其分辨能力决定分类器的分类结果质量，然而CT算法选取压缩感知后的整个特征空间作为原始哈尔特征集，未对投影得到的哈尔特征作预处理。该方法在跟踪目标不存在遮挡并且目标和其背景存在较大差别的情况下可得到鲁棒的跟踪结果，但当目标区域内某些哈尔特征被遮挡后，CT算法发生漂移。主要是因为被遮挡的哈尔特征在分类时已经失去判别目标与背景的能力，使得分类器学习到大量非目标特征信息，非目标特征信息的累加减弱了分类器的分类效果。另一方面，实验数据表明，在一定阈值范围内，即使增加哈尔特征个数也不会改善分类器的分类效果，说明CT中哈尔特征数量冗余。因此，选取压缩感知后的哈尔特征子集V'，作为构建贝叶斯分类器的分类特征集，计算分类响应值H（v）定义为：

2.2基于稀疏表示选取哈尔特征子集

图7显示了随机产生一个特征的若干特征卷积块的结果，为防止表示跟踪目标特征i的若干卷积核产生重叠，影响样本的特征稀疏表示，算法需多次调整选取合适的稀疏矩阵，并对各特征展开列向量Yi进行稀疏表示。

图8表示跟踪过程中两个遮挡与未被遮挡的哈尔特征（绿色为遮挡，蓝色为未被遮挡）。图9为图8中两个哈尔特征稀疏表示得到的系数图（上图对应蓝色，下图对应绿色），横坐标为模板，纵坐标为稀疏系数值ai，j，1≤j≤o。上图对应的特征向量化后维度di为40，除第10个模板系数较大外，平凡模板的系数均趋近于0，其稀疏系数向量ci满足稀疏性，该特征能由其特征模板稀疏表示；与此相反，在下图中，各个模板系数分布密集，该特征不能由其特征模板稀疏表示，哈尔特征被遮挡。数据表明，通过稀疏表示能够有效选取未被遮挡的哈尔特征，避免对分类器造成影响。

2.3分类器更新

为了使分类器适应目标与其背景变化，需在每一帧跟踪结果周围一定范围内采集正负样本更新分类器，从而避免继续更新被遮挡的哈尔特征导致分类器学习到遮挡物体特征，影响分类器的分类效果。本文改进CT算法中分类器参数更新方式为：

2.4特征模板更新

为了适应目标所处环境的不断变化，算法应及时更新目标特征模板。如果模板更新过快，模板产生的误差会不断积累，从而导致跟踪结果发生偏移，相反如果不更新模板或者特征模板更新过慢，将无法准确选择被遮挡的特征。

为了动态更新目标特征模板，本研究采用与Mei等[2]相同的特征更新方法。初始化特征模板时，将第一帧给定的目标中每个哈尔特征的若干特征框向各方向偏移一个像素点，选取若干个特征框，然后将特征框按照列向量展开形成该哈尔特征的特征模板Ti。更新算法流程如下所示：

2.5实验结果与分析

本算法在Matlab2016a平台上实现，操作系统为Win10，CPU为2.4GHzInteli5处理器，内存4G，算法特征数为50（经验参数），稀疏表示误差阈值M=0.002，学习因子λ=0.85（经验参数），特征模板更新角度阈值γ=30（经验参数），特征个数阈值为25，当稀疏表达选取的哈尔特征子集的特征个数小于25，选取稀疏表达误差较小的前25个特征。

为了衡量算法跟踪效果，评估其有效性，将本算法和CT及与其跟踪原理相似的算法包括MIL、FRAG进行对比，得到4个算法在5个挑战性视频片段中（Basketball，David2，David3，Deduk，Woman）的跟踪结果。数据表明，本研究提出的算法在目标部分遮挡、目标外观变化等跟踪环境下相较于CT等算法具有更高的跟踪准确度。

2.5.1定性分析

如图10所示，在目标外观剧烈变化的视频序列Basketball中，目标的背景随着目标运动不断变化，导致分类器在跟踪目标与背景时产生混淆，造成跟踪困难，其中CT和MIL在第278帧偏离目标，并在292帧漂移到非目标队员身上。FRAG和本研究提出的算法能够准确跟踪目标。在目标区域较小，背景区域与目标相似的视频序列David2中，难以投影出有效的哈尔特征，CT算法在第4帧丢失目标，MIL和FRAG在第445帧偏离跟踪目標，并在第461帧丢失目标。而本研究提出的算法在第173、336、445、461帧目标外观剧烈变化时仍能较为准确地跟踪目标。在存在目标部分遮挡的跟踪视频序列Woman、David3中，被跟踪目标在短时间内局部被完全遮挡，跟踪结果显示在Woman中，CT、MIL、FRAG都在第124帧丢失目标，在David3中，CT、MIL、FRAG分别在第89、105、167帧丢失目标。而本研究提出的算法由于在更新分类器和分类器分类时都使用了可以达到与原始哈尔特征集跟踪效果相似的特征子集，避免了被遮挡的哈尔特征对分类器的影响，相比CT、MIL、FRAG，对局部遮挡目标实现了更好的跟踪效果。在目标外观和尺度缩放的视频序列Dudek中，CT、MIL算法分别在第370、218帧偏离目标，仅有FRAG和本研究提出的算法完成准确跟踪。

2.5.2定量分析

采用定量分析计算4个算法跟踪效果指标：①跟踪目标中心点与实际中心像素位置的平均误差，结果如表1所示；②PASCALVOC评估标准，跟踪目标框与实际目标框的平均重叠率，即score=area（RT∩RG）area（RT∪RG），其中RT表示算法跟踪的结果区域，RG表示人工标定的目标区域，∪和∩分别表示两种区域的并集和交集，函数area（·）返回区域中的像素个数如表2所示。

由表1和表2的数据可以看出（最好结果由粗体标出），本文算法较CT等目标跟踪算法在跟踪目标外观、尺度变化及目标局部遮挡时，具有更高的跟踪精确度，对比4个算法在5个挑战性视频序列中，除Dudek外，FST算法中心点误差均为最小，平均重叠率均为最大，在Dudek跟踪视频序列中，本文算法和FRAG跟踪效果接近。

3结语

本文提出一种新颖的特征选择方法，通过稀疏表示选取更具判别力的哈尔特征改善CT分类器的分类效果。该算法选择重构误差较小的部分特征构建分类器，提高了CT跟踪精度。对于被遮挡的部分哈尔特征，不更新其对应的分类器参数，避免了对分类器造成影响。该算法易于实现，可以完成实时跟踪，通过在5个具有挑战性的视频序列上与CT等算法比较，取得了鲁棒性的跟踪效果，较CT有更高跟踪准确性，对于目标外观姿势变化、目标局部遮挡都具有一定鲁棒性，能够处理目标实时跟踪。在后续研究中，将重点研究在视野中消失又重现的目标跟踪。

参考文献：

[1]ZHANGK，ZHANGL，YANGMH.Real-timecompressivetracking[C].EuropeanConferenceonComputerVision，2012：864-877.

[2]MEIX，LINGH.Robustvisualtrackingusingllminimization[C].2009IEEE12thInternationalConferenceonComputerVision，2009：1436-1443.

[3]ADAMA，RIVLINE，SHIMSHONII.Robustfragments-basedtrackingusingtheintegralhistogram[C].2006IEEEComputerSocietyConferenceonComputerVisionandPatternRecognition，2006：798-805.

[4]ZHANGT，GHANEMB，LIUS，etal.Robustvisualtrackingviamulti-tasksparselearning[C].2012IEEEConferenceonComputerVisionandPatternRecognition，2012：2042-2049.

[5]GAOX，TANGX.Unsupervisedvideo-shotsegmentationandmodel-freeanchorpersondetectionfornewsvideostoryparsing[J].IEEETransactionsonCircuitsandSystemsforVideoTechnology，2002，12（9）：765-776.

[6]ATKINSONRC，SHIFFRINRM.Psychologyoflearningandmotivation[M].Pittsberg：AcademicPress，1968.

[7]MEIX，LINGH.Robustvisualtrackingandvehicleclassificationviasparserepresentation[J].IEEETransactionsonPatternAnalysisandMachineIntelligence，2011，33（11）：2259-2272.

[8]YUANY，EMMAUELS，FANGY，etal.Visualobjecttrackingbasedonbackwardmodelvalidation[J].IEEETransactionsonCircuitsandSystemsforVideoTechnology，2014，24（11）：1898-1910.

[9]LIH，SHENC，SHIQ.Real-timevisualtrackingusingcompressivesensing[C].2011IEEEConferenceonComputerVisionandPatternRecognition，2011：1305-1312.

[10]WANGCL，HUOX.Objecttrackingunderlowsignaltonoiseratiowiththeinstantaneouspossiblemovingpositionmodel[J].SignalProcessing，2013，93（5）：1044-1055.

[11]BABENKOB，YANGMH，BELONGIES.Visualtrackingwithonlinemultipleinstancelearning[C].IEEEConferenceonComputerVisionandPatternRecognition，2009：983-990.

[12]SMEULDERSAWM，CHUDM，CUCCHIARAR，etal.Visualtracking：anexperimentalsurvey[J].IEEETransactionsonPatternAnalysisandMachineIntelligence，2014，36（7）：1442-1468.

[13]WUY，LIMJ，YANGMH.Onlineobjecttracking：abenchmark[C].2013IEEEConferenceonComputervisionandpatternrecognition，2013：2411-2418.

[14]YIS，HEZ，YOUX，etal.Singleobjecttrackingviarobustcombinationofparticlefilterandsparserepresentation[J].SignalProcessing，2015，110：178-187.

[15]GRABNERH，GRABNERM，BISCHOFH.Realtimetrackingviaonlineboosting[C].BritishMachineVisionConference，2006，1（5）：6.

[16]DANELLJANM，HAGERG，SHAHBAZKHANF，etal.Adaptivedecontaminationofthetrainingset：Aunifiedformulationfordiscriminativevisualtracking[C].ProceedingsoftheIEEEConferenceonComputerVisionandPatternRecognition.2016：1430-1438.

[17]SONGH.Robustvisualtrackingviaonlineinformativefeatureselection[J].ElectronicsLetters，2014，50（25）：1931-1933.

[18]LIUQ，YANGJ，ZHANGK，etal.Adaptivecompressivetrackingviaonlinevectorboostingfeatureselection[J].IEEETransactionsonCybernetics，2017，47（12）：4289-4301.

[19]WUY，JIAN，SUNJ.Real-timemulti-scaletrackingbasedoncompressivesensing[J].TheVisualComputer，2015，31（4）：471-484.

[20]黃庆俊，何儒汉.基于协方差矩阵的压缩感知跟踪算法[J].软件导刊，2017，16（4）：31-35.

[21]LIK，HEF，CHENX.Real-timeobjecttrackingviacompressivefeatureselection[J].FrontiersofComputerScience，2016，10（4）：689-701.

[22]WANGN，SHIJ，YEUNGDY，etal.Understandinganddiagnosingvisualtrackingsystems[C].2015IEEEInternationalConferenceonComputerVision，2015：3101-3109.

（责任编辑：江艳）