壓縮感知算法在數字圖像處理中的研究與應用

邱中杰 杜宏博 王雯 馬洪 李重華

摘 要：隨著壓縮感知理論研究工作的深入，壓縮感知在信號和圖像處理領域已引起眾多研究者的關注。理論已經證明自然圖像本身具有稀疏的表示特性，符合人類所接觸的很多信號和圖像的處理。近年來，壓縮感知理論已被大量應用到信號和圖像處理的各個領域[1]。如何構造一個適合不同模態圖像的變換字典，并設計相應的快速而有效的稀疏分解算法是本項目中稀疏分解矩陣建立研究的重要內容；提出快速、準確、魯棒性好的CS重建算法也是本項目研究的主要內容之一。

關鍵詞：壓縮感知；稀疏表示；變化字典；魯棒性

1 引言

目前，圖像壓縮技術可主要分為兩大類，即有損壓縮和無損壓縮。無損壓縮雖然嚴格地保證了圖像質量，但是壓縮率較低，僅為2～3倍，無法達到實時傳輸和節省存儲空間的要求。為了提高壓縮率，人們開始嘗試有損壓縮算法，主要包括區域壓縮算法[2]、JPEG壓縮算法[3]、基于小波變換的壓縮算法[4]、面向對象的區域運動補償算法[5]等。這些算法雖然在很大程度上壓縮了圖像的冗余信息，但是其壓縮處理方法均基于以下幾個步驟進行：即首先對可壓縮信號進行高速采樣、然后對采樣數據進行壓縮，最后把壓縮過的信號進行解壓縮以便恢復原始信號。眾所周知，傳統信號采樣的準則是Nyquist采樣定理，因此，在影像設備將模擬信號轉成數字圖像的過程中經常需要較高的采樣率，而為了便于傳輸，又要對獲得的大量信息進行數據壓縮，只保留一部分必要信息。這在很大程度上浪費掉了采集、存儲和計算資源。

2 壓縮感知的研究背景與理論簡介

壓縮感知（compressive sensing，CS）技術自2006年誕生以來，就以其在圖像壓縮和傳輸領域中表現出來的獨特優勢，迅速引起國內外學者的高度重視，被美國科技評論評為2007年度十大科技進展。CS的核心思想是將信號采樣與壓縮融合在一起，即在采樣的同時實現信號的壓縮，以盡量地降低信號的冗余信息。CS突破了傳統的Nyquist采樣定理，只要信號是可壓縮的或稀疏的，CS就可以以極低的采樣率采樣，然后又可以利用測量值精準地重構原始信號。目前，CS的理論研究主要集中在信號的稀疏分解、信號觀測矩陣建立和信號重構三個方面[6]。盡管其理論研究仍出于起步階段，但已成為信息論、圖像處理、模式識別、醫療成像、地址勘探等領域的一大研究熱點。在麻省理工學院、斯坦福大學等許多知名大學已專門成立CS課題組。國內關于CS的研究基本同步進行，不過研究成果較國外少些。

隨著稀疏重構和新興采樣定理研究的不斷發展，很多學者發現，當測量數據不完全時，甚至只有很小一部分測量數據時，利用該方法仍可以很好重構原圖像。例如圖1-1重現了Candes等人在核磁共振成像（Magnetic Resonance Imaging，MRI）研究中的發現。其中圖1-1（a）為原圖像，MRI中的測量數據可以理解為原圖像的Fourier變換，一次測量可以理解為Fourier域中的某個角度下的“切片”，即如圖1-1（b）圖中的一條直線，傳統的方法需要大量的測量，即密集的直線，才可以高質量地重構圖像。當只有18個角度的測量數據時（如圖1-1（b）所示，只占整個頻域的7.71%），傳統的后向投影（Back Projection，BP）方法重構的圖像如圖1-1（c）所示，如果在重構過程中引入稀疏性約束，則可以高精度地重構原圖像，如圖1-1（d）所示[7]。

這個發現最終誘使了壓縮感知理論的產生。其后，Candes、Tao與Romberg等人，初步建立了壓縮感知的理論模型[57]。壓縮成像主要分為兩個組成部分：數據的獲取過程以及圖像的重構過程。其中，前半部分在理論上需研究使得“稀疏重構”能夠恢復原信號的測量矩陣性質，即重構條件；后半部分與稀疏重構的研究一脈相承，但是需要特別考慮二維圖像所涉及的大規模數據情況下的保精度快速計算問題。

3 研究內容

結合本項目的主要研究內容以及綜合考慮項目多研究領域的交叉性質，將研究內容分為以下幾個部分：

3.1 圖像的稀疏分解矩陣建立

CS理論的提出是建立的信號的稀疏性基礎上的，信號的稀疏性直接影響觀測個數進而影響圖像的壓縮率和重構的準確性，因此，圖像稀疏分解矩陣的選取非常重要。

信號的稀疏性是指信號中的元素絕大多數為零元素，只有少數是非零的，稀疏性是進行壓縮傳感的前提條件。信號在某一適合的基下均能稀疏表示。例如圖2-1（a）中的圖像和其小波變換圖2-1（b）。由兩幅圖像可看出，原始圖像中幾乎所有像素均為非零值，但是當對其進行小波變換時，得到的小波系數卻提供了一種簡明的表示方法：大多數小波系數的值都很小，只有很少的小波系數其值較大，這些大的小波系數攜帶了圖像絕大多數的信息。

用數學語言可描述為，對于一個N維向量x∈R（如圖1中有n個像素）可由一個正交基（如小波基）Ψ=[Ψ1，Ψ2，…Ψn]展開為如下式：

其中αi是x的系數序列，αi=〈x，Ψ1〉。上式可很方便的將x表示為Ψ（其中Ψ為N×N）的矩陣，Ψ1，Ψ2，…Ψn是它的列）。這樣信號的稀疏性的含義就很清楚了：當一個信號可以稀疏表示時，人們可以丟棄小的系數，并感覺不到信息的丟失。在形式上可表示為，xs（t）是由展開式（1-1）中αi只保留S個最大值得到的。定義xs（t）=Ψαs，其中αs為xi中除了S個最大值，其它均設為0的系數向量。由于這個向量除了少數幾個元素均為0，因此它是嚴格稀疏的；這種只有S個非零元素的對象稱為我們稱之為S-稀疏。如果是稀疏的或可壓縮的，即（αi）按幅值排列迅速遞減，則α與αs近似；又由于Ψ是正交基，我們有||x-xs||12=||α-αs||12，那么||x-xs||12的差很小。通俗的表述為，人們可“扔掉”大部分的稀疏而不會丟失很多信息。圖2-1（c）給出這種例子，圖像在扔掉97.5%的系數后，仍很難察覺到信息的丟失。

圖2-1（a）原始圖像的像素值范圍為[0，255]；（b）圖像的小波變換系數，只有少數小波系數攜帶有絕大多數信號的能量，這種圖像具有高可壓縮性；（c）僅用25000個較大的小波系數對圖像進行重構的結果（圖像像素范圍為[0，255]），它與原始圖像的差別很難覺察到。目前常用的稀疏變換基有離散小波變換（DWT），離散余弦變換（DCT），過完備原子分解等。當目標信號在標準正交基構成的空間中不具有稀疏性時，可采用過完備原子法進行信號的稀疏化表達[8]。

3.2 快速、準確、魯棒性好的CS重建算法研究

信號重構算法是壓縮感知理論關鍵的一部分，對于壓縮信號的精確重構以及采樣準確性的驗證均具有重要的意義。現有的CS重建算法有很多種，例如貪婪追蹤算法、松弛算法、范數優化算法、組合算法及最小變分算法等。每種重建算法都有其固有的缺點，無法同時兼顧算法復雜度、計算時間、觀測數目、重構質量等多個目標。以下例舉正交匹配追蹤算法與梯度追蹤算法。

（1）正交匹配追蹤算法（OMP）。正交匹配追蹤算法時常用的恢復算法，是屬于貪婪算法一類的，來源于匹配追蹤算法（MP）。MP是一種迭代算法，每次迭代的過程中選取觀測矩陣中與信號殘差最相關的列向量進行逼近，反復迭代計算殘差，當殘差值小于某一預設的數值或者達到最大迭代次數是停止，所得到的重構信號的迭代結果即為重構得到的原始信號。

OMP是MP的改進，差距體現在OMP算法過程中每次迭代計算后的殘差值都是和觀測矩陣的所選的列向量是正交的，重構信號則通過觀測信號和所選列向量求偽逆的結果求得。因為在迭代過程中，計算的殘差均與所選的列向量正交，使得每次都進行最優的迭代運算，使得重構算法達的迭代次數減少、重構信號跟接近于原始信號。

（2）梯度追蹤算法。正交匹配追蹤算法中需要進行求偽逆預算，一般的情況下偽逆運算采用QR分解或Cholesky分解實現，運算量很大，為了提升運算速度，Blumensath等人提出了梯度追蹤算法（GP）。

該算法通過構造目標函數并求其梯度的極小值代替求方程組解，該算法的步驟如下：

重構算法輸入：觀測矩陣Ф，觀測結果y，稀疏度k。

重構算法的輸出：逼近與原始信號x的稀疏解向量 。

重構算法初始化：殘差r0=y，所選列向量的索引集Λ= ，迭代次數t=1， =0。

3.3 CS觀測矩陣構造

壓縮傳感理論具有稀疏或可壓縮的特性，經過非相干的隨機投影可直接獲取的系數雖然不多，卻包含信號中的絕大部分信息，繼而實現采樣與壓縮的同步。因此，構建合適的投影矩陣也即觀測矩陣是本項目的主要研究內容。

⑴自適應隨機觀測矩陣設計。目前觀測矩陣的設計主要包括隨機觀測矩陣、確定性觀測矩陣和自適應觀測矩陣三種。自適應隨機觀測矩陣是最近新興起的CS觀測矩陣構造方法，可以同時降低計算復雜度和相關性。

⑵基于多觀測向量和稀疏貝葉斯學習的CS重建算法研究。大多數現有的CS重建算法都是針對一維信號進行處理，這些算法可以看成是基于單觀測向量的重建算法。在處理圖像信號時，如果能直接對圖像信號進行處理，將提高算法的計算效率，同時也將克服將圖像信號轉換成一維信號處理對重構圖像質量所造成的影響。相關研究表明，基于稀疏貝葉斯學習（SBL）方法能夠在重構過程中獲得全局最優解，因此本項目擬將SBL算法應用到CS圖像重構中。同時為了克服傳統算法針對單觀測向量模型處理圖像信號所出現的問題，將由圖像信號觀測得到的觀測矩陣的每一列看作是一個觀測向量，則觀測矩陣被看成是由多觀測向量（MMV）組成的矩陣。本項目結合MMV和SBL研究一種有效的CS重建算法，以縮短圖像重建的時間并提高圖像重建質量。

⑶利用自適應基追蹤去噪方法重構CS圖像。基于CS對含噪聲的圖像進行采樣重構，其誤差主要來源于兩個方面。第一是無噪聲情況下CS壓縮重構本身帶來的噪聲。第二與信號本身含有的噪聲大小有關。本項目將兩類情況綜合起來，把CS采樣和自適應基追蹤去噪運用到含噪聲的圖像壓縮與重構中，既能減少存儲、傳輸所占用的資源，又能在重構過程實現圖像增強，保證接收端能夠獲得高質量的圖像。

5 總結與展望

壓縮感知理論的提出，將K-SVD字典和稀疏編碼的思想與壓縮感知相結合并運用于圖像壓縮編碼中以代替傳統的圖像編碼方法是本文的中心內容。然而，由于壓縮感知理論是一個新穎的理論，其相關應用還不成熟，因此取代JPEG及JPEG2000算法在圖像壓縮編碼領域的地位還有很長的路要走[10]。

本文在壓縮感知的理論基礎上，致力研究圖像易于存儲和計算的CS觀測矩陣，盡可能地降低重建所需要的觀測數目，提高圖像壓縮率；研究CS圖像重構算法，降低其計算復雜度，同時縮短重構時間并提高圖像的重構質量。同時，通過大量實驗，觀察不同參數下圖像的重構質量和壓縮比，得到參數控制結果的規律，并經過統計和總結，得到最優的參數值，使得圖像在高壓縮比的基礎上同時擁有較好的重構質量。在編程實現的基礎上驗證了算法的可行性，然而實踐是檢驗真理的唯一標準，這種算法是否能夠真正投入到實際應用中，還需要進一步經過實踐的考驗。

[參考文獻]

[1]鄒偉.壓縮感知在圖像處理中的應用研究[D].上海交通大學碩士學位論文，2012.

[2]DEMOS G.High quality wide-range multi-layer image compression coding system[J].Google Patents，2011.

[3]SINGH P，SINGH P，SHARMA R K.JPEG image compression based on Biorthogonal，Coiflets and Daubechies Wavelet Families[J].Int J Comput Appl，2011，13（1）：1–7.

[4]TALUKDER K H，HARADA K.Haar wavelet based approach for image compression and quality assessment of compressed image[J].arXiv preprint arXiv：1010.4084，2010.

[5]DING J-J，LIN P-Y，HUANG J-D，et al.Morphology-based shape adaptive compression[G].Advances in Multimedia Modeling. Springer，2011：168–176.

[6]CAND?S E J，WAKIN M B.An introduction to compressive sampling[J].Signal Processing Magazine，IEEE，IEEE，2008，25（2）： 21–30.

[7]馮鑫.多尺度分析與壓縮感知理論在圖像處理中的應用研究[D].上蘭州理工大學博士學位論文，2012.

[8]丁偉.基于壓縮感知的水下圖像處理[D].中國海洋大學碩士學位論文，2013.

[9]崔佳鵬.基于壓縮感知的圖像壓縮技術研究與實現[D].哈爾濱工業大學工程碩士學位論文，2013.

[10]郎彥昆.壓縮感知技術及其在數字圖像壓縮編碼中的應用研究[D].北方工業大學碩士學位論文，2013.