What is Seam Carving?

Seam carving is a technique for image resizing, where the size of an image is reduced by one pixel in height (by removing a horizontal seam) or width (by removing a vertical seam) at a time. Unlike cropping pixels from the edges or scaling the entire image, seam carving is content-aware, because it attempts to identify and preserve the most important content in an image by inferring the “importance” of each pixel from the surrounding pixels.

Say for example that you want to crop this image1 of Broadway Tower into a square:

Original image Simple cropping Seam carving
Original image of Broadway Tower, Cotswolds with a tower and a person on a field. Simple cropping. To get to the desired size, we can't see both the person and the tower at the same time. Seam carved. You can see both the person and the castle.
Original image. The cropping is done from the edges, and the tower has to be cropped out to make it square. The width is reduced by removing repetitive grass deemed “unimportant” from the middle.

How does Seam Carving work?

Seam carving works by using an energy function to find the lowest energy-connected pixels either horizontally or vertically across an image and then removing it.

Our implementation uses a DualGradientEnergyFunction helper class (already implemented for you). You will use this as the cost function when you model the image as a graph!

A little mathematical background if you’re interested

By energy function, “energy” is of the same concept as finding derivatives in calculus:

  • The energy of a pixel is the magnitude of the rate of change of colors at that pixel, and that rate of change in turn is defined by the difference in color between the pixel and its neighbors.
  • A high energy pixel is one that has a large change from its neighbors while a low energy pixel has very little change between itself and its neighbors.

The way a DualGradientEnergyFunction calculates an energy value is by approximating the derivative in the XX and YY directions then combine these using the Pythagorean theorem to get the overall change.

This video from the algorithm’s original inventors explains the algorithm visually (we will not implement the image enlargement part of the algorithm):

Project Starter Code

Inside src/seamcarving, you’ll find the SeamCarver class that represents the overall seam carving application. It has methods for removing the least-noticeable horizontal or vertical seams from a picture. The removeHorizontal() method works by:

  1. Calling SeamFinder.findHorizontal() to find the least-noticeable horizontal seam.
  2. Removing this horizontal seam by creating a new picture with all the pixels except for the ones specified in the horizontal seam.
  3. Returning the horizontal seam (primarily to verify that the correct seam was removed).

The removeVertical() method does the same thing except in the vertical orientation.

  1. Taken by Newton2 on April 5, 2007. Used and cropped under a CC BY 2.5 license. ↩