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

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Seam Carver

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 505-by-287 pixel image; below right is the result after removing 150 vertical seams, resulting in a 30% narrower image. Unlike standard content-agnostic resizing techniques (such as cropping and scaling), seam carving preserves the most interest 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. 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 WW-by-HH image using the seam-carving technique. Finding and removing a seam involves three parts and a tiny bit of notation.

Notation. In image processing, pixel (x, y)(x,y) refers to the pixel in column x and row y, with pixel (0, 0)(0,0) at the upper-left corner and pixel (W - 1, H - 1)(W−1,H−1) at the lower-right corner. This is consistent with the Picture data type that we use in this course.

A 3-by-4 image.

 

(0, 0)(0,0)	(1, 0)(1,0)	(2, 0)(2,0)
(0, 1)(0,1)	(1, 1)(1,1)	(2, 1)(2,1)
(0, 2)(0,2)	(1, 2)(1,2)	(2, 2)(2,2)
(0, 3)(0,3)	(1, 3)(1,3)	(2, 3)(2,3)

 

Warning

 

This is the opposite of the standard mathematical notation used in linear algebra, where (i, j)(i,j) refers to row ii and column jj and (0, 0)(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 Color data type.

 

1. Energy calculation. The first step is to calculate the energyof 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 step). In this assignment, you will use the dual-gradient energy function, which is described below. Here is the dual-gradient energy function of the surfing image above:

 

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.

Implement SeamCarver.energy.

2. Seam identification. The next step is to find a vertical seam of minimum total energy. (Finding a horizontal seam is analogous.) This is similar to the classic shortest path problem in an edge-weighted digraph, but there are three important differences:

 

• Each edge weight is based on a vertex (pixel) rather than the edge itself.

 

• The goal is to find the shortest path from any of the WWpixels in the top row to any of the WWpixels in the bottom row.

 

• The digraph is acyclic, where there is a downward edge from pixel (x, y)(x,y)to pixels (x - 1, y + 1)(x−1,y+1), (x, y + 1)(x,y+1), and (x + 1, y + 1)(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).

 

Implement AStarSeamCarver.findHorizontalSeam and AStarSeamCarver.findVerticalSeam.

 

3. Seam removal. The final step is remove from the image all of the pixels along the vertical or horizontal seam. This has already been implemented for you as default methods from the SeamCarver

 

Dual-Gradient Energy Function

 

mathrm{energy}(x, y) = sqrt{nabla_x^2(x, y) + nabla_y^2(x, y)}energy(x,y)=∇x2 (x,y)+∇y2 (x,y)

where the square of the x-gradient nabla_x^2(x, y) = R_x(x, y)^2 + G_x(x, y)^2 + B_x(x, y)^2∇x2 (x,y)=Rx (x,y)2+Gx (x,y)2+Bx (x,y)2, and where the central differences R_x(x, y)Rx (x,y), G_x(x, y)Gx (x,y), and B_x(x, y)Bx (x,y) are the absolute value in differences of red, green, and blue components between pixel (x + 1, y)(x+1,y) and pixel (x - 1, y)(x−1,y). The square of the y-gradient nabla_y^2(x, y)∇y2 (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)(0,y) in the leftmost column, use its right neighbor (1, y)(1,y) and its “left” neighbor (W - 1, y)(W−1,y).

 

As an example, consider the 3-by-4 image with RGB values (each component is an integer between 0 and 255) as shown in the table below. (This is the 3x4.png image in your data/images folder.)

EXAMPLE 1

The energy of the non-border pixel (1, 2)(1,2) is calculated from pixels (0, 2)(0,2) and (2, 2)(2,2) for the x-gradient

R_x(1, 2) = 255 - 255 = 0Rx (1,2)=255−255=0
G_x(1, 2) = 205 - 203 = 2Gx (1,2)=205−203=2
B_x(1, 2) = 255 - 51 = 204Bx (1,2)=255−51=204

yielding nabla_x^2(1, 2) = 2^2 + 204^2 = 41620∇x2 (1,2)=2

Related Questions

. The fundamental operations of create, read, update, and delete (CRUD) in either Python or Java

CS 340 Milestone One Guidelines and Rubric  Overview: For this assignment, you will implement the fundamental operations of create, read, update,

. Develop a program to emulate a purchase transaction at a retail store. This  program will have two classes, a LineItem class and a Transaction class

Retail Transaction Programming Project  Project Requirements:  Develop a program to emulate a purchase transaction at a retail store. This

. The following program contains five errors. Identify the errors and fix them

7COM1028   Secure Systems Programming   Referral Coursework: Secure

. Accepts the following from a user: Item Name Item Quantity Item Price Allows the user to create a file to store the sales receipt contents

Create a GUI program that:Accepts the following from a user:Item NameItem QuantityItem PriceAllows the user to create a file to store the sales receip

. The final project will encompass developing a web service using a software stack and implementing an industry-standard interface. Regardless of whether you choose to pursue application development goals as a pure developer or as a software engineer

CS 340 Final Project Guidelines and Rubric  Overview The final project will encompass developing a web service using a software stack and impleme