Frequently Asked Questions (General)

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

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 (and you should not call this method).

Frequently Asked Questions (SeamCarver)

Must the arguments to removeHorizontalSeam() and removeVerticalSeam() be minimum energy seams? No. Each method should work for any valid seam (and throw an exception for any invalid one).

The SeamCarver data type is mutable. Must I still defensively copy of the Picture objects? A data type should not have side effects (unless they are specified in the API). It should behave properly as prescribed even if the client mutates the Picture object passed to the constructor or returned from the picture() method. As a result, you might need to make defensive copies of any Picture objects that you either take as input or return as output.

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:

• If the color of the pixels on one side of the picture are the same as on the opposite side, then these pixels probably represent the background (and a less interesting feature of the image).

• It reduces the likelihood of getting ties when finding the minimum energy seam, say, as opposed to defining the energy of every border pixel to equal some large number.

• It reduces the number of corner cases.

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.

Can I use dynamic programming? Yes, though, in this context, dynamic programming is equivalent to the topological sort algorithm for finding shortest paths in DAGs. If you take a more advanced algorithms course (such as COS 423), you’ll learn about dynamic programming in great detail.

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 recommend that you implement the first four of these optimizations. The last one is intended to help you improve your rank in the leaderboard.

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

• When finding a seam, call energy() at most once per pixel. For example, you can save the energies in a local variable energy[][] and access the information directly from the 2D array (instead of recomputing from scratch).

• Avoid redundant calls to the get() method in Picture. For example, to access the red, green, and blue components of a pixel, call get() only once (and not three times).

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

• Creating Color objects can be a bottleneck. Each call to the get() method in Picture creates a new Color object. You can avoid this overhead by using the getRGB() method in Picture, which returns the color, encoded as a 32-bit int. The companion setRGB() method sets the color of a given pixel using a 32-bit int to encode the color.

How do I determine the running time as a function of W and H? Analyze the code and formulate a hypothesis. Confirm your hypothesis with empirical evidence, as on the percolation assignment.

Which values of W and H should I use when timing? Choose W and H so that the resulting running time exceeds 0.5 seconds for all of your experimental points. You may do multiple trials for the same values of W and H to reach 0.5 seconds.

How much memory can my SeamCarver object use as a function of W and H? A Picture objects uses ~ 4W H bytes of memory—a single 32-bit int per pixel. Unless you are optimizing your program by updating only the energy values that change after removing a seam, you should not need to maintain the energy values in an instance variable. Similarly, the distTo[][] and edgeTo[][] arrays should be local variables, not instance variables. For reference, a Color object consumes 48 bytes of memory.

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 values of the image whose name is specified as a command-line argument.

• ShowEnergy.java computes and draws the energy of the image whose name is specified as a command-line argument.

• ShowSeams.java computes the horizontal seam, vertical seam, and energy of the image whose name is specified as a command-line argument. It draws the horizontal and vertical seams over the energy.

• PrintSeams.java computes the horizontal seam, vertical seam, and energy of the image whose name is specified as a command-line argument. It prints square braces around the energies of the horizontal and vertical seams. 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 the image filename, r, and s, where r is the number of columns and s 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 some of the above clients.

Sample input files.   Download seam.zip 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, picture(), width(), and height(). Think about which instance variables you will need to support the instance methods. Once you have determined the representation, these should be easy.

2. Next, write energy(). Calculating Δ_x² and Δ_y² are very similar. Use a private helper method to avoid code duplication. To test, use the client PrintEnergy.java, fescribed 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.

   • We recommended that you represent the digraph implicitly, rather than explicitly. That is, do not create an EdgeWeightedDigraph. 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.

   • The topological sort algorithm requires that you identify a topological order of the pixels. You should be able to identify such an order from the property of the digraph, without running depth-first search.

   • Think about which data structures (in addition to the W-by-H energy matrix) that you will need to implement the topological sort algorithm, e.g, to play the roles of the distTo[] and edgeTo[] arrays.

   • To test, use the client PrintSeams.java 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.java, 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.