基于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