壓縮感知算法在數(shù)字圖像處理中的研究與應(yīng)用

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

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

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

1 引言

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

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

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

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

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

3 研究內(nèi)容

結(jié)合本項目的主要研究內(nèi)容以及綜合考慮項目多研究領(lǐng)域的交叉性質(zhì)，將研究內(nèi)容分為以下幾個部分：

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

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

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

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

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

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

3.2 快速、準(zhǔn)確、魯棒性好的CS重建算法研究

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

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

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

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

該算法通過構(gòu)造目標(biāo)函數(shù)并求其梯度的極小值代替求方程組解，該算法的步驟如下：

重構(gòu)算法輸入：觀測矩陣Ф，觀測結(jié)果y，稀疏度k。

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

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

3.3 CS觀測矩陣構(gòu)造

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

⑴自適應(yīng)隨機觀測矩陣設(shè)計。目前觀測矩陣的設(shè)計主要包括隨機觀測矩陣、確定性觀測矩陣和自適應(yīng)觀測矩陣三種。自適應(yīng)隨機觀測矩陣是最近新興起的CS觀測矩陣構(gòu)造方法，可以同時降低計算復(fù)雜度和相關(guān)性。

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

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

5 總結(jié)與展望

壓縮感知理論的提出，將K-SVD字典和稀疏編碼的思想與壓縮感知相結(jié)合并運用于圖像壓縮編碼中以代替?zhèn)鹘y(tǒng)的圖像編碼方法是本文的中心內(nèi)容。然而，由于壓縮感知理論是一個新穎的理論，其相關(guān)應(yīng)用還不成熟，因此取代JPEG及JPEG2000算法在圖像壓縮編碼領(lǐng)域的地位還有很長的路要走[10]。

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

[參考文獻]

[1]鄒偉.壓縮感知在圖像處理中的應(yīng)用研究[D].上海交通大學(xué)碩士學(xué)位論文，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]馮鑫.多尺度分析與壓縮感知理論在圖像處理中的應(yīng)用研究[D].上蘭州理工大學(xué)博士學(xué)位論文，2012.

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

[9]崔佳鵬.基于壓縮感知的圖像壓縮技術(shù)研究與實現(xiàn)[D].哈爾濱工業(yè)大學(xué)工程碩士學(xué)位論文，2013.

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