“Fragment-based image completion” by Drori, Cohen-Or and Yeshurun

  • ©Iddo Drori, Daniel Cohen-Or, and Hezy Yeshurun




    Fragment-based image completion



    We present a new method for completing missing parts caused by the removal of foreground or background elements from an image. Our goal is to synthesize a complete, visually plausible and coherent image. The visible parts of the image serve as a training set to infer the unknown parts. Our method iteratively approximates the unknown regions and composites adaptive image fragments into the image. Values of an inverse matte are used to compute a confidence map and a level set that direct an incremental traversal within the unknown area from high to low confidence. In each step, guided by a fast smooth approximation, an image fragment is selected from the most similar and frequent examples. As the selected fragments are composited, their likelihood increases along with the mean confidence of the image, until reaching a complete image. We demonstrate our method by completion of photographs and paintings.


    1. ASHIKHMIN, M. 2001. Synthesizing natural textures. In ACM Symposium on Interactive 3D Graphics, 217–226. Google Scholar
    2. BAKER, S., AND KANADE, T. 2000. Limits on super-resolution and how to break them. In IEEE Conference on Computer Vision and Pattern Recognition, 372–379.Google ScholarCross Ref
    3. BERTALMIO, M., SAPIRO, G., CASELLES, V., AND BALLESTER, C. 2000. Image inpainting. In Proceedings of ACM SIGGRAPH 2000, ACM Press, 417–424. Google ScholarDigital Library
    4. BERTALMIO, M., VESE, L., SAPIRO, G., AND OSHER, S. 2003. Simultaneous structure and texture image inpainting. In IEEE Conference on Computer Vision and Pattern Recognition, to appear.Google Scholar
    5. BORENSTEIN, E., AND ULLMAN, S. 2002. Class-specific, top-down segmentation. In European Conference on Computer Vision, 109–124. Google Scholar
    6. BROOKS, S., AND DODGSON, N. 2002. Self-similarity based texture editing. ACM Transactions on Graphics, 21, 3, 653–656. Google ScholarDigital Library
    7. BURT, P. J., AND ADELSON, E. H. 1985. Merging images through pattern decomposition. Applications of Digital Image Processing VIII 575, 173–181.Google Scholar
    8. CHAN, T., AND SHEN, J. 2001. Mathematical models for local nontexture inpainting. SIAM Journal on Applied Mathematics 62, 3, 1019–1043.Google Scholar
    9. CHUANG, Y.-Y., AGARWALA, A., CURLESS, B., SALESIN, D. H., AND SZELISKI, R. 2002. Video matting of complex scenes. ACM Transactions on Graphics, 21, 3, 243–248. Google ScholarDigital Library
    10. EFROS, A. A., AND FREEMAN, W. T. 2001. Image quilting for texture synthesis and transfer. In Proceedings of ACM SIGGRAPH 2001, ACM Press, 341–346. Google ScholarDigital Library
    11. EFROS, A., AND LEUNG, T. 1999. Texture synthesis by non-parametric sampling. In IEEE International Conference on Computer Vision, 1033–1038. Google Scholar
    12. FREEMAN, W. T., PASZTOR, E. C., AND CARMICHAEL, O. T. 2000. Learning low-level vision. International Journal of Computer Vision 40, 1, 25–47. Google ScholarCross Ref
    13. FREEMAN, W. T., JONES, T. R., AND PASZTOR, E. 2002. Example-based super-resolution. IEEE Computer Graphics and Applications, 56–65. Google Scholar
    14. GONZALEZ, R. C., AND WOODS, R. E. 2002. Digital Image Processing. Prentice Hall. Google Scholar
    15. GORTLER, S. J., GRZESZCZUK, R., SZELISKI, R., AND COHEN, M. F. 1996. The lumigraph. In Proceedings of ACM SIGGRAPH 96, ACM Press, 43–54. Google Scholar
    16. GUY, G., AND MEDIONI, G. 1996. Inferring global perceptual contours from local features. IEEE International Journal of Computer Vision, 1–2, 113–133. Google Scholar
    17. HAEBERLI, P. 1990. Paint by numbers: Abstract image representations. In Computer Graphics (Proceedings of ACM SIGGRAPH 90), ACM Press, 207–214. Google Scholar
    18. HEEGER, D. J., AND BERGEN, J. R. 1995. Pyramid-based texture analysis/synthesis. In Proceedings of ACM SIGGRAPH 95, ACM Press, 229–238. Google Scholar
    19. HERTZMANN, A., JACOBS, C. E., OLIVER, N., CURLESS, B., AND SALESIN, D. H. 2001. Image analogies. In Proceedings of ACM SIGGRAPH 2001, ACM Press, 327–340. Google ScholarDigital Library
    20. HIRANI, A. N., AND TOTSUKA, T. 1996. Combining frequency and spatial domain information for fast interactive image noise removal. In Proceedings of ACM SIGGRAPH 96, ACM Press, 269–276. Google Scholar
    21. IGEHY, H., AND PEREIRA, L. 1997. Image replacement through texture synthesis. In IEEE International conference on Image Processing, vol. 3, 186–189. Google Scholar
    22. KOFFKA, K. 1935, 1967. Principles of Gestalt Psychology. New York, Hartcourt, Brace and World.Google Scholar
    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, 796–802.Google Scholar
    24. OH, B. M., CHEN, M., DORSEY, J., AND DURAND, F. 2001. Image-based modeling and photo editing. In Proceedings of ACM SIGGRAPH 2001, ACM Press, 433–442. Google ScholarDigital Library
    25. PALMER, S. 1999. Vision Science. MIT Press.Google Scholar
    26. PORTER, T., AND DUFF, T. 1984. Compositing digital images. In Computer Graphics (Proceedings of ACM SIGGRAPH 84), 253–259. Google Scholar
    27. SHARON, E., BRANDT, A., AND BASRI, R. 2000. Completion energies and scale. IEEE Transactions on Pattern Analysis and Machine Intelligence 22, 10, 1117–1131. Google ScholarDigital Library
    28. SOLER, C., CANI, M.-P., AND ANGELIDIS, A. 2002. Hierarchical pattern mapping. ACM Transactions on Graphics, 21, 3, 673–680. Google ScholarDigital Library
    29. WEI, L. Y., AND LEVOY, M. 2000. Fast texture synthesis using tree-structured vector quantization. In Proceedings of ACM SIGGRAPH 2000, ACM Press, 479–488. Google ScholarDigital Library
    30. WELSH, T., ASHIKHMIN, M., AND MUELLER, K. 2002. Transferring color to greyscale images. ACM Transactions on Graphics, 21, 3, 277–280. Google ScholarDigital Library
    31. WILLIAMS, L., AND JACOBS, D. W. 1997. Stochastic completion fields: A neural model of illusory contour shape and salience. Neural Computation 9, 4, 837–858. Google ScholarDigital Library

ACM Digital Library Publication:

Overview Page: