Programming Project #2
Seam Carving
Author: Josip Djolonga

Introduction

The purpose of this project was to implement an algorithm for content-aware resizing. This particular algorithm was invented by Shai Avidan and Ariel Shamir and the paper is available here.

Approach

The general idea of the algorithm is very intuitive and simple. First, you compute an energy function of the picture, which should correspond to the importance of the different parts. Then, at each iteration you pick a path (vertical or horizontal) that is of minimum cost and you remove it. This path can be easily computed using dynamic programming. On the right you can see a video of how my implementation works, reducing the width of the picture by 200 pixels. Furthermore, this same idea can be used for several other tasks like object removal and image stretching.

Energy Functions

There are many functions that can be used. One is to try to minimize the norm of the gradient vectors along the path (the gradient is taken as the average of the three per-channel gradients). The other function that I use computes both the norms of the gradients and finds the edges using an edge detector. Then, it does a linear interpolation between them, thus strengthening the important parts of the picture. Below are the resulting energy functions using both approaches from the picture that is in the video.

Gradient only.	Gradient + Edge detection.

These are the final results, when the images are resized by 200 pixels in width. As you can see, when we are using both the gradient and the detected edges, the structure of the house is less disturbed than in the other case (see the edges of the roof).

Gradient only.	Gradient + Edge detection.

Results

These are the results when the algorithm was applied by first scaling down horizontally and then vertically.

Original Image	Gradient Only
Picture from flickr.	Gradient and Edge Detection

Original Image	Gradient Only	Gradient and Edge Detection
A picture from flickr.

Original Image	Gradient Only	Gradient and Edge Detection
The White Horse, John Constable

Original Image	Gradient Only
	Gradient and Edge Detection

Original Image	Gradient Only
The Fighting Temeraire, J. M. W. Turner	Gradient and Edge Detection

Original Image	Gradient Only
Picture from flickr. A place near my hometown.	Gradient and Edge Detection

Original Image	Gradient Only
Elephants, Salvador Dali	Gradient and Edge Detection

The algorithm is of course, not perfect. There were some cases where it did not preserve the features of the picture. These pictures are presented in the next section, together with results of how some of them can be fixed using the techniques described below.

Bells & Whistles

Seam Insertion

To perform seam insertion, the algorithm finds the first K seams that it would remove and then it replicates them. When you replicate a seam you interpolate it with the other neighbor (linearly, you take the average). Also, note that if we do this for fairly large K what we will get is a standard image scaling. To avoid this, if we want to insert many seams, we do the operation explained above multiple times. In my implementation, I have limited every iteration to increase the size of the picture by at most 10% of the original size. Some results are shown below.

Original Image	Enlarged
Same as the picture in the previous section.

Original Image	Enlarged
Taken with my camera.

This is an example where the algorithm did not work correctly when set with maximum of 10% at each iteration.

Original Image	Enlarged
From flickr.

Object Removal

Using a slight modification of the algorithm, you can easily remove objects from the picture while keeping the same size. First, using a user provided binary mask all selected pixels (where the mask is 1) are given large negative weights to their energies so they will be the first to be removed. An interesting question is, how to choose whether to remove vertical or horizontal seams? One way to do it is to use the optimal combination which can be computed using a dynamic programming algorithm. I have taken a greedy approach, at each iteration you take what gives you less cost, a horizontal or a vertical seam. As this will reduce the size of the image, then the seam insertion algorithm is used to restore the original size.

Original Image	Mask
From flickr.
Object Removed

Original Image	Mask
From deviantart.
Object Removed

Image Resize with Human Input

One way of improving the algorithm is to use human input as well. The user has to give to the algorithm a mask that will select the areas that he doesn't want to get shrinked. Then, the energy function is adjusted by adding large weights to these areas, ensuring that they will not get modified. This approach has managed to fix a lot of problems that occurred with the original implementation. Here, both results are presented: when the original implementation is used and when we use this approach with user input.

Original Image From deviantart.	Mask
Without the Mask	With the Mask

Original Image	Mask
Without the Mask	With the Mask

Optimal Seam Removal

When we have to resize the picture in both dimensions, say by M horizontally and by N vertically, there are several ways in which we can order the combination of horizontal and vertical seams. In the pictures presented above, the seams were first removed in the vertical direction and then in the horizontal direction. Ideally, what would we be interested in is to find the optimal combination. Under optimal we understand the combination such that the total cost of all seams is minimal. This can be achieved using dynamic programming. We define a table T of size MxN such that entry T(i,j) contains the minimal cost obtainable when we perform i horizontal and j vertical seams. Using a simple recurrance we can fill in the table, and the result is then in T(M,N). I have implemented this in MATLAB, and because of MATLAB's notorious performance with loops, which can not be easily avoided because of taking minimums, this algorithm performs slowly. Below are some results of the differences when we use and when we do not use optimal seam carving.

Original Image Shown in the previous section.
Normal Algorithm	With Optimal Seam Carving

Original Image From flickr.
Normal Algorithm	With Optimal Seam Carving

As you can see, the differences are very small, and I wouldn't recommend using the optimal algorithm as the time penalty is too high for the small improvement in quality.