Project 3
Rudy Sandoval (rudy)
February 26, 2010
This project is an implementation of Graphcut for use in combining two images. When attempting to combine images, there is usually an optimal border around the source image that would make your resulting composite more believable. Graphcut attempts to find this seam using a max-flow/min-cut algorithm to decide which overlapping pixels should belong to which image. By representing each pixel in an image as a node in a flow graph, we can define relationships between pixels as edges. In our instance, we are looking at the sum of squared differences between a pixel and its neighbor in both images across all three color channels. This comparison metric is as follows:
 |
Where s and t are a pixel and its neighbor and A and B are two images with overlapping boundaries. Graphcut searches along this overlap looking for the best possible cuts between pixels, and then reassigns pixels to either A or B. The results of the graph cut algorithm are shown below. This algorithm requires either specific types of source and target images, where the desired area is surrounded by low gradient values in the source image and high gradient values in the target, or well laid out masks defining a large amount of constraints for max-flow/min-cut. Overall, the desired cut and the optimal graphcut were very rarely the same. In some instances, the optimal cut looked better than the one initially desired, but this was a rare case in my testing.
- Extra Credit Extension #1: Using my Graphcut code, I performed a very simple texture synthesis on an image of leaves. Using 5 duplicates of this image shifted around, I performed consecutive graph cuts on the next source image and the previously composited target image. The results are below. Using the entire image for each shift has lead to some visually apparent cloning. A much better approach would have been to take semi-random patches from the original image and attempt to graphcut those together.
Results Images
Texture Synthesis
