
-
Previous Article
Network centralities, demographic disparities, and voluntary participation
- MFC Home
- This Issue
-
Next Article
Sketch-based image retrieval via CAT loss with elastic net regularization
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 |
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.
References:
[1] |
A. Aldroubi, X. 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. |
[2] |
C. Bao, H. 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. |
[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. |
[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. |
[5] |
M. Bertalmio, L. Vese, G. Sapiro and S. Osher,
Simultaneous structure and texture image inpainting, IEEE Trans. Image Processing, 12 (2003), 882-889.
doi: 10.1109/TIP.2003.815261. |
[6] |
A. Bertozzi, S. 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. |
[7] |
J.-F. Cai, R. 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. |
[8] |
J.-F. Cai, H. Ji, Z. 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. |
[9] |
J.-F. Cai, S. Osher and Z. Shen,
Split Bregman methods and frame based image restoration, Multiscale Model. Simul., 8 (2009/10), 337-369.
doi: 10.1137/090753504. |
[10] |
E. J. Candès, Y. C. Eldar, D. 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. |
[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. |
[12] |
E. J. Candès, J. 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. |
[13] |
P. G. Casazza,
The art of frame theory, Taiwanese J. Math., 4 (2000), 129-201.
doi: 10.11650/twjm/1500407227. |
[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. |
[15] |
A. Criminisi, P. 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. |
[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. |
[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. |
[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. |
[19] |
D. L. Donoho,
Compressed sensing, IEEE Trans. Inform. Theory, 52 (2006), 1289-1306.
doi: 10.1109/TIT.2006.871582. |
[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. |
[21] |
M. Elad, J.-L. Starck, P. 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. |
[22] |
B. Han, G. Kutyniok and Z. Shen,
Adaptive multiresolution analysis structures and shearlet systems, SIAM J. Numer. Anal., 49 (2011), 1921-1946.
doi: 10.1137/090780912. |
[23] |
E. J. King, G. 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. |
[24] |
M. Lustig, D. 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. |
[25] |
S. Mallat, A Wavelet Tour of Signal Processing, Elsevier/Academic Press, Amsterdam, 2009.
doi: 10.1016/B978-0-12-374370-1.X0001-8.![]() ![]() ![]() |
[26] |
Y. Meyer, Wavelets and Operators, Cambridge Studies in Advanced Mathematics, 37, Cambridge University Press, Cambridge, 1992.
![]() ![]() |
[27] |
N. Parikh and S. Boyd, Proximal Algorithms, Now Foundations and Trends, 2014,128pp.
doi: 10.1561/9781601987174. |
[28] |
Y. Quan, H. 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. |
[29] |
L. I. Rudin, S. 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. |
[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. |
[31] |
Y. Wang, J. Yang, W. 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. |
[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. |
show all references
References:
[1] |
A. Aldroubi, X. 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. |
[2] |
C. Bao, H. 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. |
[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. |
[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. |
[5] |
M. Bertalmio, L. Vese, G. Sapiro and S. Osher,
Simultaneous structure and texture image inpainting, IEEE Trans. Image Processing, 12 (2003), 882-889.
doi: 10.1109/TIP.2003.815261. |
[6] |
A. Bertozzi, S. 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. |
[7] |
J.-F. Cai, R. 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. |
[8] |
J.-F. Cai, H. Ji, Z. 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. |
[9] |
J.-F. Cai, S. Osher and Z. Shen,
Split Bregman methods and frame based image restoration, Multiscale Model. Simul., 8 (2009/10), 337-369.
doi: 10.1137/090753504. |
[10] |
E. J. Candès, Y. C. Eldar, D. 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. |
[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. |
[12] |
E. J. Candès, J. 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. |
[13] |
P. G. Casazza,
The art of frame theory, Taiwanese J. Math., 4 (2000), 129-201.
doi: 10.11650/twjm/1500407227. |
[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. |
[15] |
A. Criminisi, P. 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. |
[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. |
[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. |
[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. |
[19] |
D. L. Donoho,
Compressed sensing, IEEE Trans. Inform. Theory, 52 (2006), 1289-1306.
doi: 10.1109/TIT.2006.871582. |
[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. |
[21] |
M. Elad, J.-L. Starck, P. 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. |
[22] |
B. Han, G. Kutyniok and Z. Shen,
Adaptive multiresolution analysis structures and shearlet systems, SIAM J. Numer. Anal., 49 (2011), 1921-1946.
doi: 10.1137/090780912. |
[23] |
E. J. King, G. 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. |
[24] |
M. Lustig, D. 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. |
[25] |
S. Mallat, A Wavelet Tour of Signal Processing, Elsevier/Academic Press, Amsterdam, 2009.
doi: 10.1016/B978-0-12-374370-1.X0001-8.![]() ![]() ![]() |
[26] |
Y. Meyer, Wavelets and Operators, Cambridge Studies in Advanced Mathematics, 37, Cambridge University Press, Cambridge, 1992.
![]() ![]() |
[27] |
N. Parikh and S. Boyd, Proximal Algorithms, Now Foundations and Trends, 2014,128pp.
doi: 10.1561/9781601987174. |
[28] |
Y. Quan, H. 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. |
[29] |
L. I. Rudin, S. 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. |
[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. |
[31] |
Y. Wang, J. Yang, W. 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. |
[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. |











Cosine | Coherence |
Min singular value | Max singular value | |
0.8541 | 3.8339 | 0 | 1 | |
0.4799 | 0.5888 | 0.0455 | 1.5255 | |
0.3913 | 0.4480 | 0.0937 | 1.9837 |
Cosine | Coherence |
Min singular value | Max singular value | |
0.8541 | 3.8339 | 0 | 1 | |
0.4799 | 0.5888 | 0.0455 | 1.5255 | |
0.3913 | 0.4480 | 0.0937 | 1.9837 |
Cosine | Coherence |
Min singular value | Max singular value | |
0.0667 | 0.0667 | 0 | 1 | |
0.0452 | 0.0457 | 0.0455 | 1.5255 |
Cosine | Coherence |
Min singular value | Max singular value | |
0.0667 | 0.0667 | 0 | 1 | |
0.0452 | 0.0457 | 0.0455 | 1.5255 |
[1] |
Steven L. Brunton, Joshua L. Proctor, Jonathan H. Tu, J. Nathan Kutz. Compressed sensing and dynamic mode decomposition. Journal of Computational Dynamics, 2015, 2 (2) : 165-191. doi: 10.3934/jcd.2015002 |
[2] |
Ying Zhang, Ling Ma, Zheng-Hai Huang. On phaseless compressed sensing with partially known support. Journal of Industrial and Management Optimization, 2020, 16 (3) : 1519-1526. doi: 10.3934/jimo.2019014 |
[3] |
Zohre Aminifard, Saman Babaie-Kafaki. Diagonally scaled memoryless quasi–Newton methods with application to compressed sensing. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021191 |
[4] |
Yingying Li, Stanley Osher. Coordinate descent optimization for l1 minimization with application to compressed sensing; a greedy algorithm. Inverse Problems and Imaging, 2009, 3 (3) : 487-503. doi: 10.3934/ipi.2009.3.487 |
[5] |
Song Li, Junhong Lin. Compressed sensing with coherent tight frames via $l_q$-minimization for $0 < q \leq 1$. Inverse Problems and Imaging, 2014, 8 (3) : 761-777. doi: 10.3934/ipi.2014.8.761 |
[6] |
Zhihua Zhang, Naoki Saito. PHLST with adaptive tiling and its application to antarctic remote sensing image approximation. Inverse Problems and Imaging, 2014, 8 (1) : 321-337. doi: 10.3934/ipi.2014.8.321 |
[7] |
Lok Ming Lui, Chengfeng Wen, Xianfeng Gu. A conformal approach for surface inpainting. Inverse Problems and Imaging, 2013, 7 (3) : 863-884. doi: 10.3934/ipi.2013.7.863 |
[8] |
Jian-Feng Cai, Raymond H. Chan, Zuowei Shen. Simultaneous cartoon and texture inpainting. Inverse Problems and Imaging, 2010, 4 (3) : 379-395. doi: 10.3934/ipi.2010.4.379 |
[9] |
Xiaoqun Zhang, Tony F. Chan. Wavelet inpainting by nonlocal total variation. Inverse Problems and Imaging, 2010, 4 (1) : 191-210. doi: 10.3934/ipi.2010.4.191 |
[10] |
Evelyn Herberg, Michael Hinze, Henrik Schumacher. Maximal discrete sparsity in parabolic optimal control with measures. Mathematical Control and Related Fields, 2020, 10 (4) : 735-759. doi: 10.3934/mcrf.2020018 |
[11] |
Bruno Sixou, Valentina Davidoiu, Max Langer, Francoise Peyrin. Absorption and phase retrieval with Tikhonov and joint sparsity regularizations. Inverse Problems and Imaging, 2013, 7 (1) : 267-282. doi: 10.3934/ipi.2013.7.267 |
[12] |
Yangyang Xu, Wotao Yin, Stanley Osher. Learning circulant sensing kernels. Inverse Problems and Imaging, 2014, 8 (3) : 901-923. doi: 10.3934/ipi.2014.8.901 |
[13] |
Vikram Krishnamurthy, William Hoiles. Information diffusion in social sensing. Numerical Algebra, Control and Optimization, 2016, 6 (3) : 365-411. doi: 10.3934/naco.2016017 |
[14] |
Valentin Afraimovich, Maurice Courbage, Lev Glebsky. Directional complexity and entropy for lift mappings. Discrete and Continuous Dynamical Systems - B, 2015, 20 (10) : 3385-3401. doi: 10.3934/dcdsb.2015.20.3385 |
[15] |
Richard Miles, Thomas Ward. Directional uniformities, periodic points, and entropy. Discrete and Continuous Dynamical Systems - B, 2015, 20 (10) : 3525-3545. doi: 10.3934/dcdsb.2015.20.3525 |
[16] |
Riccardo March, Giuseppe Riey. Analysis of a variational model for motion compensated inpainting. Inverse Problems and Imaging, 2017, 11 (6) : 997-1025. doi: 10.3934/ipi.2017046 |
[17] |
Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems and Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017 |
[18] |
Ville Kolehmainen, Matthias J. Ehrhardt, Simon R. Arridge. Incorporating structural prior information and sparsity into EIT using parallel level sets. Inverse Problems and Imaging, 2019, 13 (2) : 285-307. doi: 10.3934/ipi.2019015 |
[19] |
Jian Lu, Lixin Shen, Chen Xu, Yuesheng Xu. Multiplicative noise removal with a sparsity-aware optimization model. Inverse Problems and Imaging, 2017, 11 (6) : 949-974. doi: 10.3934/ipi.2017044 |
[20] |
Rafael Monteiro. Horizontal patterns from finite speed directional quenching. Discrete and Continuous Dynamical Systems - B, 2018, 23 (8) : 3503-3534. doi: 10.3934/dcdsb.2018285 |
Impact Factor:
Tools
Metrics
Other articles
by authors
[Back to Top]