# American Institute of Mathematical Sciences

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 Early access  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:

show all references

##### References:
An image to be inpainted
Forming boundary equations
Forming boundary equations: pick the best direction
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
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
Text removal of Pepper, $128\times128$
Inpaint a missing block of a vertical stripe, $64\times64$
Inpainting a thin missing block in an image with repetitive pattern of slanted stripes, $64\times64$
Inpaint a missing annulus of a sectional image, $128\times128$
Smooth stripes inpainting, $64\times64$
Text removal of a colored image, $128\times128$
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
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] 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & Imaging, 2010, 4 (1) : 191-210. doi: 10.3934/ipi.2010.4.191 [10] Yangyang Xu, Wotao Yin, Stanley Osher. Learning circulant sensing kernels. Inverse Problems & Imaging, 2014, 8 (3) : 901-923. doi: 10.3934/ipi.2014.8.901 [11] Vikram Krishnamurthy, William Hoiles. Information diffusion in social sensing. Numerical Algebra, Control & Optimization, 2016, 6 (3) : 365-411. doi: 10.3934/naco.2016017 [12] Evelyn Herberg, Michael Hinze, Henrik Schumacher. Maximal discrete sparsity in parabolic optimal control with measures. Mathematical Control & Related Fields, 2020, 10 (4) : 735-759. doi: 10.3934/mcrf.2020018 [13] Bruno Sixou, Valentina Davidoiu, Max Langer, Francoise Peyrin. Absorption and phase retrieval with Tikhonov and joint sparsity regularizations. Inverse Problems & Imaging, 2013, 7 (1) : 267-282. doi: 10.3934/ipi.2013.7.267 [14] Valentin Afraimovich, Maurice Courbage, Lev Glebsky. Directional complexity and entropy for lift mappings. Discrete & 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 & 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 & 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 & 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 & 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 & Imaging, 2017, 11 (6) : 949-974. doi: 10.3934/ipi.2017044 [20] Rafael Monteiro. Horizontal patterns from finite speed directional quenching. Discrete & Continuous Dynamical Systems - B, 2018, 23 (8) : 3503-3534. doi: 10.3934/dcdsb.2018285

Impact Factor:

## Tools

Article outline

Figures and Tables