An example execution of the algorithm on the picture provided
on the course web site.
Introduction
The purpose of this project was to implement an algorithm for contentaware 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 perchannel 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.