Seam Carving

• Checklist
• Project
• Submit
• Leaderboard

Frequently Asked Questions (Image Processing)

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 from COS 126. Note that pixel (col, row) is the pixel in specified column and row, and pixel (0, 0) is the one in the top-left corner.

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).

Which seam should I return if there are multiple seams of minimum energy? The assignment specification does not say, so you are free to return any such seam.

The SeamCarver data type is mutable. Must I still defensively copy of the Picture objects? A data type should have no side effects (unless they are specified in the API). It should also behave 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 (e.g., as opposed to defining the energy of every border pixel to equal some large constant).

• 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.

Which algorithm should I use to find a shortest energy path? That is up to you.

What does it mean to take the transpose of an image? Transposing a picture (or matrix) means interchanging the row and column indices. The following two pictures are transposes of one another.

                    

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 shortest-paths algorithm directly on the pixels. This will involve re-implementing the shortest-paths algorithm.

• 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 values directly from the 2D array (instead of recomputing them 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).

• Due to caching effects, 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.

Which images should I use for timing? The simplest approach is to generate random W-by-H pictures by calling SCUtility.randomPicture(). While not representative of real-world images, random images should suffice for timing. Do not use degenerate images (e.g., all black pixels), as that might lead to better-than-usual performance. If your program is so fast that it takes an enormous image to consume 30 seconds worth of CPU time, you can use the -Xint option to slow it down.

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 to update only the energy values that change after removing a seam, you should not need to maintain the energy values in an instance variable. Similarly, any 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.   The project folder seam.zip contains these client programs above along with some sample image files. We encourage you to use your own image files for testing and entertainment.

Unit tests. Your code should work regardless of how many times each method is called and in which order. A good test is to find and remove a seam, but then make sure that finding and removing another seam also works. Try all combinations of this with both 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. Write the constructor, picture(), width(), and height(). Think about which instance variables you will need to support the instance methods. Once you have determined the underlying representation, these should be easy.

2. Write energy(). Calculating \(\Delta_x^2\) and \(\Delta_y^2\) are very similar. Can you use a private helper method to avoid code duplication? To test, use the client PrintEnergy.java, described in the testing section above.

3. Before you write findVerticalSeam(), make sure you understand how to compute shortest paths in a digraph (e.g, using Dijkstra’s algorithm, the topological sort algorithm, Bellman–Ford algorithm, or dynamic programming).

   • We recommended that you represent the digraph implicitly (e.g., as a W-by-H energy matrix) instead of explicitly (as an EdgeWeightedDigraph). The resulting code will be substantially faster and use substantially less memory.

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

   • For testing, use the client PrintSeams.java described in the testing section above.

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

5. To implement findHorizontalSeam() and removeHorizontalSeam(), transpose the picture before calling findVerticalSeam() and removeVerticalSeam(), respectively. Don’t forget to transpose the picture back.