以圖像分類為目標的字典學習算法

徐健　常志國　趙小強

摘 要：綜述了字典學習算法的主要研究方向之一，即以圖像分類為目標的稀疏表示字典學習算法。從空間變換法和類別指示法兩個角度，分析各種算法的優缺點，并對相應的實驗結果進行比較。總結了利用這類算法進行圖像分類時所面臨的其他一些關鍵問題，如模式識別中的旋轉不變性和計算速度等。依據目前已有的技術和應用需求，探尋該領域未來的研究方向。

關鍵詞：圖像分類；稀疏表示；字典訓練；原子

中圖分類號：TN391?34 文獻標識碼：A 文章編號：1004?373X（2013）02?0022?04

信號稀疏分解方法被廣泛的應用于圖像處理的各個領域。但是與具有完美數學形式的信號分解算法，如離散傅里葉變換（Discrete Fourier Transform，DFT）[1]、離散小波變換（Discrete Wavelet Transform，DWT）[2]和傳統的主成分分析法（Principle Component Analysis，PCA）不同，近年來許多人提出的信號稀疏分解算法不再要求稀疏表示矩陣為正交完備基底[3?4]。非正交過完備的表示矩陣被人們稱為字典。稀疏表示矩陣可以由機器學習算法產生，這類算法稱為字典學習算法。人們已經證明了當使用非正交過完備字典對信號進行稀疏表示時，能夠最稀疏表示一個樣本的字典系數是惟一的[5]。

1959年David Hubel和Toresten Wiesel通過對貓的視覺條紋皮層簡單細胞感受野的研究得出一個結論：主視皮層V1區神經元的感受野能對視覺感知信息產生一種“稀疏表示”，證明了稀疏表示符合視覺感知特性[6]。1993年Mallat等首次提出了應用過完備冗余原子庫對信號進行稀疏分解的思想，并引入了匹配追蹤算法，為非正交過完備字典的應用提供了理論基礎[7?8]。自2009年以來，過完備冗余字典的稀疏表示方法成為圖像處理領域和模式識別領域的研究熱點，被廣泛應用于解決計算機視覺方面的問題，如圖像去噪、圖像修補、圖像超分辨率放大和圖像分類等[9?11]。從目前的研究現狀來看，這類字典學習算法已經成為一個研究熱點，專為圖像分類而設計的字典學習算法就有幾十種。人們希望通過稀疏字典學習算法真正揭示人類視覺特性和圖像語義之間的關系。本文將這些字典學習算法的研究思路總結為兩大類，并根據目前的研究提出該領域未來可能的發展方向。

1 圖像分類

圖像分割、圖像識別等問題都可以歸為圖像分類問題。在利用稀疏表示進行的圖像分類研究中，如何設計對特征提取有效的字典和投影是決定算法性能最關鍵的因素[3]。

傳統的基于逼近的稀疏表示字典訓練模型為：

式中：[X]為訓練樣本矩陣，每列代表一個訓練樣本；[D]為待訓練的字典；[A]為表示系數；[ai]是組成[A]矩陣的列向量；[?F]表示矩陣的F范數；[?0]表示向量的0范數。該字典訓練模型的意義是在滿足[ai]的0范數約束情況下能達到殘差最小。為了完成圖像分類任務，人們在該模型的基礎上思考出許多改進方案。

在解決圖像分類問題的過程中，根據對稀疏表示特征的利用方式不同，利用稀疏表示進行圖像分類的方案可以分為2類：

（1）設計字典把圖像變化到有利于分類的空間上，把稀疏系數放入傳統分類器進行分類，稱之為空間變換法。

（2）設計字典原子與語義直接對應， 利用稀疏系數大小所表示出的樣本屬性進行分類。稱之為類別指示法。

式（1）所示的問題是雙變量優化問題，因此在迭代過程中大多使用固定一個變量優化另一個變量的交替優化算法[4]。本文后續所綜述的算法，凡是涉及字典學習算法的雙變量優化問題，均使用交替迭代的優化算法進行，本文后續的內容只描述字典訓練模型，不再贅述優化算法。

2 空間變換法

當樣本本身不易分類時，可以利用稀疏表示字典將其變換到易于分類的空間上去。為了讓這個空間有利于分類，需要在式（1）所示的字典訓練模型的基礎上加入一些約束。

文獻[12]建立字典訓練模型時，針對每個類訓練一個字典。該算法的字典訓練模型為式（2）。

[minDjNj=1i=1…Nl∈SiCλiR*xl，DjNj=1+λγR*xl，Di，yj=R*xl，Dj，Cλiy1，y2，…，yN=logj=1Ne-λyj-yi，R*x，D=x-Da*x，D22，a*x，D=argminα∈?kx-Da22，s.t. a0L] （2）

式中：[xl]是第[l]個訓練樣本；[Dj]是第[j]個類別對應的字典；[L]是稀疏度。式（2）中在減少稀疏殘差的基礎上，將優化目標變成殘差之間大小關系，其中的[Cλi]使用了logistic函數，保證了這些字典在對自己所對應類別的樣本進行稀疏表示時殘差比較小，在對其他類別的樣本進行稀疏表示時殘差比較大。該算法本質是將樣本矢量[x]映射為高維矢量[a]，然后使用K近鄰算法判斷類別。

但是由于logistic函數的運算量較大，該算法在考慮迭代算法時需要進行二階泰勒近似以降低運算復雜度。并且該算法針對每個類別都要訓練一個字典。在分類時，樣本需要在所有的字典下根據稀疏度約束進行稀疏表示，對比其殘差才能確定類別。因此算法復雜度較高。為了降低分類時算法的復雜度，文獻[13]提出了只用一個字典就能區分多個類別的字典訓練模型，如式（3）所示：

[minD，θ（i=1mμCS*xi，D，θ，-yi-S*xi，D，θ，yi+1-μS*xi，D，θ，yi）+λ2θ22，Sai，xi，D，θ，yi=Cyifxi，ai，θ+λ0xi-Dai22+λ1ai1，yi=R*xi，DCx=log1+e-x，fx，a，θ=wTa+b或fx，a，θ=xTWa+b，θ=W∈Rn×k，b∈R] （3）

該算法借助了支持向量機（Support Vector Machine，SVM）思想，試圖將線性分類器和字典[D]均作為訓練對象。優化目標兼顧正確判決的[S*]和錯誤判決[S*]之差及稀疏表示殘差，并加入了線性分類器（或雙線性分類器）的條件。通過理論分析，得出該算法在研究分類框架時兼顧了泛化能力，這樣就避免了過擬合現象，并且提高了該算法的魯棒性。但是該算法沒有解決線性組合系數[μ]如何選取的問題。而且，盡管分類時算法復雜度降低了，分類器訓練的過程算法復雜度仍然很高。無法針對維數較高的樣本進行訓練。

文獻[14]提出了一種圖像分類算法，其主要思路是在優化稀疏表示殘差的同時降低字典間的相關性。其字典訓練模型如式（4）所示：

[minDi，AiXi-DiAi2F+ηj≠iDTjDi，ai0

式中：[Xi]為第[i]類樣本；[Di]是對應第[i]類樣本的字典[Ai]是表示系數，[η]是拉格朗日參數。該字典訓練方法不但考慮了在固定稀疏度情況下的稀疏表示殘差，還把字典間的相關性作為約束條件。

實際上，如圖1所示，假設[Dj∈Rmj×nj]是固定的，[dkjnjk=1]是[Dj]中的原子。那么訓練得到的[Di]，如果和[Dj]互不相交的話，那么[Di]的所有原子只能位于[Dj]的正交補[Φ]上。如果[Dj]是過完備且列滿秩的字典，理論上[Di]不可能和[Dj]完全正交。因此它們之間一定存在不正交的原子。為了提高字典間的正交性，每個字典盡量都不占用更大的空間。這一點可以通過降低字典維數來得到。由于相關性的要求，每個類別的字典的訓練過程都被限制在與其他字典盡量不相關的狹小空間內尋找原子，而這些狹小空間未必能夠以較小殘差對該類樣本進行稀疏表示。因此相關性降低和稀疏表示殘差是一對矛盾。較小的相關性必然帶來較大的殘差，而較小的殘差會導致相關性增強。

圖1 字典間相關性的三維示意圖

因此對這類字典進行訓練的迭代算法必須要平衡相關性和殘差之間的矛盾。并且該算法沒有解決在同時優化字典和系數2個變量時如何選取最優步長的問題。不合適的步長將會導致2個變量不能同時收斂。

[minW∈Rm×p，D∈DEy，xlog1+e-yxTWα*x，D+v2W2F] （5）

隨后文獻[15]中對前面提出的算法做出了改進，提出了如式（5）描述的字典訓練模型。

該算法對logistic函數的運算結果的均值作為優化目標，并且使用雙線性函數訓練分類器提高了算法的泛化能力。盡管雙線性函數的參數眾多導致訓練復雜度提高，但是卻為分類器提供了更多靈活性，避免了過擬合現象。但是該算法僅僅在手寫數字識別等問題上進行了測試。對于更加大型或復雜問題的實驗仍然有待進一步研究。上述幾種算法都針對MNIST和USPS手寫數字識別進行了實驗，每個文章中算法的最佳實驗結果如表1所示。REC是使用式（1）所示的字典訓練模型訓練字典得到的分類錯誤率。A是文獻[13]的最佳實驗結果。B是文獻[14]的實驗結果。C是文獻[15]提出的算法在無監督學習過程中的實驗結果。D是文獻[15]提出的算法在有監督學習過程中的實驗結果。K?NN是K近鄰算法分類的實驗結果（其中K為10）。SVM?Gauss是SVM算法在使用高斯核函數時的實驗結果[16]。

文獻[12?15]都是將稀疏表示系數作為特征進行圖像分類，其本質是將圖像映射到便于分類的空間上去，然后運用傳統的分類算法（如K近鄰，SVM算法）進行分類。由于稀疏表示本身對于噪聲具有魯棒性。因此，運用該方法的分類算法有較低的錯誤率。

表該算法首先對圖像進行極坐標映射。假設[a，b]是圖像本身的坐標，則通過式（6）將其映射為[ξ，η]。然后再通過Rapid變換將其變為平移不變特征。最后將變換過的具有平移不變性的圖像作為訓練樣本進行字典學習。這樣學習得到的字典可以提取到圖像的平移和旋轉不變的特征。由于目前存在的字典學習算法都采用雙變量迭代更新的方法，且迭代步驟中都存在奇異值分解等運算規模較大的步驟，因此大多數都是利用低于100維的數據進行字典學習[20?21]。當遇到了較大圖像的字典學習問題，都采用將數據分割成小塊分別處理[10]。為了加快字典學習速度，文獻[22]提出了使用GPU并行技術來解決較大圖像的分類識別問題。利用GPU技術來提高各種圖像處理算法的速度將是未來圖像處理發展的趨勢。

5 結 論

從上述研究現狀來看，目前的用于分類識別的稀疏字典訓練還缺乏字典參數與語義之間的關系的論證，因此下一步的研究應當關注如何從字典訓練過程揭示圖像語義方面的問題。另外，稀疏表示的特征提取方法還處于起步階段。

上述文獻所涉及算法僅僅在小規模的較簡單的分類問題上進行了測試，還沒有觸及更加大型和復雜的問題。因此，對這類方法的應用還有待進一步開發。稀疏表示的字典訓練往往涉及優化問題，需要大量的樣本參與運算，算法復雜度較高。盡管已經有少部分研究人員利用GPU技術進行仿真實驗，但是如何專門為GPU設計迭代算法，充分發揮GPU的并行計算能力，也是該領域未來的發展方向。

隨著基于訓練的字典模型理論的完善，信號處理將不再局限于以傳統的正交完備基為理論基礎。非正交過完備字典以其符合人眼感知機理、系數稀疏性、魯棒性和靈活性等優勢將成為未來信號處理研究的主流。

參考文獻

[1] 季虎，夏勝平，郁文賢.快速傅里葉變換算法概述[J].現代電子技術，2001，24（8）：11?14.

[2] 周義明，張超，張化民.樣條小波的構造方法及其應用[J].現代電子技術，2009，32（8）：36?40.

[3] WRIGHT J， MA Y， MAIRAL J， et al. Sparse representation for computer vision and pattern recognition [J]. Proceedings of the IEEE， 2010， 98（6）： 1031?1044.

[4] AHARON Michal， ELAD Michael， BRUCKSTEIN Alfred. K?SVD： An algorithm for designing overcomplete dictionaries for sparse representation [J]. IEEE Transactions on Signal Processing， 2006， 54（11）： 4311?4322.

[5]AHARON M， ELAD M， BRUCKSTEIN A M. On the uniqueness of overcomplete dictionaries， and a practical way to retrieve them [J]. Linear algebra and its applications， 2006， 416（1）： 48?67.

[6] HUBEL D H， WIESEL T N. Receptive fields of single neurones in the cat's striate cortex [J]. The Journal of physiology， 1959， 148（3）： 574?591.

[7]王建英，尹忠科，張春梅.信號與圖像的稀疏分解及初步應用[M].成都：西南交通大學出版社，2006.

[8] MALLAT S G， ZHANG Z. Matching pursuits with time?frequency dictionaries [J]. IEEE Transactions on Signal Processing， 1993， 41（12）： 3397?3415.

[9] XU Z， SUN J. Image inpainting by patch propagation using patch sparsity [J]. IEEE Transactions on Image Processing， 2010， 19（5）： 1153?1165.

[10] ELAD M， AHARON M. Image denoising via sparse and redundant representations over learned dictionaries [J]. IEEE Transactions on Image Processing， 2006， 15（12）： 3736?3745.

[11] ZHANG Hai?chao， ZHANG Yan?ning， HUANG THOMAS S. Efficient sparse representation based image super resolution via dual dictionary learning [C]// IEEE International Conference on Multimedia and Expo. Barcelona， Spain： IEEE， 2011： 1?6.

[12] MAIRAL J， BACH F， PONCE J， et al. Discriminative learned dictionaries for local image analysis [C]// IEEE Conference on Computer Vision and Pattern Recognition. Anchorage， Alaska， USA： IEEE， 2008： 1?8.

[13] MAIRAL J.， BACH F.， PONCE J.， et al. Supervised dictionary learning[C]//Annual Conference on Neural Information Processing Systems. Vancouver， BC， Canada： CNIPS， 2008： 1?6.

[14] RAMIREZ I， SPRECHMANN P， SAPIRO G. Classification and clustering via dictionary learning with structured incoherence and shared features [C]// IEEE Conference on Computer Vision and Pattern Recognition. San Francisco， CA， USA： IEEE， 2010： 3501?3508.

[15] MAIRAL J， BACH F， PONCE J. Task?driven dictionary learning [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2012， 34（4）： 791?804.

[16] LECUN Y， BOTTOU Y， BENGIO Y. Gradient?based learning applied to document recognition [J]. Proceedings of IEEE， 1998， 86（11）： 2278?2324.

[17] WRIGHT J， YANG A Y， GANESH A， et al. Robust face recognition via sparse representation [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2009， 31（2）： 210?227.

[18] YANG M， ZHANG L. Gabor feature based sparse representation for face recognition with Gabor occlusion dictionary [C]// Proceedings of the 11th European Conference on Computer Vision. Berlin： Springer?Verlag， 2010： 448?461.

[19] BAR L， SAPIRO G. Hierarchical dictionary learning for invariant classification [C]// Proceedings of 2010 IEEE International Conference on Acoustics， Speech， and Signal Processing. Dallas， TX， USA： IEEE， 2010： 3578?3581.

[20] MAIRAL J， BACH F， PONCE J， et al. Online dictionary learning for sparse coding [C]// Proceedings of Annual International Conference on Machine Learning. Montreal， QC， Canada： AICML， 2009： 689?696.

[21] ZOLTAN S， BARNABAS P， ANDRAS L. Online group?structured dictionary learning [C]// Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. Colorado Springs， CO， USA： IEEE， 2011： 2865?2872.

[22] NAGESH P， GOWDA R， LI B. Fast GPU implementation of large scale dictionary and sparse representation based vision problems [C]// Proceedings of 2010 IEEE International Conference on Acoustics， Speech， and Signal Processing. Dallas， TX， USA： IEEE， 2010： 1570?1573.