Below is an interesting paper and video on a technique for “retargeting” images to a new size.

Rather than simply stretching or cropping the image, this technique works by successively removing “uninteresting” seams from the image. (A seam is a connected path of pixels in the image; an uninteresting seam is one that minimizes the total difference in energy between itself and adjacent pixels.) The paper presents a simple dynamic programing algorithm that builds up the seam a pixel at a time, running in time proportional to the number of pixels. (Transforming a small image takes a couple of seconds.)