research-article

Image inpainting by patch propagation using patch sparsity

Authors:

Jian SunAuthors Info & Claims

IEEE Transactions on Image Processing, Volume 19, Issue 5

Pages 1153 - 1165

https://doi.org/10.1109/TIP.2010.2042098

Published: 01 May 2010 Publication History

Abstract

This paper introduces a novel examplar-based inpainting algorithm through investigating the sparsity of natural image patches. Two novel concepts of sparsity at the patch level are proposed for modeling the patch priority and patch representation, which are two crucial steps for patch propagation in the examplar-based inpainting approach. First, patch structure sparsity is designed to measure the confidence of a patch located at the image structure (e.g., the edge or corner) by the sparseness of its nonzero similarities to the neighboring patches. The patch with larger structure sparsity will be assigned higher priority for further inpainting. Second, it is assumed that the patch to be filled can be represented by the sparse linear combination of candidate patches under the local patch consistency constraint in a framework of sparse representation. Compared with the traditional examplar-based inpainting approach, structure sparsity enables better discrimination of structure and texture, and the patch sparse representation forces the newly inpainted regions to be sharp and consistent with the surrounding textures. Experiments on synthetic and natural images show the advantages of the proposed approach.

References

[1]

M. Bertalrnio, G. Sapiro, V. Caselles, and C. Ballester, "Image inpainting," in Proc. SIGGRAPH, 2000, pp. 417-424.

[2]

M. Bertalrnio, A. L. Bertozzi, and G. Sapiro, "Navier-Strokes, fluid dynamics, and image and video inpainting," in Proc. IEEE Computer Society Conf. Computer Vision and Pattern Recogaition, 2001, pp. 417-424.

[3]

T. Chan and J. Shen, "Local inpainting models and tv inpainting," SIAM J. Appl. Math., vol. 62, no. 3, pp. 1019-1043, 2001.

[4]

T. Chan and J. Shen, "Non-texture inpainting by curvature-driven diffusions," J. Vis. Commun. Image Represent., vol. 4, no. 12, pp. 436-449, 2001.

Digital Library

[5]

C. Bertalmio, M. Bertalmio, V. Caselles, G. Sapirc, and J. Verdera, "Filling-in by joint interpolation of vector fields and gray levels," IEEE Trans. Image Process., vol. 10, pp. 1200-1211, 2001.

Digital Library

[6]

A. Levin, A. Zomet, and Y. Weiss, "Learning how to inpaint from global image statistics," in Proc. Int. Conf. Compo Vision, pp. 305-313.

[7]

S. Roth and M. J. Black, "Fields of experts: A framework for learning image priors," in Proc. IEEE Computer Society Conf. Computer Vision and Pattern Recognition, 2005, pp. 860-867.

Digital Library

[8]

S. Roth and M. J. Black, "Steerable random fields," in Proc. IEEE Computer Society Conf. Computer Vision and Pattern Recognition, 2007, pp. 1-8.

[9]

A. Efros and T. Leung, "Texture synthesis by non-parametric sampling," in Proc. Int. Conf. Comp. Vision, 1999, pp. 1033-1038.

[10]

M. Bertalmio, L. Vese, G. Sapiro, and S. Osher, "Simultaneous structure and texture image inpainting," IEEE Trans. Image Process., vol. 12, pp. 882-889, 2003.

Digital Library

[11]

A. Criminisi, P. Perez, and K. Toyama, "Object removal by examplarbased image inpainting," in Proc. Int. Conf. Comp. Vision, 2003, pp. 721-728.

[12]

J. Wu and Q. Ruan, "Object removal by cross isophotes examplar-based image inpainting," in Proc. Int. Conf. Pattern Recognition, 2006, pp. 810-813.

[13]

A. Wong and J. Orchard, "A nonlocal-means appwach to examplarbased inpainting," presented at the IEEE Int. Conf. Image Processing, 2008.

[14]

G. T. N. Komodakis, "Image completion using efficient belief propagation via priority scheduling and dynamic pruning," IEEE Trans. Image Process., vol. 16, pp. 2649-2661, 2007.

Digital Library

[15]

J. Jia and C. K. Tang, "Image repairing: Robust image synthesis by adaptive nd tensor voting," in Proc. IEEE Compllter Society Conf. Computer Vision and Pattern Recogition, 2003, pp. 643-650.

[16]

I. Drori, D. Cohen-Or, and H. Yeshurun, "Fragment-based image completion," ACM Trans. Graph., vol. 22, no. 2003, pp. 303-312, 2005.

[17]

M. Elad. J. L. Starck. P. Querre, and D. L. Donoho, "Simultaneous cartoon and texture image inpainting using morphological component analysis," Appl. Comput. Harmon. Anal., vol. 19, pp. 340-358, 2005.

[18]

O. G. Guleryuz, "Nonlinear approximation based image recovery using adaptive sparse reconstructions," presented at the IEEE Int. Conf. Image Processing, 2003.

[19]

O. G. Guleryuz, "Nonlinear approximation based image recovery using adaptive sparse reconstructures and iterated denoising-part i: Theory," IEEE Trans. Image Process., vol. 15, pp. 539-554, 2006.

Digital Library

[20]

O. G. Guleryuz, "Nonlinear approximation based image recovery using adaptive sparse reconstructures and iterated denoising-part ii: Adaptive algorithms," IEEE Trans. Image Process., vol. 15, pp. 555-571, 2006.

Digital Library

[21]

M. J. Fadili, J. L. Starck, and F. Murtagh, "Inpainting and zooming using sparse representations," The Comput. J., vol. 52, no. 1, pp. 64-79, 2009.

Digital Library

[22]

A. Crimi nisi, P. Perez, and K. Toyama, "Region filling and object removal by examplar-based image inpainting," IEEE Trans. Image Process., vol. 13, pp. 1200-1212, 2004.

Digital Library

[23]

Y. P. Li and D. Huttenlocher, "Sparse long-range random field and its application to image denoising," presented at the European Conf. Computer Vision, 2008.

[24]

M. F. Tappen, B. C. Russell, and W. T. Freeman, "Exploiting the sparse derivative prior for super-resolution and image demosaicing," presented at the IEEE Workshop on Statistical and Computational Theories of Vision, 2003.

[25]

J. Sun, J. Sun, Z. B. Xu, and H.-Y. Shum, "Image super-resolution using gradient profile prior," presented at the IEEE Computer Society Conf. Computer Vision and Pattern Recogition, 2008.

[26]

R. Fergus, B. Singh, A. Hertzmann, S. T. Roweis, and W. T. Freeman, "Removing camera shake from a single photograph," ACM Trans. Graph., vol. 25, no. 3, pp. 787-794, 2006.

Digital Library

[27]

A. Levin, R. Fergus, F. Durand, and W. T. Freeman, "Image and depth from a conventional camera and depth from a conventional camera with a coded aperture," ACM Trans. Graph., vol. 26, no. 3, pp. 70:1-70:9, 2007.

Digital Library

[28]

B. Olshausen and D. Field, "Sparse coding with an overcomplete basis set: A strategy employed by v1?," Vis. Res., vol. 37, no. 33, pp. 3311-3325, 1997.

[29]

M. Elad and M. Aharon, "Image denoising via sparse and redundant representations over learned dictionaries," IEEE Trans. Image Process., vol. 15, pp. 3736-3745, 2006.

Digital Library

[30]

J. Maire, M. Elad, and G. Sapiro, "Sparse representation for color image restoration," IEEE Trans. Image Process., vol. 17, pp. 53-69, 2008.

Digital Library

[31]

J. Mairal, M. Leordeanu, F. Bach, M. Hebert, and J. Ponce, "Discriminative sparse image models for class-specific edge detextion and image interpretation," presented at the IEEE Computer Society Conf. Computer Vision and Pattern Recogition, 2008.

[32]

J. Mairal, F. Bach, J. Ponce, G. Sapiro, and A. Zisserman, "Discriminative learned dictionary for local image analysis," presented at the European Conf. Computer Vision, 2008.

[33]

J. Winn, A. Criminisi, and N. Cristianini, "Object categorization by learned universal visual dictionary," presented at the Int. Conf. Compo Vision, 2005.

[34]

J. C. Yang, J. Wright, T. Huang, and Y. Ma, "Image super-resolution as sparse representation of raw image patches," presented at the IEEE Computer Society Conf. Computer Vision and Pattern Recogition, 2008.

[35]

G. Peyre, "Non-negative sparse modeling of textures," presented at the Scale Space and Variational Methods in Computer Vision, 2007.

[36]

H. Chang, D. Y. Yeung, and Y. Xiong, "Super-resolution through neighbor embedding," presented at the IEEE Computer Society Conf. Computer Vision and Pattern Recognition, 2004.

[37]

S. T. Roweis and L. K. Saul, "Nonlinear dimensionality reduction by locally linear embedding," Science, vol. 290, pp. 2323-2326, 2000.

[38]

S. Mallat and Z. Zhang, "Matching pursuit in a time-frequency dictionary," IEEE Trans. Signal Process., vol. 41, pp. 3397-3415, 1993.

Digital Library

[39]

Y. C. Pati, R. Rezaiifar, and P. S. Krishnaprasad, "Non-negative sparse modeling of textures," presented at the Scale Space and Variational Methods in Computer Vision, 2007.

[40]

S. S. Chen, D. L. Donoho, and M. A. Saunders, "Atomic decomposition by basis pursuit," SIAM Rev., vol. 43, no. 1, pp. 129-159, 2001.

Digital Library

[41]

R. Tibshirani, "Regression shrinkge and selection via the lasso," J. Roy. Statist. Soc. B., vol. 58, no. 1, pp. 267-288, 1996.

[42]

R. F. i Ventura, P. Vandergheynst, P. Frossard, and A. Cavallaro, "Color image scalable coding with matching pursuit," IEEE Acoust. Speech, Signal Process., 2004.

[43]

R. Gribonval, C. Fvotte, and E. Vincent, "Performance measurement in blind audio source separation," IEEE Trans. Speech, Audio, Lang. Process., vol. 14, no. 4, pp. 1462-1469, 2006.

Digital Library

[44]

B. Shen, W. Hu, Y. Zhang, and Y. Zhang, "Image inpainting via sparse representation," in Proc. IEEE Int. Conf. Acoustics, Speech and Signal Processing, 2009, pp. 697-700.

Digital Library

[45]

J. Sun, Y. Lu, J. Jia, and H.-Y. Shum, "Image completion with structure propagation," in Proc. ACM SIGGRAPH, 2005, pp. 861-868.

Digital Library

[46]

J. L. Starck, M. Elad, and D. L. Donoho, "Image decomposition via the combination of sparse representations and a variational approach," IEEE Trans. Image Process., vol. 14, pp. 1570-1582, 2005.

Digital Library

Cited By

Ma XZhou XHuang HJia GWang YChen XChen C(2024)Uncertainty-aware image inpainting with adaptive feedback network▪Expert Systems with Applications: An International Journal10.1016/j.eswa.2023.121148235:COnline publication date: 10-Jan-2024
https://dl.acm.org/doi/10.1016/j.eswa.2023.121148
Man QGee SCho Y(2024)High-Quality Facial Feature Occlusion Repair Based on S-GANsComputer Information Systems and Industrial Management10.1007/978-3-031-71115-2_18(261-271)Online publication date: 27-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-71115-2_18
Deng YHui SZhou SHuang WWang J(2023)Context Adaptive Network for Image InpaintingIEEE Transactions on Image Processing10.1109/TIP.2023.329856032(6332-6345)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1109/TIP.2023.3298560
Show More Cited By

Recommendations

Color-Direction Patch-Sparsity-Based Image Inpainting Using Multidirection Features
This paper proposes a color-direction patch-sparsity-based image inpainting method to better maintain structure coherence, texture clarity, and neighborhood consistence of the inpainted region of an image. The method uses super-wavelet transform to ...
Structure-aware image inpainting using patch scale optimization

Local structure multiplier in the priority function ensures the structure continuity.Color and space distance take into consideration in path searching process.Find the patch with optimized scale between under each candidate scale. Image inpainting is ...
A color-gradient patch sparsity based image inpainting algorithm with structure coherence and neighborhood consistency

To better maintain structure coherence and neighborhood consistency, an exemplar-based inpainting algorithm is presented by introducing color-gradient patch sparsity (CGPS). Two concepts of CGPS including color-gradient structure sparsity (CGSS) and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Image Processing

IEEE Transactions on Image Processing Volume 19, Issue 5

May 2010

271 pages

ISSN:1057-7149

Issue’s Table of Contents

Copyright © 2010.

Publisher

IEEE Press

Publication History

Published: 01 May 2010

Accepted: 20 December 2009

Revised: 20 December 2009

Received: 15 April 2009

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

88
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 23 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ma XZhou XHuang HJia GWang YChen XChen C(2024)Uncertainty-aware image inpainting with adaptive feedback network▪Expert Systems with Applications: An International Journal10.1016/j.eswa.2023.121148235:COnline publication date: 10-Jan-2024
https://dl.acm.org/doi/10.1016/j.eswa.2023.121148
Man QGee SCho Y(2024)High-Quality Facial Feature Occlusion Repair Based on S-GANsComputer Information Systems and Industrial Management10.1007/978-3-031-71115-2_18(261-271)Online publication date: 27-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-71115-2_18
Deng YHui SZhou SHuang WWang J(2023)Context Adaptive Network for Image InpaintingIEEE Transactions on Image Processing10.1109/TIP.2023.329856032(6332-6345)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1109/TIP.2023.3298560
Shao XYe HYang BCao F(2023)Two-stream coupling network with bidirectional interaction between structure and texture for image inpaintingExpert Systems with Applications: An International Journal10.1016/j.eswa.2023.120700231:COnline publication date: 30-Nov-2023
https://dl.acm.org/doi/10.1016/j.eswa.2023.120700
Xiao FZhang ZYao Y(2023)CTNet: hybrid architecture based on CNN and transformer for image inpainting detectionMultimedia Systems10.1007/s00530-023-01184-w29:6(3819-3832)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1007/s00530-023-01184-w
Ji BHe GChen ZZhao L(2023)A Novel Diffusion-Model-Based OCT Image Inpainting Algorithm for Wide Saturation ArtifactsPattern Recognition and Computer Vision10.1007/978-981-99-8558-6_24(284-295)Online publication date: 13-Oct-2023
https://dl.acm.org/doi/10.1007/978-981-99-8558-6_24
Patil B(2022)Effect of Optimized Deep Belief Network to Patch-Based Image Inpainting ForensicsInternational Journal of Swarm Intelligence Research10.4018/IJSIR.30440113:3(1-21)Online publication date: 22-Jul-2022
https://dl.acm.org/doi/10.4018/IJSIR.304401
Deng YHui SZhou SMeng DWang JMagalhães Jdel Bimbo ASatoh SSebe NAlameda-Pineda XJin QOria VToni L(2022)T-former: An Efficient Transformer for Image InpaintingProceedings of the 30th ACM International Conference on Multimedia10.1145/3503161.3548446(6559-6568)Online publication date: 10-Oct-2022
https://dl.acm.org/doi/10.1145/3503161.3548446
Navasardyan SOhanyan M(2022)The Family of Onion Convolutions for Image InpaintingInternational Journal of Computer Vision10.1007/s11263-022-01679-5130:12(3070-3099)Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.1007/s11263-022-01679-5
Liu XHao CSu ZQi ZFu SLi YHan H(2022)Image inpainting algorithm based on tensor decomposition and weighted nuclear normMultimedia Tools and Applications10.1007/s11042-022-12635-382:3(3433-3458)Online publication date: 5-Jul-2022
https://dl.acm.org/doi/10.1007/s11042-022-12635-3
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents