基本介紹
- 中文名：稀疏表示
- 外文名：Sparse Representation
- 學科：計算機、通信
- 提出者：Mallat
- 研究熱點：模型的近似表示、字典學習算法
- 本質目的： 代價或成本儘可能小
- 實際套用：圖像處理、音頻處理、模式識別等
簡介,信號稀疏表示,稀疏表示模型,模型求解算法,字典學習算法,信號稀疏表示套用,稀疏表示方法局限與待解決問題,套用,
簡介
數學變換會追求所謂稀疏表示(sparse representation），即如何通過最小數量的係數儘可能更多的描述信號的能量。不同類型的信號，其在不同變換下係數的分布會不同。
信號稀疏表示的目的就是在給定的超完備字典中用儘可能少的原子來表示信號，可以獲得信號更為簡潔的表示方式，從而使我們更容易地獲取信號中所蘊含的信息，更方便進一步對信號進行加工處理，如壓縮、編碼等。信號稀疏表示方向的研究熱點主要集中在稀疏分解算法、超完備原子字典、和稀疏表示的套用等方面。
在稀疏表示理論未提出前，正交字典和雙正交字典因為其數學模型簡單而被廣泛的套用，然而他們有一個明顯的缺點就是自適應能力差，不能靈活全面地表示信號，1993年，Mallat基於小波分析提出了信號可以用一個超完備字典進行表示，從而開啟了稀疏表示的先河，經研究發現，信號經稀疏表示後，越稀疏則信號重建後的精度就越高，而且稀疏表示可以根據信號的自身特點自適應的選擇合適的超完備字典。對信號稀疏表示的目的就是尋找一個自適應字典使得信號的表達最稀疏。
稀疏分解算法首先是由Mallat提出的，也就是眾所周知的匹配追蹤算法（Matching Pursuit,MP）算法，該算法是一個疊代算法，簡單且易於實現，因此得到了廣泛的套用。隨後，Pati等人基於MP算法，提出了正交匹配追蹤算法（Orthogonal Matching Pursuit,OMP），OMP算法相較於MP算法，收斂速度更快。在以後的研究中，為了改進OMP算法，學者也提出了各種不同的其它算法，例如：壓縮採樣匹配追蹤（Conpressive Sampling Matching Pursuit,CoSaMP）算法、正則化正交匹配追蹤（Regularized Orthogonal Matching Pursuit,ROMP）算法、分段式正交匹配追蹤（Stagewise OMP,StOMP）算法、子空間追蹤（Subspace Pursuit,SP）算法等等。
信號稀疏表示的兩大主要任務就是字典的生成和信號的稀疏分解，對於字典的選擇，一般有分析字典和學習字典兩大類。常用的分析字典有小波字典、超完備DCT字典和曲波字典等，用分析字典進行信號的稀疏表示時，雖然簡單易實現，但信號的表達形式單一且不具備自適應性；反之，學習字典的自適應能力強，能夠更好的適應不同的圖像數據，在目前的研究中，常用的學習字典的方法包括：Engan於1999年提出的最優方向（Method Of Optimal Directions,MOD）算法，該算法是學習字典的鼻祖，它的字典更新方式簡單，但與此同時，它的收斂速度很慢，在該算法的基礎上，一些研究人員同時還提出了一些其它的字典學習算法，如FOCUSS字典學習算法，廣義PCA（Generalized PCA）算法等等，Micheal Elad也於2006年提出了基於超完備字典稀疏分解的K-SVD算法，該算法相較於MOD算法，收斂速度有了很大的提高，但是隨著噪聲的逐漸加大，使用該算法進行去噪後的圖像因紋理細節的丟失會產生模糊的效果。Mairal於2010年提出了一種online字典學習算法，該算法速度較快且適用於一些特殊的信號處理，例如視頻信號，語音信號等等。
信號稀疏表示
稀疏表示模型
現有稀疏表示模型一般形式如下：
X=argmin||y-Dx||k+λ||x||
其中，y 為觀測數據， D 為字典， x 為待估稀疏向量， λ 為正則參數， k （1≤ k<2 ）為稀疏度量。其中，
λ 與 k 未知， 需要預先確定（ 雖然通常取 k =1 ， 但 k <1 時模型更加靈活）。對該模型的理論研究， 主要包括模型解與 l0 範數最小化解的逼近程度、 稀疏表示模型解的唯一性與穩定性等。但是， 在一些具體的套用如圖像增強與測控資源最佳化配置中， 稀疏度量並不是唯一且最重要的指標。
λ 與 k 未知， 需要預先確定（ 雖然通常取 k =1 ， 但 k <1 時模型更加靈活）。對該模型的理論研究， 主要包括模型解與 l0 範數最小化解的逼近程度、 稀疏表示模型解的唯一性與穩定性等。但是， 在一些具體的套用如圖像增強與測控資源最佳化配置中， 稀疏度量並不是唯一且最重要的指標。
模型求解算法
上述模型的求解劃分為基於數學模型的求解算法， 如基追蹤、 F O C U S S 、S h r i n k a g e 等， 以及不考慮數學模型的求解算法， 如匹配追蹤算法族等。但現有的算法多存在一個待解決問題， 即需預先確定正則參數 λ 與表征稀疏度的參數 k ， 然後進行求解。若解未達到要求， 則重新調整兩個參數的值， 直至得到滿意解。這使得模型在套用中不能達到自動化的程度，限制了稀疏表示方法的套用。
字典學習算法
最初在稀疏表示研究領域， 一般假定字典已知， 僅求解未知稀疏向量。現已有學者研究字典的選擇與學習方法用於字典未知的情況。現有的字典學習方法可分為兩種類型： 基於訓練樣本與基於參數化字典 。其中， 後者較為困難， 需深入分析所研究的信號的特點與描述方法。對字典學習的過程一般採用兩步法， 與稀疏表示模型求解相結合。
信號稀疏表示套用
目前， 稀疏表示的套用範圍基本為自然信號形成的圖像、音頻以及文本等， 對於非自然信號或數據的套用尚未有文獻涉及。在套用方面， 可大體劃分為兩類：
基於重構的套用
此類應 用 有 圖 像 去 噪、 壓 縮 與 超 分 辨 、S A R 成像 、 缺失圖像重構 以及音頻修復 等。這些套用主要將目標的特徵用若干參數來表示， 這些特徵構成稀疏向量， 利用稀疏表示方法得到稀疏向量， 根據數學模型進行數據或圖像重構。在這些套用中， 觀測數據一般含有噪聲。
基於重構的套用
此類應 用 有 圖 像 去 噪、 壓 縮 與 超 分 辨 、S A R 成像 、 缺失圖像重構 以及音頻修復 等。這些套用主要將目標的特徵用若干參數來表示， 這些特徵構成稀疏向量， 利用稀疏表示方法得到稀疏向量， 根據數學模型進行數據或圖像重構。在這些套用中， 觀測數據一般含有噪聲。
基於分類的套用
這類套用的本質是模式識別 ， 將表征對象主要的或本質的特徵構造稀疏向量， 這些特徵具有類間的強區分性。利用稀疏表示方法得到這些特徵的值， 並根據稀疏向量與某類標準值的距離， 或稀疏向量間的距離判別完成模式識別或分類過程， 例如盲源分離、 音樂表示與分類、 人臉識別 、文本檢測。
稀疏表示方法局限與待解決問題
信號稀疏表示雖然得到廣泛研究， 但尚存在很多問題需要繼續深入挖掘。主要包括：
1. 構造更為靈活的稀疏表示模型在現有稀疏表示模型中， 存在一個目標函式與約束函式其中， 目標函式一般為在假定觀測信號具有線性模型形式以及含有高斯白噪聲情況下使得噪聲的能量最小； 約束函式一般指稀疏約束項。這種目標函式一方面將稀疏分量同等對待； 另一方面忽視了不同套用中還有其它目標的存在， 因為如
果單單從表示的角度來看， 並不一定要求最稀疏的解是唯一的或最稀疏的解並不是最理想的。例如， 在圖像重構的過程中， 僅僅考慮稀疏解， 得到的最稀疏解有可能會造成丟失目標的現象發生。因此， 需要構造多目標以及變正則參數的稀疏表示模型， 以滿足更多套用問題的特點與需要。
果單單從表示的角度來看， 並不一定要求最稀疏的解是唯一的或最稀疏的解並不是最理想的。例如， 在圖像重構的過程中， 僅僅考慮稀疏解， 得到的最稀疏解有可能會造成丟失目標的現象發生。因此， 需要構造多目標以及變正則參數的稀疏表示模型， 以滿足更多套用問題的特點與需要。
2. 確定模型超參數的取值在上述稀疏表示模型中， 主要待估參數為稀疏向量 x，但模型中還存在兩個超參數： 正則參數 λ 以及表征稀疏程度的參數 k 。在現有文獻中， 大多利用人工預先確定的方法來對兩個超參數賦值。確定其值後， 進行求解， 然後將求解結果與目標需求進行比較。如果不滿足要求， 再調整參數。這必然造成了求解過程的非適應性或非自動化， 也限制了稀疏表示方法在一些自動化程度要求較高的領域的套用。為此需研究稀疏表示模型的自適應求解問題， 構造超參數與觀測信號和稀疏向量之間的函式關係。
3. 降低稀疏表示模型求解的不確定性信號稀疏表示理論研究的最終目的是將其套用於各領域， 但現有的模型在實際套用中存在處理性能的不確定性問題： 一方面， 模型中的目標與實際問題處理目標沒有形成閉合
環； 另一方面， 稀疏表示模型求解通常從抽象的數學角度進行設計， 一般需要藉助於疊代最佳化方法， 疊代過程一般以相鄰兩次估計值的l2範數滿足一定要求作為收斂準則， 這意味著收斂準則並沒有與套用問題的需求聯繫起來， 造成了處理性能的不確定性。例如， 在圖像去噪或高解析度重構處理中， 在求解稀疏表示模型後， 需要利用人眼視覺主觀觀察以及其它若干客觀定量指標來評估處理性能， 而這些評估指標在稀疏表示模型中並未得到體現。
環； 另一方面， 稀疏表示模型求解通常從抽象的數學角度進行設計， 一般需要藉助於疊代最佳化方法， 疊代過程一般以相鄰兩次估計值的l2範數滿足一定要求作為收斂準則， 這意味著收斂準則並沒有與套用問題的需求聯繫起來， 造成了處理性能的不確定性。例如， 在圖像去噪或高解析度重構處理中， 在求解稀疏表示模型後， 需要利用人眼視覺主觀觀察以及其它若干客觀定量指標來評估處理性能， 而這些評估指標在稀疏表示模型中並未得到體現。
套用
稀疏表示研究的熱點包括模型的近似表示、模型解的唯一性與穩定性、稀 疏 表 示 的 性 能 分 析、模 型 求 解 算法 、字典學習算法、稀疏分解算法、超完備原子字典、 稀疏表示的具體套用以及緊密聯繫的壓縮感測 等方面。其中，具體的套用包括： 圖像處理（ 如壓縮、 增強與超分辨） 、音頻處理（ 如盲源分離） 與模式識別（ 如人臉與手勢識別） 等。從實用角度看，具有針對性的靈活模型、 計算速度、 自適應以及高性能表示結果是稀疏表示方法在套用領域發揮其優勢的關鍵問題。
以下是稀疏表示在圖像處理領域的套用的幾個方面：
圖像去噪
傳統的去噪方法往往假設含噪圖像的有用信息處在低頻區域，而噪聲信息處在高頻區域，從而基於中值濾波、Wiener 濾波、小波變換等方法實現圖像去噪，而實際上這種假設並不總是成立的。基於圖像的稀疏表示，近幾年來研究者們提出了基於過完備字典稀疏表示的圖像去噪模型，其基本原理是將圖像的稀疏表示作為有用信息，將逼近殘差視為噪聲。利用 K-SVD 算法求得基於稀疏和冗餘的訓練字典，同時針對 K-SVD 算法僅適合處理小規模數據的局限，通過定義全局最優來強制圖像局部塊的稀疏性。文獻[28]提出了稀疏性正則化的圖像泊松去噪算法，該算法採用 log 的泊松似然函式作為保真項，用圖像在冗餘字典下稀疏性約束作為正則項，從而取得更好的去噪效果。
人臉識別
近年來，稀疏表示廣泛套用於人臉識別，並取得了很好的識別效果。Wright 等人認為：①同類樣本處於同一個線性子空間，任一測試樣本均可以用來自於該類的訓練樣本進行線性表示；②用所有的訓練樣本構成字典，則測試樣本在該字典上的表示是稀疏的，同時該稀疏係數包含了樣本的類別信息。基於此，Wright 等提出了基於稀疏表示的人臉識別框架，即首先基於人臉庫構造過完備字典，然後計算待測圖像在該字典上的稀疏係數，再根據重構誤差判別圖像身份。該算法對特徵選擇不敏感，有很強的抗噪聲能力，並且具有較好的遮擋處理功能，從而在人臉識別領域得到了廣泛關注。提出加權稀疏編碼算法，該方法在解決人臉遮擋、光照、表情等方面取得了較好的效果。為了解決小維度，小樣本的人臉識別問題，提出了基於稀疏表示和奇異值分解的人臉識別算法，實驗表明該方法在 ORL 人臉庫上取得了較好的效果。
目標跟蹤
近年來，稀疏表示在目標跟蹤領域也得到的廣泛套用。針對紅外圖像序列中目標與背景對比度低、灰度特徵易受噪聲影響等問題，提出了一種基於稀疏表示模型的紅外目標跟蹤算法。提出了一個新的基於稀疏表示的目標跟蹤方法，通過L1 範數最小化求解，實驗結果表明，該方法比現有的基於 L1 範數最小化的跟蹤方法性能更穩定、計算效率更高。為了有效解決跟蹤過程中的目標遮擋問題，提出了一種基於局部稀疏表示模型的跟蹤方法。實驗結果表明，該方法比各種流行跟蹤方法穩定可靠且具有良好的抗遮擋性，並對海上紅外目標跟蹤取得良好效果。
圖像修復隨著稀疏表示研究的深入，稀疏表示在圖像修復領域也得到了廣泛套用[35-37]。為了確保修復時填充洞和周圍之間的視覺合理性與一致性，Shen 等人提出直接在待處理圖像完整區域採樣，構造冗餘字典，然後通過依次計算洞邊界不完整的塊的稀疏表示進行恢復。該算法在處理大洞和保留圖像細節方面具有較好的能力。針對現有圖像修複方法中待填充塊在全局搜尋與之最匹配塊的計算複雜度高、結構連貫性和紋理清晰性不佳的缺點，文獻[36]提出了基於塊結構稀疏度的自適應圖像修復算法。針對圖像結構信息缺損較大的圖像，提出利用結構約束和樣本稀疏表示實現圖像修復，該方法既能較好的修復圖像邊緣結構，又能保持結構的整體平滑性。
壓縮感知
為了有效重構原信號，傳統方式下需要基於奈奎斯特採樣定理實現對信號的採樣。近年來，隨著稀疏表示的興起為重構原信號提出了一種新的理論-壓縮感知。
壓縮感知理論突破了奈奎斯特採樣頻率的下限，它以信號的稀疏性（或可壓縮性）作為前提，將傳統方式下對信號的採樣和壓縮兩個過程融為一個過程，直接獲取稀疏信號，然後用一個與變換矩陣無關的觀測矩陣對變換係數向量進行變換，最後通過求解一個最佳化問題重構原信號。目前，國內外研究人員在該領域進行了深入研究，並提出了有效的壓縮感知理論與方法。
