人臉跟蹤：CT壓縮跟蹤
壓縮跟蹤Compressive Tracking
好了，學習瞭解了稀疏感知的理論知識後，終於可以來學習《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∊Rwxh，通過將其與一系列多尺度的矩形濾波器{h1,1,…,hw,h}進行卷積，每一種尺度的矩形濾波器定義如下：
式中，i和j分別是矩形濾波器（模版）的寬和高。然後將濾波後的的圖像矩陣展成一個wxh維的列向量。再將這些列向量連接成一個非常高維（(wxh)2維）的多尺度圖像特徵向量x=(x1,…,xm)T。維數一般在10的6次方到10次方之間。
我們通過採用上面的稀疏隨機矩陣R將x投影到低維空間的v。這個隨機矩陣R只需要在程序啓動時計算一次，然後在跟蹤過程中保持不變。通過積分圖，我們可以高效的計算v。
4.4、低維壓縮特徵的分析：
低維特徵v的每一個元素vi是不同尺度的空間分佈特徵的線性組合。由於測量矩陣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(vi|y=1)和p(vi|y=0)也屬於高斯分佈，並且可以用四個參數來描述：
上式中的四個參數會進行增量更新：
式中，學習因子λ>0，
上式可以由最大化似然估計得到。
圖中顯示了從某幀中的正樣本和負樣本提取出的三個不同特徵（低維空間下）的概率分佈。紅色和藍色階梯線分別代表正樣本和負樣本的直方圖。而紅色和藍色的曲線表示通過我們的增量更新模型得到的相應的分佈估計。圖說明了在投影空間，通過上式描述的在線更新的高斯分佈模型是特徵的一個良好估計。
五、壓縮跟蹤算法：
輸入：第t幀圖像
1、在t-1幀跟蹤到的目標位置It-1的周圍（也就是滿足Dγ={z|||l(z)−lt−1||<γ，與It-1距離小於γ）採樣n個圖像片，然後對這些圖像片進行特徵提取（降維），得到每個圖像片的特徵向量v。
2、使用式（4）中分類器H(v)對這些v進行分類，找到最大分類分數的圖像片作爲當前幀跟蹤到的目標，位置爲It；
3、採樣兩個樣本集：Dα= {z|||l(z) − lt|| < α}和 Dζ ,β= {z|ζ < ||l(z)−lt|| <β}其中，α< ζ < β；
4、提取上述兩個樣本集的特徵，通過式（6）來更新分類器參數。
輸出：跟蹤到的目標位置It和更新後的分類器參數。