Project2: Seam Carving

Danielle Millett

This project was to implement seam carving, which is a content aware algorithm for resizing images. The idea behind it is that when resizing, instead of removing an entire column, remove a seam that contains a pixel from each row that isn't that important to the content of a picture. To calculate this seam, I used the gradient as an energy function. I found that this performed fairly well on most images. My implementation of the algorithm involved the following:

1. Convolved the image with a gaussian filter to smooth it and remove any aliasing
2. Compute the gradient of the image by find the partial derivative in the x and partial derivative in the y and taking the sum of the absolute value of the two.
3. Find the seam with the least energy by using a dynamic programming algorithm.
4. Removing this seam from the image.
5. Repeat steps 2-4 until the image is the correct size.

The user can specify which direction (vertical or horizontal) to shrink the image in, and the program simply transposes the image before and after passing it into the algorithm. All the images used for results were from my own collection of pictures that I have taken.

Here are some of my results:

These last 3 pictures didn't turn out perfect and have some small traces of artifacts, but generally look okay. The artifacts are most likely due to attempting to shrink them too far.

Bad results:

The bad results in all of these pictures seem to be due to the large number of lines, particularly parallel lines. When the algorithm calculated the seams, it tended to cross over these lines creating artifacts.

SEAM INSERTION

To stretch images, I used a similar process to seam carving called seam insertion. To avoid having the same seam repeated over and over again, I added seams in the order they would have been removed from the image. To add a seam I inserted a pixel that was the average or its two neighboring pixels. I had trouble figuring out how to store the seams that were going to be removed since the values are relative to the size of the image, which changes. I was able to partially resolve this, but it wasn't the most ideal way, so the results of these aren't as good as they could be.

Here are some results from seam insertion: