Seam Carving

I. Introduction

Ever had the struggle of finding a beautiful and fabulous landscape image that you want to use as your phone wallpaper, but when you try to crop it into a portrait image nothing looks good? Well, no need to worry, because seam carving (kind of) solves the problem!

Seam carving is the process of resizing images by removing seamsin the images while taking image content into consideration. A seam is a 8-connected path that extends from one side of the image to another. The seam is chosen by considering some energy function that differentiates the important (high energy) features from the unimportant (low energy) features. The seam with the least energy is selected and removed. This process can be repeated until the image is the appropriate size.

II. Implementation

There are many ways to define an energy fuction of an image, but the energy function I chose to use is a Sobel edge detection filter that I implemented. Looking at edges is a good way to determine where objects, and therefore important features, are.

Next, we must sum up the energies of each pixel along possible seamsin the image to find the seam with the smallest total energy. This process, if done exhaustively can get very expensive very quickly. So instead, we use dynamic programming to do this calculationby creating a minimum energy path matrix and a path matrix. Each pixel has three possible paths to follow going down a row to reach an adjacent pixel: left, middle, and right. Iterating through each row in the image starting from the first, or top, row, we go through each pixel and determine which path it should take in order to minimize the summed energy. This energy path sum is placed the energy path matrix, and the path taken is placed into the path matrix. This value in the energy path matrix is used in the next row, and so on. The last row of the energy sum matrix is the total energies of the smallest total energies of seamsstarting from each bottm row pixel. The seam can be traced using the path matrix. All the pixels in the seam with the smallest total energy is deleted, and an image of 1 pixel less width is created.

Seam carving with horizontal seamsis done simply by rotation the chosen image by 90 degrees before carving and rotating it back to its original orientation before saving.

III. Results

Of the images I have been testing my seam carving with, this one I took of the Blue Angels is one of the most successful. This is because there is a very distinct foreground and solid background. The bulk of the planes and the smoke coming from them are nicely confined to just one area of the image so that there is a clear section of the image that allows continuous seamswithout going into any of the planes or smoke.

All the seam carved images of reduced size are shown with black padding to keep all the images the same size.

Below are some other examples using photos I took.

There are also several cases where seam carving does not fare well by this energy function. One of them is images with lines and edges running through them. This creates jagged or curvy edges through the image that we would normally expect to be straight.

Applying seam carving to an image of my dog, Calculus, had unfortunate results both vertically and horizontally. This is because Callie's fur, lacking edges, is rather boring compared to the marble, which has a lot of very distinct edges in the pattern.

IV. Bells and Whistles

Alternate Energy Functions

The Sobel Operator is basically a more sophisticated version (because it also considers information from pixels diagonally adjacent) of the basic gradient energy function described in Shai Avidan and Ariel Shamir's paper, Seam Carving for Content-Aware Image Resizing. I also implemented the basic gradient function and tested it out on some images.

The energy values look quite similar overall, except that some portions are less pronounced than the Sobel Operator energy. The resulting seamshowever, show that this makes quite a difference. The edges of the seamswhere pixels were removed are noticable and create unappealing edges, which is especially pronounced at 200 seamsremoved.

Seam Insertion

Seam insertion is the complete opposite of seam removal, but with a similar idea. If we can find some least energy seam in an image, inserting a new seam next to that seam with pixels averaged from that lowest energy seam and a seam beside it should allow us to insert an entire column or row of pixels without much alteration to the overall image composition.

In order to implement seam insertion, I had to change how seamswere calculated. In seam removal, at each iteration, I used the new image of one pixel less width to create a new energy function and find the least energy seam from there. In seam insertion, however, this process would simply pick one least energy seam and insert that same seam however many times, which would look... odd. Therefore, we must find some n seamsthat do not repeat. This is accomplished by using the image with the red seamsadded to compute the energy. Since the red seam is a very high difference edge, our path finding will be kept from overlapping from previous paths.

This implementation has its downfalls. Since I am using red seamsto steer future seamsaway from past seams, it will cause problems for images with high red channel content. This can be overcome by inverting the seamsinstead of colouring it red.

Object Removal

Objects can be removed from an image by adding a mask of negative weights to the energy of the image. This means that any seam going through the mask would have those negative energies added to it, and thus have a negative total energy, and those seamswill be chosen to be removed first.

I have had only limited success with object removal, however. At a certain number of seamsremoved, seamsother than the ones going through the masked area would be chosen, leaving a small portion of the object remaining.