Programming Assignment 7: Seam Carving

Frequently Asked Questions

We haven't offered this assignment before, so we don't know what kinds of questions students will have. We will add to the list as needed.

How do I manipulate images in Java? Use our Picture data type (which is part of stdlib.jar) and the Color data type (which is part of the java.awt library). 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. Does this mean I don't have to make a defensive copy of the Picture? Do not mutate the Picture that is passed to the constructor. To make changes to the Picture do a defensive copy first.

Identifying the shortest energy path in a picture looks a lot like the COS126 dynamic programming assignment about genetic sequencing. Can I use that approach? You absolutely can use the dynamic programming approach. Not all 126 students do that assignment so don't worry if you don't understand this. The dynamic programming approach in this case is the same as the shortest paths approach using topological sort.

My program is using recursion to find the shortest energy path. Is this ok? Shortest path algorithms do not use recursion. Using recursion will probably make your code inefficient even if correct. Note that tail recursion can easily be converted to iterative code.

My program seems to be really slow. Any advice? Be sure to calculate energy() once per pixel. Consider deferring any calculations until necessary.

The energy at the border (195,075) is not the maximum value that the energy can have? For example, if I have a (0,0,0) color surrounded by (255,255,255) colors, then I will get 6 * 255^2 = 2 * 195075. If you have a situation like the one you describe, then the energy is 0. The energy at the border is not absolutely maximal. Assigning the same constant to all boundary pixels is what is needed to find the minimal seam. The constant that is given equals the energy of a point on the boundary of a black area and white area.


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

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

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 very easy.

  2. From there, write energy(). Calculating Δx2 and Δy2 are very similar. A private method which can calculate either one will keep your code simple. 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 topologial sort algorithm for computing a shortest path in a DAG. Do not create an EdgeWeightedDigraph. Instead construct a 2d energy array using the energy() method that you have already written. Your algorithm can traverse this matrix treating some select entries as reachable from (x, y) to calculate where the seam is located. To test that your code works, use the client PrintSeams described in the testing section above.

  4. To write findHorizontalSeam(), do a transpose the image and, call findVerticalSeam(). (You will want to transpose the image back either here or later.)

  5. Now implement removeHorizontalSeam() and removeVerticalSeam(). Typically, these methods will be called with the output of findHorizontalSeam() and findVerticalSeam(), respectively, but be sure that they work for any valid seam. To test that your code works, use the client ResizeDemo described in the testing section above.