Assessment Task

For your second project, you will continue work from Project 1 on image compression. You will extend the program to remove vertical seams instead of columns. Vertical seams are a sequence of Pixels that start from the top of the image to the bottom where every Pixel is either directly or diagonally above the next Pixel in the sequence. We want to remove the bluest seam (seam with the largest blue value sum) or the seam with the lowest energy in the image.

The seam with the lowest energy will be the least impactful seam to remove in terms of maintaining image recognizability.

We define energy using the following formula given br(Pixel) as the brightness of the Pixel. The brightness of a Pixel is the average of the RGB values of the color of a given pixel.

Consider pixel E below. E has 8 neighbors. A, B, C, D, F, G, H, and I.

We can then define the horizontal energy and the vertical energy as:

HorizEnergy(E) = (br(A) + 2br(D) + br(G)) − (br(c) + 2br(F) + br(I))

vertEnergy(E) = (br(A) + 2br(B) + br(c)) − (br(G) + 2br(H) + br(I))

Finally, we can define the Energy at E:

Seam Finding:

Consider the table of numbers below as the pixel energies of a 4x4 image that you have computed. Scanning through this one row at a time, we look for the cheapest total energy from the current row to the top of the image.

The first row, 5 6 3 8, has no neighbors above it, so it is the minimum for each location.

Now consider the 4 (bold, shaded) in the table below:

It has 5 and 6 as neighbors above. If we were to sum 4 and 5 we get 9, 4 and 6, 10. Since 9 is smaller that is the new value for the path and we record that it came from 5.

Now consider the pixel in the second row and second column, it is a 1. Its neighbors above are 5, 6, and 3:

The smallest sum is 3 and 1, so the value becomes 4 from 3 above and to the right.

Continuing the row becomes:

Repeating with the next row:

Finally, last row:

Now tracing it backward from 7, we see 3, 4, 5, 7 as the lowest energy seam. These values are the smallest within each row, that is, 3 is the smallest at row 1, 4 is the smallest at row 2, 5 the smallest at row 3 and 7 the smallest at row 4. The resulting seam, in the table below, is the path (top-bottom) following the cells with thick borders.

We are also implementing the ability to reinsert seams in the reverse order that they were removed, so an “undo” button. Therefore, you must keep track of the seams that you removed from the image efficiently and in order and the location to reinsert  the seam’s Pixels in the image grid.

Your program should take the following key inputs:

-    “b” show the bluest seam in the image (highlight blue)

-    “e” show the seam with the lowest energy in the image (highlight red)

-    “d” delete the seam from the image and show the resulting image

-    “u” undo by reinserting the previously deleted seam back into the image