基于秩极小化的压缩感知图像恢复算法

沈燕飞，朱珍民，张勇东，李锦涛

(1.中国科学院计算技术研究所，北京 100190； 2.北京市移动计算与新型终端重点实验室,北京 100190)



基于秩极小化的压缩感知图像恢复算法

沈燕飞1，2，朱珍民1，张勇东1，李锦涛1

(1.中国科学院计算技术研究所，北京 100190； 2.北京市移动计算与新型终端重点实验室,北京 100190)

摘要：本文将压缩感知图像恢复问题作为低秩矩阵恢复问题来进行研究.为了构建这样的低秩矩阵，我们采样非局部相似度模型，将相似图像块作为列向量构建一个二维相似块矩阵.由于列向量间的强相关性，因此该矩阵具有低秩属性.然后以压缩感知测量作为约束条件对这样的二维相似块矩阵进行低秩矩阵恢复求解.在算法求解的过程中，使用增广拉格朗日方法将受限优化问题转换为非受限优化问题，同时为了减少计算复杂度，使用基于泰勒展开的线性化技术来加速算法求解.实验表明该算法的收敛率、图像恢复性能均优于目前主流压缩感知图像恢复算法.

关键词:压缩感知；秩最小化；图像恢复；非局部相似

1引言

根据经典香农-那奎斯特采样定理，为了精确重建原始信号，信号的采样频率至少是被采样信号带宽的两倍，随着信号带宽的逐步提高，例如高分辨率医学图像和卫星云图等，对信号的采样速率和数据存储提出了越来越高的要求.然而在实际应用中，为了减少数据的存储、处理和传输成本，常常采用有损的方法对采集信号进行压缩处理，丢弃大量的冗余信息.这种“先采样后压缩”的信号处理模式不仅浪费了大量的数据传输带宽，而且也大大增加了信号采集设备的设计难度和成本.另外，在一些特殊应用中，例如：医学图像、雷达信号、地震勘测等应用，由于客观条件的限制，信号采集难以满足香农-那奎斯特采样定理中规定的最低频率要求.为了解决这些问题，美国科学院院士D.Donoho，斯坦福大学的E.Candes教授和华裔科学家陶哲轩等提出了压缩感知理论[1,2].该理论的核心思想是：给定一个信号，如果信号本身或者信号在某个变换域上具有稀疏性，则可以利用一个随机测量矩阵对信号进行降维测量，然后通过对测量数据进行非线性化优化求解，就可以完成对原始信号的精确重建.该理论自2006年提出以来，吸引了相关领域学者的广泛关注和研究热情.

压缩感知理论的数学模型表示如下：对于一个长度为N的一维信号X∈RN，如果X中只有K(K≪N)个非零元素，则称X是稀疏的，其稀疏度为K/N.压缩感知的测量过程就是将稀疏信号X在随机测量矩阵Φ(Φ∈RM×N,M≪N)上进行投影的过程，如式(1)所示，得到一个比原始信号X长度小很多的测量值Y∈RM.

Y=ΦX

(1)

由于式(1)是一个欠定方程组，属于病态求解问题，因此无法直接利用测量值Y对原始信号X进行恢复重建.但是根据压缩感知理论，对于稀疏信号X，如果测量矩阵Φ满足一定的约束等距性(Restricted Isometry Property，RIP)条件，那么原始信号X可以通过求解式(2)得以恢复重建.

(2)

当信号X∈RN在空域中非稀疏时，则需要用一组基Ψ=[ψ1|ψ2|…|ψN]先对其进行稀疏表示，即：

(3)

其中θ为稀疏系数，Ψ为信号X的稀疏基或者稀疏字典，那么压缩感知测量过程可以表示为

Y=ΦΨθ

(4)

其中ΦΨ称为感知测量矩阵，这里为了保证新的测量矩阵ΦΨ能够满足RIP条件，则要求矩阵Φ和Ψ尽可能的不相关.

作为压缩感知理论核心问题之一，压缩感知重建算法一直是该领域的研究热点，直接关系到压缩感知理论实际应用的成败，特别对于高维的图像信号应用.目前主流压缩感知重建算法主要包括：凸优化算法、贪婪算法、非凸最小化方法、组合优化算法、迭代阈值算法和布莱格曼迭代算法等.这些压缩感知重建算法主要利用信号在一些基函数下的稀疏性先验知识，尽管为压缩感知理论的推广应用奠定了良好基础，但是这些稀疏性先验知识主要是在一些固定基下的稀疏性，适应性较差，对于内容多变的图像压缩感知应用而言，重建图像的质量极不稳定.为了得到稳定而真实的恢复图像，必须进一步挖掘图像中潜在的其他先验知识作为正则化条件，例如：图像小波变换系数的结构性、图像内容的平滑性、非局部图像块的相似性、相似图像块间的低秩性和视频图像帧间的相关性等.如果在图像压缩感知重建过程中，对这些先验属性加以充分利用，将可以进一步提高压缩感知效率.目前在图像去噪研究领域，很多学者基于图像的潜在先验知识先后提出了小波阈值去噪方法[3]、基于全变差(Total Variation，TV)的去噪方法[4]、奇异谱分析去噪方法[5]和非局部滤波图像去噪算法[6]等，其中最具代表性的是TV模型，在图像去噪方面取得了很好效果.如何利用这些图像先验知识模型进行压缩感知图像恢复是本文研究重点.

对于图像压缩感知应用，由于大部分图像具有稀疏或者近似稀疏的梯度属性，因此将TV模型作为稀疏正则项的压缩感知图像重建算法也得到了广泛应用[7,8]，其模型如式(5)所示：

(5)

其中

(6)

或者

(7)

式(6)和式(7)分别称为各向异性全变差和各向同性全变差.基于TV正则化的图像压缩感知恢复算法可以很好的保留图像边缘和纹理等重要图像特征信息，至今仍然是国内外研究热点.由于TV函数的非可导性和非线性，因此对式(5)的求解非常困难，目前主流的TV求解算法主要包括：二阶锥规划方法(Second-Order Cone Programming，SOCP)[9]、1-Magic方法[10]，两步迭代阈值算法(Two-step Iterative Threshold，TwIST)方法[11]、NESTA方法[12]、RecPF方法[13]、TVAL3[14]方法、布莱格曼迭代算法[15]等.但是由于TV模型仅仅依赖于图像的平滑性先验假设，因此恢复图像过于平滑，在低采样率时，恢复图像常常呈现油画效果.

本文将利用图像自身的非局部自相似性先验来进行压缩感知图像恢复，并用秩极小化算法进行求解.首先对图像中的非局部相似块进行聚类，然后将这些相似图像块作为列向量构建一个二维矩阵，由于列向量之间具有很强的相关性，因此该二维矩阵属于低秩矩阵，可以通过秩最小化方法对这个二维矩阵进行恢复，从而完成相似图像块的重建，最后将所有恢复的相似图像块进行加权平均即可得到最终的压缩感知恢复图像.由于这种相似图像块矩阵的低秩先验与恢复图像本身的内容密切相关，因此本算法具有很好的自适应.

2研究背景

2.1非局部相似性原理

自然图像中存在大量的重复冗余结构信息[16,17]，如图(1)所示，这种冗余结构信息不仅包括平滑区域，即大部分像素值相同的区域，在纹理区域和边缘部分，也同样存在大量的结构相似性，它们不仅像素值相同，而且图像块的结构也基本相似，如图1中的框选块区域.基于这种图像像素间的冗余性可以对图像进行有效的恢复重建，例如：图像去噪、超分辨率重建、压缩感知重建等.

给定一幅图像X={x(i,j),0≤i,j≤N}，其中i,j为像素坐标，N为图像的分辨率，这里为了表示方便，假设图像X为正方形结构.定义bi,j∈X为左上角位置为(i,j)，大小为n×n的图像块，块bi,j与块bm,n之间的相似度一般用它们之间的欧几里得距离进行测量，如下式(8)所示：

(8)

如果它们之间的欧几里得距离d小于一定的阈值t，则认为它们具有相似性.与图像块bi,j相似的图像块集合表示为Si,j，其表示形式为：

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

(9)

其中R为相似块搜索窗口，是以bi,j为中心的一个图像区域.相似块集合、当前块以及搜索窗口之间的位置关系如图2所示.

在集合Si,j中，如果将每个相似图像块都按一定的扫描方式(如栅格扫描)展开成一维矢量形式，形成相似块图像矩阵Ai,j=[a1,a2,…,an]，其中ai对应于每个相似图像块.由于图像块a1,a2,…,an具有相似的结构特征及像素值，因此相似块集合矩阵Ai,j具有低秩属性.利用秩极小化理论实现低秩矩阵恢复，从而实现图像恢复功能.

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

近年来，基于秩极小化理论的应用也得到很多关注，例如：基于低秩矩阵的视频去噪技术[18,19]，将视频中时空域相似图像块组合成相似矩阵，利用噪声检测器去除其中的噪声像素，然后再进行低秩矩阵恢复；在文献[20]中，E.Candes还将该理论应用于监控视频的背景建模中，可成功地将静止背景和活动的前景有效分开；其他相关应用还包括联合图像对齐[21,22]、图像超分辨率重建[23]、人脸识别[24]和图像去噪[25]等.

假设矩阵D∈Rm×n是由低秩矩阵L∈Rm×n(rank(L)≤r)和稀疏噪声矩阵E∈Rm×n组成，即：

D=L+E

(10)

其中秩r≪min(m,n)，低秩矩阵恢复就是从观测矩阵D中恢复出低秩矩阵L，其数学模型为：

(11)

根据凸包络优化理论，Wright提出了使用核范数来近似矩阵的秩[26]，矩阵的1范数来近似矩阵零范数，将问题式(11)转换为下述凸优化问题：

(12)

关于秩极小化模型式(12)的求解算法，常见的几种算法主要包括迭代阈值算法(Iterative Thresholding,IT)[27～28]、加速近邻梯度算法(Accelerated Proximal Gradient,APG)[29]和交错方向算法(Alternating Direction Method,ADM)[30]及其改进的线性化版本等.

3基于秩极小化的压缩感知图像恢复算法

对于压缩感知图像恢复，利用图像自身的非局部相似性先验来进行压缩感知图像恢复，并用秩极小化算法进行求解，这种先验知识与恢复图像本身的内容密切相关，因此具有很好的自适应.

假设给定的原始图像为X，测量矩阵为A，那么压缩感知测量后得到的测量值为Y=AX+ω，其中ω为测量噪声或量化噪声.压缩感知图像恢复就是从测量值Y中恢复原始图像X.由于感知测量是欠采样过程，直接进行恢复属于欠定方程组求解，有无数的解X能够满足Y=AX+ω，因此需要加入图像X的先验知识来正则化压缩感知图像恢复过程，提高图像恢复精度.这里我们将利用非局部相似图像块矩阵的低秩先验来恢复原始图像X，其数学模型为：

(13)

其中N为相似块集合的数目.对于图像X，按照一定的扫描顺序，对图像中相应位置的块构建对应的非局部相似图像块矩阵，例如：对于256×256分辨率的图像，假设块大小为8×8，如果对每个8×8图像块都构建相似块集合，则相似块集合的数目N=(256-8)×(256-8).由于上述优化问题式(13)含有秩极小化问题求解，直接求解上述约束最优化问题非常困难，因此首先对上述问题进行变量替换，转换成下述优化问题：

(14)

其对应的增广拉格朗日函数为：

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)

由于目标函数式(16)中含有关于秩极小化求解的非平滑项，因此对问题式(16)的求解仍然非常困难，这里将借助交替方向法ADM分别对X和U进行最优化求解，即首先在固定U的时候对X进行优化求解，然后再在固定X的时候对U进行优化求解，即将原问题分成两个子问题分别进行求解.

3.1X子问题的求解

假设在第k迭代时U的优化解为Uk，那么Xk+1的解可以表示成下式：

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

(19)

对其简化得到：

(20)

上述问题是常见的二次优化问题，有闭解，对它求导数并等于零得：

(21)

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

(22)

其中I为单位矩阵，这种求解方法看似非常简单直接，但是由于有矩阵求逆运算(βATA+θI)-1，计算复杂度高，而且对于图像压缩感知应用，矩阵的维数也很大，直接进行矩阵求逆需要的内存空间也很大，为此我们提出了一种基于线性化技术来优化上述求解过程.

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

(23)

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

(24)

这样Xk+1同样具有闭解，其解为：

(25)

即：

(26)

从上式可知，通过线性化技术有效地消除了矩阵的求逆运算.

3.2U子问题的求解

与求解X子问题一样，在求解U子问题时，假设Xk+1已经求出并固定，则Uk+1的解可以表示成下式：

s.t.Si,j∈U

(27)

进行同类项合并后，得到下式：

s.t.Si,j∈U

(28)

上式中的第一项是对图像U中的相似块矩阵Si,j进行秩极小化求解，求和表示对所有非局部相似块组的秩求最小值.由于图像中的非局部相似块组Si,j具有可分性结构，因此可以将上式中的第二项同样分解成与第一项相同的块组形式，然后对每个相似块组分别进行秩极小化求解，则式(28)可以改写成下式：

(29)

(30)

其中U∑VT为图像块集合Wi,j的奇异值分解，Sτ为软阈值算子，定义如下：

(31)

在完成相似块矩阵Si,j秩极小化求解之后，那么图像Uk+1就是图像中所有相似块Si,j的平均值，由于每个图像块可能与多个块存在相似，因此这里的平均是对每个图像块在Si,j出现的次数进行平均.

基于秩极小化的压缩感知图像恢复算法描述如算法1所示.

4实验结果与分析

为了验证基于秩极小化的压缩感知图像恢复算法的有效性，我们将模拟压缩感知测量过程，对常用的测试图像进行模拟感知测量，然后利用本文中的算法对测量数据进行图像恢复重建，一方面对算法中涉及到的参数进行讨论，选择最优的参数值；另一方面评估本文中的恢复算法在不同参数配置、不同采样率设置下的恢复效果，同时还对恢复算法的鲁棒性、收敛性和计算复杂度进行评估.

在本文实验中，压缩感知测量矩阵采用的是部分DCT矩阵，其流程如下：首先将二维图像进行随机置换，然后对置换后的图像进行DCT变换，最后对变换后的DCT系数进行随机下采样产生形成感知测量数据.这种基于部分DCT变换的感知测量矩阵不仅不需要显式存储测量矩阵系数，而且存在快速算法，如蝶形快速DCT变换和反变换算法，适合图像压缩感知应用.

本文算法属于迭代优化求解算法，如何选择合适的迭代中止条件对算法也很重要，既期望恢复图像尽可能接近原始图像，又希望避免过度迭代计算引起计算复杂度的增加.本文中我们选择每次迭代产生的恢复图像相对变化值作为迭代中止条件，其定义如下：

(32)

其中v为预定义的阈值，其值设置为5×10-3，如果恢复图像相对变化值小于这个阈值，则中止迭代运算.

我们选择了多个测试图像库中不同属性的测试图像以及医学图像进行评估测试，如图3所示，所有测试图像都是灰度图像，其分辨率为256×256.

表1　基于秩极小化的压缩感知图像恢复算法(PSNR：dB)

用于性能比较的压缩感知图像恢复算法包括YALL1[31]、BCS[32]、NESTA[12]和BM3D-CS[33]，这些算法代表了当前压缩感知领域中图像恢复性能最好算法，每个算法也包含了大量的参数设置和自适应调整过程.在我们的比较测试过程中，所使用的算法参数都是原作者在相应论文中给出的最佳参数设置，详细设置请参考相应作者的主页，这里不再详细解释和列举.

在测试过程中，采样率分别设置为0.3，0.4，0.5和0.6，恢复算法性能比较如表1所示，其中CSIRLR为本文中的算法.从表中的数据，我们可以看到，算法CSIRLR优于其它所有算法，特别对于测试图像barbara，由于其图像中存在丰富的相似纹理信息，这对于其他所有的压缩感知恢复算法都是一个挑战，但由于CSIRLR算法利用了非局部相似图像块的低秩特征，完美的恢复了感知图像，即使对于恢复性能最好的算法NESTA，也有接近7dB的增益.对于两个医学图像MRI-1和MRI-2，本算法CSIRLR也取得了比较好的恢复效果，特别在高采样率的情况下，由于相似图像块矩阵的构建更加精确，恢复性能的提高也更加明显.

测试图像Barbara在0.3采样率下的恢复图像及其恢复残差如图4所示，从图中可以，BM3D-CS算法的重建图像主观质量仅次于本文算法CSIRLR，因为BM3D-CS也是采用了非局部相似块的思想进行重建，但是在数据逼近求解过程中采用的是随机投影算法，难以恢复复杂的纹理信息，其整体重建误差仍然较大.YALL1和NESTA算法都是使用全变差正则项进行压缩感知图像恢复，对于复杂的纹理图像，它们假设的局部平滑特性较弱，因此重建图像呈现明显的油画效果，在边缘部分的重建误差非常明显.BCS算法是以块单位进行压缩感知采样和重建的算法，尽管在恢复重建过程中使用维纳滤波进行减少块效应，但是由于块间频率特性分布的差异，在块边缘存在还是明显的块斑效应，而我们提出的基于秩极小化理论压缩感知图像恢复算法CSIRLR利用了非局部相似块的低秩特性进行恢复感知图像，恢复的图像不仅客观图像质量PSNR值优于其他算法，而且恢复图像的主观质量效果和恢复图像误差也明显的优于其他算法.

本文中提出的基于秩极小化理论压缩感知图像恢复算法CSIRLR是属于迭代恢复算法，算法复杂度与迭代次数密切相关，即算法的收敛率.即使单次迭代的计算复杂度很小，如果收敛较慢，那么其计算复杂度也很高.图5给出了我们算法对测试图像Barbara和MRI-2恢复的收敛性结果，即每个测试图像在不同采样率下PSNR值随迭代次数的变化情况，这里参数设置与上述重建图像质量评估实验参数设置相同.从图5中可以看出，我们算法的收敛性较好，基本上在迭代30次的情况下就能获得稳定的重建图像.

5结论

目前压缩感知恢复算法主要是利用图像先验知识，根据感知测量值来进行恢复重建，目前常用的图像先验包括全变分、稀疏性等，尽管这些重建算法在特定的应用领域都能获得较好的重建效果，但适应性较差，而且由于自然图像内容复杂，纹理多变，预定义的先验知识难以适应所有情况.本文提出了一种基于秩最小化的压缩感知图像恢复算法，其基本思想是利用图像中存在大量相似块的先验知识，将这些相似图像块构建成一个二维数据矩阵，由于块的相似性，这个二维数据矩阵具有低秩属性.基于低秩矩阵恢复理论，对这个二维数据矩阵进行低秩矩阵恢复求解，从而完成压缩感知图像恢复重建.和传统的压缩感知图像恢复算法相比，本算法利用图像自身的信息进行恢复，适应性较强.实验表明本算法优于目前主流的压缩感知图像恢复算法，并且具有良好的收敛性能.

参考文献

[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年毕业于武汉大学，其后在中国科学院计算技术研究所工作，任副研究员，2011年攻读中国科学院大学计算机应用专业博士学位，并于2014年7月毕业.主要从事数字图像处理、多媒体通信和计算机视觉等方面的研究工作.

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

作者简介

DOI:电子学报URL:http://www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.03.012

中图分类号:TP391

文献标识码：A

文章编号：0372-2112 (2016)03-0572-08

基金项目:国家自然科学基金(No.61001123，No.61327013，No.61471343);广东省教育部产学研结合项目(No.2012B091000106);中科院仪器装备项目(No.YZ201321)

收稿日期:2014-03-24;修回日期:2014-07-02；责任编辑：梅志强