林金勇,鄧德祥,顏 佳,林曉英

1.武漢大學 電子信息學院,武漢 430072; 2.北京郵電大學 電子工程學院,北京 100876)(*通信作者電子郵箱ljy609@whu.edu.cn)

基于自適應相似組稀疏表示的圖像修復算法

林金勇1*,鄧德祥1,顏 佳1,林曉英2

1.武漢大學 電子信息學院,武漢 430072; 2.北京郵電大學 電子工程學院,北京 100876)(*通信作者電子郵箱ljy609@whu.edu.cn)

針對圖像修復結果中存在的結構連續(xù)性和紋理清晰性較差的問題,提出了一種基于自適應相似組的圖像修復算法。區(qū)別于傳統(tǒng)的以單一圖像塊或固定數(shù)目圖像塊作為修復單元的方法,該算法根據(jù)自然圖像中紋理區(qū)和結構區(qū)的不同特點,自適應地選取不同數(shù)目的相似圖像塊,構造自適應相似組；然后以相似組作為基本單元,學習自適應字典,并構造基于稀疏表示的圖像修復模型；最后,采用Split Bregman Iteration算法高效地求解目標代價函數(shù)。實驗結果表明,與基于圖像塊的圖像修復算法和圖像塊組稀疏表示(GSR)算法相比,該算法在峰值信噪比(PSNR)上平均提高了0.94～4.34 dB,在結構相似性指數(shù)(SSIM)上平均提高了0.006 9～0.034 5,同時,修復速度分別是對比算法的2.51倍和3.32倍。

圖像修復;稀疏表示;自適應相似組;學習字典;自適應性

0 引言

圖像修復指的是利用先驗信息對圖像中信息缺失的區(qū)域進行修正,以達到視覺上合理的效果[1]。圖像修復是圖像處理領域中一個重要的研究方向,其研究成果已經(jīng)得到了廣泛的運用,包括文物保護、文字去除、影視效果制作等方面。目前的圖像修復方法主要分為兩大類:基于偏微分方程的方法和基于紋理合成的方法。

基于偏微分方程的圖像修復算法利用待修復區(qū)域邊緣的信息估計等值線的方向,然后將待修復區(qū)域周圍的信息傳播到待修復區(qū)中[2-3],這類方法是基于像素級的操作,對于大面積的待修復區(qū),會出現(xiàn)過平滑和模糊的現(xiàn)象?；诩y理合成的圖像修復算法以圖像塊為基本修復單元[4-8],Criminisi等[6]通過尋找最佳匹配圖像塊,替換待修復圖像塊,該方法能夠有效地修復大面積受損區(qū)域,但是往往造成結構上的不連續(xù)性。文獻[9]在Criminisi的基礎上改進了待修復圖像塊的優(yōu)先級,并對待修復圖像塊進行稀疏表達。Mairal等[10]提出了一種基于非局部稀疏表示的圖像修復方法,將字典學習和稀疏編碼合并在統(tǒng)一的框架中。

為了更充分地利用自然圖像中的先驗信息,文獻[11-12]擴展了圖像塊的概念,提出了以相似圖像塊組作為基本修復單元,并且分別在圖像修復和圖像去噪中取得了明顯的效果。但是它們都是根據(jù)固定數(shù)目的相似圖像塊,構造尺寸固定的組,因此不能有效地區(qū)分自然圖像中的結構區(qū)和紋理區(qū)。本文在此基礎上,進一步提出了自適應相似組的概念,并以此作為稀疏表示的基本單元。為了更準確地描述圖像塊之間的相似性,本文采用結構相似性指數(shù)[13]作為圖像塊相似性的判別準則。最后,通過實驗對算法進行驗證,表明該算法具有較強的自適應性,能夠有效地進行圖像修復。

1 算法描述

1.1 自適應相似組

(1)

其中:μx、μy是亮度均值作為亮度估計；σx、σy是標準方差作為對比度估計。結構相似性指數(shù)越大,表明x和y的相似性越高。

將所有圖像塊均表示成向量的形式Ψk∈Rβ,其相似圖像塊集合Sk可以表示成矩陣的緊湊形式Gk∈Rβ×nk,則稱Gk為圖像塊Ψk的一個相似組。在自然圖像中,位于紋理區(qū)的圖像塊具有較多的相似圖像塊,而位于結構區(qū)的圖像塊則具有較少的相似圖像塊[9],因此,不同的待修復圖像塊Ψk將對應不同尺寸的相似組Gk,即所構造的相似組是自適應的。定義Gk=Rk(I)為從圖像I中提取相似組Gk(k=1,2,…,N)的操作,則相似組的構造過程如圖1所示。

圖1 自適應相似組的構造

1.2 稀疏表示模型

給定集合Dk={dk,1,dk,2,…,dk,nk},其元素dk,m(m=1,2,…,nk)為與相似組Gk相同尺寸大小的矩陣,即dk,m∈Rβ×nk,稱集合Dk為字典,元素dk,m為原子。根據(jù)稀疏表示理論,對任意給定的相似組Gk∈Rβ×nk,都能用字典Dk中原子的線性組合近似表示,即:

(2)

對圖像I中的所有相似組Gk(k=1,2,…,N),進行上述的稀疏表達,使得圖像I可以僅由各字典中的少量原子的線性組合進行較好的重構:

(3)

考慮到系數(shù)向量的稀疏性,則基于稀疏表示的圖像修復問題可表述為求解優(yōu)化問題[7]:

min ‖α‖0

s.t. ‖MI-F‖<ε

(4)

其中:α表示N個系數(shù)向量的集合{αk|k=1,2,…,N}；M為不可逆的圖像降質(zhì)操作(這里用模板矩陣表示該操作)；I為原始圖像；F為受損圖像；ε為一個極小的誤差容忍閾值。MI表示兩個矩陣的點乘,是對原始圖像進行降質(zhì)。

將式(3)代入式(4),可以得到稀疏表示數(shù)學模型:

(5)

1.3 自適應字典學習

稀疏表示的主要目標是得到原始信號在字典上最稀疏的表示,即信號可以僅由字典中的少數(shù)原子的線性組合近似表示[7],因此,構造合適的字典是在稀疏表示框架下進行圖像修復的關鍵[12]。本文提出一種學習自適應字典的方法,區(qū)別于傳統(tǒng)的學習字典,該方法為每個相似組構造不同的字典,因此具有較強的自適應能力。

考慮到在圖像修復的過程中,原始圖像I是未知的,無法直接通過原圖得到相似組Gk,所以采用Gk的估計量rk進行字典學習,rk的具體含義將在第2章優(yōu)化部分詳細討論。通過對rk進行奇異值分解(Singular Value Decomposition, SVD),得到:

(6)

(7)

基于上述方法構造的字典具有較強的自適應能力,能夠有效地對原始信號進行表達,其自適應性主要體現(xiàn)在三個方面:1)字典直接從圖像信號中學習得到,反映圖像的本質(zhì)特征;2)不同的相似組Gk對應不同的字典Dk,區(qū)別于傳統(tǒng)的方法中,所有圖像塊共用一個字典進行稀疏編碼;3)字典中的原子dk,i(i=1,2,…,nk)為與相似組Gk相同尺寸的矩陣,具有自適應性,因此能更充分地利用自然圖像中圖像塊之間的相似性先驗信息。

2 優(yōu)化算法

經(jīng)過上述分析,基于自適應相似組的圖像修復問題即為求解優(yōu)化問題式(5),其等價為:

(8)

(10)b(t+1)=b(t)-(u(t+1)-RTα(t+1))

(11)t←t+1

End for

上述迭代過程的關鍵在于求解最小化問題式(9)和式(10)。對于最小化問題式(9),通過令其梯度等于零,可以容易地得到其對應的解析解:

u(t+1)=(MTM+μE)-1Q

(12)

其中:Q=MTF+μ(RTα(t)+b(t));E為單位矩陣。

對于最小化問題式(10),其等價為N個子問題[11]:

(13)

其中:τ=240λ/μ為比例系數(shù);r(t+1)=u(t+1)-b(t)為原始圖像I的估計;rk=Rk(r(t+1))為從估計圖像r(t+1)中提取出的相似組,即1.3節(jié)中提到的Gk的估計。

將式(6)和式(7)代入式(13),可得式(13)的等價問題:

(14)

其中:k=1,2,…,N;γk=[γk,1,γk,2,…,γk,nk]為對rk進行SVD后的奇異值向量。因此,最小化問題式(14)具有如下簡潔的解析解:

(15)

基于自適應相似組的圖像修復算法描述如下:

End for

通過式(11),更新b;

t←t+1

End for

3 實驗與分析

為了驗證算法的有效性,針對隨機缺失像素復原、文字去除等方面進行圖像修復實驗,并將實驗結果和文獻[15]算法、GSR算法[11]、文獻[16]算法進行對比。采用峰值信噪比(PeakSignal-to-NoiseRatio,PSNR)及結構相似性指數(shù)(SSIM)[13]作為圖像修復效果的客觀評價指標。實驗環(huán)境：CPU為AMDAthlonX2270 3.42GHz,內(nèi)存為4GB，系統(tǒng)為MicrosoftWindows7,軟件為MatlabR2014a。

圖2 Barbara圖隨機缺失50%像素復原

圖3 Boat圖隨機缺失50%像素復原

3.1 隨機缺失像素復原

圖2和圖3分別展示了各算法對隨機缺失50%像素的Barbara圖和Boat圖進行修復的效果。通過對比可知,文獻[16]算法不能有效地修復自然圖像中的紋理和結構信息,而文獻[15]算法則會導致較嚴重的圖像模糊,例如圖2中Barbara褲子和圍巾上的紋理區(qū)域、圖3中的桅桿和繩纜。這主要是由于基于圖像塊的圖像修復算法只考慮單一圖像塊的修復,不能較好地保持鄰域信息的連貫一致性。相比之下,GSR算法和本文算法修復后的圖像取得了較好的視覺效果,能夠同時有效地復原受損圖像中的紋理和結構。但是,由于GSR算法是構造尺寸固定的組,會引入非相似圖像塊；而本文采用自適應相似組,能夠有效地排除非相似塊的干擾,準確地構造相似組,保證修復后的圖像具有較好的清晰性。

為了進一步說明算法的性能,表1給出了各算法對8幅圖像進行修復后的指標對比,可以看出,本文算法較其他三種算法在PSNR和SSIM等客觀指標上都有明顯的優(yōu)勢。其中,在峰值信噪比上平均提高了1.07～4.34 dB,在結構相似性指數(shù)上平均提高了0.009 1～0.034 5。

表1 各算法隨機缺失像素修復結果對比

表2 各算法文字去除結果對比

3.2 文字去除

圖4為對Lena圖進行文字去除的實驗效果,其余圖像的實驗結果如表2所示。

圖4 文字去除

可以看出,對于文字去除實驗,本文算法同樣展示出了良好的修復效果,在峰值信噪比上平均提高了0.94～2.75 dB,在結構相似性指數(shù)上平均提高了0.006 9～0.025 4。在視覺效果方面,文獻[15]算法會引入多余的干擾信息,例如圖4(c)中Lena的眼睛和帽檐區(qū)域,這是由于基于圖像塊的圖像修復算法,容易導致錯誤圖像塊的產(chǎn)生;而文獻[16]算法和GSR算法則會使得修復區(qū)域產(chǎn)生模糊的現(xiàn)象,如圖4(d)～(e)所示。相比之下,本文算法能夠在不引入多余信息的情況下,較好地保證結構的連貫性以及紋理的清晰性,使修復后的圖像具有較好的視覺效果。

3.3 算法收斂性及算法性能分析

圖5為本文算法在50%、80%隨機缺失像素修復和文字去除實驗中PSNR的變化趨勢。

圖5 峰值信噪比隨迭代次數(shù)的變化趨勢

從圖5可看出,圖像質(zhì)量先是有明顯的改善,然后趨于收斂,由此得出本文算法具有快速收斂的特性。對于隨機缺失像素修復實驗,只需進行25次迭代,而對于文字去除實驗,只需40次迭代。這主要是由于本文算法以自適應相似組作為基本單元,因此能夠充分地利用自然圖像中的先驗信息,根據(jù)圖像的本質(zhì)特征指導圖像的修復過程,從而保證算法的高效性。表3給出各算法修復一幅512×512圖像的平均耗時,其中修復區(qū)域比例為20%。本文算法在修復效率上，是文獻[15]算法的2.51倍，是GSR算法的3.32倍。雖然文獻[16]算法在修復效率上是最高的,但是其修復效果遠不如本文算法。

表3 各算法平均耗時對比

4 結語

針對圖像修復結果中存在的結構連續(xù)性及紋理清晰性較差的問題,本文在稀疏表示框架下提出了一種基于自適應相似組的圖像修復算法。該算法充分利用自然圖像中圖像塊之間的相似性,構造自適應相似組,從而對原始圖像的本質(zhì)特征進行準確的描述。實驗結果表明,本文算法在客觀評價指標和視覺效果上均有明顯的優(yōu)勢,能夠?qū)D像中的紋理信息和結構信息進行有效的修復,同時具有快速收斂的特性。本文將自適應相似組的概念運用于圖像修復,未來希望能夠?qū)⑦@個概念推廣到其他的圖像處理領域中,包括圖像去噪、圖像去模糊以及超分辨率重建等。

References)

[1] GUILLEMOT C, LE MEUR O. Image inpainting: overview and recent advances[J]. IEEE Signal Processing Magazine, 2014, 31(1): 127-144.

[2] CHAN T, SHEN J. Local inpainting models and TV inpainting[J]. SIAM Journal on Applied Mathematics, 2001, 62(3): 1019-1043.

[3] CHAN T F, SHEN J. Nontexture inpainting by curvature-driven diffusions[J]. Journal of Visual Communication and Image Representation, 2001, 12(4): 436-449.

[4] RAM I, ELAD M, COHEN I. Image processing using smooth ordering of its patches[J]. IEEE Transactions on Image Processing, 2013, 22(7): 2764-2774.

[5] WONG A, ORCHARD J. A nonlocal-means approach to exemplar-based inpainting[C]// ICIP 2008: Proceedings of the 15th IEEE International Conference on Image Processing. Piscataway, NJ: IEEE, 2008: 2600-2603.

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

[7] SHEN B, HU W, ZHANG Y, et al. Image inpainting via sparse representation[C]// ICASSP 2009: Proceedings of the 2009 IEEE International Conference on Acoustics, Speech and Signal Processing. Washington, DC: IEEE Computer Society, 2009: 697-700.

[8] LI Z, HE H, YIN Z, et al. A color-gradient patch sparsity based image inpainting algorithm with structure coherence and neighborhood consistency[J]. Signal Processing, 2014, 99(6): 116-128.

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

[10] MAIRAL J, BACH F, PONCE J, et al. Non-local sparse models for image restoration[C]// Proceedings of the 2009 IEEE 12th International Conference on Computer Vision. Piscataway, NJ: IEEE, 2009: 2272-2279.

[11] ZHANG J, ZHAO D, GAO W. Group-based sparse representation for image restoration[J]. IEEE Transactions on Image Processing, 2014, 23(8): 3336-3351.

[12] XU J, ZHANG L, ZUO W, et al. Patch group based nonlocal self-similarity prior learning for image denoising[C]// Proceedings of the 2015 IEEE International Conference on Computer Vision. Piscataway, NJ: IEEE, 2015: 244-252.

[13] WANG Z, BOVIK A C, SHEIKH H R, et al. Image quality assessment: from error visibility to structural similarity[J]. IEEE Transactions on Image Processing, 2004, 13(4): 600-612.

[14] GOLDSTEIN T, OSHER S. The split Bregman method for L1-regularized problems[J]. SIAM Journal on Imaging Sciences, 2009, 2(2): 323-343.

[15] JIN K H, YE J C. Annihilating filter-based low-rank Hankel matrix approach for image inpainting[J]. IEEE Transactions on Image Processing, 2015, 24(11): 3498-3511.

[16] AFONSO M V, SANCHES J M R. Blind inpainting usingl0and total variation regularization[J]. IEEE Transactions on Image Processing, 2015, 24(7): 2239-2253.

This work is partially supported by the National Natural Science Foundation of China (61501334).

LIN Jinyong, born in 1992, M. S. candidate. His research interests include digital image processing, machine learning.

DENG Dexiang, born in 1961, M. S., professor. His research interests include computer vision, target tracking.

YAN Jia, born in 1983, Ph. D., lecturer. His research interests include target tracking, image quality assessment.

LIN Xiaoying, born in 1992, M. S. candidate. Her research interests include digital image processing, data mining.

Self-adaptive group based sparse representation for image inpainting

LIN Jinyong1*, DENG Dexiang1, YAN Jia1, LIN Xiaoying2

(1.School of Electronic Information, Wuhan University, Wuhan Hubei 430072, China;2. School of Electronic Engineering, Beijing University of Posts and Telecommunications, Beijing 100876, China)

Focusing on the problem of object structure discontinuity and poor texture detail occurred in image inpainting, an inpainting algorithm based on self-adaptive group was proposed. Different from the traditional method which uses a single image block or a fixed number of image blocks as the repair unit, the proposed algorithm adaptively selects different number of similar image blocks according to the different characteristics of the texture area to construct self-adaptive group. A self-adaptive dictionary as well as a sparse representation model was established in the domain of self-adaptive group. Finally, the target cost function was solved by Split Bregman Iteration. The experimental results show that compared with the patch-based inpainting algorithm and Group-based Sparse Representation (GSR) algorithm, the Peak Signal-to-Noise Ratio (PSNR) and the Structural SIMilarity (SSIM) index are improved by 0. 94-4.34 dB and 0. 006 9-0.034 5 respectively; meanwhile, the proposed approach can obtain image inpainting speed-up of 2.51 and 3.32 respectively.

image inpainting; sparse representation; self-adaptive group; dictionary learning; adaptivity

2016- 09- 27;

2016- 11- 20。 基金項目:國家自然科學基金資助項目(61501334)。

林金勇(1992—),男,福建廈門人,碩士研究生,主要研究方向:數(shù)字圖像處理、機器學習; 鄧德祥(1961—),男,湖北荊州人,教授,碩士,主要研究方向:計算機視覺、目標跟蹤; 顏佳(1983—),男,湖北天門人,講師,博士,主要研究方向:目標跟蹤、圖像質(zhì)量評價;林曉英(1992—),女,福建泉州人,碩士研究生,主要研究方向:數(shù)字圖像處理、數(shù)據(jù)挖掘。

1001- 9081(2017)04- 1169- 05

10.11772/j.issn.1001- 9081.2017.04.1169

TN911.7

A