江 平， 張 錦

(合肥工業(yè)大學(xué)數(shù)學(xué)學(xué)院，安徽 合肥 230009)

基于平行坐標(biāo)下降法的圖像修復(fù)

江 平， 張 錦

(合肥工業(yè)大學(xué)數(shù)學(xué)學(xué)院，安徽 合肥 230009)

以壓縮傳感和稀疏表示為理論依據(jù)，提出了一種基于平行坐標(biāo)下降法的圖像修復(fù)模型。該模型用小波變換作為圖像的稀疏表示，以稀疏性作為正則化項；同時基于松弛閾值來標(biāo)記函數(shù)實現(xiàn)全局優(yōu)化，并采用該模型算法得到全局最優(yōu)解。從峰值信噪比、收斂速度和視覺效果等3個方面驗證了算法的有效性。結(jié)果表明新的模型無論是在客觀還是視覺主觀上都有更好的效果，同時算法具有更快的收斂速度。

稀疏表示；圖像修復(fù)；平行坐標(biāo)下降法；閾值

數(shù)字圖像修復(fù)是由Bertalmio等[1]于2000年提出，指利用圖像中已有的信息，根據(jù)一定的算法或規(guī)則對破損區(qū)域進(jìn)行修復(fù)或者目標(biāo)物體的去除，以達(dá)到良好的視覺效果。近年來，數(shù)字圖像修復(fù)技術(shù)得到快速發(fā)展，并廣泛應(yīng)用于文物的保護(hù)、多余物的剔除、影視特技的制作、圖像壓縮、視頻圖像差錯隱藏等領(lǐng)域，已成為數(shù)字圖像處理領(lǐng)域的一個重要分支。

現(xiàn)有的圖像修復(fù)可分為基于偏微分方程(partial differential equation，PDE)的修復(fù)算法、基于樣本塊的紋理合成修復(fù)算法、混合方法以及基于稀疏表示的方法。文獻(xiàn)[2-4]采用非線性偏微分方程的方法，將待修復(fù)區(qū)域周圍的已知信息通過逐漸擴散來修復(fù)圖像中的待修復(fù)區(qū)域，該類算法考慮的是圖像的幾何結(jié)構(gòu)信息，本質(zhì)上都是一種擴散過程，但是修復(fù)大面積區(qū)域時效果明顯變差；文獻(xiàn)[5]提出的Criminisi算法，以基于塊的紋理合成技術(shù)來修復(fù)破損區(qū)域，首先待修復(fù)區(qū)域分塊，然后按照優(yōu)先級公式計算出修補順序，最后在圖片中尋找與待修復(fù)區(qū)域塊最相近的塊將其填補，以達(dá)到修復(fù)的目的，對大面積破損圖像的修復(fù)效果較好；文獻(xiàn)[6-8]將圖像分解為幾何結(jié)構(gòu)分量與紋理分量，分別對這兩個分量進(jìn)行修補和合成，在一定程度上改善了圖像的修復(fù)效果，但是仍不可避免的存在結(jié)構(gòu)模糊或塊效應(yīng)等缺點；文獻(xiàn)[9-11]是基于稀疏重構(gòu)和迭代去噪技術(shù)在圖像修復(fù)上的應(yīng)用，在迭代過程中使用經(jīng)典的去噪理論，估計圖像修復(fù)區(qū)域的最優(yōu)解，該方法理論上可獲得局部最優(yōu)解，具有一定的魯棒性；Elad等[7]以壓縮理論為基礎(chǔ)，采用形態(tài)成分分析(morphological component analysis，MCA)將圖像分解為結(jié)構(gòu)和紋理兩部分，通過分別重構(gòu)圖像的結(jié)構(gòu)和紋理部分來實現(xiàn)修復(fù)，最后將兩部分重建結(jié)果相加得到修復(fù)圖像。

近年來，迭代收縮方法正在逐步建立，對于處理最優(yōu)化問題非常有效，它擴展了信號去噪的經(jīng)典的 Donoho-Johnston[12]收縮方法，并且 Elad等[13]證明了這個算法的收斂性，保證了這個算法的解對于凸面的整體最小化。在迭代收縮算法中分 離 代 理 函 數(shù) 算 法 (separableSurrogate functionals，SSF)和平行坐標(biāo)下降法(paralle coordinate descent，PCD)彼此很接近，不同的是SSF算法中的有個常量c，PCD算法用了同樣的方式但是用的是重要矩陣 (ATA)-1所提出的對角元素，因此，PCD算法的效果較好。本文把SSF算法和PCD算法分別用于圖像修復(fù)，希望PCD算法對修復(fù)效果仍然較好。

鑒于稀疏理論在圖像處理領(lǐng)域的優(yōu)勢，本文把稀疏表示、PCD算法與圖像修復(fù)結(jié)合起來，使得修復(fù)的過程是一個迭代收縮的過程，每迭代一次進(jìn)行一次線性收縮，直到缺失區(qū)域修復(fù)結(jié)果趨于穩(wěn)定。

1 稀疏表示

設(shè)信號 x ∈Rn可由預(yù)定原子的線性組合表示，則x的稀疏表示問題為[7]：

2 基于PCD的圖像修復(fù)算法

圖像修復(fù)是將圖像中丟失的信息(像素)進(jìn)行補全的過程。在有噪聲的情況下，圖像修復(fù)還伴隨著噪聲的去除。噪聲情況下，原圖像(信息完整圖像)與觀測圖像(待修復(fù)圖像)關(guān)系描述如下[14]：

假設(shè)已經(jīng)知道第k次迭代值 zk，想要更新其第j個值 zk(j)，保持其余的不變。因此，得到一個1- D的優(yōu)化形式：

其中， aj表示A的第j列，Azk-ajzk(j )用當(dāng)前的值來更新所有的系數(shù)，第j個值用z來代替。因為這是一個1-D優(yōu)化問題，相對還是比較容易解決的。如設(shè)，對式(2)中的z求導(dǎo)得到：

進(jìn)而可得：

類似這樣的收縮過程，ρ (?)可以選擇任意函數(shù)，本文取：

它的一階導(dǎo)和二階導(dǎo)分別為：

所以，ρ (?)是一個二階可導(dǎo)且嚴(yán)格凸的函數(shù)，其有著類似平滑的功能。

上述的過程每次沿不同的方向更新一個系數(shù)，循環(huán)更新，直到得到滿意解，稱之為坐標(biāo)下降法(coordinate descent algorithm，CD算法)。

由于CD算法更新緩慢，而且要用到字典的單個原子 aj，計算效率低下，所以Elad等[13]提出在已知當(dāng)前值 zk的情況下，用上面的算法并行更新所有的系數(shù)，代替一次次的更新。

首先，使v(A,y,zj,j )，成一個向量形式，一次更新所有系數(shù)，即：

ATA的對角陣的提取是由矩陣A的列向量的標(biāo)準(zhǔn)基所組成的。然而 CD算法每個方向都保證了下降，它的非負(fù)線性組合也是下降的，因此，考慮它的一個線性搜索：

μ沿線性搜索：

這里 hk是可計算的向量，得到計算μ的方程[15]：

這種方法可以解決式(1)的問題，每一次迭代，同時也是一次收縮。定義第k次迭代值為通過計算λ?diag-1{ATA}?1和沿線性下降方向來更新[16]。

3 算法步驟

綜上分析，用PCD算法求解稀疏化的圖像修復(fù)模型算法流程如下：

步驟1. 讀入一幅待修復(fù)圖像y，提取掩膜信息M；

步驟2. 利用小波變換得到冗余字典，并對圖像進(jìn)行稀疏化；

步驟3. 初始化迭代次數(shù) k=1， zk=0線性收縮系數(shù) μ= 0.1，閾值 threshold= 0.1，參數(shù) s=1、λ= 0.1及算法終止參數(shù)ε；

步驟4. 通過對圖像的小波變換稀疏化閾值threshold；

步驟5. 計算 v(A,y,zj,j )，下降方向 hk，系數(shù)μ；

步驟6. 代入 zk+1= zk+μhk中，計算得到 zk+1；

步驟7. 閾值松弛threshold=threshold×0 .7；

步驟 9. 輸出，將會得到最優(yōu)系數(shù) zopt，代入xopt=Azopt，即可得到修復(fù)后的圖像。

4 數(shù)值實驗與分析

本文實驗用Matlab 2009 b作為工具，在Intel酷睿5處理器(2.67 GHz)，4 G內(nèi)存的PC機上實現(xiàn)的。

為了驗證算法的有效性，以Lena、Peppers 兩幅圖為例進(jìn)行性能測試。引入SSF算法，增加線性搜索的SSF算法[13](記為：SSF-LS算法)和固定μ的PCD算法(μ=0.5)與本文算法進(jìn)行比較，從峰值信噪比(peakSignal to noise ratio，PSNR)、迭代次數(shù)和視覺效果3個方面進(jìn)行。

圖 1為修復(fù)刮痕損壞的 Lena圖像效果圖，圖1(d)~(f)從視覺效果上看相差無幾，但是達(dá)到算法的迭代終止條件圖1(f)只需迭代23次，而圖1(d)需迭代25次，圖1(e)需迭代26次，而且圖1(f)的PSNR高于其他算法，說明線性搜索的PCD算法收斂速度較快，效果較好。具體數(shù)據(jù)見表1。

圖1 Lena修復(fù)效果圖

表1 Lena圖像各修復(fù)算法迭代次數(shù)和PSNR比較

圖2 peppers修復(fù)效果圖

圖2為去除Peppers圖像中的英文字母，從表2中可以看出，雖然SSF算法和PCD算法達(dá)到終止條件時的迭代次數(shù)一樣，但是PCD算法修復(fù)得到的圖像比SSF-LS算法修復(fù)得到的圖像PSNR高出0.31 dB，說明PCD算法的修復(fù)效果較好。具體數(shù)據(jù)見表2。

表2 pepperes圖像各修復(fù)算法迭代次數(shù)和PSNR比較

5 結(jié) 束 語

本文提出基于PCD算法來修復(fù)圖像，該算法用小波變換作為圖像的稀疏表示，通過閾值收縮確定下降方向，用線性搜索的方法來確定每次下降的步長，然后進(jìn)行迭代求解。采用不同的圖像進(jìn)行實驗驗證，結(jié)果表明本文算法能夠較好地修復(fù)圖像，獲得較好的視覺效果。本文算法對小缺損圖像進(jìn)行修復(fù)時能取得較好的修復(fù)效果，但是對修復(fù)區(qū)域較大的圖像效果較差，需要繼續(xù)研究。

[1] BertalmioM,Sapiro G, Caselles V, et al. Image inpainting [C]//Proceedings ofSIGGRAPH. New York, USA, 2000:417-424.

[2] Chan T F,Shen Jianhong.MathematicalModels for local non-texture inpainting [J].SIAM Journal on AppliedMathematics, 2002, 62(3): 1019-1043.

[3] Rudin L I, OsherS, Faterni E. Nonlinear total variation based noise removal algorithms [J]. Physica D Nonlinear Phenomena, 1992, 60: 259-268.

[4] Chan T F,Shen Jianhong. Non-texture inpainting by curvature-driven diffusions (CDD) [J]. Journal of Visual Communication and Image Representation, 2001, 12(4):436-449.

[5] Criminisi A, Perez P, Toyam K. Region filling and object removal by exemplar-based image inpainting [J]. IEEE Transactions on Image Processing, 2004, 13(9): 1200-1212.

[6] BertalmioM, Vese L,Sapiro G, et al.SimultaneousStructure and texture image inpainting [J]. IEEE Transactions on Image Processing, 2003, 12(8): 882-889.

[7] EladM,Starck J-L, Querre P, et al.Simultaneous cartoon and texture image inpainting usingMorphological component analysis (MCA) [J]. Applied and Computational Harmonic Analysis, 2005, 19(3): 340-358.

[8] 黃江林, 劉 紅, 陶少杰. 一種改進(jìn)的基于K-SVD字典的圖像修復(fù)算法[J]. 安徽大學(xué)學(xué)報：自然科學(xué)版, 2013, 37(3): 69-74.

[9] Guleryuz O G. Nonlinear approximation based image recovery using adaptiveSparse reconstructions and iterated denoising-part I: theory [J]. IEEE Transactions on Image Processing, 2006, 15(3): 539-554.

[10] FadiliM J,Starck J L,Murtagh F. Inpainting and zooming usingSparse representations [J]. The Computer Journal Advance Access, 2007, (6): 1-16.

[11]Mairal J, EladM,Sapiro G.Sparse representation for color image restoration [J]. IEEE Transactions on Image Processing, 2008, 17(1): 53-69.

[12] Donoho D L. De-noising bySoft thresholding [J]. IEEE Transactions on Information Theory, 1995,41(3): 613-627.

[13] EladM,Matalon B, ZibulevskyM. Coordinate andSubspace optimizationMethods for linear leastSquares with non-quadratic regularization [J]. Applied and Computational Harmonic Analysis, 2007, 23(3): 346-367.

[14] 鄧承志, 劉娟娟, 汪勝前，等. 保留結(jié)構(gòu)特征的稀疏性正則化圖像修復(fù)[J]. 光學(xué)精密工程, 2013, 21(7): 1906-1913.

[15] Tropp J A, WrightS J. ComputationalMethods forSparseSolution of linear inverse problems [J]. Proceeding of the IEEE, 2010, 98(6): 948-958.

[16] EladM. WhySimpleShrinkage isStill relevant for redundant representations? [J]. IEEE Transactions on Information Theory, 2006, 52(12): 5559-5569.

Image Inpainting Based on Parallel Coordinate DescentMethod

Jiang Ping, Zhang Jin
(School ofMathematics, Hefei University of Technology, Hefei Anhui 230009, China)

Based on the compressedSensing andSparse representation theory, and on the parallel coordinate descent an image inpaintingModelMethod is proposed, which uses theMethod of wavelet transform for imageSparse representation, withSparse as the regularization term, and at theSame time, realizes global optimization based on the threshold of relaxation toMark function. The global optimalSolution can be obtained by using PCD. The proposed algorithm is verified from the peakSignal to noise ratio of convergenceSpeed and visual effect. The resultsShow that the newModel has better effect in both objective andSubjective, and at theSame time has faster convergenceSpeed.

Sparse representation; image inpainting; parallel coordinate descentMethod; threshold

TP 391

A

2095-302X(2015)02-0222-05

2014-10-08；定稿日期：2014-10-24

國家自然科學(xué)基金面上項目(11471093)；中央高校基本科研業(yè)務(wù)費專項資助項目(J2014HGXJ0077)

江 平(1972–)，女，安徽安慶人，副教授，博士。主要研究方向為CAGD、圖像處理。E-mail：jiang_hfut@126.com