Content-aware image resizing by seam carving

This is a classic, or, as much of a classic as a 3-year-old graphics paper can be.

Seam Carving for Content-Aware Image Resizing (Avidan and Shamir, 2007) describes a technique for resizing photographs along one dimension in a way that allows the aspect ratio to be changed while reducing the amount of distortion in perceptually important parts of the image. Watch the video, if you haven't seen this before:

Youtube link

The algorithm translates into identifying the shortest path in a DAG and it can be easily implemented by a dynamic programming algorithm. As Dmitry pointed out to me some years ago, this makes an ideal teaching example for dynamic programming, for a number of reasons. The algorithm is easily visualized because the space of values to be computed maps straightforwardly onto the pixels of the image. Both the naive exponential-time algorithm (testing all 3^#rows paths) and the dynamic programming algorithm are fairly easily expressed without too much additional machinery. And, unlike most classroom dynamic programming questions I have encountered, which seemed either banal or contrived, the applications of this one are visually appealing and fairly interesting. For example, as someone pointed out to me, it makes the fallout of breaking up much easier to deal with.

Before... and after (Source: video, above)