image equation

Project 3: Graphcut Images

Compositing along the minimum seam between two images (Kwatra, et al.; Website).

Due Date: 11:59pm on Friday, February 26th, 2010



You are required to implement a graphcut algorithm as well as take your own photos and apply your algorithm to those images to get full credit.


MATLAB stencil code is available in /course/cs195g/asgn/proj3/stencil/. You're free to do this project in whatever language you want, but the TAs are only offering support in MATLAB. One file supplied is fiximages.m which automatically resizes and moves all the images so that one could easily composite them. The stencil code is set up to do this immediately. Feel free to use or ignore this function. Another file getmask.m will allow you to interactively make an image mask.

When compositing two images, it is often a goal to combine them along a seam (series of pixels) that has the minimal difference between the two images, hereafter referred to as the optimal seam. For this project you will be implementing an algorithm that finds the minimal seam between two images.

If you've taken a graphics course at Brown, you've probably heard of Seam Carving. You may have even implemented it. That algorithm uses dynamic programming to find the minimal seam of an image along a specific dimension, and then remove it. Unfortunately, that doesn't generalize as well to finding seams that are not along a single dimension.

graph cut

An algorithm called Graphcut (website), was created to address this problem. The algorithm works by formulating the image as a connected graph with edge weights based on the difference between neighboring pixels. This graph is then treated as a max-flow/min-cut problem where the sources are any pixels to be taken only from the first image and the sinks are any pixels to be taken only from the second image.

It's quite simple to formulate the optimal seam search as a max-flow/min-cut problem too. You can easily represent the image graph as an adjacency matrix while each entry in the adjacency matrix can be the flow (or as the paper calls them, "constraint arcs"). The paper suggests using the sum of squared difference between the first image and the second image plus the sum of squared difference of the first image and the second image at the neighboring pixel.

graph cut

You will also need to represent the source and sink edge weights in this problem. One solution is to use a mask that signifies that any pixel under the mask must come from that image. The terminal weight for those pixels is set to infinity (or a large value).

Once formulated, you can solve the max-flow/min-cut problem and the output should be a labeling of the pixels as belonging to one side or the other. This is effectively a new mask for the image that you can use for compositing.

The stencil includes a mex compiled max-flow/min-cut algorithm that runs fast and requires a specific type of input. The source code for this can be found here: Maxflow. You are not responsible for implementing a max-flow/min-cut algorithm; this course is not cs157

Write up

For this project, just like all other projects, you must do a project report in HTML. In the report you will describe your algorithm and any decisions you made to write your algorithm a particular way. Then you will show and discuss the results of your algorithm. Also discuss any extra credit you did. Feel free to add any other information you feel is relevant.

Extra Credit

You are free to do whatever extra credit you can think of. The paper has many suggestions: texture synthesis, video synthesis, etc. Another possible extension that one of the TAs has done is a simple panorama stitching (assuming that all images are aligned and have identical overlaps) using Graphcut to find the seam and Poisson blending to make the seams less apparent. The TAs recommend that you hold off on the more advanced versions of the mentioned extra credit, especially patch-matching texture synthesis and panorama stitching as they will appear in later projects.

Graduate Credit

You must do at least 1 form of extra credit to get graduate credit.

Handing in

This is very important as you will lose points if you do not follow instructions. Every time after the first that you do not follow instructions, you will lose 5 points. The folder you hand in must contain the following:

Then run: cs195g_handin proj3
If it is not in your path, you can run it directly: /course/cs195g/bin/cs195g_handin proj3


Final Advice


Project derived from Kwatra, et al.; website.

Good Luck!