Fast content-aware image resizing

A simple content-aware image resizer, quite small, readable and fast: over 6 times faster than the LiquidRescale GIMP plugin, which is written in C.

Implemented object removal and preservation.

Seam carving is a recently presented method to resize images "intelligently", by removing pixels of the image that carry little information. It can do things like turning this image into this one Go watch the video for more examples.

I first heard about content-aware image resizing using seam carving about one month ago, when I found this implementation written in Python that uses SciPy/NumPy, i.e., lots of C code.

I quickly reimplemented it in OCaml, obtaining an unexpected two-order-of-magnitude speed increase. This was slightly surprising because the Python version uses optimized extensions written in C, and Psyco should have brought the parts written in Python to at least one tenth of the native speed. In this case, the key, it turns out, was not the implementation language but the algorithm itself.

Seam carving is performed in three steps, executed iteratively (each run shrinks the image by one pixel):

• compute an energy map, where high energy regions correspond to detailed parts of the image that are to be retained
• find a minimum energy seam, i.e., a connected path which traverses regions of low energy. If you're resizing the image horizontally, you have to find a path that goes from the top of the image to the bottom.
• remove the pixels contained in the minimum energy seam. This tends to erase parts of the image with few details (low energy) and of little importance.

The authors of the original paper examined several image energy functions and found that simple ones, based on the gradient of the image intensity, work well. Both the Python implementation and mine used thus a Sobel filter *1. The difference lies in the way the energy map is updated after a seam has been carved. Whereas the Python version uses a fast C routine to apply the Sobel filter to the whole resized image (which has seen either its width or its height reduced by one pixel after the deletion of the seam), my code selectively updates the energy map only for the parts of the image that have been modified.

You can find my content-aware image resizing code here. The core algorithm takes around 200 lines, to which I had to add another hundred for the Sobel operator.

Another implementation, LiquidRescaling

It is only very recently that I found the GIMP LiquidRescaling Plug-in. Even though it uses a simpler edge detector (one that could run up to three times faster than Sobel in theory), it is over 6 times slower than my implementation. After a cursory read of the 2200 lines of code devoted to the render code, I believe the culprit is the heavyweight data structure used to represent the image. To be fair, some of the extra info is used for things my implementation doesn't do yet, such as energy biasing (this allows you to use another pixmap to indicate which regions are to be preserved). Still, I'm quite sure I can implement energy biasing on top of the normal energy computation without modifying the underlying image representation (a mere matrix of rgb pixels), with a very small effect on performance, and most importantly without making the common case (no biasing) any slower. My seam carving code is abstracted over the energy computation (it's a functor), so it shouldn't be difficult.

No Title - vruz (2007-10-01 (Mon) 08:47:40)

great job, Mauricio !!

mfp 2007-10-01 (Mon) 10:07:30

hey vruz

Allow me to quote from README.txt:

There's nothing particularly impressive about this implementation, and basically no claims to fame. There's however some value in it because it is quite small, readable and fast. Indeed, it is over 6 times faster than the GIMP LiquidRescale Plug-in on my machine.

This is quite straightforward code, but it avoids the mistake involving energy updates from the Python version, and performs much better than the GIMP plugin by virtue of the simpler data structure used for the energy map.

y - x (2007-10-01 (Mon) 09:58:45)

I have a slight problem... the scale of the images now look different the 2nd image doesnt have the same scale :/

Anonymous 2007-10-01 (Mon) 10:07:38

The scales are supposed to be different. See the video or the papers for more details.

mfp 2007-10-01 (Mon) 10:16:57

You can resize the image vertically in a second pass with the -vert option if you want to preserve the X:Y dimension ratio.

The cmdline can obviously be improved, but I didn't think anybody would really care.

Bigger - Anonymous (2007-10-02 (Tue) 17:29:11)

Can this program make images bigger w/out pixelating them?

mfp 2007-10-04 (Thr) 08:51:16

Not yet, I'm probably coding that soon.

mfp 2007-10-31 (Wed) 10:05:02

Done: Fast image enlargement through seam insertion in OCaml

Wow. - Aria (2007-10-05 (Fri) 09:42:12)

Nice work again!

Assissotom 2008-01-17 (Thr) 04:30:35

Keep up this great resource

Alisa 2008-02-26 (Tue) 09:48:22

National Transportation Safety Board recently divulged they had funded a project with the US auto makers for the past five years.

Funny result - Sebastian (2007-10-06 (Sat) 05:31:03)

If you'd like to see a funny result, compare to

mfp 2007-10-07 (Sun) 05:49:37

hah a long legged dog

This is the sort of images that need energy biasing for object preservation.