基于SIFT的压缩跟踪算法

王权+刘侍刚+彭亚丽+裘国永

摘 要： 为了克服基于灰度特征信息的跟踪算法在复杂的环境下无法区分目标和背景的缺陷，提出基于SIFT的压缩跟踪算法。该算法采用改进的SIFT特征提取方式，结合压缩感知理论对特征进行有效的降维，以在线多实例学习算法训练分类器，实现在出现目标偏移、姿态变化和光暗变化等情况下对目标实时准确的跟踪。实验结果表明，该算法能够在复杂环境下实现目标的准确实时跟踪。

关键词： SIFT； 压缩感知； 目标跟踪； 降维

中图分类号： TN911.7?34； TP311.1 文献标识码： A 文章编号： 1004?373X（2014）15?0062?03

Compressive tracking algorithm based on SIFT

WANG Quan1， 2， LIU Shi?gang2， PENG Ya?li1， 2， QIU Guo?yong2

（1. Key Laboratory of Modern Teaching Technology， Ministry of Education， Xian 710062， China；

2. School of Computer Science， Shaanxi Normal University， Xian 710062， China）

Abstract：To overcome the shortcoming that the tracking algorithm based on the gray feature information can not distinguish the target from its complex background， the compressive tracking algorithm based on SIFT is presented in this paper. The modified SIFT feature extraction mode is used in the algorithm to reduce the feature dimensions in combination with the theory of compressed sensing， so as to train the classifiers with the online multi?instance learning algorithm， and to achieve the real?time accurate tracking of target when target drifting， posture change and illumination change occur. The experiment results show that the algorithm can realize the the real?time accurate tracking of target in the complex environment.

Keywords： SIFT； compressed sensing； target tracking； dimensionality reduction

0 引 言

基于检测的分类模型在跟踪领域越来越受到重视。分类模型先检测再跟踪，充分利用了背景信息，在应对部分遮挡和背景与目标相似的情况有良好的跟踪效果。为了解决目标在跟踪过程中可能存在的姿态变化问题，Grabner引入了在线学习的方式[1]，但分类器学习时会出现正样本的不确定性。Babenko采用多实例学习将多个实例组成的包作为训练数据[2]。实验证明MIL可有效解决偏移问题，但易受新更新目标模板和噪声影响，其选取的灰度信息无法很好地区别目标和背景。Lowe提出了SIFT图像特征[3]，其具有尺度不变性，并且在应对旋转、光暗、视角和尺度变化的情况时有很好的鲁棒性。但SIFT特征维数高，不适合实时跟踪算法。所以如何大量减少特征维数具有现实意义。而近些年Wright 提出的基于压缩感知理论的稀疏表示算法[4]在这方面取得很好的效果，压缩后的低维空间仍然能很好地保留高维空间的数据结构。同时使用模板子空间重构稀疏性实现对目标的逼近的目标跟踪算法[5]也证明了在应对部分遮挡时的有效性。

本文提出了一种基于SIFT特征和压缩感知的目标跟踪算法。标记视频序列首帧图像，在多实例模型正集合包内提取改进SIFT特征，使用满足RIP条件的随即高斯矩阵完成SIFT特征构成的原图像特征空间的投影，在得到的低维压缩空间内，将正样本和负样本通过计算各自的稀疏编码作为更新分类器的权重，使用朴素贝叶斯分类器在线学习更新分类器，认定得分最高的分类器所得到位置为下一帧目标出现的位置，完成对目标的实时跟踪。

1 视频图像特征

基于灰度信息的Haar?like特征只能描述图像特定方向的结构，不能很好地描述目标。SIFT特征在图像局部提取，其对旋转、尺度、和光照变化保持鲁棒性。但SIFT算法产生高维特征会影响实时跟踪效果，本文分别通过减少高斯金字塔层数、选定8方向直方图和使用稀疏矩阵实现特征降维。

将样本[x]生成的SIFT特征记为向量[Djx=dixi=1：n，j=1：m]，[n]为每个样本产生SIFT特征个数，[m]为每次采集的候选样本个数。[ltx0]表示初始[t]时刻标记的目标区域，在距离目标较近的区域随机提取正样本[Xα=xltx-ltx0<α]，在距离目标较远的地方随机选取负样本[X?，β=x?

2 基于压缩感知的目标表示与降维

2.1 稀疏表示与稀疏编码

压缩感知主要通过稀疏表示实现信号重构。由于原问题是NP难问题，所以转化为以下问题求解：

[a0=argmina1 subject to y-Da2<ε] （1）

本文通过使用在目标区域内提取的降维特征近似的构造过完备基，其中经过稀疏矩阵降维的代表性特征集合为[D=di|i=1：p]。其中：[di∈Rn]表示第[i]个向量化的特征；[n]表示目标区域提取原始特征的维数；[p]表示目标区域降维后的特征维数。

根据Mei提出的对噪声鲁棒的琐碎模板算法[6]定义过完备字典如下：

[?=D，E] （2）

式中[E=I，-I∈Rn×2n]表示处理噪声点的小模板，[I∈Rn×n]表示单位矩阵。

根据式（1）计算每一个特征向量的稀疏编码，得到样本的稀疏系数矩阵[L=l1，l2，…，lp]作为计算分类器权重的训练数据。

2.2 特征降维

Ke采用主成分分析算法PCA替换SIFT中的直方图计算描述子将维数降低[7]，但因为投影矩阵导致其具有不完全的仿射不变性。相比较PCA，近年来利用基于压缩感知理论的稀疏表示算法[4]，利用符合压缩感知RIP条件的随即感知矩阵对多尺度图像进行降维。根据Johnson?Lindenstrauss推论[8]，WMIL算法[9]中，选取的投影矩阵满足要求，本文选定同样矩阵完成降维工作，其中[s]取值为3：

[rcv=s×1 with probability 12s0 with probability 1-1s-1 with probability 12s] （3）

样本区域所提取的特征向量经过降维可表示为：

[Djx*rcv=Djdix|i=1：p，p?n] （4）

式中：[rcv]为[c×v]维的稀疏矩阵。通过稀疏矩阵（3）的投影，样本特征维数下降明显。

3 多实例在线学习算法

本文采取级联方式将弱分类器结合生成强分类器。其中分类器使用朴素贝叶斯分类器，每个样本[x][（n]维向量），它的低维表示是[v（p]维向量，[p?n）。]假定[v]中的各元素是独立分布的。其建立分类器如下所示：

[Hv=logi=1ppviy=1py=1i=1ppviy=0py=0] （5）

其中4个参数[μ1i，σ1i，μ0i，σ0i]通过[pvi|y=1～][Nμ1i，σ1i]和[pvi|y=0～Nμ0i，σ0i]描述，其中[σ1]和[μ1]可通过最大似然估计求得，参数更新为：

[μ1i←λμ1i+1-λμ1] （6）

[σ1i←λσ1i2+1-λσ12+λ1-λμ1i-μ12] （7）

式中：[λ]为学习因子，[λ>0。]

[σ1=1nk=0|y=1p=1vik-μ12] （8）

[μ1=1nk=0|y=1p=1vik] （9）

假定存在[R]个正样本[x1，j，j=0，…，R-1]和[T]个负样本[x0，j，j=R，…，R+T-1]，标记的首帧样本位置记为[x10，]那么正样本和负样本被分到[X+，X-]内，则正包的概率为：

[py=1|X+=j=0N-1wj0py1=1|x1j] （10）

式中[wj0]是衡量样本[x1j]和[x10]距离的权重函数：

[wj0=exp-lx1j-lx10σ2] （11）

其中[lx1j]和[lx10]即为由样本生成稀疏编码计算的样本距离[L=l1，l2，…，lp。]

4 测试结果与分析

本文算法对视频序列Tiger进行试验，视频中出现部分遮挡、视角与姿态变化、光暗变化和目标相似与背景的问题。为了更好地验证本算法的有效性，本文算法与最近提出的目标跟踪算法（增量学习跟踪算法IVT[10]、多实例学习跟踪算法MIL[2]和权重多实例学习跟踪算法WMIL[9]进行比较。在Windows 7下，用Matlab 2010实现整个算法，在Core i5 2.5 GHz处理器上的平均速度为3 f/s。跟踪前人工标记首帧目标所在位置选定出现光暗变化、部分遮挡和目标与背景相似的Tiger视频序列。4种算法实验结果如图1所示。图1中3行分别选自图像的202帧、278帧和350帧。

由图1可知IVT和MIL出现不同程度的偏移现象。对比WMIL和本文算法，202帧时出现明显的光暗变化和姿态变化，本文算法更能稳定地跟踪。从350帧可看出在出现目标被严重遮挡问题时，本文算法更能很好地区别背景和目标。因此，本文算法在稳定性和准确性方面优于其他3类算法。

使用跟踪目标中心和真实中心的欧式距离作为评判标准，距离数值大表明偏移目标远，每隔5帧图像选取图像，计算其数值与其他4种算法进行比较，中心位置误差如表1所示。

表1 各视频中心位置误差

[视频＼&IVT＼&MIL＼&WMIL＼&本文＼&tiger＼&14.639＼&34.771＼&10.843＼&9.034＼&]

由表1可以看出本文中心误差比较稳定，优于其他算法。从定量关系上说明本文算法在应对复杂环境时能更优地跟踪到目标。

5 结 语

本文提出了一种基于SIFT特征的压缩跟踪算法。将SIFT特征所具有对尺度、光照和姿态变化不敏感的特性融入多实例在线学习算法中，并结合压缩感知有效地对大数据量的特征值进行降维以及实现目标的稀疏表示，使其不仅获得更好的跟踪效果并实现了实时的目标跟踪。实验结果证明算法能够实现在尺度伸缩、形变和光暗变化情况下对目标实施准确的跟踪。本文算法的跟踪精度和稳定程度都高于基于灰度信息特征的跟踪算法。

参考文献

[1] GRABNER H， GRABNER M， BISCHOF H. Real?time tracking via online boosting [C]// British Machine Vision Conference. Edinburgh， UK： [s.n.]， 2006： 47?56.

[2] BABENKO B， YANG M， BELONGIE S. Robust object tracking with online multiple instance learning [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2011， 33 （8）： 1619?1632.

[3] LOWE D G. Distinctive image features from scale?invariant keypoints [J]. International Journal of Computer Vision， 2004， 60（2）： 91?110.

[4] WRIGHT J， ALLEN Y， GANESH A. Robust face recognition via sparse representation [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2009， 31（2）： 210?227.

[5] HAN Zhen?jun， JIAO Jian?bin， ZHANG Bao?chang. Visual object tracking via sample?based adaptive sparse representation [J]. Pattern Recognition， 2011， 44（9）： 2170?2183.

[6] MEI X， LING H. Robust visual tracking using l1 minimization [C]// International Conference on Computer Vision. Kyoto： [s.n.]， 2009： 1436?1443.

[7] KE Y， SUKTHANKAR R. PCA?SIFT： A more distinctive representation for local image descriptors [C]// IEEE Conference on Computer Vision and Pattern Recognition. Washington D C， USA： IEEE， 2004： 506?513.

[8] ACHLIOPTAS D. Database?friendly random projections： Johnson?Lindenstrauss with binary coins [J]. Journal of Computer and System Sciences， 2003， 66（4）： 671?687.

[9] ZHANG K， SONG H. Real?time visual tracking via online weighted multiple instance learning [J]. Pattern Recognition， 2013， 46（1）： 397?411.

[10] ROSS D， LIM J， LIN R， et al. Incremental learning for robust visual tracking [J]. International Journal of Computer Vision， 2008， 77（1/3）： 125?141.

参考文献

[1] GRABNER H， GRABNER M， BISCHOF H. Real?time tracking via online boosting [C]// British Machine Vision Conference. Edinburgh， UK： [s.n.]， 2006： 47?56.

[2] BABENKO B， YANG M， BELONGIE S. Robust object tracking with online multiple instance learning [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2011， 33 （8）： 1619?1632.

[3] LOWE D G. Distinctive image features from scale?invariant keypoints [J]. International Journal of Computer Vision， 2004， 60（2）： 91?110.

[4] WRIGHT J， ALLEN Y， GANESH A. Robust face recognition via sparse representation [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2009， 31（2）： 210?227.

[5] HAN Zhen?jun， JIAO Jian?bin， ZHANG Bao?chang. Visual object tracking via sample?based adaptive sparse representation [J]. Pattern Recognition， 2011， 44（9）： 2170?2183.

[6] MEI X， LING H. Robust visual tracking using l1 minimization [C]// International Conference on Computer Vision. Kyoto： [s.n.]， 2009： 1436?1443.

[7] KE Y， SUKTHANKAR R. PCA?SIFT： A more distinctive representation for local image descriptors [C]// IEEE Conference on Computer Vision and Pattern Recognition. Washington D C， USA： IEEE， 2004： 506?513.

[8] ACHLIOPTAS D. Database?friendly random projections： Johnson?Lindenstrauss with binary coins [J]. Journal of Computer and System Sciences， 2003， 66（4）： 671?687.

[9] ZHANG K， SONG H. Real?time visual tracking via online weighted multiple instance learning [J]. Pattern Recognition， 2013， 46（1）： 397?411.

[10] ROSS D， LIM J， LIN R， et al. Incremental learning for robust visual tracking [J]. International Journal of Computer Vision， 2008， 77（1/3）： 125?141.

参考文献

[1] GRABNER H， GRABNER M， BISCHOF H. Real?time tracking via online boosting [C]// British Machine Vision Conference. Edinburgh， UK： [s.n.]， 2006： 47?56.

[2] BABENKO B， YANG M， BELONGIE S. Robust object tracking with online multiple instance learning [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2011， 33 （8）： 1619?1632.

[3] LOWE D G. Distinctive image features from scale?invariant keypoints [J]. International Journal of Computer Vision， 2004， 60（2）： 91?110.

[4] WRIGHT J， ALLEN Y， GANESH A. Robust face recognition via sparse representation [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2009， 31（2）： 210?227.

[5] HAN Zhen?jun， JIAO Jian?bin， ZHANG Bao?chang. Visual object tracking via sample?based adaptive sparse representation [J]. Pattern Recognition， 2011， 44（9）： 2170?2183.

[6] MEI X， LING H. Robust visual tracking using l1 minimization [C]// International Conference on Computer Vision. Kyoto： [s.n.]， 2009： 1436?1443.

[7] KE Y， SUKTHANKAR R. PCA?SIFT： A more distinctive representation for local image descriptors [C]// IEEE Conference on Computer Vision and Pattern Recognition. Washington D C， USA： IEEE， 2004： 506?513.

[8] ACHLIOPTAS D. Database?friendly random projections： Johnson?Lindenstrauss with binary coins [J]. Journal of Computer and System Sciences， 2003， 66（4）： 671?687.

[9] ZHANG K， SONG H. Real?time visual tracking via online weighted multiple instance learning [J]. Pattern Recognition， 2013， 46（1）： 397?411.

[10] ROSS D， LIM J， LIN R， et al. Incremental learning for robust visual tracking [J]. International Journal of Computer Vision， 2008， 77（1/3）： 125?141.