CS129 / Project 3 / Seam Carving
The goal of this project is to
implement an image retargeting algorithm. Following the directions, I
have implemented the algorithm described in "Seam Carving for Content-Aware Image
Resizing" by Shai Avidan and Ariel Shamir.
The cost function used to select the minimum cost path depends on
the intensity gradient: E = |d I/dx| + | d I/dy|. I have approximated
the image gradients using the Sobel operator. The core algorithm
uses dynamic programming to find a column minimum cost path and removes
it from the image. In order to retarget an image to the required
dimensions, the basic algorithm that removes one column has to be
repeated several times, the same procedure is used to remove rows. In
my case, I remove one column and one row alternating in an effort to
resize the image more evenly, however, it is not clear which is optimum
order to remove rows and columns for each image.
Resized test images
Here I present the result of removing 200 columns on the provided images for baseline comparison. As can be seen from the right column, the algorithm works acceptably well in this test set.
| Original | Result |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
Additional images (click to zoom in)
In this section, I present the result
on my own images which I had to select very carefully because the
algorithm failed on most of my everyday photographs. The "X" column
shows the original image resized only in the X direction, in the "Y"
column the images were resized only on the Y direction. The "XY" column
shows the results of removing both columns and rows. According to my
results, the algorithm works pretty well on "green" scenes (e.g. grass,
trees, and nature), on constant backgrounds (e.g. sky), but fails on
straight edges which unluckily most of the man-made structures contains
in large proportion (e.g. buildings, cars, and others).
| Original | X | Y | XY |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
Image expansion (click to zoom in)
In addition to shrinking images, a
very similar approach can be used to enlarge the images by adding
columns and rows seamlessly. Having the same considerations as before
on the class of images where the algorithm works best, the result of
expanding images are of the same quality as the result of shrinking
them.
| Original | X | Y | XY |
 |
 |
 |
 |
 |
 |
 |
 |
| |
 |
 |
 |
Object removal
A different application that can be
achieved with the same concepts is to remove some object from image and
fill that region seamlessly. I have implemented this by combining
the gradient based cost function with a user provided mask that tells
which region of the image we want to remove. In this way, the new
energy has a very low cost on the selected region and the algorithm
favors paths passing through it until the region is completely removed.
The final step is to use the previous algorithm to expand the new image
to match the input image size again. In the table below are shown a few
examples of the mask used and the final result.
| Original | Mask | Result |
 |
 |
 |
 |
 |
 |
Failure case
I have found many failures cases as I
mentioned previously. Here I want to discuss another situation which
happens very often in my tests: in the presence of a textured
background (e.g the ocean) the front plane objects are usually
partially removed or distorted. The reason is that the background has
larger magnitude gradients than the other objects (e.g. the sail boat
or plain color human clothes). The result is the opposite of what a
human observer might expect, humans focus their attention on the front
plane objects and persons instead of the equally textured background.
To correct this issue, a different cost function is required.
| Original | Result |
 |
 |
| |
 |