SL0分類稀疏表示的圖像修復(fù)算法

屠雅麗，唐向宏，張　東，蔡倩，任玉升

(1.杭州電子科技大學(xué)通信工程學(xué)院，浙江 杭州 310018；2.浙江水利水電學(xué)院電氣工程學(xué)院，浙江 杭州 310018)

?

SL0分類稀疏表示的圖像修復(fù)算法

屠雅麗1，唐向宏1，張東1，蔡倩1，任玉升2

(1.杭州電子科技大學(xué)通信工程學(xué)院，浙江 杭州 310018；2.浙江水利水電學(xué)院電氣工程學(xué)院，浙江 杭州 310018)

將SL0算法應(yīng)用于圖像修復(fù).在傳統(tǒng)的SL0算法基礎(chǔ)上，采用近似雙曲正切函數(shù)去近似l0范數(shù)，利用共軛梯度法求解該函數(shù)，實(shí)現(xiàn)高精度的重構(gòu)，提出一種利用SL0算法的分類稀疏表示圖像修復(fù)算法.算法首先將圖像分塊，并根據(jù)圖像塊的梯度信息和局部方差依次對(duì)圖像塊進(jìn)行分類；然后分別對(duì)每一類圖像塊樣本用K-SVD字典訓(xùn)練得到相對(duì)應(yīng)的過完備字典；最后利用改進(jìn)的SL0算法進(jìn)行圖像修復(fù).仿真實(shí)驗(yàn)結(jié)果表明，算法對(duì)圖像修復(fù)后的質(zhì)量有較大的提高，更符合人眼視覺效應(yīng).

SL0；K-SVD；梯度；局部方差；分類訓(xùn)練

0　引　言

數(shù)字圖像修復(fù)是根據(jù)破損圖像中的已知信息，利用算法對(duì)圖像破損區(qū)域進(jìn)行修復(fù)的過程.經(jīng)典的修復(fù)算法有基于偏微分方程的圖像修復(fù)算法[1]和基于樣本塊的圖像修復(fù)算法[2].除此之外，基于稀疏表示理論的數(shù)字圖像修復(fù)成為近年來研究的熱點(diǎn).文獻(xiàn)[3]將待修復(fù)圖像中的所有已知圖像塊作為字典，對(duì)待修復(fù)的圖像塊進(jìn)行稀疏重構(gòu)，但該算法字典的自適應(yīng)性不足.為此，文獻(xiàn)[4]采用聚類和分類相結(jié)合的方式對(duì)圖像塊進(jìn)行特征分類，針對(duì)不同特征的樣本圖像塊進(jìn)行字典訓(xùn)練，提高了字典的自適應(yīng)能力.

重構(gòu)算法是基于稀疏表示的圖像修復(fù)中至關(guān)重要的一環(huán)，由于正交匹配追蹤(Orthogonal Matching Pursuit，OMP)算法[5]的原理簡(jiǎn)單且十分易于實(shí)現(xiàn)，因此成為主流的重構(gòu)算法，并廣泛應(yīng)用于基于稀疏表示的圖像修復(fù)算法中.但該算法在重構(gòu)時(shí)往往需要預(yù)估信號(hào)的稀疏度，無論稀疏度估計(jì)過小或者過大都不能達(dá)到較好的重構(gòu)效果.而平滑l0范數(shù) ( Smoothedl0Norm，SL0)[6]則可以避免該問題，不需要事先估計(jì)信號(hào)的稀疏度.SL0算法是要尋求一個(gè)連續(xù)函數(shù)去逼近l0范數(shù)，并求解該函數(shù)的最小值.它是一種近似l0范數(shù)的稀疏重構(gòu)算法，相比于OMP算法具有高重構(gòu)率、不用預(yù)估信號(hào)稀疏度等優(yōu)點(diǎn)，可以很好地應(yīng)用于基于稀疏表示的圖像修復(fù)中.因此，本文在傳統(tǒng)的SL0算法的基礎(chǔ)上，采用近似雙曲正切函數(shù)去近似l0范數(shù)，并采用共軛梯度法求解該函數(shù)最小值以減少鋸齒現(xiàn)象，從而實(shí)現(xiàn)高精度的重構(gòu).

1　稀疏表示的圖像修復(fù)模型

假設(shè)信號(hào)x∈RN，其可用一組基線性表示，稀疏問題即找到一個(gè)最佳稀疏表示為[7]：

(1)

(2)

式中，ε≥0表示一定的誤差容限.通過正則化方法和參數(shù)λ來平衡稀疏性和稀疏誤差，得到稀疏問題的表達(dá)式為：

(3)

由于式(3)為NP難問題，計(jì)算量非常大，無法得到最優(yōu)解，因此需要一個(gè)有效的編碼算法來求解上述問題.

2　算法原理及實(shí)現(xiàn)

本算法的基本思路是：首先將圖像分塊，根據(jù)圖像塊的梯度信息和局部方差依次對(duì)圖像塊進(jìn)行分類；然后分別對(duì)每一類圖像塊樣本用K-SVD字典訓(xùn)練得到相對(duì)應(yīng)的過完備字典；最后，實(shí)現(xiàn)SL0重構(gòu)算法對(duì)圖像的修復(fù).

2.1圖像塊特征分類

為了增強(qiáng)學(xué)習(xí)字典的自適應(yīng)能力，本文采用結(jié)合圖像塊梯度信息和局部方差的方法對(duì)圖像進(jìn)行特征分類.令圖像中任意位置(x,y)的像素值為f(x,y)，其上下左右4個(gè)方向的梯度值分別為：

(4)

取這4個(gè)方向上的最大梯度值為該像素點(diǎn)的權(quán)值g(x,y)，將每個(gè)圖像塊(大小為n×n)內(nèi)的每個(gè)像素進(jìn)行梯度加權(quán)，其大小為：

(5)

設(shè)定一個(gè)閾值T，其中T為經(jīng)驗(yàn)常數(shù)，一般取100.當(dāng)uk

第k個(gè)圖像塊的局部方差為：

(6)

圖1　圖像分類結(jié)果

再根據(jù)K-SVD[8]算法，即可得到3種不同類別圖像樣本塊所對(duì)應(yīng)的自適應(yīng)字典：不規(guī)則紋理字典Dt、平滑字典Ds和邊緣結(jié)構(gòu)字典De.

2.2SL0重構(gòu)算法及其改進(jìn)

重構(gòu)算法在基于稀疏表示的圖像修復(fù)中起著舉足輕重的作用，重構(gòu)效果的好壞直接影響圖像修復(fù)的質(zhì)量.SL0算法是近似l0范數(shù)的一種稀疏重構(gòu)算法，其原理是尋找一個(gè)連續(xù)函數(shù)去近似l0范數(shù)，并采用一定的方式去逼近函數(shù)最優(yōu)解，其數(shù)學(xué)模型如式(1)所示.

(7)

則

(8)

(9)

式中：σ表示高斯函數(shù)的標(biāo)準(zhǔn)差.但該連續(xù)函數(shù)的“陡峭性”不夠明顯，不能準(zhǔn)確的逼近l0范數(shù).因此本文利用下式的近似雙曲正切函數(shù)作為近似估計(jì)l0范數(shù)的函數(shù).

(10)

最速下降法的搜索方向?yàn)楹瘮?shù)的負(fù)梯度方向，越接近目標(biāo)值，步長(zhǎng)越小，前進(jìn)越慢，在求解過程中存在鋸齒效應(yīng)，使得l0范數(shù)估計(jì)的準(zhǔn)確性降低.而共軛梯度法的搜索方向?yàn)樨?fù)梯度方向與上一次迭代的搜索方向的線性組合，可以解決最速下降法帶來的鋸齒效應(yīng).兩類方法迭代過程如圖3所示.

圖2　高斯函數(shù)和近似雙曲正切函數(shù)比較

圖3　最速下降法和共軛梯度法迭代過程示意圖

利用SL0算法的分類稀疏表示圖像修復(fù)流程如圖4所示，其算法實(shí)現(xiàn)步驟如下：

1) 令初始值分別為X=DT(DDT)-1Y,σ1=2max(X)，k=1(k用于計(jì)算σk大小的循環(huán)變量)；

圖4　本文算法流程圖

(2)X←X+μdn，其中步長(zhǎng)因子μ=1.5；

(4)n=n+1,j=j+1,如果j

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

為了驗(yàn)證所使用方法的性能，在計(jì)算機(jī)上對(duì)小面積和大面積破損區(qū)域修復(fù)進(jìn)行了仿真實(shí)驗(yàn)，并將改進(jìn)SL0算法的圖像修復(fù)效果與傳統(tǒng)SL0算法的圖像修復(fù)效果、文獻(xiàn)[3]、文獻(xiàn)[4]的圖像修復(fù)效果進(jìn)行了比較分析.在對(duì)圖像修復(fù)效果評(píng)價(jià)時(shí)，除了采用主觀評(píng)價(jià)外，同時(shí)也采用峰值信噪比(PSNR)進(jìn)行客觀評(píng)價(jià)[4].

仿真實(shí)驗(yàn)在MATLAB環(huán)境中進(jìn)行，其中圖像塊的大小取為7×7.在仿真實(shí)驗(yàn)中，利用BABOON、BARB、LENA等標(biāo)準(zhǔn)圖像進(jìn)行破損修復(fù)處理，下面給出部分仿真結(jié)果.

從圖5，圖6和圖7可以看出，4種圖像修復(fù)算法對(duì)平滑區(qū)域的修復(fù)效果均十分理想；前3種算法在對(duì)不規(guī)則紋理區(qū)域和邊緣區(qū)域修復(fù)后產(chǎn)生了不同程度的模糊以及延伸現(xiàn)象，修復(fù)效果不自然，而本文算法在這兩種區(qū)域的修復(fù)效果符合人眼視覺規(guī)律.

如圖7所示，對(duì)LENA圖像修復(fù)后，在其帽頂、眉毛和嘴角等部分(畫黑圈部分)，4種算法在修復(fù)時(shí)均出現(xiàn)一定程度的不自然延伸或模糊現(xiàn)象，這些部分屬于“弧形”邊緣或紋理復(fù)雜區(qū)域，本文算法對(duì)這部分區(qū)域的修復(fù)不夠理想.

圖5　BABOON修復(fù)效果圖

圖6　BARB圖修復(fù)效果圖

圖7　LENA修復(fù)效果圖

表1給出了仿真實(shí)驗(yàn)中4種算法的PSNR值和耗時(shí)情況.從表1中可以看出，本文算法在修復(fù)時(shí)間上與傳統(tǒng)SL0修復(fù)算法相比相差不大，卻是文獻(xiàn)[3]和文獻(xiàn)[4]算法的2～3倍，這是由于文獻(xiàn)[3]和文獻(xiàn)[4]均采用OMP算法對(duì)圖像進(jìn)行修復(fù)，而OMP算法簡(jiǎn)單復(fù)雜度較低，使得修復(fù)時(shí)間較短；本文算法的PSNR 值相比傳統(tǒng)SL0算法均提高1 dB左右，而相比文獻(xiàn)[3]和文獻(xiàn)[4]要提高1.5～2 dB左右，即本文算法在修復(fù)質(zhì)量上有較大的提升.

表1　4種算法PSNR與消耗時(shí)長(zhǎng)的比較

4　結(jié)束語(yǔ)

本文提出一種利用SL0分類稀疏表示的圖像修復(fù)算法.仿真實(shí)驗(yàn)結(jié)果表明，本文方法綜合性能較好，修復(fù)后的圖像質(zhì)量有較大的提升，可以有效修復(fù)圖像結(jié)構(gòu)邊緣、不規(guī)則紋理和平滑區(qū)域的圖像信息.但SL0算法在修復(fù)時(shí)耗時(shí)比較長(zhǎng)對(duì)復(fù)雜紋理以及“弧形”邊緣破損區(qū)域的修復(fù)不夠理想，有待改進(jìn).

[1]BERTALMIO M,SAPIRO G, CASELLES V,et al.Image inpainting[J].Proceedings of Annual Conference on Computer Graphics & Interactive Techniques,2002,4(9):417-424.

[2]CRIMINISI A,PEREZ P,TOYAMA K.Object Removal by Exemplar-Based Inpainting[C]//IEEE Computer Society Conference on Computer Vision and Pattern Recognition,2003:721-728.

[3]XU Z,SUN J.Image inpainting by patch propagation using patch sparsity[J].IEEE Transactions on Image Processing,2010,19(5):1153-1165.

[4]康佳倫.基于FMM和稀疏表示圖像修復(fù)算法的研究[D].杭州:杭州電子科技大學(xué),2013.

[5]TROPP J A,GILBERT A C.Signal Recovery from partial information via orthogonal matching pursuit[J].IEEE Transactions on Information Theory,2007,53(12):4655-4665.

[6]MOHIMANI H,BABAIE-ZADEH M,JUTTEN C.A fast approach for overcomplete sparse decomposition based on smoothed l0norm[J].IEEE Transactions on Signal Processing, 2009,57(1):289-301.

[7]DONOHO D L,HUO X.Uncertainty principles and ideal atomic decomposition[J].IEEE Transactions on Information Theory,2001,47(7):2845-2862.

[8]AHARON M,ELAD M,BRUCKSTEIN A.K-SVD:An Algorithm for Designing Over-complete Dictionaries for Sparse Representation[J].IEEE Transaction on Signal Processing,2006,54(11):4311-4322.

Classified Sparse Representation of Image Inpainting by SL0 Algorithm

TU Yali1, TANG Xianghong1, ZHANG Dong1, CAI Qian1, REN Yusheng2

(1.SchoolofCommunicationEngineering,HangzhouDianziUniversity,HangzhouZhejiang310018,China;2.SchoolofElectricalEngineering,ZhejiangUniversityofWaterResourcesandElectricPower,HangzhouZhejiang310018,China)

This paper proposes a novel image inpainting algorithm by SL0 algorithm. Based on traditional SL0 algorithm, it takes use of approximate hyperbolic tangent function to approachl0norm and uses conjugate gradient to solve this function, which are helpful to improve the reconstructive accuracy. The proposed algorithm firstly divides the damaged image into blocks and classifies them in turn through the gradient information and local variance of image block; then trains the each type image block samples with K-SVD to get the corresponding over complete dictionary; finally, utilizes the modified SL0 algorithm to image inpainting. The experiment results show that the proposed algorithm in image inpainting is greatly improved the image quality and the images are more in accordance with visual effect.

SL0; K-SVD; gradient; local variance; classified train

10.13954/j.cnki.hdu.2016.01.007

2015-05-21

屠雅麗(1991-)，女，浙江寧波人，在讀研究生，數(shù)字圖像修復(fù).通信作者：唐向宏教授，E-mail：tangxh@hdu.edu.cn.

TP391

A

1001-9146(2016)01-0032-05