NOTE: A Newer version of this tutorial may exist. Click here to go to the never version

<--Back to Projects

COS 429 Assignment #2: Seam Carving

Chris Tralie
Platform: Windows Vista SP2 Using Matlab 7.7.0 (R2008b)
Assignment Specification

Purpose / Algorithm

Simply scaling an image down will blur important areas just as much as unimportant areas (e.g. a huge sky background with little data will be blurred just the same as someone's face in the foreground). The seam carving algorithm is a "content aware image resizer"; that is, it tries to do a better job than just uniform scale by choosing to erase areas of the image that are "less noticeable." It removes a "seam" from an image, which is a line of connected pixels from top to bottom or left to right whsoe presence is the least noticeable if removed. This "least noticeable" effect is determined by applying an objective function to every possible seam. The choice of objective function in this assignment is the absolute sum of both gradient components. Minimizing this ensures that regions with the least energy/detail get removed first.

Implementation Details


First, here is an example of the energy image and the minimum vertical and horizontal seams for an image:
Original Image (Dimension 640x480,)
Objective energy function
Vertical Seam
Horizontal Seam

Here is an example of the image sized by 25% down in both the horizontal and vertical directions

Sized down to 75% horizontally (new resolution 480x480). Note how well all of the important features and sizes are preserved. My face has barely changed in size, and all of the pictures in the background are still in tact, since the seams mostly only removed sections of the couch and the blank wall in the background that are unimportant.Sized down to 75% in vertical direction (new resolution 640 x 360). NOTE that my hair is a bit distorted here since there are many fewer horizontal seams than vertical seams (so distortion is inevitable). But the sizes of all of the rest of the features turned out well.

Here is another example:
Original image (672x420)Retargeted image (500x400)
NOTE: The seam carving techique did a great job at retaining the important parts of the image here; notice how the items on the desk (the computer, keyboard, mouse, and clipboard) have moved closer together, but that they have barely changed in size. Also note how the specks on the wall have moved closer together as a result of moving minimum cost seams, and how the calendar has been preserved between the two images.

Here is another example:
Original image (615x372)Retargeted image (450x350)
I was starting to really push the boundaries here, but it still worked without too many artifacts

One last example:
Original image (576x432)Retargeted image (400x400)
This one worked extremely well, and it's perhaps one of the best. In general, it seems that the nature scenese work out the best since there is so much detail to begin with, moving seams in areas of less detail is that much less noticeable in the overall effect.

Remove Feature Extension

One trick that can be played with seam carving is to intentionally zero regions of the objective energy function so certain regions of the image get removed first. I extended my seam carver so that the user can supply an extra black/white image, where black regions will be marked to zero in the energy image. Here are a few examples with this extension:

Original ImageHouse marked for removal
Result of resizing
This result shows one of the dangers of using this trick. Note that since there is a lot of variation in the clouds, a noticeable artifact has been introduced there (not the case with the sand since it is more homogenous throughout the image). If there are regions of high variation like that and the objective energy function is tweaked, then the chances of distorting the image will increase.

Here is a slightly better result:
Original ImagePerson marked for removal
Result of resizing

This example worked much better, since the sky, the water, and the sand are all very homogeneous and removing seams that go through the child standing there is much less noticeable.

Code Summary

EnergyImg.mCalculates the objective function for a grayscale image, using the gradient method discussed above
find_vertical_seam.mFinds the minimum cost vertical seam using dynamic programming
find_horizontal_seam.mFinds the minimum cost horizontal seam by calling the vertical seam function with the transpose of the grayscale image
markSeam.mMarks a horizontal or vertical seam in red in the color image
remove_horizontal_seam.mRemoves a horizontal seam from an image and shifts all of the pixels below it up, then removes the last row
remove_vertical_seam.mRemoves a vertical seam from an image and shifts all of the pixels to the right of it to the left, then removes the last column
seam_carve_extended.mTakes a filename for the image, a filename for the regions to be removed (the extra step I did), and a target number of rows and columns. This will resize the image to the target size by removing horizontal and vertical seams one by one
seam_carve.mAn overloaded version of the seam carver that doesn't take a remove image.

<--Back to Projects