Saturday, October 20, 2007

Objective Evaluation of Seam Carving

Recently, I've blogged on some experiments I've done to investigate the seam carving algorithm. In particular, I wanted to test the algorithm against some real-world images with different reduction factors. The idea was to find in which conditions the algorithm performed best and in which it performed worst, and although I used a specific implementation, the gimp plug-in developed by Carlo Bassaldi, on the images, I did run a few of these images through other implementations (especifically, Andy Owen's implementation and a Java one) to verify the results (they gave the same result).

Wolfger has also blogged on the algorithm, later giving an update stating that the gimp plug-in seemed to be worthless. Since I used the plug-in a lot and found it quite useful, I left a comment stating that, in my opinion, the plug-in was not worthless, to which he answered

"The horse pic on your site demonstrates why I called the Gimp plugin worthless."
and finished saying
"So it’s far less useful than it ought to be. Can we agree on that?".
Well, no, I'm afraid we can't agree on that since the plug-in does allow to preserve important areas in the image, as I've shown later in the blog for the same image he mentioned. I guess he didn't make to the end of the blog, although on his defense I must say the post was a long, albeit (in my opinion) interesting, one, and you had to have more than a fleeting interest on the algorithm to read it all.

For the mark, I'd like to reiterate that the gimp plug-in is not only NOT worthless, but in fact it is one of the best implementations of seam carving out there that I've tried, both in performace and in flexibility. It's also very easy to use, especially if you have some basic knowledge on gimp.

As I said, the whole point in my previous blog was to explore the strengths and weaknesses of the algorithm itself, not of any implementation in particular. The conclusion I've arrived is that the algorithm is somewhat limited for most images, especially those with persons and animals, if done without assistance. By that I mean if you just run the algorithm on an image without marking down areas to be preserved (like human shapes) or areas to be removed prioritarily.

If, on the other hand, you take the time to give hints to the algorithm, you can get quite good results, although it may take more than one try, and it may depend on the image itself. This can be seen not only in the many sites throught the web, but also from the landscape image with a horse in the foreground shown in the previous blog entry.

You can see how different are the results by the images below, taken from the previous blog. At the left we have the original image, in the middle the one processed without any preserved area, and the last protecting the horse against any seam carving.

Original Image.
Seam carving with no protective mask applied.
Seam carving with a protective mask around the horse applied.
It's easily seen how much difference our interaction made to the end result. Using a protective mask for the horse actually ensures no seam which goes through the horse is removed, which guarantees the horse's shape in unaltered.

Why is this issue important? Because it makes automatic image processing with seam carving more difficult, not to mention applying it to video processing, as some have already considered. It is not that it is impossible to do a good job, but it certainly is far from trivial. And having a good notion of when and how seam carving can give good results is essential for someone deciding what is the best algorithm to apply in any circunstance. To ignore it makes anyone susceptible of easily falling for sweet talk.

Labels: ,

eXTReMe Tracker