Seam Carving - Content Aware Image Resizing

Sometimes we have an image too big and we want to re-size it. Until recently we had two ways to handle this problem: scaling or cropping. Both techniques present drawbacks, in particular scaling leads to unnatural distortions, and cropping entails lost of content.

In 2007, Shai Avidan¹ and Ariel Shamir² presented an algorithm, called Seam Carving or Content Aware Image Resizing³, capable or reducing the size of an image, in a content-aware manner, that is without removing important information from the image itself.

Given as input an image and a target size the algorithm proceeds removing connected straight paths of unnoticeable pixel that blend well with their neighbors. The paths selection is based on an energy function, in my case a Sobel Filter, computed over the image. Once it has been given an energy value to each pixel, as the next step, the algorithm uses dynamic programming to find the minimum cost path connecting the image from top to bottom or left to right depending on the dimension we are reducing. This is really similar to what has been done by Alexei Efros⁴ in Image Quilting for Texture Synthesis⁵, where he uses the same dynamic programming algorithm to cut the boundaries of overlapping blocks of textures. 

Finally the pixels that are part of the selected path are removed generating the final result.

Original image by SBA73, http://www.flickriver.com

Left: scaled image. Right: seam-carved image.

Original image by TJP, http://interfacelift.com

Horizontally seam-carved image.

References:
¹Shai Avidan, Mitsubishi Electric Research Labs (MERL), http://www.shaiavidan.org
²Ariel Shamir, Interdisciplinary Center and MERL, http://www.faculty.idc.ac.il/arik/site/index.asp  
³Seam Carving, http://www.shaiavidan.org/papers/imretFinal.pdf
⁴Alexei Efros, Carnegie Mellon University, http://www.cs.cmu.edu/~efros
⁵Image Quilting, http://www.eecs.berkeley.edu/Research/Projects/CS/vision/papers/efros-siggraph01.pdf