Homework 2 | CS 61B Fall 2021 Main Course Info Staff Beacon Resources Piazza Navigation Navigation A. Preliminaries B. Lists of Lists C. Array Warm-up D. Seam Carving E. Submission Optional Required Homework 2: Arrays and Lists of Lists Navigation Preliminaries Lists of Lists Array Warm-up Seam Carving Submission A. Preliminaries The introduction video for this assignment is available to you for help, and you should watch it if you have any questions. You can get the skeleton files from the shared repository as usual. git fetch shared
git merge shared/hw2 -m "commit message here" B. Lists of Lists In this section, you will make changes to hw2/lists/Lists.java and hw2/lists/ListsTest.java. We've provided a new class IntListList (in package lists), which consists of a reference to an IntList and a reference to an IntListList. Using this class, we can form lists of lists. Very meta... This should remind you of our arrays of arrays! Complete the naturalRuns method in the file Lists.java, and write a few tests for it in ListsTest.java. While we don't usually provide skeletons in 61B, to hopefully make this homework more manageable we've provided you two skeleton versions: one for an iterative solution, and one for a recursive solution. You only have to do one, and if you go with the recursive solution make sure to fix the method name (see the comments in the code). For test-writing purposes, you may find the IntListList constructor helpful, which takes as input two-dimensional arrays. Don't feel pressured to go too overboard on tests. Two "normal" input and a couple of corner cases per method is likely enough for 61B HW purposes! Write more tests when you think you'll either save time or learn something by writing them. The Utils class provides some handy methods, but you are not required to use the Utils class in any way. C. Array Warm-up Take a look at the two functions corresponding to problems C1 and C2 of this homework in Arrays.java (in package arrays). Fill out ArraysTest.java to test these methods perform as indicated in their comments. Then implement the methods. Remember that some arrays can have zero elements. You may find System.arraycopy useful for these problems, but you are not required to use it. We've again provided a Utils class (which could be helpful), but again you can get along just fine without using it. D. Seam Carving Set aside some time before you start this. There's a solid 15-minute read ahead of you before you're ready to get started on this problem. The ideas aren't too complicated, but I've erred on the side of caution and written a really verbose step-by-step description. Suppose you have an image and want to rescale it in a way that doesn't preserve the aspect ratio, e.g. you have a widescreen movie that you'd like to view on a square screen. Two obvious choices are rescaling and cropping. However, rescaling makes everything look weird, and cropping means you lose the edges of the image. There is an image resizing technique known as seam carving that avoids these problems. In this HW problem you'll implement the tricky part of this algorithm. Before proceeding, watch the first 2 minutes and 30 seconds of this video so you can get a feeling for what the technique can achieve. In this problem, you'll be completing an implementation of a partially completed MatrixUtils class that supports the rescaling of images. We've provided code that does all the messy stuff like reading in image files and so forth. You'll be writing the code that does the actual smart part of the program. Seam carving works as follows. First we start with a W x H color image, which is really just a two-dimensional array of Color objects, where each Color object contains a red, green, and blue value. The image.Rescaler class calculates the "energy" of each pixel and returns the energy of the overall image as a matrix with R=H rows and C=W columns. The energy of a pixel represents the importance of a pixel. Pixels with low energy (e.g. black in a sea of other black pixels) will be considered unimportant, whereas pixels with high energy (e.g. a white dot in a sea of black pixels) will be worth saving. You can think of energy as how much a pixel contrasts with its neighbors: a pixel that highly contrasts with its neighbors has more energy as a pixel that doesn't contrast at all with its neighbors. So a pixel's energy is really just how important that pixel is which is measured by how much it contrasts with its neighbors. By neighbors we mean the pixels surrounding that particular pixel. As an example, consider the silly 4 pixel wide by 6 pixel tall image, shown below (zoomed in): Our code converts the image into its "energy", which depends on the differences between the neighboring pixels. Suppose that a pixel at position $(c, r)$ has an RGB color value $V(c, r)$—a 3-vector of red, green, and blue intensities. Then we'll take its energy to be $$||V(c+1, r) - V(c-1,r)||^2 + ||V(c, r+1) - V(c,r-1)||^2.$$ On the boundaries (where it lacks one or more neighbors), we'll use a color value of $10^6$, and a value of $\infty$ for pixels that are off the image. (We've already written this code, so this is just FYI). The basic idea is that the more similar a pixel is to its neighbors, the lower its energy). For this image, we get: 1000000 1000000 1000000 1000000
1000000 75990 30003 1000000
1000000 30002 103046 1000000
1000000 29515 38273 1000000
1000000 73403 35399 1000000
1000000 1000000 1000000 1000000 Here, pixels with high values are ones we want to keep, and things that have low energy (like the one with energy 29,515) are relatively expendable. Suppose we want to resize this image by making it one row shorter. To do this, we'd find the lowest energy horizontal path from any pixel in the left column to any pixel in the right column--contraining ourselves to only walking between contiguous pixels (see below for a more precise definition). As an example, the minimum energy path for the energy shown is:
1000000 1000000 1000000 *1000000*
*1000000* 75990 *30003* 1000000
1000000 *30002* 103046 1000000
1000000 29515 38273 1000000
1000000 73403 35399 1000000
1000000 1000000 1000000 1000000
We'd then remove all the marked pixels, and we'd have a rescaled image that is only 5x4. It is not obvious, but the resulting rescaling algorithm does a really good job with certain types of images (which you'll be able to experiment with once you're done). We can also use this algorithm to remove columns of images. Walking top to bottom, one minimum energy path would be:
1000000 1000000 1000000 *1000000*
1000000 75990 *30003* 1000000
1000000 *30002* 103046 1000000
1000000 *29515* 38273 1000000
1000000 73403 *35399* 1000000
1000000 1000000 1000000 *1000000*
Let's be a bit more explicit in what it means to find a contiguous path. For a vertical path, imagine that we're walking from the top to the bottom across the image, starting at any point in the top row, with the constraint that we can only walk: Directly down. Diagonally down and to the left one space. Diagonally down and to the right one space. The total energy of the marked path is 1000000 for this first step, then 30003 for the next step, then 30002 for the third step, then 29515, 35399, and finally 1000000 for the final three steps. The total energy of these is six positions is 1000000+30003+30002+29515+35399+1000000=2124919 units of energy. By inspection, you should be able to convince yourself that the path we walked is the minimum among all paths that obey our constraints above. We now define the useful term vertical seam: The vertical seam is the minimum energy contiguous path from any pixel in the top row to any pixel in the bottom row. The seam does not need to be unique. Observe above that since the edge pixels are all energy 1000000, we could have picked any of them. If the example above is not satisfying to you and you insist on a precise definition, we can define it as follows: Given an energy matrix int[][] e, then int[] verticalSeam is an array of length H such that if at the ith index of verticalSeam there is an integer j, this means that we should remove the pixel at row i and column j. Here are more definitions and properties: abs(verticalSeam[i] - verticalSeam[i+1]) <= 1 sum is minimized, where sum is defined as: for (int r = 0; r < R; r += 1) {
int lowestTotalEnergyColumn = verticalSeam[r];
sum += e[r][lowestTotalEnergyColumn];
} Don't feel obligated to fully digest this formal definition. If you can follow the coming example, you're in great shape. Finding such a path seems like it might involve a bunch of trial-and-error, but we can avoid this by accumulating the energy matrix. For example, if we accumulate the energy matrix vertically (up to this point we were discussing horizontal seams, we are now discussing vertical seams), we get:
1000000 1000000 1000000 1000000
2000000 1075990 1030003 2000000
2075990 1060005 1133049 2030003
2060005 1089520 1098278 2133049
2089520 1162923 1124919 2098278
2162923 2124919 2124919 2124919
If double[][] e is the energy matrix, and double[][] am is the vertically accumulated energy matrix, am[i][j] is defined as the minimum total energy needed to reach i, j from any starting position in the top row. Let's work through how we could calculate the accumulated energy matrix. It's a pretty straightforward idea once you get it, but sorry for the moment for the wall of text needed to understand this. First off, the accumulation of the energy matrix is 1000000 for the entire top row, because the cost to reach any top pixel from itself is 1000000. This means that the top row of am is the trivial:
1000000 1000000 1000000 1000000
??????? ??????? ??????? ???????
??????? ??????? ??????? ???????
??????? ??????? ??????? ???????
??????? ??????? ??????? ???????
??????? ??????? ??????? ???????
Let's next consider position [1][1]. You'll see from the filled in copy of int[][] am that am[1][1] (marked in blue in the filled matrix) has value 1075990. To understand where this value came from, consider that there are three ways that you can get to [1][1], namely: Moving down and to the right from [0][0], which has accumulated energy 1000000. Moving directly down from [0][1], which has accumulated energy 1000000. Moving down and to the left from [0][2], which has accumulated energy 1000000. All of these starting locations are equally bad at a whopping 1000000 units of energy, so the total cost to reach [1][1] is given by 1000000 + 75990 (the cost of including the pixel at [1][1] itself). The rest of the second row will be the same story, and we'll end up with the following top two rows:
1000000 1000000 1000000 1000000
2000000 1075990 1030003 2000000
??????? ??????? ??????? ???????
??????? ??????? ??????? ???????
??????? ??????? ??????? ???????
??????? ??????? ??????? ???????
The first entry that is really interesting is [2][0]. There are two ways to get to [2][0], either: Moving directly down from [1][0], which has accumulated energy 2000000. Moving down and to the left from our old friend [1][1], which has accumulated energy 1075990. Obviously it'd be better to have come from [1][1], so we know that the minimum cost to reach [2][0] must be 1075990 + 1000000 (the cost of [2][0] itself). And in fact, by an inductive argument, we know that this is not just the lowest cost to reach [2][0] from its two neighbors, but also from any pixel in the top row (if you are unsatisfied or bored, try to prove that this same way works for all pixels). Try to figure out what [2][1] should be, and then check your answer by highlighting the following blank area after the colon with the mouse: 1060005. If you didn't get this, then the answer is as follows. There are three possible paths: Down and to the right from [1][0], which has accumulated energy 2000000. Down from [1][1], which has accumulated energy 1075990. Down and to the left from [1][2], which has accumulated energy 1030003. Our best choice is to come from [1][2], for a total of 1030003 + 30002 = 1060005. Following this same process, we finally arrive at the accumulated energy matrix:
1000000 1000000 1000000 1000000
2000000 1075990 1030003 2000000
2075990 1060005 1133049 2030003
2060005 1089520 1098278 2133049
2089520 1162923 1124919 2098278
2162923 2124919 2124919 2124919
Once we have the accumulated energy matrix, finding a minimum energy path is trivial (by eye, but trickier in code)! We start by picking the lowest energy position in the bottom row, in this case am[5][1], am[5][2], or am[5][3] are all equally good with cumulative energies of 2124919. We then walk back up the array, taking note of the smallest entry along the way, leading us from 2124919 to 1124919 to 1089520 to 1060005 to 1030003 to 1000000. This technique is an example of dynamic programming, which we'll be revisiting later. If you're curious, dynamic programming is a technique in which we solve a problem by identifying its subproblems and solve them one by one, smallest first, using the answers from small problems to calculate answers to larger ones. In this case, we calculated the accumulated energy of a square by considering these 3 subproblems: the accumulated energy values of the square (1) one row up, (2) one row up and one column right, and (3) one row up and one column left. By starting at the top row and working our way down, once we arrive at a square all of its subproblems are already solved. To find the accumulated energy of the square all we need is an update rule - in our case we add the square's energy with the minimum of its 3 subproblems.It has applications from determining the degree of difference between two texts to performing error correction on a noisy communication line. For this problem, you'll be required to complete two methods in the MatrixUtils class: accumulateVertical: Does exactly the operation described on this page. accumulate: Takes a parameter that determines if we should accumulate vertically or horizontally. See the skeleton file for details. If you want to complete the image resizing program, you'll also add two more optional methods: findVerticalSeam and findSeam. This is not required for credit, but is very emotionally satisfying. If you complete all four methods, you'll be able to use the image.Rescaler class. Try it out on images with big empty spaces (e.g. the provided HJoceanSmall.jpg). Also try it on faces -- it's super creepy and weird. To do this, make sure you're in the hw2 directory (not the image subdirectory) and just run the program as follows: java -ea image.Rescaler [image filename] [num columns to remove] [num rows to remove] or within IntelliJ. E. Submission Optional findVerticalSeam and findSeam are optional. If you complete them, you will be able to run your seam carver code on images. While this is optional, we highly encourage you do this so you can see the power of what you've just coded. If you decide you don't want to do it yourself, you can watch the intro vid to see how it works. Required You should have completed Lists.java, ListsTest.java, MatrixUtils.java, MatrixUtilsTest.java, Arrays.java, ArraysTest.java. To get a full score on the assignment: Your Lists.java must pass 5 out of 8 of our tests Your Arrays.java must pass 5 out of 8 of our tests Your MatrixUtils.java must pass 2 out of 4 of our tests You should have written proper tests in ListsTest.java You should have written proper tests in ArraysTest.java Submit as usual by adding, committing, tagging, and pushing. You could do this like so, from your repo: git add hw2
git commit -m "yay i am done with homework 2"
git tag hw2-0
git push
git push --tags
