Seam Carving

Introduction

Think about how you usually scale an image. The most intuitive ways to go about it is:

1. Crop. Basically cut out a piece of the image, while losing significant amount of information.

2. Proportionally Resize. This is most commonly implemented when you change the perspectives of the image. The disadvantage is that the resizing is not aware of the content; therefore important things in the image become distorted.

Shai Avidan and Ariel Shamir proposed "Seam Carving for Content-Aware Image Resizing", basically resizing the image however doing it so that important information gets preserved while unimportant information gets removed. In this project, we implemented their idea in python, and tried it on a variety of images.

Algorithm

There are 2 parts to this problem.

1. How to determine which pixels are insignificant enough to remove? This is done by defining an energy function, as stated in the paper simple pixel gradients perform well, and in our experiments, the gradients indeed performed pretty well for common usage.

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

2. Since we are scaling the image, we can mechanically remove a column or a row that has the least energy; however doing so leads to very obvious artifacts, as if the image is shifted at the column or row removed. Instead the paper proposed finding a seam that minimizes the total energy. In a seam, each pixel is within k pixels away from its previous pixel. (We used k = 1.) This is done via dynamic programming, using the following recurrent relation.

M(i, j) = e(i, j) + min{M(i+1, j+1), M(i+1, j), M(i+1, j-1)}

where e is the energy function and M is the cumulative energy, assuming we are carving horizontally.

In the next section, I will showcase some sucessful examples.

In the above examples, we can see that when the image gets shrunk, we were able to preserve most of the important contents, such as the motoryclce and rider in the third picture, the house in the second picture, while shrinking the unimportant. Notice however in the fourth picture, the algorithm decided to shrink the building instead of the river. It is because it deemed the little white pillars to be more imporant than the building.

Failures

The algorithm is not perfect. It usually performs well where objects are very textured and background is reasonably simple. Performance tend to drop when applied on highly structured scenes or human faces, as artifacts will start to show up. Here are some examples where the algorithm fails to render decent results.

What we have learned

Using gradients to calculate the "importance" value of each pixel.

Dynamic programming to efficiently find the seams that can be smoothly removed. Here are some examples.