Homework 2: Arrays and Lists of Lists

## A. Preliminaries

You can get the skeleton files from the shared repository as usual.

## B. Lists of Lists

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 following Java function so that it performs as indicated in its comment. The files IntList.java and IntListList.java in the template contain the declarations of the classes IntList and IntListList. Put your answers in a file called Lists.java, for which we've also provided a template.

/* B. */
/** Return the list of lists formed by breaking up L into "natural runs":
*  that is, maximal strictly ascending sublists, in the same order as
*  the original.  For example, if L is (1, 3, 7, 5, 4, 6, 9, 10, 10, 11),
*  then result is the four-item list ((1, 3, 7), (5), (4, 6, 9, 10),
*  (10, 11)).
*  Destructive: creates no new IntList items, and may modify the
*  original list pointed to by L. */

static IntListList naturalRuns(IntList L) {
/* *Replace this body with the solution. */
return null;
}

For test-writing purposes, you may find the IntListList constructor helpful, which takes as input two-dimensional arrays.

You'll also write a similar naturalRuns method in the next part with arrays. You may find it useful to look at this method when completing the next part.

Also don't 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

Complete the following Java functions (in package arrays) so that they perform as indicated in their comments. Remember that some arrays can have zero elements. Put your answers to this problem (all parts) in a file named Arrays.java, for which we've provided a template.

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.

/* C1. */
/** Returns a new array consisting of the elements of A followed by the
*  the elements of B. */
static int[] catenate(int[] A, int[] B) {
/* *Replace this body with the solution. */
return null;
}

/* C2. */
/** Returns the array formed by removing LEN items from A,
*  beginning with item #START. */
static int[] remove(int[] A, int start, int len) {
/* *Replace this body with the solution. */
return null;
}

/* C3. */
/** Returns the array of arrays formed by breaking up A into
*  maximal ascending lists, without reordering.
*  For example, if A is {1, 3, 7, 5, 4, 6, 9, 10}, then
*  return the three-element array
*      { {1, 3, 7}, {5}, {4, 6, 9, 10} }. */
static int[][] naturalRuns(int[] A) {
...
}

You may find the subarray command in the Utils class useful, though you are not required to use the Utils class in your solution. For naturalRuns(int[] A), the approaches one might decide between use recursion and iteration. Using iteration might be more intuitive to you, but the recursive solution is more elegant and challenging. We encourage you to try both approaches but, of course, you are only required to use one of these.

## 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 (2) 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 add two methods to 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. Even if you cannot do so this week because of the project, feel free to come back later in the semester and finish this.

###### Required

You should have completed Lists.java, ListsTest.java, MatrixUtils.java, MatrixUtilsTest.java, Arrays.java, ArraysTest.java. Submit as usual by adding, committing, tagging, and pushing. Don't forget to run the style checker (make style) before submitting.