基于SURF的压缩跟踪算法研究*

李　倩,刘　坤

(上海海事大学 信息工程学院，上海 201306)



基于SURF的压缩跟踪算法研究*

李倩,刘坤

(上海海事大学 信息工程学院，上海 201306)

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

目标检测；SURF；压缩感知；目标跟踪

引用格式：李倩，刘坤．基于SURF的压缩跟踪算法研究[J].微型机与应用，2016,35(16)：63-66，71.

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<

(3)重构原始特征，将原始特征x从压缩的特征信号y中完整重现、最快速的方法就是通过l0范数来求解：

(1)

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

(2)

2　基于SURF的压缩跟踪算法

基于SURF算法的目标跟踪能够很好处理目标尺度变化和光照变化的场景，而压缩感知可以用很少的采样值几乎完整地重构出原始信号，故本文提出了基于SURF的压缩跟踪算法。该算法既保留了SURF特征的优点，减少了目标跟踪过程中一些冗余特征的计算，加快跟踪的实时性，同时在目标部分被遮挡和目标快速移动的场景下，仍能稳定地跟踪。

图1所示为本文算法的流程图，算法主要分为4个步骤：(1)选取目标特征并提取SURF特征；(2)通过压缩感知中的稀疏测量矩阵将高维的前景目标和背景特征投影到低维空间，而这些低维特征一方面几乎保留了原始图像中的所有信息，另一方面减少了后续跟踪的计算量；(3)通过一定的阈值对压缩的样本筛选，剔除小概率的样本，训练和更新分类器；(4)使用朴素贝叶斯分类器对下一帧目标待测图像进行分类，并确定其精确位置。下面将详细阐述算法的实现过程。

图1　算法流程图

2.1SURF特征提取

在SURF特征提取的过程中，采用了积分图实现特征的描述，由于积分图运用盒状滤波近似图像，极大地提高了特征提取的过程，而且提取的特征还具有旋转不变和尺度不变的特性[5，9]。

在图像G中一点(x,y)的值为ii(x,y),则SURF特征的提取包括以下5部分。

(2)提取特征点：首先通过Hessian矩阵粗略确定特征点，其次利用非极大抑制精确确定。

(3)确定特征点的主方向：以特征点为中心，6s为半径的圆中，通过使用haar小波，分别计算每个扇形区域中x、y方向的响应，其中响应模值最大的扇形方向即为特征点的主方向。

(5)特征点匹配：计算两幅图像中每一个特征点的欧式距离，其中d1、d2分别为最小和次小的距离值，若d1/d2≤α(文中取α为0.6),则认为这两个距离值对应的特征点匹配，否则剔除该点。

2.2特征压缩

本文采用的是提取过后的SURF特征，在压缩感知的理论基础上，对所得高维的特征进行降维处理，其公式如下：

v=Rx

(3)

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

(4)

Achlioptas证明了当ρ=1或者ρ=3时的矩阵满足Johnson-Lindenstrauss引理[2-3]，特别是当ρ=3的时候，矩阵中大部分的元素为0，大大减少了文中特征的计算量。

2.3样本的预处理

正负样本的质量会直接影响到跟踪结果的实时性和准确性，为了改变这种现象，对候选的样本进行预处理。设σ(样本像素值方差)为预处理的阈值，σi为候选样本的像素值方差，如果σi<0.5σ，则认为该样本不是目标样本。经过这样的筛选方法，不仅可以减少分类器分类的次数，减少计算量，加快跟踪的速度，而且还可以训练出能够更好区分背景和目标的分类器，提高跟踪的精确度。

一是推进《河湖长制宣传“六进”方案》深入实施，持续开展河湖长制系列化、多样化宣传，推动形成全社会共同关心河湖、建设河湖、保护河湖的良好局面。近两年应重点聚焦“进机关”“进党校”。

2.4分类器的构造及更新

将以上得到的低维特征向量v通过朴素贝叶斯分类器来建模，下面是朴素贝叶斯分类器的模型：

H(v)=

(5)

(6)

(7)

其中学习率λ>0，λ越小，目标模板更新速度就越快。

3　实验结果与分析

为了验证本文算法的跟踪效果，分别使用本文算法、CT算法和基于SURF跟踪算法对skating、football两个视频序列进行了对比跟踪，图2为目标跟踪结果对比图，其中实线框代表本文算法，虚线框代表CT，点线框代表基于 SURF跟踪算法。

图2　跟踪跟踪结果图

[10]中给出了跟踪精度的定义：

(8)

其中，ROIT代表实际的跟踪框，ROIG代表真实的目标框，实际跟踪框和真实目标框的区域的交集与两者区域的并集的比值即为跟踪精度。若目标跟踪精度低于0.5，则认为跟踪失败。

为了更形象地说明本文所提算法相对其他两种算法具有更高的跟踪精度，图3给出三者的跟踪精度对比图。

(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的跟踪算法。

表1　不同视频序列每秒运行的帧数　(f/s)

本文算法将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.

Research of compressive tracking algorithm based on SURF

Li Qian，Liu Kun

( College of Information Engineering, Shanghai Maritime University, Shanghai 201306,China)

As the basis of machine vision, target tracking technology has been widely used, but there are still a lot of problems. In order to deal with the problem of target tracking drift under illumination change and fast-moving scenarios, the compressive tracking algorithm based on SURF is presented in this paper. Firstly, it chooses the tracking target and extracts SURF features. Then, the SURF features can be projected to a randomly chosen low-dimensional space in combination with the compressive sensing theory to reduce its dimensions and computation time. Finally, it screens the compressed sample features and trains the classifiers with the online multi-instance learning algorithm to achieve the real-time accurate tracking of object in the complex environment. From the vast contrast experimental results among the traditional SURF algorithm, compressive tracking algorithm and the algorithm proposed in this paper, we can see that the algorithm greatly reduces the calculation of the target in the process of tracking compared with the compressive tracking algorithm and SURF algorithm. Meanwhile the accuracy of tracking is improved also.

target detection;speed up robust feature;compressive sensing;object tracking

航空科学基金(2013ZC15005)

TP391

A

10.19358/j.issn.1674- 7720.2016.16.019

2016-03-25)

李倩(1991-)，通信作者，女，硕士研究生，主要研究方向：图像处理。E-mail：liqian6522@163.com。

刘坤(1982-)，女，博士，副教授，主要研究方向：智能信息处理、图像处理。