Although the underlying algorithm is simple and elegant, it was not discovered until 2007. Now, it is now a core feature in Adobe Photoshop and other computer graphics applications.
In this assignment, you will create a data type that resizes a W-by-H image using the seam-carving technique. Finding and removing a seam involves three parts and a tiny bit of notation:
algs4.jar
.
(0, 0) | (1, 0) | (2, 0) |
(0, 1) | (1, 1) | (2, 1) |
(0, 2) | (1, 2) | (2, 2) |
(0, 3) | (1, 3) | (2, 3) |
Warning: this is the opposite of the standard mathematical notation used in linear algebra, where (i, j) refers to row i and column j and (0, 0) is at the lower-left corner.
We also assume that the color of each pixel is represented in RGB space, using three integers between 0 and 255. This is consistent with the java.awt.Color data type.
The energy is high (white) for pixels in the image where there is a rapid color gradient (such as the boundary between the sea and sky and the boundary between the surfing Josh Hug on the left and the ocean behind him). The seam-carving technique avoids removing such high-energy pixels.
Seams cannot wrap around the image (e.g., a vertical seam cannot cross from the leftmost column of the image to the rightmost column).
The SeamCarver API. Your task is to implement the following mutable data type:
public class SeamCarver { // create a seam carver object based on the given picture public SeamCarver(Picture picture) // current picture public Picture picture() // width of current picture public int width() // height of current picture public int height() // energy of pixel at column x and row y public double energy(int x, int y) // sequence of indices for horizontal seam public int[] findHorizontalSeam() // sequence of indices for vertical seam public int[] findVerticalSeam() // remove horizontal seam from current picture public void removeHorizontalSeam(int[] seam) // remove vertical seam from current picture public void removeVerticalSeam(int[] seam) // unit testing (required) public static void main(String[] args) }
Corner cases. Your code must throw an exception when a constructor or method is called with an invalid argument, as documented below:
java.lang.IllegalArgumentException
if energy()
is called with either an x-coordinate
or y-coordinate outside its prescribed range.
java.lang.IllegalArgumentException
if the constructor,
removeVerticalSeam()
, or removeHorizontalSeam()
is called with a null argument.
java.lang.IllegalArgumentException
if either removeVerticalSeam()
or
removeHorizontalSeam()
is called with an array of the wrong length
or if the array is not a valid seam (either an entry is outside the height/width bounds
or two adjacent entries differ by more than 1).
java.lang.IllegalArgumentException
if either
removeVerticalSeam()
or
removeHorizontalSeam()
is called when the width or height of the current picture is 1,
respectively.
Constructor.
The data type may not mutate the Picture
argument to the constructor.
Computing the energy of a pixel. You will use the dual-gradient energy function: The energy of pixel \((x, y)\) is \(\sqrt{\Delta_x^2(x, y) + \Delta_y^2(x, y)}\), where the square of the x-gradient \(\Delta_x^2(x, y) = R_x(x, y)^2 + G_x(x, y)^2 + B_x(x, y)^2\), and where the central differences \(R_x(x, y)\), \(G_x(x, y)\), and \(B_x(x, y)\) are the differences in the red, green, and blue components between pixel (x + 1, y) and pixel (x − 1, y), respectively. The square of the y-gradient \(\Delta_y^2(x, y)\) is defined in an analogous manner. To handle pixels on the borders of the image, calculate energy by defining the leftmost and rightmost columns as adjacent and the topmost and bottommost rows as adjacent. For example, to compute the energy of a pixel (0, y) in the leftmost column, use its right neighbor (1, y) and its “left” neighbor (W − 1, y).
As an example, consider the following 3-by-4 image (supplied as 3x4.png):
R_{x}(1, 2) = 255 − 255 = 0,yielding Δ_{x}^{2}(1, 2) = 2^{2} + 204^{2} = 41620;
G_{x}(1, 2) = 205 − 203 = 2,
B_{x}(1, 2) = 255 − 51 = 204,
and pixels (1, 1) and (1, 3) for the y-gradient
R_{y}(1, 2) = 255 − 255 = 0,yielding Δ_{y}^{2}(1, 2) = 102^{2} = 10404.
G_{y}(1, 2) = 255 − 153 = 102,
B_{y}(1, 2) = 153 − 153 = 0,
Thus, the energy of pixel (1, 2) is \(\sqrt{41620 + 10404} = \sqrt{52024}\). Similarly, the energy of pixel (1, 1) is \(\sqrt{204^2 + 103^2}= \sqrt{52225}\).
R_{x}(1, 0) = 255 − 255 = 0,yielding Δ_{x}^{2}(1, 0) = 204^{2} = 41616;
G_{x}(1, 0) = 101 − 101 = 0,
B_{x}(1, 0) = 255 − 51 = 204,
and pixels (1, 3) and (1, 1) for the y-gradient
R_{y}(1, 0) = 255 − 255 = 0,yielding Δ_{y}^{2}(1, 0) = 102^{2} = 10404.
G_{y}(1, 0) = 255 − 153 = 102,
B_{y}(1, 0) = 153 − 153 = 0,
Thus, the energy of pixel (1, 0) is \(\sqrt{41616 + 10404} = \sqrt{52020}\).
Finding a vertical seam.
The findVerticalSeam()
method returns an array of length H
such that entry y is the column number of the pixel to
be removed from row y of the image.
For example, the dual-gradient energies of a 6-by-5 image
(supplied as 6x5.png)
are shown in the table below.
The minimum energy vertical seam is highlighted in blue.
In this case, the method findVerticalSeam()
returns the array { 3, 4, 3, 2, 2 }
because the pixels in the minimum energy vertical seam are
(3, 0),
(4, 1),
(3, 2),
(2, 3), and
(2, 4).
Finding a horizontal seam.
The behavior of findHorizontalSeam()
is
analogous to that of findVerticalSeam()
except that it returns
an array of length W such that entry x is the row number of
the pixel to be removed from column x of the image.
For the 6-by-5 image, the method findHorizontalSeam()
returns the array { 2, 2, 1, 2, 1, 2 }
because the pixels in the minimum energy horizontal seam are
(0, 2),
(1, 2),
(2, 1),
(3, 2),
(4, 1), and
(5, 2).
Unit testing.
Your main()
method must call each public constructor and method directly and
help verify that they work as prescribed (e.g., by printing results to standard output).
Performance requirements. Make it fast.
Other requirements. Finding the shortest energy path must be done using Dijkstra's shortest paths algorithm. For the leaderboard, you may use any shortest paths algorithm of your choice.
Analysis of running time. Estimate empirically the running times (in seconds) to remove one row and one column from a W-by-H image as a function of W, and H. Use tilde notation to simplify your answer.
Submission.
Submit SeamCarver.java
, and any other files needed by your program
(excluding those in algs4.jar
).
You may not call any library functions other than those in java.lang
,
java.util
, java.awt.Color
, and algs4.jar
.
Finally, submit a
readme.txt file and answer the questions.
Grading.
file points finding seams 14 removing seams 10 other 10 readme.txt
6 40
Reminder: You can lose up to 4 points for poor style
and up to 4 points for inadequate unit testing.