Project 3: Graphcut Images

Ben Cohen (btcohen)
February 26, 2010

Algorithm

Graphcut Solver

For this project we were asked to use the Graphcut algorithm to composite images. Graphcut finds the minimum "cut" through the edges in a graph, which in this case represented the seam that would result in the least error when compositing the images. Although we didn't have to implement a Graphcut solver, we did have to generate the graph for the supplied solver to cut.

The solver takes an adjacency matrix representing the pixels in the image. Each pixel is connected to each of its neighbors by an edge with weight of |A(t)-B(t)| + |A(s)-B(s)| where A and B are the two images, s is the pixel and t is the neighboring pixel. It also takes an additional matrix which indicates which pixels are anchored to either the source or the target image. The solver then returns the mask indicating which pixels come from which image.

Masks

Instead of having the user input the mask for each image every time, I modified the code so that the mask for the source image is specified in an image file. The mask for the target image is the area of the target image that the source image does not cover.

Poisson Blend

For extra credit I used the Poisson solver from the last assignment to reduce the appearance of seams in the images. Once the Graphcut solver had produced a mask, it was passed to the Poisson solver along with the source and target images.

Results

The Graphcut solver worked very well for cases where the source and target images had similar colors and there wasn't much texture where you were trying to place the source image. In the first two required images, the algorithm preforms poorly since there is too much of a color difference between the source and target images. However for the third and fourth required images, there are areas of very similar solid colors (water in both cases), which allow for a good cut to be found. In all cases, applying a Poisson blend somewhat reduces the appearance of the seams.

Required Images

Graphcut Graphcut + Poisson

Additional Images

+
=

Graphcut

Graphcut + Poisson

In my first image, the solver finds a reasonable cut, but due to the color differences of the water, the resulting image has very visible seams; running this image thought the Poisson solver mostly corrects these discrepancies, making for a much more seamless image.


+
=

Graphcut

Graphcut + Poisson

In this image, the color differences between the sky in the two images causes the solver to be almost entirely unable to make a cut. Fortunately, the Poisson blending mostly corrects this (although it does leave the shuttle looking slightly ghostly).


+
=

Graphcut

Graphcut + Poisson

In this image, although the colors of the two lawns are fairly similar, they have drastically different textures, which makes the compositing very visible. Since the colors were already very similar, the Poisson blending doesn't help much.


+
=

Graphcut

Graphcut + Poisson

Since both the source and target images are similar in color and texture, the cut found by the Graphcut solver is almost seamless.


+
=

Graphcut

Graphcut + Poisson

Like the previous images, these images are fairly similar in color and texture so the compositing works well.