Seam carving is an algorithm for image resizing

Image scaling

In computer graphics, image scaling is the process of resizing a digital image. Scaling is a non-trivial process that involves a trade-off between efficiency, smoothness and sharpness. As the size of an image is increased, so the pixels which comprise the image become increasingly visible, making...

, developed by Shai Avidan, of Mitsubishi Electric Research Labs (MERL), and Ariel Shamir, of the Interdisciplinary Center

Interdisciplinary Center

The Interdisciplinary Center, Herzliya is a private Israeli college located in Herzliya, Israel.The languages of instruction in the Interdisciplinary Center are Hebrew and English.-History:...

 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.

Seams

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.

Computing Seams

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

Dijkstra's algorithm

Dijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree...

, dynamic programming, or graph cuts

Cut (graph theory)

In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. The cut-set of the cut is the set of edges whose end points are in different subsets of the partition. Edges are said to be crossing the cut if they are in its cut-set.In an unweighted undirected graph, the...

 .

Dynamic Programming

Dynamic programming

Dynamic programming

In mathematics and computer science, dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems which are only slightly smaller and optimal substructure...

 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.

This is better described by this image:
The first row has no rows above it, so the sum (black) is just the energy value of the current pixel (red).

The second row, if we look at the second pixel for example, we see its energy value is a 2 (red). If we look above it, it has a choice of either 1, 4, or 3 (black). Since 1 is the minimum number of the three values, we ignore the other two and set the sum of the pixel to its energy value which is 2 (red) plus 1 (black).

After the above operation is carried out for every pixel in the second row, we go to the third row:
We repeat the process in row two in row three to end up with the final cumultive sums for the seams/paths. The lowest value or values are the seams with the lowest energy, which would be in this example the seams with '5' in the last row.

To trace the seam/path, work from the last row and follow the green arrows:

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:

Issues

1. The algorithm may need user provided information to reduce errors. This can consist of painting the regions which are to be preserved. With human faces it is possible to use face detection.
2. Sometimes the algorithm by removing a low energy seam may end up inadvertently creating a seam of higher energy. The solution to this is to simulate a removal of a seam, and then check the energy delta to see if the energy increases. If it does, prefer other seams instead.

Implementations

Adobe Systems

Adobe Systems

Adobe Systems Incorporated is an American computer software company founded in 1982 and headquartered in San Jose, California, United States...

 acquired a non-exclusive license to seam carving technology from MERL, and implemented it as a feature in Photoshop CS4, where it is called Content Aware Scaling.
As the license is non-exclusive, other popular computer graphics applications, among which are GIMP

GIMP

GIMP is a free software raster graphics editor. It is primarily employed as an image retouching and editing tool and is freely available in versions tailored for most popular operating systems including Microsoft Windows, Apple Mac OS X, and Linux.In addition to detailed image retouching and...

, digiKam

DigiKam

digiKam is an image organizer and editor using KDE Platform. It runs on most known desktop environments and window managers if the required libraries are installed. It supports all major image file formats, and can organize collections of photographs in directory-based albums, or dynamic albums by...

, and ImageMagick

ImageMagick

ImageMagick is an open source software suite for displaying, converting, and editing raster image files. It can read and write over 100 image file formats. ImageMagick is licensed under the Apache 2.0 license.- Features and capabilities:...

, as well as some stand-alone programs, also have implementations of this technique, some of which are released as free and open source software

Free and open source software

Free and open-source software or free/libre/open-source software is software that is liberally licensed to grant users the right to use, study, change, and improve its design through the availability of its source code...

.

Improvements and extensions

• Better energy function and application to video.
• Combine with cropping and scaling.
• Much faster removal of multiple seams
• On-demand, server-side seam carving

External links

• Seam Carving demonstration videos:
  • on YouTube
  • on Ariel Shamir's pages on the Interdisciplinary Center web site (higher resolution)
• Explanation of seam carving (Liquid rescaling) at the ImageMagick
  ImageMagick
  ImageMagick is an open source software suite for displaying, converting, and editing raster image files. It can read and write over 100 image file formats. ImageMagick is licensed under the Apache 2.0 license.- Features and capabilities:...
  
  website