基于笛卡爾乘積字典的稀疏編碼跟蹤算法

黃宏圖畢篤彥 查宇飛 高 山 覃 兵

(空軍工程大學航空航天工程學院 西安 710038)

基于笛卡爾乘積字典的稀疏編碼跟蹤算法

黃宏圖*畢篤彥 查宇飛 高 山 覃 兵

(空軍工程大學航空航天工程學院 西安 710038)

為了提高基于稀疏編碼的視頻目標跟蹤算法的魯棒性，該文將原始稀疏編碼問題分解為兩個子稀疏編碼問題，在大大增加字典原子個數的同時，降低了稀疏性求解過程的計算量。并且為了減少1范數最小化的計算次數，利用基于嶺回歸的重構誤差先對候選目標進行粗估計，而后選取重構誤差較小的若干個粒子求解其在兩個子字典下的稀疏表示，最后將目標的高維稀疏表示代入事先訓練好的分類器，選取分類器響應最大的候選位置作為目標的跟蹤位置。實驗結果表明由于笛卡爾乘積字典的應用使得算法的魯棒性得到一定程度的提高。

計算機視覺；視頻跟蹤；笛卡爾乘積；稀疏編碼；支持向量回歸機；嶺回歸

1 引言

視頻目標跟蹤技術是計算機視覺領域的關鍵問題之一[1]，廣泛應用于視頻監控、機器人導航、人機交互和精確制導等領域。跟蹤面臨的挑戰從內外兩個方面來說包括目標內部變化和外界變化，其中目標內部變化包括目標姿態變化、形變和尺度變化等，外界變化包括噪聲、光照變化和遮擋等。為了處理上述變化，一個好的目標模型需要滿足以下兩個條件：對于目標自身變化的自適應性和對于外界變化的魯棒性[2]。

稀疏編碼廣泛應用于人臉識別、圖像超分辨率重建、圖像去噪和恢復、背景建模、圖像分類等計算機視覺領域[3]。得益于稀疏表示在人臉識別[4]領域的成功應用，很多學者將其應用到視頻目標跟蹤[5]，可以分為基于稀疏編碼重構誤差的生成式模型和基于稀疏編碼的判別式模型。無論是生成式模型還是判別式模型都需要首先求解目標在字典下的稀疏表示，其中稀疏性求解過程為1范數最小化問題，此類算法有同倫法、正交匹配追蹤法、梯度投影法、迭代收縮閾值法、基追蹤法和內點法等[6]。而這些算法的時間復雜度一般較高，尤其是當字典的維數較高時，嚴重制約了跟蹤算法的實時性。而理論研究和實驗結果表明字典中原子個數增加后目標能夠獲得更高維的稀疏表示，而在高維的稀疏表示下目標和背景更加線性可分[7]。這樣就形成了一組矛盾，為了獲得跟蹤的實時性需要降低字典的維數，而為了提高魯棒性又不得不提高字典的維數。

程的算法時間復雜度為O(Nm2n3/2)，其中N是候選目標個數，m為特征維數，n為字典中原子個數[5]。因此降低稀疏性求解過程的計算量可以分為以下兩種方法：(1)降低每次1范數最小化的計算量。(2)減少1范數最小化的次數。雖然上述方法一定程度上降低了稀疏性求解過程的計算量，但是實質并沒有增加字典中原子個數，因而在提高跟蹤的魯棒性方面效果有限。如何在計算量一定的前提下，增加字典中的原子個數來提高跟蹤算法的魯棒性是稀疏編碼跟蹤算法需要解決的關鍵問題。

本文提出了基于笛卡爾乘積字典[8]的稀疏編碼跟蹤算法，將原始字典分解為兩個子字典，而后按照同樣的方式分別求解目標在兩個子字典上的稀疏表示，以較低的計算代價獲得了目標高維的稀疏表示。為了進一步提高跟蹤算法的實時性，利用基于嶺回歸的重構誤差排除大量的無關粒子，而后求解重構誤差較小的若干個候選目標在兩個子字典上的稀疏表示，最后將目標的高維稀疏表示代入事先訓練好的支持向量回歸機，根據分類器響應確定目標的跟蹤位置，在此基礎上利用跟蹤結果和正負樣本對分類器進行在線更新。實驗結果表明由于乘積稀疏編碼的應用，算法的魯棒性得到了一定程度的提高。

2 過完備字典構建

如圖1所示，首先通過仿射變換將目標轉換至32×32大小區域，對于每個候選目標iY這里使用固定大小(16×16)的滑動窗，利用尺度不變特征變換(Scale-Invariant Feature Transform, SIFT)提取交疊的k個圖像塊的[9]特征{y1,y2,…,yk}，其中k=9。與原始SIFT特征不同，本文指定圖像塊的中心為關鍵點，而后對關鍵點周圍的區域提取梯度幅值直方圖，并且為了降低特征提取過程的計算量，僅提取一個尺度下的SIFT特征，目標的尺度變化可以通過仿射變換中的尺度參數對其進行描述。

圖1 圖像塊的SIFT特征提取

3 笛卡爾乘積稀疏編碼

對于兩個子字典的笛卡爾乘積稀疏編碼[8]問題，可以將圖像塊的SIFT特征表示為x=[,]T，x1∈和x2∈分別是x的兩個子向量。按照同樣的方式字典D∈?m×n中的原子可以表示為[,]T，其中d1p是D1∈中的第p個原子，d2q是D2∈中的第q個原子，p,q=1,2,…,n。選取目標和其中心8鄰域目標的SIFT特征構建字典D，即m=128, n=81。x在該字典下的笛卡爾乘積稀疏表示βpq可以通過下面的目標函數獲得。

式(1)的稀疏編碼問題的等價形式為

其中De為字典D1和D2的笛卡爾乘積。

式(2)的稀疏編碼問題可以分解為下面兩個子稀疏編碼問題[8]：

其中λ1=λ2=λ/2=0.15。

則有x在D1和D2的笛卡爾乘積字典下的稀疏表示為

其中vec(·)表示將矩陣按列轉換成列向量，?β為式(2)的近似解。

原始稀疏編碼問題為

基于式(2)和式(3)～式(5)的稀疏性求解過程的算法時間復雜度比較如表1所示。從表1中可以看出當m=128, n =81時，基于笛卡爾乘積字典的稀疏表示的計算量遠遠小于直接在等效字典上求解稀疏表示的計算量。因此基于笛卡爾乘積的稀疏表示在增加原子個數的同時，降低了求解的計算量。

表1 算法時間復雜度比較

則有候選目標iY的所有k個圖像塊的SIFT特征在笛卡爾乘積字典下的稀疏表示為

4 支持向量回歸機

在當前幀跟蹤位置基礎上，在目標周圍按照高斯分布提取一定數量的正負樣本，其中正樣本中心坐標lpos滿足負樣本中心坐標lneg滿足, l為當前幀的跟蹤位置，σt1和σ2為樣本中心與目標中心之間的歐式距離(像素)。分別計算正負樣本在當前笛卡爾乘積字典下的稀疏表示ρj。將代入線性分類器進行訓練，其中lj=±1表示樣本標簽，c=100，即50個正樣本和50個負樣本。線性分類器的目標函數[10,11]為

其中ω是分類器參數，γ=0.01為正則化參數。損失函數l(lj,ω,ρj)為

5 基于嶺回歸的粗估計

對于N個候選目標選擇重構誤差較小的0N個粒子，因此大大減少了1范數最小化的次數。

6 跟蹤算法

算法是在粒子濾波框架[13]下完成。粒子濾波通過觀測數據I1:t來遞推計算狀態St取不同值時的置信度p(St|I1:t)，由此獲得狀態的最優估計。給定目標的觀察變量集合I1:t={I1,I2,…,It}，目標的狀態變量St可以通過最大后驗估計得到

其中p(St|St-1)表示動態模型，p(It|St)表示觀察模型。動態模型描述相鄰兩幀之間目標狀態的時間相關性，這里使用6參數的仿射變換[14]來模擬相鄰兩幀之間目標的運動，St=(xt,yt,θt,st,αt,φt)分別表示t時刻目標x方向和y方向位移，旋轉角度，尺度，寬高比，傾斜角度。狀態轉換公式為p(St|St-1)= N(St;St-1,Σ), Σ是仿射變換參數的標準差組成的協方差矩陣，這里假定仿射變換參數相互獨立且不隨時間變化[14]。

觀察模型p(It|St)表示觀察變量It位于狀態St的可能性，算法構建的觀察模型為

其中h(ρi)表示候選目標的分類器響應。

因此，本文跟蹤算法框架如圖2所示。

7 實驗結果及分析

7.1 跟蹤結果及分析

測試視頻來自文獻[1]，視頻數據及目標特征描述如表2所示，實驗在Dual-Core 3.20 GHz，內存3 GB的臺式計算機上通過Matlab(R2013a)軟件實現。其中粒子個數=600N，經過粗估計后剩余粒子個數為N0=200。FaceOcc2仿射變換參數的標準差為[4,4,0.02,0.03,0.001,0], Cliffbar仿射變換參數的標準差為[5,5,0.05,0.20,0.005,0.001], Jumping仿射變換參數的標準差為[8,18,0,0,0,0], Trellis仿射變換參數的標準差為[4,4,0.01,0.01,0.002,0.001]。

圖2 算法跟蹤過程

表2 視頻數據及目標特征描述

實驗的部分跟蹤結果如圖3所示，其中白色實線為本文算法跟蹤結果，其它算法跟蹤結果如圖例所示。比較算法分別為：增量子空間學習算法(Incremental Visual Tracking, IVT)[14]，多事例學習算法(Multiple Instance Learning, MIL)[15]，基于加速最近梯度的快速1跟蹤算法(L1 Tracker Using Accelerated Proximal Gradient Approach, L1APG)[16]，快速壓縮感知跟蹤算法(Fast Compressive Tracking, FCT)[17]。稀疏編碼跟蹤算法(Sparse Coding Tracking, SCT)為基于字典D的跟蹤算法，基于笛卡爾乘積的稀疏編碼跟蹤算法(Product Sparse Coding Tracking, PSCT)為本文提出算法，其中SCT算法和PSCT算法除字典不同外其它參數均相同。

遮擋：由于算法提取的是局部圖像塊的SIFT特征，并且稀疏性求解過程即是對圖像塊SIFT特征的選擇過程，能夠抓住目標中較為穩定的圖像塊的SIFT特征，因而能夠較好地處理跟蹤中的遮擋問題。

共面旋轉和尺度變化：算法每次生成不同尺度和旋轉角度的候選框，并且SIFT特征本身對于共面旋轉具有不變性，因此能夠解決跟蹤中的共面旋轉和尺度變化問題。

運動模糊和快速運動：由于算法字典中原子個數大大增加，使得目標能夠獲得高維的稀疏表示，同時支持向量回歸機具有較好的推廣能力，使得在稀疏的高維特征下目標和背景更加線性可分。

非均勻光照變化：SIFT特征由于對梯度幅值直方圖進行了歸一化因而能夠對于光照變化具有一定的魯棒性，同時PSCT算法字典中原子的個數遠大于SCT算法字典中原子的個數，使得高維稀疏表示下分類器區分目標和背景的能力更強。

7.2 跟蹤精度

7.2.1 重疊率 RT是算法標定的跟蹤區域，RG是人工標定的真實目標區域，area(RT∩RG)是二者重疊面積，area(RT∪RG)是二者面積之和。定義重疊率[18]為

不同算法下4個視頻重疊率隨幀數變化曲線如圖4所示。

7.2.2 中心誤差 中心誤差定義為算法跟蹤框的中心位置與人工標定的真實的中心位置之間的歐氏距離(像素)[18]，中心誤差的統計特征如表3所示，其中每個視頻對應的第1行為中心誤差的均值，第2行為中心誤差的標準差。從表3中可以看出本文提出的算法整體上優于其它4種算法，并且PSCT算法優于SCT算法。

表3 不同算法下各視頻中心誤差的均值和標準差(像素)

圖3 部分實驗跟蹤結果

圖4 各視頻重疊率隨幀數的變化曲線

7.3 跟蹤魯棒性

如果在一幀中重疊率0.5o≥，則認為跟蹤成功，反之則認為跟蹤失敗[18]。不同算法下視頻的跟蹤成功率如表4所示，其中最后一行為算法在4個視頻上的跟蹤成功率的平均值。從表4中可以看出本文提出算法的跟蹤成功率整體上高于其它5種算法。

表4 不同算法下各視頻跟蹤成功率(%)

8 結束語

利用笛卡爾乘積將稀疏編碼問題分解為兩個子字典下的稀疏編碼問題，在大大增加字典原子個數的同時降低了稀疏性求解過程的計算量。為了減少l1范數最小化的次數，利用基于嶺回歸的重構誤差排除大量無關粒子，從而選取重構誤差較小的若干個粒子求解其在兩個子字典的笛卡爾乘積上的稀疏表示。實驗結果表明由于字典中原子個數大大增加，使得目標能夠獲得更加高維的稀疏表示，進而使得目標和背景更加線性可分，提高了算法的魯棒性。

[1] Wu Yi, Lim J, and Yang Ming-hsuan. Online object tracking: a benchmark[C]. Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, Portland, USA, 2013: 2411-2418.

[2] Arnold W M S, Dung M C, Rita C, et al.. Visual tracking: an experimental survey[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2014, 36(7): 1442-1468.

[3] 彭義剛, 索津莉, 戴瓊海, 等. 從壓縮傳感到低秩矩陣恢復:理論與應用[J]. 自動化學報, 2013, 39(7): 981-994.

Peng Yi-gang, Suo Jin-li, Dai Qiong-hai, et al.. From compressed sensing to low-rank matrix recovery: theory and applications[J]. Acta Automatica Sinica, 2013, 39(7): 981-994.

[4] Wright, Yang A, Ganesh A, et al.. Robust face recognition via sparse representation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009, 31(2): 210-227.

[5] Zhang Sheng-ping, Yao Hong-xun, Sun Xin, et al.. Sparse coding based visual tracking: review and experimental comparison[J]. Pattern Recognition, 2013, 46(7): 1772-1788.

[6] 李佳, 王強, 沈毅, 等. 測量矩陣與重建算法的協同構造[J].電子學報, 2013, 41(1): 29-34.

Li Jia, Wang Qiang, Shen Yi, et al.. Collaborative construction of measurement matrix and reconstruction algorithm in compressive sensing[J]. Acta Electronica Sinica, 2013, 41(1): 29-34.

[7] Chatfield K, Lempitsky V, Vedaldi A, et al.. The devil is in the details: an evaluation of recent feature encoding methods[C]. Proceedings of British Machine Vision Conference (BMVC), Dundee, England, 2011: 1-12.

[8] Ge Tie-zheng, He Kai-ming, and Sun Jian. Product sparse coding[C]. Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, Columbus, USA, 2014: 1211-1218.

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

[10] Alex J S and Bernhard S. A tutorial on support vector regression[J]. Statistics and Computing, 2004, 14(3): 199-222.

[11] Chang Chih-chung and Lin Chih-jen. LIBSVM: a library for support vector machines[J]. ACM Transactions on Intelligent Systems and Technology, 2011, 2(3): 1-27.

[12] 向馗, 李炳南. 主元分析中的稀疏性[J]. 電子學報, 2012, 40(12): 2525-2532.

Xiang Kui and Li Bing-nan. Sparsity in principal component analysis: a survey[J]. Acta Electronica Sinica, 2012, 40(12): 2525-2532.

[13] Michel I and Andrew B. Condensation-conditional density propagation for visual tracking[J]. International Journal of Computer Vision, 1998, 29(1): 5-28.

[14] David A R, Jongwoo L, Lin R S, et al.. Incremental learning for robust visual tracking[J]. International Journal of Computer Vision, 2008, 77(1/3): 125-141.

[15] Babenko B, Yang Ming-hsuan, and Belongie S. Visual tracking with online multiple instance learning[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(8): 1619-1632.

[16] Bao Cheng-long, Wu Yi, Ling Hai-bin, et al.. Real time robust L1tracker using accelerated proximal gradient approach[C]. Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, Providence, RI, USA, 2012: 1830-1837.

[17] Zhang Kai-hua, Zhang Lei, and Yang M H. Fast compressive tracking[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2014, 36(10): 2002-2015.

[18] Mark E, Luc V G, Christopher K I, et al.. The PASCAL visual object classes (VOC) challenge[J]. Interational Journal of Computer Vision, 2010, 88(2): 303-338.

黃宏圖： 男，1986年生，博士生，研究方向為視頻目標跟蹤.

畢篤彥： 男，1962年生，博士，教授，博士生導師，研究方向為圖像處理和模式識別.

查宇飛： 男，1979年生，博士，副教授，研究方向為計算機視覺和機器學習.

高 山： 女，1983年生，博士，講師，研究方向為圖像處理.

覃 兵： 男，1991年生，碩士生，研究方向為視頻目標跟蹤.

Sparse Coding Visual Tracking Based on the Cartesian Product of Codebook

Huang Hong-tu Bi Du-yan Zha Yu-fei Gao Shan Qin Bing

(Aeronautics and Astronautics Engineering College, Air Force Engineering University, Xi’an 710038, China)

In order to improve the robustness of the visual tracking algorithm based on sparse coding, the original sparse coding problem is decomposed into two sub sparse coding problems. And the size of the codebook is intensively increased while the computational cost is decreased. Furthermore, in order to decrease the number of the1-norm minimization, ridge regression is employed to exclude the intensive outlying particles via the reconstruction error. And the sparse representation of the particles with small reconstruction error is computed on the two subcodebooks. The high-dimension sparse representation is put into the classifier and the candidate with the biggest response is recognized as the target. The experiment results demonstrate that the robustness of the proposed algorithm is improved due to the employed Cartesian product of subcodebooks.

Computer vision; Visual tracking; Cartesian product; Sparse coding; Support vector machine regression; Ridge regression

TP391

A

1009-5896(2015)03-0516-06

10.11999/JEIT140931

2014?07?15收到，2014-10-28改回

國家自然科學基金(61175029, 61379104, 61372167)，國家自然科學基金青年科學基金(61203268, 61202339)，博士后特別資助基金(2012M512144)和博士后面上資助基金(2012JQ8034)資助課題

*通信作者：黃宏圖 huanghongtu@sina.cn