“Multi-operator media retargeting” by Rubinstein, Shamir and Avidan

  • ©Michael Rubinstein, Ariel Shamir, and Shai Avidan




    Multi-operator media retargeting



    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.


    1. Avidan, S., and Shamir, A. 2007. Seam carving for contentaware image resizing. ACM Trans. Graph. 26, 3, 10. Google ScholarDigital Library
    2. Chen, B., and Sen, P. 2008. Video carving. In Short Papers Proceedings of Eurographics.Google Scholar
    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.Google ScholarDigital Library
    4. Gal, R., Sorkine, O., and Cohen-Or, D. 2006. Feature-aware texturing. In Eurographics Symposium on Rendering, 297–303. Google ScholarDigital Library
    5. Keysers, D., and Unger, W. 2003. Elastic image matching is np-complete. Pattern Recogn. Lett. 24, 1–3, 445–453. Google ScholarDigital Library
    6. Liu, F., and Gleicher, M. 2006. Video retargeting: automating pan and scan. In Proc. of the 14th annual ACM international conf. on Multimedia, ACM, 241–250. Google ScholarDigital Library
    7. Liu, H., Xie, X., Ma, W., and Zhang, H. 2003. Automatic browsing of large pictures on mobile devices. Proceedings of the 11tn ACM international conf. on Multimedia, 148–155. Google ScholarDigital Library
    8. Rubinstein, M., Shamir, A., and Avidan, S. 2008. Improved seam carving for video retargeting. ACM Trans. Graph. 27, 3. Google ScholarDigital Library
    9. Sakoe, H. 1978. Dynamic programming algorithm optimization for spoken word recognition. IEEE Transactions on Acoustics, Speech, and Signal Processing 26, 43–49.Google ScholarCross Ref
    10. Salvador, S., and Chan, P. 2007. Toward accurate dynamic time warping in linear time and space. Intell. Data Anal. 11, 5, 561–580. Google ScholarCross Ref
    11. Santella, A., Agrawala, M., DeCarlo, D., Salesin, D., and Cohen, M. 2006. Gaze-based interaction for semiautomatic photo cropping. In ACM Human Factors in Computing Systems (CHI), 771–780. Google ScholarDigital Library
    12. 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. Google ScholarDigital Library
    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.Google Scholar
    14. 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, 95–104. Google ScholarDigital Library
    15. Uchida, S., and Sakoe, H. 1998. A monotonic and continuous two-dimensional warping based on dynamic programming. In ICPR ’98: Proceedings of the 14th International Conference on Pattern Recognition-Volume 1, 521. Google ScholarDigital Library
    16. Wang, Y.-S., Tai, C.-L., Sorkine, O., and Lee, T.-Y. 2008. Optimized scale-and-stretch for image resizing. ACM Trans. Graph. (Proceedings of ACM SIGGRAPH ASIA 27, 5. Google ScholarDigital Library
    17. Wei, L.-Y., Han, J., Zhou, K., Bao, H., Guo, B., and Shum, H.-Y. 2008. Inverse texture synthesis. ACM Trans. Graph. 27, 3, 1–9. Google ScholarDigital Library
    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.Google Scholar

ACM Digital Library Publication: