Project 6 (Seam Carving) Solution

$30.00

Description

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 6×5.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:

  1. SeamCarver.java

  1. report.txt

6 of 6


error: Content is protected !!