沈燕飛，朱珍民，張勇東，李錦濤

(1.中國(guó)科學(xué)院計(jì)算技術(shù)研究所，北京 100190； 2.北京市移動(dòng)計(jì)算與新型終端重點(diǎn)實(shí)驗(yàn)室,北京 100190)

?

基于秩極小化的壓縮感知圖像恢復(fù)算法

沈燕飛1，2，朱珍民1，張勇東1，李錦濤1

(1.中國(guó)科學(xué)院計(jì)算技術(shù)研究所，北京 100190； 2.北京市移動(dòng)計(jì)算與新型終端重點(diǎn)實(shí)驗(yàn)室,北京 100190)

摘要：本文將壓縮感知圖像恢復(fù)問(wèn)題作為低秩矩陣恢復(fù)問(wèn)題來(lái)進(jìn)行研究.為了構(gòu)建這樣的低秩矩陣，我們采樣非局部相似度模型，將相似圖像塊作為列向量構(gòu)建一個(gè)二維相似塊矩陣.由于列向量間的強(qiáng)相關(guān)性，因此該矩陣具有低秩屬性.然后以壓縮感知測(cè)量作為約束條件對(duì)這樣的二維相似塊矩陣進(jìn)行低秩矩陣恢復(fù)求解.在算法求解的過(guò)程中，使用增廣拉格朗日方法將受限優(yōu)化問(wèn)題轉(zhuǎn)換為非受限優(yōu)化問(wèn)題，同時(shí)為了減少計(jì)算復(fù)雜度，使用基于泰勒展開(kāi)的線性化技術(shù)來(lái)加速算法求解.實(shí)驗(yàn)表明該算法的收斂率、圖像恢復(fù)性能均優(yōu)于目前主流壓縮感知圖像恢復(fù)算法.

關(guān)鍵詞:壓縮感知；秩最小化；圖像恢復(fù)；非局部相似

1引言

根據(jù)經(jīng)典香農(nóng)-那奎斯特采樣定理，為了精確重建原始信號(hào)，信號(hào)的采樣頻率至少是被采樣信號(hào)帶寬的兩倍，隨著信號(hào)帶寬的逐步提高，例如高分辨率醫(yī)學(xué)圖像和衛(wèi)星云圖等，對(duì)信號(hào)的采樣速率和數(shù)據(jù)存儲(chǔ)提出了越來(lái)越高的要求.然而在實(shí)際應(yīng)用中，為了減少數(shù)據(jù)的存儲(chǔ)、處理和傳輸成本，常常采用有損的方法對(duì)采集信號(hào)進(jìn)行壓縮處理，丟棄大量的冗余信息.這種“先采樣后壓縮”的信號(hào)處理模式不僅浪費(fèi)了大量的數(shù)據(jù)傳輸帶寬，而且也大大增加了信號(hào)采集設(shè)備的設(shè)計(jì)難度和成本.另外，在一些特殊應(yīng)用中，例如：醫(yī)學(xué)圖像、雷達(dá)信號(hào)、地震勘測(cè)等應(yīng)用，由于客觀條件的限制，信號(hào)采集難以滿足香農(nóng)-那奎斯特采樣定理中規(guī)定的最低頻率要求.為了解決這些問(wèn)題，美國(guó)科學(xué)院院士D.Donoho，斯坦福大學(xué)的E.Candes教授和華裔科學(xué)家陶哲軒等提出了壓縮感知理論[1,2].該理論的核心思想是：給定一個(gè)信號(hào)，如果信號(hào)本身或者信號(hào)在某個(gè)變換域上具有稀疏性，則可以利用一個(gè)隨機(jī)測(cè)量矩陣對(duì)信號(hào)進(jìn)行降維測(cè)量，然后通過(guò)對(duì)測(cè)量數(shù)據(jù)進(jìn)行非線性化優(yōu)化求解，就可以完成對(duì)原始信號(hào)的精確重建.該理論自2006年提出以來(lái)，吸引了相關(guān)領(lǐng)域?qū)W者的廣泛關(guān)注和研究熱情.

壓縮感知理論的數(shù)學(xué)模型表示如下：對(duì)于一個(gè)長(zhǎng)度為N的一維信號(hào)X∈RN，如果X中只有K(K?N)個(gè)非零元素，則稱X是稀疏的，其稀疏度為K/N.壓縮感知的測(cè)量過(guò)程就是將稀疏信號(hào)X在隨機(jī)測(cè)量矩陣Φ(Φ∈RM×N,M?N)上進(jìn)行投影的過(guò)程，如式(1)所示，得到一個(gè)比原始信號(hào)X長(zhǎng)度小很多的測(cè)量值Y∈RM.

Y=ΦX

(1)

由于式(1)是一個(gè)欠定方程組，屬于病態(tài)求解問(wèn)題，因此無(wú)法直接利用測(cè)量值Y對(duì)原始信號(hào)X進(jìn)行恢復(fù)重建.但是根據(jù)壓縮感知理論，對(duì)于稀疏信號(hào)X，如果測(cè)量矩陣Φ滿足一定的約束等距性(Restricted Isometry Property，RIP)條件，那么原始信號(hào)X可以通過(guò)求解式(2)得以恢復(fù)重建.

(2)

當(dāng)信號(hào)X∈RN在空域中非稀疏時(shí)，則需要用一組基Ψ=[ψ1|ψ2|…|ψN]先對(duì)其進(jìn)行稀疏表示，即：

(3)

其中θ為稀疏系數(shù)，Ψ為信號(hào)X的稀疏基或者稀疏字典，那么壓縮感知測(cè)量過(guò)程可以表示為

Y=ΦΨθ

(4)

其中ΦΨ稱為感知測(cè)量矩陣，這里為了保證新的測(cè)量矩陣ΦΨ能夠滿足RIP條件，則要求矩陣Φ和Ψ盡可能的不相關(guān).

作為壓縮感知理論核心問(wèn)題之一，壓縮感知重建算法一直是該領(lǐng)域的研究熱點(diǎn)，直接關(guān)系到壓縮感知理論實(shí)際應(yīng)用的成敗，特別對(duì)于高維的圖像信號(hào)應(yīng)用.目前主流壓縮感知重建算法主要包括：凸優(yōu)化算法、貪婪算法、非凸最小化方法、組合優(yōu)化算法、迭代閾值算法和布萊格曼迭代算法等.這些壓縮感知重建算法主要利用信號(hào)在一些基函數(shù)下的稀疏性先驗(yàn)知識(shí)，盡管為壓縮感知理論的推廣應(yīng)用奠定了良好基礎(chǔ)，但是這些稀疏性先驗(yàn)知識(shí)主要是在一些固定基下的稀疏性，適應(yīng)性較差，對(duì)于內(nèi)容多變的圖像壓縮感知應(yīng)用而言，重建圖像的質(zhì)量極不穩(wěn)定.為了得到穩(wěn)定而真實(shí)的恢復(fù)圖像，必須進(jìn)一步挖掘圖像中潛在的其他先驗(yàn)知識(shí)作為正則化條件，例如：圖像小波變換系數(shù)的結(jié)構(gòu)性、圖像內(nèi)容的平滑性、非局部圖像塊的相似性、相似圖像塊間的低秩性和視頻圖像幀間的相關(guān)性等.如果在圖像壓縮感知重建過(guò)程中，對(duì)這些先驗(yàn)屬性加以充分利用，將可以進(jìn)一步提高壓縮感知效率.目前在圖像去噪研究領(lǐng)域，很多學(xué)者基于圖像的潛在先驗(yàn)知識(shí)先后提出了小波閾值去噪方法[3]、基于全變差(Total Variation，TV)的去噪方法[4]、奇異譜分析去噪方法[5]和非局部濾波圖像去噪算法[6]等，其中最具代表性的是TV模型，在圖像去噪方面取得了很好效果.如何利用這些圖像先驗(yàn)知識(shí)模型進(jìn)行壓縮感知圖像恢復(fù)是本文研究重點(diǎn).

對(duì)于圖像壓縮感知應(yīng)用，由于大部分圖像具有稀疏或者近似稀疏的梯度屬性，因此將TV模型作為稀疏正則項(xiàng)的壓縮感知圖像重建算法也得到了廣泛應(yīng)用[7,8]，其模型如式(5)所示：

(5)

其中

(6)

或者

(7)

式(6)和式(7)分別稱為各向異性全變差和各向同性全變差.基于TV正則化的圖像壓縮感知恢復(fù)算法可以很好的保留圖像邊緣和紋理等重要圖像特征信息，至今仍然是國(guó)內(nèi)外研究熱點(diǎn).由于TV函數(shù)的非可導(dǎo)性和非線性，因此對(duì)式(5)的求解非常困難，目前主流的TV求解算法主要包括：二階錐規(guī)劃方法(Second-Order Cone Programming，SOCP)[9]、1-Magic方法[10]，兩步迭代閾值算法(Two-step Iterative Threshold，TwIST)方法[11]、NESTA方法[12]、RecPF方法[13]、TVAL3[14]方法、布萊格曼迭代算法[15]等.但是由于TV模型僅僅依賴于圖像的平滑性先驗(yàn)假設(shè)，因此恢復(fù)圖像過(guò)于平滑，在低采樣率時(shí)，恢復(fù)圖像常常呈現(xiàn)油畫(huà)效果.

本文將利用圖像自身的非局部自相似性先驗(yàn)來(lái)進(jìn)行壓縮感知圖像恢復(fù)，并用秩極小化算法進(jìn)行求解.首先對(duì)圖像中的非局部相似塊進(jìn)行聚類，然后將這些相似圖像塊作為列向量構(gòu)建一個(gè)二維矩陣，由于列向量之間具有很強(qiáng)的相關(guān)性，因此該二維矩陣屬于低秩矩陣，可以通過(guò)秩最小化方法對(duì)這個(gè)二維矩陣進(jìn)行恢復(fù)，從而完成相似圖像塊的重建，最后將所有恢復(fù)的相似圖像塊進(jìn)行加權(quán)平均即可得到最終的壓縮感知恢復(fù)圖像.由于這種相似圖像塊矩陣的低秩先驗(yàn)與恢復(fù)圖像本身的內(nèi)容密切相關(guān)，因此本算法具有很好的自適應(yīng).

2研究背景

2.1非局部相似性原理

自然圖像中存在大量的重復(fù)冗余結(jié)構(gòu)信息[16,17]，如圖(1)所示，這種冗余結(jié)構(gòu)信息不僅包括平滑區(qū)域，即大部分像素值相同的區(qū)域，在紋理區(qū)域和邊緣部分，也同樣存在大量的結(jié)構(gòu)相似性，它們不僅像素值相同，而且圖像塊的結(jié)構(gòu)也基本相似，如圖1中的框選塊區(qū)域.基于這種圖像像素間的冗余性可以對(duì)圖像進(jìn)行有效的恢復(fù)重建，例如：圖像去噪、超分辨率重建、壓縮感知重建等.

給定一幅圖像X={x(i,j),0≤i,j≤N}，其中i,j為像素坐標(biāo)，N為圖像的分辨率，這里為了表示方便，假設(shè)圖像X為正方形結(jié)構(gòu).定義bi,j∈X為左上角位置為(i,j)，大小為n×n的圖像塊，塊bi,j與塊bm,n之間的相似度一般用它們之間的歐幾里得距離進(jìn)行測(cè)量，如下式(8)所示：

(8)

如果它們之間的歐幾里得距離d小于一定的閾值t，則認(rèn)為它們具有相似性.與圖像塊bi,j相似的圖像塊集合表示為Si,j，其表示形式為：

Si,j={bm,n|d(bi,j,bm,n)

(9)

其中R為相似塊搜索窗口，是以bi,j為中心的一個(gè)圖像區(qū)域.相似塊集合、當(dāng)前塊以及搜索窗口之間的位置關(guān)系如圖2所示.

在集合Si,j中，如果將每個(gè)相似圖像塊都按一定的掃描方式(如柵格掃描)展開(kāi)成一維矢量形式，形成相似塊圖像矩陣Ai,j=[a1,a2,…,an]，其中ai對(duì)應(yīng)于每個(gè)相似圖像塊.由于圖像塊a1,a2,…,an具有相似的結(jié)構(gòu)特征及像素值，因此相似塊集合矩陣Ai,j具有低秩屬性.利用秩極小化理論實(shí)現(xiàn)低秩矩陣恢復(fù)，從而實(shí)現(xiàn)圖像恢復(fù)功能.

2.2秩極小化模型及求解算法

近年來(lái)，基于秩極小化理論的應(yīng)用也得到很多關(guān)注，例如：基于低秩矩陣的視頻去噪技術(shù)[18,19]，將視頻中時(shí)空域相似圖像塊組合成相似矩陣，利用噪聲檢測(cè)器去除其中的噪聲像素，然后再進(jìn)行低秩矩陣恢復(fù)；在文獻(xiàn)[20]中，E.Candes還將該理論應(yīng)用于監(jiān)控視頻的背景建模中，可成功地將靜止背景和活動(dòng)的前景有效分開(kāi)；其他相關(guān)應(yīng)用還包括聯(lián)合圖像對(duì)齊[21,22]、圖像超分辨率重建[23]、人臉識(shí)別[24]和圖像去噪[25]等.

假設(shè)矩陣D∈Rm×n是由低秩矩陣L∈Rm×n(rank(L)≤r)和稀疏噪聲矩陣E∈Rm×n組成，即：

D=L+E

(10)

其中秩r?min(m,n)，低秩矩陣恢復(fù)就是從觀測(cè)矩陣D中恢復(fù)出低秩矩陣L，其數(shù)學(xué)模型為：

(11)

根據(jù)凸包絡(luò)優(yōu)化理論，Wright提出了使用核范數(shù)來(lái)近似矩陣的秩[26]，矩陣的1范數(shù)來(lái)近似矩陣零范數(shù)，將問(wèn)題式(11)轉(zhuǎn)換為下述凸優(yōu)化問(wèn)題：

(12)

關(guān)于秩極小化模型式(12)的求解算法，常見(jiàn)的幾種算法主要包括迭代閾值算法(Iterative Thresholding,IT)[27～28]、加速近鄰梯度算法(Accelerated Proximal Gradient,APG)[29]和交錯(cuò)方向算法(Alternating Direction Method,ADM)[30]及其改進(jìn)的線性化版本等.

3基于秩極小化的壓縮感知圖像恢復(fù)算法

對(duì)于壓縮感知圖像恢復(fù)，利用圖像自身的非局部相似性先驗(yàn)來(lái)進(jìn)行壓縮感知圖像恢復(fù)，并用秩極小化算法進(jìn)行求解，這種先驗(yàn)知識(shí)與恢復(fù)圖像本身的內(nèi)容密切相關(guān)，因此具有很好的自適應(yīng).

假設(shè)給定的原始圖像為X，測(cè)量矩陣為A，那么壓縮感知測(cè)量后得到的測(cè)量值為Y=AX+ω，其中ω為測(cè)量噪聲或量化噪聲.壓縮感知圖像恢復(fù)就是從測(cè)量值Y中恢復(fù)原始圖像X.由于感知測(cè)量是欠采樣過(guò)程，直接進(jìn)行恢復(fù)屬于欠定方程組求解，有無(wú)數(shù)的解X能夠滿足Y=AX+ω，因此需要加入圖像X的先驗(yàn)知識(shí)來(lái)正則化壓縮感知圖像恢復(fù)過(guò)程，提高圖像恢復(fù)精度.這里我們將利用非局部相似圖像塊矩陣的低秩先驗(yàn)來(lái)恢復(fù)原始圖像X，其數(shù)學(xué)模型為：

(13)

其中N為相似塊集合的數(shù)目.對(duì)于圖像X，按照一定的掃描順序，對(duì)圖像中相應(yīng)位置的塊構(gòu)建對(duì)應(yīng)的非局部相似圖像塊矩陣，例如：對(duì)于256×256分辨率的圖像，假設(shè)塊大小為8×8，如果對(duì)每個(gè)8×8圖像塊都構(gòu)建相似塊集合，則相似塊集合的數(shù)目N=(256-8)×(256-8).由于上述優(yōu)化問(wèn)題式(13)含有秩極小化問(wèn)題求解，直接求解上述約束最優(yōu)化問(wèn)題非常困難，因此首先對(duì)上述問(wèn)題進(jìn)行變量替換，轉(zhuǎn)換成下述優(yōu)化問(wèn)題：

(14)

其對(duì)應(yīng)的增廣拉格朗日函數(shù)為：

L(X,U)=∑Ni,jSi,j*-αT(Y-AX)

(15)

(16)

αk+1=αk-β(Y-AXk+1)

(17)

γk+1=γk-θ(Xk+1-Uk+1)

(18)

由于目標(biāo)函數(shù)式(16)中含有關(guān)于秩極小化求解的非平滑項(xiàng)，因此對(duì)問(wèn)題式(16)的求解仍然非常困難，這里將借助交替方向法ADM分別對(duì)X和U進(jìn)行最優(yōu)化求解，即首先在固定U的時(shí)候?qū)進(jìn)行優(yōu)化求解，然后再在固定X的時(shí)候?qū)進(jìn)行優(yōu)化求解，即將原問(wèn)題分成兩個(gè)子問(wèn)題分別進(jìn)行求解.

3.1X子問(wèn)題的求解

假設(shè)在第k迭代時(shí)U的優(yōu)化解為Uk，那么Xk+1的解可以表示成下式：

Xk+1=minX-αT(Y-AX)+β2Y-AX22

(19)

對(duì)其簡(jiǎn)化得到：

(20)

上述問(wèn)題是常見(jiàn)的二次優(yōu)化問(wèn)題，有閉解，對(duì)它求導(dǎo)數(shù)并等于零得：

(21)

Xk+1=(βATA+θI)-1(βATY-ATα+θUk+γ)

(22)

其中I為單位矩陣，這種求解方法看似非常簡(jiǎn)單直接，但是由于有矩陣求逆運(yùn)算(βATA+θI)-1，計(jì)算復(fù)雜度高，而且對(duì)于圖像壓縮感知應(yīng)用，矩陣的維數(shù)也很大，直接進(jìn)行矩陣求逆需要的內(nèi)存空間也很大，為此我們提出了一種基于線性化技術(shù)來(lái)優(yōu)化上述求解過(guò)程.

Y-AX-αβ22=Y-AXk-αβ22+gk(X-Xk)

(23)

Xk+1=minXβ2(Y-AXk-αβ22+gk(X-Xk)

(24)

這樣X(jué)k+1同樣具有閉解，其解為：

(25)

即：

(26)

從上式可知，通過(guò)線性化技術(shù)有效地消除了矩陣的求逆運(yùn)算.

3.2U子問(wèn)題的求解

與求解X子問(wèn)題一樣，在求解U子問(wèn)題時(shí)，假設(shè)Xk+1已經(jīng)求出并固定，則Uk+1的解可以表示成下式：

s.t.Si,j∈U

(27)

進(jìn)行同類項(xiàng)合并后，得到下式：

s.t.Si,j∈U

(28)

上式中的第一項(xiàng)是對(duì)圖像U中的相似塊矩陣Si,j進(jìn)行秩極小化求解，求和表示對(duì)所有非局部相似塊組的秩求最小值.由于圖像中的非局部相似塊組Si,j具有可分性結(jié)構(gòu)，因此可以將上式中的第二項(xiàng)同樣分解成與第一項(xiàng)相同的塊組形式，然后對(duì)每個(gè)相似塊組分別進(jìn)行秩極小化求解，則式(28)可以改寫(xiě)成下式：

(29)

(30)

其中U∑VT為圖像塊集合Wi,j的奇異值分解，Sτ為軟閾值算子，定義如下：

(31)

在完成相似塊矩陣Si,j秩極小化求解之后，那么圖像Uk+1就是圖像中所有相似塊Si,j的平均值，由于每個(gè)圖像塊可能與多個(gè)塊存在相似，因此這里的平均是對(duì)每個(gè)圖像塊在Si,j出現(xiàn)的次數(shù)進(jìn)行平均.

基于秩極小化的壓縮感知圖像恢復(fù)算法描述如算法1所示.

4實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證基于秩極小化的壓縮感知圖像恢復(fù)算法的有效性，我們將模擬壓縮感知測(cè)量過(guò)程，對(duì)常用的測(cè)試圖像進(jìn)行模擬感知測(cè)量，然后利用本文中的算法對(duì)測(cè)量數(shù)據(jù)進(jìn)行圖像恢復(fù)重建，一方面對(duì)算法中涉及到的參數(shù)進(jìn)行討論，選擇最優(yōu)的參數(shù)值；另一方面評(píng)估本文中的恢復(fù)算法在不同參數(shù)配置、不同采樣率設(shè)置下的恢復(fù)效果，同時(shí)還對(duì)恢復(fù)算法的魯棒性、收斂性和計(jì)算復(fù)雜度進(jìn)行評(píng)估.

在本文實(shí)驗(yàn)中，壓縮感知測(cè)量矩陣采用的是部分DCT矩陣，其流程如下：首先將二維圖像進(jìn)行隨機(jī)置換，然后對(duì)置換后的圖像進(jìn)行DCT變換，最后對(duì)變換后的DCT系數(shù)進(jìn)行隨機(jī)下采樣產(chǎn)生形成感知測(cè)量數(shù)據(jù).這種基于部分DCT變換的感知測(cè)量矩陣不僅不需要顯式存儲(chǔ)測(cè)量矩陣系數(shù)，而且存在快速算法，如蝶形快速DCT變換和反變換算法，適合圖像壓縮感知應(yīng)用.

本文算法屬于迭代優(yōu)化求解算法，如何選擇合適的迭代中止條件對(duì)算法也很重要，既期望恢復(fù)圖像盡可能接近原始圖像，又希望避免過(guò)度迭代計(jì)算引起計(jì)算復(fù)雜度的增加.本文中我們選擇每次迭代產(chǎn)生的恢復(fù)圖像相對(duì)變化值作為迭代中止條件，其定義如下：

(32)

其中v為預(yù)定義的閾值，其值設(shè)置為5×10-3，如果恢復(fù)圖像相對(duì)變化值小于這個(gè)閾值，則中止迭代運(yùn)算.

我們選擇了多個(gè)測(cè)試圖像庫(kù)中不同屬性的測(cè)試圖像以及醫(yī)學(xué)圖像進(jìn)行評(píng)估測(cè)試，如圖3所示，所有測(cè)試圖像都是灰度圖像，其分辨率為256×256.

表1　基于秩極小化的壓縮感知圖像恢復(fù)算法(PSNR：dB)

用于性能比較的壓縮感知圖像恢復(fù)算法包括YALL1[31]、BCS[32]、NESTA[12]和BM3D-CS[33]，這些算法代表了當(dāng)前壓縮感知領(lǐng)域中圖像恢復(fù)性能最好算法，每個(gè)算法也包含了大量的參數(shù)設(shè)置和自適應(yīng)調(diào)整過(guò)程.在我們的比較測(cè)試過(guò)程中，所使用的算法參數(shù)都是原作者在相應(yīng)論文中給出的最佳參數(shù)設(shè)置，詳細(xì)設(shè)置請(qǐng)參考相應(yīng)作者的主頁(yè)，這里不再詳細(xì)解釋和列舉.

在測(cè)試過(guò)程中，采樣率分別設(shè)置為0.3，0.4，0.5和0.6，恢復(fù)算法性能比較如表1所示，其中CSIRLR為本文中的算法.從表中的數(shù)據(jù)，我們可以看到，算法CSIRLR優(yōu)于其它所有算法，特別對(duì)于測(cè)試圖像barbara，由于其圖像中存在豐富的相似紋理信息，這對(duì)于其他所有的壓縮感知恢復(fù)算法都是一個(gè)挑戰(zhàn)，但由于CSIRLR算法利用了非局部相似圖像塊的低秩特征，完美的恢復(fù)了感知圖像，即使對(duì)于恢復(fù)性能最好的算法NESTA，也有接近7dB的增益.對(duì)于兩個(gè)醫(yī)學(xué)圖像MRI-1和MRI-2，本算法CSIRLR也取得了比較好的恢復(fù)效果，特別在高采樣率的情況下，由于相似圖像塊矩陣的構(gòu)建更加精確，恢復(fù)性能的提高也更加明顯.

測(cè)試圖像Barbara在0.3采樣率下的恢復(fù)圖像及其恢復(fù)殘差如圖4所示，從圖中可以，BM3D-CS算法的重建圖像主觀質(zhì)量?jī)H次于本文算法CSIRLR，因?yàn)锽M3D-CS也是采用了非局部相似塊的思想進(jìn)行重建，但是在數(shù)據(jù)逼近求解過(guò)程中采用的是隨機(jī)投影算法，難以恢復(fù)復(fù)雜的紋理信息，其整體重建誤差仍然較大.YALL1和NESTA算法都是使用全變差正則項(xiàng)進(jìn)行壓縮感知圖像恢復(fù)，對(duì)于復(fù)雜的紋理圖像，它們假設(shè)的局部平滑特性較弱，因此重建圖像呈現(xiàn)明顯的油畫(huà)效果，在邊緣部分的重建誤差非常明顯.BCS算法是以塊單位進(jìn)行壓縮感知采樣和重建的算法，盡管在恢復(fù)重建過(guò)程中使用維納濾波進(jìn)行減少塊效應(yīng)，但是由于塊間頻率特性分布的差異，在塊邊緣存在還是明顯的塊斑效應(yīng)，而我們提出的基于秩極小化理論壓縮感知圖像恢復(fù)算法CSIRLR利用了非局部相似塊的低秩特性進(jìn)行恢復(fù)感知圖像，恢復(fù)的圖像不僅客觀圖像質(zhì)量PSNR值優(yōu)于其他算法，而且恢復(fù)圖像的主觀質(zhì)量效果和恢復(fù)圖像誤差也明顯的優(yōu)于其他算法.

本文中提出的基于秩極小化理論壓縮感知圖像恢復(fù)算法CSIRLR是屬于迭代恢復(fù)算法，算法復(fù)雜度與迭代次數(shù)密切相關(guān)，即算法的收斂率.即使單次迭代的計(jì)算復(fù)雜度很小，如果收斂較慢，那么其計(jì)算復(fù)雜度也很高.圖5給出了我們算法對(duì)測(cè)試圖像Barbara和MRI-2恢復(fù)的收斂性結(jié)果，即每個(gè)測(cè)試圖像在不同采樣率下PSNR值隨迭代次數(shù)的變化情況，這里參數(shù)設(shè)置與上述重建圖像質(zhì)量評(píng)估實(shí)驗(yàn)參數(shù)設(shè)置相同.從圖5中可以看出，我們算法的收斂性較好，基本上在迭代30次的情況下就能獲得穩(wěn)定的重建圖像.

5結(jié)論

目前壓縮感知恢復(fù)算法主要是利用圖像先驗(yàn)知識(shí)，根據(jù)感知測(cè)量值來(lái)進(jìn)行恢復(fù)重建，目前常用的圖像先驗(yàn)包括全變分、稀疏性等，盡管這些重建算法在特定的應(yīng)用領(lǐng)域都能獲得較好的重建效果，但適應(yīng)性較差，而且由于自然圖像內(nèi)容復(fù)雜，紋理多變，預(yù)定義的先驗(yàn)知識(shí)難以適應(yīng)所有情況.本文提出了一種基于秩最小化的壓縮感知圖像恢復(fù)算法，其基本思想是利用圖像中存在大量相似塊的先驗(yàn)知識(shí)，將這些相似圖像塊構(gòu)建成一個(gè)二維數(shù)據(jù)矩陣，由于塊的相似性，這個(gè)二維數(shù)據(jù)矩陣具有低秩屬性.基于低秩矩陣恢復(fù)理論，對(duì)這個(gè)二維數(shù)據(jù)矩陣進(jìn)行低秩矩陣恢復(fù)求解，從而完成壓縮感知圖像恢復(fù)重建.和傳統(tǒng)的壓縮感知圖像恢復(fù)算法相比，本算法利用圖像自身的信息進(jìn)行恢復(fù)，適應(yīng)性較強(qiáng).實(shí)驗(yàn)表明本算法優(yōu)于目前主流的壓縮感知圖像恢復(fù)算法，并且具有良好的收斂性能.

參考文獻(xiàn)

[1]Candes E,Romberg J,Tao T.Robust uncertainty principles:exact signal reconstruction from highly incomplete frequency information[J].Information Theory,IEEE Transactions on,2006,52(2):489-509.

[2]David L Donoho.Compressed sensing[J].Information Theory,IEEE Transactions on,2006,52(4):1289-1306.

[3]Bioucas-Dias JM,Figueiredo MA.A new TwIST:Two-step iterative shrinkage thresholding algorithms for image restoration[J].Image Processing,IEEE Transactions on,2007,16(12):2992-3004.

[4]Leonid I Rudin,Stanley Osher,Emad Fatemi.Nonlinear total variation based noise removal algorithms[J].Physica D:Nonlinear Phenomena,1992,60(11),259-268.

[5]Jianhua Luo,Wanqing Li,Yuemin Zhu.Reconstruction From limited-angle projections based onδ-uspectrum analysis[J].Image Processing,IEEE Transactions on,2010,19(1):131-140.

[6]Buades A,Coll B,Morel J-M.A non-local algorithm for image denoising[A].IEEE Computer Society Conference on Computer Vision and Pattern Recognition[C].Washington,DC:IEEE Press,2005.60-65.

[7]T Chan,S Esedoglu,F Park,A Yip.In Mathematical Models of Computer Vision[M].Berlin Germany:springer verlag,2005.

[8]A Chambolle,P L Lions.Image recovery via total variation minimization and related problems[J].Numerische Mathematik,1997,76(3):167-188.

[9]D Goldfarb,W Yin.Second-order cone programming methods for total variation based image restoration[J].SIAM Journal on Scientific Computing,2005,27(2):622-645.

[10]Candes E J,Tao T.Near-optimal signal recovery from random projections:Universal encoding strategies?[J].Information Theory,IEEE Transactions on,2006,52(12):5406-5425.

[11]Bioucas-Dias J M,Figueiredo M A T.Two-step algorithms for linear inverse problems with non-quadratic regularization[A].IEEE International Conference on Image Processing[C].Washington,DC:IEEE Press,2007.105-108.

[12]Stephen Becker,Jerome Bobin,Emmanuel J Candes.NESTA:A fast and accurate first-order method for sparse recovery[J].SIAM Journal on Imaging Sciences,2011,4(1):1-39.

[13]Junfeng Yang,Yin Zhang,Wotao Yin.A fast alternating direction method for TVL1-L2 signal reconstruction from partial Fourier data[J].IEEE Journal of Selected Topics in Signal Processing,2010,4(2):288-297.

[14]C Li,W Yin,Y Zhang.TVAL3:TV minimization by augmented Lagrangian and alternating direction algorithms[EB/OL].http://www.caam.rice.edu/optimization/L1/TVAL3/,2009.

[15]Y Xiao,J Yang,X Yuan,Alternating algorithms for total variation image reconstruction from random projections[J].Inverse Problems and Imaging,2012,6(3):547-563.

[16]K Dabov,A Foi,V Katkovnik,K Egiazarian.Image denoising by sparse 3D transform-domain collaborative filtering[J].IEEE Trans Image Process,2007,16(8):2080-2095.

[17]M Maggioni,V Katkovnik,et al.A nonlocal transform-domain filter for volumetric data denoising and reconstruction[J].IEEE Trans Image Process,2013,22(1):119-133.

[18]Hui Ji，Chaoqiang Liu，et al.Robust video denoising using low rank matrix completion[A].IEEE Conference on Computer Vision and Pattern Recognition (CVPR)[C].Washington,DC:IEEE Press,2010.1791-1798.

[19]Hui Ji,Sibin Huang,et al.Robust video restoration by joint sparse and low rank matrix approximation[J].SIAM Journal on Imaging Sciences,2011,4(4):1122-1142.

[20]Emmanuel J Candes,Xiaodong Li,Yi Ma,John Wright.Robust principal component analysis?[J].Journal of the ACM,2011,58(3):1-37.

[21]Yigang Peng,Ganesh A,Wright J,Wenli Xu,Yi Ma.RASL:Robust alignment by sparse and low-rank decomposition for linearly correlated images[A].IEEE Conference on Computer Vision and Pattern Recognition[C].Washington,DC:IEEE Press,2010.763-770.

[22]Yigang Peng,Ganesh A,et al.RASL:Robust alignment by sparse and low-rank decomposition for linearly correlated images[J].Pattern Analysis and Machine Intelligence,IEEE Transactions on,2012,34(11):2233-2246.

[23]Jianchao Yang,Wright J,Huang T S,Yi Ma.Image super-resolution via sparse representation[J].Image Processing,IEEE Transactions on,2010,19(11):2861-2873.

[24]Wright J,Yang A Y,Ganesh A,Sastry S S,Yi Ma.Robust face recognition via sparse representation[J].Pattern Analysis and Machine Intelligence,IEEE Transactions on,2009,31(2):210-227.

[25]Weisheng Dong,Guangming Shi,Xin Li.Nonlocal image restoration with bilateral variance estimation:A low-rank approach[J].Image Processing,IEEE Transactions on,2013,22(2):700-711.

[26]Wright J,Ganesh A,Rao S,Ma Y.Robust principal component analysis:exact recovery of corrupted low-rank matrices by convex optimization[A].Proceedings of Advances in Neural Information Processing Systems (NIPS)[C].San Francisco:Morgan Kaufmann,2009.2080-2088.

[27]Ganesh A,Zhouchen Lin,Wright J,Leqin Wu,Minming Chen,Yi Ma.Fast algorithms for recovering a corrupted low-rank matrix[A].IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP)[C].Washington,DC:IEEE Press,2009.213-216.

[28]Jian-Feng Cai,E J Candès,Zuowei Shen.A singular value thresholding algorithm for matrix completion[J].SIAM Journal on Optimization,2010,20(4):1956-1982.

[29]Amir Beck,Marc Teboulle.A fast iterative shrinkage-thresholding algorithm for linear inverse problems[J].SIAM Journal on Imaging Sciences,2009,2(1):183-202.

[30]Zhouchen Lin,Minming Chen,Leqin Wu,Yi Ma.The Augmented Lagrange Multiplier Method for Exact Recovery of Corrupted Low-Rank Matrices[EB/OL].http://arxiv.org/abs/1009.5055,2009.

[31]J F Yang,Yin Zhang.Alternating direction algorithms for L1-problems in compressive sensing[J].SIAM Journal on Scientific Computing,2011,33(1):250-278.

[32]S Mun,Fowler J E.Residual reconstruction for block-based compressed sensing of video[A].Data Compression Conference (DCC)[C].Washington,DC:IEEE Press,2011.183-192.

[33]K Egiazarian,A Foi,V Katkovnik.Compressed sensing image reconstruction via recursive spatially adaptive filtering[A].IEEE International Conference on Image Processing[C].Washington,DC:IEEE Press,2007.549-552.

沈燕飛男，1976年4月出生，江蘇靖江人.2002年畢業(yè)于武漢大學(xué)，其后在中國(guó)科學(xué)院計(jì)算技術(shù)研究所工作，任副研究員，2011年攻讀中國(guó)科學(xué)院大學(xué)計(jì)算機(jī)應(yīng)用專業(yè)博士學(xué)位，并于2014年7月畢業(yè).主要從事數(shù)字圖像處理、多媒體通信和計(jì)算機(jī)視覺(jué)等方面的研究工作.

E-mail:syf@ict.ac.cn

Compressed Sensing Image Reconstruction Algorithm Based on Rank Minimization

SHEN Yan-fei1,2,ZHU Zhen-min1,ZHANG Yong-dong1,LI Jin-tao1

(1.InstituteofComputingTechnology,ChineseAcademyofSciences,Beijing100190,China;2.BeijingKeyLaboratoryofMobileComputingandPervasiveDevice,Beijing100190,China)

Abstract:The problem of compressed sensing image reconstruction is imagined as a low rank matrix recovery problem for research.In order to construct this low rank matrix,the nonlocal similarity model is exploited,and every similar image block is treated as a column vector in the matrix.The matrix has the low rank property because the column vectors are strong correlation.The algorithm model is to solve the low rank matrix recovery problem subject to the compressed sensing measurement constraints.In the solution of our proposed algorithm,the constrained optimization problem is converted to unconstrained optimization problem by the augmented lagrangian method,and then the alternating direction multiplier method is employed to solve it.To reduce the computational burden,the linear technique based on Taylor series expansion is taken to accelerate the proposed algorithm.The experimental results show that the subjective and objective performance of our proposed reconstruction algorithm is superior to the state of art reconstruction algorithms.

Key words:compressed sensing;rank minimization;image recovery;non-local similarity

作者簡(jiǎn)介

DOI:電子學(xué)報(bào)URL:http://www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.03.012

中圖分類號(hào):TP391

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：0372-2112 (2016)03-0572-08

基金項(xiàng)目:國(guó)家自然科學(xué)基金(No.61001123，No.61327013，No.61471343);廣東省教育部產(chǎn)學(xué)研結(jié)合項(xiàng)目(No.2012B091000106);中科院儀器裝備項(xiàng)目(No.YZ201321)

收稿日期:2014-03-24;修回日期:2014-07-02；責(zé)任編輯：梅志強(qiáng)