Given an image, it is sometimes desirable to scale that image in only one dimension, for example, making it narrower without changing the height. As an example, consider the 505 pixel wide x 287 pixel tall image below. Suppose that we'd like to resize it to 357 x 287 pixels.
The easiest approaches are to rescale the image or crop the image. However rescaling ruins the aspect ratio, making everything look squashed, whereas cropping removes image content (like the poor guys on the right).


Scaled  Cropped 
By contrast, seam carving (published in 2007 by Shai Avidan and Ariel Shamir) resizes images in a content aware manner, resulting in much better results for some types of images. Unimportant pixels (like the ocean separating the two people in the middle) are thrown away, while interesting pixels like the people and the island on the left are preserved.


Original  Seam Carved 
Despite its power and modernity, the seam carving algorithm is elegant and easy to describe. We start by converting an image to a 2D "energy matrix" (see spec for details) using a very simple function that gives high energy values to important pixels, and low energy to unimportant ones. For example, the energy of the original image on this page is shown below to the left. An exaggerated version of the energies is shown below and to the right.


Energy of Original Image  Energy (Exaggerated) 
We then find the path from the top to the bottom such that the total energy of the path is minimized. This can be done either using a simple dynamic programming approach or by casting it as a shortest paths problem on a directed graph:
We then "shrink" the image by creating a copy of the original image, but excluding all of the seam pixels (highlighted in image above). Since the seam is exactly one pixel per row, the resulting image is one pixel narrower. To shrink the image further, we repeat the entire process as many times as we'd like, reducing the width by one each time.
Summary 
Students resize images using a stateoftheart but easy to understand algorithm that feels like magic. 
Topics 
2D and 3D arrays, dynamic programming or shortest paths in a weighted directed graph, image processing 
Audience 
Late CS1, CS2 
Difficulty 
Easy to moderate. Length of assignment can be reduced by providing energy calculation and/or seam removal code.

Strengths 

Weaknesses 

Library Dependencies 
Requires a library which can read in images as 3D arrays, and can display (or at least save) 3D arrays as images. 
Variants 
Students can try to find a way to expand images instead of shrinking them. They can do this either on their own (for stronger students), or by looking at the original SIGGRAPH paper or video, which provide key ideas. The original SIGGRAPH publications (and subsequent followups) provides other ideas, including targeted removal of objects. By selecting a region of the image and forcing its energy to zero, objects can be removed during the SeamCarving process. Default implementation involves recalculation of entire image energies everytime a seam is removed, resulting in quadratic performance. Using fancier data structures, it is possible to achieve a linear time seam removal. 