基于加速鲁棒特征和多示例学习的目标跟踪算法
开篇：润墨网以专业的文秘视角，为您筛选了一篇基于加速鲁棒特征和多示例学习的目标跟踪算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘 要：视频目标跟踪是机器视觉与人工智能的重要研究方向， 具有很强的实用价值和重要的研究意义。众多学者和专家都致力于研究如何更好地解决照明变化、形状变化、外观变化和遮挡对目标跟踪的影响。针对照明变化、形状变化、外观变化和遮挡对目标跟踪的影响， 提出一种基于加速鲁棒特征（SURF）和多示例学习（MIL）的目标跟踪算法。首先，提取目标及其周围图像的SURF特征；然后，将SURF描述子引入到MIL中作为正负包中的示例；其次，将提取到的所有SURF特征采用聚类算法实现聚类， 建立视觉词汇表；再次， 通过计算视觉字在多示例包的重要程度， 建立“词文档”矩阵， 并且求出包的潜在语义特征通过潜在语义分析（LSA）；最后， 通过包的潜在语义特征训练支持向量机（SVM）， 使得MIL问题可以依照有监督学习问题进行解决， 进而判断是否为感兴趣目标， 最终实现视觉跟踪的目的。通过实验， 明确了所提算法对于目标的尺度缩放以及短时局部遮挡的情况都有一定的鲁棒性。
关键词：加速鲁棒特征；多示例学习；潜在语义分析；目标跟踪；支持向量机
中图分类号：TP391.4
文献标志码：A
文章编号：1001-9081（2016）11-2974-05
0 引言
目标跟踪正在社会科技发展和国民经济中发挥着巨大的作用， 其研究具有重要的应用价值和广阔的发展前景， 然而， 照明变化[1-3]、外观变化[4-5]、形状变化[6-7]和遮挡[8-10]这些因素仍然是目标跟踪的巨大挑战。
根据跟踪目标的相似性度量方法以及表示的不同， 将跟踪算法归类为基于模型的、基于轮廓的、基于区域统计特性的和基于特征的跟踪算法等。
基于模型的跟踪对于目标的运动轨迹分析比较准确， 即便目标在被跟踪的过程中有姿态变化也能跟踪到目标， 但在实际的跟踪系统中， 如果没有先验知识就很难得到目标模型。 对刚体目标如汽车[11]进行跟踪时， 首先通过已知的先验信息得到汽车的3D结构， 然后通过视频序列获取3D模型的参数， 继而得到跟踪目标的瞬时运动参数； 但是， 实际中很难保证几何模型的精确， 同时3D模型的相关算法也比较耗时， 使得这种算法在运用中有了一定的局限性。基于轮廓的跟踪， 在对目标进行跟踪时采用先分割后提取边缘， 这种方法对外形有变化的目标有较好的跟踪效果， 如对运动细胞的跟踪， 但当运动的目标被全部或部分遮挡时， 这种算法将受到很大的局限。基于区域统计特性的跟踪方法由于利用目标的全局描述信息， 难以准确定位， 同时， 受到存在其他区域统计特性相似的影响， 跟踪算法也会失效[12]。基于特征的跟踪算法的关键是进行特征提取， 常见的方法有Harris角点检测[13]、SUSAN（Smallest Univalue Segment Assimilating Nucleus）[14]、HessianLaplace[15]、强角点检测[16-17]等。但是它们的缺点是不能适应图像的尺度变化， 对于不同尺度的图像， 无法建立相应特征点的对应关系。近几年， 目标跟踪更关注于基于特征的目标跟踪算法， 如在实际复杂多变的场景中目标在跟踪过程中往往会出现形变、遮挡等问题， 当前利用其他方法很难有效解决这些问题， 而通过特征点匹配， 不断更新特征点最终可以实现目标的跟踪[18]。加速鲁棒特征 （Speeded Up Robust Feature， SURF）[19]是一种尺度不变和旋转不变的特征， 与传统的跟踪算法相比， SURF是一种很好的局部特征， 并且这种特征具有尺度不变、图像旋转不变和视角不变性， 以及良好的特征提取速度。因此， 本文针对目标的尺度变化选用了SURF特征， 同时由于多示例学习（MultiInstance Learning， MIL）是若干个样本构成的样本包取代单个样本， 通过此办法可以解决正样本很难确定的情况， 对目标被部分短时遮挡的情况具有很好的效果。本文提出了基于SURF特征和MIL的目标跟踪算法。
1 目标特征的提取
1.1 SURF特征的提取
本文提出的目标跟踪算法提取目标区域及其周围的SURF[20]特征， 如图1所示。
第一步 进行特征点检测， 主要利用Hessian矩阵的行列式判断图像上某点是否为极值点， 如式（1）所示：
若行列式小于零， 即此矩阵的特征值不同号， 就可判断出（x，y）是非局部极值点；反之， 若行列式大于零， 即此矩阵的特征值同号， 就可判断出（x，y）是极值点。
第二步 确定主方向， 构造SURF特征描述子向量。提取SURF特征的算法如图2所示。
1.2 潜在语义特征的提取
将目标区域及其周围的SURF特征继续构造其潜在语义特征[21]， 主要涉及到用提取的SURF特征形成多示例包， 通过聚类构造视觉字典， 生成图像区域的词文档矩阵， 进而获得关于目标及其周围区域的潜在语义特征。
首先构造词文档矩阵， 把训练集的全部包相对应的向量按列放在一起：
2 分类器的构造
虽然本文算法用到的分类器是支持向量机（Support Vector Machine， SVM）， 但是其基于多示例框架的， 所以本文算法对整个包提取其潜在语义特征， 而不是用多示例包中的单个示例即SURF描述子作为SVM的训练样本，因此本文算法在训练SVM时是提取多示例包的潜在语义特征， 用包的潜在语义特征和这个包相应的标记组成训练样本来训练SVM， 同样， 当得到SVM模型后， 用SVM识别多示例包， 输出多示例包的正负标记。
3 基于多示例学习的目标跟踪
3.1 多示例学习框架
本文在训练SVM以及提取特征时都是把包作为单个训练样本， 即用到了MIL中对训练样本中的包标记的思想， 而不是单个示例的思想。
该算法首先提取包的SURF特征， 通过聚类形成视觉字典， 然后将这些多示例包中的SURF特征都一一对应成视觉字典中的视觉字， 再次通过计算， 得出每一个视觉字在多示例包中的重要程度， 接下来由多示例的列向量构成“词文档矩阵”， 提取包的潜在语义特征， 然后训练SVM。
在后续帧中， 多示例包都是未标记的， 先对新来帧提取多示例包的潜在语义特征， 然后用训练好的SVM对多示例包进行识别并给出目标的位置， 同时更新视觉字典， 重新训练SVM， 跟踪算法如下所示。
输入 视频数据根据相同视觉特征可形成的视觉字的种类N和视频数据集；
输出 跟踪算法的精度和速率。
步骤1 利用第1章中的方法提取SURF特征。
步骤2 构造“视觉词汇表”。将提取到的SURF描述子利用Kmeans方法聚成K类， 把各个类中心称之为“视觉字”， 这K个“视觉字”称作“视觉词汇表”， 表示成R。
步骤3 生成“词文档矩阵”。把训练集中的各个包中的各个示例对照成步骤3中生成的R中的“视觉字”；
步骤4 潜在语义特征提取。对“词文档”矩阵进行奇异值分解， 然后降维， 训练集中的每个多示例包的“潜在语义特征”就是降维后的“词文档”矩阵中的每一列。
步骤5 初始化训练样本集TS=， 将生成的已知的正负包的潜在语义特征表示成φ（Bi）， 将（φ（Bi）， yi）加入TS。
步骤6 训练SVM分类器， 由TS训练SVM分类器。
步骤7 对后续帧的每一个新包计算出它的潜在语义特征， 再用前面训练好的SVM分类器进行识别， 生成正、负包。
重复步骤1～步骤7， 直到最后一帧。
3.2 跟踪过程中的更新机制
为了自适应目标的外观和姿态的变化， 所提出的跟踪算法每5帧更新一次SVM。更新时首先对每一帧新来的图像进行多示例包的划分， 并提取SURF特征；然后将5帧提取到的所有SURF特征进行聚类形成新的视觉字典；再用5帧积累的多示例包构造新的“词文档”矩阵；最后提取新的多示例包的潜在语义特征来更新分类器。
3.3 跟踪算法
本文算法主要思想是先进行特征点检测， 生成SURF描述子， 然后利用聚类方法对当前提取到的全部SURF描述子聚类， 构建视觉词汇表， “词文档矩阵”是按视觉字在包中的重要程度构建的。接下来采用潜在语义分析（Latent Semantic Analysis， LSA）得到包的潜在语义特征， 把MIL变成规范的有监督学习， 最后用支持向量机进行识别。
4 实验结果与分析
本文的实验环境为Intel Core2 Duo CPU E7500 2.93GHz、 2.94GHz和4.00GB的内存以及Matlab R2011a。收集了50个标准测试视频序列[22]以及2个手工录制的视频。
实验中用到的对比算法有：跟踪学习检测（Tracking Learning Detection， TLD）[23]、多示例学习跟踪MILTrack[24]、压缩跟踪（Compressive Tracking， CT）[25]。视频数据里包含目标尺度变化、姿态变化和短时遮挡。实验中， 先验信息为前5帧的目标的初始位置和目标的大小， 同时， 在更新视觉字典时， 采用的是每5帧更新1次。
4.1 实验定性分析
实验一 尺寸变化。图3是Dog1上运行的跟踪结果。MILTrack对于目标的大小的变动， 尽管可以达到跟踪的要求， 不过此算法对目标大小缩放的情形不能适应。本算法可以适应目标的尺度缩放。
实验二 遮挡情况。在跟踪的过程中正样本可能会出现不好确定的问题， 为了解决这种问题采用了MIL的方式， 其让含有若干样本的多示例包取代用独个样本作为训练集。这样对于跟踪过程中目标的漂移能够做到一定的减少， 让跟踪的目标更加稳定。本文选用一组具有短时遮挡的视频序列来测试所提算法和其他算法的跟踪效果， 然后进行对比。图4是被短时遮挡过脸的视频（FaceOcc2）序列的每种算法的跟踪效果。
从图4中可以看到， 当目标受到遮挡， MILTrack算法产生了漂移，而本文算法却有较好的效果， 不过本文算法对于目标被长时间全部遮挡这种情况也是没有鲁棒的跟踪效果。对于本文算法对短时局部遮挡有较好的效果是因为本文算法使用了局部特征SURF。
实验三 光照、外观变化等情况。本文算法在其他方面（光照、外观变化、旋转）也能满足跟踪的要求， 如图5～7所示。
1）光照变化，如图5所示。
2）外观变化，如图6所示。
3）快速移动、旋转以及短时遮挡，如图7所示。
4.2 定量分析实验
本文算法和其他算法的对比结果如表1所示， 结果的运算是对50个基准视频数据的精度的平均值， 本文算法都具有较好的跟踪性能。
几种算法在跟踪时的位置误差曲线如图8所示。
5 结语
本文提出了一个基于SURF和MIL的目标跟踪算法。算法提取了图像的SURF特征， 利用MIL训练包的性质， 用户仅需对划分的多示例包给定一个标号， 而不必对其中的每一个关键点进行标注， 使得训练集的初始化工作量大幅减少。未来， 我们将致力于更加高效的目标外观表达方式的研究。
参考文献：
[1] 单勇，王润生. 适应灰度和光照变化的运动目标跟踪方法[J]. 计算机辅助设计与图形学学报，2006，18（2）：283-288.（SHAN Y， WANG R S. Tracking of moving objects with intensity and luminance changes[J]. Journal of ComputerAided Design & Computer Graphics， 2006，18（2）：283-288.）
[2] 郑增国，宣士斌，桑高丽，等. 一种改进的Mean Shift目标跟踪算法――针对视频对象部分遮挡和光照变化[J]. 广西民族大学学报（自然科学版），2012，18（1）：50-54.（ZHENG Z G，XUAN S B，SANG G L， et al. A robust mean shift algorithm for target tracking―under partial occlusion and illumination variations[J]. Journal of Guangxi University for Nationalities （Natural Science Edition），2012，18（1）：50-54.）
[3] 林明秀，刘伟佳，张达旭， 等. 适应光照变化的车辆目标跟踪算法[C]// 2007中国控制与决策学术年会论文集.沈阳：控制与决策，2007：4.（LIN M X，LIU W J，ZHANG D X， et al. Algorithm of vehicle tracking adapting light changing[C]// Proceedings of the 2007 Chinese Control and Decision Conference. Shenyang： Control and Decision， 2007：4.）
[4] 左军毅，赵春晖，梁彦，等. 一种具有跟踪外观变化目标能力的均值漂移算法[J]. 计算机科学，2007，34（10）：244-246.（ZUO J Y， ZHAO C H， LIANG Y， et al. A mean shift tracker with the ability to track object with changing appearance[J]. Computer Science，2007， 34（10）：244-246.）
[5] 贾旭. 基于局部外观模型的目标跟踪方法研究[D]. 大连： 大连理工大学，2013：1-49.（JIA X. Research of object tracking based on local appearance model[D]. Dalian： Dalian University of Technology，2013：1-49.）
[6] 王漫. 基于改进主动形状模型的目标跟踪方法研究[D]. 合肥： 中国科学技术大学， 2010：1-44.（WANG M. Target tracking method based on improved active shape model research[D]. Hefei： University of Science and Technology of China， 2010：1-44.）
[7] 史久根， 王祥澍， 韩江洪. 基于形状感应的运动目标跟踪算法[J]. 计算机工程， 2011，37（22）：143-144.（SHI J G， WANG X S， HAN J H. Moving object tracking algorithm based on shape induction[J]. Computer Engineering， 2011，37（22）：143-144.）
[8] 彭勃兴.图像序列跟踪中的遮挡问题研究[D]. 西安： 西安电子科技大学， 2014：1-46.（PENG B X. Research on occlusion in image sequence tracking[D].Xi’an： Xidian University，2014：1-46.）
[9] 薛陈，朱明，刘春香. 遮挡情况下目标跟踪算法综述[J]. 中国光学与应用光学，2009，2（5）： 388-394.（XUE C， ZHU M，LIU C X. Review of tracking algorithms under occlusions[J]. Chinese Journal of Optics and Applied Optics， 2009，2（5）： 388-394.）
[10] MA L. The shade problem study in target tracking[D]. Jinan： Shandong University， 2006：1-58.（马丽. 目标跟踪中的遮挡问题研究[D]. 济南：山东大学， 2006：1-58.）
[11] KOLLER D， DANIILIDIS K， NAGEL H. Modelbased object tracking in monocular image sequences of road traffic scenes[J]. International Journal of Computer Vision，1993，10（3）： 257-281.
[12] 邢藏菊，曲延锋，王守觉. 静态灰度图像中的人脸快速检测[J]. 计算机辅助设计与图形学学报，2002，14（5）：401-403.（XING C J，QU Y F，WANG S J. Face detection on grayscale static image with complex background[J]. Journal of Computer Aided Design & Computer Graphics， 2002，14（5）： 401-403.）
[13] HARRIS C G， STEPHENS M J. A combined corner and edge detector[C]// Processing of the 4th Alvey Vision Conference. Plessey Research Roke Manor， UK： The Plessey Company， 1988：147-151.
[14] SMITH S M， BRADY J M. SUSAN ― a new approach to low level image processing[J]. International Journal of Computer Vision，1997，23（1）：45-78.
[15] MIKOLAJCZYK K， SCHMID C. Scale & affine invariant interest point detectors[J].International Journal of Computer Vision，2004，60（1）：63-86.
[16] SHI J B， TOMASI C. Good features to track[C]// Proceedings of the 1994 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Piscataway， NJ： IEEE， 1994： 593-600.
[17] TOMMASINI T，FUSIELLO A， TRUCCO E， et al. Making good features track better[C]// Proceedings of the 1998 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Washington， DC： IEEE Computer Society， 1998：178-183.
[18] 刘静寒，钟辉.基于特征点匹配的自适应目标跟踪算法[J]. 微型机与应用， 2015，38（8）：17-19. （LIU J H， ZHONG H. An adaptive object tracking algorithm based on featurepoints matching[J]. Microcomputer & Its Applications， 2015， 38（8）：17-19.）
[19] BAY H， TUYTELAARS T， GOOL L V. SURF： speeded up robust features[J]. Computer Vision & Image Understanding， 2006， 110（3）：404-417.
[20] 梅振顺，战荫伟，钟左峰.基于SURF特征的目标跟踪[J].中国体视学与图像分析，2011，16（1）：28-32.（MEI Z S， ZHAN Y W， ZHONG Z F. Video object tracking based on SURF features[J]. Chinese Journal of Stereology and Image Analysis， 2011，16（1）： 28-32.）
[21] 李大湘，赵小强，刘颖，等. 融合SIFT和MIL的红外人脸识别方法[J]. 西安邮电学院学报， 2012，17（4）：15-20.（LI D X， ZHAO X Q， LIU Y， et al. Infrared face recognition method by integration of SIFT and MIL[J]. Journal of Xi’an University of Posts and Telecommunications， 2012，17（4）：15-20.）
[22] WU Y， LIM J， YANG M H. Online object tracking： a benchmark[C]// Proceedings of the 2013 IEEE Conference on Computer Vision and Pattern Recognition. Washington， DC： IEEE Computer Society， 2013：2411-2418.
[23] KALAL Z， MIKOLAJCZYK K， MATAS J. Trackinglearningdetection[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2011，34（7）：1409-1422.
[24] BABENKO B， YANG M H， BELONGIE S. Robust object tracking with online multiple instance learning[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2010， 33（8）：1619-1632.
[25] ZHANG K， ZHANG L， YANG M H. Realtime compressive tracking[C]// Proceedings of the 12th European Conference on Computer Vision. Berlin： SpringerVerlag， 2012： 864-877.