How do I manipulate images in Java?
Use our Picture
data type (which is part of
and Java’s java.awt.Color data
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).
data type is mutable. Must I still defensively copy of the
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
Picture object passed to the constructor or returned from the
As a result, you might need to make defensive copies of any
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:
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? No, use a MinPQ. 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. Instead use the idea of Dijkstra's algorithm by using a MinPQ.
My program seems to be really slow. Any advice? We recommend that you implement the first four of these optimizations. The fourth one is intended to help you improve your rank in the leaderboard.
EdgeWeightedDigraph. Instead, execute with a MinPQ, as Dijkstra's algorithm does, directly on the pixels. You will know you have found the best solution the first time you delete a pixel (or energy value) from the PQ that is on the other edge.
energy()at most once per pixel. For example, you can save the energies in a local variable
energyand access the information directly from the 2D array (instead of recomputing from scratch).
Picture. For example, to access the red, green, and blue components of a pixel, call
get()only once (and not three times).
Colorobjects can be a bottleneck. Each call to the
Picturecreates a new
Colorobject. You can avoid this overhead by using the
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
intto 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
Picture objects uses ~ 4W H bytes of memory—a single 32-bit
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.
edgeTo arrays should be local variables,
not instance variables.
For reference, a
Color object consumes 48 bytes of memory.
Clients. You may use the following client programs to test and debug your code.
printseams.txtfile (such as 5x6.printseams.txt), so you can compare your results to the correct solution.
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.
These are purely suggestions for how you might make progress. You do not have to follow these steps.
height(). Think about which instance variables you will need to support the instance methods. Once you have determined the representation, these should be easy.
energy(). Calculating Δx2 and Δy2 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.
findVerticalSeam(), you will want to first make sure you understand Dijkstra's algorithm for computing a shortest path in a DAG. DO NOT create a graph!
EdgeWeightedDigraph. The resulting code will not only be slower, but also harder to write. Instead, construct a W-by-H energy matrix using the
energy()method that you have already written.
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.
removeHorizontalSeam(), transpose the picture and call
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 out of date. For example the API has changed, the topological sort algorithm (which you cannot use) is explained, and seams can wrap around the edges (which is not allowed).