Dynamic Programming Implementation

Dynamic Programming Seam Finder (Optional)¶

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