Seam Carving

I stumbled upon a video today that shows an amazing image processing tool that allows for rescaling an image with minimum distortion. By minimum distortion I mean the main features are preserved by the operation, whereas more redundant parts are suppressed (or augmented) to make for the size difference. This is best illustrated by two still frames from the video:

 

In both still frames you can see the original image on the upper right of the frames, and its scaled versions on the lower left. Note that the two persons in the image keep their apparent sizes and shapes. The video has many more examples.

This is a pretty interesting image manipulation. I wonder, though, how much computing processing power and memory you need for these operations?