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. AriasG. FaccioloV. 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.  Google Scholar

[2]

G. Aubert and P. Kornprobst, Mathematical Problems in Image Processing: Partial Differential Equations and the Calculus of Variations, Springer, 2006.  Google Scholar

[3]

J. F. AujolS. 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.  Google Scholar

[4]

M. BertalmioG. SapiroV. Caselles and C. Ballester, Image inpainting, Siggraph, 4 (2005), 417-424.   Google Scholar

[5]

A. L. BertozziS. 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.  Google Scholar

[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.  Google Scholar

[7]

M. BurgerL. 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.  Google Scholar

[8]

J. -F. CaiE. 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.  Google Scholar

[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.  Google Scholar

[10]

F. CaoY. GousseauS. Masnou and P. Prez, Geometrically guided exemplar-based inpainting, SIAM Journal on Imaging Sciences, 4 (2011), 1143-1179.  doi: 10.1137/110823572.  Google Scholar

[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.  Google Scholar

[12]

T. F. Chan and J. Shen, Nontexture inpainting by curvature-driven diffusions, Journal of Visual Communication & Image Representation, 12 (2001), 436-449.   Google Scholar

[13]

T. F. ChanS. 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.  Google Scholar

[14]

A. CriminisiP. Perez and K. Toyama, Region filling and object removal by exemplar-based image inpainting, IEEE Transactions on Image Processing, 13 (2004), 1200-1212.   Google Scholar

[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. Google Scholar

[16]

M. EladJ. L. StarckP. 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.  Google Scholar

[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.  Google Scholar

[18]

M. J. FadiliJ. L. Starck and F. Murtagh, Inpainting and zooming using sparse representations, The Computer Journal, 52 (2009), 64-791.   Google Scholar

[19]

R. Glowinski, Augmented Lagrangian and Operator Splitting Methods in Nonlinear Mechanics, SIAM, Philadelphia, 1989. Google Scholar

[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.   Google Scholar

[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. Google Scholar

[22]

W. LiL. ZhaoZ. LinD. Xu and D. Lu, Non-local image inpainting using low-rank matrix completion, Computer Graphics Forum, 34 (2015), 111-122.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[25]

L. I. RudinS. 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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[30]

M. ZhouH. ChenJ. PaisleyL. RenL. LiZ. XingD. DunsonG. 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.  Google Scholar

show all references

References:
[1]

P. AriasG. FaccioloV. 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.  Google Scholar

[2]

G. Aubert and P. Kornprobst, Mathematical Problems in Image Processing: Partial Differential Equations and the Calculus of Variations, Springer, 2006.  Google Scholar

[3]

J. F. AujolS. 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.  Google Scholar

[4]

M. BertalmioG. SapiroV. Caselles and C. Ballester, Image inpainting, Siggraph, 4 (2005), 417-424.   Google Scholar

[5]

A. L. BertozziS. 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.  Google Scholar

[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.  Google Scholar

[7]

M. BurgerL. 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.  Google Scholar

[8]

J. -F. CaiE. 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.  Google Scholar

[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.  Google Scholar

[10]

F. CaoY. GousseauS. Masnou and P. Prez, Geometrically guided exemplar-based inpainting, SIAM Journal on Imaging Sciences, 4 (2011), 1143-1179.  doi: 10.1137/110823572.  Google Scholar

[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.  Google Scholar

[12]

T. F. Chan and J. Shen, Nontexture inpainting by curvature-driven diffusions, Journal of Visual Communication & Image Representation, 12 (2001), 436-449.   Google Scholar

[13]

T. F. ChanS. 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.  Google Scholar

[14]

A. CriminisiP. Perez and K. Toyama, Region filling and object removal by exemplar-based image inpainting, IEEE Transactions on Image Processing, 13 (2004), 1200-1212.   Google Scholar

[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. Google Scholar

[16]

M. EladJ. L. StarckP. 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.  Google Scholar

[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.  Google Scholar

[18]

M. J. FadiliJ. L. Starck and F. Murtagh, Inpainting and zooming using sparse representations, The Computer Journal, 52 (2009), 64-791.   Google Scholar

[19]

R. Glowinski, Augmented Lagrangian and Operator Splitting Methods in Nonlinear Mechanics, SIAM, Philadelphia, 1989. Google Scholar

[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.   Google Scholar

[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. Google Scholar

[22]

W. LiL. ZhaoZ. LinD. Xu and D. Lu, Non-local image inpainting using low-rank matrix completion, Computer Graphics Forum, 34 (2015), 111-122.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[25]

L. I. RudinS. 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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[30]

M. ZhouH. ChenJ. PaisleyL. RenL. LiZ. XingD. DunsonG. 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.  Google Scholar

Figure 1.  Filling in the missing pixels by different inpainting method
Figure 2.  Comparison of details between different inpainting methods
Figure 3.  Scratch and text removal by different inpainting methods
Figure 4.  Comparison of details between different inpainting methods
Figure 5.  The relative error curves as functions of the iteration number on our experiments for the proposed-$\ell_1$ method
Figure 6.  The relative error curves as functions of the iteration number on our experiments for the proposed-$\ell_0$ method
Table 1.  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
Table 2.  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]

Jia Cai, Guanglong Xu, Zhensheng Hu. Sketch-based image retrieval via CAT loss with elastic net regularization. Mathematical Foundations of Computing, 2020, 3 (4) : 219-227. doi: 10.3934/mfc.2020013

[2]

Kha Van Huynh, Barbara Kaltenbacher. Some application examples of minimization based formulations of inverse problems and their regularization. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020074

[3]

Predrag S. Stanimirović, Branislav Ivanov, Haifeng Ma, Dijana Mosić. A survey of gradient methods for solving nonlinear optimization. Electronic Research Archive, 2020, 28 (4) : 1573-1624. doi: 10.3934/era.2020115

[4]

Xuefei He, Kun Wang, Liwei Xu. Efficient finite difference methods for the nonlinear Helmholtz equation in Kerr medium. Electronic Research Archive, 2020, 28 (4) : 1503-1528. doi: 10.3934/era.2020079

[5]

Xin Guo, Lei Shi. Preface of the special issue on analysis in data science: Methods and applications. Mathematical Foundations of Computing, 2020, 3 (4) : i-ii. doi: 10.3934/mfc.2020026

[6]

Shun Zhang, Jianlin Jiang, Su Zhang, Yibing Lv, Yuzhen Guo. ADMM-type methods for generalized multi-facility Weber problem. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020171

[7]

Shuyang Dai, Fengru Wang, Jerry Zhijian Yang, Cheng Yuan. A comparative study of atomistic-based stress evaluation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020322

[8]

Hong Niu, Zhijiang Feng, Qijin Xiao, Yajun Zhang. A PID control method based on optimal control strategy. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 117-126. doi: 10.3934/naco.2020019

[9]

Wenbin Li, Jianliang Qian. Simultaneously recovering both domain and varying density in inverse gravimetry by efficient level-set methods. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020073

[10]

Håkon Hoel, Gaukhar Shaimerdenova, Raúl Tempone. Multilevel Ensemble Kalman Filtering based on a sample average of independent EnKF estimators. Foundations of Data Science, 2020  doi: 10.3934/fods.2020017

[11]

Jie Zhang, Yuping Duan, Yue Lu, Michael K. Ng, Huibin Chang. Bilinear constraint based ADMM for mixed Poisson-Gaussian noise removal. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020071

[12]

S. Sadeghi, H. Jafari, S. Nemati. Solving fractional Advection-diffusion equation using Genocchi operational matrix based on Atangana-Baleanu derivative. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020435

[13]

Lingfeng Li, Shousheng Luo, Xue-Cheng Tai, Jiang Yang. A new variational approach based on level-set function for convex hull problem with outliers. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020070

[14]

Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077

[15]

Xuemei Chen, Julia Dobrosotskaya. Inpainting via sparse recovery with directional constraints. Mathematical Foundations of Computing, 2020, 3 (4) : 229-247. doi: 10.3934/mfc.2020025

[16]

Mehdi Bastani, Davod Khojasteh Salkuyeh. On the GSOR iteration method for image restoration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 27-43. doi: 10.3934/naco.2020013

[17]

Abdelghafour Atlas, Mostafa Bendahmane, Fahd Karami, Driss Meskine, Omar Oubbih. A nonlinear fractional reaction-diffusion system applied to image denoising and decomposition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020321

2019 Impact Factor: 1.373

Metrics

  • PDF downloads (172)
  • HTML views (279)
  • Cited by (1)

Other articles
by authors

[Back to Top]