In this assignment1, you will create a data type called SeamCarving that resizes a Wby-H image using the seam-carving technique. Seam carving is a content-aware image resizing technique where the image is reduced in size by one pixel of height (or width) at a time. A vertical seam in an image is a path of pixels connected from the top to the bottom with one pixel in each row; a horizontal seam is a path of pixels connected from the left to the right with one pixel in each column. Below left is the original 298-by298 pixel image; below right is the result after removing 50 vertical and horizontal seams. Unlike standard content-agnostic resizing techniques (such as cropping and scaling), seam carving preserves the most interesting features (aspect ratio, set of objects present, etc.) of the image. See image.
Although the underlying algorithm is simple and elegant, it was not discovered until 2007 by Shai Avidan and Ariel Shamir. Now, it is a core feature in many computer graphics applications. Your task is to implement a mutable data type SeamCarver, with the following API2:
public class SeamCarver
// Create a seam carver object based on the given picture , making a
// defensive copy of picture.
public SeamCarver(Picture picture)
// Return current picture.
public Picture picture()
// Return width of current picture.
public int width()
// Return height of current picture.
public int height()
// Return energy of pixel at column x and row y.
public double energy(int x, int y)
// Return sequence of indices for horizontal seam.
public int[] findHorizontalSeam()
// Return 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)
Finding and removing a seam involves three parts and a tiny bit of notation. In image processing, pixel (x,y) refers to the pixel in column x and row y, with pixel (0,0) at the upper-left corner and pixel (W 1,H 1) at the lower-right corner. This is consistent with the Picture data type in stdlib.jar. Note that 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.
Problem 1. (Energy Calculation) The rst step is to implement the energy() method to calculate the energy of a pixel, which is a measure of its importance the higher the energy, the less likely that the pixel will be included as part of a seam (as you will see in the next problem). To compute the energy of a pixel, use the dual-gradient energy function. The energy of pixel (x,y) is 2 x(x,y) + 2 y(x,y), where the square of the xgradient 2 x(x,y) = R2 x(x,y) + G2 x(x,y) + B2 x(x,y), and where the central dierences Rx(x,y),Gx(x,y), and Bx(x,y) are the absolute value in dierences of red, green, and blue components between pixel (x + 1,y) and pixel (x 1,y). The square of the ygradient 2 y(x,y) is dened in an analogous manner. To handle pixels on the borders of the image, calculate energy by dening 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).
Consider the 3-by-4 image with RGB values (each component is an integer between 0 and 255) as shown in the table below: See image.
Non-border pixel example. The energy of pixel (1,2) is calculated from pixels (0,2) and (2,2) for the x-gradient:
Rx(1,2) = 255−255 = 0,
Gx(1,2) = 205−203 = 2,
Bx(1,2) = 255−51 = 204,
yielding 2 x(1,2) = 22 +2042 = 41620; and pixels (1,1) and (1,3) for the y-gradient
Ry(1,2) = 255−255 = 0,
Gy(1,2) = 255−153 = 102,
By(1,2) = 153−153 = 0,
yielding 2 y(1,2) = 1022 = 10404. Thus, the energy of pixel (1,2) is 41620+10404 = 52024. Similarly, the energy of pixel (1,1) is 2042 + 1032 = 52225.
Border pixel example. The energy of the border pixel (1,0) is calculated by using pixels (0,0) and (2,0) for the x-gradient
Rx(1,0) = 255255 = 0,
Gx(1,0) = 101101 = 0,
Bx(1,0) = 25551 = 204,
yielding 2 x(1,0) = 2042 = 41616; and pixels (1,3) and (1,1) for the y-gradient
Ry(1,0) = 255255 = 0,
Gy(1,0) = 255153 = 102,
By(1,0) = 153153 = 0,
yielding 2 y(1,2) = 1022 = 10404. Thus, the energy of pixel (1,2) is 41616+10404 = 52020.
The energies for all the pixels of the above 3-by-4 image are show below: See image.
$ java PrintEnergy 6x5.png
6-by-5 image
Printing energy calculated for each pixel.
57685 50893 91370 25418 33055 37246
15421 56334 22808 54796 11641 25496
12344 19236 52030 17708 44735 20663
17074 23678 30279 80663 37831 45595
32337 30796 4909 73334 40613 36556
Here is the dual gradient3 of the Mandrill image above. The energy is high (white) for pixels in the image where there is a rapid color gradient. The seam-carving technique avoids removing such high-energy pixels. See image.
Problem 2. (Seam Identication) The next step is to implement findVerticalSeam() to nd a vertical seam of minimum total energy implementing findHorizontalSeam() to nd a horizontal seam is analogous. This is similar to the classic shortest path problem in an edge-weighted digraph, but there are three important dierences:
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 findVerticalSeam() method returns an array of length H such that entry i is the column number of the pixel to be removed from row i of the image. For example, consider the 6-by-5 image below (supplied as 6x5.png). See image.
The corresponding pixel energies are shown below, with a minimum energy vertical seam highlighted in pink. In this case, the method findVerticalSeam() returns the array {3, 4, 3, 2, 2}. See image.
$ java PrintSeams 6x5.png
6-by-5 image
Horizontal seam:
57685 50893 91370 25418 33055 37246
15421 56334 22808* 54796 11641* 25496
12344* 19236* 52030 17708* 44735 20663*
17074 23678 30279 80663 37831 45595
32337 30796 4909 73334 40613 36556
Total energy = 104400
Vertical seam:
57685 50893 91370 25418* 33055 37246
15421 56334 22808 54796 11641* 25496
12344 19236 52030 17708* 44735 20663
17074 23678 30279* 80663 37831 45595
32337 30796 4909* 73334 40613 36556
Total energy = 89955
See figure: See image.
Problem 3. (Seam Removal) The nal step is to implement removeVerticalSeam() to remove from the image all of the pixels along the vertical seam implementing removeHorizontalSeam() to remove from the image all of the pixels along the horizontal seam is analogous.
$ java RemoveSeams 6x5.png 1 1
5-by-4 image
Printing energy calculated for each pixel.
57685 50893 49196 45397 37246
18803 33246 9172 17549 33926
8192 58360 11431 37831 42155
32337 29222 26170 40613 36556
Implementation Details: