Multi-operator media retargeting

ABSTRACT

Content aware resizing gained popularity lately and users can now choose from a battery of methods to retarget their media. However, no single retargeting operator performs well on all images and all target sizes. In a user study we conducted, we found that users prefer to combine seam carving with cropping and scaling to produce results they are satisfied with. This inspires us to propose an algorithm that combines different operators in an optimal manner. We define a resizing space as a conceptual multi-dimensional space combining several resizing operators, and show how a path in this space defines a sequence of operations to retarget media. We define a new image similarity measure, which we term Bi-Directional Warping (BDW), and use it with a dynamic programming algorithm to find an optimal path in the resizing space. In addition, we show a simple and intuitive user interface allowing users to explore the resizing space of various image sizes interactively. Using key-frames and interpolation we also extend our technique to retarget video, providing the flexibility to use the best combination of operators at different times in the sequence.

REFERENCES

• 1: Shai Avidan , Ariel Shamir, Seam carving for content-aware image resizing, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 2: Chen, B., and Sen, P. 2008. Video carving. In Short Papers Proceedings of Eurographics.
• 3: 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.
• 4: Gal, R., Sorkine, O., and Cohen-Or, D. 2006. Feature-aware texturing. In Eurographics Symposium on Rendering, 297--303.
• 5: Daniel Keysers , Walter Unger, Elastic image matching is NP-complete, Pattern Recognition Letters, v.24 n.1-3, p.445-453, January 2003 [doi>10.1016/S0167-8655(02)00268-4]
• 6: 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]
• 7: 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]
• 8: Michael Rubinstein , Ariel Shamir , Shai Avidan, Improved seam carving for video retargeting, ACM Transactions on Graphics (TOG), v.27 n.3, August 2008
• 9: Sakoe, H. 1978. Dynamic programming algorithm optimization for spoken word recognition. IEEE Transactions on Acoustics, Speech, and Signal Processing 26, 43--49.
• 10: Stan Salvador , Philip Chan, Toward accurate dynamic time warping in linear time and space, Intelligent Data Analysis, v.11 n.5, p.561-580, October 2007
• 11: 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]
• 12: 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]
• 13: Simakov, D., Caspi, Y., Shechtman, E., and Irani, M. 2008. Summarizing visual data using bidirectional similarity. In Proc. of IEEE Conf. on Computer Vision and Pattern Recognition.
• 14: 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]
• 15: Seiichi Uchida , Hiroaki Sakoe, A Monotonic and Continuous Two-Dimensional Warping Based on Dynamic Programming, Proceedings of the 14th International Conference on Pattern Recognition-Volume 1, p.521, August 16-20, 1998
• 16: Yu-Shuen Wang , Chiew-Lan Tai , Olga Sorkine , Tong-Yee Lee, Optimized scale-and-stretch for image resizing, ACM SIGGRAPH Asia 2008 papers, December 10-13, 2008, Singapore
• 17: 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
• 18: Wolf, L., Guttmann, M., and Cohen-Or, D. 2007. Nonhomogeneous content-driven video-retargeting. In Proceedings of the Eleventh IEEE International Conference on Computer Vision (ICCV '07), 1--6.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.7 Feature Measurement

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.10 Vision and Scene Understanding
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Dynamic programming
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Similarity measures

General Terms:
Algorithms, Design, Measurement

Keywords:
bidirectional warping, media retargeting, multi-operator, resizing space