Seam Carving for Content-Aware Image Resizing

Figure 1: A seam is a connected path of low energy pixels. The image on the left is the original image, the second image shows the seams removed to obtain the third image.

The same seams may be duplicated to increase the width of the image to obtain the image on the right.

Overview

Seam Carving is an algorithm to resize images while preserving the “content” of the image. Every pixel has an associated energy which is a measure of the gradient at that pixel; however other energy measures may be used. Given an energy function defined over the pixels, there are many strategies to alter the dimensions of the image. For example, one can start removing pixels of the lowest energy. This will destroy the rectangular shape of the image; hence we should remove an equal number of pixels from each row. This strategy preserves the rectangular shape but would destroy the image content and introduce many artifacts. Another strategy is to remove a low energy column from the image, but this strategy will be too restrictive. Instead the authors propose to remove a “seam”, which is defined as a connected path of low energy pixels.

More formally, a vertical seam s^x is an 8-connected path of pixels that runs from the top of the image to the bottom. The energy E(s) of a seam s is defined as the sum of the energies of pixels lying on the seam. An optimal seam s*, is simply the seam with the lowest energy. The optimal seam may be found using dynamic programming. Let M(i,j) denote the minimum energy over all seams running from the top of the image to the pixel (i,j). Then,

Where e(i,j) is the energy of the pixel (i,j). The minimum value in the last row of M will correspond to the optimal vertical seam.

Reducing the size of the image along a single dimension

This is achieved simply by removing the desired number of horizontal or vertical seams. Figure 1 shows an example where 50 vertical seams were removed from the original image in order to obtain the third image with reduced width.

Reducing the size of the image along both dimensions

Assume that we want to resize a nXm image to n’Xm’ image where n’≤n and m’≤m. Although this can be achieved by first removing (n-n’) vertical seams followed by removal of (m-m’) horizontal seams, but this may not be the optimal order. The optimal order of seam removal is found using dynamic programming. Let T(r,c) denote the cost of obtaining an image of size (n-r)X(m-c). We can arrive at an image of these dimensions by either removing a horizontal seam from an image of dimensions (n-r)X(m-c+1) or removing a vertical seam from an image of size (n-r+1)X(m-c). Hence,

Where is the cost of removing a horizontal seam from the image and is the cost of removing a vertical seam from the image . Practically we observed that simply removing the required number of horizontal and vertical seams in any order gave comparable results.

Image Enlargement

The most straightforward method to enlarge an image is to duplicate the optimal seam. However, this creates stretching artifacts when enlarging by large amounts as the same pixels would be duplicated repeatedly. Hence, to increase the width of the image by k pixels, we instead first find the first k seams that will be removed if the image width is decreased by k, and then duplicate those seams to increase the width. Figure 1 shows the result of enlarging the width of an image by 50 pixels by duplicating the 50 seams shown in the second image. However, extreme resizing is likely to produce artifacts as shown in Figure 2.

Figure 2: Stretching artifacts

Applications based on augmented pixel energy functions

In the seam carving process, seams are removed based on the energy content of the image regions. In the examples above, this energy content is based on the gradient magnitude. The energy content can also be visualized as an importance map defined for the pixels in the image. So using gradient based energy means that smooth regions have less importance and will be removed first.

We can also define new importance maps to augment gradients to get interesting applications.

Object removal or preservation

Through the user interface, the user can specify importance of individual pixels by painting on the image. These importance weights are added to the gradient energy function.

To reduce artifacts in nearby regions, we can increase the importance there as shown below.

Motion aware seam carving for image sequences

We computed optical flow ^[2] on an image sequence to measure the amount of motion each pixel is going through. Results of some sample frames are shown here.

Image Sequence

Optical Flow maps (Brightness of a pixel is proportional to the magnitude of the motion vector)

Foreground removal

For removing the moving foreground, we decrease the importance of the pixels in proportion to their motion vector magnitude. We get the following results after decreasing the width by 75%.

Background removal

For removing the static background, we increase the importance of the pixels in proportion to their motion vector magnitude. We get the following results after decreasing the width by 25%.

Using only gradient based importance for pixels leads to deformation artifacts as seen on the arm.

Future directions

A higher level understanding of the image content

As of now, doing seam carving leads to removal of seams across the image leading to aliasing artifacts as seen in the following figure.

This is mainly because the energy content is defined at the level of pixels. We can think of new energy maps based on the statistics of patches instead of pixels. For example, in the above case we would have liked to remove seams through the grass regions instead of those intersecting the sticks. However, having a consistent definition of these statistics across all the images is difficult.

Seam carving for videos

Seam carving run individually on consecutive frames does not lead to temporal coherence. Objects are seen to jump around. We may want to “flow” the removed seams across frames using correspondence information to enforce temporal consistency. Also, instead of removing one-dimensional seams in image sequences as above, we can consider the whole video as a space-time volume and remove two-dimensional manifolds from this. However the optimal manifold using simple dynamic programming.

User interaction

More controls can be provided to the user than just importance brushes. The user may decide to draw rectangles around objects and choose to maintain the aspect ratio of the object during the resizing process. This will require significant implementation and algorithmic changes to the system.

References

[1] Avidan S., Shamir A., 2007, “Seam Carving for Content-Aware Image Resizing”, In Proceedings of SIGGRAPH.

[2] Sand P., Teller S., 2006, “Particle Video: Long-Range Motion Estimation using Point Trajectories”, In Proceedings of CVPR.