基于Tikhonov模型的原-对偶算法在图像恢复中的应用

何姣姣，庹　谦，周　震，陈剑鸣

(昆明理工大学 理学院，云南 昆明 650500)



基于Tikhonov模型的原-对偶算法在图像恢复中的应用

何姣姣，庹谦，周震，陈剑鸣

(昆明理工大学 理学院，云南 昆明 650500)

摘要：图像在采集、存储、传输以及显示过程中，由于各种因素，往往会造成图像模糊，所以消除图像中的噪声、去除模糊等意义重大。在模糊图像恢复过程中，运用针对Tikhonov正则化问题演化来的梯度下降法与原-对偶算法，以及它们改进的算法对模糊图像进行恢复。在这一模型中，正则化参数的选择对图像恢复的效果有很大的影响，选取一个相对合适的正则化参数来平衡拟合项与正则项情况很重要。选定合适的正则化参数后，在Armijo准则下应用0.618优选法选择步长，进行梯度下降法以及正则化下的原-对偶算法的计算，对模糊灰度图像进行恢复。使用上述2种方法对模糊图像进行恢复，实验表明，与梯度下降法相较而言，原-对偶算法在图像恢复中效果更好。

关键词：图像恢复；Tikhonov正则化；梯度下降法；原-对偶算法

模糊图像的恢复在图像处理中是一个重要的研究课题。图像模糊的过程在数学上可表示为g=Ax+n，其中，x表示原始图像，A表示模糊核，n表示加性噪声，g表示模糊图像[1]。图像模糊的原因有离焦模糊、运动模糊等，通常解决这些模糊图像恢复应先估计出模糊核(PSF)，进而通过进行图像模糊的逆过程来求解恢复后的图像。经典的模糊图像恢复算法有维纳滤波法、逆滤波法、最小二乘法和神经网络法等。1972年，W.H.Richardson在有噪声的情况下使用贝叶斯估计法对模糊图像进行复原，有不错的效果[2]。维纳滤波法和逆滤波法是利用图像频谱的傅里叶变换来求图像的逆，最小二乘法和Tikhonov正则化是通过建立数学模型，找到合适的正则项来求最优解。

本文基于经典的Tikhonov正则化[3]图像恢复来解决下述问题，计算式如下：

(1)

式中，A∈Rm×n,m≥n,g∈Rm,λ∈R，λ为正则化参数，本文取0.01。由于图像像素值的有界性，x满足式1的约束条件。A是模糊矩阵，g是观察图像，H是高通滤波器或者单位矩阵，H.W.Engl和G.H.Golub等[4-5]讨论了正则项中矩阵的选择问题。为简化运算，本文取H为单位矩阵[6-7]，图像恢复问题则变成解式2的问题。通过选择合适的λ参数值，来获得较好的恢复效果。

(2)

采用梯度下降法和原-对偶算法这2种方法来解上述模型的约束最小化问题。这2种算法在计算过程中都应进行迭代运算，迭代步长的选择在迭代运算中起着重要作用，其中，有固定步长和变化步长。梯度下降法应选择迭代步长，本文采用基于Armijo准则[8]的0.618优选法来进行步长的搜索，而原-对偶算法的迭代步长固定为1。结果表明，原-对偶算法恢复效果明显优于梯度下降法。

1梯度下降法解Tikhovon正则化图像恢复问题

d=(AT-A+λI)x+AT-g

(3)

采用x(k+1)=x(k)+tdk这一迭代过程，其中t代表步长值，步长取值不同，会影响算法收敛速度。为了提高整个算法的收敛速度，无需把线性搜索做得十分精确。本文采用Armijo准则下的0.618法迭代方式来进行步长的选择，进而提高迭代效率。梯度下降法的具体步骤如下。

Step1：初始化x(0)。

Step2：取t=1,α=0.1,β=0.618。

Step3：计算dk。

Step4：设置目标函数fobj=@(x)[norm(Ax-g)2/2+α·norm(x)2/2]。

Step5：检验fobj(xk+tdk)≥fobj(xk)+αtd′x是否满足。

Step6：如果不满足，取t=βt，转Step5；否则，取xk+1=xk+td。

2原-对偶法解Tikhovon正则化图像恢复问题

2.1原-对偶算法基本原理

对偶理论是最优化中很重要的理论。对于每一个线性规划问题，可以构造另一个与之相应且密切相关的线性规划问题，若前者称为原始问题，那么后者就称为对偶问题[10]。对一些线性规划问题，求其对偶问题有时更便捷。对这样的需要构造新的问题来解决问题的方法，称为原-对偶法。

假设函数F(x,y)关于变量x是凸函数，而关于变量y是凹函数。如果存在(x*,y*)，对任意的x∈X,y∈Y使得：

F(x*,y)≤F(x*,y*)≤F(x,y*)

(4)

成立，则称(x*,y*)是函数F(x,y)的鞍点。如果x*和y*分别是原始问题和对偶问题的最优点，且对偶性成立，则称这个点是Lagrange函数的一个鞍点。反之，亦成立。C.Antonin等[11]研究了如下最小最大问题的解：

(5)

式中，φ(x),ψ(y)是下半连续、正常的凸函数；K是一个线性矩阵。

结合以往的算法，得到新的迭代形式：

(6)

(7)

(8)

该算法推广至一般求鞍点问题为：

(9)

(10)

(11)

2.2原-对偶算法的计算

(12)

式中，满足x-z=0，x∈RN，α≤z≤β，这样x变为无约束变量。

定义变量K=(I,-I)，其中I为单位矩阵，该问题就类似于式5的最小最大问题，即：

(13)

给定初值x(0),z(0),y(0)，求解第k次迭代形式为：

由于上述关于x和z有可分离结构，故可以分开计算x(k+1)和z(k+1)。原-对偶的一般解法算法过程如下。

Step6：结束while。

Step7：更新x至迭代结束。

3实验结果

分别应用传统的梯度下降法、改进的梯度下降法以及原-对偶算法和改进的原-对偶算法进行仿真实验。实验环境为CPU：PentiumDualE2200处理器，主频：2.2GHz。内存2GB，2.2GHz。实验平台为MATLAB2012a版本。4种算法的正则项参数均选0.01，即λ=0.01。在Tikhonov模型中，A为散焦半径为3的模糊矩阵。观察图像g=Ax+ηr，其中，x是真实图像，η是噪声水平，r是高斯噪声。对cameraman,clock和church三幅灰度大小为256×256的图像进行模糊恢复仿真，最后用峰值信噪比PSNR[12]来衡量图像的质量：

(14)

从峰值信噪比方面，分别对噪声水平为1、3、5和7时，对比了2种算法的PSNR峰值，结果见表1。设定最大迭代次数为200，停止迭代条件为相对误差<10-4[13]，即：

(15)

从表1可知，原-对偶算法恢复效果在噪声水平增加的情况下也较好。噪声水平为1时PSNR与CPUTime(s)如图1所示。显然，改进的原-对偶算法耗时最短，恢复效果图如图2所示。

表1　2种算法PSNR峰值结果

图1　2种方法恢复图像的PSNR随时间变化图

图2　噪声水平为1时SD、PD算法的恢复结果

4结语

本文研究了基于Tikhonov模型的两大模糊图像恢复算法——改进的梯度下降法以及原-对偶算法。应用原-对偶算法对迷糊图像进行恢复所得的PSNR峰值要比基于Armijo准则的0.618优选步长梯度下降的平均高0.2dB。

参考文献

[1] 苏军.基于频谱分析的运动模糊图像的参数鉴别[J].电子科技，2011，24(7):77-79.

[2]RichardsonWH.Bayesian-basediterativemethodofimagerestoration[J].JournaloftheOpticalSocietyofAmerica, 1972, 62(1): 55-59.

[3]BouhamidiA,JbilouK.Sylvestertikhonov-regularizationmethodsinimagerestoration[J].JournalofComputationalandAppliedMathematics, 2007, 206:86-98.

[4]EnglHW,HankeM,NeubauerA.Regularizationofinverseproblems[J].SiamReview, 1996, 43(2):347-366.

[5]GolubGH,VonMattU.Tikhonovregularizationforlargescaleproblems[J].ScientificComputing, 1997:3-26.

[6]LewisB,ReichelL.Arnoldi-Tikhonovregularizationmethods[J].J.Comput.Appl.Math., 2009, 226(1):92-102.

[7]LiuW,WuCS.Apredictor-correctoriteratedTikhonovregularizationforlinearill-posedinverseproblems[J].AppliedMathematicsandComputation, 2013, 221:802-818.

[8]BryanL,LotharR.ArnoldiTikhonovregularizationmethods[J].JournalofComputationalandAppliedMathematics, 2009, 226:92-102.

[9] 孙文瑜，徐成贤，朱德通. 最优化方法[M]. 2版. 北京：高等教育出版社，2010.

[10]MasaoF. 非线性最优化基础[M]. 林贵华,译. 北京:科学出版社,2011.

[11]AntoninC,ThomasP.Afirst-orderprimal-dualalgorithmforconvexproblemswithapplicationstoimaging[J].JournalofMathematicalImaging&Vision, 2011, 40(1):120-145.

[12]ZhangJ,MoriniB,ZhangJ.Solvingregularizedlinearleast-squaresproblemsbythealternatingdirectionmethodwithapplicationstoimagerestortion[J].ElectronicTransactionsonNumericalAnalysisEtna, 1976, 1(3):237-263.

[13]WenYW,YipAM.Adaptiveparameterselectionfortotalvariation[J].NumericalMathematicsTheory, 2009, 2(4):427-438.

责任编辑郑练

The Primal-dual Algorithm based on Tikhonov Model Application in Image Restoration

HE Jiaojiao, TUO Qian, ZHOU Zhen, CHEN Jianming

(Kunming University of Science and Technology, Kunming 650500, China)

Abstract：In the process of collection, storage, transmission and display of image, it often has blurring due to various factors, so to eliminate the noise in the image and remove the fuzzy is of great significance. In the process of blur image restoration, the gradient decent method with the primal-dual algorithm and improved algorithm evolved by Tikhonov regularization problem are used to recover the image. In this model, the choice of regularization parameter has a great influence on the effect of image restoration, and it is very important to select a relatively suitable regularization parameter to balance the fitting term and regularization term. After selecting the appropriate regularization parameter, the gradient descent method and the primal dual algorithm are applied in the Armijo criteria, and the fuzzy gray image is restored by using the gradient descent method and the normalized algorithm. Two methods are used to restore the blurred image. The experiments show that the original dual algorithm is better than the gradient descent method in image restoration.

Key words:image restoration, Tikhonov regularization, gradient descent, primal-dual algorithm

收稿日期：2015-07-28

作者简介：何姣姣(1989-)，女，硕士研究生，主要从事图像恢复处理等方面的研究。

中图分类号：TP 391.4

文献标志码:B