Seam carving for content-aware image resizing

ABSTRACT

Effective resizing of images should not only use geometric constraints, but consider the image content as well. We present a simple image operator called seam carving that supports content-aware image resizing for both reduction and expansion. A seam is an optimal 8-connected path of pixels on a single image from top to bottom, or left to right, where optimality is defined by an image energy function. By repeatedly carving out or inserting seams in one direction we can change the aspect ratio of an image. By applying these operators in both directions we can retarget the image to a new size. The selection and order of seams protect the content of the image, as defined by the energy function. Seam carving can also be used for image content enhancement and object removal. We support various visual saliency measures for defining the energy of an image, and can also include user input to guide the process. By storing the order of seams in an image we create multi-size images, that are able to continuously change in real time to fit a given size.

REFERENCES

• 1: Agarwala, A., Dontcheva, M., Agrawala, M., Drucker, S., Colburn, A., Curless, B., Salesin, D., and Cohen, M. 2004. Interactive digital photomontage. ACM Trans. Graph. 23, 3, 294--302.
• 2: Bertalmio, M., Sapiro, G., Caselles, V., and Ballester, C. 2000. Image inpainting. In Proceedings of ACM SIGGRAPH, 417--424.
• 3: Bertalmio, M., Vese, L., Sapiro, G., and Osher, S. 2003. Simultaneous structure and texture image inpainting. In Proc. IEEE Conference on Computer Vision and Pattern Recognition, 707--714.
• 4: Boykov, Y., and Jolly, M.-P. 2001. Interactive graph cuts for optimal boundary & region segmentation of objects in n-d images. In International Conference on Computer Vision, (ICCV), vol. I, 105--112.
• 5: Chen, L., Xie, X., Fan, X., Ma, W., Zhang, H., and Zhou, H. 2003. A visual attention model for adapting images on small displays. Multimedia Systems 9, 4, 353--364.
• 6: Christoudias, C., Georgescu, B., and Meer, P. 2002. Synergism in low-level vision. In 16th International Conference on Pattern Recognition, vol. IV, 150--155.
• 7: Criminisi, A., Perez, P., and Toyama, K. 2003. Object removal by exemplar-based inpainting. In In IEEE Conference on Computer Vision and Pattern Recognition, 417--424.
• 8: Dalal, N., and Triggs, B. 2005. Histograms of oriented gradients for human detection. In International Conference on Computer Vision & Pattern Recognition, vol. 2, 886--893.
• 9: Davis, J. 1998. Mosaics of scenes with moving objects. In Proceedings of CVPR.
• 10: DeCarlo, D., and Santella, A. 2002. Stylization and abstraction of photographs. In Proceedings of SIGGRAPH, 769--776.
• 11: Drori, I., Cohen-Or, D., and Yeshurun, Y. 2003. Fragment-based image completion. In Proceedings of ACM SIGGRAPH, 303--312.
• 12: Efros, A. A., and Freeman, W. T. 2001. Image quilting for texture synthesis and transfer. In SIGGRAPH 2001, Computer Graphics Proceedings, ACM Press / ACM SIGGRAPH, E. Fiume, Ed., 341--346.
• 13: Gal, R., Sorkine, O., and Cohen-Or, D. 2006. Feature-aware texturing. In Eurographics Symposium on Rendering.
• 14: Harris, C., and Stephens, M. 1988. A combined corner and edge detector. In Proceedings of the 4th Alvey Vision Conference, 147--151.
• 15: Itti, L., Koch, C., and Neibur, E. 1999. A model of saliency-based visual attention for rapid scene analysis. PAMI 20, 11, 1254--1259.
• 16: Jacobs, C., Li, W., Schrier, E., Bargeron, D., and Salesin, D. 2003. Adaptive grid-based document layout. In Proceedings of ACM SIGGRAPH, 838--847.
• 17: Jia, J., Sun, J., Tang, C.-K., and Shum, H.-Y., 2006. Drag-and-drop pasting. In Proceedings of SIGGRAPH.
• 18: Kuhn, H. W. 1995. The hungarian method for the assignment problem. In Naval Research Logistic Quarterly, 2:83--97.
• 19: Liu, F., and Gleicher, M. 2005. Automatic Image Retargeting with Fisheye-View Warping. In ACM UIST, 153--162.
• 20: Liu, F., and Gleicher, M. 2006. Video Retargeting: Automating Pan and Scan. In ACM international conference on Multimedia, 241--250.
• 21: Liu, H., Xie, X., Ma, W., and Zhang, H. 2003. Automatic browsing of large pictures on mobile devices. Proceedings of the eleventh ACM international conference on Multimedia, 148--155.
• 22: Perez, P., Gangnet, M., and Blake, A. 2003. Poisson image editing. ACM Trans. Graph. 22, 3, 313--318.
• 23: Rother, C., Bordeaux, L., Hamadi, Y., and Blake, A. 2006. Autocollage. In Proceedings of SIGGRAPH 2006.
• 24: Santella, A., Agrawala, M., DeCarlo, D., Salesin, D., and Cohen, M. 2006. Gaze-based interaction for semi-automatic photo cropping. In ACM Human Factors in Computing Systems (CHI), 771--780.
• 25: Setlur, V., Takagi, S., Raskar, R., Gleicher, M., and Gooch, B. 2005. Automatic Image Retargeting. In In the Mobile and Ubiquitous Multimedia (MUM), ACM Press.
• 26: Suh, B., Ling, H., Bederson, B. B., and Jacobs, D. W. 2003. Automatic thumbnail cropping and its effectiveness. In UIST '03: Proceedings of the 16th annual ACM symposium on User interface software and technology, ACM Press, New York, NY, USA, 95--104.
• 27: Sun, J., Yuan, L., Jia, J., and Shum, H. 2005. Image completion with structure propagation. In Proceedings of ACM SIGGRAPH.
• 28: V. Kwatra, A. Schdl, I. E. G. T., and Bobick, A. 2003. Graphcut textures: Image and video synthesis using graph cuts. In Proceedings of SIGGRAPH.
• 29: Viola, P., and Jones, M. 2001. Rapid object detection using a boosted cascade of simple features. In Conference on Computer Vision and Pattern Recognition (CVPR).
• 30: Wang, J., and Cohen, M. 2006. Simultaneous Matting and Compositing. Microsoft Research Technical Report, MSR-TR-2006-63 (May).
• 31: Zomet, A., Levin, A., Peleg, S., and Weiss, Y. 2005. Seamless image stitching by minimizing false edges. IEEE Transactions on Image Processing 15, 4, 969--977.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.0 General

Additional Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
        I.4.10 Image Representation

Keywords:
content-aware image manipulation, display devices, image resizing, image retargeting, image seams