Local block operators and TV regularization based image inpainting

Wei Wan; Haiyang Huang; Jun Liu

doi:10.3934/ipi.2018058

Article Contents

2018, Volume 12, Issue 6: 1389-1410. Doi: 10.3934/ipi.2018058

This issue Previous Article Lens rigidity with partial data in the presence of a magnetic field Next Article Inverse source problems in electrodynamics

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
* Corresponding author: jliu@bnu.edu.cn

Received: December 31, 2017

Revised: June 30, 2018

Published: November 2018

Abstract Full Text(HTML) Figure(6) / Table(2) Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 94A08; Secondary: 68U10.

Citation:

Full Text(HTML)

Figure 1. Filling in the missing pixels by different inpainting method

Download: Full-size image PowerPoint slide

Figure 2. Comparison of details between different inpainting methods

Download: Full-size image PowerPoint slide

Figure 3. Scratch and text removal by different inpainting methods

Download: Full-size image PowerPoint slide

Figure 4. Comparison of details between different inpainting methods

Download: Full-size image PowerPoint slide

Figure 5. The relative error curves as functions of the iteration number on our experiments for the proposed-$\ell_1$ method

Download: Full-size image PowerPoint slide

Figure 6. The relative error curves as functions of the iteration number on our experiments for the proposed-$\ell_0$ method

Download: Full-size image PowerPoint slide

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

Related Papers

Cited by

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.