Project 3 Writeup

Algorithm

This project implements the graphcut algorithm from the paper ("Graphcut Textures: Image and Video Synthesis Using Graph Cuts", Kwatra, et al.). The algorithm takes as input:

• A source image and a mask specifying pixels that MUST come from the source image
• A target image and a mask specifying pixels that MUST come from the target image

And finds the minimum seam between the two images. The output is a composite image of the 2 input images as well as a mask specifying the found minimum seam. The algorithm works by creating an undirected graph of the 2 images, where edges refer to neighboring pixels and edge weights correspond to gradient information. A max-flow analysis is then executed on this created graph and the input masks, and each pixel of the output image is assigned a value specifying if its information comes from the source or target image.

Discussion of Results

I tested the algorithm on the 5 given images, as well as 5 image pairs of my own. In many cases, the minimum seam found by the algorithm was slightly jarring (see the ski jumper). Furthermore, this algorithm does not attempt to blend the two images together along the seam, it merely composites the input images. This makes the composition very noticeable, since any color differences are blatantly noticeable.

I decided to correct this problem by using the Poisson Blending from project 2 to blend the two images together after they have been composited by the graphcut algorithm.

Extra Credit

• I used Poisson blending to blend the images together after they are composited. This made the seam between the two images much less noticeable (see below).

Results

Comparing images with only graphcut used (Left), and images that have been blended using Poisson Blending after graphcut is applied (Right)