Programming Project #2 (proj2)
15-463: Computational Photography

Seam Carving
Due Date: 11:59pm on Wed, September 24, 2008

Overview

One of the recent papers at SIGGRAPH that made news was Seam Carving for Content-Aware Image Resizing by Shai Avidan and Ariel Shamir. In this assignment, you'll be implementing the basic algorithm presented therein. To wit, you'll be designing a program which can shrink an image (either horizontally or vertically) to a given dimension.

Details

For a brief overview of the algorithm and some inspiring results, check out the video. Your algorithm will shrink images as follows:

1. Determine the 'importance' of each pixel has using an energy function.
2. Until image has shrunk to the desired dimension:
   1. Find the lowest-importance seam in the image.
   2. Remove it.

Feel free to use any energy function in the paper (or cook up something on your own). Defining a good energy function seems to be the key to achieving good results.

Seam examples. Black: horizontal seam. Gray: vertical seam. Blue: not a seam -- contains more than one pixel from some columns.

A horizontal seam is a connected path from one side of the image to the other that chooses exactly one pixel from each column. (A vertical seam is the same, but from top to bottom and with rows.) Finding the lowest-importance seam is a simple dynamic programming exercise. If you find yourself spending large amounts of time on it, please ask the course staff for help.

Your final code should be able to, given an input image, produce an output image shrunk by a given number of pixels either in width or in height (but not both at once!). A simple way to achieve this goal is to write your code to shrink only in one dimension and then create a wrapper function that transposes the image to shrink in the other dimension.

Example: Horizontal Carving

Example: Vertical Carving

Notice how the content in the image is preserved, and the large, boring, area of asphalt is removed. (This does ruin the composition, but such is life.)

Example: Carving Artifacts

As you push the algorithm to its limits, artifacts -- such as shape distortions and odd cubist angles -- will begin to crop up. A lot of time on this project will be spent tweaking your code to mitigate these effects, as well as searching for pictures which don't exhibit them. Generally, highly-structured scenes and human faces will suffer, while scenes with textured objects on simple backgrounds will work better.

Bells & Whistles (Extra Credit)

Try some special moves to up your multiplier, chain a longer combo, and increase your score:

• (5 points) Make it fast. Divide your function into a precompute section and an on-line section. The on-line section should be able to produce a resized version of an image very quickly (like in the Seam Carving video).
• (10 points) It seems that some energy functions may be better than others for certain scenes. Implement two energy functions which produce good results on different kinds of images. Propose and test a heuristic to select the correct energy function for an input image.
• (10 points) Add "optimal" diagonal resizing as described in the paper -- that is, find the optimal ordering of horizontal and vertical seams to simultaneously achieve a given width and height.
• (10 points) Stretch images using seam insertion.
• (10 points) Remove objects using seam carving and seam insertion.
• (7.24 points) Compose and photograph an engaging scene. Seam carve your masterpiece to a smaller size. Use The GIMP or similar along with your enormous (compared to matlab, at least) human brain to do better. Don't limit yourself to simple cropping or scaling -- use cloning, reposition objects, and generally go all-out.

Deliverables

The project will be graded out of 100 points, with points allocated as noted below and above. Use the proj2/www and proj2/code folders, as described in the submission instructions.

Code: Please supply the all the code you used to generate your results, along with a README file or sufficient comments to allow us to test it out. (Basic seam horizontal and vertical carving is worth 50 points for those in the undergrad version of the class, 30 points for the grad version. On top of this base score, you will earn points for your report [see Web below].)

Web: Create a project page to showcase your results. By now you know the drill: simple html, nothing too complicated. Please:

• (30 points) Include lots (six or more) great examples of resized images (either from yourself or the internet, but remember to attribute!). Show us your implementation works.
• (N points) Dazzle us with any bells and/or whistles you've added in.
• (20 points) Once we're riding high on your success, calm us down with some examples of where your code doesn't work.
• Make sure to tell your story with weighty words as well as potent pictures.

NOTE: Your example images don't need to be larger than the above examples (i.e. around 500x500 pixels).