### Overview

Seam Carving for Content-Aware Image Resizing discusses shrinking an image vertically or horizontally to a given dimension automatically while keeping the "important" content of the image.

In general, the algorithm works as follow:

- Compute the energy alue for every pixel
- Find a vertical or horizontal path of the pixels with the least energy
- Delete all pixels in that path and reshape the image
- Repeat 1-3 till the edesireed number for rows and columns is reached

### Energy Function

The most important thing in the ealgorithm is the energy function. The original paper proposed several energy function; we used the most basic one: sum of partial derivative. Specifically, for each pixel in each channel, we will compute the partial derivative in the x-axis and the partial derivative in the y-axis. Then, we will sum their absolute value together. That's it! Mathmatically, it can be described as

\(E(i) = |\frac{d}{dx}i| + |\frac{d}{dy}i|\)

where i is the pixel and E(i) is the energy value for that pixel.

Let's examine the energy map for the white bear image.

### Finding Path

We could use dynamic programming to repeatedly remove least important seams in the image until it reaches the desirable dimension. We will store the curreent minimum result to a matrix M, which has the same shape as the image energy map. Then, finding the minimum value in the last row will essentially find the path that need to be deleted. Repeat this step untile the desired size reached.

### Result

Note: pictures enlarged to show details.

Here are the success results for both horizontal and vertical carving:

#### Failure case:

Sad to see campnile distorted ;(((

### Bells & Whistles: Stretch images using seam insertion

Seam Insertion is the inverse of seam carving. The idea is therefore very similar. We first make a copy of the original image and perform the seam carving with desired size. Record all coordinates while performing the seam carving. Then, we insert new seam on the target image with the same order. The inserted artifical seam is computed by the average of the right and left seam.

### What we learned

We learned that seam carving does not work well with images that have a strong pattern, the distorted campnile for example. Determining importance of pixels by energy function is also fascinating to us because of its simplicity and intuitiveness.