肖 宿，洪留榮，沈 克，鄭 穎

淮北師范大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，安徽 淮北 235000

L1-L2正則化的圖像復(fù)原交替優(yōu)化算法

肖 宿，洪留榮，沈 克，鄭 穎

淮北師范大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，安徽 淮北 235000

XIAO Su,HONG Liurong,SHEN Ke,et al.L1-L2regularization based alternating optimal algorithm for image restoration.Computer Engineering and Applications,2014,50（3）：125-128.

CNKI網(wǎng)絡(luò)優(yōu)先出版：2013-06-08，http://www.cnki.net/kcms/detail/11.2127.TP.20130608.0956.014.html

1 引言

在采集、傳輸、存儲和使用的過程中，數(shù)字圖像的退化是不可避免的，退化圖像主要表現(xiàn)為模糊和含有噪聲。無論對研究還是應(yīng)用而言，退化圖像很難發(fā)揮其應(yīng)有的價值。因此，需要一種技術(shù)可以去除圖像中的模糊和噪聲，獲得清晰無噪聲的圖像（即所謂的原始圖像）。圖像復(fù)原正是在這種背景下出現(xiàn)的。圖像復(fù)原分為圖像盲復(fù)原和非盲的圖像復(fù)原，前者重建原始圖像時，同步對模糊進(jìn)行辨識；后者模糊是已知的，直接重建原始圖像。非盲的圖像復(fù)原算法主要有：基于總變分（Total Variation，TV）模型的算法、基于Bregman迭代的算法和基于稀疏表示的算法。TV范式||?·||1是TV模型[1]的關(guān)鍵，由于它的存在，基于TV模型的算法能有效保留復(fù)原圖像重要的信息，如邊緣、紋理等。但TV模型會導(dǎo)致圖像出現(xiàn)階梯效應(yīng)（staircase effects）[2]，且它是不可微分的，給數(shù)值計算帶來了困難。因此，一些高階的TV模型[3-4]被提出，一定程度上克服了TV模型固有的缺點。Bregman迭代法最早由S.Osher等人[5]引入圖像處理領(lǐng)域，主要針對TV正則化的圖像復(fù)原問題。近年來，在傳統(tǒng)Bregman迭代法的基礎(chǔ)上，衍生出了線性Bregman迭代法[6]和分裂Bregman迭代法[7]等。借助Bregman距離，Bregman迭代法可將圖像問題分解為等價的子問題求解。該類算法的優(yōu)點是速度快、所需的迭代次數(shù)少，且容易編程實現(xiàn)。作為近年來出現(xiàn)的新技術(shù)，稀疏表示在圖像復(fù)原領(lǐng)域已得到較廣泛的應(yīng)用。在稀疏表示的框架下，圖像被表示為字典矩陣各列的線性組合，圖像復(fù)原只需估計最優(yōu)的線性系數(shù)向量（即原始圖像的稀疏表示）。字典的選擇對該類算法非常重要，早期多用正交小波基分解表示圖像。為消除正交小波基給復(fù)原圖像帶來的塊效應(yīng)，M.A.T.Figueiredo等人[8]提出將超完備小波字典用于圖像復(fù)原。此后，超完備小波字典成為稀疏表示復(fù)原算法的主流選擇。小波變換的缺點是方向選擇性差，曲波（curvelet）、輪廓波（contourlet）等新的表示方法克服了這一缺點。越來越多的算法采用曲波、輪廓波等分解表示圖像，以獲得更好的圖像復(fù)原結(jié)果。正如F.X.Dupe等人[9]文章中所論述的，相比超完備的小波字典，這些新型的超完備字典更適用于圖像復(fù)原。雖然圖像復(fù)原時，許多優(yōu)秀的算法仍傾向于采用預(yù)先給定的字典，但J.Mairal等人指出，這些預(yù)先給定的字典無法適用所有類型的圖像，今后的算法將更多通過學(xué)習(xí)的方式獲得所需要字典[10-11]。

本文提出了一種快速高效的圖像復(fù)原算法，針對圖像復(fù)原，借助稀疏表示理論，建立了一種通用的包含雙正則項的復(fù)原問題模型。由于復(fù)原模型的目標(biāo)函數(shù)不可直接微分，利用交替優(yōu)化方法處理該模型，將其分解為更容易求解的子問題。最后通過實驗驗證該算法的有效性。

2 圖像復(fù)原建模及其算法

觀測圖像與原始圖像之間的關(guān)系可表示為：

式中，y∈Rm×1表示觀測圖像；線性算子A∈Rm×n表示模糊；x∈Rn×1表示原始圖像；n∈Rm×1是加性噪聲。觀測圖像y是已知的，原始圖像x是未知的，圖像復(fù)原的目的即獲得x的最優(yōu)估計，因此它屬于線性反問題，需要為其建立適合的問題表示模型。

2.1 圖像復(fù)原問題模型

本文為圖像復(fù)原問題建立了如下模型：

式中，c∈Rl×1表示原始圖像的稀疏表示；DT∈Rl×n表示超完備字典，可以是通過學(xué)習(xí)得到的也可以是預(yù)先指

定的；凸函數(shù)g1(x)和g2(c)為：

式中，μ1≥0，μ2≥0；L1范式 (||·||1)和L2范式 (||·||2)為目標(biāo)函數(shù)的正則項。一些常見的模型，如Tikhonov模型[12]、基追蹤降噪模型[13]和彈性網(wǎng)模型[14]等都可看做模型式（2）的特例。

由于目標(biāo)函數(shù)J(x，c)含有兩個未知量，優(yōu)化問題式（2）無法直接求解，為避免同時存在多個變量，采用交替優(yōu)化方法將式（2）分解為以下的子問題：

式中，λ≥0；k表示迭代次數(shù)。式（4）可直接求得：

因子問題式（4）的目標(biāo)函數(shù)是連續(xù)可微的凸函數(shù)，因此式（6）得到的是子問題式（4）的全局最優(yōu)解。當(dāng)式（6）中的DT是Parseval框架小波時，滿足DDT=I[15]，其中I表示單矩陣。

2.2 子問題式（5）的計算

由于L1范式的存在，子問題式（5）的目標(biāo)函數(shù)不可直接微分。利用迭代重加權(quán)（iterative reweighted）方法[16]對其處理，該子問題可表示為：

對于第k+1次迭代，fk(ck)為常數(shù)。式（8）中，wk為：

式中，t表示閾值函數(shù)；τ表示閾值，其定義為：

將式（8）代入式（7），直接可得：

綜上所述，本文提出的圖像復(fù)原算法如下：

其中，ε≥0表示容許誤差，是一個很小的常數(shù)。

3 實驗結(jié)果

不失一般性，實驗采用標(biāo)準(zhǔn)圖像cameraman作為原始圖像，如圖1所示，該圖像的分辨率為256×256。將圖2中的模糊核分別作用于原始圖像，在生成的模糊圖像中加入標(biāo)準(zhǔn)差為0.5的高斯噪聲，得到圖3（a）、圖 3（b）所示的退化圖像。圖3中，高斯退化圖像和運動退化圖像的峰值信噪比（Peak Signal-to-Noise Ratio，PSNR）分別是21.07 dB和21.65 dB，PSNR是衡量圖像質(zhì)量的客觀標(biāo)準(zhǔn)，一般PSNR值越大說明圖像的質(zhì)量越高。PSNR的定義為：

圖1 原始圖像

圖2 模糊核（放大顯示）

圖3 退化圖像

實驗選擇了Haar小波作為字典D，它是一種正交、緊支撐、對稱的小波，有助計算變得更簡單快速。參數(shù)的取值分別為：μ1=2.0E-3，μ2=1.0E-6，λ=2.5E-3。實驗所用仿真軟件為MATLAB R2011b，算法的運行環(huán)境為Windows XP SP3，2 GB內(nèi)存和2 GHz的雙核CPU。

本文所提算法被應(yīng)用于處理退化圖像，以驗證其有效性。同時與A.Levin等人[18]和D.Krishnan等人[19]提出的算法進(jìn)行比較，以評估本算法在速度和復(fù)原質(zhì)量等方面的性能。Levin等人提出的是基于圖像導(dǎo)數(shù)稀疏先驗的復(fù)原算法，Krishnan等人提出的是基于稀疏超拉普拉斯（hyper-Laplacian）先驗的圖像復(fù)原算法，這兩種算法均屬于稀疏表示算法。三種算法對退化圖像的復(fù)原結(jié)果如圖4所示，為保證復(fù)原結(jié)果的客觀性，表1給出了圖4中所有復(fù)原圖像相應(yīng)的PSNR值，以及復(fù)原所需的時間和迭代次數(shù)。表1中的時間是每個算法運行10次所需時間的平均值，Levin算法的結(jié)果是基于稀疏先驗得到的。

圖4 退化圖像復(fù)原結(jié)果

表1 退化圖像復(fù)原結(jié)果比較

圖5 本文算法的收斂情況

由表1和圖4的結(jié)果可看出，在復(fù)原圖像的質(zhì)量和復(fù)原速度方面，本文所提算法優(yōu)于Levin算法和Krishnan算法。僅需少量迭代，本文的算法即可獲得較理想的結(jié)果，這與該算法良好的整體架構(gòu)及子問題的處理策略有關(guān)。由于子問題計算的時間復(fù)雜度較低，加之Haar小波的簡單高效，本算法具有較好的時間性能。Levin算法利用迭代重加權(quán)最小二乘法和共軛梯度法處理圖像復(fù)原問題，所需共軛梯度迭代次數(shù)較多，限制了自身的速度。因此，圖像復(fù)原的速度明顯比本算法和Krishnan算法慢。上文已對本文算法的收斂性進(jìn)行了簡單分析，它在迭代過程中的實際收斂情況如圖5所示。由該圖可看出，在迭代過程中，||xk+1-x||2的值逐漸減小，說明本算法是不斷地收斂的，這與上文的分析一致。

4 結(jié)束語

作為線性反問題，圖像復(fù)原的難點在于提高復(fù)原質(zhì)量的同時提高速度。針對此問題，本文提出了一種新的算法。結(jié)合稀疏表示技術(shù)，建立圖像復(fù)原模型。在求解圖像復(fù)原模型時，選擇用交替優(yōu)化方法將其分解為子問題。對于不可微分的子問題，采用迭代重加權(quán)方法處理。相比較而言，子問題的求解比原問題更簡單。實驗對高斯模糊和運動模糊的cameraman圖像進(jìn)行復(fù)原，并且與Levin和Krishnan算法進(jìn)行比較，實驗結(jié)果驗證了本文算法的有效性，相比Levin和Krishnan算法，本文的算法在速度及復(fù)原質(zhì)量方面更具優(yōu)勢。

[1]Beck A，Teboulle M.Fast gradient-based algorithms for constrained total variation image denoising and deblurring problems[J].IEEE Transactions on Image Processing，2009，18（11）：2419-2434.

[2]Stefan W，Renaut R A，Gelb A.Improved total variationtype regularization using higher order edge detectors[J].SIAM Journal on Imaging Sciences，2010，3（2）：232-251.

[3]Goldfarb D，Yin W T.Second-order cone programming methods for total variation-based image restoration[J].SIAM Journal on Scientific Computing，2005，27（2）：622-645.

[4]Lysaker M，Tai X C.Iterative image restoration combining total variation minimization and a second-order functional[J].International Journal of Computer Vision，2006，66（1）：5-18.

[5]Osher S，Burger M，Goldfarb D，et al.An iterative regularization method for total variation-based image restoration[J].Multiscale Modeling&Simulation，2005，4（2）：460-489.

[6]Cai J F，Osher S，Shen Z W.Split bregman methods and frame based image restoration[J].Multiscale Modeling&Simulation，2009，8（2）：337-369.

[7]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.

[8]Figueiredo M A T，Nowak R D.A bound optimization approach to wavelet-based image deconvolution[C]//Proceedings of the IEEE International Conference on Image Processing.Piscataway，USA：IEEE Signal Processing Society，2005：782-785.

[9]Dupe F X，F(xiàn)adili J M，starck J L.A proximal iteration for deconvolving Poisson noisy images using sparse representations[J].IEEE Transactions on Image Processing，2009，18（2）：310-321.

[10]Mairal J，Elad M，Sapiro G.Sparse representation for color image restoration[J].IEEE Transactions on Image Processing，2008，17（1）：53-69.

[11]Mairal J，Sapiro G，Elad M.Learning multiscale sparse representations for image and video restoration[J].SIAM Journal on Multiscale Modeling&Simulation，2011，7（1）：214-241.

[12]Lorenz D A.Convergence rates and source conditions for Tikhonov regularization with sparsity constraints[J].Journal of Inverse and III-posed Problems，2008，16（5）：463-478.

[13]van den Berg E，F(xiàn)riedlander M P.Probing the Pareto frontier for basis pursuit solutions[J].SIAM Journal on Scientific Computing，2009，31（2）：890-912.

[14]Zou H，Hastie T.Regularization and variable selection via the elastic net[J].Journal of the Royal Statistical Society：Series B（Statistical Methodology），2005，67（2）：301-320.

[15]Mallat S.A wavelet tour of signal processing：the sparse way[M].3rd ed.New York：Academic Press，2008.

[16]Daubechies I，Devore R，F(xiàn)ornasier M，et al.Iteratively reweighted least squares minimization for sparse recovery[J].Communications on Pure and Applied Mathematics，2010，63（1）：1-38.

[17]Combettes P L，wajs V R.Signal recovery by proximal forward-backward splitting[J].Multiscale Modeling&Simulation，2005，4（4）：1168-1200.

[18]Levin A，F(xiàn)ergus R，Durand F，et al.Image and depth from a conventional camera with a coded aperture[J].ACM Transactions on Graphics，2007，26（3）.

[19]Krishnan D，F(xiàn)ergus R.Fast image deconvolution using hyper-laplacian priors[J].Advances in Neural Information Processing Systems，2009，22.

XIAO Su,HONG Liurong,SHEN Ke,ZHENG Ying

School of Computer Science and Technology,Huaibei Normal University,Huaibei,Anhui 235000,China

For rapidly and accurately restoring images,a novel image restoration algorithm is presented.In the framework of sparse representation,a new constrained optimization model is created,which enables the estimations of the original image and its sparse representation.The objective function of the model hasL1-L2regularized terms,thus the alternating optimization method is introduced to decompose the model into equivalent sub-problems.The non-differentiable one among sub-problems is handled by iterative reweighted method.The experimental results demonstrate that with only a few iterations,the presented algorithm can achieve optimal estimations of the original image and its sparse representation.Compared with some state-of-the-art algorithms,the presented algorithm shows to be faster,and obtains better results.

image restoration;alternating optimization;sparse representation;regularization;iteratively reweighted method

為快速且準(zhǔn)確地重建原始圖像，提出一種新的圖像復(fù)原算法。在稀疏表示的框架下，建立圖像復(fù)原問題的約束優(yōu)化模型，同步估計原始圖像及其稀疏表示。復(fù)原模型的目標(biāo)函數(shù)包含L1-L2雙正則項，為此采用交替優(yōu)化將模型分解為若干子問題，交替迭代求解這些子問題。其中不可微分的子問題，由迭代重加權(quán)方法進(jìn)行處理。實驗結(jié)果表明，僅需較少次迭代該算法即可獲得原始圖像及其稀疏表示的最優(yōu)估計。與某些優(yōu)秀的同類算法相比，該算法的速度更快，復(fù)原圖像的質(zhì)量更高。

圖像復(fù)原；交替優(yōu)化；稀疏表示；正則化；迭代重加權(quán)方法

2013-03-11

2013-04-27

1002-8331（2014）03-0125-04

A

TP391

10.3778/j.issn.1002-8331.1303-0128

國家自然科學(xué)基金（No.61070090）；安徽省高等學(xué)校省級自然科學(xué)研究項目（No.KJ2013B237）。

肖宿（1982—），男，博士，講師，研究領(lǐng)域為數(shù)字圖像復(fù)原；洪留榮（1969—），男，博士，教授，研究領(lǐng)域為模式識別與圖像處理；沈克（1975—），男，副教授，研究領(lǐng)域為數(shù)字圖像處理；鄭穎（1982—），女，講師，研究領(lǐng)域為數(shù)字圖像處理。E-mail：smartwindows@sohu.com