Skip to main content

Fast Hole-Filling in Images Via Fast Comparison of Incomplete Patches

  • Conference paper
Multimedia Content Representation, Classification and Security (MRCS 2006)

Part of the book series: Lecture Notes in Computer Science ((LNISA,volume 4105))

  • 1091 Accesses

Abstract

We present an algorithm for fast filling of missing regions (holes) in images. Holes may be the result of various causes: manual manipulation e.g. removal of an object from an image, errors in the transmission of an image or video, etc. The hole is filled one pixel at a time by comparing the neighborhood of each pixel to other areas in the image. Similar areas are used as clues for choosing the color of the pixel. The neighborhood and the areas that are compared are square shaped. This symmetric shape allows the hole to be filled in an evenly fashion. However, since square areas inside the hole include some uncolored pixels, we introduce a fast and efficient data structure which allows fast comparison of areas, even with partially missing data. The speed is achieved by using a two phase algorithm: a learning phase which can be done offline and a fast synthesis phase. The data structure uses the fact that colors in an image can be represented by a bounded natural number. The algorithm fills the hole from the boundaries inward, in a spiral form to produce a smooth and coherent result.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Bertalmio, M., Sapiro, G., Caselles, V., Ballester, C.: Image inpainting. In: Proceedings of ACM SIGGRAPH, pp. 417–424. ACM Press, New York (2000)

    Google Scholar 

  2. Bertalmio, M., Vese, L., Sapiro, G., Osher, S.: Simultaneous structure and texture imag inpainting. UCLA CAM Report 02(47) (2002)

    Google Scholar 

  3. Chan, T., Shen, J.: Mathematical models for local nontexture inpaintings. SIAM Journal of Applied Mathematics 62(3), 1019–1043 (2001)

    MathSciNet  Google Scholar 

  4. Efros, A.A., Leung, T.: Texture synthesis by non-parametric sampling. In: IEEE International Conference on Computer Vision, pp. 1033–1038 (1999)

    Google Scholar 

  5. Heeger, D.J., Bergen, J.R.: Pyramid-based texture analysis/synthesis. In: Proceedings of ACM SIGGRAPH, pp. 229–238 (1995)

    Google Scholar 

  6. Igehy, H., Pereira, L.: Image replacement through texture synthesis. In: Proceedings of the 1997 International Conference on Image Processing, vol. 3, p. 186 (1997)

    Google Scholar 

  7. Wei, L.Y., Levoy, M.: Fast texture synthesis using tree-structured vector quantization. In: Proceedings of ACM SIGGRAPH, pp. 479–488. ACM Press, New York (2000)

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Editors and Affiliations

Rights and permissions

Reprints and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Averbuch, A., Gelles, G., Schclar, A. (2006). Fast Hole-Filling in Images Via Fast Comparison of Incomplete Patches. In: Gunsel, B., Jain, A.K., Tekalp, A.M., Sankur, B. (eds) Multimedia Content Representation, Classification and Security. MRCS 2006. Lecture Notes in Computer Science, vol 4105. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11848035_97

Download citation

  • DOI: https://doi.org/10.1007/11848035_97

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-39392-4

  • Online ISBN: 978-3-540-39393-1

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics