图像的稀疏表示——ScSPM和LLC的总结
稀疏編碼系列：
- （一）----Spatial Pyramid 小結
- （二）----圖像的稀疏表示——ScSPM和LLC的總結
- （三）----理解sparse coding
- （四）----稀疏模型與結構性稀疏模型
---------------------------------------------------------------------------
?
-
前言
???????上一篇提到了SPM。這篇博客打算把ScSPM和LLC一起總結了。ScSPM和LLC其實都是對SPM的改進。這些技術，都是對特征的描述。它們既沒有創造出新的特征（都是提取SIFT,HOG, RGB-histogram et al），也沒有用新的分類器（也都用SVM用于最后的image classification），重點都在于如何由SIFT、HOG形成圖像的特征（見圖1）。從BOW，到BOW+SPM，都是在做這一步。說到這，怕會迷糊大家------SIFT、HOG本身不就是提取出的特征么，它們不就已經形成了對圖像的描述了嗎，為啥還有我后面提到的各種BOW云云呢。這個問題沒錯，SIFT和HOG它們確實本身已經是提取到的特征了，我們姑且把它們記為x。而現在，BOW+SPM是對特征x再進行一層描述，就成了Φ(x)——這相當于是更深一層（deeper）的model。一個十分相似的概念是SVM里面的核函數kernel，K=Φ(x)Φ(x)，x是輸入的特征，Φ(x)則對輸入的特征又做了一層抽象（不過我們用核函數沒有顯式地對Φ(x)做定義罷了）。根據百度的余凱老師在CVPR2012的那個Tutorial上做的總結[5]：Deeper model is preferred，自然做深一層的抽象效果會更好了。而Deep Learning也是同樣的道理變得火了起來。
? ? ? ?再次盜用一些余凱老師在CVPR2012的那個Tutorial上的一些圖：
圖 （1）
? ? ? ? SPM，ScSPM，LLC所做的工作也都集中在design feature這一步，而不是在Machine Learning那一步。值得注意的是，我們一直在Design features，而deep learning則是design feature learners。
????? BOW+SPM的整體流程如圖(2)所示：
圖（2）
??????? Feature Extraction的整體過程就是先提取底層的特征（SIFT，HOG等），然后經過coding和pooling，得到最后的特征表示。
???????????? ----Coding: nonlinear mapping data into another feature space
???????????? ----Pooling: obtain histogram
????????而SIFT、HOG本身就是一個coding+pooling的過程，因此BOW+SPM就是一個兩層的Coding+Pooling的過程。所以可以說，SIFT、SURF等特征的提出，是為了尋找更好的第一層Coding+Pooling的辦法；而SPM、ScSPM、LLC的提出，是為了尋找更好的第二層Coding+Pooling的辦法。而ScSPM和LLC所提出的更好的Coding辦法就是Sparse Coding。
圖（3）
?
-
再前言
????????在總結ScSPM之前又要啰嗦些話。為啥會有SPM→ScSPM呢？原因之一是為了尋找better coding + better pooling的方式提高性能，原因之二就是提高速度。如何提高速度？這里的速度，不是Coding+Pooling的速度，而是分類器的速度。SPM設計的是一個Linear feature，在文章中作者用于實驗則是用了nonlinear SVM（要用Mercer Kernels）。相比linear SVM，nonlinear SVM在training和testing的時候速度會慢的。至于其原因，我們不妨看看SVM的對偶形式：
(1)
??????? 如果核函數是一個線性的kernel：K(z, zi)=zTzi，那么SVM的決策函數就可以改寫為：
??? (2)
????????? 從兩式可以看見，拋開訓練和存儲的復雜度不說，對于測試來說，（1）式對每個測試樣本要單獨計算K(z, zi)，因此testing的時間復雜度為O(n)。而（2）式的wT可以一次性事先算出，所以每次testing的時間復雜度為O(1)。此外，linear classifier的可擴展性會更好。
????????? 因此，如果能在coding+pooling后設計得到線性可分的特征描述，那就最好了。因此能否設計一個nonlinear feature + linear SVM得到與 linear feature + nonlinear SVM等效甚至更好的效果，成為ScSPM和LLC的研究重點。
-
ScSPM
??????? SPM在coding一步采用的是Hard-VQ，也就是說一個descriptor只能投影到dictionary中的一個term上。這樣就造成了明顯的重建誤差（worse reconstruction，large quantization errors）。這樣，原本很相似的descripors經過coding之后就會變得非常不相似了。ScSPM為此取消了這一約束，它認為descripor可以投影到某幾個terms上，而不僅僅是一個。因此，其目標函數變成了：
???? (3)
?????? ?其中M是descriptor的數目，Um表示第m個descriptor在字典V上的投影系數。
??????? 它對投影系數用L1-norm做約束實現了稀疏。求解問題稱為LASSO (least absolute shrinkage and selection operator)，在得到稀疏結果的同時，它無法得到解析解，因此速度肯定是很慢的。關于L1-norm和LASSO問題，可以參看這里。
??????? 為什么Sparse Coding好，主要有以下幾個原因：
????? 1）已經提到過的重建性能好；[2]
????? 2）sparse有助于獲取salient patterns of descripors；[2]
????? 3）image statistics方面的研究表明image patches都是sparse signals；[2]
????? 4）biological visual systems的研究表明信號的稀疏特征有助于學習；[4]
????? 5）稀疏的特征更加線性可分。[2]
?????????總之，"Sparse coding is a better building block“。
???????? Coding過后，ScSPM采用的Pooling方法是max pooling：Zj=max Uij。相比SPM的average pooling：Zj=1/M *Σ Uij。可以看見average pooling是一個linear feature representation，而max pooling是nonlinear的。我是這么理解再前言中提到的linear和nonlinear feature的。(@13.08.11:今天在寫理解sparse coding的時候發現這里搞錯了。不光是pooling的函數是線性的，VQ的coding得到的u關于x好像也是線性的。)
??????? 作者在實驗中得出max pooling的效果好于average pooling，原因是max pooling對local spatial variations比較魯棒。而Hard-VQ就不好用max pooling了，因為U中各元素非0即1。
??????? 另外實驗的一個有趣結果是發現ScSPM對大的codebook size表現出更好的性能，反觀SPM，codebook大小對SPM結果影響不大。至于為啥，我也不懂。
-
LLC
???????? LLC和ScSPM差不多了，也是利用了Sparsity。值得一說的是，其實Hard-VQ也是一種Sparse Coding，只不過它是一種重建誤差比較大的稀疏編碼。LLC對ScSPM的改進，則在于引入了locality。為了便于描述，盜用一下論文的圖：
圖（4）
??????? 這個圖實在是太棒了，太能解釋問題了。VQ不用說，重點在于SC和LLC之間，LLC引入了locality的約束，即不僅僅是sparse要滿足，非零的系數還應該賦值給相近的dictionary terms。作者在[4]中解釋到，locality 很重要是因為：
???? 1）nonlinear function的一階近似要求codes是local的；
???? 2）locality能夠保證codes的稀疏性，而稀疏卻不能保證locality；
??? ?3）稀疏的coding只有再codes有局部性的時候有助于learning。
????????總之，"locality is more essential than sparsity"。
?????? ?LLC的目標函數是：
???? (4)
?????? 和（3）一樣，（4）可以按照加號的前后分成兩部分：加號前的一項最小化是為了減少量化誤差（學習字典、確認投影系數）；加號后的一項則是做出假設約束（包括是一些參數的regularization）。這個求解是可以得到閉合解的，同時也有快速的近似算法解決這個問題，因此速度上比ScSPM快。
?????? di描述的是xi到每個dictionary term的距離。顯然這么做是為了降低距離大的term對應的系數。
?????? locality體現出的最大優勢就是，相似的descriptors之間可以共享相似的descriptors，因此保留了codes之間的correlation。而SC為了最小化重建誤差，可能引入了不相鄰的terms，所以不能保證smooth。Hard-VQ則更不用說了。
?????? 實驗部分，則采用max pooling + L2-normalization。
???
??????? 文章的最后，盜竊一個ScSPM第一作者的總結表格結束吧（又是以偷竊別人圖標的方式結束）
?
References：
[1] S. Lazebnik, C. Schmid, and J. Ponce.?Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories. CVPR2006
[2] Jianchao Yang, Kai Yu, Yihong Gong, and Thomas Huang.?Linear spatial pyramid matching using sparse coding for image classification.?CVPR2009.
[3] Jinjun Wang, Jianchao Yang, Kai Yu, Fengjun Lv, and Thomas Huang.?Locality-constrained linear coding for image classification. CVPR2010
[4] Kai Yu, Tong Zhang, and Yihong Gong.?Nonlinear learning using local coordinate coding.?NIPS2009.
[5] Kai Yu.?CVPR12 Tutorial on Deep Learning: Sparse Coding.
-----------------------
作者：jiang1st2010
引用請注明來源：http://blog.csdn.net/jwh_bupt/article/details/9837555
總結
以上是生活随笔為你收集整理的图像的稀疏表示——ScSPM和LLC的总结的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 空间金字塔匹配Spatial Pyram
- 下一篇： 稀疏模型与结构性稀疏模型