Doi: 10.1145/1435417.1435437
By Ariel shamir and shai Avidan
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 takes 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.
The diversity and versatility of display devices today imposes new demands on digital media. Designers must create different alternatives for web-content and design different layouts, possibly even dynamic layouts, for different devices. Nevertheless, images and video, although being key elements in digital media, typically remain rigid in size and shape and cannot deform to fit different displays. To accommodate high definition TVs, computer screens, PDAs, and cell phones not only the resolution, but often the aspect ratio of the media must be adjusted. Standard image scaling is not sufficient since it is oblivious to the image content and typically can be applied only uniformly. Cropping is limited since it can only remove pixels from the image periphery and cannot support expansion (Figure 1). More effective resizing can only be achieved by considering the image content and not only geometric constraints. We propose a simple operator, we term seam carving, which can change the size of images and video by gracefully carving out or inserting pixels in different parts of the media. Seam carving is based on the definition of an energy function defining the importance of pixels. In images, a seam is a connected path of low energy pixels crossing the image from top to bottom (or from left to right), and is monotonic, that is, including one, and only one, pixel in each row (or column). In video, a seam is a monotonic and connected low energy 2D manifolds passing through a 3D volume cube defined by stacking the video frames (Figure 2).
By successively removing or inserting seams we can reduce, as well as enlarge, the size of media in both directions. For size reduction, seam selection ensures that we remove more of the low energy pixels and fewer of the high energy ones from the source, while also taking care to insert the least amount of energy to the target. For enlarging, the order of seam insertion ensures a balance between the original media content and the artificially inserted pixels. These operators produce, in effect, a content-aware resizing of media.
On images, the search for an optimal seam can be formulated using an efficient dynamic programming algorithm, which is linear in the number of pixels. For videos the dynamic programming approach is no longer applicable. We show how to define a graph such that running the min-cut/max-flow algorithm on it will create a cut that is a 2D
figure 1: content aware vs. content oblivious resizing: scaling (left) creates distortion, cropping (middle) removes important parts, while seam carving (right) preserves the image content.
This paper is a summary of two papers originally published in SIGGRAPH Proceedings: Seam carving for content-aware image resizing. ACM Trans. Graph. 26, 3 (2007), 10; Improved seam carving for video retargeting. ACM Trans. Graph. 27, 3 (2008), 10.
References:
Archives