基于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.