These series of Posts will talk about the video retargeting using Improved Seam carving ,So let’s start our journey in this interesting topic.

First of all, We should talk about the standard Seam carving which is related to the image retargeting to understand the concept of media retargeting , then We will talk in details about the video retargeting  in further posts .

What’s Seam carving ?

Seam carving (also known as image retargeting, content-aware image resizing, content-aware scaling, liquid resizing, or liquid rescaling), is an algorithm for image resizing, developed by Shai Avidan, of Mitsubishi Electric Research Labs (MERL), and Ariel Shamir, of the Interdisciplinary Center and MERL. It functions by establishing a number of seams (paths of least importance) in an image and automatically removes seams to reduce image size or inserts seams to extend it. Seam carving also allows manually defining areas in which pixels may not be modified, and features the ability to remove whole objects from photographs. The purpose of the algorithm is to display images without distortion on various media (cell phones, PDAs) using document standards, like HTML, that already support dynamic changes in page layout and text, but not images.

What is meant by a Seam ?

Seams can be either vertical or horizontal. A vertical seam is a path of pixels connected from top to bottom in an image with one pixel in each row. A horizontal seam is similar with the exception of the connection being from left to right. The importance/energy function values a pixel by measuring its contrast with its neighbor pixels.

How can we calculate a Seam ?

Computing the seam consists of finding the path of minimum cost from one end of the image to another. This can be done via Dijkstra’s algorithm or dynamic programming .

Dynamic Programming (DP) is a programming method that stores the results of sub-calculations in order to simplify calculating a more complex result. Dynamic programming is used in seam carving for computing seams.

If attempting to compute a vertical seam (path) of lowest energy, for each pixel in a row we compute the energy of the current pixel plus the energy of one of the three possible pixels above it.

Algorithm

1. We start with an image such as :

2. We then calculate the weight/density/energy of each pixel. This can be done by various algorithms: gradient magnitude, entropy, visual saliency, eye-gaze movement. Although gradient magnitude gives ‘satisfactory results.

3. After we have the energy of the image, we generate a list of seams. Seams are ranked by energy, with low energy seams being of least importance to the content of the image. We can choose to calculate seams via the dynamic programming approach.

Seams shown with the energy function	Seams shown with the original image

4. We then remove the seams from the image, reducing the size of the image as a result:

The recalculated energy function of the image would be:

To Be Continued…….Next Post will be  the standard Seam carving in Videos using Static Seams

References

• Wikipedia Page
• Seam Carving for Content-Aware Image Resizing. Shai Avidan, Ariel Shamir, 2007.