Seam Finding

It’s A Graph Problem!¶

A seam is a path of adjacent or diagonally-adjacent pixels from one side of the image to the other, with exactly 1 pixel from each column/row, for horizontal/vertical seams respectively (opposite sides of an image are not adjacent, so seams cannot wrap around the image).

This subproblem looks much like a regular shortest path problem, since you would still be looking for a “path” of pixels to draw a line through. However, there are three important items to take into account:

• Each edge weight is based on a vertex (pixel) rather than the edge itself. So, you’ll have to calculate a weight based on pixels, but also decide where to put the weight on the edges.
• The goal is to find the shortest path from any of the $H$ pixels in the left column to any of the $H$ pixels in the right column or any of the $W$ pixels in the top row to any of the $W$ pixels in the bottom row.
• The graph has a regular structure assuming that the coordinates are in the prescribed ranges (which means that the graph is a directed acyclic graph (DAG)):
  • There is a rightward edge $(x, y)$ to pixels $(x + 1, y - 1)$, $(x + 1, y)$,
    and $(x + 1, y + 1)$.
  • There is a downward edge from pixel $(x, y)$ to pixels $(x - 1, y + 1)$, $(x, y + 1)$, and $(x + 1, y + 1)$.

Horizontal Seams¶

The findHorizontalSeam() method returns an array of length $W$, where every entry $arr[i]$ stores the vertical position of the pixel to be removed from column $x=i$ of the image. For a less mathematical walkthrough of the return value, consider the 6-by-5 image (provided as 6x5.png) with the energy values shown in the table below.

The minimum energy horizontal seam is highlighted below. In this case, the method findHorizontalSeams() returns the array [2, 2, 1, 2, 1, 1] because the pixels in the minimum energy horizontal seam are $(0, 2), (1, 2), (2 ,1), (3, 2), (4, 1), (5, 1)$ (or, $(i, \text{pos}H_i)$ for every $i$):

When there are multiple horizontal seams with minimal total energy, your method can return any of those seams.

Vertical Seams¶

The behavior of findVerticalSeam() is analogous to that of findHorizontalSeam() except that it should return an array of length $H$ such that every entry $arr[i]$ is the horizontal position of the pixel to be removed from row $y=i$ of the image.

For the 6-by-5 image, the method findVerticalSeam() returns the array [4, 4, 3, 2, 2] because the pixels in the minimum energy vertical seam are $(4, 0), (4, 1), (3, 2), (2, 3), (2, 4)$ (or, $(\text{pos}W_i, i)$ for every $i$):

DijkstraSeamFinder¶

In order to get DijkstraShortestPathFinder to be able to remove seams, we’ll need to reduce the seam finding problem into one that’s solvable with a shortest path finder:

1. Create the Graph implementation that DijkstraShortestPathFinder will operate on.
2. Set the actual reduction:
   • Transform the DijkstraSeamFinder’s input into one that works with DijkstraShortestPathFinder — instantiating the graph implementation and choosing our start and end vertices.
   • Convert the output of DijkstraShortestPathFinder into the format required for DijkstraSeamFinder.

Graph Implementation¶

Roughly, this is how you should represent your graph to be able to find seams:

• Vertices represent pixels.
• Edges exist from a pixel to its 3 adjacent, rightward or downward neighbors, for finding horizontal and vertical seams respectively.
• Edge weights represent the energy of each pixel.
• The shortest path (least total weight) represents the minimum energy seam.

Here are some additional implementation notes that you should keep in mind as well:

• Don’t name the graph class Graph since that will conflict with the graphs.Graph interface.
• The graph (and any other custom classes) must be declared as nested classes within the DijkstraSeamFinder class. If you write code in new files, our autograder will not be able to find them during grading.
• The provided pathFinder field in DijkstraSeamFinder suggests what the graph and edge types should be, but you will also need to choose your own vertex object (either by selecting a suitable existing type or writing your own). Once you choose a vertex type (and being sure to update the pathFinder type definition to match the chosen vertex type), you can declare your Graph subtype to look something like

  private class MyGraph implements Graph<MyVertex, Edge<MyVertex>> {
        // ...
    }
  

• Since horizontal and vertical seams will need slightly different graphs, you may need to create two versions of the graph class or include logic to switch between horizontal and vertical versions (note that the vertical seam of a $W$-by-$H$ image is just the horizontal seam of an $H$-by-$W$ image).

Tests¶

Unlike previous projects, we have not provided many unit tests to test your implementation. Instead, we’ve included multiple images of various sizes in the seamcarving/data folder along with the expected energies and seams in .txt files. You should test your implementation by running the provided demo applications, and modify them as needed to test your implementation (or just for fun!):

• The SeamCarverVisualizer can remove either the horizontal or vertical seam:
  

• The PrintSeams class prints the numerical seams values to console. It might be helpful to manually check your results against the expected ones provided as text files in that folder.

Or, you can practice making your own tests using the provided text files.

Optional: Dynamic Programming Implementation¶

In the real world, seam carving is implemented using a different approach called dynamic programming (DP). In fact, the original paper for seam carving described the algorithm using dynamic programming.

The dynamic programming approach works by starting from the leftmost column and working your way right, using the previous columns to help identify the best shortest paths, when removing a horizontal seam. The difference is that dynamic programming does not create a graph representation (vertices and edges) nor does it use a graph algorithm.

How does dynamic programming solve the seam finding problem? Most of the runtime is spent generating the dynamic programming table (DP table):

1. Initialize a 2-D double[picture.width()][picture.height()] array where each entry corresponds to a pixel coordinate in the picture and represents the total energy cost of the least-noticeable path from the left edge to the given pixel.
2. Fill out the leftmost column in the 2-D array, which is just the energy for each pixel.
3. For each pixel in each of the remaining columns, determine the lowest-energy predecessor to the pixel: the minimum of its left-up, left-middle, and left-down neighbors. Compute the total energy cost to the current pixel by adding its energy to the total cost for the best predecessor.

To find the shortest horizontal path using this DP table, start from the right edge and add the y-value of each minimum-cost predecessor to a list. The result is a list of y-value from right to left. Finally, to get the coordinates from left to right, Collections.reverse the list.

To find the shortest vertical path, the same process is followed as the horizontal path but in a vertical manner (starting from the bottom and going up).

Submission¶

If you’re working in a group, the partner who submits must add the other partner as a group member on Gradescope. Here’s a video demonstrating that process. You’ll also need to re-add group members whenever you resubmit to the same assignment, even if you already did so on a previous submission.