“Improved seam carving for video retargeting” by Rubinstein, Shamir and Avidan

Video, like images, should support content aware resizing. We present video retargeting using an improved seam carving operator. Instead of removing 1D seams from 2D images we remove 2D seam manifolds from 3D space-time volumes. To achieve this we replace the dynamic programming method of seam carving with graph cuts that are suitable for 3D volumes. In the new formulation, a seam is given by a minimal cut in the graph and we show how to construct a graph such that the resulting cut is a valid seam. That is, the cut is monotonic and connected. In addition, we present a novel energy criterion that improves the visual quality of the retargeted images and videos. The original seam carving operator is focused on removing seams with the least amount of energy, ignoring energy that is introduced into the images and video by applying the operator. To counter this, the new criterion is looking forward in time – removing seams that introduce the least amount of energy into the retargeted result. We show how to encode the improved criterion into graph cuts (for images and video) as well as dynamic programming (for images). We apply our technique to images and videos and present results of various applications.

1. Avidan, S., and Shamir, A. 2007. Seam carving for content-aware image resizing. ACM Trans. Graph. 26, 3, 10. Google ScholarDigital Library
2. Boykov, Y., and Kolmogorov, V. 2004. An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision. IEEE Transactions on Pattern Analysis and Machine Intelligence 26, 9, 1124–1137. Google ScholarDigital Library
3. Chen, B., and Sen, P. 2008. Video carving. In Short Papers Proceedings of Eurographics.Google Scholar
4. Fan, X., Xie, X., Zhou, H.-Q., and Ma, W.-Y. 2003. Looking into video frames on small displays. In MULTIMEDIA ’03: Proceedings of the eleventh ACM international conference on Multimedia, ACM, 247–250. Google ScholarDigital Library
5. Kohli, P., and Torr, P. H. S. 2007. Dynamic graph cuts for efficient inference in markov random fields. IEEE Trans. Pattern Analysis and Machine Intelligence (PAMI) 29, 12, 2079–2088. Google ScholarDigital Library
6. Kwatra, V., Schödl, A., Essa, I., Turk, G., and Bobick, A. 2003. Graphcut textures: image and video synthesis using graph cuts. ACM Trans. Graph. 22, 3, 277–286. Google ScholarDigital Library
7. Liu, F., and Gleicher, M. 2006. Video retargeting: automating pan and scan. In MULTIMEDIA ’06: Proceedings of the 14th annual ACM international conference on Multimedia, ACM, 241–250. Google ScholarDigital Library
8. Lombaert, H., Sun, Y., Grady, L., and Xu, C. 2005. A multilevel banded graph cuts method for fast image segmentation. In Proceedings of the Tenth IEEE International Conference on Computer Vision (ICCV’05), vol. 1, 259–265. Google ScholarDigital Library
9. Pritch, Y., Rav-Acha, A., and Peleg, S. 2008. Nonchronological video synopsis and indexing. IEEE Trans. Pattern Analysis and Machine Intelligence (PAMI), to appear. Google ScholarDigital Library
10. Rav-Acha, A., Pritch, Y., Lischinski, D., and Peleg, S. 2007. Dynamosaicing: Mosaicing of dynamic scenes. IEEE Trans. Pattern Analysis and Machine Intelligence (PAMI) 29, 10, 1789–1801. Google ScholarDigital Library
11. Schödl, A., Szeliski, R., Salesin, D. H., and Essa, I. 2000. Video textures. In SIGGRAPH ’00: Proceedings of the 27th annual conference on Computer graphics and interactive techniques, ACM Press/Addison-Wesley Publishing Co., 489–498. 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. Tao, C., Jia, J., and Sun, H. 2007. Active window oriented dynamic video retargeting. In Proceedings of the Workshop on Dynamical Vision, ICCV 2007.Google Scholar
14. Viola, P., and Jones, M. J. 2004. Robust real-time face detection. Int. J. Comput. Vision 57 2, 137–154. Google ScholarDigital Library
15. Wang, J., Xu, Y., Shum, H.-Y., and Cohen, M. F. 2004. Video tooning. ACM Trans. Graph. 23, 3, 574–583. Google ScholarDigital Library
16. Wang, J., Reinders, M., Lagendijk, R., Lindenberg, J., and Kankanhalli, M. 2004. Video content presentation on tiny devices. In IEEE International Conference on Multimedia and Expo (ICME), vol. 3, 1711–1714.Google Scholar
17. Wang, J., Bhat, P., Colburn, R. A., Agrawala, M., and Cohen, M. F. 2005. Interactive video cutout. ACM Trans. Graph. 24, 3, 585–594. 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