基于目標特征提取的改進型壓縮跟蹤算法

莊哲民， 龔家銘， 謝光成， 袁 野

(汕頭大學 電子工程系， 廣東 汕頭 515063)

基于目標特征提取的改進型壓縮跟蹤算法

莊哲民， 龔家銘， 謝光成， 袁 野

(汕頭大學 電子工程系， 廣東 汕頭 515063)

本文在傳統(tǒng)的尺度不變特征子(Scale Invariant Feature Transform， SIFT)算法的基礎上， 提出了一種新的基于改進的SIFT 壓縮感知跟蹤算法. 該方法一方面通過改進壓縮跟蹤算法中分類器的更新策略來提高算法的實時性； 另一方面， 通過改進SIFT向量鄰域的選取方法來實現(xiàn)降低向量維度， 從而減少計算復雜度. 仿真實驗表明， 該方法不僅可以提高跟蹤目標的實時性， 而且能夠在發(fā)生目標尺度變化、 遮擋、 漂移的情況下對運動目標進行準確跟蹤.

運動目標跟蹤； 特征提取； SIFT； 壓縮感知

0 引 言

在視頻圖像處理技術(shù)日益成熟以及相關(guān)應用領域日益廣泛的背景下， 視頻跟蹤技術(shù)已成為當前研究與關(guān)注的熱點[1]. 由于視頻內(nèi)容的復雜性、 多變性以及場景的變化， 實時跟蹤某個運動的對象具有一定的難度， 特別是當對象發(fā)生形變以及對象被嚴重遮擋時， 實時跟蹤將變得更為困難. 目前常用的視頻跟蹤方法主要有均值偏移算法[2]、 卡爾曼濾波、 粒子濾波、 基于模板匹配[3]以及尺度不變性特征子(Scale Invariant Feature Transform， SIFT)算法[4]等.

SIFT作為圖像的一個局部特征算子， 最早是David Lowe在1999年提出的. 由于SIFT算法具備對圖像變換較強的適應能力， 在圖像匹配以及重建中都有著很好的應用， 但因為SIFT算法的復雜性， 導致匹配過程中花費的時間較長. 因此， 本文提出了SIFT的改進算法， 其核心一方面是在進行特征提取過程中改進SIFT的處理鄰域， 精簡生成的SIFT算子的維度， 從而減輕計算的復雜度； 另一方面將壓縮感知技術(shù)[5]用于視頻數(shù)據(jù)的壓縮， 并改進壓縮感知中分類器學習因子的更新策略， 從而提高了整個算法的實時性.

仿真實驗結(jié)果表明， 在處理運動目標發(fā)生尺度變化、 旋轉(zhuǎn)、 遮擋等的情況下， 基于目標特征提取的改進型壓縮跟蹤算法能夠準確并且高效率地追蹤運動目標， 而且能夠自適應應對光照改變引起的問題.

1 基于壓縮感知的SIFT視頻跟蹤算法

1.1 改進的SIFT視頻跟蹤算法

標準SIFT算法利用目標的尺度不變性的特征， 整合相應的特征點來鎖定目標并加以跟蹤. 針對SIFT算子維度過高的缺點， 本文提出從特征算子的生成鄰域入手， 對SIFT算子進行改進. 為了保證生成的描述算子具有旋轉(zhuǎn)不變性， 該鄰域是以SIFT特征點為圓心， 以8個像素單位為半徑繪制的圓形鄰域D. 我們將整個圓形領域劃分為4個部分， 半徑為2個像素單位的內(nèi)圓D1以及環(huán)寬為2個像素單位的3個圓環(huán)D2，D3，D4， 圓形鄰域D的數(shù)學表達如式(1)所示

D=(D1,D2,D3,D4).

(1)

改進后的SIFT圓形鄰域D如圖 1(a) 所示.

圖 1 改進型SIFT特征算子的生成Fig.1 Generation of improved SIFT descriptor

圖1(a)表示的是一個16×16像素單位的局部圓形鄰域圖， 其中不同的區(qū)域代表不同的子區(qū)域Di(其中i=1， 2， 3， 4)， 圖中每一個小方格代表一個像素.

傳統(tǒng)SIFT算子首先記錄0°， 45°， 90°， 135°， 180°， 225°， 270°， 315°這8個方向的子向量， 通過整合2×2的像素子單元生成一個8維向量， 最后生成一個高達128維的向量. 而在本文中， 指定圓形鄰域D對應4個部分， 其中每個部分Di分別由10個子向量構(gòu)成， 這些子向量的方向分別是 0°， 36°， 72°， 108°， 144°， 180°， 216°， 252°， 288°， 324°. 因此， 圓形鄰域任意一部分Di的構(gòu)成可由式(2)表示

式中： 向量組(di1，di2,...,di10)是由改進后SIFT鄰域所生成的10個子向量構(gòu)成， 由于整個圓形鄰域D生成的SIFT算子向量維度僅為40維， 大大地降低了計算復雜度.

我們以整個圓形鄰域中的D1部分作為示例， 在圖1(b)中的向量d11～d110就是構(gòu)成向量D1的10個子向量， 顯然向量D1的維度為10維， 而D2，D3，D43個向量的生成步驟與D1一致， 改進后的SIFT算子通過將圓形鄰域的4個部分整合在一起后， 最終算子的維度為40維.

之所以選定圓形鄰域， 是由于其對旋轉(zhuǎn)不敏感， 從而減少一些特殊狀況對跟蹤結(jié)果的影響. 為了能夠進一步處理復雜場景中目標發(fā)生較大尺度的旋轉(zhuǎn)的問題， 則需要在鄰域的每個部分Di中尋找幅值最大的那個子向量dij(i=1， 2， 3， 4；j=1， 2， ...， 10)， 并將dij以及之后的所有子向量同時進行相應的左移. 假設在D1找到其中最大的子向量， 假設該子向量就是d11, 那么D1則不需要進行左移， 因為該向量集的第一個子向量即為本向量集中幅值最大的一個. 否則就需要把幅值最大的這個子向量以及其后的所有向量提前， 相應地， 在該幅值最大的子向量之前的所有子向量右移到后部分. 也就是說假設D1中最大的子向量是d14, 那么前面3個向量則右移到最后， 其他子向量全部一致性地左移. 最后結(jié)果如式(3)所示

D=(di4,di5,…,di9,di10,di1,di2,di3)i∈[1,4].

(3)

在傳統(tǒng)SIFT算法中， 只將特征點(極值點)梯度的相角作為旋轉(zhuǎn)角度， 而不是把鄰域內(nèi)其他點的相角作為旋轉(zhuǎn)角度， 故在本文中， 只將子向量集中第一個子向量作為左移的參考來處理發(fā)生旋轉(zhuǎn)的狀況.

實際的跟蹤過程中很容易發(fā)生光照的驟變或者漸變， 為了減輕相應的影響， 故在生成完整的特征算子之前對其進行歸一化處理

(4)

在處理非線性光照的情況時， 根據(jù)實驗經(jīng)驗設置臨界值為0.2， 當向量中某子向量的幅值超過了臨界值， 則重置為0.2， 相應地再重新進行歸一化處理使得每個子向量符合要求.

可見對SIFT算子的生成鄰域進行改進后， 優(yōu)化后的SIFT算子不僅能夠保留傳統(tǒng)算子的優(yōu)秀性能， 而且大大降低了算子的維度， 從而降低了算法的計算復雜度， 為了進一步提高整個算法的實時性， 將引入壓縮感知理論， 將視頻目標跟蹤結(jié)果進行優(yōu)化.

1.2 基于特征提取的壓縮跟蹤算法的實現(xiàn)

壓縮感知理論在視頻跟蹤的應用當中最大的優(yōu)點即為減少計算復雜度， 本文將壓縮感知理論與特征提取算法相結(jié)合， 一方面利用壓縮感知使算法降低計算量， 另一方面利用特征提取來優(yōu)化跟蹤效果. 同時針對傳統(tǒng)的壓縮跟蹤算法和特征提取算子存在的缺點， 分別對SIFT算子以及壓縮跟蹤算法中分類器的更新參數(shù)進行優(yōu)化， 提高跟蹤算法的實時性以獲取更好的跟蹤結(jié)果.

基于壓縮感知理論， 可以利用滿足RIP條件的測量矩陣R=Rn×m， 將數(shù)據(jù)從較高維度的信號x∈Rm投影到較低維度的信號v∈Rn， 如式(5)所示

式中：n?m， 在理想情況下， 稀疏矩陣R能夠保留下每個點對的初始距離， 并且滿足Johnson-Lindenstrauss定律， 測量矩陣由式(6)的規(guī)則生成

在此設置s=m/4， 通常情況下s=2或3， 可以獲取一個非常稀疏的隨機矩陣. 之后利用測量矩陣就可獲取一個低維的特征集v(v1,v2,v3,…,vn)，n?m, 同時為了能夠更高效地進行建模， 采用貝葉斯分類器對候選者進行分類跟蹤， 分類器生成方式如下[6-8]

式中：p(·)表征的是測量值y=1或者y=0時的概率值或是基于不同的y的測量值時的條件概率.

當運動目標發(fā)生漂移時， 由于壓縮跟蹤算法無法控制不斷累計的誤差， 最終很容易導致失敗， 為了能夠滿足實時性要求， 并且控制在跟蹤過程中累加的誤差， 我們引入學習率來權(quán)衡分類器中高斯參數(shù)的比重[9]

式中：d和b分別表示采樣特征集的前一幀與新的采樣值的參數(shù)(均值μ以及協(xié)方差σ)的差值， 學習率λ就是影響分類器函數(shù)內(nèi)高斯參數(shù)權(quán)重的因子[10,11]. 由于分類器的參數(shù)分為兩個部分， 一部分是前一幀中目標特征的模版參數(shù)， 另一部分是當前幀中搜尋位置處新的模版參數(shù). 當相鄰兩幀中運動物體運動量較小時， 那么由于新的模版參數(shù)改變量很少， 則將學習率設置得大一點， 使得分類器參數(shù)基本維持上一幀時的狀態(tài)； 如果相鄰兩幀中的運動目標發(fā)生了劇烈運動， 則需要將λ設置得小一點， 畢竟最新的跟蹤結(jié)果更加依賴于新的一幀中的信息. 綜合來說， 學習率λ間接反應了運動目標的實時狀況.

為了使學習率λ反映運動目標的實時狀況， 需要一個能夠自適應調(diào)整的學習率來權(quán)衡相鄰幀的變動情況， 從而控制分類器的效果. 為了更好地表征相鄰幀圖片的“距離”， 首先計算出每幅圖片中我們感興趣的追蹤區(qū)域的歸一化直方圖， 并利用巴氏系數(shù)來度量兩幀圖片的“距離”， 如式(10)所示

式中：pi為前一幀圖像追蹤區(qū)域直方圖的離散分布概率， 而qi表征當前幀所追蹤區(qū)域最可能的預測目標區(qū)域直方圖的離散分布概率. 距離ρ就是前后兩幀圖像之間差異的度量， 根據(jù)設定好的閾值來確定是否對分類器相應參數(shù)進行更新， 判定規(guī)則如式(11)所示

新的學習率可定義為

學習率λ′的取值范圍是(0， 1)， 它與兩幀距離ρ成反比， 在實際的跟蹤過程中， 首幀與末幀圖像變化不大時， 學習率λ′的取值會較??； 相應的， 若是首幀與末幀中運動目標的位置情況相差甚大， 則λ′會被調(diào)整變大. 因此， 自適應的學習率能夠有效地控制誤差的累積， 當發(fā)生漂移和旋轉(zhuǎn)的情況時， 能較好地避免跟蹤失敗， 采用自適應的學習率不僅沒有給整個解決方案增加很多的計算量， 且能改善復雜場景下的運動目標跟蹤效率.

改進的SIFT特征集是從前一幀的目標區(qū)域采樣獲得， 然后從初始特征點里面隨機選擇固定數(shù)量的特征點作為初始特征點庫， 其中隨機選取的特征點數(shù)量f事先會設置好. 本文的式(13)～式(15)為各個特征庫內(nèi)是互不影響的特征點， 分別以u,v,w進行表示， 其中第一級特征點庫Sf表示為

Sf=(u1,u2,u3,…,uf).

(13)

提取當前幀的特征點集， 與前一幀所提取獲得特征點庫Sf進行匹配， 匹配之后的特征點集則可表示為

Sm=(v1,v2,v3,…,vm).

(14)

顯而易見， 匹配的數(shù)量m一定不會超過f.

RANSC(Random Sample Concensus) 優(yōu)化算法則用來將現(xiàn)有匹配之后的特征點進行優(yōu)化， 除去錯誤匹配的特征點， 然后獲得更準確的特征點集Sp， 如式(15)所示

Sp=(w1,w2,w3,…,wp).

(15)

此外， 還可以利用已經(jīng)獲取的特征點集求取變換矩陣中的未知數(shù)， 然后用來求解前一幀與當前幀目標尺寸的縮放比例和角度. 選取已經(jīng)凈化獲得的特征點集， 并在當前幀中隨機選擇若干數(shù)量的特征點， 最終構(gòu)成固定數(shù)量f的新的特征點庫. 將上述步驟從初始幀到最后一幀， 往復地在相鄰兩幀中施行， 就可以求得目標尺寸的縮放比例， 算法就可以自適應地調(diào)整追蹤窗口的大小， 減小跟蹤誤差.

2 算法仿真實現(xiàn)與分析

針對發(fā)生遮擋、 光照以及旋轉(zhuǎn)的場景中的目標跟蹤， 我們分別從公共目標跟蹤視頻庫中選取face片段與coke片段， 并在i7-4710MQ， 8G主機上進行調(diào)試， 獲取如圖 2 的跟蹤結(jié)果， 其中a矩形框為原始壓縮跟蹤算法的跟蹤結(jié)果， b矩形框則是基于特征提取改進型壓縮感知跟蹤算法的追蹤結(jié)果. 從整個跟蹤過程當中隨機抽取6幀出來進行對比， 可見人臉在從未遮擋到遮住部分再到完整再現(xiàn)整個過程中兩種方法的跟蹤結(jié)果.

圖 2 face人臉跟蹤效果對比Fig.2 Face contrast experiment

如圖 2 所示， 第1幀為初始化跟蹤目標， 在發(fā)生遮擋以前， a框與b框的效果基本一致， 然后從第22幀開始有書籍分別從各種角度遮擋住人臉， 在第27幀、 第92幀、 第157幀時a框都不能像b那樣穩(wěn)定地追蹤運動目標， 而且在最后目標重新暴露在視頻中的時候， a框也無法恢復跟蹤. 我們可以看出b框不論在哪種遮擋的情況下都能穩(wěn)定地追蹤到目標， 而采用原始壓縮跟蹤算法的a框跟蹤效果并不理想. 其原因一是在改進型的壓縮跟蹤算法的分類器參數(shù)λ是實時更新的， 而在傳統(tǒng)算法中該學習率的值是設置為固定的0.85； 二是改進型的算法融合了優(yōu)化的特征提取算法SIFT來強化跟蹤效果， 能在復雜的場景下跟蹤目標.

圖 3 coke可樂罐跟蹤效果對比Fig.3 Coke cans contrast experiment

在第二個場景中， 視頻流中會出現(xiàn)光照、 遮擋和旋轉(zhuǎn)這幾種常見的問題， 同樣采用傳統(tǒng)的壓縮跟蹤算法與改進型壓縮跟蹤算法分別進行實驗， 隨機選取其中的6幀進行對比， 其中b框代表的是采用基于特征提取的改進型壓縮跟蹤算法的實驗結(jié)果， a框代表的是傳統(tǒng)壓縮跟蹤算法的跟蹤結(jié)果， 具體見圖 3.

如圖 3 所示， 同樣第一幀為初始化選定跟蹤目標， 當人拿著罐頭在燈泡以及植被附近運動且罐頭僅僅自身旋轉(zhuǎn)時， 我們可以看到在第16幀附近時兩種算法的跟蹤效果基本一致； 但在第34幀時， 當罐頭在移至離燈泡較遠處并被植被的葉子所遮擋的時候， a框已經(jīng)部分脫離了要跟蹤的物體； 第102幀時罐頭自身發(fā)生旋轉(zhuǎn)， 此時的a框依然脫離了想要跟蹤的目標； 再到第274幀時， a框完全脫離目標， 無法再跟上運動目標的節(jié)奏， 然后b框卻從始至終穩(wěn)定地將目標跟蹤在框內(nèi).

可見由于物體的運動不可預測， 跟蹤過程中的分類器參數(shù)如果只單憑借經(jīng)驗設置固定值而不隨物體實際運動實時更新的話， 則跟蹤效果總是不能如意； 再則就是在復雜場景中， 對運動目標進行高效率的特征提取， 那樣才能保證在發(fā)生了光照變化、 遮擋、 目標旋轉(zhuǎn)等情況下仍然能穩(wěn)定追蹤到前景目標.

為了數(shù)值化測量本方法的計算復雜度， 顯示其優(yōu)越性， 故將改進型壓縮感知跟蹤算法與傳統(tǒng)壓縮跟蹤算法(CT)分別在同一PC機上重復進行調(diào)試運行20遍， 取各個過程的均值記錄如表 1 所示.

表 1 改進型壓縮跟蹤算法與傳統(tǒng)壓縮跟蹤算法的運行耗時對比

本文算法除了具有較高的實時性的優(yōu)點之外， 經(jīng)過改進后的SIFT算子與壓縮感知理論融合后的算法還能夠在跟蹤的準確度上有較高的優(yōu)越性. 中心位置錯誤率是用來定量評估追蹤矩形的中心和實際目標中心的歐幾里德距離. 為了提高該數(shù)據(jù)的準確性， 在軟-硬件平臺分別進行仿真本文的算法、 傳統(tǒng)的CT算法、 TLD算法以及OAB(Online AdaBoost)算法20遍， 分別取中心位置錯誤率的平均值進行對比.

表 2 中心位置錯誤率對比(以單個像素為單位)

通過觀察表 2 中的數(shù)據(jù)， 相比于其他算法， 本文算法在兩個視頻流中的跟蹤具有較強的魯棒性.

3 結(jié) 論

本文在傳統(tǒng)SIFT 算法的基礎上， 通過將改進的SIFT算法與壓縮感知理論進行融合， 獲得基于改進SIFT特征提取的壓縮跟蹤算法. 該算法一方面利用SIFT算子對目標進行實時檢測跟蹤的優(yōu)秀性能， 并且克服了原算子高維度的缺點； 另一方面將壓縮感知理論引入到視頻跟蹤算法中來， 進一步優(yōu)化跟蹤結(jié)果， 提高實時性能， 從而在復雜的環(huán)境下， 能夠魯棒地跟蹤運動目標.

[1] Kalal Z, Mikolajczyk K, Matas J. Tracking-learning-detection[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 34(7)： 1409-1422.

[2] David G. Lowe. Distinctive image features from scale-invariant keypoints[J]. International Journal of Computer Vision, 2004, 60(2)： 91-110.

[3] Grabner H, Leistner C, Bischof H. Semi-supervised on-line boosting for robust tracking[C]. European Conference on Computer Vision, Marseille, France, October 12-18, 2008： 234-247.

[4] 李新德， 劉苗苗， 徐葉帆. 一種基于2D和3D SIFT特征級融合的一般物體識別算法[J]. 電子學報， 2015， 43(11)： 2277-2283. Li Xinde, Liu Miaomiao, Xu Yefan. A recognition algorithm of generic objects based on feature-level fusion of 2D and 3D SIFT descriptors[J]. Acta Electronica Sinica, 2015, 43(11)： 2277-2283. (in Chinese)

[5] 石光明， 劉丹華， 高大化， 等. 壓縮感知理論及其研究進展[J]. 電子學報， 2009， 37(5)： 1070-1081. Shi Guangming, Liu Danhua, Gao Dahua, et al. Advances in theory and application of compressed sensing[J]. Acta Electronica Sinica, 2009, 37(5)： 1070-1081. (in Chinese)

[6] 謝昕， 徐殷， 熊煥東， 等. 基于壓縮感知的SIFT圖像匹配算法的研究[J]. 華東交通大學學報， 2015， 32(6)： 115-121. Xie Xin, Xu Yin, Xiong Huandong, et al. Research on SIFT image matching algorithm based on compressed sensing[J]. Journal of East China Jiaotong University, 2015， 32(6)： 115-121. (in Chinese)

[7] Babu R, Patrick P, fez, et al. Robust tracking with motion estimation and local Kernel-based color modeling[J]. Image Vision Computing, 2007, 25(8)： 1205-1216.

[8] Kim T K, Woodley T, Stenger B, et al. Online multiple classifier boosting for object tracking[C]. Computer Vision and Pattern Recognition Workshops (CVPRW), IEEE Xplore, 2010： 1-6.

[9] Matthews I, Ishikawa T, Baker S. The template update problem[J]. IEEE transactions on pattern analysis and machine intelligence, 2004, 26( 6)： 810-815.

[10] Javed O, Ali S, Shah M. Online detection and classification of moving objects using progressively improving detectors[C]. Computer Vision and Pattern Recognition, 2005. CVPR 2005. IEEE Computer Society Conference on, 2005： 696-701.

[11] Williams O, Blake A, Cipolla R. Sparse bayesian learning for efficient visual tracking[J]. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2005, 27( 8)： 1292-1304.

The Improved Compression Tracking Algorithm Based on Video Target Feature Extraction

ZHUANG Zhemin, GONG Jiaming, XIE Guangcheng, YUAN Ye

(Dept. of Electronic Engineering, Shantou University, Shantou 515063, China)

An improved SIFT target tracking algorithm based on compressed sensing is proposed in this paper. The real-time performanceis improved by improving updating strategy of the classifier in the compressive theory.On the other hand, The vector neighborhood of SIFT has been improved to decrease the vector dimension and the complexity of calculation. Simulations and experiments show that this method not only can improve the real-time performance of tracking target, but also can carry on the tracking of moving target accurately in the event of a target scale variation, occlusion shelter, drifting.

video target tracking; feature extraction; SIFT; compressive sensing

1671-7449(2017)02-0093-07

2016-12-20

國家自然科學基金資助項目(61471228)； 廣東省應用型科技研發(fā)專項項目(2015B020233018)

莊哲民(1965-)， 男， 教授， 博士， 主要從事圖像處理， 無線傳感網(wǎng)絡方面研究

TN911.73

A

10.3969/j.issn.1671-7449.2017.02.001