CS129 / Project 3 / Seam Carving

This project involves a content-aware image-resizing technique called seam carving. When reducing the size of an image, seam carving will calculate the lowest energy seams (connected strand of pixels 1 pixel wide that go through the image), and remove those first. In many cases, the lower energy seams happen to be ones with less content, and removing those seams will preserve the more important information in the original image. In a high level, it's algorithm includes the following steps:

  1. Calculate the energy of the image to resize across all three color channels. I did this by using a sobel filter and running it on each channel of the image, then adding their absolute values together.
  2. Find the best (lowest energy) seam to remove. This takes a few steps. First, I generated a scoring matrix the same size of the image, so that I can use dynamic programming to find the lowest energy seam. While I dynamically calculate the energy of the seams row by row, I record for each pixel which pixel it came from. To accomplish this I generated another back-tracing matrix the same size as the image. For each pixel in the scoring matrix (except for the first row), a number, -1, 0, or 1 is placed in the back-tracing matrix to indicate that the pixel belongs to a seam that went through the top-left,top-center, or top-right pixel, respectively. After dynamically calculating the energy of the vertical seams, I can find the total energy values of the seams in the bottom row of the scoring matrix. I choose the minimum of those values, or one of the minimum values, then trace back upwards, using the back-tracing matrix, to find the lowest energy seam.
  3. With the lowest energy seam, I then remove it from the image and obtain a scaled-down image that is content-aware.

The above algorithm is used to calculate lowest energy vertical seams, used for horizontal resizing. To resize vertically, I transposed the source image and ran the same algorithm on it, then rotated the processed image back.

Results

Below are the results of some of my seam carving trials.

Successful Results

From 400x400 to 200x350

From 500x321 to 350x271

From 350x248 to 150x248

From 480x360 to 380x310

From 274x186 to 174x136

From 480x320 to 380x270

The above results all seem to be scaled down pretty well, with most of the important information existing and in proportion.

Failure Cases

Mona Lisa, from 400x536 to 200x486

Kandinsky, from 400x280 to 200x230

These cases did not work so well. In the Mona Lisa painting, her hair was considered low energy because it consisted of vertical strands with small amounts of change. But removing the hair largely distorts the painting. In the Kandinsky image, the straight lines and shapes were distorted from the original art piece. These are some cases that the algorithm cannot produce very satisfactory results.