Seam carving for media retargeting

ABSTRACT

Traditional image resizing techniques are oblivious to the content of the image when changing its width or height. In contrast, media (i.e., image and video) retargeting take s content into account. For example, one would like to change the aspect ratio of a video without making human figures look too fat or too skinny, or change the size of an image by automatically removing "unnecessary" portions while keeping the "important" features intact. We propose a simple operator; we term seam carving to support image and video retargeting. A seam is an optimal 1D path of pixels in an image, or a 2D manifold in a video cube, going from top to bottom, or left to right. Optimality is defined by minimizing an energy function that assigns costs to pixels. We show that computing a seam reduces to a dynamic programming problem for images and a graph min-cut search for video. We demonstrate that several image and video operations, such as aspect ratio correction, size change, and object removal, can be recast as a successive operation of the seam carving operator.

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: Shai Avidan , Ariel Shamir, Seam carving for content-aware image resizing, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 3: Boykov, Y. and Jolly, M.-P. Interactive graph cuts for optimal boundary & region segmentation of objects in n-d images. In International Conference on Computer Vision (ICCV), volume I. 2001,105--112.
• 4: Chen, L., Xie, X., Fan, X., Ma, W., Zhang, H., and Zhou, H. A visual attention model for adapting images on small displays. Multimedia Systems 9, 4 (2003), 353--364.
• 5: J. Davis, Mosaics of Scenes with Moving Objects, Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, p.354, June 23-25, 1998
• 6: 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]
• 7: Xin Fan , Xing Xie , He-Qin Zhou , Wei-Ying Ma, Looking into video frames on small displays, Proceedings of the eleventh ACM international conference on Multimedia, November 02-08, 2003, Berkeley, CA, USA [doi>10.1145/957013.957063]
• 8: Gal, R., Sorkine, O., and Cohen-Or, D. Feature-aware texturing. In Eurographics Symposium on Rendering, 2006.
• 9: Laurent Itti , Christof Koch , Ernst Niebur, A Model of Saliency-Based Visual Attention for Rapid Scene Analysis, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.20 n.11, p.1254-1259, November 1998 [doi>10.1109/34.730558]
• 10: Jiaya Jia , Jian Sun , Chi-Keung Tang , Heung-Yeung Shum, Drag-and-drop pasting, ACM SIGGRAPH 2006 Papers, July 30-August 03, 2006, Boston, Massachusetts
• 11: 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
• 12: Feng Liu , Michael Gleicher, Automatic image retargeting with fisheye-view warping, Proceedings of the 18th annual ACM symposium on User interface software and technology, October 23-26, 2005, Seattle, WA, USA [doi>10.1145/1095034.1095061]
• 13: Feng Liu , Michael Gleicher, Video retargeting: automating pan and scan, Proceedings of the 14th annual ACM international conference on Multimedia, October 23-27, 2006, Santa Barbara, CA, USA [doi>10.1145/1180639.1180702]
• 14: Hao Liu , Xing Xie , Wei-Ying Ma , Hong-Jiang Zhang, Automatic browsing of large pictures on mobile devices, Proceedings of the eleventh ACM international conference on Multimedia, November 02-08, 2003, Berkeley, CA, USA [doi>10.1145/957013.957045]
• 15: Roditty, L. and Zwick, U. On dynamic shortest paths problems. In Proceedings of the 12th Annual European Symposium on Algorithms (ESA), 2004, 580--591.
• 16: Carsten Rother , Lucas Bordeaux , Youssef Hamadi , Andrew Blake, AutoCollage, ACM SIGGRAPH 2006 Papers, July 30-August 03, 2006, Boston, Massachusetts
• 17: Michael Rubinstein , Ariel Shamir , Shai Avidan, Improved seam carving for video retargeting, ACM Transactions on Graphics (TOG), v.27 n.3, August 2008
• 18: Anthony Santella , Maneesh Agrawala , Doug DeCarlo , David Salesin , Michael Cohen, Gaze-based interaction for semi-automatic photo cropping, Proceedings of the SIGCHI conference on Human Factors in computing systems, April 22-27, 2006, Montréal, Québec, Canada [doi>10.1145/1124772.1124886]
• 19: Arno Schödl , Richard Szeliski , David H. Salesin , Irfan Essa, Video textures, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.489-498, July 2000 [doi>10.1145/344779.345012]
• 20: Vidya Setlur , Saeko Takagi , Ramesh Raskar , Michael Gleicher , Bruce Gooch, Automatic image retargeting, Proceedings of the 4th international conference on Mobile and ubiquitous multimedia, December 08-10, 2005, Christchurch, New Zealand [doi>10.1145/1149488.1149499]
• 21: Simakov, D., Caspi, Y., Shechtman, E., and Irani, M. Summarizing visual data using bidirectional similarity. In Proceedings of CVPR, 2008.
• 22: Bongwon Suh , Haibin Ling , Benjamin B. Bederson , David W. Jacobs, Automatic thumbnail cropping and its effectiveness, Proceedings of the 16th annual ACM symposium on User interface software and technology, p.95-104, November 02-05, 2003, Vancouver, Canada [doi>10.1145/964696.964707]
• 23: Viola, P. and Jones, M. Rapid object detection using a boosted cascade of simple features. In Conference on Computer Vision and Pattern Recognition (CVPR), 2001.
• 24: Jue Wang , Pravin Bhat , R. Alex Colburn , Maneesh Agrawala , Michael F. Cohen, Interactive video cutout, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 25: Wang, J., Reinders, M., Lagendijk, R., Lindenberg, J., and Kankanhalli, M. Video content presentation on tiny devices. In IEEE International Conference on Multimedia and Expo (ICME), volume 3, 2004,1711--1714.
• 26: Jue Wang , Yingqing Xu , Heung-Yeung Shum , Michael F. Cohen, Video tooning, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 27: Yu-Shuen Wang , Chiew-Lan Tai , Olga Sorkine , Tong-Yee Lee, Optimized scale-and-stretch for image resizing, ACM Transactions on Graphics (TOG), v.27 n.5, December 2008
• 28: Li-Yi Wei , Jianwei Han , Kun Zhou , Hujun Bao , Baining Guo , Heung-Yeung Shum, Inverse texture synthesis, ACM Transactions on Graphics (TOG), v.27 n.3, August 2008
• 29: Wolf, L., Guttmann, M., and Cohen-Or, D. Non-homogeneous content-driven video-retargeting. In Proceedings of the 11th IEEE International Conference on Computer Vision (ICCV07), 2007,1--6.

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.10 Vision and Scene Understanding
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.9 Applications