Seam Carving

CS 194-26 Project #4  ·  Owen Jow  ·  October 2016

---

Overview / Algorithm Description

As described in Seam Carving for Content-Aware Image Resizing (Avidan and Shamir), seam carving is a method for image resizing based on actual scene content. In other words, we modify the aspect ratio of an image and protect its contents by choosing to remove or duplicate only its most unimportant regions. (Incidentally, over the course of this project we will focus on image shrinking, i.e. removal only.) In theory, this allows us to avoid messing with salient features / strong contours, and play merely with the proportions of smooth (again, "unimportant") areas instead.

To preserve the rectangular shape of the image, we make sure to only modify one seam at a time. For our purposes, a seam is an "optimal 8-connected path of pixels on a single image from top to bottom." Note that by "optimal", we refer to the seam with the minimal cost – where our cost is said to be the total energy of all the pixels along the seam. Here, energy is defined as the gradient magnitude at each pixel:

E(I) = |dI / dx| + |dI / dy|

(We convolve our image with the 3x3 Sobel kernels in order to approximate pixelwise gradients in each direction.)

Anyway... algorithmically speaking, how do we find the optimal vertical seam? Well, we first determine the energy at each pixel in the image and store the values in an identically-sized array. Then we turn everything into the dynamic programming problem of computing the cumulative minimum energy M at each pixel (i, j). The minimal cost of a seam going through any given pixel is based on that of the three pixels above:

M(i, j) = E(i, j) + min[M(i - 1, j - 1), M(i - 1, j), M(i - 1, j + 1)]

As a base case, M(i, j) for each top-row image pixel is simply the value of the energy function for that pixel.

After we've computed the cumulative minimum energy for every position in the image, we can find the optimal vertical seam by taking the smallest result from the bottommost row and backtracking upward from there. (Of course we want the seam with the least cumulative energy!) If we make sure to grab only one pixel per row, then we can cut out the seam, maintain image rectangularity, and be assured that we've only removed a vertical sliver of pixels that nobody even noticed in the first place!

---

For vertical carving (meaning the removal of horizontal seams), we simply transpose the image, run the horizontal carving algorithm as before, and then transpose everything back upon completion.

Successful Results

The connotations associated with that first word are obvious, but hey – we'll start with the good stuff. Below, you can find a collection of arguably successful seam carvings in the horizontal and vertical dimensions (one, the other, and sometimes both!).

Unsuccessful Results

And here we have the other side of the coin. A few of the images didn't work, whether due to the inability of the energy function to predict important parts of the image or due to our pushing of seam carving to its limit – specifically to the point where removing more seams wouldn't really be possible without noticeable shape distortions.

In the following image, for example, the algorithm mostly attempts to remove paths traveling down the middle of Jerry's face. This is probably because there is only one major color disparity there (i.e. the black bridge of the glasses). In truth, though, we would prefer to eliminate seams running through the window, couch, and Jerry's shoulders. Anything but the face!

Other failures:

Reflection

Once again, I learned that gradients are a very powerful tool for image processing. Since humans tend to focus on high frequency components, I guess we don't notice as much when the rest of an image is modified (as is the case in seam carving). At the very least, things don't seem as off as one might expect.

I also discovered that (a) as suggested in my algorithms class, dynamic programming is not designed around efficiency, and (b) Python for-loops are bad. As my algorithm contains no performance adjustments, every large (> 1000 x 1000) image requires a decent chunk of time (on the order of tens of minutes, in the worst case!) to process. The midnight deadline approaches, so I will most likely be forced to cast aside my beautiful high-res images and turn them into 360 x ? miniatures. In the future, this problem could be solved by starting earlier and vectorizing my operations. It's probably also possible to discover multiple minimum-cost seams upon a single image iteration.

Finally, since I have the time, I'll mention that it was very cool to be able to resize images using a technique more sophisticated than that of regular old scaling and cropping!