Part 2b: Compute Seam

Implement the following method to find a seam:

• public int[] computeSeam()
  should return an array of integers representing the location of the least-noticeable seam in this Picture. This is the crucial subroutine and the dynamic programming algorithm for this project! See below for a pretty extensive explanation.
  You might find the debugging methods printArray(int[][] A) helpful.

This is the dynamic-programming part of the assignment. A vertical seam is a sequence of pixels, one per row of pixels, such that pixels in adjacent rows are no more than one column apart. Since there’s exactly one pixel per row, we only have to remember the columns of each pixel; this can be represented as a single array of integers.

Step one is to create an array table of integers, of the same size as the image. Each entry table[x][y] is the total energy of all pixels in the least-energy seam starting on the top row and moving down to the ending at pixel (x,y). It is sometimes called the cumulative-energy table (or cost table): it does not contain single energies, but the smallest cumulative energy starting from anywhere at the top and ending at pixel (x,y).

As discussed in the paper, we can define the entries in table recursively by at is, the least-energy seam ending at (x,y) extends the best seam ending either directly above-and-to-the-left, directly above, or directly above-and-to-the-right. (Note that for pixels on the far left and far right borders, only two of these three possibilities exist.)

The dynamic programming approach is to fill out this table in order of increasing y: first all the entries where y=0, then the entries where y=1, etc.

We also need code to keep track, at each pixel, which of the 3 possible parent seams was chosen. This means creating a second 2D array, perhaps named parent. The idea is that parent[x][y] will hold the column number (x-value) of the previous-row’s pixel in the best seam ending at (x,y).

Table, Parent, Seam

If we had a 3-by-3 image whose energies were:

 1 2 3
 8 6 4
 5 6 5

Then table would be:

1  2  3
9  7  6
12 12 11

and parent would be:

X X X
0 0 1
1 2 2

The top row of the parent array doesn’t matter, since there are no more pixels above. Slightly more generally, if while computing table[x][y] we decided the smallest of the three possible parent locations was table[x+1][y-1], then parent[x][y] should be set to x+1. If the smallest of the three possible parent locations was table[x][y-1], then parent[x][y] should be set to x. And so on.

Finally, when we have filled out the table and parent arrays, we can find the best seam. You won’t be surprised that several loops are involved in this!

First, we loop across the bottom row of the table array. As we do so, we find the smallest table value in that bottom row (where y == height-1). The location you find has the minimum cumulative energy and will be where the seam ends. Then, using the parent array, you can determine whether the seam extends up-and-left, up, or up-and-right. Then, you continue working your way up, until reaching the top row.

As this process happens, you can collect each of the column (x) values for the pixels in the seam at each row. A one-dimensional array whose length is the height of the picture is ideal for this: the index into the array is the row number and the contents of the array is the column location of the seam at that row. (Think of it as a ”column” array, though it doesn’t really have any preferred direction.) My implementation called this array seam.

Continuing from the 3×3 example above, the best seam ends in the lower right corner, in column 2, because that’s the smallest value of table in the bottom row. Thus, seam[2] = 2. Working backward through the parent array, we find that the best north-neighboring pixel in row 1 (the one with lowest cumulative energy) is also in column 2, so seam[1] = 2. From there, the best northneighboring pixel in row 0 is in column 1, so that seam[0] = 1. Thus we get the seam (from top to bottom) 1,2,2, corresponding to original pixels that had intensities 2, 4, and 5.

Tiebreaking! We need a rule for breaking ties when defining the seam: more than one of the neighbors in the next-row-up may share the same minimum value!

If there is a tie when you’re identifying which Pixel to select on the minimum-cost path, please select the Pixel with the same x value as the first choice (if it is the min or shares the min). Choose the Pixel to the left (x-1) as the second choice (if it’s the min but the previous one is not). Finally, choose the pixel to the right (x+1) – if it’s the only one with the minimum value. If there are multiple paths that have same, minimum cost: Select the path that has the minimum X value on the bottom row (i.e. the largest Y value)

Please make sure you understand what table, parent, and seam are before you start coding!

Tests

Your code should be able to pass all of the tests in PictureTest_ComputeSeam.java.