Programming Assignment 7: Seam Carving

Frequently Asked Questions

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? No, you should still make a defensive copy of the picture that is passed to the constructor because your data type should not have any side effects (unless they are specified in the API).

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 topologial sort algorithm for finding shortest paths in DAGs.

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

My program seems to be really slow. Any advice? There are numerous opportunities for optimization.

• Call energy() only once per pixel.

• Consider deferring any calculations until necessary.

• Don't use an explicit EdgeWeightedDigraph. Instead, execute the topological sort algorithm directly on the pixels.

• The order in which you traverse the pixels (row major order vs. column major order) can make a big difference.

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 imagesnot 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 easy. Be sure to defensively copy the Picture before returning to the client. Why?

2. Next, 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. 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 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. 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 that your code works, 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.