Doi: 10.1145/1435417.1435437
Seam Carving
for Media Retargeting
By Ariel shamir and shai Avidan
abstract
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.
1. intRoDuction
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.
