Project 3: Graphcut
Tristan Hale (thale)

Overview
The goal of this project was to find a good-looking seam around an image to serve as a mask for pasting it into another image. It is similar to the concept of seam-carving, except that we are looking for a path around the whole object, rather than just a one-dimensional path through the image.


Algorithm
I implemented the Graphcut algorithm outlined in the paper by Kwatra, et al. The algorithm is a simple implementation of max-flow/min-cut, where the source and sink are the two images. The cut is made along the optimized edges according to the valued assigned by the function:
M(i_0,j_0,i_1,j_1) = (S(i_0,j_0)-T(i_0,j_0))^2 + (S(i_1,j_1)-T(i_1,j_1))^2
This is the sum of squares difference between the source and target images at the two points.



Results
The first two images didn't turn out too well. The graphcut algorithm finds a hard edge on the target and cuts there, but it leaves a large amount of "empty" space on the source. The jet turns out particularly badly. Some of the jet gets cut off, and a lot sky above the jet is left in the mask. The simple solution to this problem is to specify that those parts of the target should be in the target mask.
The remaining two images worked out as expected. The algorithm found a good seam and the two images composite pretty well.
Here are some resulting images. I show the generated mask, the composited image, and then the image blended using the Poisson blend from the last assignment.


Generated Mask
Composited Image
Blended Image














And here are the composites using my own images. Again, the results were mixed. But after blending, some looked pretty good.

Generated Mask
Composited Image
Blended Image