壓縮跟蹤Compressive Tracking

zouxy09@qq.com

http://blog.csdn.net/zouxy09

???

????? 好了，學習了解了稀疏感知的理論知識后，終于可以來學習《Real-Time Compressive Tracking》這個paper介紹的感知跟蹤算法了。自己英文水平有限，理解難免出錯，還望各位不吝指正。

????? 下面是這個算法的工程網站：里面包含了上面這篇論文、Matlab和C++版本的代碼，還有測試數據、demo等。后面我再學習學習里面的C++版本的代碼，具體見博客更新。

http://www4.comp.polyu.edu.hk/~cslzhang/CT/CT.htm

?????? 之前自己稍微學習了下稀疏感知的理論知識總結：

http://blog.csdn.net/zouxy09/article/details/8118329

?

一、實時壓縮跟蹤：

????? 感謝香港理工大學的Kaihua Zhang，這是他即將在ECCV 2012上出現的paper：Real-timeCompressive Tracking。這里是他的介紹：

??????? 一種簡單高效地基于壓縮感知的跟蹤算法。首先利用符合壓縮感知RIP條件的隨機感知矩對多尺度圖像特征進行降維，然后在降維后的特征上采用簡單的樸素貝葉斯分類器進行分類。該跟蹤算法非常簡單，但是實驗結果很魯棒，速度大概能到達40幀/秒。

?????? 實際上，感覺上面這幾句話的介紹已經高度的概括了這個論文的主要思想。和一般的模式分類架構一樣：先提取圖像的特征，再通過分類器對其分類，不同在于這里特征提取采用壓縮感知，分類器采用樸素貝葉斯。然后每幀通過在線學習更新分類器。當然，里面還包含著很多細節的推導和優化了，下面我們從論文中一起來學習一下。

????? 上一博文中提到compressive sensing的主要原理就是用一個隨機感知矩陣去降維一個高維信號，得到的低維信號可以完全保持高維信號的特性。這個隨機感知矩陣要滿足CS理論的RIP條件就可以完全從低維信號重建高維信號。

?

二、主要思想：

?????? 我再啰嗦一下：通過稀疏感知理論可以知道，我們通過一個滿足RIP條件的非常稀疏的測量矩陣對原圖像特征空間做投影，就可以得到一個低維壓縮子空間。低維壓縮子空間可以很好的保留高維圖像特征空間的信息。所以我們通過稀疏測量矩陣去提取前景目標和背景的特征，作為在線學習更新分類器的正樣本和負樣本，然后使用該樸素貝葉斯分類器去分類下一幀圖像的目標待測圖像片（感知空間下）。

?

三、具體工作過程如下：

（1）在t幀的時候，我們采樣得到若干張目標（正樣本）和背景（負樣本）的圖像片，然后對他們進行多尺度變換，再通過一個稀疏測量矩陣對多尺度圖像特征進行降維，然后通過降維后的特征（包括目標和背景，屬二分類問題）去訓練樸素貝葉斯分類器。

（2）在t+1幀的時候，我們在上一幀跟蹤到的目標位置的周圍采樣n個掃描窗口（避免去掃描整幅圖像），通過同樣的稀疏測量矩陣對其降維，提取特征，然后用第t幀訓練好的樸素貝葉斯分類器進行分類，分類分數最大的窗口就認為是目標窗口。這樣就實現了從t幀到t+1幀的目標跟蹤。

?

四、相關理論推導：

4.1、隨機投影：

????? 一個n x m的隨機矩陣R，它可以將一個高維圖像空間的x（m維）變換到一個低維的空間v（n維），數學表達就是：v = R x

????? 在這里n遠遠小于m（這樣才叫降維嘛）。最理想的情況，我們當然希望低維的v可以完全的保留高維的x的信息，或者說保持原始空間中各樣本x的距離關系，這樣在低維空間進行分類才有意義。

??????? Johnson-Lindenstrauss推論表明：可以隨機選擇一個適當的高維子空間（當然，需要比原始空間維度小），原始空間兩點的距離投影到這個子空間，能高概率的保留這種距離關系。（K+1次測量足以精確復原N維空間的K-稀疏信號）。

?????? 而Baraniuk證明了滿足Johnson-Lindenstrauss推論的隨機矩陣同樣滿足壓縮感知理論中的restricted isometry property（RIP）條件。所以，如果隨機矩陣R滿足Johnson-Lindenstrauss推論，那么如果x是可壓縮的（或者說是稀疏的），我們就可以通過最小化誤差來從v中高概率恢復x。

?????? 所以原文就找到了一個非常稀疏的投影矩陣，不但滿足Johnson-Lindenstrauss推論，而且可以高效的實時計算。

?

4.2、隨機測量矩陣：

?????? 一個比較典型的滿足RIP條件的測量矩陣是隨機高斯矩陣，矩陣元素滿足N(0,1)分布。但是，如果m的維數比較大的話，這個矩陣還是比較稠密的，它的運算和存儲消耗還是比較大的。而在原文，采用了一個非常稀疏的隨機測量矩陣，其矩陣元素定義為：

???????? Achlioptas證明了，上式s取2或者3時，矩陣就滿足Johnson-Lindenstrauss推論。這個矩陣非常容易計算，因為它只需要一個均勻隨機數發生器就行，而且當s=3時，這個矩陣非常稀疏，計算量將會減少2/3。如果s=3，那么矩陣元素有1/6的概率為1.732（表示根號3，懶得插入公式了），有1/6的概率為-1.732，有2/3的概率為0；

??????? 本文中s=m/4，矩陣R的每一行只需要計算c（小于4）個元素的值。所以它的計算復雜度為O(cn)。另外，我們只需要存儲R的非零元素即可，所以所需存儲空間也很少。

?

4.3、提出的算法：

????? 上圖表明一個n x m的稀疏矩陣，它可以將一個高維圖像空間的x（m維）變換到一個低維的空間v（n維），數學表達就是：v = R x ；

????? 其中，矩陣R中，黑色、灰色和白色分別代表矩陣元素為負數、正數和零。藍色箭頭表示測量矩陣R的一行的一個非零元素感知x中的一個元素，等價于一個方形窗口濾波器和輸入圖像某一固定位置的灰度卷積。

????? 為了實現尺度不變性，對每一個樣本z?R^wxh，通過將其與一系列多尺度的矩形濾波器{h_1,1,…,h_w,h}進行卷積，每一種尺度的矩形濾波器定義如下：

?????? 式中，i和j分別是矩形濾波器（模版）的寬和高。然后將濾波后的的圖像矩陣展成一個wxh維的列向量。再將這些列向量連接成一個非常高維（(wxh)²維）的多尺度圖像特征向量x=(x₁,…,x_m)^T。維數一般在10的6次方到10次方之間。

????? 我們通過采用上面的稀疏隨機矩陣R將x投影到低維空間的v。這個隨機矩陣R只需要在程序啟動時計算一次，然后在跟蹤過程中保持不變。通過積分圖，我們可以高效的計算v。

?

4.4、低維壓縮特征的分析：

?????? 低維特征v的每一個元素v_i是不同尺度的空間分布特征的線性組合。由于測量矩陣R的系數可正，可負，所以壓縮特征可以像廣義Haar-like特征一樣計算相關灰度差。Haar-like特征的計算比較耗時，傳統方法是通過boosting算法選擇重要的特征來減少需要計算的特征數。本文中，我們通過稀疏測量矩陣對這些數目龐大的Haar-like特征進行壓縮，稀疏感知理論保證了，壓縮后的特征幾乎保留原有圖像的信息。因此，我們可以直接對壓縮空間里面的投影特征進行分類，而避免了維數災難。

?

4.5、分類器構建和更新：

?????? 對每個樣本z（m維向量），它的低維表示是v（n維向量，n遠小于m）。假定v中的各元素是獨立分布的?？梢酝ㄟ^樸素貝葉斯分類器來建模。

?????? 其中，y?{0,1}代表樣本標簽，y=0表示負樣本，y=1表示正樣本，假設兩個類的先驗概率相等。p(y=1)=p(y=0)=0.5。Diaconis和Freedman證明了高維隨機向量的隨機投影幾乎都是高斯分布的。因此，我們假定在分類器H(v)中的條件概率p(v_i|y=1)和p(v_i|y=0)也屬于高斯分布，并且可以用四個參數來描述：

?

上式中的四個參數會進行增量更新：

式中，學習因子λ>0，

上式可以由最大化似然估計得到。

????? 圖中顯示了從某幀中的正樣本和負樣本提取出的三個不同特征（低維空間下）的概率分布。紅色和藍色階梯線分別代表正樣本和負樣本的直方圖。而紅色和藍色的曲線表示通過我們的增量更新模型得到的相應的分布估計。圖說明了在投影空間，通過上式描述的在線更新的高斯分布模型是特征的一個良好估計。

?

五、壓縮跟蹤算法：

輸入：第t幀圖像

1、在t-1幀跟蹤到的目標位置I_t-1的周圍（也就是滿足D^γ={z|||l(z)?l_t?1||<γ，與I_t-1距離小于γ）采樣n個圖像片，然后對這些圖像片進行特征提取（降維），得到每個圖像片的特征向量v。

2、使用式（4）中分類器H(v)對這些v進行分類，找到最大分類分數的圖像片作為當前幀跟蹤到的目標，位置為I_t；

3、采樣兩個樣本集：D^α= {z|||l(z) ? l_t|| < α}和 D^{ζ ,β}= {z|ζ < ||l(z)?l_t|| <β}其中，α< ζ < β；

4、提取上述兩個樣本集的特征，通過式（6）來更新分類器參數。

輸出：跟蹤到的目標位置I_t和更新后的分類器參數。

總結

以上是生活随笔為你收集整理的压缩跟踪Compressive Tracking的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。