# Project 6 (Seam Carving) Solution

$30.00 Category: ## 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 () 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 !!