Table of Contents
Background
Image resizing allows us to display images on various media and display sizes. Scaling and cropping are two methods of image resizing, but each have downsides. Scaling will stretch or compress the contents of the image and make them look ugly. Cropping may cut out important subjects in the image. Enter seam carving. One of the recent papers at SIGGRAPH that made news was Seam Carving for Content-Aware Image Resizing by Shai Avidan and Ariel Shamir. Seam carving allows us to remove parts of the image that contain the least entropy—the least important parts of the image. This allows us to resize images while preserving the context of their contents. reddit, a popular social news website, uses a simpler version of the algorithm presented below to automatically crop thumbnails of user-submitted content while preserving the important part of the image.Algorithm
The algorithm repeatedly removes seams from the image until the image is the desired size. We measure the gradient magnitude of the image, averaged across all color channels. Then we apply a dynamic programming algorithm to find the seam that contains the pixels with the lowest entropy. That seam is then removed from the image. To enlarge an image, we need to insert seams. Using the same algorithm, we compute the lowest entropy seam. We then insert a seam containing the average of the neighboring pixels of that seam. The reddit algorithm differs in that it only removes seams from one of the four edges of the image, and that the seams are always straight lines.Results
Notice how my legs and the mountains in the background are squeezed together.
An example of image enlarging. Unfortunately, the same seam tends to be the lowest entropy seam through every iteration.
My friends and I don't have high enough entropy. Ouch!
Sources
All photos are either my own, from the project page, or the following sources:http://www.travelpod.co.uk/travel-blog-entries/reverie/1/1264464976/tpod.html
http://en.wikipedia.org/wiki/Seam_carving
http://www.ramblingtraveler.com/2009/05/new-york-city-subway.html