Liquid Resize
Wednesday, September 5, 2007 at 5:19PM 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"
We can take a look at some of the low energy seams, which seem roughly correct. 
We now proceed to remove seams to resize from 373x500 pixels to 249x249 pixels.
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:
Ah well. I really should be getting back to work.