基于多特征融合的目标跟踪算法

1、基于多特征融合的目标跟踪算法单东晶1，田海静1，马宝红1（1.重庆通信学院 重庆市 400035）照片尺寸为20mm*30mm；最好不用红色背景摘 要：本文以压缩感知、随机投影理论等为基础,比较验证国内外主要方法，提出了一种在级联粒子滤波器框架下的多特征集成的目标跟踪算法。算法中采用了两类特征：颜色自相关图与基于随机投影降维的haar-like特征。其中降维haar-like特征被用于压缩感知跟踪算法中。实验采用了当前主流跟踪算法用于性能对比，测试视频的来源涵盖复杂背景、严重遮挡、剧烈的形变等问题。实验结果可以表明本文算法对比其他算法的性能优势。关键词：压缩感知；稀疏表示；级联粒子滤波器；随机

2、投影；目标跟踪Visual Tracking Based on Multi-Features CombinationDongjing Shan1, Haijing Tian1, Baohong Ma1(1.Chongqing Communication Institution ChongQing 400035)Abstract: This method is based on the framework of cascade particle filter,and two features are integrated under it,which are color correlogram

3、and down-sampling haar-like feature after dimensionality reduction by random projection. The emphasis will be placed on the down-sampling haar-like feature, whose dimensionality has been reduced significantly using random projection and is used in a sparse representation tracking method. The random

4、projection will maintain most of the information kept in the original large set of haar-like features and accelerate the execution speed significantly.Keywords: Compressive sensing; Sparse representation; Cascade particle filter; Random projection; Visual tracking9目标跟踪是机器视觉、人工智能领域研究的热点问题之一,在智能视频监控、交

5、通控制、人机交互、机器人导航等方面有着很好的或者潜在的应用价值.目标跟踪面临的挑战、待解决的问题主要是需要采用有效的特征,建立鲁棒的目标模板以及有效的更新方法,使得算法整体对目标遮挡、背景干扰、光照变化、噪声等具有鲁棒性. 针对目标跟踪领域存在的问题,本文提出了一种基于级联粒子滤波器框架的多特征集成跟踪器算法. 算法联合了颜色自相关图1和降维haar-like特征,颜色自相关图可以利用到目标颜色的空间分布信息,而降维haar-like特征采用随机投影理论对全尺度的haar-like特征进行降维,降维后的向量能够保持绝大部分的信息,该特征能利用到目标表面丰富的纹理梯度信息,与颜色自相关图形成互补

6、. 级联粒子滤波第一级采用颜色自相关图特征,第二级采用压缩感知跟踪算法,并且把降维haar-like特征应用于第二级中.收稿日期：2014-06-25 作者简介：单东晶，男，重庆通信学院，研究生科参谋。1 相关研究目前国际上目标跟踪领域有海量的文献,按照目标跟踪的框架可以大致分为三类：基于概率模型的算法、基于轨迹优化的算法和基于分类器的算法. 概率模型算法经典的主要有mean-shift算法2、卡尔曼滤波3、粒子滤波算法4等,其中粒子滤波通过采样大量粒子可以模拟任何形式的概率分布,在目标跟踪领域得到了广泛的应用,衍生出了很多经典的算法,例如IPCA、稀疏表示等算法. 基于轨迹优化的算法一般有基

7、于全局轨迹优化的离线跟踪算法5,基于K最短路径6、路径匹配7等目标跟踪算法. 这些算法都是通过优化准则例如贪心法、动态规划等来获取最优或者次最优的路径. 基于分类器的跟踪算法文献十分丰富，不同的文献设计了不同的特征、采用了不同的分类器等,单从分类器类型来说有贝叶斯分类器8,自行设计的树形9、森林分类器10,boosting分类器11等等.有关多特征融合的跟踪算法主要有：Valtteri Takala等在2007年提出的多目标跟踪算法7融合了三类特征：颜色自相关图、LBP29纹理信息和运动信息. 其中运动信息的提取是基于目标运动的连续性,包括速度大小和方向的连续性,如下式提取出每个候选目标块的运

8、动信息权重：其中表示目标块索引,是跟踪视频帧索引,是速度大小与方向加权权重,前后两项分别表示速度矢量的大小和方向信息.候选块基于最近邻矩阵分配它们对应的track,该算法还引入了分离合并事件检测的模块,主要用来处理目标块相互间发生遮挡的问题.Ju Hong Yoon等在2012年提出了基于多跟踪器集成的目标跟踪算法,该算法的每一个跟踪器都采用不同的特征,对目标形变、噪声、背景变化等有相应的适应能力,集成跟踪器主要基于两点,一个是跟踪器本身的跟踪可靠性,二是它们之间的转移概率,二者相辅相成. 跟踪器的可靠性更新标准如下：是归一化系数，是该跟踪器的观测似然度,该跟踪器的跟踪可靠性与其观测似然度有关

9、,同时也与其它跟踪器的转移概率有关,为某跟踪器转入另一跟踪器的概率,和式表示的是所有其它跟踪器转移到某跟踪器的概率和.上式为转移概率矩阵的更新公式,矩阵的元素,表示跟踪器转入跟踪器的概率.Yuan Li，Haizhou Ai等在2008年提出低帧率下多跟踪器集成的级联粒子滤波器算法13. 该算法的每一级可以采用不同的特征作为观测模型. 首先第一级粒子经过本级的观测模型赋予权值,再根据权值进行粒子重采样,重采样之后的粒子赋予完全相等的权值(), 后验概率分布采用粒子的分布密度模拟,而不再是粒子的权重. 这些重采样之后的粒子有利于粒子滤波倾向于该级观测模型所指定的目标区域,接下来一级粒子滤波的观测

10、模型则重新给这些相同权重的粒子赋予权值,再通过重采样进一步锁定到目标区域.2 多特征集成跟踪算法多特征集成的跟踪算法是在级联粒子滤波框架下采用多特征构造多级粒子观测模型,通过粒子重采样模拟多级概率分布,从而准确找出最佳粒子。在级联粒子滤波框架内,算法采用了颜色自相关图与haar-like特征两种特征,该框架实际上允许多类特征,出于计算效率的考虑这里只采用了两类,并且这两类特征一个基于颜色一个基于纹理梯度信息,具有较好的互补性. 算法的重点将落在haar-like特征上,在这一级我们采用的跟踪器是基于稀疏表示的跟踪器,并且结合国际上新颖的设计提出了本文的算法. 首先,稀疏表示跟踪器本文采用了目标

11、模板与背景模板的模板集形式,并且使用OMP算法求解优化问题14,而不是原算法4解lasso问题的LARS算法. OMP算法的采用极大的提高了算法速度. 其次,原算法4采用的像素特征过于原始,没有提取高层信息,我们的算法采用了全尺度的haar-like特征向量,并且通过随机投影理论做降维,得到了低维的特征向量用于稀疏表示算法中.2.1 多特征融合的级联粒子滤波框架粒子滤波的基本过程是已知所有时刻的观测数据去估计后验概率,概括为如下公式：解这个问题的直接的方法是求出联合观测概率：但是这样会导致大量的计算资源浪费在权值极低的粒子上,降低了运算效率并且会降低跟踪效果,所以文献13提出的级联粒子滤波器很

12、好的克服了这个问题,它把计算资源尽量的集中在有效粒子上,并且在每一级滤波时都可以采用比上一级少得多的粒子数,提高运算效率的同时还不会损失性能.首先定义： 图1 级联粒子滤波示意图推出： 级联粒子滤波的过程可以叙述如下：在第阶段，需要从建议分布采样一组加权粒子. 该建议分布在上一阶段已经由另一组加权粒子模拟: . 从该建议分布重采样出的粒子为:. 这些粒子的权值初值全设为相等,接下来通过第级的观测模型修改这些粒子的权值为：粒子集可用来模拟概率 的分布. 重要性重采样重复进行直到第阶段，于是最终得到级的观测后验分.每级重采样的粒子数目可以依次递减,这是因为上一级观测模型的限制可以有效的缩小粒子需要

13、搜索的范围,如图1所示,可见粒子重采样的过程.图1来源于Yuan Li 200713,一共有三级粒子滤波,每一级在前一级观测模型基础上重采样的粒子数有很大程度减少,这样为后级的粒子滤波采用较复杂、运算复杂度较高的观测模型提供了条件.在本文算法中,第一级采用了颜色自相关图1的特征,该特征简单有效,使用范围较广,主要是基于直方图的距离匹配来计算观测模型,距离的倒数通过归一化之后可得出每个粒子的观测似然度.本文的重点放在第二级使用降维haar-like 特征上.2.2 基于降维haar-like特征的压缩感知跟踪算法2.2.1 基于随机投影的降维haar-like特征对haar-like特征的降维如

14、图所示,在粒子滤波框架下使用的候选粒子代表的候选目标块若干,需要对每一个图像块提取出全尺度的haar-like特征,该特征的维数会非常大,基本上会有至 的量级,所以应用随机投影矩阵对这些超长特征向量做降维显得很有必要,并且我们要尽量保持住原有的包含信息,以便不损失特征的区分力.在图中,跟踪帧提取的图像块被依次进行haar-like特征提取,得到每一个图像块的超长特征描述向量,接下来就是用随机矩阵进行降维的过程.使用随机矩阵降维的过程：是需要降维的原始向量,维数为；为随机矩阵;是降维之后的向量,维数为,这里有.图2 haar-like特征降维示意图为了降维之后的向量尽量保持原有长向量信息,需要矩

15、阵满足等距约束条件(RIP21),一般的随机高斯矩阵 满足会有满足RIP条件,但是这个高斯矩阵不是稀疏的,在计算全尺度haar-like特征上会带来很大的运算代价,于是本算法采用了另一种满足等距约束条件的稀疏投影矩阵，既可以保持原向量大部分信息，又可以极大提升运算效率。随机矩阵 的设计如公式12.Achlioptas15证明当或时并且 ，以概率 随机矩阵 满足Johnson-Lindenstrauss引理，当时,有三分之二的矩阵元素都是零,降低了很大部分的计算量.另外Li et al.16证明时,矩阵满足渐进正态性,例如当时,经过稀疏矩阵投影之后的低维数据与高维数据用随机高斯矩阵降维后的低维数

16、据具有相同的期望、方差值,从而说明作者设计的矩阵与高斯随机矩阵在同等条件下可以满足等距约束条件. 这个同等条件就是的行数满足的条件. 本算法采用的设置,可得到一个非常稀疏的随机投影矩阵. 对于矩阵每一行,非零元不超过6个 (),总体计算复杂度为,为矩阵 的行数.关于矩阵行数的选择,Candes,E17等给出了更紧的条件,证明当,且为常数时,投影矩阵(高斯、等) 满足RIP条件. 当，有. 本文算法中选取.2.2.2 基于压缩传感的跟踪算法本文的压缩感知算法是基于OMP优化的解稀疏解问题. 字典包含的原子有目标模板与背景模板,同时取消了噪声模板,同时不再解lasso 问题,而是 Algorith

17、m 1 OMP算法流程Require: 归一化的观测值：模板集：恢复残差：迭代次数：Ensure：恢复出的系数1初始化残差残差，索引集为空，选择模板集合为空集.2 循环求近似可行解3 得出近似解Retrieve signalaccording toand;解一个最小化问题(求近似解). 目标模板若干,背景模板可以采用高斯背景建模构造背景,也可以采用压缩感知背景模型建模(CSBM18). 求解当前帧目标位置可概括如下：首先,该算法也是基于粒子滤波框架的,最核心的一点就是设计粒子观测模型找出最佳粒子. 那么本文中,采用的观测模型是粒子到其字典投影的距离. 由Hanxi Li18的思想,我们有公式形

18、式如下：为字典,为目标模板集,共包含个目标模板, Algorithm 2 目标模板集更新算法流程1:是跟踪到的目标粒子2:是公式13的解,是目标模板集上的系数3:是目标模板集的权重,初始值为4:是预先给定的一个阈值参数5:由更新目标模板的权值6:,这里表示比较相似度的函数,表示有最大系数的相应目标模板,其中 7:归一化使得权值和为背景模板集,来自CSBM模型,共有个模板.为候选粒子,需要注意的是,背景模板的选择对于每一个候选粒子都是不同的,需要按照粒子坐标在背景模型上对应坐标处选取. 另外,表示对字典元素、候选粒子(图像块)提取haar-like 特征并得到降维向量的过程,也就是说这里的所有字

19、典元素、候选粒子向量等均为haar-like特征降维之后的维特征.上述稀疏解的获得采用了OMP算法(正交匹配追踪算法),OMP算法解的流程如算法1 所示.对每个粒子求解稀疏系数之后,粒子的评价标准如下：是字典,为在目标模板上的稀疏系数. 取最小的粒子被选为最佳粒子. 很显然,每个粒子仅与它在目标模板上的投影做对比,这样就可以滤掉那些与背景十分相似的粒子的影响,因为这类粒子由于与背景相似导致在目标模板上的线性组合几乎为零,分解系数基本都落在背景模板上. 显然这种思想可以有效的抵抗背景的干扰.最后,需要提到目标模板的更新问题. 本算法采用了若干个目标模板,将采用加权更新的模式对这个模板集做维护,以

20、使得模板集与目标的形态最为符合. 模板集加权更新算法如算法2所示.3 实验分析本文算法的实验采用了PETS等开放数据集以及一些自采数据,并且使用了IPCA19、MIL11、-tracker4等主流算法做对比实验. 在2.8GHZ P4 CPU与2GB内存的电脑上四类算法运行速度对比见表1. 由于本文算法中的OMP求解通过适当改变残差可以获得极高的解出速度,用其替换原-tracker中对每一个粒子解一个lasso问题,所以算法执行速度获得了较大提升.算法的性能具体见下文的实验.算法速度s/frame算法框架源代码IPCA0.12粒子滤波（600粒子）matlabMIL1.8Boosting分类器

21、c-tracker6.7粒子滤波（600粒子）matlab本文算法0.62级联粒子滤波（第一级600粒子第二级300粒子）matlab表1 算法速度对比图3到图5是在三个数据集上的跟踪轨迹误差显示,每个图都采用了三种对比算法：IPCA、MIL和 -tracker.轨迹图的左上角文本框是每一个跟踪器的轨迹误差平均值,其下的图框是所用数据的图示. 由这些数据可以看出本文算法对强烈光照(图3、图5)、严重遮挡、形变(图4、图5)等处理得较为理想.表2是平均距离误差与正确跟踪帧数的百分比列表. 正确跟踪帧采用的评价标准为：给定跟踪框 与ground truth的目标框,它们覆盖的百分数定义如公式15.

22、图3 跟踪轨迹对比图: david11如果分数大于就认为该帧的跟踪框与ground truth一致,即跟踪正确。表2中黑体表示排图4 跟踪轨迹对比图: faceocc211名第一的项,下划线表示排名第二项. 数据集采用的基本上是有遮挡或者形变严重的数据. 图6到图7是跟踪器性能的图例显示, 采用了与本文算法关联最大的-tracker用于性能对比. 图6是一个被严重遮挡的人脸视频8,可见本文算法与-tracker都取得了很好的跟踪效果,-tracker由于稀疏性而对遮挡具有一定的鲁棒性,在没有相似背景干扰的情况下仍然能找出被遮挡的物体. 本文算法除了稀疏性对遮挡有鲁棒性之外,更重要的是有背景模板

23、集可以抵抗相似背景的干扰,适应性强于-tracker. 图7是自采的车辆行驶视频,黑色目标车辆超越白色车辆时有严重遮挡发生, -tracker在遮挡发生时产生了跟踪漂移,原因是相似背景对跟踪器有强烈干扰作用, 并且跟踪器一旦发生漂移就难以回到目标本身,本文算法则成功处理了遮挡, 原因在于背景模板集的使用限制了跟踪器锁定背景,提高了对目标遮挡的鲁棒性.4 结论本文提出了基于随机投影降维与压缩感知的跟踪算法. 该算法基于级联粒子滤波框架. 在这个框架下可以使用多个观测模型,也就是结合使用多种不同的特征以实现对目标更准确的跟踪.算法中采用了颜色自相关图与随机矩阵降维的haar-like特征并应用于压

24、缩感知跟踪算法里.该算法具有较强的可扩展性,可以根据具体的应用场景选择合适的特征,甚至增加特征的层数.算法改进的方向主要是设计 表2 跟踪轨迹平均误差和正确跟踪帧数百分比测试数据IPCAL1-trackerMIL本文算法David11 7.553 / 0.90 43.281 / 0.70 15.529 / 0.54 1.418 / 0.95Car19 1.096 / 1.0 33.484 / 0.60 40.474 / 0.41 0.956 / 1.0Sylv4 40.375 / 0.55 44.480 / 0.41 7.309 / 0.78 12.516 / 0.76Girl4 44.808

25、 / 0.66 12.120 / 0.97 31.604 / 0.71 10.378 / 0.96 Faceocc1119.651 / 0.99 10.195 / 0.93 15.175 / 0.98 8.356 / 1.0 Faceocc211 17.245 / 0.80 18.225 / 0.69 15.387 / 0.95 8.231 / 0.97 Walker20 44.833 / 0.71 86.456 / 0.71 193.612 / 0.65 9.715 / 0.89 图6 遮挡人脸跟踪关键帧对比结果. 帧数：#415,#428,#436,#445,#460图7 城市道路车辆跟踪

26、关键帧对比结果. 帧数：#81,#90,#186,#222,#229图5 跟踪轨迹对比图: sylv4更好的目标模板集更新机制,使之具有覆盖性的同时也具有对错误模板的容错能力,能更好的防止跟踪器的漂移.参 考 文 献1 Qi Zhao, Hai Tao. Object tracking using color correlo- gramC. Visual Surveillance and Performance Evaluation of Tracking and Surveillance, 2005. 2nd Joint IEEE Inter- national Workshop on. I

27、EEE, 2005, 263-2702 Dorin Comaniciu, Peter Meer. Mean shift: A robust ap- proach toward feature space analysisJ. Pattern Analysis and Machine Intelligence, IEEE Transactions on. 2002, 24(5):603-619 3 Amir Betser, Patricio Vela, Allen Tannenbaum. Automatic tracking of ying vehicles using geodesic sna

28、kes and Kalman lteringC. Decision and Control, 2004. CDC. 43rd IEEE Conference on. IEEE, 2004, vol. 2, 1649-1654 4 Xue Mei, Haibin Ling. Robust visual tracking and vehicle classi cation via sparse representationJ. Pattern Analy- sis and Machine Intelligence, IEEE Transactions on. 2011, 33(11):2259-2

29、272 5 Steve Gu, Ying Zheng, Carlo Tomasi. Linear time online tracking and lower envelope algorithmsC. Computer Vision (ICCV), 2011 IEEE International Conference on. IEEE, 2011, 1840-18466 Jerome Berclaz, Francois Fleuret, Engin Turetken, Pascal Fua. Multiple object tracking using k-shortest paths op

30、timizationJ. Pattern Analysis and Machine Intelligence,IEEE Transactions on. 2011, 33(9):1806-18197 Valtteri Takala, Matti Pietikainen. Multi-object tracking using color, texture and motionC. Computer Vision and Pattern Recognition, 2007. CVPR'07. IEEE Conference on. IEEE, 2007, 1-7 8 Dan Li, Ke

31、rry D Wong, Yu Hen Hu, Akbar M Sayeed. Detection, classi cation, and tracking of targetsJ. Signal Processing Magazine, IEEE. 2002, 19(2):17-29.9 Rainer W Lienhart, Luhong Liang, Alexander Kuranov, et al. Detector tree of boosted classi ers for real-time object detection and trackingZ, 2007.USPatent

32、7,203, 669.10 Aiping Wang, Guowei Wan, Zhiquan Cheng, Sikun Li. An incremental extremely random forest classierfor online learning and trackingC.Image Processing (ICIP), 2009 16th IEEE International Conference on. 1449-1452.11 Boris Babenko, Ming-Hsuan Yang, Serge Belongie. Visual tracking with onli

33、ne multiple instance learningC. Comput- er Vision and Pattern Recognition, 2009. CVPR 2009. IEEE Conference on. IEEE, 2009, 983-990.12 Xiaoyu Wang, Tony X Han, Shuicheng Yan. An HOG-LBP human detector with partial occlusion handlingC. Computer Vision, 2009 IEEE 12th International Conference on. IEEE

34、, 2009, 32-39.13 Yuan Li, Haizhou Ai, Takayoshi Yamashita, Shihong Lao, Masato Kawade. Tracking in low frame rate video: A cas- cade particle lter with discriminative observers of di erent life spansJ. Pattern Analysis and Machine Intelligence, IEEE Transactions on. 2008, 30(10):1728-1740.14 Joel A Tropp, Anna C Gilbert. Signal recovery from random measurements via orthogonal matching pursuitJ. Information Theory, IEEE Transaction