Seam carving is a technique for **image resizing** where the size of an image is reduced by one pixel in height (by removing a horizontal seam) or width (by removing a vertical seam) at a time. Unlike cropping pixels from the edges or scaling the entire image, seam carving is **content-aware** because it attempts to identify and preserve the most important content in an image. Seam carving works by using an energy function to find the lowest energy connected pixels either horizontally or vertically across an image and then removing it.

Our implementation uses a `DualGradientEnergyFunction`

which defines the energy of a pixel to be the magnitude of the rate of change of colors at that pixel — a high energy pixel is one that has a large change from its neighbors while a low energy pixel has very little change between itself and its neighbors. The way we calculate this value is by approximating the derivative in the $X$ and $Y$ directions then combine these using the pythagorean theorem to get the overall change. This has been implemented for you.

Inside `src/seamcarving`

, you’ll find the `SeamCarver`

class which has already been implemented as well. SeamCarver has methods for removing the least-noticeable horizontal or vertical seams from a picture. The `removeHorizontal()`

method works by:

- Calling
`SeamFinder.findHorizontal()`

to find the least-noticeable horizontal seam. - Removing this horizontal seam by creating a new picture with all the pixels except for the ones specified in the horizontal seam.
- Returning the horizontal seam (primarily to verify that the correct seam was removed).

The `removeVertical()`

method does the same thing except in the vertical orientation.

In this project you will implement 1 graph representation, 2 graph algorithms, and 1 dynamic programming algorithm for seam carving:

Info

For this project, you are only required to implement `DjikstraShortestPathFinder`

, and `DjikstraSeamFinder`

. `DynamicProgrammingSeamFinder`

is optional and worth extra credit if completed.

`DjikstraShortestPathFinder`

: finds the shortest path by using Dijkstra’s Algorithm.`DjikstraSeamFinder`

: finds the seam to remove by using a reduction of the shortest path problem.`DynamicProgrammingSeamFinder`

: an optimized way to find the seam to remove by using dynamic programming.