计算机应用   2017, Vol. 37 Issue (4): 1169-1173  DOI: 10.11772/j.issn.1001-9081.2017.04.1169 0

引用本文

LIN Jinyong, DENG Dexiang, YAN Jia, LIN Xiaoying. Self-adaptive group based sparse representation for image inpainting[J]. Journal of Computer Applications, 2017, 37(4): 1169-1173. DOI: 10.11772/j.issn.1001-9081.2017.04.1169.

文章历史

1. 武汉大学 电子信息学院, 武汉 430072;
2. 北京邮电大学 电子工程学院, 北京 100876

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
Abstract: 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. 0069-0.0345 respectively; meanwhile, the proposed approach can obtain image inpainting speed-up of 2.51 and 3.32 respectively.
0 引言

1 算法描述 1.1 自适应相似组

 $SSIM(x, y)=\frac{(2{{\mu }_{x}}{{\mu }_{y}}+{{C}_{1}})(2{{\sigma }_{xy}}+{{C}_{2}})}{(\mu _{x}^{2}+\mu _{y}^{2}+{{C}_{1}})(\sigma _{x}^{2}+\sigma _{y}^{2}+{{C}_{2}})}$ (1)

 图 1 自适应相似组的构造 Figure 1 Construction of self-adaptive group
1.2 稀疏表示模型

 ${{{\mathrm{\hat{G}}}}_{k}}=\sum\limits_{m=1}^{{{n}_{k}}}{{{\mathrm{d}}_{k, m}}}{{\alpha }_{k, m}}$ (2)

 $\mathrm{\hat{I}}=\sum\limits_{k=1}^{N}{\mathrm{R}_{k}^{\text{T}}\left( {{D}_{k}}{{\mathrm{ }\!\!\alpha\!\!\text{ }}_{k}} \right)}$ (3)

 $\begin{matrix} \min {{\left\| \mathit{\boldsymbol{ }}\!\!\alpha\!\!\rm{ } \right\|}_{0}} \\ \rm{s}\rm{.t}\rm{.}\ \ \ \ \ \ \left\| \mathit{\boldsymbol{MI}}-\mathit{\boldsymbol{F}} \right\|<\varepsilon \\ \end{matrix}$ (4)

 $\mathit{\boldsymbol{\hat{ }\!\!\alpha\!\!\rm{ }}}=\underset{\mathit{\boldsymbol{ }}\!\!\alpha\!\!\rm{ }}{\mathop{\rm{arg min}}}\, \frac{1}{2}\left\| \mathit{\boldsymbol{M}}\sum\limits_{k=1}^{N}{\mathit{\boldsymbol{R}}_{k}^{\rm{T}}\left( {{D}_{k}}{{\mathit{\boldsymbol{ }}\!\!\alpha\!\!\rm{ }}_{k}} \right)}-\mathit{\boldsymbol{F}} \right\|_{2}^{2}+\lambda {{\left\| \mathit{\boldsymbol{ }}\!\!\alpha\!\!\rm{ } \right\|}_{0}}$ (5)

1.3 自适应字典学习

 ${{\mathit{\boldsymbol{r}}}_{k}}={{\mathit{\boldsymbol{U}}}_{k}}{{\mathit{\boldsymbol{ }}\!\!\Sigma\!\!\rm{ }}_{k}}\mathit{\boldsymbol{V}}_{k}^{\rm{T}}=\sum\limits_{i=1}^{{{n}_{k}}}{{{\gamma }_{k, i}}\left( {{\mathit{\boldsymbol{u}}}_{k, i}}\mathit{\boldsymbol{v}}_{k, i}^{\rm{T}} \right)}$ (6)

 \begin{align} & {{D}_{k}}=\left\{ {{\mathit{\boldsymbol{d}}}_{k, 1}}, {{\mathit{\boldsymbol{d}}}_{k, 2}}, \cdots, {{\mathit{\boldsymbol{d}}}_{k, {{n}_{k}}}} \right\} \\ & \rm{ }=\left\{ {{\mathit{\boldsymbol{u}}}_{k, 1}}\mathit{\boldsymbol{v}}_{k, 1}^{\rm{T}}, {{\mathit{\boldsymbol{u}}}_{k, 2}}\mathit{\boldsymbol{v}}_{k, 2}^{\rm{T}}, \cdots, {{\mathit{\boldsymbol{u}}}_{k, {{n}_{k}}}}\mathit{\boldsymbol{v}}_{k, {{n}_{k}}}^{\rm{T}} \right\} \\ \end{align} (7)

2 优化算法

 \begin{align} & \ \ \ \ \ \underset{\mathit{\boldsymbol{ }}\!\!\alpha\!\!\rm{, u}}{\mathop{\min }}\, \frac{1}{2}\left\| \mathit{\boldsymbol{Mu}}-\mathit{\boldsymbol{F}} \right\|_{2}^{2}+\lambda {{\left\| \mathit{\boldsymbol{ }}\!\!\alpha\!\!\rm{ } \right\|}_{0}} \\ & \rm{s}\rm{.t}.\rm{ }\mathit{\boldsymbol{u}}=\sum\limits_{k=1}^{N}{\mathit{\boldsymbol{R}}_{k}^{\rm{T}}\left( {{D}_{k}}{{\mathit{\boldsymbol{ }}\!\!\alpha\!\!\rm{ }}_{k}} \right)} \\ \end{align} (8)

For t < T

 ${{\mathit{\boldsymbol{u}}}^{\left( t+1 \right)}}=\underset{\mathit{\boldsymbol{u}}}{\mathop{\arg \min }}\, f\left( \mathit{\boldsymbol{u}} \right)+\frac{\mu }{2}\left\| \mathit{\boldsymbol{u}}-{{\mathit{\boldsymbol{R}}}^{\rm{T}}}{{\mathit{\boldsymbol{ }}\!\!\alpha\!\!\rm{ }}^{\left( t \right)}}-{{\mathit{\boldsymbol{b}}}^{\left( t \right)}} \right\|_{2}^{2}$ (9)
 ${{\mathit{\boldsymbol{ }}\!\!\alpha\!\!\rm{ }}^{\left( t+1 \right)}}=\underset{\mathit{\boldsymbol{ }}\!\!\alpha\!\!\rm{ }}{\mathop{\arg \min }}\, g\left( \mathit{\boldsymbol{ }}\!\!\alpha\!\!\rm{ } \right)+\frac{\mu }{2}\left\| {{\mathit{\boldsymbol{u}}}^{\left( t+1 \right)}}-{{\mathit{\boldsymbol{R}}}^{\rm{T}}}\mathit{\boldsymbol{ }}\!\!\alpha\!\!\rm{ }-{{\mathit{\boldsymbol{b}}}^{\left( t \right)}} \right\|_{2}^{2}$ (10)
 ${{\mathit{\boldsymbol{b}}}^{\left( t+1 \right)}}={{\mathit{\boldsymbol{b}}}^{\left( t \right)}}-\left( {{\mathit{\boldsymbol{u}}}^{\left( t+1 \right)}}-{{\mathit{\boldsymbol{R}}}^{\rm{T}}}{{\mathit{\boldsymbol{ }}\!\!\alpha\!\!\rm{ }}^{\left( t+1 \right)}} \right)$ (11)

tt+1

End for

 ${{\mathit{\boldsymbol{u}}}^{\left( t+1 \right)}}={{\left( {{\mathit{\boldsymbol{M}}}^{\rm{T}}}\mathit{\boldsymbol{M}}+\mu \mathit{\boldsymbol{E}} \right)}^{-1}}\mathit{\boldsymbol{Q}}$ (12)

 $\underset{{{\mathit{\boldsymbol{ }}\!\!\alpha\!\!\rm{ }}_{k}}}{\mathop{\arg \min }}\, \frac{1}{2}\left\| {{D}_{k}}{{\mathit{\boldsymbol{ }}\!\!\alpha\!\!\rm{ }}_{k}}-{{\mathit{\boldsymbol{r}}}_{k}} \right\|_{2}^{2}+\tau {{\left\| {{\mathit{\boldsymbol{ }}\!\!\alpha\!\!\rm{ }}_{k}} \right\|}_{0}};k=1, 2, \cdots, N$ (13)

 ${{{\mathit{\boldsymbol{\hat{ }\!\!\alpha\!\!\rm{ }}}}}_{k}}=\underset{{{\mathit{\boldsymbol{ }}\!\!\alpha\!\!\rm{ }}_{k}}}{\mathop{\arg \min }}\, \frac{1}{2}\left\| {{\mathit{\boldsymbol{ }}\!\!\alpha\!\!\rm{ }}_{k}}-{{\mathit{\boldsymbol{ }}\!\!\gamma\!\!\rm{ }}_{k}} \right\|_{2}^{2}+\tau {{\left\| {{\mathit{\boldsymbol{ }}\!\!\alpha\!\!\rm{ }}_{k}} \right\|}_{0}}$ (14)

 ${{{\boldsymbol{\hat{\alpha }}}}_{k}}=hard\left( {{\boldsymbol{\gamma} }_{k}}, \sqrt{2\tau } \right);k=1, 2, \cdots, N$ (15)

For t < T

通过式 (12), 更新u;

图像I的估计: r(t+1)= u(t+1)-b(t);

将r(t+1)分解为N个图像块{ Ψk|k=1, 2, …, N};

For k=1, 2, …, N

基于结构相似性指数得到Ψk的相似图像块;

由相似图像块构造自适应相似组rk;

对相似组rk进行SVD, 构造字典Dk;

通过式 (15), 更新αk;

End for

通过式 (11), 更新b;

tt+1

End for

3 实验与分析

3.1 随机缺失像素复原

 图 2 Barbara图随机缺失50%像素复原 Figure 2 Reconstructed Barbara images with 50% randomly pixels missing
 图 3 Boat图随机缺失50%像素复原 Figure 3 Reconstructed Boat images with 50% randomly pixels missing

3.2 文字去除

 图 4 文字去除 Figure 4 Text removal

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

 图 5 峰值信噪比随迭代次数的变化趋势 Figure 5 Effect of iteration number on PSNR performance

4 结语

 [1] GUILLEMOT C, LE MEUR O. Image inpainting: overview and recent advances[J]. IEEE Signal Processing Magazine, 2014, 31 (1) : 127-144. doi: 10.1109/MSP.2013.2273004 [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. doi: 10.1006/jvci.2001.0487 [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. doi: 10.1109/TIP.2013.2257813 [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. doi: 10.1109/TIP.2004.833105 [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. doi: 10.1109/TIP.2010.2042098 [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. doi: 10.1109/TIP.2014.2323127 [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. doi: 10.1109/TIP.2003.819861 [14] GOLDSTEIN T, OSHER S. The split Bregman method for L1-regularized problems[J]. SIAM Journal on Imaging Sciences, 2009, 2 (2) : 323-343. doi: 10.1137/080725891 [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. doi: 10.1109/TIP.2015.2446943 [16] AFONSO M V, SANCHES J M R. Blind inpainting using l0 and total variation regularization[J]. IEEE Transactions on Image Processing, 2015, 24 (7) : 2239-2253. doi: 10.1109/TIP.2015.2417505