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.
A |
B |
C |
D |
E |
F |
G |
H |
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.
5 |
6 |
3 |
8 |
4 |
1 |
6 |
4 |
3 |
2 |
1 |
3 |
8 |
6 |
5 |
2 |
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:
5 |
6 |
3 |
8 |
4 |
1 |
6 |
4 |
3 |
2 |
1 |
3 |
8 |
6 |
5 |
2 |
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.
5 |
6 |
3 |
8 |
9 (above) |
1 |
6 |
4 |
3 |
2 |
1 |
3 |
8 |
6 |
5 |
2 |
Now consider the pixel in the second row and second column, it is a 1. Its neighbors above are 5, 6, and 3:
5 |
6 |
3 |
8 |
9 (above) |
1 |
6 |
4 |
3 |
2 |
1 |
3 |
8 |
6 |
5 |
2 |
The smallest sum is 3 and 1, so the value becomes 4 from 3 above and to the right.
5 |
6 |
3 |
8 |
9 (above) |
4 (above,right) |
6 |
4 |
3 |
2 |
1 |
3 |
8 |
6 |
5 |
2 |
Continuing the row becomes:
5 |
6 |
3 |
8 |
9 (above) |
4 (above,right) |
9 (above) |
7 (above,left) |
3 |
2 |
1 |
3 |
8 |
6 |
5 |
2 |
Repeating with the next row:
5 |
6 |
3 |
8 |
9 (above) |
4 (above,right) |
9 (above) |
7 (above,left) |
7 (above,right) |
6 (above) |
5 (above,left) |
10 (above) |
8 |
6 |
5 |
2 |
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
Your program should include the methods: removeSeam, and insertSeam. The removeSeam and insertSeam methods must run in O(n) time where n is the height of the image in pixels. Therefore, we are notable to use a 2D array to store the Pixels in the grid, so choose a more natural way to represent the grid of Pixels.
In summary, this project asks:
1. Change the program to compress by removing seams instead of columns.
Define seams as a string of pixels from a pixel in the top row and choosing the next pixel by finding the surrounding 3 pixels (down left, down, downright) from the current pixel with the highest blue value all the way down to a pixel in the bottom row of the image.
2. Remove bluest seams or the lowest energy based on choice. The bluest should be highlighted in blue, the lowest energy in red.
3. Create a user interface that allows the user to select how deletion should
happen (lowest energy or bluest). The program then highlights the column and removes it upon user confirmation. The interface allows the user to undo any number of deletions.
Specification
You must submit your work as a ZIP file to Gradescope. This file should:
● Preserve the directory structure covered during the course (i.e., main, test, package)
● The pom.xml with updated dependencies, where applicable.
● Include all of the corresponding Java files that perform the tasks requested above, that is, not just the class containing the main method.
● Comprise the image(s), in PNG format, involved in the project:
○ The original image
○ At least 1 image resulting from applying the bluest seam to the original image.
○ At least 1 image resulting from applying the lowest energy seam to the original image.
● All Java files should be commented on by you.
Assessment Criteria
70 or higher There was evidence of the ability to perform all programming tasks correctly. The demonstration of the methods was excellent, coherent, well documented and clearly explained.