doi: 10.3934/ipi.2021015

Large region inpainting by re-weighted regularized methods

School of Mathematics, Sun Yat-Sen University, 135 Xin Gang Xi Lu, Guangzhou, 510275, China

* Corresponding author: Jia Li

Received  April 2020 Revised  November 2020 Published  February 2021

Fund Project: The corresponding author's work is partially supported by NSFC young researchers' grant 11801594 and Guangdong-Hong Kong-Macau Applied Math Center grant 2020B1515310011

In the development of imaging science and image processing request in our daily life, inpainting large regions always plays an important role. However, the existing local regularized models and some patch manifold based non-local models are often not effective in restoring the features and patterns in the large missing regions. In this paper, we will apply a strategy of inpainting from outside to inside and propose a re-weighted matching algorithm by closest patch (RWCP), contributing to further enhancing the features in the missing large regions. Additionally, we propose another re-weighted matching algorithm by distance-based weighted average (RWWA), leading to a result with higher PSNR value in some cases. Numerical simulations will demonstrate that for large region inpainting, the proposed method is more applicable than most canonical methods. Moreover, combined with image denoising methods, the proposed model is also applicable for noisy image restoration with large missing regions.

Citation: Yiting Chen, Jia Li, Qingyun Yu. Large region inpainting by re-weighted regularized methods. Inverse Problems & Imaging, doi: 10.3934/ipi.2021015
References:
[1]

M. Aharon, M. Elad and A. Bruckstein, An algorithm for designing overcomplete dictionaries for sparse representation, IEEE Transactions on Signal Processing, 54 (2006). doi: 10.1109/TSP.2006.887825.  Google Scholar

[2]

P. Arias, V. Caselles and G. Sapiro, A variational framework for non-local image inpainting, 08 (2009), 345–358. Google Scholar

[3]

M. Bertalmio, G. Sapiro, V. Caselles and C. Ballester, Image inpainting, Siggraph'00, (2000), 417–424. doi: 10.1145/344779.344972.  Google Scholar

[4]

M. BertalmioL. VeseG. Sapiro and S. Osher, Simultaneous structure and texture image inpainting, IEEE Transactions on Image Processing, 12 (2003), 882-889.  doi: 10.1109/TIP.2003.815261.  Google Scholar

[5]

F. Bornemann and T. äMrz, Fast image inpainting based on coherence transport, Journal of Mathematical Imaging & Vision, 28 (2007), 259-278.  doi: 10.1007/s10851-007-0017-6.  Google Scholar

[6]

A. BuadesB. Coll and J.-M. Morel, A non-local algorithm for image denoising, 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05), 2 (2005), 60-65.   Google Scholar

[7]

A. Buades, B. Coll and J.-M. Morel, Image enhancement by non-local reverse heat equation, Preprint CMLA, 22 (2006), 2006. Google Scholar

[8]

J.-F. CaiR. H. ChanL. Shen and Z. Shen, Convergence analysis of tight framelet approach for missing data recovery, Advances in Computational Mathematics, 31 (2009), 87-113.  doi: 10.1007/s10444-008-9084-5.  Google Scholar

[9]

J.-F. CaiR. H. Chan and Z. Shen, A framelet-based image inpainting algorithm, Applied and Computational Harmonic Analysis, 24 (2008), 131-149.  doi: 10.1016/j.acha.2007.10.002.  Google Scholar

[10]

J.-F. CaiR. H. Chan and Z. Shen, Simultaneous cartoon and texture inpainting, Inverse Probl. Imaging, 4 (2010), 379-395.  doi: 10.3934/ipi.2010.4.379.  Google Scholar

[11]

J.-F. CaiH. JiZ. Shen and G.-B. Ye, Data-driven tight frame construction and image denoising, Applied and Computational Harmonic Analysis, 37 (2014), 89-105.  doi: 10.1016/j.acha.2013.10.001.  Google Scholar

[12]

R. Chan, L. Shen and Z. Shen, A framelet-based approach for image inpainting, Research Report, 4 (2005), 325. 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]

T. F. Chan and J. Shen, Image Processing and Analysis: Variational, PDE, Wavelet, and Stochastic Methods, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2005. doi: 10.1137/1.9780898717877.  Google Scholar

[15]

T. F. Chan and J. Shen, Variational image inpainting, Commun. Pure Appl. Math, 58 (2005), 579-619.  doi: 10.1002/cpa.20075.  Google Scholar

[16]

T. F. ChanJ. Shen and H.-M. Zhou, Total variation wavelet inpainting, Journal of Mathematical Imaging and Vision, 25 (2006), 107-125.  doi: 10.1007/s10851-006-5257-3.  Google Scholar

[17]

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

[18]

K. Dabov, A. Foi, V. Katkovnik and K. Egiazarian, Image denoising with block-matching and 3D filtering, in Electronic Imaging 2006, International Society for Optics and Photonics, (2006), 606414–606414. Google Scholar

[19]

B. DongH. JiJ. LiZ. Shen and Y. Xu, Wavelet frame based blind image inpainting, Applied and Computational Harmonic Analysis, 32 (2012), 268-279.  doi: 10.1016/j.acha.2011.06.001.  Google Scholar

[20]

B. Dong and Z. Shen, MRA based wavelet frames and applications, IAS Lecture Notes Series, Summer Program on "Mathematics of Image Processing", IAS/Park City Math. Ser., 19, Amer. Math. Soc., Providence, RI, 2013, 9–158. doi: 10.1090/pcms/019/02.  Google Scholar

[21]

W. DongG. ShiX. LiY. Ma and F. Huang, Compressive sensing via nonlocal low-rank regularization, IEEE Transactions on Image Processing, 23 (2014), 3618-3632.  doi: 10.1109/TIP.2014.2329449.  Google Scholar

[22]

W. DongG. Shi and X. li, Nonlocal image restoration with bilateral variance estimation: A low-rank approach, IEEE Transactions on Image Processing, 22 (2013), 700-711.  doi: 10.1109/TIP.2012.2221729.  Google Scholar

[23]

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

[24]

M. J. FadiliJ. L. Starck and F. Murtagh, Inpainting and zooming using sparse representations, Comput. J., 52 (2009), 64-79.   Google Scholar

[25]

G. Gilboa and S. Osher, Nonlocal operators with applications to image processing, Multiscale Model. Simul., 7 (2008), 1005-1028.  doi: 10.1137/070698592.  Google Scholar

[26]

G. Gilboa, N. Sochen and Y. Zeevi, Image enhancement and denoising by complex diffusion processes, Pattern Analysis and Machine Intelligence, IEEE Transactions on, 26 (2004), 1020–1036. Google Scholar

[27]

G. GilboaN. Sochen and Y. Y. Zeevi, Forward-and-backward diffusion processes for adaptive image enhancement and denoising, IEEE Transactions on Image Processing, 11 (2002), 689-703.  doi: 10.1109/TIP.2002.800883.  Google Scholar

[28]

R. Glowinski and P. Le Tallec, Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics, SIAM, 1989. doi: 10.1137/1.9781611970838.  Google Scholar

[29]

H. JiZ. Shen and Y. Xu, Wavelet frame based image restoration with missing/damaged pixels, East Asia Journal on Applied Mathematics, 1 (2011), 108-131.   Google Scholar

[30]

R. Lai and J. Li, Manifold based low-rank regularization for image restoration and semi-supervised learning, Journal of Scientific Computing, 74 (2018), 1241-1263.  doi: 10.1007/s10915-017-0492-x.  Google Scholar

[31]

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

[32]

T. März, Image inpainting based on coherence transport with adapted distance functions, SIAM Journal on Imaging Sciences, 4 (2011), 981-1000.  doi: 10.1137/100807296.  Google Scholar

[33]

A. NewsonA. AlmansaY. Gousseau and P. Pérez, Non-local patch-based image inpainting, IPOL J. Image Processing On Line, 7 (2017), 373-385.  doi: 10.5201/ipol.2017.189.  Google Scholar

[34]

S. OsherZ. Shi and W. Zhu, Low dimensional manifold model for image processing, SIAM Journal on Imaging Sciences, 10 (2017), 1669-1690.  doi: 10.1137/16M1058686.  Google Scholar

[35]

A. Ron and Z. Shen, Affine Systems in $ L_2(\mathbb{R}^d)$: The Analysis of the Analysis Operator, Journal of Functional Analysis, 148 (1997), 408-447.  doi: 10.1006/jfan.1996.3079.  Google Scholar

[36]

Z. Shen, Wavelet frames and image restorations, Proceedings of the International Congress of Mathematicians, Volume IV, Hindustan Book Agency, New Delhi, 2010, 2834–2863.  Google Scholar

[37]

Z. Shi, S. Osher and W. Zhu, Weighted graph laplacian and image inpainting, Journal of Scientific Computing, 577 (2017). Google Scholar

[38]

J. Yu, Z. Lin, J. Yang, X. Shen, X. Lu and T. Huang, Generative image inpainting with contextual attention, 06 (2018), 5505–5514. Google Scholar

[39]

K. ZhangW. ZuoY. ChenD. Meng and L. Zhang, Beyond a gaussian denoiser: Residual learning of deep cnn for image denoising, IEEE Transactions on Image Processing, 26 (2017), 3142-3155.  doi: 10.1109/TIP.2017.2662206.  Google Scholar

show all references

References:
[1]

M. Aharon, M. Elad and A. Bruckstein, An algorithm for designing overcomplete dictionaries for sparse representation, IEEE Transactions on Signal Processing, 54 (2006). doi: 10.1109/TSP.2006.887825.  Google Scholar

[2]

P. Arias, V. Caselles and G. Sapiro, A variational framework for non-local image inpainting, 08 (2009), 345–358. Google Scholar

[3]

M. Bertalmio, G. Sapiro, V. Caselles and C. Ballester, Image inpainting, Siggraph'00, (2000), 417–424. doi: 10.1145/344779.344972.  Google Scholar

[4]

M. BertalmioL. VeseG. Sapiro and S. Osher, Simultaneous structure and texture image inpainting, IEEE Transactions on Image Processing, 12 (2003), 882-889.  doi: 10.1109/TIP.2003.815261.  Google Scholar

[5]

F. Bornemann and T. äMrz, Fast image inpainting based on coherence transport, Journal of Mathematical Imaging & Vision, 28 (2007), 259-278.  doi: 10.1007/s10851-007-0017-6.  Google Scholar

[6]

A. BuadesB. Coll and J.-M. Morel, A non-local algorithm for image denoising, 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05), 2 (2005), 60-65.   Google Scholar

[7]

A. Buades, B. Coll and J.-M. Morel, Image enhancement by non-local reverse heat equation, Preprint CMLA, 22 (2006), 2006. Google Scholar

[8]

J.-F. CaiR. H. ChanL. Shen and Z. Shen, Convergence analysis of tight framelet approach for missing data recovery, Advances in Computational Mathematics, 31 (2009), 87-113.  doi: 10.1007/s10444-008-9084-5.  Google Scholar

[9]

J.-F. CaiR. H. Chan and Z. Shen, A framelet-based image inpainting algorithm, Applied and Computational Harmonic Analysis, 24 (2008), 131-149.  doi: 10.1016/j.acha.2007.10.002.  Google Scholar

[10]

J.-F. CaiR. H. Chan and Z. Shen, Simultaneous cartoon and texture inpainting, Inverse Probl. Imaging, 4 (2010), 379-395.  doi: 10.3934/ipi.2010.4.379.  Google Scholar

[11]

J.-F. CaiH. JiZ. Shen and G.-B. Ye, Data-driven tight frame construction and image denoising, Applied and Computational Harmonic Analysis, 37 (2014), 89-105.  doi: 10.1016/j.acha.2013.10.001.  Google Scholar

[12]

R. Chan, L. Shen and Z. Shen, A framelet-based approach for image inpainting, Research Report, 4 (2005), 325. 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]

T. F. Chan and J. Shen, Image Processing and Analysis: Variational, PDE, Wavelet, and Stochastic Methods, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2005. doi: 10.1137/1.9780898717877.  Google Scholar

[15]

T. F. Chan and J. Shen, Variational image inpainting, Commun. Pure Appl. Math, 58 (2005), 579-619.  doi: 10.1002/cpa.20075.  Google Scholar

[16]

T. F. ChanJ. Shen and H.-M. Zhou, Total variation wavelet inpainting, Journal of Mathematical Imaging and Vision, 25 (2006), 107-125.  doi: 10.1007/s10851-006-5257-3.  Google Scholar

[17]

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

[18]

K. Dabov, A. Foi, V. Katkovnik and K. Egiazarian, Image denoising with block-matching and 3D filtering, in Electronic Imaging 2006, International Society for Optics and Photonics, (2006), 606414–606414. Google Scholar

[19]

B. DongH. JiJ. LiZ. Shen and Y. Xu, Wavelet frame based blind image inpainting, Applied and Computational Harmonic Analysis, 32 (2012), 268-279.  doi: 10.1016/j.acha.2011.06.001.  Google Scholar

[20]

B. Dong and Z. Shen, MRA based wavelet frames and applications, IAS Lecture Notes Series, Summer Program on "Mathematics of Image Processing", IAS/Park City Math. Ser., 19, Amer. Math. Soc., Providence, RI, 2013, 9–158. doi: 10.1090/pcms/019/02.  Google Scholar

[21]

W. DongG. ShiX. LiY. Ma and F. Huang, Compressive sensing via nonlocal low-rank regularization, IEEE Transactions on Image Processing, 23 (2014), 3618-3632.  doi: 10.1109/TIP.2014.2329449.  Google Scholar

[22]

W. DongG. Shi and X. li, Nonlocal image restoration with bilateral variance estimation: A low-rank approach, IEEE Transactions on Image Processing, 22 (2013), 700-711.  doi: 10.1109/TIP.2012.2221729.  Google Scholar

[23]

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

[24]

M. J. FadiliJ. L. Starck and F. Murtagh, Inpainting and zooming using sparse representations, Comput. J., 52 (2009), 64-79.   Google Scholar

[25]

G. Gilboa and S. Osher, Nonlocal operators with applications to image processing, Multiscale Model. Simul., 7 (2008), 1005-1028.  doi: 10.1137/070698592.  Google Scholar

[26]

G. Gilboa, N. Sochen and Y. Zeevi, Image enhancement and denoising by complex diffusion processes, Pattern Analysis and Machine Intelligence, IEEE Transactions on, 26 (2004), 1020–1036. Google Scholar

[27]

G. GilboaN. Sochen and Y. Y. Zeevi, Forward-and-backward diffusion processes for adaptive image enhancement and denoising, IEEE Transactions on Image Processing, 11 (2002), 689-703.  doi: 10.1109/TIP.2002.800883.  Google Scholar

[28]

R. Glowinski and P. Le Tallec, Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics, SIAM, 1989. doi: 10.1137/1.9781611970838.  Google Scholar

[29]

H. JiZ. Shen and Y. Xu, Wavelet frame based image restoration with missing/damaged pixels, East Asia Journal on Applied Mathematics, 1 (2011), 108-131.   Google Scholar

[30]

R. Lai and J. Li, Manifold based low-rank regularization for image restoration and semi-supervised learning, Journal of Scientific Computing, 74 (2018), 1241-1263.  doi: 10.1007/s10915-017-0492-x.  Google Scholar

[31]

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

[32]

T. März, Image inpainting based on coherence transport with adapted distance functions, SIAM Journal on Imaging Sciences, 4 (2011), 981-1000.  doi: 10.1137/100807296.  Google Scholar

[33]

A. NewsonA. AlmansaY. Gousseau and P. Pérez, Non-local patch-based image inpainting, IPOL J. Image Processing On Line, 7 (2017), 373-385.  doi: 10.5201/ipol.2017.189.  Google Scholar

[34]

S. OsherZ. Shi and W. Zhu, Low dimensional manifold model for image processing, SIAM Journal on Imaging Sciences, 10 (2017), 1669-1690.  doi: 10.1137/16M1058686.  Google Scholar

[35]

A. Ron and Z. Shen, Affine Systems in $ L_2(\mathbb{R}^d)$: The Analysis of the Analysis Operator, Journal of Functional Analysis, 148 (1997), 408-447.  doi: 10.1006/jfan.1996.3079.  Google Scholar

[36]

Z. Shen, Wavelet frames and image restorations, Proceedings of the International Congress of Mathematicians, Volume IV, Hindustan Book Agency, New Delhi, 2010, 2834–2863.  Google Scholar

[37]

Z. Shi, S. Osher and W. Zhu, Weighted graph laplacian and image inpainting, Journal of Scientific Computing, 577 (2017). Google Scholar

[38]

J. Yu, Z. Lin, J. Yang, X. Shen, X. Lu and T. Huang, Generative image inpainting with contextual attention, 06 (2018), 5505–5514. Google Scholar

[39]

K. ZhangW. ZuoY. ChenD. Meng and L. Zhang, Beyond a gaussian denoiser: Residual learning of deep cnn for image denoising, IEEE Transactions on Image Processing, 26 (2017), 3142-3155.  doi: 10.1109/TIP.2017.2662206.  Google Scholar

Figure 1.  Large region ipainting by some canonical and recent methods
Figure 2.  An example of similar patches in fruits image
Figure 5.  Large region inpainting for a fruits image
Figure 3.  Convergence curve for the object functions in Algorithm 2. The left image is the convergence curve for RWMC model and the right image is that for RWWA model
Figure 4.  The result of large region inpainting from noisy images with Gaussian noise $ \sigma = 10 $
Figure 6.  Numerical results for boat and bricks image inpainting from missing large region
Figure 7.  Edge detection of inpainting results via Canny operator
Figure 8.  Large region inpainting from images with Gaussian noise by Algorithm 3
[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]

Ritu Agarwal, Kritika, Sunil Dutt Purohit, Devendra Kumar. Mathematical modelling of cytosolic calcium concentration distribution using non-local fractional operator. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021017

[3]

Bouthaina Abdelhedi, Hatem Zaag. Single point blow-up and final profile for a perturbed nonlinear heat equation with a gradient and a non-local term. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021032

[4]

Umberto Biccari. Internal control for a non-local Schrödinger equation involving the fractional Laplace operator. Evolution Equations & Control Theory, 2021  doi: 10.3934/eect.2021014

[5]

Zhiming Guo, Zhi-Chun Yang, Xingfu Zou. Existence and uniqueness of positive solution to a non-local differential equation with homogeneous Dirichlet boundary condition---A non-monotone case. Communications on Pure & Applied Analysis, 2012, 11 (5) : 1825-1838. doi: 10.3934/cpaa.2012.11.1825

[6]

Andreas Neubauer. On Tikhonov-type regularization with approximated penalty terms. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2021027

[7]

Ahmad Mousavi, Zheming Gao, Lanshan Han, Alvin Lim. Quadratic surface support vector machine with L1 norm regularization. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021046

[8]

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

[9]

Dingheng Pi. Periodic orbits for double regularization of piecewise smooth systems with a switching manifold of codimension two. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021080

[10]

De-han Chen, Daijun jiang. Convergence rates of Tikhonov regularization for recovering growth rates in a Lotka-Volterra competition model with diffusion. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2021023

[11]

Antonio De Rosa, Domenico Angelo La Manna. A non local approximation of the Gaussian perimeter: Gamma convergence and Isoperimetric properties. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021059

[12]

Lekbir Afraites, Abdelghafour Atlas, Fahd Karami, Driss Meskine. Some class of parabolic systems applied to image processing. Discrete & Continuous Dynamical Systems - B, 2016, 21 (6) : 1671-1687. doi: 10.3934/dcdsb.2016017

[13]

Paul E. Anderson, Timothy P. Chartier, Amy N. Langville, Kathryn E. Pedings-Behling. The rankability of weighted data from pairwise comparisons. Foundations of Data Science, 2021, 3 (1) : 1-26. doi: 10.3934/fods.2021002

[14]

John Villavert. On problems with weighted elliptic operator and general growth nonlinearities. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021023

[15]

Zhihua Zhang, Naoki Saito. PHLST with adaptive tiling and its application to antarctic remote sensing image approximation. Inverse Problems & Imaging, 2014, 8 (1) : 321-337. doi: 10.3934/ipi.2014.8.321

[16]

Israa Mohammed Khudher, Yahya Ismail Ibrahim, Suhaib Abduljabbar Altamir. Individual biometrics pattern based artificial image analysis techniques. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2020056

[17]

Jon Aaronson, Dalia Terhesiu. Local limit theorems for suspended semiflows. Discrete & Continuous Dynamical Systems, 2020, 40 (12) : 6575-6609. doi: 10.3934/dcds.2020294

[18]

Min Li. A three term Polak-Ribière-Polyak conjugate gradient method close to the memoryless BFGS quasi-Newton method. Journal of Industrial & Management Optimization, 2020, 16 (1) : 245-260. doi: 10.3934/jimo.2018149

[19]

Jonathan DeWitt. Local Lyapunov spectrum rigidity of nilmanifold automorphisms. Journal of Modern Dynamics, 2021, 17: 65-109. doi: 10.3934/jmd.2021003

[20]

Ademir Fernando Pazoto, Lionel Rosier. Uniform stabilization in weighted Sobolev spaces for the KdV equation posed on the half-line. Discrete & Continuous Dynamical Systems - B, 2010, 14 (4) : 1511-1535. doi: 10.3934/dcdsb.2010.14.1511

2019 Impact Factor: 1.373

Article outline

Figures and Tables

[Back to Top]