Homework 2: Arrays and Lists of Lists

A. Preliminaries

Due Wednesday, September 18 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...

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.

/** 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 good uses for the IntListList constructor, which takes as input two-dimensional arrays.

Also don't go overboard on tests. One "normal" input and a couple of corner cases is likely enough for 61B HW purposes! Only write more tests if you think you'll either save time or learn something by writing them. If you DO want to go overboard, the Utils class provides some handy methods for doing so. 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, but again you can get along just fine without using it.

/* 2a. */
/** 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;
}

/* 2b. */
/** 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;
}

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 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 edge 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 W=C 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.

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:

• 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 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 . You'll see from the filled in copy of int[][] am that am (marked in blue) has value 1075990. To understand where this value came from, consider that there are three ways that you can get to , namely:

• Moving down and to the right from , which has accumulated energy 1000000.
• Moving directly down from , which has accumulated energy 1000000.
• Moving down and to the left from , 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  is given by 1000000 + 75990 (the cost of including the pixel at  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 . There are two ways to get to , either:

• Moving directly down from , which has accumulated energy 2000000.
• Moving down and to the left from our old friend , which has accumulated energy 1075990.

Obviously it'd be better to have come from , so we know that the minimum cost to reach  must be 1075990 + 1000000 (the cost of  itself). And in fact, by an inductive argument, we know that this is not just the lowest cost to reach  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  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 , which has accumulated energy 2000000.
• Down from , which has accumulated energy 1075990.
• Down and to the left from , which has accumulated energy 1030003.

Our best choice is to come from , 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, am, or am 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. 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.

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, just run the program as follows:

java -ea image.Rescaler [image filename] [num columns to remove] [num rows to remove]

or within IntelliJ.

E. Natural Runs in Arrays

Here's an array problem whose most natural solution involves recursion. For this problem, go back to Arrays.java and complete the final method:

/* 4. */
/** 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. You are not required to use the Utils class in your solution.

F. Submission

You should have completed Lists.java, ListsTest.java, Arrays.java, ArraysTest.java, MatrixUtils.java, MatrixUtilsTest.java. Submit as usual by committing, tagging, and pushing.