基于協方差矩陣的壓縮感知跟蹤算法

黃慶俊+何儒漢

摘要：壓縮感知是信號處理領域的新理論，用于目標跟蹤算法時可在大量底層特征中提取出少量重要信息，減少計算量，提高算法速度。傳統的基于壓縮感知的跟蹤算法，為了保證算法速度，對壓縮后的特征簡單建模，準確性還有待提高。提出一種基于協方差矩陣的壓縮感知跟蹤算法，先利用壓縮感知原理獲取壓縮后的Haar特征，再利用協方差矩陣融合Haar特征區域內的底層多維特征，以此構建目標模型，并通過搜索當前目標區域的鄰域，利用流形空間上的距離度量算法匹配最佳目標，從而提高算法準確性。關鍵詞：壓縮感知；特征融合；協方差矩陣；Haar特征；LogEuclidean黎曼測度DOI：10.11907/rjdk.162874 中圖分類號： TP312 文獻標識碼： A 文章編號： 16727800（2017）004003104

0引言 壓縮感知（Compressive Sensing，CS）理論是信號處理領域最近幾年才提出的新理論[13]。信號處理包括4個基本過程：采樣、壓縮、傳輸以及恢復。壓縮感知理論將采樣與壓縮過程結合在一起，在采樣過程中對信號進行壓縮，可以低于香農定理的頻率獲取采樣數據，簡化信號處理過程，因而得到了信號處理領域的廣泛關注。同時，該理論在應用科學的諸多領域，如統計學、信息學、編碼領域等也有著相當重要的應用，推動了這些領域的基礎研究發展。 目標跟蹤是計算機視覺等熱點研究領域的核心課題之一[47]，其主要過程可分為目標建模和目標匹配。使用大量底層特征建模目標可以使匹配結果更準確，但會犧牲算法效率。壓縮感知理論在信號采集過程中提出的新方法為目標跟蹤領域帶來了啟發。Zhang等[8]在基于CS理論的實時跟蹤系統研究，使用壓縮感知理論對高維原始特征集降維，減少底層特征計算量，從而提高算法速度。另外，在目標跟蹤領域，基于協方差矩陣的跟蹤算法獲得了廣泛研究[1016]。協方差矩陣可以融合多種底層特征，同時保持低維特性，從而減輕了目標匹配過程的計算復雜度，保持了算法效率與魯棒性之間的平衡。 傳統的基于壓縮感知的跟蹤算法（Compress Sensing Tracking，CT）利用壓縮感知理論對原始數據中大量的Haar特征采樣壓縮，得到壓縮后的特征。隨后簡單計算Haar特征的區域積分作為特征值，以保證算法具有較快的處理速度。最后通過構造多組貝葉斯分類器來提高跟蹤結果的準確性。由于特征模型較為簡單，算法面對復雜場景如光照、干擾等狀況不能保持較好的魯棒性。基于此，提出一種基于協方差矩陣的壓縮感知跟蹤算法。使用協方差矩陣對壓縮后的Haar特征進行進一步處理，強化目標模型的表征能力，從而提高傳統壓縮感知跟蹤算法的準確度。1基于協方差矩陣的壓縮感知跟蹤算法原理及實現在CT基礎上，使用協方差矩陣描述算子融合多種底層點特征構造基本特征模型，改善算法適應能力，基本過程如下： ①應用協方差矩陣構造壓縮后的特征模型；②對搜索區域的待定目標計算相應的匹配模型；③根據匹配模型選擇合適的相似度算法，以決定最優的待定目標；④更新特征模型，轉②繼續跟蹤或者結束算法。1.1壓縮特征提取 Haar特征是計算機視覺等領域中常用的特征描述方法，若直接使用Haar特征來構建特征模型，則對于一個20*20的目標區域，可選的特征矩形將超過80 000個。盡管計算簡單，但由于數量較大，使得最終仍需要較多計算時間。因此，結合壓縮感知理論構造特定的壓縮矩陣，當選擇合適的觀測矩陣后，可以減少大量不必要的計算量，同時保留必要的Haar特征。 假設X={X1，X2…XN}表示目標區域內所有的Haar特征，V={V1，V2…VM}為降維后的特征，N>>M。壓縮過程為V=RX。 采用傳統壓縮感知跟蹤算法[8]中使用的隨機測量矩陣：rij=〖JB（{〗1 概率1/s0 概率1-1/s在公式（1）中，當s取值為2或3時，所構造出的測量矩陣滿足Johnson-Lindenstrauss推論。最后得到的矩陣會非常稀疏，很方便進行后續處理。算法中，s取值為m/4，最終的低維觀測值中不超過3個非零值，即用不超過3個矩形區域的組合（稱為Haarlike特征）對目標區域建模，從而大大減輕了計算量。1.2協方差矩陣特征計算傳統的壓縮感知跟蹤算法在獲取壓縮后的矩形特征后，對矩形區域內的單一點特征取積分值，以此構建目標模型。該處理可以使算法具有很高的速度，但魯棒性不夠優秀。為提高魯棒性，使用協方差矩陣進一步處理壓縮后的區域特征，融合區域內的多種點特征，同時保持較低維度。選定Haar特征組合即Haarlike特征后，可以得到2～3個矩形特征區域。對每一個矩形區域，提取區域內的點特征（坐標、顏色分類、梯度等），建立相應的協方差矩陣模型。設I為視頻序列的某一幀圖像，R是待定目標區域，F是對當前目標區域的建模，F（x，y）=（I，x，y），即F是對當前圖像上目標區域內所有像素的某種變換，表示區域中所有像素的d維底層特征向量，C表示計算的d×d的協方差矩陣，即：其中，μ表示區域內底層特征的均值向量，根據該公式可以得到區域R上的協方差矩陣。該協方差矩陣融合了d維的底層特征，底層特征可以任意選擇每個像素點的位置、梯度、顏色以及其它點特征。協方差矩陣中的每一個分量都表示相應的兩個底層特征之間的關聯信息。實際過程中，通過公式（2）計算協方差矩陣的過程往往過于繁瑣，計算速度相對較慢，文獻[4]提出的一種基于整體圖像的積分圖快速計算方法可以提高運算速度。同時考慮到目標運動過程中的時空連續性，在計算積分過程中只需對局部區域進行計算，從而進一步提高計算速度。

1.3目標匹配方法 在傳統的壓縮感知跟蹤算法中，取得目標模型后，在目標區域周圍采樣構造貝葉斯分類器，利用分類器對待定目標進行匹配識別。盡管需要多次采樣計算，但由于目標模型相對簡單，總計算量并不大。當選擇使用協方差矩陣來構造目標模型時，由于協方差矩陣本身計算量較大，采樣后的總計算量過于龐大，即使能完成跟蹤任務，算法已不具有實際應用意義。因此，有必要選擇其它方法來匹配目標。由于協方差矩陣模型已經融合了多種底層特征，因此可以簡單地通過計算目標模型之間的距離來判斷相似度。協方差矩陣是個正定矩陣，歐式空間中的相關算法并不適用于協方差矩陣，可以采用黎曼流形領域中的距離測度方法計算協方差矩陣之間的距離。文獻[17]中的log-Euclidean度量方法計算量相對較少，計算速度相對較快，因此本文采用該方法。首先對正定矩陣X進行奇異值分解，得到X=U*S*UT，隨后對X進行log運算，可以得到：對每個待定目標，計算目標的Haarlike特征的協方差矩陣值，應用流形距離度量算法，計算目標Haarlike特征的協方差矩陣與當前目標Haarlike特征的協方差矩陣之間的流形距離。在Haarlike特征中選擇2～3個矩形特征，最后會得到2～3個協方差矩陣距離。將這些距離值累加，最終可以得到待定目標與當前目標之間的相似度關系。最后選擇最接近的待定目標作為最終結果。在傳統的壓縮感知跟蹤算法中，通過使用多種壓縮后的HaarLike特征構造分類模型，利用多個分類模型同時對待定目標進行分類，以提高識別準確性。本文中同樣采用多個Haarlike特征，分別計算對應特征下的流形空間距離，將多個距離累加，得到最終的待定目標相似度，并以此選擇最優目標作為跟蹤結果。〖JP+2〗考慮到在實際應用場景中，并不是所有特征都對跟蹤具有正反饋效果，如某些特征可以很好地匹配人物的正面姿態，而某些特征則對側面姿態具有更好的識別能力。因此，可以在跟蹤過程中為不同特征賦予不同權重，以更好地適應人物當前的狀態變化。特征權重調整過程如下：〖JP〗（1）初始化M個Haarlike特征，每個特征的權值均為1/M。（2）在T幀時，計算當前目標Haarlike特征的協方差矩陣模型。（3）對搜索窗的每一個待定目標計算相應的M個Haarlike特征的協方差矩陣模型。（4）for i=1：M 計算待定目標與當前目標的第i個Haarlike特征協方差矩陣之間的流形距離 若距離超過閾值，則其它M-1個Haarlike特征的權值增加1/M end（5）歸一化權重，計算加權距離值，取距離最近的待定目標作為最終目標。同時以當前權值作為當前M個Haarlike特征的權重。最后整個算法的主要流程如圖1所示。1.4 協方差矩陣特征模型更新假設當前已有前T幀視頻序列的目標模型，需要獲取下一幀所需要的目標模型。最直觀的想法是使用已有目標模型的均值作為新的目標模型，由于協方差矩陣事實上是黎曼流形中的一點，因此可以使用黎曼流形中相應的均值計算方法。Li等[17]提出了一種基于log-Euclidean黎曼測度的均值算法。該算法只需經過基于矩陣的對數和指數運算即可得到協方差矩陣均值。相比于其它方法，該算法計算量少，計算速度快。其公式如下：

1.5基于協方差矩陣的壓縮感知跟蹤算法實現

（1）應用協方差矩陣構造壓縮后的基本特征模型。在利用CS理論選擇2～3個隨機矩形作為特征后，計算相應矩形區域的協方差矩陣；計算協方差矩陣時，選擇每個像素的位置、梯度和顏色值來構造7*7的CM；重復操作以得到多個壓縮后的特征模型。本文選擇重復100次。 （2）計算多組Haarlike特征的協方差矩陣特征值。 （3）檢索目標，確認最優結果。對每一個待定目標，計算相應Haarlike特征的協方差矩陣值，根據流形距離度量算法計算多個流形距離，應用加權距離算法計算待定目標距離，最終確定最優目標。 （4）若需要繼續跟蹤，則返回（2）；否則，算法結束。

2實驗 對比算法包括傳統的壓縮感知算法（CT）、基于局部搜索的協方差矩陣跟蹤算法（COV）和基于全局搜索的協方差矩陣跟蹤算法（GLOCOV）以及本文算法（WCTCOV），使用trackerbenchmark平臺的標準視頻幀序列basketball進行實驗。 實驗中，CT算法在首次發生干擾后丟失目標，且隨后不能自動找回；由于全局范圍內干擾，GLOCOV多次丟失目標，但可以將其自動找回；COV算法則僅在局部搜索目標，跟蹤穩定，準確性不高；本文算法保持穩定，且效果更好。實驗過程如圖2所示（彩圖見封三），青色為人工標定的結果，紅色為本文算法結果，綠色為CT跟蹤結果，藍色為COV跟蹤結果，黑色為GLOCOV跟蹤結果。 圖3所示（彩圖見封三）為每一幀的目標與人工標定目標的重合率。如圖所示，CT重合度很快下降，丟失目標，隨后跟蹤失敗；WCTCOV算法始終保持較高的重合度，具有較好的魯棒性；COV與GLOCOV由于僅有搜索區域的差別，兩者在局部有相同的匹配結果，即圖中兩者多次重合；GLOCOV在全局搜索目標，當干擾較多時，會匹配錯誤結果丟失目標，但可以快速將其找回。 表1所示為4種算法的有效目標占比，以及有效目標的平均重合率。其中有效目標占比表示與標定目標有重合的幀數與視頻序列長度的比值。重合率表示重合區域占標定目標的百分比范圍。有效目標占比可以直觀地說明算法跟蹤對目標的識別能力，顯然，應用協方差矩陣后，算法可以更多地識別到目標。重合率可以說明算法跟蹤結果是否足夠準確，顯然重合率高的更為準確。因此，本文算法對目標識別的準確度同樣相對較高。 通過實驗可以得出結論，相較于原始的壓縮感知算法，使用協方差矩陣后，算法對于干擾、目標快速運動等狀況有了更強的適應能力，可以更多、更準確地檢索到目標。盡管如此，在實驗中當干擾超過一定限度后，本文算法同樣會丟失目標。當前算法通過在上一幀目標周圍的局部范圍內搜索目標，以提高算法搜索速度，當目標超過該局部范圍時，算法并不能正確地尋找到目標。因此，當遮擋出現時，目標丟失。在后續工作中，可以在目標丟失時適當增加搜索范圍，從而在一定程度上提高算法魯棒性。

參考文獻：[1]DO T T，GAN L，NGUYEN N，et al.Sparsity adaptive matching pursuit algorithm for practical compressed sensing[C].Asilomar Conference on Signals，Systems and Computers，2008：581587.

[2]BARANIUK R，DAVENPORT M，DEVORE R，et al.A simple proof of the restricted isometry property for random matrices[J].Constructive Approximation，2008，28（3）：253263.

[3]EMMANUEL C，LAURENT D，DAVID D，et al.Fast discrete curvelet transforms[J].Multiscale Modeling & Simulation，2006，5（3）：861899.

[4]YILMAZ A，JAVED O，SHAH M.Object tracking： a survey[J].Acm Computing Surveys，2006，38（4）：8193.

[5]侯志強，韓崇昭.視覺跟蹤技術綜述[J].Acta Automatica Sinica，2006，32（4）：603617.

[6]K CANNONS.A review of visual tracking[R].Technical Report.Computer Science and Engineering，York University，2008.

[7]YANG H，SHAO L，ZHENG F，et al.Recent advances and trends in visual tracking： a review[J].Neurocomputing，2011，74（18）：38233831.

[8]ZHANG K，ZHANG L，YANG M H.Realtime compressive tracking[C].Computer Vision，2012：864877.

[9]TUZEL O，PORIKLI F，MEER P.Region covariance： a fast descriptor for detection and classification[C].Computer VisionECCV 2006，European Conference on Computer Vision，Graz，Austria，2006：589600.〖ZK）〗[10]〖ZK（#〗GUO Q，WU C，FENG Y，et al.Conjugate gradient algorithm for efficient covariance tracking with JensenBregman LogDet metric[J].Computer Vision Iet，2015，9（6）：814820.

[11]WANG D，LI L，LIU W，et al.Bayesian covariance tracking with adaptive feature selection[M].Advances in Neural Networks – ISNN 2014，2014：516523.

[12]XIE Y H，WU C D.Covariance tracking algorithm on bilateral filtering under lie group structure[J].Applied Mechanics & Materials，2014 （6）：682686.

[13]ROMERO A，LACASSAGNE L，GOUIFFS M，et al.Covariance tracking： architecture optimizations for embedded systems[J].EURASIP Journal on Advances in Signal Processing，2014（1）：115.

[14]顧鑫，王華，李喆，等.基于積分協方差矩陣的粒子濾波目標跟蹤[J].激光與紅外，2014（12）：13841386.

[15]謝英紅，吳成東.基于投影群和協方差流形雙重建模的目標跟蹤[J].儀器儀表學報，2014，35（2）：374379.

[16]蘆鴻雁，趙方舟.基于協方差描述子的紅外目標粒子濾波跟蹤算法[J].微電子學與計算機，2013，30（4）：7174.

[17]LI X，HU W，ZHANG Z，et al.Visual tracking via incremental logeuclidean riemannian subspace learning[C].Proc of IEEE Conference on Computer Version and Pattern Recognition，2008：18（責任編輯：黃健）

Abstract：Compressed sensing is a new theory in the signal processing.It can extract the important features from lots of lowlevel features when it is used for object tracking.Traditional tracking algorithm based on compressed sensing used a simple target model to keep the speed.To improve its accuracy，a compressed sensing tracking algorithm based on covariance matrix has been proposed.First，Haar features are compressed.by compressed sensing.Second，based on covariance matrix，a new target model with more lowlevel features is obtained.Then，the neighborhood of the current target is searched and the best target is matched using the manifold distance measure.Finally，the proposed algorithm gets a better accuracy.Key Words：Compressed Sensing； Feature Fusion； Covariance Matrix； Haar Feature； LogEuclidean Riemann Measure