Programming Assignment 7: Seam Carving


Seam-carving is a content-aware image resizing technique where the image is reduced in size by one pixel of height (or width) at a time. A vertical seam in an image is a path of pixels connected from the top to the bottom with one pixel in each row; a horizontal seam is a path of pixels connected from the left to the right with one pixel in each column. Below left is the original 505-by-287 pixel image; below right is the result after removing 150 vertical seams, resulting in a 30% narrower image. Unlike standard content-agnostic resizing techniques (such as cropping and scaling), seam carving preserves the most interest features (aspect ratio, set of objects present, etc.) of the image.

The underlying algorithm is simple and elegant, but the technique was not discovered until 2007 by Shai Avidan and Ariel Shamir. Now, it is a core feature in Adobe Photoshop (thanks to a Princeton graduate student) and other computer graphics applications.

Dr. Hug in the ocean Dr. Hug in the ocean

In this assignment, you will create a data type that resizes a W-by-H image using the seam-carving technique. Finding and removing a seam involves three parts and a tiny bit of notation:

  1. Notation. In image processing, pixel (x, y) refers to the pixel in column x and row y, with pixel (0, 0) at the upper left corner and pixel (W − 1, H − 1) at the bottom right corner. This is consistent with the Picture data type in stdlib.jar. Warning: this is the opposite of the standard mathematical notation used in linear algebra where (i, j) refers to row i and column j and with Cartesian coordinates where (0, 0) is at the lower left corner.

    a 3-by-4 image
      (0, 0)     (1, 0)     (2, 0)  
      (0, 1)     (1, 1)     (2, 1)  
      (0, 2)     (1, 2)     (2, 2)  
      (0, 3)     (1, 3)     (2, 3)  

    We also assume that the color of a pixel is represented in RGB space, using three integers between 0 and 255. This is consistent with the java.awt.Color data type.

  2. Energy calculation. The first step is to calculate the energy of each pixel, which is a measure of the importance of each pixel—the higher the energy, the less likely that the pixel will be included as part of a seam (as we'll see in the next step). In this assignment, you will use the dual-gradient energy function, which is described below. Here is the dual gradient of the surfing image above:

    Dr. Hug as energy

    The energy is high (white) for pixels in the image where there is a rapid color gradient (such as the boundary between the sea and sky and the boundary between the surfing Josh Hug on the left and the ocean behind him). The seam-carving technique avoids removing such high-energy pixels.

  3. Seam identification. The next step is to find a vertical seam of minimum total energy. This is similar to the classic shortest path problem in an edge-weighted digraph, but there are three important differences:

    Seams can wrap around the image (e.g. a vertical seam can cross from the leftmost column of the image to the rightmost column). This is equivalent to treating the image as a torus. For example, when finding a vertical seam, there is a directed edge from pixel (0, y) to pixels (W − 1, y + 1), (0, y + 1), and (1, y + 1) and from pixel (W − 1, y) to pixels (W − 2, y + 1), (W − 1, y + 1), and (0, y + 1).

    Vertical Seam
  4. Finding a horizontal seam is analogous.

  5. Seam removal. The final step is remove from the image all of the pixels along the vertical or horizontal seam.

The SeamCarver API. Your task is to implement the following mutable data type:

public class SeamCarver {
   public SeamCarver(Picture picture)                // create a seam carver object based on the given picture
   public Picture picture()                          // current picture
   public     int width()                            // width of current picture
   public     int height()                           // height of current picture
   public  double energy(int x, int y)               // energy of pixel at column x and row y
   public   int[] findHorizontalSeam()               // sequence of indices for horizontal seam
   public   int[] findVerticalSeam()                 // sequence of indices for vertical seam
   public    void removeHorizontalSeam(int[] seam)   // remove horizontal seam from picture
   public    void removeVerticalSeam(int[] seam)     // remove vertical seam from picture
}

Analysis of running time.  Estimate empirically the running times (in seconds) to remove one row and one column from a W-by-H image as a function of W, and H. Use tilde notation to simplify your answer. Answer the relevant questions in the readme.txt file.

Extra credit.

Submission.  Submit SeamCarver.java, and any other files needed by your program (excluding those in stdlib.jar and algs4.jar). Finally, submit a readme.txt file and answer the questions.

This assignment was developed by Josh Hug, Maia Ginsburg, and Kevin Wayne.