Project 6 (Seam Carving) Solution

In this assignment1, you will create a data type called SeamCarving that resizes a W - by-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-by-298 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.









































































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 S e a m C a r v e r




Create a seam carver object based on the given picture , making a



de fe ns iv e copy of picture .



public S e a m C a r v e r ( Picture picture )







Return current picture . public Picture picture ()



Return width of current picture . public int width ()









1Adapted from www.cs.princeton.edu/courses/archive/spring15/cos226/assignments/seamCarving.html.

2The data type may not mutate the Picture argument to the constructor.










1 of 6
CS210 Project 6 (Seam Carving) Swami Iyer













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 h o r i z o n t a l seam . public int [] f i n d H o r i z o n t a l S e a m () {



Return sequence of indices for vertical seam . public int [] f i n d V e r t i c a l S e a m ()



Remove h o r i z o n t a l seam from current picture . public void r e m o v e H o r i z o n t a l S e a m ( int [] seam )



Remove vertical seam from current picture . public void r e m o v e V e r t i c a l S e a m ( 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 2x(x; y) + 2y(x; y), where the square of the x-gradient 2x(x; y) = Rx2(x; y) + G2x(x; y) + Bx2(x; y), and where the central di erences Rx(x; y); Gx(x; y), and Bx(x; y) are the absolute value in di erences of red, green, and blue components between pixel (x + 1; y) and pixel (x 1; y). The square of the y-gradient 2y(x; y) is de ned in an analogous manner. To handle pixels on the borders of the image, calculate energy by de ning 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:































2 of 6
CS210 Project 6 (Seam Carving) Swami Iyer










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
(1; 2) = 22
+ 2042 = 41620; and pixels (1; 1) and (1; 3) for the y-gradient
x










Ry(1; 2) = 255
255 = 0;




Gy(1; 2) = 255
153 = 102;




By(1; 2) = 153
153 = 0;



yielding 2y(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 2x(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 2y(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:

























java P r i n t E n e r g y 6 x5 . png 6 - by -5 image



Printing energy c a l c u l a t e d 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


















3 of 6
CS210 Project 6 (Seam Carving) Swami Iyer










Here is the dual gradient3 of the Mandrill image above.

for pixels in the image where there is a rapid color gradient.




avoids removing such high-energy pixels.







The energy is high (white) The seam-carving technique





































































Problem 2. (Seam Identi cation) 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 di erences:




The weights are on the vertices instead of the edges.




The goal is to nd the shortest path from any of the W pixels in the top row to any of the W pixels in the bottom row.




The digraph is acyclic, where there is a downward edge from pixel (x; y) to pixels (x 1; y + 1), (x; y + 1), and (x + 1; y + 1), assuming that the coordinates are in the prescribed ranges.




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




























3Generated using the ShowEnergy client.






4 of 6
CS210 Project 6 (Seam Carving) Swami Iyer










The corresponding pixel energies are shown below, with a minimum energy vertical seam highlighted in pink. In this case, the method findVerticalSeam() returns the ar-ray {3, 4, 3, 2, 2}.




























$ java
P r i n t S e a m s 6 x5 . png






6 - by -5 image
















H o r i z o n t a l 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























Shown below are the vertical and horizontal seams 4 for the Mandrill image from above.







4Generated using the ShowSeam client.
































































5 of 6
CS210 Project 6 (Seam Carving) Swami Iyer












































































Problem 3. (Seam Removal) The nal step is to implement removeVerticalSeam() to re-




move 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 R e m o v e S e a m s
6 x5 . png 1
1


5 - by -4 image








Printing energy c a l c u l a t e d 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:




The width(), height(), and energy() methods should take constant time in the worst case. All other methods should run in time proportional to W H (or better) in the worst case.




To implement findHorizontalSeam() and removeHorizontalSeam(), transpose the pic-ture and call findVerticalSeam() and removeVerticalSeam(). Don’t forget to transpose the picture back, when needed.




Files to Submit:




SeamCarver.java



report.txt






























6 of 6