稀疏表示在信號(hào)處理中的應(yīng)用

SparseRepresentationsforSignalProcessingandCoding120140420outlineWhataresparserepresentations/approximations?Howtofindsparserepresentations/approximations?HowtofindthedictionaryD?Whataresparserepresentations/approximationsgoodfor?2Whataresparserepresentations/approximations?定義：用較少的基本信號(hào)的線(xiàn)性組合來(lái)表達(dá)大部分或者全部的原始信號(hào)信號(hào)。其中，這些基本信號(hào)被稱(chēng)作原子，是從過(guò)完備字典中選出來(lái)的；而過(guò)完備字典則是由個(gè)數(shù)超過(guò)信號(hào)維數(shù)的原子聚集而來(lái)。可見(jiàn)，任一信號(hào)在不同的原子組下有不同的稀疏表示。3Whataresparserepresentations/approximations?4Howtofindsparserepresentations/approximations?尋找少量重要的系數(shù)來(lái)表示原始信號(hào)的技術(shù)被稱(chēng)作SparseCoding（稀疏編碼或稀疏分解）；從任意一個(gè)字典中為原始信號(hào)尋找最稀疏的表示常用的方法分類(lèi)兩類(lèi)：①貪婪算法，比如匹配追蹤（MP）、正交匹配追蹤（OMP）、弱匹配追蹤（WMP）、閾值方法等；②松弛算法，比如迭代加權(quán)最小二乘（Iterative-Reweighed-Least-Squares，IRLS）、基追蹤（BP）等。其中，貪婪算法的特點(diǎn)是速度快，精度相對(duì)較低；松弛算法是精度高，但速度慢。5Howtofindsparserepresentations/approximations?現(xiàn)假設(shè)已知字典D和信號(hào)X，進(jìn)行稀疏編碼的問(wèn)題可以表示為L(zhǎng)0優(yōu)化問(wèn)題這也是一個(gè)組合優(yōu)化問(wèn)題。窮舉法——NP難：假設(shè)

的非零項(xiàng)數(shù)目為L(zhǎng)(sparselevel)，先令L=1，字典里的每一個(gè)原子（列向量）嘗試一遍，看是否滿(mǎn)足終止條件，共有K種組合。如果沒(méi)有滿(mǎn)足，再令L=2，再次嘗試，共有K(K-1)/2種組合。還沒(méi)有滿(mǎn)足條件的，則令L=3……組合的數(shù)目呈指數(shù)增長(zhǎng)，于是遇到了NP難問(wèn)題。貪婪算法——MatchingPursuit第一步，找到最接近X的原子，等效于

向量上僅取一個(gè)非零項(xiàng)，求出最接近的原子，保留下來(lái)；第二步，計(jì)算誤差是否滿(mǎn)足要求，如果滿(mǎn)足，算法停止，否則，計(jì)算出殘差信號(hào)，和第一步類(lèi)似，找到最接近殘差向量的原子，保留下來(lái)；第三步，調(diào)整已選向量的系數(shù)，使得

最接近X，重復(fù)第二步。松弛算法——BasisPursuit，將L0問(wèn)題轉(zhuǎn)化為L(zhǎng)1問(wèn)題，解決的方法有很多，比如內(nèi)點(diǎn)法、迭代收縮法等。事實(shí)上，它可以化成一個(gè)線(xiàn)性規(guī)劃的問(wèn)題，用MATLAB很容易解。6HowtofindthedictionaryD?尋找字典的過(guò)程稱(chēng)為字典學(xué)習(xí)。字典學(xué)習(xí)的一個(gè)假設(shè)是字典對(duì)于指定信號(hào)具有稀疏表示。因此，選擇字典的原則就是能夠稀疏地表達(dá)信號(hào)。兩種方法來(lái)設(shè)計(jì)字典:從已知的變換基中選取，比如DCT、小波基等，這種方法很通用，但是不能自適應(yīng)于信號(hào)。學(xué)習(xí)字典，即通過(guò)訓(xùn)練和學(xué)習(xí)大量的與目標(biāo)數(shù)據(jù)相似的數(shù)據(jù)來(lái)獲得。這里，我們介紹一種叫K-SVD的方法。78假設(shè)現(xiàn)在有原始信號(hào)矩陣，

該矩陣的每一行表示一個(gè)信號(hào)或者一張圖片，D矩陣是字典矩陣，右下方是稀疏解矩陣S，紅色的點(diǎn)表示非零項(xiàng)。HowtofindthedictionaryD?——K-SVDHowtofindthedictionaryD?——K-SVDStep2:

SparseCoding.用松弛或者貪婪法進(jìn)行稀疏編碼，使得9Step1:Initialize.在

矩陣中隨機(jī)挑選一些行向量(一些原圖），填滿(mǎn)矩陣D，并歸一化每一列。得到稀疏表示構(gòu)成稀疏矩陣S的第i行。SHowtofindthedictionaryD?——K-SVD10

Step4：StoppingRule.如果則停止迭代。SWhataresparserepresentations/approximationsgoodfor?稀疏性是DFT、WT和SVD分解得以廣泛利用的原因之一，這些變換的目的都是為了反映信號(hào)的確定性結(jié)構(gòu)，并用緊湊的或稀疏的表示來(lái)表征這些結(jié)構(gòu)；稀疏表示的思想為模式分類(lèi)方法建立了基礎(chǔ)，比如SVM和RVM，其中稀疏性直接與估計(jì)函數(shù)（estimator）的學(xué)習(xí)能力有關(guān)。稀疏表示解決的問(wèn)題主要集中在：圖像去噪（Denoise），代表性paper：ImageDenoiseViaSparseandRedundantRepresentationsOverLearnedDictionaries(EladM.andAharonM.IEEETrans.onImageProcessing,Dec,2006);ImageSequenceDenoisingViaSparseandRedundantRepresentations(ProtterM.andEladM.IEEETrans.onImageProcessing,Jan,2009)；超分辨率重建（Super-ResolutionORScale-Up），代表性paper：ImageSuper-ResolutionviaSparseRepresentation（JianchaoYang,JohnWright,ThomasHuang,andYiMa，IEEETransactionsonImageProcessing,Nov,2010）,AShrinkageLearningApproachforSingleImageSuper-ResolutionwithOvercompleteRepresentations(A.Adler,Y.Hel-Or,andM.Elad,ECCV,Sep,2010);另外還有inpaintting，deblurring，compression等等..更多應(yīng)用參考EladM的書(shū)。11OutputOriginalInputTrainingpatches12Whataresparserepresentations/approximationsgoodfor?去噪：超分辨率：Whatare