By now most people have seen the youtube video below showing the use of "Seam-carving" for re-sizing images to fit a different pixel ratio.

It has definately caught the imagination of several developers, myself included, but before we start talking about my version, here is the video to catch up:

Since this video appeared a month ago (backing up a paper published at SIGGRAPH) there has been a rush of people coding their own versions, and a GIMP plugin (Liquid Rescale) released, so I thought I would post my version. Bear in mind that I have only spent a few hours on it, and it is not fast, but I have been focusing in optimising a pure-python version for portability. There is no GUI at the moment, but that should come soon.

Here is the origional image (under Creative Commons from Flickr member Tidewise Muse) - click on the images to view the full size.

And here is the same image only 150 pixels thinner after seam removal.

Notice that (in this case) the boats have be reduced in length, since the choppy waves create a high energy barrier. in the image, however this method still creates a better re-sized image than standard scaling. Note also that the middle boat has shifted left in the image, moving forwards relative to the boat on the left.

The algorithm I have written is a little slow, however when the GUI is done I hope to increase the percieved speed significantly, as well as some major speed increases in the actual algorithm speed.

I have run the code on two machines to test the speed, and these times are for an image which is 400px by 300px:

(running on a AMD 1900+ with 512 mb 400mhz RAM) and using the python module psyco - currently takes between 0.02 and 2 seconds (averaging around 0.1 seconds)
(running on an old, [slow] 500mhz laptop with 128 mb oldschool RAM) (no psyco) currently takes between 1 and 15 seconds per pixel width to be reduced (averaging about 4 seconds)

I hope people find this interesting, and I will (at some time in the next few weeks) be releasing this program, so add my RSS to your feedreader. If you are interested in some of the optimization methods I have been using for this then you can read the article I wrote this morning on the Viral Content Network development blog on 11 ways to optimize your python code.