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. Luminance.java and Grayscale.java 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.

Testing

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

• PrintEnergy.java computes and prints a table of the energy of an image with filename provided on the command line.

• ShowEnergy.java computes and draws the energy of an image with filename provided on the command line.

• ShowSeams.java computes the horizontal seam, vertical seam, and energy of the image with filename provided on the command line. Draws the horizontal and vertical seams over the energy.

• PrintSeams.java computes the horizontal seam, vertical seam, and energy of the image with filename provided on the command line. Prints the horizontal and vertical seams as annotations to the energy. Many of the small input files provided also have a printseams.txt file (such as 5x6.printseams.txt), so you can compare your results to the correct solution.

• ResizeDemo.java uses your seam removal methods to resize the image. The command line arguments are filename, W and H where W is the number of columns and H is the number rows to remove from the image specified. This file works best with real images, not small test files.

• SCUtility.java is a utility program used by most of the above clients.

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 Δ_x² and Δ_y² 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.