基于SIFT的壓縮跟蹤算法

王權(quán)+劉侍剛+彭亞麗+裘國(guó)永

摘 要： 為了克服基于灰度特征信息的跟蹤算法在復(fù)雜的環(huán)境下無(wú)法區(qū)分目標(biāo)和背景的缺陷，提出基于SIFT的壓縮跟蹤算法。該算法采用改進(jìn)的SIFT特征提取方式，結(jié)合壓縮感知理論對(duì)特征進(jìn)行有效的降維，以在線多實(shí)例學(xué)習(xí)算法訓(xùn)練分類器，實(shí)現(xiàn)在出現(xiàn)目標(biāo)偏移、姿態(tài)變化和光暗變化等情況下對(duì)目標(biāo)實(shí)時(shí)準(zhǔn)確的跟蹤。實(shí)驗(yàn)結(jié)果表明，該算法能夠在復(fù)雜環(huán)境下實(shí)現(xiàn)目標(biāo)的準(zhǔn)確實(shí)時(shí)跟蹤。

關(guān)鍵詞： SIFT； 壓縮感知； 目標(biāo)跟蹤； 降維

中圖分類號(hào)： TN911.7?34； TP311.1 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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 引 言

基于檢測(cè)的分類模型在跟蹤領(lǐng)域越來(lái)越受到重視。分類模型先檢測(cè)再跟蹤，充分利用了背景信息，在應(yīng)對(duì)部分遮擋和背景與目標(biāo)相似的情況有良好的跟蹤效果。為了解決目標(biāo)在跟蹤過(guò)程中可能存在的姿態(tài)變化問(wèn)題，Grabner引入了在線學(xué)習(xí)的方式[1]，但分類器學(xué)習(xí)時(shí)會(huì)出現(xiàn)正樣本的不確定性。Babenko采用多實(shí)例學(xué)習(xí)將多個(gè)實(shí)例組成的包作為訓(xùn)練數(shù)據(jù)[2]。實(shí)驗(yàn)證明MIL可有效解決偏移問(wèn)題，但易受新更新目標(biāo)模板和噪聲影響，其選取的灰度信息無(wú)法很好地區(qū)別目標(biāo)和背景。Lowe提出了SIFT圖像特征[3]，其具有尺度不變性，并且在應(yīng)對(duì)旋轉(zhuǎn)、光暗、視角和尺度變化的情況時(shí)有很好的魯棒性。但SIFT特征維數(shù)高，不適合實(shí)時(shí)跟蹤算法。所以如何大量減少特征維數(shù)具有現(xiàn)實(shí)意義。而近些年Wright 提出的基于壓縮感知理論的稀疏表示算法[4]在這方面取得很好的效果，壓縮后的低維空間仍然能很好地保留高維空間的數(shù)據(jù)結(jié)構(gòu)。同時(shí)使用模板子空間重構(gòu)稀疏性實(shí)現(xiàn)對(duì)目標(biāo)的逼近的目標(biāo)跟蹤算法[5]也證明了在應(yīng)對(duì)部分遮擋時(shí)的有效性。

本文提出了一種基于SIFT特征和壓縮感知的目標(biāo)跟蹤算法。標(biāo)記視頻序列首幀圖像，在多實(shí)例模型正集合包內(nèi)提取改進(jìn)SIFT特征，使用滿足RIP條件的隨即高斯矩陣完成SIFT特征構(gòu)成的原圖像特征空間的投影，在得到的低維壓縮空間內(nèi)，將正樣本和負(fù)樣本通過(guò)計(jì)算各自的稀疏編碼作為更新分類器的權(quán)重，使用樸素貝葉斯分類器在線學(xué)習(xí)更新分類器，認(rèn)定得分最高的分類器所得到位置為下一幀目標(biāo)出現(xiàn)的位置，完成對(duì)目標(biāo)的實(shí)時(shí)跟蹤。

1 視頻圖像特征

基于灰度信息的Haar?like特征只能描述圖像特定方向的結(jié)構(gòu)，不能很好地描述目標(biāo)。SIFT特征在圖像局部提取，其對(duì)旋轉(zhuǎn)、尺度、和光照變化保持魯棒性。但SIFT算法產(chǎn)生高維特征會(huì)影響實(shí)時(shí)跟蹤效果，本文分別通過(guò)減少高斯金字塔層數(shù)、選定8方向直方圖和使用稀疏矩陣實(shí)現(xiàn)特征降維。

將樣本[x]生成的SIFT特征記為向量[Djx=dixi=1：n，j=1：m]，[n]為每個(gè)樣本產(chǎn)生SIFT特征個(gè)數(shù)，[m]為每次采集的候選樣本個(gè)數(shù)。[ltx0]表示初始[t]時(shí)刻標(biāo)記的目標(biāo)區(qū)域，在距離目標(biāo)較近的區(qū)域隨機(jī)提取正樣本[Xα=xltx-ltx0<α]，在距離目標(biāo)較遠(yuǎn)的地方隨機(jī)選取負(fù)樣本[X?，β=x?

2 基于壓縮感知的目標(biāo)表示與降維

2.1 稀疏表示與稀疏編碼

壓縮感知主要通過(guò)稀疏表示實(shí)現(xiàn)信號(hào)重構(gòu)。由于原問(wèn)題是NP難問(wèn)題，所以轉(zhuǎn)化為以下問(wèn)題求解：

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

本文通過(guò)使用在目標(biāo)區(qū)域內(nèi)提取的降維特征近似的構(gòu)造過(guò)完備基，其中經(jīng)過(guò)稀疏矩陣降維的代表性特征集合為[D=di|i=1：p]。其中：[di∈Rn]表示第[i]個(gè)向量化的特征；[n]表示目標(biāo)區(qū)域提取原始特征的維數(shù)；[p]表示目標(biāo)區(qū)域降維后的特征維數(shù)。

根據(jù)Mei提出的對(duì)噪聲魯棒的瑣碎模板算法[6]定義過(guò)完備字典如下：

[?=D，E] （2）

式中[E=I，-I∈Rn×2n]表示處理噪聲點(diǎn)的小模板，[I∈Rn×n]表示單位矩陣。

根據(jù)式（1）計(jì)算每一個(gè)特征向量的稀疏編碼，得到樣本的稀疏系數(shù)矩陣[L=l1，l2，…，lp]作為計(jì)算分類器權(quán)重的訓(xùn)練數(shù)據(jù)。

2.2 特征降維

Ke采用主成分分析算法PCA替換SIFT中的直方圖計(jì)算描述子將維數(shù)降低[7]，但因?yàn)橥队熬仃噷?dǎo)致其具有不完全的仿射不變性。相比較PCA，近年來(lái)利用基于壓縮感知理論的稀疏表示算法[4]，利用符合壓縮感知RIP條件的隨即感知矩陣對(duì)多尺度圖像進(jìn)行降維。根據(jù)Johnson?Lindenstrauss推論[8]，WMIL算法[9]中，選取的投影矩陣滿足要求，本文選定同樣矩陣完成降維工作，其中[s]取值為3：

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

樣本區(qū)域所提取的特征向量經(jīng)過(guò)降維可表示為：

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

式中：[rcv]為[c×v]維的稀疏矩陣。通過(guò)稀疏矩陣（3）的投影，樣本特征維數(shù)下降明顯。

3 多實(shí)例在線學(xué)習(xí)算法

本文采取級(jí)聯(lián)方式將弱分類器結(jié)合生成強(qiáng)分類器。其中分類器使用樸素貝葉斯分類器，每個(gè)樣本[x][（n]維向量），它的低維表示是[v（p]維向量，[p?n）。]假定[v]中的各元素是獨(dú)立分布的。其建立分類器如下所示：

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

其中4個(gè)參數(shù)[μ1i，σ1i，μ0i，σ0i]通過(guò)[pvi|y=1～][Nμ1i，σ1i]和[pvi|y=0～Nμ0i，σ0i]描述，其中[σ1]和[μ1]可通過(guò)最大似然估計(jì)求得，參數(shù)更新為：

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

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

式中：[λ]為學(xué)習(xí)因子，[λ>0。]

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

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

假定存在[R]個(gè)正樣本[x1，j，j=0，…，R-1]和[T]個(gè)負(fù)樣本[x0，j，j=R，…，R+T-1]，標(biāo)記的首幀樣本位置記為[x10，]那么正樣本和負(fù)樣本被分到[X+，X-]內(nèi)，則正包的概率為：

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

式中[wj0]是衡量樣本[x1j]和[x10]距離的權(quán)重函數(shù)：

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

其中[lx1j]和[lx10]即為由樣本生成稀疏編碼計(jì)算的樣本距離[L=l1，l2，…，lp。]

4 測(cè)試結(jié)果與分析

本文算法對(duì)視頻序列Tiger進(jìn)行試驗(yàn)，視頻中出現(xiàn)部分遮擋、視角與姿態(tài)變化、光暗變化和目標(biāo)相似與背景的問(wèn)題。為了更好地驗(yàn)證本算法的有效性，本文算法與最近提出的目標(biāo)跟蹤算法（增量學(xué)習(xí)跟蹤算法IVT[10]、多實(shí)例學(xué)習(xí)跟蹤算法MIL[2]和權(quán)重多實(shí)例學(xué)習(xí)跟蹤算法WMIL[9]進(jìn)行比較。在Windows 7下，用Matlab 2010實(shí)現(xiàn)整個(gè)算法，在Core i5 2.5 GHz處理器上的平均速度為3 f/s。跟蹤前人工標(biāo)記首幀目標(biāo)所在位置選定出現(xiàn)光暗變化、部分遮擋和目標(biāo)與背景相似的Tiger視頻序列。4種算法實(shí)驗(yàn)結(jié)果如圖1所示。圖1中3行分別選自圖像的202幀、278幀和350幀。

由圖1可知IVT和MIL出現(xiàn)不同程度的偏移現(xiàn)象。對(duì)比WMIL和本文算法，202幀時(shí)出現(xiàn)明顯的光暗變化和姿態(tài)變化，本文算法更能穩(wěn)定地跟蹤。從350幀可看出在出現(xiàn)目標(biāo)被嚴(yán)重遮擋問(wèn)題時(shí)，本文算法更能很好地區(qū)別背景和目標(biāo)。因此，本文算法在穩(wěn)定性和準(zhǔn)確性方面優(yōu)于其他3類算法。

使用跟蹤目標(biāo)中心和真實(shí)中心的歐式距離作為評(píng)判標(biāo)準(zhǔn)，距離數(shù)值大表明偏移目標(biāo)遠(yuǎn)，每隔5幀圖像選取圖像，計(jì)算其數(shù)值與其他4種算法進(jìn)行比較，中心位置誤差如表1所示。

表1 各視頻中心位置誤差

[視頻＼&IVT＼&MIL＼&WMIL＼&本文＼&tiger＼&14.639＼&34.771＼&10.843＼&9.034＼&]

由表1可以看出本文中心誤差比較穩(wěn)定，優(yōu)于其他算法。從定量關(guān)系上說(shuō)明本文算法在應(yīng)對(duì)復(fù)雜環(huán)境時(shí)能更優(yōu)地跟蹤到目標(biāo)。

5 結(jié) 語(yǔ)

本文提出了一種基于SIFT特征的壓縮跟蹤算法。將SIFT特征所具有對(duì)尺度、光照和姿態(tài)變化不敏感的特性融入多實(shí)例在線學(xué)習(xí)算法中，并結(jié)合壓縮感知有效地對(duì)大數(shù)據(jù)量的特征值進(jìn)行降維以及實(shí)現(xiàn)目標(biāo)的稀疏表示，使其不僅獲得更好的跟蹤效果并實(shí)現(xiàn)了實(shí)時(shí)的目標(biāo)跟蹤。實(shí)驗(yàn)結(jié)果證明算法能夠?qū)崿F(xiàn)在尺度伸縮、形變和光暗變化情況下對(duì)目標(biāo)實(shí)施準(zhǔn)確的跟蹤。本文算法的跟蹤精度和穩(wěn)定程度都高于基于灰度信息特征的跟蹤算法。

參考文獻(xiàn)

[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.

參考文獻(xiàn)

[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.

參考文獻(xiàn)

[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.