# American Institute of Mathematical Sciences

October  2021, 15(5): 827-842. 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  October 2021 Early access  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, 2021, 15 (5) : 827-842. 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. Bertalmio, L. Vese, G. 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. Buades, B. 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. Cai, R. H. Chan, L. 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. Cai, R. 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. Cai, R. 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. Cai, H. Ji, Z. 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. 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.  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. Chan, J. 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. Criminisi, P. 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. Dong, H. Ji, J. Li, Z. 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. Dong, G. Shi, X. Li, Y. 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. Dong, G. 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. 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.  Google Scholar [24] M. J. Fadili, J. 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. Gilboa, N. 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. Ji, Z. 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. Newson, A. Almansa, Y. 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. Osher, Z. 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. Zhang, W. Zuo, Y. Chen, D. 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. Bertalmio, L. Vese, G. 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. Buades, B. 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. Cai, R. H. Chan, L. 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. Cai, R. 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. Cai, R. 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. Cai, H. Ji, Z. 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. 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.  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. Chan, J. 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. Criminisi, P. 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. Dong, H. Ji, J. Li, Z. 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. Dong, G. Shi, X. Li, Y. 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. Dong, G. 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. 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.  Google Scholar [24] M. J. Fadili, J. 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. Gilboa, N. 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. Ji, Z. 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. Newson, A. Almansa, Y. 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. Osher, Z. 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. Zhang, W. Zuo, Y. Chen, D. 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
Large region ipainting by some canonical and recent methods
An example of similar patches in fruits image
Large region inpainting for a fruits image
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
The result of large region inpainting from noisy images with Gaussian noise $\sigma = 10$
Numerical results for boat and bricks image inpainting from missing large region
Edge detection of inpainting results via Canny operator
Large region inpainting from images with Gaussian noise by Algorithm 3
 [1] 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 [2] Gabriel Peyré, Sébastien Bougleux, Laurent Cohen. Non-local regularization of inverse problems. Inverse Problems & Imaging, 2011, 5 (2) : 511-530. doi: 10.3934/ipi.2011.5.511 [3] Ruiqiang He, Xiangchu Feng, Xiaolong Zhu, Hua Huang, Bingzhe Wei. RWRM: Residual Wasserstein regularization model for image restoration. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020069 [4] Matteo Negri. Crack propagation by a regularization of the principle of local symmetry. Discrete & Continuous Dynamical Systems - S, 2013, 6 (1) : 147-165. doi: 10.3934/dcdss.2013.6.147 [5] Victor Churchill, Rick Archibald, Anne Gelb. Edge-adaptive $\ell_2$ regularization image reconstruction from non-uniform Fourier data. Inverse Problems & Imaging, 2019, 13 (5) : 931-958. doi: 10.3934/ipi.2019042 [6] Badr Saad T. Alkahtani, Ilknur Koca. A new numerical scheme applied on re-visited nonlinear model of predator-prey based on derivative with non-local and non-singular kernel. Discrete & Continuous Dynamical Systems - S, 2020, 13 (3) : 429-442. doi: 10.3934/dcdss.2020024 [7] Yuan Wang, Zhi-Feng Pang, Yuping Duan, Ke Chen. Image retinex based on the nonconvex TV-type regularization. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020050 [8] 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 [9] Bartomeu Coll, Joan Duran, Catalina Sbert. Half-linear regularization for nonconvex image restoration models. Inverse Problems & Imaging, 2015, 9 (2) : 337-370. doi: 10.3934/ipi.2015.9.337 [10] Wei Wan, Weihong Guo, Jun Liu, Haiyang Huang. Non-local blind hyperspectral image super-resolution via 4d sparse tensor factorization and low-rank. Inverse Problems & Imaging, 2020, 14 (2) : 339-361. doi: 10.3934/ipi.2020015 [11] Len Margolin, Catherine Plesko. Discrete regularization. Evolution Equations & Control Theory, 2019, 8 (1) : 117-137. doi: 10.3934/eect.2019007 [12] Qinghua Ma, Zuoliang Xu, Liping Wang. Recovery of the local volatility function using regularization and a gradient projection method. Journal of Industrial & Management Optimization, 2015, 11 (2) : 421-437. doi: 10.3934/jimo.2015.11.421 [13] Qiyu Jin, Ion Grama, Quansheng Liu. Convergence theorems for the Non-Local Means filter. Inverse Problems & Imaging, 2018, 12 (4) : 853-881. doi: 10.3934/ipi.2018036 [14] Olivier Bonnefon, Jérôme Coville, Guillaume Legendre. Concentration phenomenon in some non-local equation. Discrete & Continuous Dynamical Systems - B, 2017, 22 (3) : 763-781. doi: 10.3934/dcdsb.2017037 [15] 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 [16] Huan Han. A variational model with fractional-order regularization term arising in registration of diffusion tensor image. Inverse Problems & Imaging, 2018, 12 (6) : 1263-1291. doi: 10.3934/ipi.2018053 [17] Daniela Calvetti, Erkki Somersalo. Microlocal sequential regularization in imaging. Inverse Problems & Imaging, 2007, 1 (1) : 1-11. doi: 10.3934/ipi.2007.1.1 [18] Gernot Holler, Karl Kunisch. Learning nonlocal regularization operators. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021003 [19] Henri Berestycki, Nancy Rodríguez. A non-local bistable reaction-diffusion equation with a gap. Discrete & Continuous Dynamical Systems, 2017, 37 (2) : 685-723. doi: 10.3934/dcds.2017029 [20] Matteo Focardi. Vector-valued obstacle problems for non-local energies. Discrete & Continuous Dynamical Systems - B, 2012, 17 (2) : 487-507. doi: 10.3934/dcdsb.2012.17.487

2020 Impact Factor: 1.639