何姣姣，庹　謙，周　震，陳劍鳴

(昆明理工大學(xué) 理學(xué)院，云南 昆明 650500)

?

基于Tikhonov模型的原-對(duì)偶算法在圖像恢復(fù)中的應(yīng)用

何姣姣，庹謙，周震，陳劍鳴

(昆明理工大學(xué) 理學(xué)院，云南 昆明 650500)

摘要：圖像在采集、存儲(chǔ)、傳輸以及顯示過程中，由于各種因素，往往會(huì)造成圖像模糊，所以消除圖像中的噪聲、去除模糊等意義重大。在模糊圖像恢復(fù)過程中，運(yùn)用針對(duì)Tikhonov正則化問題演化來的梯度下降法與原-對(duì)偶算法，以及它們改進(jìn)的算法對(duì)模糊圖像進(jìn)行恢復(fù)。在這一模型中，正則化參數(shù)的選擇對(duì)圖像恢復(fù)的效果有很大的影響，選取一個(gè)相對(duì)合適的正則化參數(shù)來平衡擬合項(xiàng)與正則項(xiàng)情況很重要。選定合適的正則化參數(shù)后，在Armijo準(zhǔn)則下應(yīng)用0.618優(yōu)選法選擇步長(zhǎng)，進(jìn)行梯度下降法以及正則化下的原-對(duì)偶算法的計(jì)算，對(duì)模糊灰度圖像進(jìn)行恢復(fù)。使用上述2種方法對(duì)模糊圖像進(jìn)行恢復(fù)，實(shí)驗(yàn)表明，與梯度下降法相較而言，原-對(duì)偶算法在圖像恢復(fù)中效果更好。

關(guān)鍵詞：圖像恢復(fù)；Tikhonov正則化；梯度下降法；原-對(duì)偶算法

模糊圖像的恢復(fù)在圖像處理中是一個(gè)重要的研究課題。圖像模糊的過程在數(shù)學(xué)上可表示為g=Ax+n，其中，x表示原始圖像，A表示模糊核，n表示加性噪聲，g表示模糊圖像[1]。圖像模糊的原因有離焦模糊、運(yùn)動(dòng)模糊等，通常解決這些模糊圖像恢復(fù)應(yīng)先估計(jì)出模糊核(PSF)，進(jìn)而通過進(jìn)行圖像模糊的逆過程來求解恢復(fù)后的圖像。經(jīng)典的模糊圖像恢復(fù)算法有維納濾波法、逆濾波法、最小二乘法和神經(jīng)網(wǎng)絡(luò)法等。1972年，W.H.Richardson在有噪聲的情況下使用貝葉斯估計(jì)法對(duì)模糊圖像進(jìn)行復(fù)原，有不錯(cuò)的效果[2]。維納濾波法和逆濾波法是利用圖像頻譜的傅里葉變換來求圖像的逆，最小二乘法和Tikhonov正則化是通過建立數(shù)學(xué)模型，找到合適的正則項(xiàng)來求最優(yōu)解。

本文基于經(jīng)典的Tikhonov正則化[3]圖像恢復(fù)來解決下述問題，計(jì)算式如下：

(1)

式中，A∈Rm×n,m≥n,g∈Rm,λ∈R，λ為正則化參數(shù)，本文取0.01。由于圖像像素值的有界性，x滿足式1的約束條件。A是模糊矩陣，g是觀察圖像，H是高通濾波器或者單位矩陣，H.W.Engl和G.H.Golub等[4-5]討論了正則項(xiàng)中矩陣的選擇問題。為簡(jiǎn)化運(yùn)算，本文取H為單位矩陣[6-7]，圖像恢復(fù)問題則變成解式2的問題。通過選擇合適的λ參數(shù)值，來獲得較好的恢復(fù)效果。

(2)

采用梯度下降法和原-對(duì)偶算法這2種方法來解上述模型的約束最小化問題。這2種算法在計(jì)算過程中都應(yīng)進(jìn)行迭代運(yùn)算，迭代步長(zhǎng)的選擇在迭代運(yùn)算中起著重要作用，其中，有固定步長(zhǎng)和變化步長(zhǎng)。梯度下降法應(yīng)選擇迭代步長(zhǎng)，本文采用基于Armijo準(zhǔn)則[8]的0.618優(yōu)選法來進(jìn)行步長(zhǎng)的搜索，而原-對(duì)偶算法的迭代步長(zhǎng)固定為1。結(jié)果表明，原-對(duì)偶算法恢復(fù)效果明顯優(yōu)于梯度下降法。

1梯度下降法解Tikhovon正則化圖像恢復(fù)問題

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

(3)

采用x(k+1)=x(k)+tdk這一迭代過程，其中t代表步長(zhǎng)值，步長(zhǎng)取值不同，會(huì)影響算法收斂速度。為了提高整個(gè)算法的收斂速度，無需把線性搜索做得十分精確。本文采用Armijo準(zhǔn)則下的0.618法迭代方式來進(jìn)行步長(zhǎng)的選擇，進(jìn)而提高迭代效率。梯度下降法的具體步驟如下。

Step1：初始化x(0)。

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

Step3：計(jì)算dk。

Step4：設(shè)置目標(biāo)函數(shù)fobj=@(x)[norm(Ax-g)2/2+α·norm(x)2/2]。

Step5：檢驗(yàn)fobj(xk+tdk)≥fobj(xk)+αtd′x是否滿足。

Step6：如果不滿足，取t=βt，轉(zhuǎn)Step5；否則，取xk+1=xk+td。

2原-對(duì)偶法解Tikhovon正則化圖像恢復(fù)問題

2.1原-對(duì)偶算法基本原理

對(duì)偶理論是最優(yōu)化中很重要的理論。對(duì)于每一個(gè)線性規(guī)劃問題，可以構(gòu)造另一個(gè)與之相應(yīng)且密切相關(guān)的線性規(guī)劃問題，若前者稱為原始問題，那么后者就稱為對(duì)偶問題[10]。對(duì)一些線性規(guī)劃問題，求其對(duì)偶問題有時(shí)更便捷。對(duì)這樣的需要構(gòu)造新的問題來解決問題的方法，稱為原-對(duì)偶法。

假設(shè)函數(shù)F(x,y)關(guān)于變量x是凸函數(shù)，而關(guān)于變量y是凹函數(shù)。如果存在(x*,y*)，對(duì)任意的x∈X,y∈Y使得：

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

(4)

成立，則稱(x*,y*)是函數(shù)F(x,y)的鞍點(diǎn)。如果x*和y*分別是原始問題和對(duì)偶問題的最優(yōu)點(diǎn)，且對(duì)偶性成立，則稱這個(gè)點(diǎn)是Lagrange函數(shù)的一個(gè)鞍點(diǎn)。反之，亦成立。C.Antonin等[11]研究了如下最小最大問題的解：

(5)

式中，φ(x),ψ(y)是下半連續(xù)、正常的凸函數(shù)；K是一個(gè)線性矩陣。

結(jié)合以往的算法，得到新的迭代形式：

(6)

(7)

(8)

該算法推廣至一般求鞍點(diǎn)問題為：

(9)

(10)

(11)

2.2原-對(duì)偶算法的計(jì)算

(12)

式中，滿足x-z=0，x∈RN，α≤z≤β，這樣x變?yōu)闊o約束變量。

定義變量K=(I,-I)，其中I為單位矩陣，該問題就類似于式5的最小最大問題，即：

(13)

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

由于上述關(guān)于x和z有可分離結(jié)構(gòu)，故可以分開計(jì)算x(k+1)和z(k+1)。原-對(duì)偶的一般解法算法過程如下。

Step6：結(jié)束while。

Step7：更新x至迭代結(jié)束。

3實(shí)驗(yàn)結(jié)果

分別應(yīng)用傳統(tǒng)的梯度下降法、改進(jìn)的梯度下降法以及原-對(duì)偶算法和改進(jìn)的原-對(duì)偶算法進(jìn)行仿真實(shí)驗(yàn)。實(shí)驗(yàn)環(huán)境為CPU：PentiumDualE2200處理器，主頻：2.2GHz。內(nèi)存2GB，2.2GHz。實(shí)驗(yàn)平臺(tái)為MATLAB2012a版本。4種算法的正則項(xiàng)參數(shù)均選0.01，即λ=0.01。在Tikhonov模型中，A為散焦半徑為3的模糊矩陣。觀察圖像g=Ax+ηr，其中，x是真實(shí)圖像，η是噪聲水平，r是高斯噪聲。對(duì)cameraman,clock和church三幅灰度大小為256×256的圖像進(jìn)行模糊恢復(fù)仿真，最后用峰值信噪比PSNR[12]來衡量圖像的質(zhì)量：

(14)

從峰值信噪比方面，分別對(duì)噪聲水平為1、3、5和7時(shí)，對(duì)比了2種算法的PSNR峰值，結(jié)果見表1。設(shè)定最大迭代次數(shù)為200，停止迭代條件為相對(duì)誤差<10-4[13]，即：

(15)

從表1可知，原-對(duì)偶算法恢復(fù)效果在噪聲水平增加的情況下也較好。噪聲水平為1時(shí)PSNR與CPUTime(s)如圖1所示。顯然，改進(jìn)的原-對(duì)偶算法耗時(shí)最短，恢復(fù)效果圖如圖2所示。

表1　2種算法PSNR峰值結(jié)果

圖1　2種方法恢復(fù)圖像的PSNR隨時(shí)間變化圖

圖2　噪聲水平為1時(shí)SD、PD算法的恢復(fù)結(jié)果

4結(jié)語(yǔ)

本文研究了基于Tikhonov模型的兩大模糊圖像恢復(fù)算法——改進(jìn)的梯度下降法以及原-對(duì)偶算法。應(yīng)用原-對(duì)偶算法對(duì)迷糊圖像進(jìn)行恢復(fù)所得的PSNR峰值要比基于Armijo準(zhǔn)則的0.618優(yōu)選步長(zhǎng)梯度下降的平均高0.2dB。

參考文獻(xiàn)

[1] 蘇軍.基于頻譜分析的運(yùn)動(dòng)模糊圖像的參數(shù)鑒別[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] 孫文瑜，徐成賢，朱德通. 最優(yōu)化方法[M]. 2版. 北京：高等教育出版社，2010.

[10]MasaoF. 非線性最優(yōu)化基礎(chǔ)[M]. 林貴華,譯. 北京:科學(xué)出版社,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.

責(zé)任編輯鄭練

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

作者簡(jiǎn)介：何姣姣(1989-)，女，碩士研究生，主要從事圖像恢復(fù)處理等方面的研究。

中圖分類號(hào)：TP 391.4

文獻(xiàn)標(biāo)志碼:B