Experiments on Seam Carving

OK, I admit. I was really curious about the technique named seam carving, which I've blogged before, and which has received a fair amount of attention on the net recently. I then decided to explore it a bit more using the gimp plug-in (BTW, kudos to Carlo Baldassi for this plug-in, I'll write more about it later). So, I've chosen a few representative images and ran the implementation on them in order to evaluate in what conditions the algorithm performed ok and when it failed. The rest of this blog details these experiments.

A Reference Image

Before checking the algorithm on real pictures, I've decided to test it on the following somewhat artificial image to better check for its effects on image features:

A Reference Picture With a 1024 Pixels Width

As can be seen, the image, which has a width of 1024 pixels, consists of two subjects, an apple and grapes, with a gradient background behind them. Why the gradient background? Well, since for this image the seam carving algorithm is going to be applied on its width, and hence it will run roughly over the vertical columns of pixels, we should get approximately the same results as for a plain background. On the other hand, any distortion caused by the carving will be readily apparent, due to distortion on the gradient itself.

Just for the sake of comparison, I've scaled the width down to 640 pixels, which gives a little less than 40% reduction, and the result is shown below. As can be seen, distortion is evident throughout the scaled-down image.

Scaled Down Version of Reference Picture

Applying the seam carving algorithm on the reference image to reduce it to a 640-pixel width gives the result below. Comparing it with the previous scaled-down image, we can immediately see the gains the algorithm gives. Although distortion is visible in the gradient background, the apple and the grapes keep their original shapes.

Reducing Reference Picture to 640 pixel-width With Seam Carving

We also reduced the image further to a 480 pixel width (a reduction of more than 50%), as shown below. In this case, the fruits start to present some distortion, but this is unavoidable seeing that they are already packed against each other.

Reducing Reference Picture to 480 pixel-width With Seam Carving

From these pictures we see that the algorithm performs reasonably well when applied to an image with an homogeneous background. Let's check now for more interesting images.

Selected Images

For real-world images, five images were chosen (two landscapes, two with people and one geometric) having features that are representative of most pictures, like human and animal figures, geometric shapes and loosely-constrained shapes (like trees, mountains, grass fields and clouds, whose shapes can vary significantly and still look ok). The images were reduced to 75% and 50% of their original size using seam carving in both width and height (separately).

The first landscape image is a picture of a small village in a valley.

First Landscape Picture - A Valley

Here we see that the image contains a detailed bottom half and a more homogeneous upper half. Besides, none of the elements in the picture are too constrained on their shapes. We then applied the algorithm on this image, getting the results below. As I said in my previous post, the processing time for 1024x800 pixels images are in the order of 15 - 20 seconds. This one, being a little smaller (680x500), took less than 10 seconds.

Applying Seam Carving at 75% on Width

Applying Seam Carving at 75% on Height

Applying Seam Carving at 50% on Width

Applying Seam Carving at 50% on Height

From the above images we see that the algorithm performs reasonably well at both reduction rates and in both directions (width and height). So far, so good.

The next image is a landscape picture with a horse in the middleground.

Horse at a Grass Field

Applying Seam Carving at 75% on Width

Applying Seam Carving at 75% on Height

Applying Seam Carving at 50% on Width

Applying Seam Carving at 50% on Height

The situation here is a little different. The algorithm has problems even at the lower scaling rate, since the horse is significantly distorted in all cases, even though the rest of the picture looks ok. That may be partly due to the patterns for the grass and the clouds having more details than for the horse, but it is also because any change in the shape of the horse is much more noticeable than for the other elements in the picture. This effect can be seen not only here but in the next pictures, too.

Another problematic picture is the one below with a man silhouette in the center of the image.

Silhoueted Man

This is a rather interesting picture because of its lack of details, both in the man as in the other parts of the picture. Running the algorithm on it gives the following images:

Applying Seam Carving at 75% on Width

Applying Seam Carving at 75% on Height

Applying Seam Carving at 50% on Width

Applying Seam Carving at 50% on Height

We can see that only the least reduced-height picture is really acceptable, since it is the only one where the man is not significantly distorted. Again, it may partly due to the lack of details in the man texture, but also is due to more stringent criteria for the human shape.

The fourth picture also has human figures in it, in this case, two children.

Children at the Beach

It's worth noticing that the children are well-lit and have good details, unlike the silhoutted man in the previous image. Applying the algorithm gives the images below.

Applying Seam Carving at 75% on Width

Applying Seam Carving at 75% on Height

Applying Seam Carving at 50% on Width

Applying Seam Carving at 50% on Height

We can see that, even though the algorithm performs a little better, the higher-compressed images are still problematic.

The last image is a picture of a part of the Golden Gate, in San Francisco, and as such is strongly geometric.

Golden Gate

Although the picture doesn't have a lot of detailed patterns, it has lots of straight lines. Applying then the algorithm gives the following results:

Applying Seam Carving at 75% on Height

Applying Seam Carving at 50% on Width

Applying Seam Carving at 50% on Height

We can see that in none of the cases the algorithm performs satisfactorily. Hector Yee in his blog reported finding problems with geometric shapes, too. Interestingly, he tried a modified algorithm which chooses the seam to be removed in a more stochastically way found that it apparently gave better results. Since I didn't have access to the modified algorithm, I couldn't test with the above image, but in some way it makes sense, since removing seams more or less randomly may give straighter lines.

The Gimp Plug-in

The gimp plug-in has a feature where one can define a region of the image to be (mostly) preserved from the operations of the algorithm. We used this feature to re-run the algorithm for the second and third pictures, preserving the areas around the horse and the man, respcectively. The results for the 50% reduction cases are shown below.

Applying Seam Carving at 50% on Width Preserving Horse Shape

Applying Seam Carving at 50% on Width Preserving Human Shape

It can be readily seen that the results have improved very significantly, with both the man and the horse shapes preserved (as they should), while the rest of the picture with the same good results as before. We can conclude that seam carving, as implemented by the gimp plug-in, does a good job in scaling down images with "generic" shapes, like trees and mountains, which are present in most landscape pictures. It has, however, problems with pictures with more constrained shapes, like human and animal shapes. These problems can be, though, substantially improved by protecting the sensitive parts manually before applying the algorithm. On the other hand, images with strong geometric shapes are not suitable in general for the seam carving algoritm.

Conclusions

I'd be most interested in hearing comments on the finding of other implementations.