15-463 Project #2: Seam Carving

Done by: Junjie Liang (junjieli)

30 September 2010

Overview

In this project, we were required to implement the basic algorithm described in the paper "Seam Carving for Content-Aware Image Resizing" by Shai Avidan and Ariel Shamir. The basic result was a program that could shrink an image (horizontally or vertically) to a given dimension.

Algorithm

The main idea behind the paper was to find the seam with the lowest energy to delete. A vertical (horizontal) seam is defined as a connected path from top to bottom (left to right) that contains a square in each row (column). There are two main parts to the implementation. First, we need to find a good energy function. In this project, I used the e1 energy function described in the paper, which sums up the horizontal and vertical gradient at each pixel. I also tried another energy function which was e1 together an edge detection function in matlab to give more emphasis to edges in the image. The second part was finding the seam with the lowest energy. For that, I used a simple dynamic programming technique which, at each step, computes the cost of the cheapest seam at each row (or column). Then we backtrack at the end to find the exact path used, to determine the seams.

Results

Here are the results of shrinking various images using both the e1 energy function, and the e1 with edge emphasis energy function. As we can see, putting an extra emphasis on edges seem to perform well in most cases. Humans, however, almost always gets distorted by carving.

Original With e1 With emphasis on edges

Notice the bottom of the lighthouse is "carved" away.
This energy function reduces the artifact seen at the bottom of the lighthouse.

The right of the roof is disjointed, presumably because a seam passed through it.
This is better, because an extra emphasis was put on the edge of the roof so less seams passed through it.

Notice the top left corner of the building is carved away.
Edge emphasis to the rescue: This is slightly better.

Where the algorithm doesn't work well

As we see above, whenever there are faces or humans in the image, it becomes difficult to shrink the image, because the slightest distortion looks weird. In general, images with lots of information do not shrink well, because it is hard to find a seam of low energy within the image. For example, the following images all have artifacts when they are shrunk.
Type Original Shrunk
Regular patterns (get distorted)
Humans

Bells and whistles

I implemented a precompute part to the algorithm, so that while it takes a while to preprocess an image, resizing becomes very fast once the precomputation is done. Furthermore, with the precomputation, we can expand the image as well. This is seen in the matlab GUI in the video here.

(This is my first time using the matlab GUI, so it looks a bit clunky and VB6-ish...)

Acknowledgements

Pictures were taken from the following sources. If an image is not listed here, it comes from the class project page, or my personal collection.