# 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

## Brief

- This handout:
`/course/cs195g/asgn/proj3/handout/` - Stencil code:
`/course/cs195g/asgn/proj3/stencil/` - Data:
`/course/cs195g/asgn/proj3/data/` - Handin:
`cs195g_handin proj3` - Required files: README, code/, html/, html/index.html

## Requirements

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.

## Details

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.

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.

- s = current pixel
- t = neighboring pixel
- A = first image
- B = second image

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:

- README - text file containing anything about the project that you want to tell the TAs
- code/ - directory containing all your code for this assignment
- html/ - directory containing all your html report for this assignment (including images)
- html/index.html - home page for your results

Then run: ` cs195g_handin proj3`

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

## Rubric

- +70 pts: Graphcut implementation
- +10 pts: Using at least 5 new images you have taken
- +20 pts: Write up
- +20 pts: Extra credit (up to twenty points)

## Final Advice

- A naive implementation will run slowly because of indexing into a sparse matrix. Test your algorithm on smaller images first.
- That part of the algorithm can be made significantly faster by finding all the adjacency matrix values ahead of time and then
constructing the sparse matrix; see
`sparse(i,j,s,m,n,nzmax)`

## Credits

Project derived from Kwatra, et al.; website.