November  2020, 3(4): 229-247. doi: 10.3934/mfc.2020025

Inpainting via sparse recovery with directional constraints

1. 

Department of Mathematics and Statistics, University of North Carolina Wilmington, Wilmington, NC 28403, USA

2. 

Department of Mathematics, Applied Mathematics and Statistics, Case Western Reserve University, Cleveland, OH 44106, USA

* Corresponding author: Xuemei Chen

Received  February 2020 Revised  October 2020 Published  November 2020

Fund Project: The first author is supported by NSF DMS-2050028

Image inpainting is a particular case of image completion problem. We describe a novel method allowing to amend the general scenario of using sparse or TV-based recovery for inpainting purposes by an efficient use of adaptive one-dimensional directional "sensing" into the unknown domain. We analyze the smoothness of the image near each pixel on the boundary of the unknown domain and formulate linear constraints designed to promote smooth transitions from the known domain in the directions where smooth behavior have been detected. We include a theoretical result relaxing the widely known sufficient condition of sparse recovery based on coherence, as well as observations on how adding the directional constraints can improve the well-posedness of sparse inpainting.

The numerical implementation of our method is based on ADMM. Examples of inpainting of natural images and binary images with edges crossing the unknown domain demonstrate significant improvement of recovery quality in the presence of adaptive directional constraints. We conclude that the introduced framework is general enough to offer a lot of flexibility and be successfully utilized in a multitude of image recovery scenarios.

Citation: 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
References:
[1]

A. AldroubiX. Chen and A. M. Powell, Perturbations of measurement matrices and dictionaries in compressed sensing, Appl. Comput. Harmon. Anal., 33 (2012), 282-291.  doi: 10.1016/j.acha.2011.12.002.  Google Scholar

[2]

C. BaoH. Ji and Z. Shen, Convergence analysis for iterative data-driven tight frame construction scheme, Appl. Comput. Harmon. Anal., 38 (2015), 510-523.  doi: 10.1016/j.acha.2014.06.007.  Google Scholar

[3]

M. Bertalmio, A. L. Bertozzi and G. Sapiro, Navier-Stokes, fluid dynamics, and image and video inpainting, Proc. IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Kauai, HI, 2001,355–362. doi: 10.1109/CVPR.2001.990497.  Google Scholar

[4]

M. Bertalmio, G. Sapiro, V. Caselles and C. Ballester, Image inpainting, Proc. 27th Conference on Computer Graphics and Interactive Techniques, 2000,417–424. doi: 10.21236/ADA437378.  Google Scholar

[5]

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

[6]

A. BertozziS. Esedoḡlu and A. Gillette, Analysis of a two-scale Cahn-Hilliard model for binary image inpainting, Multiscale Model. Simul., 6 (2007), 913-936.  doi: 10.1137/060660631.  Google Scholar

[7]

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

[8]

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

[9]

J.-F. CaiS. Osher and Z. Shen, Split Bregman methods and frame based image restoration, Multiscale Model. Simul., 8 (2009/10), 337-369.  doi: 10.1137/090753504.  Google Scholar

[10]

E. J. CandèsY. C. EldarD. Needell and P. Randall, Compressed sensing with coherent and redundant dictionaries, Appl. Comput. Harmon. Anal., 31 (2011), 59-73.  doi: 10.1016/j.acha.2010.10.002.  Google Scholar

[11]

E. J. Candès, X. Li, Y. Ma and J. Wright, Robust principal component analysis?, J. ACM, 58 (2011), 37pp. doi: 10.1145/1970392.1970395.  Google Scholar

[12]

E. J. CandèsJ. K. Romberg and T. Tao, Stable signal recovery from incomplete and inaccurate measurements, Comm. Pure Appl. Math., 59 (2006), 1207-1223.  doi: 10.1002/cpa.20124.  Google Scholar

[13]

P. G. Casazza, The art of frame theory, Taiwanese J. Math., 4 (2000), 129-201.  doi: 10.11650/twjm/1500407227.  Google Scholar

[14]

T. F. Chan and J. Shen, Mathematical models for local nontexture inpaintings, SIAM J. Appl. Math., 62 (2001/02), 1019-1043.  doi: 10.1137/S0036139900368844.  Google Scholar

[15]

A. CriminisiP. Pérez and K. Toyama, Region filling and object removal by exemplar-based image inpainting, IEEE Trans. Image Processing, 13 (2004), 1200-1212.  doi: 10.1109/TIP.2004.833105.  Google Scholar

[16]

J. Darbon and M. Sigelle, A fast and exact algorithm for total variation minimization, in Pattern Recognition and Image Analysis, Lecture Notes in Computer Science, 3522, Springer, 2005,351–359. doi: 10.1007/11492429_43.  Google Scholar

[17]

J. Dobrosotskaya and W. Guo, Data adaptive multi-scale representations for image analysis, in Wavelets and Sparsity XVIII, 11138, International Society for Optics and Photonics, 2019. doi: 10.1117/12.2529695.  Google Scholar

[18]

B. Dong and Z. Shen, Image restoration: A data-driven perspective, Proceedings of the 8th International Congress on Industrial and Applied Mathematics, Higher Ed. Press, Beijing, 2015, 65-108.  Google Scholar

[19]

D. L. Donoho, Compressed sensing, IEEE Trans. Inform. Theory, 52 (2006), 1289-1306.  doi: 10.1109/TIT.2006.871582.  Google Scholar

[20]

A. A. Efros and T. K. Leung, Texture synthesis by non-parametric sampling, Proceedings of the Seventh IEEE International Conference on Computer Vision, Kerkyra, Greece, 1999. doi: 10.1109/ICCV.1999.790383.  Google Scholar

[21]

M. EladJ.-L. StarckP. Querre and D.-L. Donoho, Simultaneous cartoon and texture image inpainting using morphological component analysis (MCA), Appl. Comput. Harmon. Anal., 19 (2005), 340-358.  doi: 10.1016/j.acha.2005.03.005.  Google Scholar

[22]

B. HanG. Kutyniok and Z. Shen, Adaptive multiresolution analysis structures and shearlet systems, SIAM J. Numer. Anal., 49 (2011), 1921-1946.  doi: 10.1137/090780912.  Google Scholar

[23]

E. J. KingG. Kutyniok and X. Zhuang, Analysis of inpainting via clustered sparsity and microlocal analysis, J. Math. Imaging Vision, 48 (2014), 205-234.  doi: 10.1007/s10851-013-0422-y.  Google Scholar

[24]

M. LustigD. Donoho and J. M. Pauly, Sparse MRI: The application of compressed sensing for rapid MR imaging, Magnetic Resonance in Medicine, 58 (2007), 1182-1195.  doi: 10.1002/mrm.21391.  Google Scholar

[25] S. Mallat, A Wavelet Tour of Signal Processing, Elsevier/Academic Press, Amsterdam, 2009.  doi: 10.1016/B978-0-12-374370-1.X0001-8.  Google Scholar
[26] Y. Meyer, Wavelets and Operators, Cambridge Studies in Advanced Mathematics, 37, Cambridge University Press, Cambridge, 1992.   Google Scholar
[27]

N. Parikh and S. Boyd, Proximal Algorithms, Now Foundations and Trends, 2014,128pp. doi: 10.1561/9781601987174.  Google Scholar

[28]

Y. QuanH. Ji and Z. Shen, Data-driven multi-scale non-local wavelet frame construction and image recovery, J. Sci. Comput., 63 (2015), 307-329.  doi: 10.1007/s10915-014-9893-2.  Google Scholar

[29]

L. I. RudinS. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms, Phys. D, 60 (1992), 259-268.  doi: 10.1016/0167-2789(92)90242-F.  Google Scholar

[30]

S. F. D. Waldron, An Introduction to Finite Tight Frames, Applied and Numerical Harmonic Analysis, Birkhäuser/Springer, New York, 2018. doi: 10.1007/978-0-8176-4815-2.  Google Scholar

[31]

Y. WangJ. YangW. Yin and Y. Zhang, A new alternating minimization algorithm for total variation image reconstruction, SIAM J. Imaging Sci., 1 (2008), 248-272.  doi: 10.1137/080724265.  Google Scholar

[32]

Z. Xu and J. Sun, Image inpainting by patch propagation using patch sparsity, IEEE Trans. Image Process., 19 (2010), 1153-1165.  doi: 10.1109/TIP.2010.2042098.  Google Scholar

show all references

References:
[1]

A. AldroubiX. Chen and A. M. Powell, Perturbations of measurement matrices and dictionaries in compressed sensing, Appl. Comput. Harmon. Anal., 33 (2012), 282-291.  doi: 10.1016/j.acha.2011.12.002.  Google Scholar

[2]

C. BaoH. Ji and Z. Shen, Convergence analysis for iterative data-driven tight frame construction scheme, Appl. Comput. Harmon. Anal., 38 (2015), 510-523.  doi: 10.1016/j.acha.2014.06.007.  Google Scholar

[3]

M. Bertalmio, A. L. Bertozzi and G. Sapiro, Navier-Stokes, fluid dynamics, and image and video inpainting, Proc. IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Kauai, HI, 2001,355–362. doi: 10.1109/CVPR.2001.990497.  Google Scholar

[4]

M. Bertalmio, G. Sapiro, V. Caselles and C. Ballester, Image inpainting, Proc. 27th Conference on Computer Graphics and Interactive Techniques, 2000,417–424. doi: 10.21236/ADA437378.  Google Scholar

[5]

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

[6]

A. BertozziS. Esedoḡlu and A. Gillette, Analysis of a two-scale Cahn-Hilliard model for binary image inpainting, Multiscale Model. Simul., 6 (2007), 913-936.  doi: 10.1137/060660631.  Google Scholar

[7]

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

[8]

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

[9]

J.-F. CaiS. Osher and Z. Shen, Split Bregman methods and frame based image restoration, Multiscale Model. Simul., 8 (2009/10), 337-369.  doi: 10.1137/090753504.  Google Scholar

[10]

E. J. CandèsY. C. EldarD. Needell and P. Randall, Compressed sensing with coherent and redundant dictionaries, Appl. Comput. Harmon. Anal., 31 (2011), 59-73.  doi: 10.1016/j.acha.2010.10.002.  Google Scholar

[11]

E. J. Candès, X. Li, Y. Ma and J. Wright, Robust principal component analysis?, J. ACM, 58 (2011), 37pp. doi: 10.1145/1970392.1970395.  Google Scholar

[12]

E. J. CandèsJ. K. Romberg and T. Tao, Stable signal recovery from incomplete and inaccurate measurements, Comm. Pure Appl. Math., 59 (2006), 1207-1223.  doi: 10.1002/cpa.20124.  Google Scholar

[13]

P. G. Casazza, The art of frame theory, Taiwanese J. Math., 4 (2000), 129-201.  doi: 10.11650/twjm/1500407227.  Google Scholar

[14]

T. F. Chan and J. Shen, Mathematical models for local nontexture inpaintings, SIAM J. Appl. Math., 62 (2001/02), 1019-1043.  doi: 10.1137/S0036139900368844.  Google Scholar

[15]

A. CriminisiP. Pérez and K. Toyama, Region filling and object removal by exemplar-based image inpainting, IEEE Trans. Image Processing, 13 (2004), 1200-1212.  doi: 10.1109/TIP.2004.833105.  Google Scholar

[16]

J. Darbon and M. Sigelle, A fast and exact algorithm for total variation minimization, in Pattern Recognition and Image Analysis, Lecture Notes in Computer Science, 3522, Springer, 2005,351–359. doi: 10.1007/11492429_43.  Google Scholar

[17]

J. Dobrosotskaya and W. Guo, Data adaptive multi-scale representations for image analysis, in Wavelets and Sparsity XVIII, 11138, International Society for Optics and Photonics, 2019. doi: 10.1117/12.2529695.  Google Scholar

[18]

B. Dong and Z. Shen, Image restoration: A data-driven perspective, Proceedings of the 8th International Congress on Industrial and Applied Mathematics, Higher Ed. Press, Beijing, 2015, 65-108.  Google Scholar

[19]

D. L. Donoho, Compressed sensing, IEEE Trans. Inform. Theory, 52 (2006), 1289-1306.  doi: 10.1109/TIT.2006.871582.  Google Scholar

[20]

A. A. Efros and T. K. Leung, Texture synthesis by non-parametric sampling, Proceedings of the Seventh IEEE International Conference on Computer Vision, Kerkyra, Greece, 1999. doi: 10.1109/ICCV.1999.790383.  Google Scholar

[21]

M. EladJ.-L. StarckP. Querre and D.-L. Donoho, Simultaneous cartoon and texture image inpainting using morphological component analysis (MCA), Appl. Comput. Harmon. Anal., 19 (2005), 340-358.  doi: 10.1016/j.acha.2005.03.005.  Google Scholar

[22]

B. HanG. Kutyniok and Z. Shen, Adaptive multiresolution analysis structures and shearlet systems, SIAM J. Numer. Anal., 49 (2011), 1921-1946.  doi: 10.1137/090780912.  Google Scholar

[23]

E. J. KingG. Kutyniok and X. Zhuang, Analysis of inpainting via clustered sparsity and microlocal analysis, J. Math. Imaging Vision, 48 (2014), 205-234.  doi: 10.1007/s10851-013-0422-y.  Google Scholar

[24]

M. LustigD. Donoho and J. M. Pauly, Sparse MRI: The application of compressed sensing for rapid MR imaging, Magnetic Resonance in Medicine, 58 (2007), 1182-1195.  doi: 10.1002/mrm.21391.  Google Scholar

[25] S. Mallat, A Wavelet Tour of Signal Processing, Elsevier/Academic Press, Amsterdam, 2009.  doi: 10.1016/B978-0-12-374370-1.X0001-8.  Google Scholar
[26] Y. Meyer, Wavelets and Operators, Cambridge Studies in Advanced Mathematics, 37, Cambridge University Press, Cambridge, 1992.   Google Scholar
[27]

N. Parikh and S. Boyd, Proximal Algorithms, Now Foundations and Trends, 2014,128pp. doi: 10.1561/9781601987174.  Google Scholar

[28]

Y. QuanH. Ji and Z. Shen, Data-driven multi-scale non-local wavelet frame construction and image recovery, J. Sci. Comput., 63 (2015), 307-329.  doi: 10.1007/s10915-014-9893-2.  Google Scholar

[29]

L. I. RudinS. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms, Phys. D, 60 (1992), 259-268.  doi: 10.1016/0167-2789(92)90242-F.  Google Scholar

[30]

S. F. D. Waldron, An Introduction to Finite Tight Frames, Applied and Numerical Harmonic Analysis, Birkhäuser/Springer, New York, 2018. doi: 10.1007/978-0-8176-4815-2.  Google Scholar

[31]

Y. WangJ. YangW. Yin and Y. Zhang, A new alternating minimization algorithm for total variation image reconstruction, SIAM J. Imaging Sci., 1 (2008), 248-272.  doi: 10.1137/080724265.  Google Scholar

[32]

Z. Xu and J. Sun, Image inpainting by patch propagation using patch sparsity, IEEE Trans. Image Process., 19 (2010), 1153-1165.  doi: 10.1109/TIP.2010.2042098.  Google Scholar

Figure 1.  An image to be inpainted
Figure 2.  Forming boundary equations
Figure 3.  Forming boundary equations: pick the best direction
Figure 4.  Recovery via directional sensing only. (a) Image with a thin missing domain. (b) 'DB-2', all smooth directions per pixel included, both centered and shifted equations used. (c) 'DB-2', all smooth directions per pixel included, only centered equations used. (d) 'DB-2', one direction per pixel included, only centered equations used could be formed as the filter has length 2. (e) 'DB-4', all smooth directions included, both centered and shifted equations used
Figures 6 and 9">Figure 5.  Examples of directional constraints adaptively formulated for the inpainting examples discussed further in the text. In both cases the 'DB2' filter of length 4 was used to form centered equations. Green dots indicate the unknown pixels around which the constraints were formed. Red dots indicate other pixels present in those constraints. The constraints are shown only for some pixels to avoid overcrowding the images. The actual results of inpainting appear later in Figures 6 and 9
Figure 9.  Text removal of Pepper, $ 128\times128 $
Figure 6.  Inpaint a missing block of a vertical stripe, $ 64\times64 $
Figure 7.  Inpainting a thin missing block in an image with repetitive pattern of slanted stripes, $ 64\times64 $
Figure 8.  Inpaint a missing annulus of a sectional image, $ 128\times128 $
Figure 10.  Smooth stripes inpainting, $ 64\times64 $
Figure 11.  Text removal of a colored image, $ 128\times128 $
Table 1.  Here $ \sqrt{\beta} = .75 $, $ F $ is the reshaped 2D DB-4 wavelet basis matrix, the first filter $ h $ is a high pass DB-2 filter, all smooth directions used and only centered equations included, the second filter added is a high pass DB-4 filter
Cosine Coherence $ \mu_1 $ Min singular value Max singular value
$ P_{\Lambda} F $ 0.8541 3.8339 0 1
$ SF $ (1 filter) 0.4799 0.5888 0.0455 1.5255
$ S_2F $ (2 filters) 0.3913 0.4480 0.0937 1.9837
Cosine Coherence $ \mu_1 $ Min singular value Max singular value
$ P_{\Lambda} F $ 0.8541 3.8339 0 1
$ SF $ (1 filter) 0.4799 0.5888 0.0455 1.5255
$ S_2F $ (2 filters) 0.3913 0.4480 0.0937 1.9837
Table 2.  Here $ \sqrt{\beta} = .75 $, $ F $ is the reshaped 2D binary Weyl basis matrix, the filter $ h $ is a high pass DB-2 filter, all smooth directions used and only centered equations included
Cosine Coherence $ \mu_1 $ Min singular value Max singular value
$ P_{\Lambda} F $ 0.0667 0.0667 0 1
$ SF $ (1 filter) 0.0452 0.0457 0.0455 1.5255
Cosine Coherence $ \mu_1 $ Min singular value Max singular value
$ P_{\Lambda} F $ 0.0667 0.0667 0 1
$ SF $ (1 filter) 0.0452 0.0457 0.0455 1.5255
[1]

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

[2]

Anton Schiela, Julian Ortiz. Second order directional shape derivatives of integrals on submanifolds. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021017

[3]

Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017

[4]

Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 327-345. doi: 10.3934/naco.2013.3.327

[5]

Murat Uzunca, Ayşe Sarıaydın-Filibelioǧlu. Adaptive discontinuous galerkin finite elements for advective Allen-Cahn equation. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 269-281. doi: 10.3934/naco.2020025

[6]

Rabiaa Ouahabi, Nasr-Eddine Hamri. Design of new scheme adaptive generalized hybrid projective synchronization for two different chaotic systems with uncertain parameters. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2361-2370. doi: 10.3934/dcdsb.2020182

[7]

Zheng Chang, Haoxun Chen, Farouk Yalaoui, Bo Dai. Adaptive large neighborhood search Algorithm for route planning of freight buses with pickup and delivery. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1771-1793. doi: 10.3934/jimo.2020045

 Impact Factor: 

Metrics

  • PDF downloads (53)
  • HTML views (154)
  • Cited by (0)

Other articles
by authors

[Back to Top]