Image resizing using energy paths
September 14, 2007 – 12:54 pmIt’s good to be subscribed to lots of different mailing lists, just for the absolutely wonderful pockets of air which exist around all the traffic. On the kde-imaging mailing list there was a thread about image resizing algorithms. My interest was piked and it paid off - the video explains a dynamic image resizing technique by removing paths of least enery. This is probably done by some complicated Fourier transform, and the results are phenomenal. Resize an image by removing redundant parts of the image, not by making everything smaller. Furthermore, this technique can be also used to remove particular elements of an image by applying negative energy weights to an area. Fascinating!
Planet KDE readers: The embedded video doesn’t show on p.k.o, so you can just watch the video here
Update: The original work is done by Dr. Ariel Shamir and Shai Avidan from the Efi Arazi School of Computer Science in Israel.
13 Responses to “Image resizing using energy paths”
Wow, that makes me feel really dumb. Great informational video Seb.
By Wade on Sep 14, 2007
Wow! this is the most amazing thing I’ve seen in imaging in years! Simply wow! Like, speechless wow. I think I’ll have to publicize this a little more…
By Troy Unrau on Sep 14, 2007
First of all, this *is* really cool. I first heard of it on slashdot a few weeks ago, then it was brought up in a comment on the dot.
I looked into it in detail (read the paper), and it’s actually fairly simple. They use a standard 2D diffusion PDE as the energy function (they tested others, but that worked best), and simple recursion to find the path which removes the least energy.
Unfortunately, because of the PDE and recursion, it takes a long time, and probably at least twice the memory as a regular picture. performance could be improved by only taking the energy function once at the start, and caching each path as it is removed. Adding columns would be more complicated, as it involves duplicating (with averages) the paths in the same sequence as they would be removed.
For calculating paths alone, an X by Y image would involve about X*(3^Y) comparisons
There was a stab at it using QT that took shortcuts on the calculations (only diffusion by row), didn’t use connected paths, but did recalculate energy (inaccurately) every time, and there was noticeable lag for each row removed.
The way Dr Shamir and Avidan got around the performance issues was but creating a new multi-sized image format, storing all the seams that get removed in the file. So, if we were to created a widget, it would involve working with additional information to the image, and precalculating the transformations.
However, I do see it working well as a filter for Krita, or some other image editing software.
Sorry for the long comment.
By Soap on Sep 14, 2007
There have been a number of implementations already. The algorithm is really very simple; the first third-party code appeared only a day or so after the paper was presented at SIGGRAPH. For one example (amongst many) see: http://inamidst.com/code/seamless.c
It would be great if this could be worked into existing platforms; especially browser renderers like WebKit and Gecko.
By Joe Geldart on Sep 14, 2007
Amazing!
By fish on Sep 14, 2007
there’s also a wish request about this for digikam: http://bugs.kde.org/show_bug.cgi?id=149485
It would be nice have it integrated directly in kde, so every application can use it without programming it every time. What do you think?
By cover on Sep 14, 2007
This is very experimental and the energy functional has to be choosen vere carefull, otherwise you’ll get really silly results. This is nothing to integrate in an everyday applications, but a nice toy for geeks to play around in an image manipulation program. And I’m afraid that even there it is of limited use if the image is a little bit more complex. Always remember: these are promotional videos of scientific groups who are always in need of new funds.
By furanku on Sep 14, 2007
@furanku:
I’ve seen many other implementations already (check youtube), also by some hobyists and totally independent hackers. Seems to work very nice. Gimp already has a plugin which seems to work great.
So I don’t think this is of limited use, and I’d love to see Konqueror being the first to support this!
By jospoortvliet on Sep 14, 2007
@jos: awesome i’ll have to check out that gimp plugin!
By Seb on Sep 14, 2007
This has been asked for in DigiKam for a while now. Vote for it:
http://bugs.kde.org/show_bug.cgi?id=149485
By Louis on Sep 15, 2007
Realy awsome, tehnology is advancing so fast. Altough how the program resized the images was obvious. Guessed it before you started explaining.
Can’t belive some apps still don’t eaven use smart imageing!
By Joosep Parts on Sep 16, 2007
Hey Seb, this is Andy from uni. I just was just stalking you for a little bit, and thought you’d be interested in my site, which has an implementation of this algorithm, which some guy took and turned into a QT app.
Relevant pages are:
http://www.ultra-premium.com/b/photos/resize.html
http://www.ultra-premium.com/b/news/source_party.html
http://www.ultra-premium.com/b/news/resizer-gui.html
Hope you are well
Andy
By Andy on Sep 18, 2007