The diversity and versatility of display devices today imposes new demands on
digital media. Designers must create different alternatives for webcontent
different layouts for different devices. Traditional image resizing techniques are oblivious
to the content of the image when changing its height or width. 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. Here is a simple operator; 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. Here showing that
computing a seam reduces to a dynamic programming problem for images and a graph
search for video and also 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
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. Computing a seam reduces to a
dynamic programming problem for images and graph mincut
search for video. A seam is
a path of pixels that travel horizontally or vertically with low energy.
Horizontal seam: A connected line from left to right that can move at most 1pixel
pixel per row.
Vertical seam: connected line from top to bottom, that can move at most 1pixel
Two constraints for calculating seams are
Monotonicity : the seam must include one and only one pixel, in each row for vertical
seams (or column for horizontal seams)
Connectivity : the pixels of the seams must be connected.
Finding the seam:
For ease of exposition, we will focus on images first, then we will
show how to extend the seam carving operator to handle video. Our approach to
resizing is to remove pixels in a judicious manner. Therefore, the
question is how to choose the pixels to be removed? Intuitively, our goal is to
remove unnoticeable pixels that blend with their surroundings. Since human
vision is more sensitive to edges, we give high value to edges using the following
simple energy function.
Given this, or similar, energy function, assume we need to reduce
the width of an image. One can think of several strategies to achieve this. For
instance, an optimal strategy to preserve energy (i.e., keep pixels with high
energy value) would be to remove the pixels with lowest energy in ascending
order. This destroys the rectangular shape of the image, because we may remove
a different number of pixels from each row. If we want to prevent the image from
breaking we can remove an equal of number low energy pixels from every row.
This preserves the rectangular shape of the image but destroys the image content
by creating a zigzag effect. To preserve both the shape and the visual coherence
of the image we can use autocropping.
That is, look for a subwindow, the size
of the target image, that contains the highest energy.
Another possible strategy
somewhat between removing pixels and cropping is to remove whole columns
with the lowest energy. Still, artifacts might appear in the resulting image.
Therefore, we need a resizing operator that will be less restrictive than
cropping or column removal, but can preserve the image content better than a
single pixel removals. This leads to our strategy of seam carving