《电子技术应用》
您所在的位置:首页 > 嵌入式技术 > 设计应用 > 基于SURF的压缩跟踪算法研究
基于SURF的压缩跟踪算法研究
2016年微型机与应用第16期
李倩,刘坤
上海海事大学 信息工程学院,上海 201306
摘要: 目标跟踪技术作为机器视觉领域中的基础,有着广泛的应用,但其仍然存在许多问题。为了解决目标在光照变化和快速移动场景下跟踪漂移的问题,提出了基于SURF的压缩跟踪算法。首先选择跟踪目标并提取SURF特征,其次采用压缩感知理论对SURF高维特征降维,来减少特征描述的维数和计算时间,最后筛选压缩后的样本特征并训练分类器,来实现对多种复杂场景下目标实时准确跟踪。通过实验与传统的SURF算法和Compressive Tracking(CT)算法的对比,证明该算法不仅大大减少了目标在跟踪的过程中的计算量,其跟踪的实时性和准确性相较于CT算法和SURF算法都有所提高。
Abstract:
Key words :

  李倩,刘坤
  (上海海事大学 信息工程学院,上海 201306)

       摘要:目标跟踪技术作为机器视觉领域中的基础,有着广泛的应用,但其仍然存在许多问题。为了解决目标在光照变化和快速移动场景下跟踪漂移的问题,提出了基于SURF的压缩跟踪算法。首先选择跟踪目标并提取SURF特征,其次采用压缩感知理论对SURF高维特征降维,来减少特征描述的维数和计算时间,最后筛选压缩后的样本特征并训练分类器,来实现对多种复杂场景下目标实时准确跟踪。通过实验与传统的SURF算法和Compressive Tracking(CT)算法的对比,证明该算法不仅大大减少了目标在跟踪的过程中的计算量,其跟踪的实时性和准确性相较于CT算法和SURF算法都有所提高。
  关键词:目标检测;SURF;压缩感知;目标跟踪  

0引言
  目标跟踪技术作为机器视觉中的一个重要研究领域,其应用已经得到广泛的普及。但目前目标跟踪仍面临着一些亟待解决的问题,如目标形态的改变、外界光照场景的变化、目标部分遮挡、快速移动或突然停止等。近年来目标跟踪的主流方法多是基于特征的匹配[1],提取目标中具有不变性的特征(角、点、边缘等),通过目标特征的模板匹配来实现目标的跟踪过程,它的优点是计算量较小,抗干扰能力强,但是对于一些较大尺寸的目标,仍然无法很好地实时跟踪,且不能很好地处理目标遮挡的问题。压缩感知理论[24]的引入,减少了目标跟踪算法的计算量,同时在处理一些复杂场景上有了突破性的进展,提高了目标跟踪的鲁棒性。2012年张开华等人提出了压缩跟踪算法(CT)[2],该算法提高了实时性,但是针对目标遮挡、光照变化这些问题有待提高。
  本文提出了一种将SURF特征[56]和压缩感知相结合的目标跟踪算法,在目标提取的时候选取了在图像发生平移、旋转等情况下仍具有强大表达能力的SURF特征,通过压缩感知理论中的稀疏测量矩阵,将高维空间的SURF特征投影到低维空间,同时通过一定的阈值对压缩的特征筛选并训练分类器,来实现目标的跟踪。通过实验验证,本文提出的算法不仅克服了目标遮挡、快速移动和光照变化的问题,还有效地提高了跟踪的实时性。
1压缩感知理论
  压缩感知理论[78]指出:如果原始图片序列提取的特征空间维度非常高,不利于后续的跟踪计算,那么这些特征就可以通过一个稀疏基来实现低维特征的投影,与此同时,投影后的低维特征仍将保留足够的信息去重构出高维的原始特征。
  下面将从3方面来阐述压缩感知理论。
  (1)信号的稀疏表示为x=Ψs,Ψ为稀疏基N×N矩阵,s为稀疏系数;
  (2)测量矩阵的设计Φ=M×N(M<<N),测量矩阵的关键作用就是在降低特征空间维数的同时又能保证原始特征x包含的信息的完整性,即y=Φx;
  (3)重构原始特征,将原始特征x从压缩的特征信号y中完整重现、最快速的方法就是通过l0范数来求解:
  QQ图片20160920194236.png

  然而l0范数的求解是一个很难实现的问题,为了能够更好地解决这个问题,DONOHO D和LOGAN B证实了如果特征信号足够稀疏,那么l0最小范数就可以完全等价于l1最小范数,同样可以得到相同的解,即:
  QQ图片20160920194242.png

2基于SURF的压缩跟踪算法
  基于SURF算法的目标跟踪能够很好处理目标尺度变化和光照变化的场景,而压缩感知可以用很少的采样值几乎完整地重构出原始信号,故本文提出了基于SURF的压缩跟踪算法。该算法既保留了SURF特征的优点,减少了目标跟踪过程中一些冗余特征的计算,加快跟踪的实时性,同时在目标部分被遮挡和目标快速移动的场景下,仍能稳定地跟踪。
  图1所示为本文算法的流程图,算法主要分为4个步骤:(1)选取目标特征并提取SURF特征;(2)通过压缩感知中的稀疏测量矩阵将高维的前景目标和背景特征投影到低维空间,而这些低维特征一方面几乎保留了原始图像中的所有信息,另一方面减少了后续跟踪的计算量;(3)通过一定的阈值对压缩的样本筛选,剔除小概率的样本,训练和更新分类器;(4)使用朴素贝叶斯分类器对下一帧目标待测图像进行分类,并确定其精确位置。下面将详细阐述算法的实现过程。
  

图像 001.png

  2.1SURF特征提取
  在SURF特征提取的过程中,采用了积分图实现特征的描述,由于积分图运用盒状滤波近似图像,极大地提高了特征提取的过程,而且提取的特征还具有旋转不变和尺度不变的特性[5,9]。
  在图像G中一点(x,y)的值为ii(x,y),则SURF特征的提取包括以下5部分。
  (1)积分图构造:ii(x,y)=∑x′≤x,y′≤yg(x′,y′),其中g(x′,y′)为点(x′,y′)的灰度值。
  (2)提取特征点:首先通过Hessian矩阵粗略确定特征点,其次利用非极大抑制精确确定。
  (3)确定特征点的主方向:以特征点为中心,6s为半径的圆中,通过使用haar小波,分别计算每个扇形区域中x、y方向的响应,其中响应模值最大的扇形方向即为特征点的主方向。
  (4)生成特征描述子:以主方向为中心轴,构造一个20σ×20σ的正方形区域,并将其划分为16个子区域,每个子区域上采样25个点,计算采样点的haar小波响应,记为dx、dy,并记录∑dx、∑dy、∑|dx|、∑|dy|,一共4×4×4=64维,归一化后即可得到特征描述子。
  (5)特征点匹配:计算两幅图像中每一个特征点的欧式距离,其中d1、d2分别为最小和次小的距离值,若d1/d2≤α(文中取α为0.6),则认为这两个距离值对应的特征点匹配,否则剔除该点。
  2.2特征压缩
  本文采用的是提取过后的SURF特征,在压缩感知的理论基础上,对所得高维的特征进行降维处理,其公式如下:
  QQ图片20160920194247.png

  其中x为特征向量,R为稀疏测量矩阵,v为压缩的特征向量。在该算法中,最核心的部分就是稀疏测量矩阵的选取,本文采用的是一个极具典型且满足有限等距性(RIP)的测量矩阵:随机高斯矩阵RRn×m,矩阵中的每一个元素rij~N(0,1),它的定义如下:
  QQ图片20160920194251.png

  Achlioptas证明了当ρ=1或者ρ=3时的矩阵满足JohnsonLindenstrauss引理[23],特别是当ρ=3的时候,矩阵中大部分的元素为0,大大减少了文中特征的计算量。
  2.3样本的预处理
  正负样本的质量会直接影响到跟踪结果的实时性和准确性,为了改变这种现象,对候选的样本进行预处理。设σ(样本像素值方差)为预处理的阈值,σi为候选样本的像素值方差,如果σi<0.5σ,则认为该样本不是目标样本。经过这样的筛选方法,不仅可以减少分类器分类的次数,减少计算量,加快跟踪的速度,而且还可以训练出能够更好区分背景和目标的分类器,提高跟踪的精确度。
  2.4分类器的构造及更新
  将以上得到的低维特征向量v通过朴素贝叶斯分类器来建模,下面是朴素贝叶斯分类器的模型:
  QQ图片20160920194308.png

  其中y=0表示负样本,y=1表示正样本,p(vi|y=1)和p(vi|y=0)均服从高斯分布,μ1i、σ1i、μ0i、σ2i分别为正负样本条件概率的均值和方差,选取分类器中响应最大的值对应的区域作为新的目标区域。文中参数的更新规则如下:
  QQ图片20160920194624.png

  其中学习率λ>0,λ越小,目标模板更新速度就越快。
3实验结果与分析
  为了验证本文算法的跟踪效果,分别使用本文算法、CT算法和基于SURF跟踪算法对skating、football两个视频序列进行了对比跟踪,图2为目标跟踪结果对比图,其中实线框代表本文算法,虚线框代表CT,点线框代表基于 SURF跟踪算法。
  

图像 002.png

  参考文献[10]中给出了跟踪精度的定义:
  QQ图片20160920194330.png

  其中,ROIT代表实际的跟踪框,ROIG代表真实的目标框,实际跟踪框和真实目标框的区域的交集与两者区域的并集的比值即为跟踪精度。若目标跟踪精度低于0.5,则认为跟踪失败。
  为了更形象地说明本文所提算法相对其他两种算法具有更高的跟踪精度,图3给出三者的跟踪精度对比图。
  

图像 003.png

  (1)skating序列中,如图2(a)、图2(c)所示,基于SURF跟踪算法由于在跟踪的过程中需要目标特征更新,特别是当目标快速移动和被遮挡时很容易产生一些模糊的特征,从而使目标跟踪结果出现较大的误差。跟踪精度曲线图3(a)中,25~75帧由于目标快速移动出现了目标漂移的现象,150~190帧之间由于目标排位过程中被遮挡,导致目标跟踪跟踪失败。CT算法虽然对目标移动和光照变化不大的情况下跟踪效果较好,但是在图2(b)帧中,光线突然变暗导致目标跟踪结果甚至比基于SURF跟踪算法要差。然而本文算法在处理此种场景时,并没有出现以上的状况。
  (2)football序列中,如图2(d)、图2(e)所示,由于目标的激烈争夺,会出现目标快速移动、目标碰撞的现象,基于SURF跟踪算法出现了目标漂移;如图2(f)所示,当目标被遮挡时,基于SURF跟踪算法和CT算法均出现目标丢失。在跟踪精度曲线图3(b)中,由于目标全程均在快速移动致使基于SURF跟踪算法跟踪精度不高,在280~295帧之间,目标被遮挡,基于SURF跟踪算法和CT算法跟踪失败。本文算法针对以上情况均跟踪较好。
  为了衡量算法的实时性,分别度量football、skating图像序列每秒处理的帧数,实验结果如表1所示。文中的算法均采用MATLAB2013a运行,硬件环境为Windows 7系统,第二代英特尔酷睿i52450M处理器和2GB内存,实时性均可以达到要求。从实验数据中可以看出本文算法优于CT、基于SURF的跟踪算法。

图像 004.png

       本文算法将SURF特征和压缩感知理论结合,保留了SURF特征对光照和尺度变化不敏感以及压缩感知能够减少运算量的特点,并在训练分类器时对样本进行了预处理,保留区分度高的样本。通过实验对比得出,本文算法在处理光照变化、目标快速移动和目标部分遮挡方面,要优于基于SURF跟踪算法和CT算法,同时,算法的时效性也有了明显的提高。
4结论
  本文提出了一种基于SURF的压缩跟踪算法,将SURF特征所具有的位置、尺度和旋转不变的特性融入到压缩感知理论中,实现了目标的稀疏表示,并有效地减少了高维特征的计算量,大大加快了目标跟踪的速度。在优化分类器方面,通过阈值筛选出一些目标与背景区别度较低的样本,不仅减少了分类器分类的次数,而且还提高了样本的质量。通过实验对比可知,改进后的算法在目标快速移动、目标遮挡和光照变化的环境下有着相对良好的跟踪效果,并且实时性也明显有了提高。本文算法在目标提取的过程中主要针对的是固定的目标特征,研究实现多个特征的融合,使跟踪算法能够处理更为复杂的场景将是未来研究的热点。
  参考文献
  [1] 王露露,张洪 ,高忠国.基于SURF的目标跟踪算法[J].江南大学学报(自然科学版), 2012,11(5):515519.
  [2] Zhang Kaihua, Zhang Lei, YANG M H. Fast compressive tracking[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2014, 36(10):20022015.
  [3] Zhang Kaihua, Zhang Lei, YANG M H. Realtime compressive tracking[C]. European Conference on Computer VisionECCV 2012, 2012,7574(1):864877.
  [4] 马庆涛,唐加山.基于压缩感知的测量矩阵研究[J].微型机与应用, 2013,32(8):6467.
  [5] Zhang Kaihua, Song Huihui. Realtime visual tracking via online weighted multiple instance learning [J]. Pattern Recognition, 2013, 46(1):397–411 .
  [6] BAY H, ESS A, TUYTELAARS T, et al. Speededup robust features (SURF)[J]. Computer Vision & Image Understanding, 2008, 110(3):346359.

  [7] Li Hanxi, Shen Chunhua, Shi Qinfeng. Realtime visual tracking using compressive sensing [J]. IEEE Conference on Computer Vision Pattern Recognition, 2011,42(7):13051312.
  [8] JAVANMARDI M, YAZDI M, SHIRAZI M A M. Fast and robust L0tracker using compressive sensing[C]. 2015 2nd International Conference on Pattern Recognition and Image Analysis (IPRIA), 2015:16.
  [9] PANCHAM A, WITHEY D, BRIGHT G. Tracking image features with PCASURF descriptors[C]. 2015 14th IAPR International Conference on Machine Vision Applications (MVA), IEEE, 2015:365368.
  [10] EVERINGHAM M, GOOL L V, WILLIAMS C K I, et al. The pascal visual object classes (VOC) challenge[J]. International Journal of Computer Vision, 2010, 88(2):303338.