Seam Carving for Media Retargeting

Definition of Seam Carving for Media Retargeting

The diversity and versatility of display devices today imposes new demands on digital media. Designers must create different alternatives for webcontent and design 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 mincut 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

Introduction of Seam Carving for Media 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. 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 1 pixel per row.
Vertical seam: connected line from top to bottom, that can move at most 1pixel per column.
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 contentaware 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