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).
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:
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? Dijkstra's shortest paths algorithm. You may use any other algorithm if you submit for the leaderboard.
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.
EdgeWeightedDigraph
.
Instead, execute the shortest-paths algorithm directly on the pixels.
This will involve re-implementing the shortest-paths algorithm.
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).
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).
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 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.
Clients. You may use the following client programs to test and debug your code.
printseams.txt
file
(such as 5x6.printseams.txt),
so you can compare your results to the correct solution.
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.
These are purely suggestions for how you might make progress. You do not have to follow these steps.
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.
energy()
.
Calculating Δx2 and Δy2
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.
findVerticalSeam()
, make sure you
understand how to compute shortest paths in a digraph (using Dijkstra’s algorithm).
EdgeWeightedDigraph
).
The resulting code will be substantially faster and use substantially less memory.
distTo[]
and edgeTo[]
arrays.
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.
findHorizontalSeam()
and removeHorizontalSeam()
,
transpose the picture before calling findVerticalSeam()
and
removeVerticalSeam()
, respectively.
Don’t forget to transpose the picture back.