Programming Assignment 7: Seam Carving

Frequently Asked Questions

How do I manipulate images in Java? Use our Picture data type (which is part of algs4.jar) and Java's java.awt.Color data type. Here is some more information about the Color and Picture data types. and are example clients that use the Color and Picture data types, respectively.

I noticed that the Picture API has a method to change the origin (0, 0) from the upper left to the lower left. Can I assume (0, 0) is the upper left pixel? Yes.

The data type is mutable. Must I still make a defensive copy of the Picture? Yes. Probably. A data type should not have side effects (unless they are specified in the API). Also, your data type should still behave properly even if the client mutates the picture object passed to the constructor or returned from the picture() method.

Why does the energy function wrap around the image? This is one of several reasonable conventions. Here are a few advantages of defining it in this way:

Why can't seams wrap around the image (i.e., why not treat the image as a torus when computing seams)? While it would be consistent with the way that we define the energy of a pixel, it often produces undesirable visual artifacts.

Identifying the shortest energy path in a picture looks a lot like the COS 126 dynamic programming assignment about genetic sequencing. Can I use that approach? You are welcome to use a dynamic programming approach; however, in this case, it is equivalent to the topological sort algorithm for finding shortest paths in DAGs.

My program is using recursion to find the shortest energy path. Is this okay? You should not need recursion. Note that the underlying DAG has such special structure that you don't need to compute its topological order explicitly.

My program seems to be really slow. Any advice? We strongly encourage you to implement these optimizations.

What values of W and H should I use when timing? The value of W and H are not as significant as the resulting time. Be sure that the resulting time is greater than 1 second for all your data.

How do I determine the relationship between W and H? Analyze the code. Use the feedback you got on the Percolation assignment to help you.


Clients.  You may use the following client programs to test and debug your code.

Sample input files.   The directory seamCarving contains these client programs above along with some sample image files. You can also use your own image files for testing and entertainment.

Your code should work no matter the order or how many times the methods are called. A good test would be to find and remove a seam, but then make sure that finding and removing another seam also works. Try all combinations of this with horizontal and vertical seams.

Possible Progress Steps

These are purely suggestions for how you might make progress. You do not have to follow these steps.

  1. Start by writing the constructor as well as picture(), width(), and height(). These should be easy. Be sure to defensively copy the Picture before returning to the client. Why?

  2. Next, write energy(). Calculating Δx2 and Δy2 are very similar. Consider a private helper method to avoid code duplication. To test that your code works, use the client PrintEnergy described in the testing section above.

  3. To write findVerticalSeam(), you will want to first make sure you understand the topological sort algorithm for computing a shortest path in a DAG. It is recommended that you do not create an EdgeWeightedDigraph, as the resulting code will be not only slower, but also harder to write. Instead, construct a W-by-H energy matrix using the energy() method that you have already written. Think about which data structures (in addition to the 2D energy matrix) that you will need to implement the shortest path algorithm. To test, use the client PrintSeams described in the testing section above.

  4. Now implement removeVerticalSeam(). Typically, it will be called with the output of findVerticalSeam(), but be sure that it works for any valid seam. To test, use the client ResizeDemo described in the testing section above.

  5. To implement findHorizontalSeam() and removeHorizontalSeam(), transpose the picture and call findVerticalSeam() and removeVerticalSeam(). Don't forget to transpose the picture back, when needed.

A video is provided for those wishing additional assistance. Warning: the video was made in early 2014 and is somewhat out of date. For example the API has changed.