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 is an example of how you may define your own Vertex class.

private static class YourVertex {
  // Note: use "static" in the class header if it doesn't use any non-static fields
  // in the outer class. Otherwise, remove the static keyword.

  // ...

  // implements equals
  @Override
  public boolean equals(Object other) {
    // ...
  }

  // implements hashCode
  @Override
  public int hashCode() {
    // ...
  }
}

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 YourGraph implements Graph<YourVertex, Edge<YourVertex>> {
    // Note: use "static" in the class header if it doesn't use any non-static fields
    // in the outer class. Otherwise, remove the static keyword.
  
    // ...
  }
  

• 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.

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.