Scene completion using millions of photographs

ABSTRACT

What can you do with a million images? In this paper we present a new image completion algorithm powered by a huge database of photographs gathered from the Web. The algorithm patches up holes in images by finding similar image regions in the database that are not only seamless but also semantically valid. Our chief insight is that while the space of images is effectively infinite, the space of semantically differentiable scenes is actually not that large. For many image completion tasks we are able to find similar scenes which contain image fragments that will convincingly complete the image. Our algorithm is entirely data-driven, requiring no annotations or labelling by the user. Unlike existing image completion methods, our algorithm can generate a diverse set of results for each input image and we allow users to select among them. We demonstrate the superiority of our algorithm over existing image completion approaches.

REFERENCES

• 1: Aseem Agarwala , Mira Dontcheva , Maneesh Agrawala , Steven Drucker , Alex Colburn , Brian Curless , David Salesin , Michael Cohen, Interactive digital photomontage, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 2: Agrawal, A., Raskar, R., and Chellappa, R. 2006. What is the range of surface reconstructions from a gradient field? In ECCV.
• 3: Yuri Boykov , Olga Veksler , Ramin Zabih, Fast Approximate Energy Minimization via Graph Cuts, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.11, p.1222-1239, November 2001 [doi>10.1109/34.969114]
• 4: Criminisi, A., Perez, P., and Toyama, K. 2003. Object removal by exemplar-based inpainting. CVPR 02, 721.
• 5: Diakopoulos, N., Essa, I., and Jain, R. 2004. Content based image synthesis. In Conference on Image and Video Retrieval.
• 6: Iddo Drori , Daniel Cohen-Or , Hezy Yeshurun, Fragment-based image completion, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 7: Alexei A. Efros , William T. Freeman, Image quilting for texture synthesis and transfer, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.341-346, August 2001 [doi>10.1145/383259.383296]
• 8: Alexei A. Efros , Thomas K. Leung, Texture Synthesis by Non-Parametric Sampling, Proceedings of the International Conference on Computer Vision-Volume 2, p.1033, September 20-25, 1999
• 9: Irani, M., Anandan, P., and Hsu, S. 1995. Mosaic based representations of video sequences and their applications.
• 10: Jiaya Jia , Jian Sun , Chi-Keung Tang , Heung-Yeung Shum, Drag-and-drop pasting, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 11: Johnson, M., Brostow, G. J., Shotton, J., Arandjelović, O., Kwatra, V., and Cipolla, R. 2006. Semantic photo synthesis. Computer Graphics Forum (Proc. Eurographics) 25, 3 (September), 407--413.
• 12: King, D. 1997. The Commissar Vanishes. Henry Holt and Co.
• 13: Nikos Komodakis, Image Completion Using Global Optimization, Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, p.442-452, June 17-22, 2006 [doi>10.1109/CVPR.2006.141]
• 14: Vivek Kwatra , Arno Schödl , Irfan Essa , Greg Turk , Aaron Bobick, Graphcut textures: image and video synthesis using graph cuts, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 15: Vivek Kwatra , Irfan Essa , Aaron Bobick , Nipun Kwatra, Texture optimization for example-based synthesis, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 16: Oliva, A., and Torralba, A. 2006. Building the gist of a scene: The role of global image features in recognition. In Visual Perception, Progress in Brain Research, vol. 155.
• 17: Patrick Pérez , Michel Gangnet , Andrew Blake, Poisson image editing, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 18: Russell, B. C., Torralba, A., Murphy, K. P., and Freeman, W. T. 2005. LabelMe: a database and web-based tool for image annotation. Tech. rep., MIT, 2005.
• 19: Noah Snavely , Steven M. Seitz , Richard Szeliski, Photo tourism: exploring photo collections in 3D, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 20: Jian Sun , Lu Yuan , Jiaya Jia , Heung-Yeung Shum, Image completion with structure propagation, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 21: Antonio Torralba , Kevin P. Murphy , William T. Freeman , Mark A. Rubin, Context-based vision system for place and object recognition, Proceedings of the Ninth IEEE International Conference on Computer Vision, p.273, October 13-16, 2003
• 22: Torralba, A., Fergus, R., and Freeman, W. T. 2007. Tiny images. Tech. Rep. MIT-CSAIL-TR-2007-024.
• 23: Wertheimer, M. 1938. Laws of organization in perceptual forms (partial translation). In A sourcebook of Gestalt Psychology, W. Ellis, Ed. Harcourt Brace and Company, 71--88.
• 24: Wexler, Y., Shechtman, E., and Irani, M. 2004. Space-time video completion. CVPR 01, 120--127.
• 25: Wilczkowiak, M., Brostow, G. J., Tordoff, B., and Cipolla, R. 2005. Hole filling through photomontage. In BMVC, 492--501.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.8 Scene Analysis

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.8 Applications
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.7 Feature Measurement
          Subjects: Feature representation
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Pattern analysis

General Terms:
Algorithms, Design, Measurement

Keywords:
hole filling, image completion, image compositing, image database, inpainting