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

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. 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. The LineItem class will represent an individual

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

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of