Article

Image completion with structure propagation

Authors:

Heung-Yeung ShumAuthors Info & Claims

SIGGRAPH '05: ACM SIGGRAPH 2005 Papers

Pages 861 - 868

https://doi.org/10.1145/1186822.1073274

Published: 01 July 2005 Publication History

Abstract

In this paper, we introduce a novel approach to image completion, which we call structure propagation. In our system, the user manually specifies important missing structure information by extending a few curves or line segments from the known to the unknown regions. Our approach synthesizes image patches along these user-specified curves in the unknown region using patches selected around the curves in the known region. Structure propagation is formulated as a global optimization problem by enforcing structure and consistency constraints. If only a single curve is specified, structure propagation is solved using Dynamic Programming. When multiple intersecting curves are specified, we adopt the Belief Propagation algorithm to find the optimal patches. After completing structure propagation, we fill in the remaining unknown regions using patch-based texture synthesis. We show that our approach works well on a number of examples that are challenging to state-of-the-art techniques.

References

[1]

Ashikhmin, M. 2001. Synthesizing natural textures. In ACM Symposium on Interactive 3D Graphics, 217--226.

Digital Library

[2]

Ballester, C., Bertalmio, M., Caselles, V., Sapiro, G., and Verdera, J. 2001. Filling in by joint interpolation of vector fields and gray levels. IEEE Trans. Image Processing 10, 8, 1200--1211.

Digital Library

[3]

Barret, A., and Cheney, A. 2002. Object-based image editing. In Proceedings of ACM SIGGRAPH 2002, 777--784.

Digital Library

[4]

Bellman, R. E. 1957. Dynamic Programming. Princeton University Press, Princeton, NJ.

Digital Library

[5]

Bertalmio, M., Sapiro, G., Ballester, C., and Caselles, V. 2000. Image inpainting. In Proceedings of ACM SIGGRAPH 2000, 417--424.

Digital Library

[6]

Bertalmio, M., Bertozzi, A., and Sapiro, G. 2001. Navier-stokes, fluid dynamics, and image and video inpainting. In Proc. Conf. Comp. Vision Pattern Rec., I.355--362.

[7]

Bertalmio, M., Vese, L., Sapiro, G., and Osher, S. 2003. Simultaneous structure and texture image inpainting. In Proc. Conf. Comp. Vision Pattern Rec., II.707--714.

[8]

Bornard, R., Lecan, E., Laborelli, L., and Chenot, J.-H. 2002. Missing data correction in still images and image sequences. In Proc. ACM Int. Conf. on Multimedia, 355--361.

Digital Library

[9]

Chan, T., and Shen, J. 2001. Non-texture inpaintings by curvature-driven diffusions. J. Visual Comm. Image Rep. 12, 4, 436--449.

Digital Library

[10]

Criminisi, A., Perez, P., and Toyama, K. 2003. Object removal by exemplar-based inpainting. In In Proc. Conf. Comp. Vision Pattern Rec., 417--424.

[11]

Drori, I., Cohen-Or, D., and Yeshurun, H. 2003. Fragment-based image completion. In Proceedings of ACM SIGGRAPH 2003, 303--312.

Digital Library

[12]

Efros, A., and Freeman, W. 2001. Image quilting for texture synthesis and transfer. In Proceedings of ACM SIGGRAPH 2001, 341--346.

Digital Library

[13]

Efros, A., and Leung, T. 1999. Texture synthesis by non-parametric sampling. In Proceedings of Inte. Conf. on Comp. Vision, 1033--1038.

Digital Library

[14]

Freeman, W., Pasztor, E., and Carmichael, O. 2000. Learning low-level vision. Int. J. Computer Vision 40, 1, 25--47.

Digital Library

[15]

Harrison, P. 2001. A non-hierarchical procedure for re-synthesis of complex textures. In Proc. Int. Conf. Central Europe Comp. Graphics, Visua. and Comp. Vision.

[16]

Hertzmann, A., Jacobs, C. E., Oliver, N., Curless, B., and Salesin, D. 2001. Image analogies. In Proceedings of ACM SIGGRAPH 2001, 327--340.

Digital Library

[17]

Igehy, H., and Pereira. L. 1997. Image replacement through texture synthesis. In Proc. of Inte. Conf. on Image Processing, 186--189.

Digital Library

[18]

Jia, J., and Tang, C. K. 2003. Image repairing: robust image synthesis by adaptive nd tensor voting. In Proc. Conf. Comp. Vision Pattern Rec., 1643--650.

Digital Library

[19]

Koffka, K. 1935, 1967. Principles of gestalt psychology. New York, Hartcourt, Brace and World.

[20]

Kwatra, V., Schödl, A., Essa, I., Turk, G., and Bobick, A. 2003. Graphcut textures: Image and video synthesis using graph cuts. In Proceedings of ACM SIGGRAPH 2003, 277--286.

Digital Library

[21]

Levin, A., Zomet, A., and Weiss, Y. 2003. Learning how to inpaint from global image statistics. In Proceedings of Inte. Conf. on Comp. Vision. II.305--313.

Digital Library

[22]

Liang, L., Liu, C., Xu, Y. Q., Guo, B., and Shum, H. 2001. Real-time texture synthesis by patch-based sampling. ACM Transactions on Graphics 20, 3, 127--150.

Digital Library

[23]

Noe, A., Pessoa, L., and Thompson, E. 1998. Finding out about filling-in: A guide to perceptual completion for visual science and the philosophy of perception. Behavioral and Brain Sciences 6, 723--748.

[24]

Pearl, J. 1988. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann Publishers, San Mateo, California.

Digital Library

[25]

Pérez, P., Gangnet, M., and Blake, A. 2003. Poisson image editing. In Proceedings of ACM SIGGRAPH 2003, 313--318.

Digital Library

[26]

Pérez, P., Gangnet, M., and Blake, A. 2004. Patchworks: example-based region tiling for image editing. Technical Report, Microsoft Research, MSR--TR-2004-04.

[27]

Sharf, A., Alexa, M., and Cohen-Or, D. 2004. Context-based surface completion. In Proceedings of ACM SIGGRAPH 2004, 878--887.

Digital Library

[28]

Sun, J., Shum, H. Y., and Zheng, N. N. 2002. Stereo matching using belief propagation. In Proceedings of European Conference on Computer Vision 2002, vol. II, 510--524.

Digital Library

[29]

Wei, L. W., and Levoy, M. 2000. Fast texture synthesis using tree-structured vector quantization. In Proceedings of ACM SIGGRAPH 2000, 479--488.

Digital Library

[30]

Weiss, Y., and Freeman, W. T. 2001. On the optimality of solutions of the max-product belief propagation algorithm in arbitrary graphs. IEEE Transactions on Information Theory. 47, 2, 723--735.

Digital Library

[31]

Wexler, Y., Shechtman, E., and Irani, M. 2004. Space-time video completion. In Proc. Conf. Comp. Vision Pattern Rec., I:120--127.

[32]

Yedidia, J. S., Freeman, W. T., and Weiss, Y. 2002. Understanding belief propagation and its generalizations. Technical Report, Mitsubishi Electric Research Laboratories, MERL-TR-2001-22.

Cited By

Wang YGuo DZhao HYang MZheng H(2025)Image inpainting via Multi-scale Adaptive PriorsPattern Recognition10.1016/j.patcog.2025.111410162(111410)Online publication date: Jun-2025
https://doi.org/10.1016/j.patcog.2025.111410
Qin YDing PPei CMao Y(2025)Structural self-attention GAN-based inpainting of high dynamic range fringe pattern for 3D measurement of metal gear teethMeasurement10.1016/j.measurement.2024.116630245(116630)Online publication date: Mar-2025
https://doi.org/10.1016/j.measurement.2024.116630
Hou YMa XZhang JGuo C(2024)Symmetric Connected U-Net with Multi-Head Self Attention (MHSA) and WGAN for Image InpaintingSymmetry10.3390/sym1611142316:11(1423)Online publication date: 25-Oct-2024
https://doi.org/10.3390/sym16111423
Show More Cited By

Index Terms

Image completion with structure propagation
1. Computing methodologies
  1. Artificial intelligence
    1. Computer vision
      1. Computer vision problems
        Reconstruction
  2. Computer graphics
    1. Image manipulation
2. Theory of computation
  1. Design and analysis of algorithms
    1. Algorithm design techniques
      1. Dynamic programming

Recommendations

Image completion with structure propagation

In this paper, we introduce a novel approach to image completion, which we call structure propagation. In our system, the user manually specifies important missing structure information by extending a few curves or line segments from the known to the ...
Structure-Aware Image Completion with Texture Propagation
ICIG '11: Proceedings of the 2011 Sixth International Conference on Image and Graphics

Structure-aware image completion has the reputation of keeping the salient structure of images, except for the case in texture propagation of images with distinguishing texture characteristics and large missing region. This inspirits us to design this ...
Image inpainting with salient structure completion and texture propagation

Image inpainting technique uses structural and textural information to repair or fill missing regions of a picture. Inspired by human visual characteristics, we introduce a new image inpainting approach which includes salient structure completion and ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGGRAPH '05: ACM SIGGRAPH 2005 Papers

July 2005

826 pages

ISBN:9781450378253

DOI:10.1145/1186822

Editor:
Markus Gross
Eidgenössische Technische Hochschule Zürich

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SIGGRAPH05

Sponsor:

SIGGRAPH

SIGGRAPH05: Special Interest Group on Computer Graphics and Interactive Techniques Conference

July 31 - August 4, 2005

California, Los Angeles

Acceptance Rates

SIGGRAPH '05 Paper Acceptance Rate 98 of 461 submissions, 21%;

Overall Acceptance Rate 1,822 of 8,601 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

156
Total Citations
View Citations
2,644
Total Downloads

Downloads (Last 12 months)76
Downloads (Last 6 weeks)9

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wang YGuo DZhao HYang MZheng H(2025)Image inpainting via Multi-scale Adaptive PriorsPattern Recognition10.1016/j.patcog.2025.111410162(111410)Online publication date: Jun-2025
https://doi.org/10.1016/j.patcog.2025.111410
Qin YDing PPei CMao Y(2025)Structural self-attention GAN-based inpainting of high dynamic range fringe pattern for 3D measurement of metal gear teethMeasurement10.1016/j.measurement.2024.116630245(116630)Online publication date: Mar-2025
https://doi.org/10.1016/j.measurement.2024.116630
Hou YMa XZhang JGuo C(2024)Symmetric Connected U-Net with Multi-Head Self Attention (MHSA) and WGAN for Image InpaintingSymmetry10.3390/sym1611142316:11(1423)Online publication date: 25-Oct-2024
https://doi.org/10.3390/sym16111423
Liu CXu SPeng JZhang KLiu D(2024)Toward Interactive Image Inpainting via Robust Sketch RefinementIEEE Transactions on Multimedia10.1109/TMM.2024.340262026(9973-9987)Online publication date: 2024
https://doi.org/10.1109/TMM.2024.3402620
Chen HZhao Y(2024)Don't Look into the Dark: Latent Codes for Pluralistic Image Inpainting2024 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)10.1109/CVPR52733.2024.00725(7591-7600)Online publication date: 16-Jun-2024
https://doi.org/10.1109/CVPR52733.2024.00725
Cao YMa RZhao KAn P(2024)WFIL-NET: image inpainting based on wavelet downsampling and frequency integrated learning moduleMultimedia Systems10.1007/s00530-024-01609-031:1Online publication date: 20-Dec-2024
https://doi.org/10.1007/s00530-024-01609-0
Luo WYang SZhang W(2023)Reference-Guided Large-Scale Face Inpainting With Identity and Texture ControlIEEE Transactions on Circuits and Systems for Video Technology10.1109/TCSVT.2023.325727133:10(5498-5509)Online publication date: Oct-2023
https://doi.org/10.1109/TCSVT.2023.3257271
Wang FWu KCao Y(2023)High resolution Mural images inpainting based on Dual Aggregation Generative Adversarial Network2023 International Conference on Image Processing, Computer Vision and Machine Learning (ICICML)10.1109/ICICML60161.2023.10424787(97-102)Online publication date: 3-Nov-2023
https://doi.org/10.1109/ICICML60161.2023.10424787
Kasturiwala S(2022)Image Retrieval Using Digital Image Inpainting TechniquesInternational Journal of Information Retrieval Research10.4018/IJIRR.29993712:2(1-17)Online publication date: 26-Aug-2022
https://dl.acm.org/doi/10.4018/IJIRR.299937
Shah RGautam ASingh S(2022)Overview of Image Inpainting Techniques: A Survey2022 IEEE Region 10 Symposium (TENSYMP)10.1109/TENSYMP54529.2022.9864513(1-6)Online publication date: 1-Jul-2022
https://doi.org/10.1109/TENSYMP54529.2022.9864513
Show More Cited By

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten