以圖像分類為目標(biāo)的字典學(xué)習(xí)算法

徐健　常志國　趙小強(qiáng)

摘 要：綜述了字典學(xué)習(xí)算法的主要研究方向之一，即以圖像分類為目標(biāo)的稀疏表示字典學(xué)習(xí)算法。從空間變換法和類別指示法兩個角度，分析各種算法的優(yōu)缺點(diǎn)，并對相應(yīng)的實(shí)驗(yàn)結(jié)果進(jìn)行比較?？偨Y(jié)了利用這類算法進(jìn)行圖像分類時所面臨的其他一些關(guān)鍵問題，如模式識別中的旋轉(zhuǎn)不變性和計(jì)算速度等。依據(jù)目前已有的技術(shù)和應(yīng)用需求，探尋該領(lǐng)域未來的研究方向。

關(guān)鍵詞：圖像分類；稀疏表示；字典訓(xùn)練；原子

中圖分類號：TN391?34 文獻(xiàn)標(biāo)識碼：A 文章編號：1004?373X（2013）02?0022?04

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

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

1 圖像分類

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

傳統(tǒng)的基于逼近的稀疏表示字典訓(xùn)練模型為：

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

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

（1）設(shè)計(jì)字典把圖像變化到有利于分類的空間上，把稀疏系數(shù)放入傳統(tǒng)分類器進(jìn)行分類，稱之為空間變換法。

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

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

2 空間變換法

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

文獻(xiàn)[12]建立字典訓(xùn)練模型時，針對每個類訓(xùn)練一個字典。該算法的字典訓(xùn)練模型為式（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]個訓(xùn)練樣本；[Dj]是第[j]個類別對應(yīng)的字典；[L]是稀疏度。式（2）中在減少稀疏殘差的基礎(chǔ)上，將優(yōu)化目標(biāo)變成殘差之間大小關(guān)系，其中的[Cλi]使用了logistic函數(shù)，保證了這些字典在對自己所對應(yīng)類別的樣本進(jìn)行稀疏表示時殘差比較小，在對其他類別的樣本進(jìn)行稀疏表示時殘差比較大。該算法本質(zhì)是將樣本矢量[x]映射為高維矢量[a]，然后使用K近鄰算法判斷類別。

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

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

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

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

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

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

圖1 字典間相關(guān)性的三維示意圖

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

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

隨后文獻(xiàn)[15]中對前面提出的算法做出了改進(jìn)，提出了如式（5）描述的字典訓(xùn)練模型。

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

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

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

5 結(jié) 論

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

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

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

參考文獻(xiàn)

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

[2] 周義明，張超，張化民.樣條小波的構(gòu)造方法及其應(yīng)用[J].現(xiàn)代電子技術(shù)，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]王建英，尹忠科，張春梅.信號與圖像的稀疏分解及初步應(yīng)用[M].成都：西南交通大學(xué)出版社，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.