# CS 195-G: Graphcut Images

The goal of this project was to implement the graphcut algorithm of Kwatra, et al. using the Maxflow library.

## Algorithm

### Basic Algorithm

 The source image The target image

This algorithm merges a source image and a target image given pixels that must be in the source image and pixels that must be in the target image.  In this example it will use the gravel from the source image to replace the watermarked gravel in the destination image.  To select the regions from the source image and the target image that are constrained, a third mask image is needed.  It is yellow for pixels that must come from the source and blue for pixels that must come from the target.

 The combined mask Yellow = source imageBlue = target image

The image can be interpreted as a connected graph where nodes are pixels and each pixel has an edge to up to four neighboring pixels.  Edge weights are based on the difference between adjacent pixels.  The basic cost function for each edge is the sum of squared differences of the source and target images at both the current and neighbor pixels:

s = current pixel, t = neighboring pixel
A = source image, B = target image

If we create two extra nodes, called the source and the sink, we can then add constraint edges to either the source or the sink which constrain pixels to either the source image or the target image.  These edges have infinite weight so they don't get cut:

A graph for a 3x3 image

The optimal seam is then found by solving the max-flow/min-cut problem.  This gives us a list of all pixels in the source and all pixels in the sink.  From that we construct the composite mask which is then used to combine the source and target images:

 The composite mask The final image

### Improved Cost Function

The cost function used to weight the edges of the graph can be improved by making edges have lower weights, so they will be more likely to be cut.  The cost function I used involved dividing by the gradients of both images:

s = current pixel, t = neighboring pixel
A = source image, B = target image
M(s,t,A,B) = old cost function (above),
GA(s,t) = gradient of A from s to t,
GB(s,t) = gradient of B from s to t

The new cost function greatly improves the way the algorithm treats object boundaries:

 The source image The target image
 The combined mask Without new cost function With new cost function

## Results

All of the images below use the improved cost function.

### Project Images

The jet image didn't work out so well because the outline had to be specified fairly precisely.  This could have been because the clouds and the mountainside are both relatively constant, so the edge weights are also pretty constant and it makes little difference exactly where the cut is.

 The source image The target image The combined mask The composite mask The composite image

In the pool image, the algorithm correctly found the outline of the bear with very little input.

 The source image The target image The combined mask The composite mask The composite image

The rafting image worked out pretty well.  The black background that ended up under the trees is the only visible artifact.

 The source image The target image The combined mask The composite mask The composite image

The mountain hut image worked out well too.  The algorithm didn't need much input to pick a seam through the water.

 The source image The target image The combined mask The composite mask The composite image

### Other Images

All of my images take a texture and stretch it by merging it with a copy of itself shifted to the right.  This is what graphcut is best at; combining images with a lot of texture and very little structure.  Images like the ones below can all be trivially merged without any visible seams.  Other images, like images of brick walls, will not work well with graphcut because there is too much structure.  To merge two brick walls, you would have to painstakingly align both images or the merge would look very out of place.

In this image the basket of kittens is stretched to one and a half times its width by merging it with itself.  It worked out pretty well, but you can unfortunately see the seam because of the edge of the basket.

 The source image The combined mask The composite mask The stretched image

In this image the school of fish is also stretched to one and a half times its width.  It worked out perfectly; the seam is almost impossible to find.

 The source image The combined mask The composite mask The stretched image

In this image the flock of geese is stretched horizontally.  The seam is pretty tough to find, although there are a few partial geese in the middle.

 The source image The combined mask The composite mask The stretched image

In this image the flock of flamingos is also stretched horizontally.  This also worked flawlessly; the seam is virtually invisible.

 The source image The combined mask The composite mask The stretched image

In this image the pond of lilies is stretched horizontally, and is perfectly seamless.

 The source image The combined mask The composite mask The stretched image

In this image the crinkled piece of paper is stretched to one and a half times its width.  It looks like one continuous sheet of paper.

 The source image The combined mask The composite mask The stretched image

In this image I tried to stretch this crowd of redheads, but it didn't quite work out.  Check out that face!

 The source image The combined mask The composite mask The stretched image