Hua Guo (huag)

CS129 / Project 3 / Seam Carving

Introduction

In this project, seam carving is implemented to retarget a given image to a specified size while trying not to distort important objects in the image. In addition to the basic implementation, three extra credits are implemented: score matrix based on forward energy, seam insertion and preservation of user-chosen objects.

Basic Implementation

The basic implementation of the seam carving algorithm is divided into three blocks: computing the energy matrix, computing the score matrix based on the energy matrix, and finding and removing the seam that produces the least energy. The seam removing function removes one seam at a time, and the function is iteratively called, each time taking in the result image from the previous iteration as the input, until the image is reduced to the target size.

In step 1, the energy function is based on the gradients of the image. Both vertical and horizontal gradients are computed for each channel and added together. Matlab's gradient function is used to compute the gradients. In step 2, the score matrix is computed using dynamic programming. The algorithm starts by copying the first row in the energy matrix to the score matrix, and for each of the following rows in the score matrix, the value of each element is computed as the summation of the corresponding element in the energy matrix and the smallest neighbor in the row above. In step 3, the seam is found simply by starting from the smallest element in the bottom row and traversing all the way up by always selecting the smallest neighbor in the row above.

Impelementation Based on Forward Energy

One potential improvement for the basic implementation is to "look forward" when computing scores for seams, i.e., take into account the change in the local gradient after removing a seam. This way, more penalty will be put on seams that will result in more discontinuties or edges if removed.

To implement forward energy, the computation of the score matrix is modified so that at each pixel, it considers the change in the local gradients after the removal of each neighbor in the row above. Step 1 and 3 are identical to those in the basic implemention.

Result 1: Backward v.s. forward energy

Original	Backward energy	Forward energy

For the images that have been tested in this project, forward energy always does a better job. For example, in the above images, the shapes of the mountains are more natural with forward energy in the first and the fifth examples, and the woman's figure is more natural in the second image.

Result 2: Images resized in both dimensions

Seam Insertion

In addition to using seam carving to reduce the size of an image, I have also implemented image expansion based on seam insertion. Similar to the principle behind seam carving, seam insertion also involves computing energy matrix, computing score matrix and finding the minimal energy seams. However, instead of removing the seam that has the least energy, we want to duplicate it to expand the image.

While the most naive approach to expand the image width by k columns might be to simply duplicate the k minimal energy seams found in the original image, the results will have obvious artifacts because the k minimal energy seams are likely to be concentrated in one or two small regions. Instead, my algorithm finds every ith seam from the image where i-1 seams have already been removed. In the implemention, the program first runs like in the original seam carving algorithm, iteratively removing seams and recording the seams removed. Then, the algorithm proceeds to duplicate each recorded seam to produce the expanded image. One tricky part of the implementation is that when recording each seam in the seam removal stage, one needs to recover the position of the removed seam in the original image, instead of simply recording the position of the seam in the current processed image.

Result 3: Seam Insertion

Original	Expanded by 200px in width naively	Expanded by 200px in width through smarter seam insertion

The algorithm can also reduce the image size in one dimension and increase the size in another dimension:

Left: original image (620 * 572 px). Right: the original image retargeted to 520 * 672 px.

User defined object preservation

Sometimes, the seam carving algorithm does not work well with images that have faces in it, as even the slightest distortion to human faces is likely to be very noticeable. One way to help cope with this is to allow the user to specify a region that they want to preserve. In the implementation, I have reused the interactive mask drawing function from project 2 to allow the program take in a user-specified mask. After obtaining the mask, the program will add a large value (the maximum value in the original energy matrix) to the masked pixels when computing the energy matrix. With this modification, the user selected region will be preserved unless all the other possible seams are already removed.

Result 4: Seam carving with user defined masks

Original	Without mask	With mask

Failure cases

The algorithm does not work very well with images that have many long straight lines. To prevent noticeable artifacts when removing pixels from an object that is composed of straight lines (pillars, stairs, door frames etc), the algorithm must remove a series pixel that consists of a line that is perpendicular to the object. This is almost impossible when there are many such objects in the image, though, like in the case of the photo of CIT, or when there is only one such object but that object is positioned far from being either horizontal or vertical.