Latest Comments
Search
« Moving to California | Main | Python »

Liquid Resize

One of the talking points of SIGGRAPH has been Liquid Resizing, also known as seam carving/removal or content aware image resizing.

Check out the YouTube video demonstration, and then read the paper [http://www.faculty.idc.ac.il/arik/imret.pdf]. While the effect is visually impressive, the mathematics and concept are surprisingly simple and easy to explain.

There are "uninteresting" parts of an image - these occur when nothing in particular is present at a pixel. There are numerous measures we can use to detect this, but one simple function is edge detection. If there are no edges (i.e. transitions to other objects) around a pixel, that means nothing is there! This is easily computed using the intensity gradient, which is a fancy way of saying I(x) = 0.5*I(x+1) - 0.5*I(x-1), where I(x) is the intensity of the pixel at location x. Using dynamic programming, it is computationally tractable to find the minimum energy seam where energy is just the intensity gradient, and a seam is a 1-pixel width line from one edge of the image to the other edge (can be vertical or horizontal). This minimum energy seam can be thought of as the most "uninteresting" single-pixel line in the image.

To downsize the image by width, delete the most "uninteresting" vertical seam. We surely will miss it the least of all the vertical seams present in the image. Likewise, to reduce the height of an image, remove the minimum energy horizontal seam. We repeatedly remove such seams until the desired dimensions are reached.

The word "easy" is thrown around too often

It's really simple. I spent one morning coding it up in Python using PIL and numpy, and the source code is available here. (Disclaimer: It's slow.)

To resize an image to width 100 pixels and height 200 pixels and preview it:

import liquid
liquid.resize("test.jpg",100,200).show()

An example

Let's see an example. Start by using an image from flickr - "a man, a whale, a beach"
a man, a whale, a beach - medium

We can take a look at some of the low energy seams, which seem roughly correct.
a man, a whale, a beach - seams

We now proceed to remove seams to resize from 373x500 pixels to 249x249 pixels.
a man, a whale, a beach - resized

Not bad not bad - The man, most of the cloud and the wave on the right are largely preserved. This is all the more surprising because the algorithm has no concept of "man", "cloud", "whale" or "wave"! It's simply looking for seams with as few "edges" as possible (in a manner of speaking).

It's also possible to resize the image larger. We do this by inserting averages of pixels beside minimum energy seams instead of removing them.

1. Find minimum energy seam. (Horizontal or Vertical depending on which dimension to lengthen)
2. Insert a 1-pixel seam beside (left or right is fine) minimum energy seam and set the pixel value to be the average of the adjacent pixels.

Let's try that on our man, whale, beach picture:
a man, a whale, a beach - resized

Ah well. I really should be getting back to work.

Reader Comments (1)

This algorithm is really cool. What would you think about an ActionScript implementation? IMHO it would have remarkable advantages:
the "optimal" display size of on image is really known only on the client machine. Windows can be resized all the time and having the server resize the image would place much load on the server.
A flash box could be relatively sized with css, and Flash + AS powered liquid resizing could put a new image in the box each time it is resized.
My 2ยข

November 21, 2007 | Unregistered Commentersilviot

PostPost a New Comment

Enter your information below to add a new comment.

My response is on my own website »
Author Email (optional):
Author URL (optional):
Post:
 
Some HTML allowed: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <code> <em> <i> <strike> <strong>