“Seam carving for content-aware image resizing” by Avidan and Shamir

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.

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. Google ScholarDigital Library
2. Bertalmio, M., Sapiro, G., Caselles, V., and Ballester, C. 2000. Image inpainting. In Proceedings of ACM SIGGRAPH, 417–424. Google ScholarDigital Library
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.Google Scholar
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.Google Scholar
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.Google ScholarDigital Library
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. Google ScholarDigital Library
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.Google Scholar
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. Google ScholarDigital Library
9. Davis, J. 1998. Mosaics of scenes with moving objects. In Proceedings of CVPR. Google ScholarDigital Library
10. DeCarlo, D., and Santella, A. 2002. Stylization and abstraction of photographs. In Proceedings of SIGGRAPH, 769–776. Google ScholarDigital Library
11. Drori, I., Cohen-Or, D., and Yeshurun, Y. 2003. Fragment-based image completion. In Proceedings of ACM SIGGRAPH, 303–312. Google ScholarDigital Library
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. Google ScholarDigital Library
13. Gal, R., Sorkine, O., and Cohen-Or, D. 2006. Feature-aware texturing. In Eurographics Symposium on Rendering. Google ScholarCross Ref
14. Harris, C., and Stephens, M. 1988. A combined corner and edge detector. In Proceedings of the 4th Alvey Vision Conference, 147–151.Google Scholar
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. Google ScholarDigital Library
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. Google ScholarDigital Library
17. Jia, J., Sun, J., Tang, C.-K., and Shum, H.-Y., 2006. Drag-and-drop pasting. In Proceedings of SIGGRAPH. Google ScholarDigital Library
18. Kuhn, H. W. 1995. The hungarian method for the assignment problem. In Naval Research Logistic Quarterly, 2:83–97.Google ScholarCross Ref
19. Liu, F., and Gleicher, M. 2005. Automatic Image Retargeting with Fisheye-View Warping. In ACM UIST, 153–162. Google ScholarDigital Library
20. Liu, F., and Gleicher, M. 2006. Video Retargeting: Automating Pan and Scan. In ACM international conference on Multimedia, 241–250. Google ScholarDigital Library
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. Google ScholarDigital Library
22. Perez, P., Gangnet, M., and Blake, A. 2003. Poisson image editing. ACM Trans. Graph. 22, 3, 313–318. Google ScholarDigital Library
23. Rother, C., Bordeaux, L., Hamadi, Y., and Blake, A. 2006. Autocollage. In Proceedings of SIGGRAPH 2006. Google ScholarDigital Library
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. Google ScholarDigital Library
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. Google ScholarDigital Library
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. Google ScholarDigital Library
27. Sun, J., Yuan, L., Jia, J., and Shum, H. 2005. Image completion with structure propagation. In Proceedings of ACM SIGGRAPH. Google ScholarDigital Library
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. Google ScholarDigital Library
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).Google Scholar
30. Wang, J., and Cohen, M. 2006. Simultaneous Matting and Compositing. Microsoft Research Technical Report, MSR-TR-2006-63 (May).Google Scholar
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. Google ScholarDigital Library