# American Institute of Mathematical Sciences

December 2018, 12(6): 1389-1410. doi: 10.3934/ipi.2018058

## Local block operators and TV regularization based image inpainting

 Laboratory of Mathematics and Complex Systems (Ministry of Education of China), School of Mathematical Sciences, Beijing Normal University, Beijing 100875, China

* Corresponding author: jliu@bnu.edu.cn

Received  January 2018 Revised  July 2018 Published  October 2018

In this paper, we propose a novel image blocks based inpainting model using group sparsity and TV regularization. The block matching method is employed to collect similar image blocks which can be formed as sparse image groups. By reducing the redundant information in these groups, we can well restore textures missing in the inpainting areas. We built a variational framework based on a local SVD operator for block matching and group sparsity. In addition, TV regularization is naturally integrated in the model to reduce artificial effects which are caused by image blocks stacking in the block matching method. Besides, enforcing the sparsity of the representation, the SVD operators in our method are iteratively updated and play the role of dictionary learning. Thus it can greatly improve the quality of the restoration. Moreover, we mathematically show the existence of a minimizer for the proposed inpainting model. Convergence results of the proposed algorithm are also given in the paper. Numerical experiments demonstrate that the proposed model outperforms many benchmark methods such as BM3D based image inpainting.

Citation: Wei Wan, Haiyang Huang, Jun Liu. Local block operators and TV regularization based image inpainting. Inverse Problems & Imaging, 2018, 12 (6) : 1389-1410. doi: 10.3934/ipi.2018058
##### References:
 [1] P. Arias, G. Facciolo, V. Caselles and G. Sapiro, A variational framework for exemplar-based image inpainting, International Journal of Computer Vision, 93 (2011), 319-347. doi: 10.1007/s11263-010-0418-7. [2] G. Aubert and P. Kornprobst, Mathematical Problems in Image Processing: Partial Differential Equations and the Calculus of Variations, Springer, 2006. [3] J. F. Aujol, S. Ladjal and S. Masnou, Exemplar-based inpainting from a variational point of view, SIAM Journal on Mathematical Analysis, 42 (2010), 1246-1285. doi: 10.1137/080743883. [4] M. Bertalmio, G. Sapiro, V. Caselles and C. Ballester, Image inpainting, Siggraph, 4 (2005), 417-424. [5] A. L. Bertozzi, S. Esedoglu and A. Gillette, Inpainting of binary images using the cahn-hilliard equation, IEEE Transactions on Image Processing, 16 (2007), 285-291. doi: 10.1109/TIP.2006.887728. [6] F. Bornemann and T. März, Fast image inpainting based on coherence transport, Journal of Mathematical Imaging and Vision, 28 (2007), 259-278. doi: 10.1007/s10851-007-0017-6. [7] M. Burger, L. He and C. B. Nlieb, Cahn-hilliard inpainting and a generalization for grayvalue images, SIAM Journal on Imaging Sciences, 2 (2009), 1129-1167. doi: 10.1137/080728548. [8] J. -F. Cai, E. J. Candès and Z. Shen, A singular value thresholding algorithm for matrix completion, SIAM Journal on Optimizaition, 20 (2010), 1956-1982. doi: 10.1137/080738970. [9] E. J. Candès and B. Recht, Exact matrix completion via convex optimization, Foundations of Computational Mathematics, 9 (2009), 717-772. doi: 10.1007/s10208-009-9045-5. [10] F. Cao, Y. Gousseau, S. Masnou and P. Prez, Geometrically guided exemplar-based inpainting, SIAM Journal on Imaging Sciences, 4 (2011), 1143-1179. doi: 10.1137/110823572. [11] T. F. Chan and J. Shen, Mathematical models for local nontexture inpaintings, SIAM Journal on Applied Mathematics, 62 (2001), 1019-1043. doi: 10.1137/S0036139900368844. [12] T. F. Chan and J. Shen, Nontexture inpainting by curvature-driven diffusions, Journal of Visual Communication & Image Representation, 12 (2001), 436-449. [13] T. F. Chan, S. H. Kang and J. Shen, Euler's elastica and curvature based inpainting, SIAM Journal on Applied Mathematics, 63 (2002), 564-592. doi: 10.1137/S0036139901390088. [14] A. Criminisi, P. Perez and K. Toyama, Region filling and object removal by exemplar-based image inpainting, IEEE Transactions on Image Processing, 13 (2004), 1200-1212. [15] L. Demanet, B. Song and T. Chan, Image inpainting by correspondence maps: a deterministic approach, Variational Level Set Methods, Prod. Of Workshop in Int"l Conf. Image Proc., (2003), 1100. [16] M. Elad, J. L. Starck, P. Querre and D. L. Donoho, Simultaneous cartoon and texture image inpainting using morphological component analysis (mca), Applied and Computational Harmonic Analysis, 19 (2005), 340-358. doi: 10.1016/j.acha.2005.03.005. [17] S. Esedoglu and J. Shen, Digital inpainting based on the mumford-shah-euler image model, European Journal of Applied Mathematics, 13 (2002), 353-370. doi: 10.1017/S0956792502004904. [18] M. J. Fadili, J. L. Starck and F. Murtagh, Inpainting and zooming using sparse representations, The Computer Journal, 52 (2009), 64-791. [19] R. Glowinski, Augmented Lagrangian and Operator Splitting Methods in Nonlinear Mechanics, SIAM, Philadelphia, 1989. [20] O. G. Guleryuz, Nonlinear approximation based image recovery using adaptive sparse reconstructions and iterated denoising-part Ⅱ: adaptive algorithms, IEEE Transactions on Image Processing, 15 (2006), 555-571. [21] N. Kawai, T. Sato and N. Yokoya, Image inpainting cosidiering brightness change and spatial locality of textures and its evaluation, Pacific Rim Symposium on Advances in Image and Video Technology, Springer, Berlin, Heidelberg, 5414 (2009), 271–282. [22] W. Li, L. Zhao, Z. Lin, D. Xu and D. Lu, Non-local image inpainting using low-rank matrix completion, Computer Graphics Forum, 34 (2015), 111-122. [23] F. Li and T. Zeng, A universal variational framework for sparsity-based image inpainting, IEEE Transactions on Image Processing, 23 (2014), 4242-4254. doi: 10.1109/TIP.2014.2346030. [24] J. Liu and S. Osher, Block matching local svd operator based sparsity and tv regularization for image denoising, Journal of Scientific Computing, (2018), 1-18. doi: 10.1007/s10915-018-0785-8. [25] L. I. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms, Physica D Nonlinear Phenomena, 60 (1992), 259-268. doi: 10.1016/0167-2789(92)90242-F. [26] X. C. Tai, S. Osher and R. Holm, Image inpainting using a tv-stokes equation, Image Processing Based on Partial Differential Equations, 3–22, Math. Vis., Springer, Berlin, 2007. doi: 10.1007/978-3-540-33267-1_1. [27] Y. Wexler, E. Shechtman and M. Irani, Space-time video completion, Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2004. [28] C. Wu and X. -C. Tai, Augmented lagrangian method, dual Methods, and split Bregman Iteration for rof, vectorial tv, and high order models, SIAM Journal on Imaging Sciences, 3 (2012), 300-339. doi: 10.1137/090767558. [29] Z. Xu and J. Sun, Image inpainting by patch propagation using patch sparsity, IEEE Transactions on Image Processing, 19 (2010), 1153-1165. doi: 10.1109/TIP.2010.2042098. [30] M. Zhou, H. Chen, J. Paisley, L. Ren, L. Li, Z. Xing, D. Dunson, G. Sapiro and L. Carin, Nonparametric Bayesian Dictionary Learning for Analysis of Noisy and Incomplete Images, IEEE Transactions on Image Processing, 21 (2012), 130-144. doi: 10.1109/TIP.2011.2160072.

show all references

##### References:
 [1] P. Arias, G. Facciolo, V. Caselles and G. Sapiro, A variational framework for exemplar-based image inpainting, International Journal of Computer Vision, 93 (2011), 319-347. doi: 10.1007/s11263-010-0418-7. [2] G. Aubert and P. Kornprobst, Mathematical Problems in Image Processing: Partial Differential Equations and the Calculus of Variations, Springer, 2006. [3] J. F. Aujol, S. Ladjal and S. Masnou, Exemplar-based inpainting from a variational point of view, SIAM Journal on Mathematical Analysis, 42 (2010), 1246-1285. doi: 10.1137/080743883. [4] M. Bertalmio, G. Sapiro, V. Caselles and C. Ballester, Image inpainting, Siggraph, 4 (2005), 417-424. [5] A. L. Bertozzi, S. Esedoglu and A. Gillette, Inpainting of binary images using the cahn-hilliard equation, IEEE Transactions on Image Processing, 16 (2007), 285-291. doi: 10.1109/TIP.2006.887728. [6] F. Bornemann and T. März, Fast image inpainting based on coherence transport, Journal of Mathematical Imaging and Vision, 28 (2007), 259-278. doi: 10.1007/s10851-007-0017-6. [7] M. Burger, L. He and C. B. Nlieb, Cahn-hilliard inpainting and a generalization for grayvalue images, SIAM Journal on Imaging Sciences, 2 (2009), 1129-1167. doi: 10.1137/080728548. [8] J. -F. Cai, E. J. Candès and Z. Shen, A singular value thresholding algorithm for matrix completion, SIAM Journal on Optimizaition, 20 (2010), 1956-1982. doi: 10.1137/080738970. [9] E. J. Candès and B. Recht, Exact matrix completion via convex optimization, Foundations of Computational Mathematics, 9 (2009), 717-772. doi: 10.1007/s10208-009-9045-5. [10] F. Cao, Y. Gousseau, S. Masnou and P. Prez, Geometrically guided exemplar-based inpainting, SIAM Journal on Imaging Sciences, 4 (2011), 1143-1179. doi: 10.1137/110823572. [11] T. F. Chan and J. Shen, Mathematical models for local nontexture inpaintings, SIAM Journal on Applied Mathematics, 62 (2001), 1019-1043. doi: 10.1137/S0036139900368844. [12] T. F. Chan and J. Shen, Nontexture inpainting by curvature-driven diffusions, Journal of Visual Communication & Image Representation, 12 (2001), 436-449. [13] T. F. Chan, S. H. Kang and J. Shen, Euler's elastica and curvature based inpainting, SIAM Journal on Applied Mathematics, 63 (2002), 564-592. doi: 10.1137/S0036139901390088. [14] A. Criminisi, P. Perez and K. Toyama, Region filling and object removal by exemplar-based image inpainting, IEEE Transactions on Image Processing, 13 (2004), 1200-1212. [15] L. Demanet, B. Song and T. Chan, Image inpainting by correspondence maps: a deterministic approach, Variational Level Set Methods, Prod. Of Workshop in Int"l Conf. Image Proc., (2003), 1100. [16] M. Elad, J. L. Starck, P. Querre and D. L. Donoho, Simultaneous cartoon and texture image inpainting using morphological component analysis (mca), Applied and Computational Harmonic Analysis, 19 (2005), 340-358. doi: 10.1016/j.acha.2005.03.005. [17] S. Esedoglu and J. Shen, Digital inpainting based on the mumford-shah-euler image model, European Journal of Applied Mathematics, 13 (2002), 353-370. doi: 10.1017/S0956792502004904. [18] M. J. Fadili, J. L. Starck and F. Murtagh, Inpainting and zooming using sparse representations, The Computer Journal, 52 (2009), 64-791. [19] R. Glowinski, Augmented Lagrangian and Operator Splitting Methods in Nonlinear Mechanics, SIAM, Philadelphia, 1989. [20] O. G. Guleryuz, Nonlinear approximation based image recovery using adaptive sparse reconstructions and iterated denoising-part Ⅱ: adaptive algorithms, IEEE Transactions on Image Processing, 15 (2006), 555-571. [21] N. Kawai, T. Sato and N. Yokoya, Image inpainting cosidiering brightness change and spatial locality of textures and its evaluation, Pacific Rim Symposium on Advances in Image and Video Technology, Springer, Berlin, Heidelberg, 5414 (2009), 271–282. [22] W. Li, L. Zhao, Z. Lin, D. Xu and D. Lu, Non-local image inpainting using low-rank matrix completion, Computer Graphics Forum, 34 (2015), 111-122. [23] F. Li and T. Zeng, A universal variational framework for sparsity-based image inpainting, IEEE Transactions on Image Processing, 23 (2014), 4242-4254. doi: 10.1109/TIP.2014.2346030. [24] J. Liu and S. Osher, Block matching local svd operator based sparsity and tv regularization for image denoising, Journal of Scientific Computing, (2018), 1-18. doi: 10.1007/s10915-018-0785-8. [25] L. I. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms, Physica D Nonlinear Phenomena, 60 (1992), 259-268. doi: 10.1016/0167-2789(92)90242-F. [26] X. C. Tai, S. Osher and R. Holm, Image inpainting using a tv-stokes equation, Image Processing Based on Partial Differential Equations, 3–22, Math. Vis., Springer, Berlin, 2007. doi: 10.1007/978-3-540-33267-1_1. [27] Y. Wexler, E. Shechtman and M. Irani, Space-time video completion, Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2004. [28] C. Wu and X. -C. Tai, Augmented lagrangian method, dual Methods, and split Bregman Iteration for rof, vectorial tv, and high order models, SIAM Journal on Imaging Sciences, 3 (2012), 300-339. doi: 10.1137/090767558. [29] Z. Xu and J. Sun, Image inpainting by patch propagation using patch sparsity, IEEE Transactions on Image Processing, 19 (2010), 1153-1165. doi: 10.1109/TIP.2010.2042098. [30] M. Zhou, H. Chen, J. Paisley, L. Ren, L. Li, Z. Xing, D. Dunson, G. Sapiro and L. Carin, Nonparametric Bayesian Dictionary Learning for Analysis of Noisy and Incomplete Images, IEEE Transactions on Image Processing, 21 (2012), 130-144. doi: 10.1109/TIP.2011.2160072.
Filling in the missing pixels by different inpainting method
Comparison of details between different inpainting methods
Scratch and text removal by different inpainting methods
Comparison of details between different inpainting methods
The relative error curves as functions of the iteration number on our experiments for the proposed-$\ell_1$ method
The relative error curves as functions of the iteration number on our experiments for the proposed-$\ell_0$ method
PSNR values of the different methods on filling randomly missing pixels
 Image CTM Cubic BPFA IDI-BM3D Proposed-$\ell_1$ Proposed-$\ell_0$ Monarch 23.01 24.18 24.49 26.63 25.15 27.25 Lena 27.21 27.40 28.32 29.63 28.50 29.98 Barbara 25.65 26.24 27.08 28.62 27.59 29.69
 Image CTM Cubic BPFA IDI-BM3D Proposed-$\ell_1$ Proposed-$\ell_0$ Monarch 23.01 24.18 24.49 26.63 25.15 27.25 Lena 27.21 27.40 28.32 29.63 28.50 29.98 Barbara 25.65 26.24 27.08 28.62 27.59 29.69
PSNR values of different inpainting methods on text and scratch removal
 Image Cubic TV BPFA IDI-BM3D Proposed-$\ell_1$ Proposed-$\ell_0$ Barbara 33.25 34.58 37.28 40.16 38.26 40.98 Hill 33.30 33.44 33.84 35.38 34.54 35.61 Baboon 35.87 35.86 35.39 37.77 36.80 38.03
 Image Cubic TV BPFA IDI-BM3D Proposed-$\ell_1$ Proposed-$\ell_0$ Barbara 33.25 34.58 37.28 40.16 38.26 40.98 Hill 33.30 33.44 33.84 35.38 34.54 35.61 Baboon 35.87 35.86 35.39 37.77 36.80 38.03
 [1] Emmanuel Frénod. Homogenization-based numerical methods. Discrete & Continuous Dynamical Systems - S, 2016, 9 (5) : i-ix. doi: 10.3934/dcdss.201605i [2] Emmanuel Frénod. An attempt at classifying homogenization-based numerical methods. Discrete & Continuous Dynamical Systems - S, 2015, 8 (1) : i-vi. doi: 10.3934/dcdss.2015.8.1i [3] Dale McDonald. Sensitivity based trajectory following control damping methods. Numerical Algebra, Control & Optimization, 2013, 3 (1) : 127-143. doi: 10.3934/naco.2013.3.127 [4] Michael Hintermüller, Monserrat Rincon-Camacho. An adaptive finite element method in $L^2$-TV-based image denoising. Inverse Problems & Imaging, 2014, 8 (3) : 685-711. doi: 10.3934/ipi.2014.8.685 [5] Alina Toma, Bruno Sixou, Françoise Peyrin. Iterative choice of the optimal regularization parameter in TV image restoration. Inverse Problems & Imaging, 2015, 9 (4) : 1171-1191. doi: 10.3934/ipi.2015.9.1171 [6] Sergio Grillo, Leandro Salomone, Marcela Zuccalli. On the relationship between the energy shaping and the Lyapunov constraint based methods. Journal of Geometric Mechanics, 2017, 9 (4) : 459-486. doi: 10.3934/jgm.2017018 [7] Xiangtuan Xiong, Jinmei Li, Jin Wen. Some novel linear regularization methods for a deblurring problem. Inverse Problems & Imaging, 2017, 11 (2) : 403-426. doi: 10.3934/ipi.2017019 [8] Stefan Kindermann, Antonio Leitão. Convergence rates for Kaczmarz-type regularization methods. Inverse Problems & Imaging, 2014, 8 (1) : 149-172. doi: 10.3934/ipi.2014.8.149 [9] Sanjay Khattri. Another note on some quadrature based three-step iterative methods for non-linear equations. Numerical Algebra, Control & Optimization, 2013, 3 (3) : 549-555. doi: 10.3934/naco.2013.3.549 [10] Abdel-Rahman Hedar, Ahmed Fouad Ali, Taysir Hassan Abdel-Hamid. Genetic algorithm and Tabu search based methods for molecular 3D-structure prediction. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 191-209. doi: 10.3934/naco.2011.1.191 [11] Tan Bui-Thanh, Quoc P. Nguyen. FEM-based discretization-invariant MCMC methods for PDE-constrained Bayesian inverse problems. Inverse Problems & Imaging, 2016, 10 (4) : 943-975. doi: 10.3934/ipi.2016028 [12] Zhong Wan, Chaoming Hu, Zhanlu Yang. A spectral PRP conjugate gradient methods for nonconvex optimization problem based on modified line search. Discrete & Continuous Dynamical Systems - B, 2011, 16 (4) : 1157-1169. doi: 10.3934/dcdsb.2011.16.1157 [13] Stefan Klus, Christof Schütte. Towards tensor-based methods for the numerical approximation of the Perron--Frobenius and Koopman operator. Journal of Computational Dynamics, 2016, 3 (2) : 139-161. doi: 10.3934/jcd.2016007 [14] Julian Koellermeier, Roman Pascal Schaerer, Manuel Torrilhon. A framework for hyperbolic approximation of kinetic equations using quadrature-based projection methods. Kinetic & Related Models, 2014, 7 (3) : 531-549. doi: 10.3934/krm.2014.7.531 [15] Shummin Nakayama, Yasushi Narushima, Hiroshi Yabe. Memoryless quasi-Newton methods based on spectral-scaling Broyden family for unconstrained optimization. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-21. doi: 10.3934/jimo.2018122 [16] Yigui Ou, Haichan Lin. A class of accelerated conjugate-gradient-like methods based on a modified secant equation. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-16. doi: 10.3934/jimo.2019013 [17] Jingwei Liang, Jia Li, Zuowei Shen, Xiaoqun Zhang. Wavelet frame based color image demosaicing. Inverse Problems & Imaging, 2013, 7 (3) : 777-794. doi: 10.3934/ipi.2013.7.777 [18] Amir Averbuch, Pekka Neittaanmäki, Valery Zheludev. Periodic spline-based frames for image restoration. Inverse Problems & Imaging, 2015, 9 (3) : 661-707. doi: 10.3934/ipi.2015.9.661 [19] Ye Yuan, Yan Ren, Xiaodong Liu, Jing Wang. Approach to image segmentation based on interval neutrosophic set. Numerical Algebra, Control & Optimization, 2019, 0 (0) : 0-0. doi: 10.3934/naco.2019028 [20] Jianhong (Jackie) Shen, Sung Ha Kang. Quantum TV and applications in image processing. Inverse Problems & Imaging, 2007, 1 (3) : 557-575. doi: 10.3934/ipi.2007.1.557

2017 Impact Factor: 1.465