Project 3: Graphcut Images

cs195-g: Computational Photography	Patrick Doran
Spring 2010	pdoran

Directory

Home

Algorithm

High level description of the algorithm.

1	Reshape the source, mask, and target so they all have the same dimensions.
2	Create a sparse matrix that is #pixels x #pixels. This is an adjacency matrix whose values are the weights of the edge between pixels. It is the sum of squared differences of the source and target pixel plus that of the adjacent pixel.
3	Create a sparse matrix that is #pixels x 2. The values here are the cost of assigning the pixel to each label. Any pixel that is a graph source is assigned a large value in the first column. Any pixel that is a graph sink is assigned a large value in the second column.
4	Solve the min cut problem using the supplied code.
5	Repeat for each color channel and combine.
6	For smoothness on the edges, apply poisson image blending using the mask generated by the min cut algorithm.

General Comments

The algorithm assumes that the color of the edges of the source image is close to that of the edges of target. This assumption means that when the colors don't match nearly, the minimum seam between the source and target may not be the desired seam. Often, the minimum seam around the source may be desired first, then the seam between the source and target.

Bells and Whistles

Applied poisson image blending to the composited image. Created an interactive tool for choosing a mask for an image. Supplied it as the stencil for Poisson Image Blending as well as this project.

I also did panorama stitching. It doesn't work that well because I didn't do any aligning, but the images are composited quite well. It works by treating the left edge of the first image and right edge of the second images as the source and sink respectively. Then the images are graphcut and poisson blended. This process is repeated for each image in the panorama, using the previously created composite as the first image in each step.

Results

Source	Target	Composite	Poisson
Mask	Mask	Mask
Mask	Mask	Mask
Mask	Mask	Mask
Mask	Mask	Mask

Source	Panorama
Image 1 Image 2 Image 3 Image 4
Image 1 Image 2 Image 3 Image 4
Image 1 Image 2 Image 3 Image 4