基于稀疏正则优化的图像复原算法

文章编号:1001-9081(2012)01-0261-03 doi:10.3724/SP.J.1087.2012.00261

摘 要:为提高图像复原的速度，改进图像复原的质量，提出一种新算法。将图像复原表示为一类标准的优化问题，采用交替最小化把该优化问题分解为等价的两个子问题。通过迭代求解这两个子问题，获得图像复原问题的解。在此迭代过程中，引入迭代软阈值法处理图像降噪子问题。实验对不同类型的模糊图像进行了复原，其结果验证了算法的有效性。与多级阈值Landweber(MLTL)算法和快速收缩阈值算法(FISTA)相比，处理相同图像时，所提算法可分别节省28%和71%的时间，同时复原图像的信噪比(SNR)可提高0.7~3.5dB。

关键词: 图像复原；约束优化问题；稀疏表示；交替最小化；迭代软阈值

中图分类号: TP391.413 文献标志码:A

Abstract: For speeding up image restoration and improving the restored results, a new algorithm was proposed. The image restoration was represented as a class of standard optimization problem, which was decomposed into two subproblems by the alternating minimization algorithm. By iteratively solving the two subproblems, a solution to the image restoration problems was obtained. During the subproblem solving, the iterative soft-thresholding algorithm was introduced for the denoising subproblem. In the experiment, the images blurred by different type of blur were restored. The experimental results show the effectiveness of the proposed algorithm. When dealing with the images, compared with Multilevel Thresholded Landweber (MLTL) and Fast Iterative Shrinkage-Thresholding Algorithm (FISTA), the proposed algorithm can reduce the time by 28% and 71% respectively, and it improves the Signal-to-Noise Ratio (SNR) values by 0.7dB to 3.5dB.

Key words: image restoration; constrained optimization problem; sparse representation; alternating minimization; iterative soft-thresholding

0 引言

图像成像模型可表示为：

y=Hx+n(1)

或

y=HDz+n(2)

其中：y∈RM×1表示已知的观测图像；x∈RN×1表示未知的原始图像；线性算子H∈RM×N；n∈RM×1N改为M表示加性噪声；D∈RN×L表示字典。特别地，若D是Parseval框架小波（即归一化的紧框架小波），它满足DTD=I［1］；z∈RL×1表示稀疏系数。式(1)和(2)分别代表了图像复原的两类主要算法：分析优化算法［2-4］和稀疏优化算法［5-7］。之所以将后一类算法称为稀疏优化算法，是因为该类算法首先估计向量z的最稀疏解，然后通过x=Dz重建原始图像。其思想来源于最近提出的压缩传感理论（compressed sensing）［8］，该理论认为：虽然空间域的图像大多是非稀疏的，但是选择合适的变换域，可得到任何信号的稀疏表示。除了图像复原领域，在图像降噪［9］、图像修复［10］、图像重建［11］等领域，图像的变换稀疏性也获得了成功应用。图像复原的稀疏优化问题可表示为：

minz12y－HDz22+λB(z)(3)

其中：常数λ>0；B(z)表示目标函数的正则项，用来抑制图像复原问题的病态性。解决优化问题(3)的方法主要有迭代收缩/阈值法(iterative shrinkage/thresholding)［6］、前向―后向分离法（forward-backward splitting）［12］和Bregman迭代法［13］等。这些算法在处理高维数据时（N≥104），效率大多比较低，且较依赖初始估计，并不能保证一定得到最优解。

因此，提出了一种新的算法，在解决优化问题(3)，实现图像复原的同时，提高图像复原的速度。该算法选择L1范式作为目标函数的正则项，Parseval框架小波作为字典D。因该算法是L1正则化技术与稀疏表示/压缩传感技术相结合的算法，故称其为稀疏正则优化算法（Sparse Regularized Optimization Algorithm， SROA）。

1 本文提出的算法

考虑约束条件DTx=z，优化问题(3)可表示为：

minx,z12y－Hx22+λB(z)

s.t. DTx=z(4)

对式(4)应用拉格朗日乘子法，可得非约束优化：

minx,z12y－Hx22+λB(z)+γ2z－DTx22(5)

其中γ>0。选择合适的λ、γ和初始估计x0、z0，式(4)和(5)会收敛到同一解。λ和γ的取值不能过小，否则式(5)收敛的速度很慢。迭代时逐渐增大λ和γ的取值，可提高收敛速度［14-15］。但λ和γ的取值变大，式(5)求解的数值稳定性又会受到影响［16］。另外，式(5)的目标函数含有两个未知变量，该目标函数是非凸的，优化问题(5)难以获得全局最优解。因此，本文用交替迭代最小化求解式(4)：

xk+1=arg minx［y－Hx22+γzk－DTx22］(6)

zk+1=arg minzγ2z－DTxk+122+λB(z)(7)

交替迭代最小化将式(4)分解为两个非约束优化子问题(6)和(7)。式(6)和(7)的目标函数是凸的，且交替最小化方法具有全局收敛性。选择合适的方法处理式(6)和(7)，式(6)和(7)可收敛到式(5)的最优解，即全局最优解。因此，式(6)、(7)与式(5)是等价问题。但相比式(5)，式(6)和(7)的求解会更简单。由式(6)可得闭合的全局最优解：xk+1=(HTH+γI)-1(HTy+γDzk)。利用快速傅里叶变换，xk+1计算的时间复杂度约为O(N log N)。令B(z)=z1，优化问题(7)变为：

zk+1=arg minzλz1+γ2z－DTxk+122(8)

式(8)代表了常见的图像降噪问题，处理该类问题最有效的方法之一是迭代软阈值法［17］，迭代软阈值法主要优点是时间复杂度很低，如式(9)所示：

zk+1=soft(DTxk+1,λ/γ)(9)

其中soft(•,•)表示软阈值函数，定义为式(10)：

soft(u,a)=sgn(u)max(|u|－a,0)(10)

综合以上的讨论，本文提出的SROA描述如下。

程序前

输入 γ，λ，H，D和z0。

for k=0,1,2,…,P

xk+1=arg minx［y－Hx22+γzk－DTx22］

zk+1=soft(DTxk+1,λ/γ)

end

程序后

2 实验结果

实验环境为：Windows XP SP2，Intel Core2 Duo CPU 2.10GHz，2GB DDR3 RAM，仿真软件Matlab 7.9.0（R2009b）；采用的测试图像（即原始图像x）如图1所示。对测试图像分别进行高斯模糊、均匀模糊和运动模糊，

并添加标准差为0.5的高斯噪声，以生成实验所需的观测图像y。其中：高斯模糊核的支撑域大小为9×9，标准差为9；均匀模糊核的支撑域大小为9×9；运动模糊核的长度为15，角度为9°。

SROA的初始输入如下：γ=4.8×10-3;λ=5.6×10-3;D这句话这样书写正确吗？请确认。为TIHP-4，TIHP-4（Translation Invariant Haar Pyramid with 4 levels）表示移不变Haar小波金字塔。

实验时手动调整参数γ和λ的取值，以获得SROA所能得到的最优结果。

σ=9表格中有此项，是否可以这样书写？;h1、h2和h3分别表示高斯模糊核、均匀模糊核和运动模糊核，h1为9×9，h2为9×9,h3为15/9。这里，9×9表示高斯模糊核和均匀模糊的尺寸；15/9表示运动模糊核的长度为15，角度为9°是9°吗？请明确。。然后，对所有的模糊图像均添加标准差为0.5的高斯噪声，生成实验所需的观测图像y。

为验证SROA的有效性，实验利用该算法对观测图像进行复原，并将复原结果与多级阈值Landweber（Multilevel Thresholded Landweber， MLTL）［5］算法和快速迭代收缩阈值算法（Fast Iterative Shrinkage-Thresholding Algorithm，FISTA）［6］进行比较。它们同属稀疏正则优化算法，基于相似的目标函数处理图像复原问题。比较将从时间、信噪比改进（Improved Signal-to-Noise Ratio，ISNR）和均方误差（Mean Squared Error，MSE）等方面进行。ISNR和MSE的定义为：

ISNR=10 lg y－x22MSE×N

MSE=x－xk+122/N

(11)

为使比较结果更准确，将3种算法的迭代次数均设为50。对每幅观测图像，3种算法均运行15次，所得结果的平均值作为最终的实验结果，详见表1~3。

实验结果表明，SROA可有效地进行图像复原，对于各种类型的模糊图像均适用。与FISTA和MLTL算法相比，该算法的速度更快，得到的结果更优。虽然，实验过程中SROA采用了相同的参数和字典，并获得了较好的实验结果，体现了该算法的鲁棒性。但是根据具体的观测图像，调整相应参数的取值，为其选择合适的字典，才能得到理想的复原结果。

实验过程中，目标函数（0.5×y-Hx22+λB(z)）的均值变化情况如图2所示。随着迭代次数的增加，目标函数逐渐减小，表明SROA在不断地收敛。尽管将SROA的迭代次数设置为50，但图2表明，只需约20~30次迭代，目标函数即逼近其最小值。

3 结语

本文提出了稀疏正则优化算法(SROA)，将图像复原作为约束优化问题进行处理。为解决该约束优化问题，利用交替最小化过程，将其分解为两个非约束优化问题，并用迭代软阈值法求解其中的图像降噪问题，从而提高了图像复原速度和复原图像的质量。实验对测试图像进行了不同类型的模糊，通过观测图像的复原，验证了SROA的有效性。虽然，对于所有的观测图像，该算法设置了相同的参数和字典，但其复原效果和速度始终优于MLTL算法和FISTA。

参考文献:

[1]

GARRIGOS G, HERNANDEZ E, SIKIC H, et al. Further results on the connectivity of Parseval frame wavelets ［J］. Proceedings of the American Mathematical Society, 2006, 134(11): 3211-3221.

[2]

AUJOL J F. Some first-order algorithms for total variation based image restoration ［J］. Journal of Mathematical Imaging and Vision, 2009, 34(3): 307-327.

[3]

SETZER S, STEIDL G, TEUBER T. Deblurring Poissonian images by split Bregman techniques ［J］. Journal of Visual Communication and Image Representation, 2010, 21(3): 193-199.

[4]

AUROUX D, BELAID L J, RJAIBI B. Application of the topological gradient method to color image restoration ［J］. SIAM Journal on Imaging Sciences, 2010, 3(2): 153-175.

[5]

VONESCH C, UNSER M. A fast multilevel algorithm for wavelet-regularized image restoration ［J］. IEEE Transactions on Image Processing, 2009, 18(3): 509-523.

[6]

BECK A, TEBOULLE M. A fast iterative shrinkage-thresholding algorithm for linear inverse problems ［J］. SIAM Journal on Imaging Sciences, 2009, 2(1): 183-202.

[7]

BECKER S, BOBIN J, CANDES E J. NESTA: A fast and accurate first-order method for sparse recovery ［J］. SIAM Journal on Imaging Sciences, 2011, 4(1): 1-39.

[8]

DONOHO D L. Compressed sensing ［J］. IEEE Transactions on Information Theory, 2006, 52(4): 1289-1306.

[9]

MAIRAL J, ELAD M, SAPIRO G. Sparse representation for color image restoration ［J］. IEEE Transactions on Image Processing, 2008, 17(1): 53-69.

[10]

FADILI M J, STARCK J-L, MURTAGH F. Inpainting and zooming using sparse representations ［J］. Computer Journal, 2009, 52(1): 64-79.

[11]

LUSTIG M, DONOHO D L, SANTOS J M, et al. Compressed sensing MRI ［J］. IEEE Signal Processing Magazine, 2008, 25(2): 72-82.

[12]

DAUBECHIES I, DEFRIESE M, de MOL C. An iterative thresholding algorithm for linear inverse problems with a sparsity constraint ［J］. Communications in Pure and Applied Mathematics, 2004, 57(11): 1413-1457.

[13]

GOLDSTEIN T, OSHER S. The split Bregman method for L1-regularized problems ［J］. SIAM Journal on Imaging Sciences, 2009, 2(2): 323-343.

[14]

WRIGHT S J, NOWAK R D, FIGUEIREDO M A T. Sparse reconstruction by separable approximation ［J］. IEEE Transactions on Signal Processing, 2009, 57(7): 2479-2493.

[15]

LORENZ D A. A projection proximal-point algorithm for l1 minimization ［J］. Numerical Functional Analysis and Optimization, 2010, 31(2): 172-190.

[16]

NOCEDAL J, WRIGHT S J. Numerical optimization ［M］. 2nd ed. New York: Springer-Verlag, 2006.

[17]

COMBETTES P L, WAJS V R. Signal recovery by proximal for-ward-backward splitting ［J］. Multiscale Modeling and Simulation, 2005, 4(4): 1168-1200.

收稿日期:2011-08-04;修回日期:2011-09-22。

基金项目:

国家自然科学基金资助项目(61070090)；国家自然科学基金青年基金资助项目(61102117)；淮北师范大学青年科研项目(700442)。

作者简介:

肖宿（1982-），男，安徽淮北人，讲师，博士，主要研究方向：数字图像复原； 韩国强（1962-），男，江西临川人，教授，博士生导师，博士，主要研究方向：数字图像处理。