Project 4 Writeup
Alex Collins (aecollin)
March 12, 2010
This project focuses on scene completion, using th Flickr image database to find suitable matching images. In general, this is the problem of having a source image and a mask specifying a part of the source image that we wish to elimante (replace with other content).
By comparing the source image to millions of potentially similar images, we can find a small subset (~100 images) that are fairly similar. We then iterate through this subset and find a suitable patch to fill th original source mask. Finally, the 2 images are recomposited and blended using Graphcut and Poisson blending.
Algorithm
My algorithm works by comparing the potential image matches to the image using a weighted Sum of Squared Difference (SSD) metric. The weights are determined from the proximity to the edge of the source mask, so that pixels right on the edge are considered very important, and pixels that are far away are not considered to be important.
By implementing this 'alpha mask' idea into the computation, the overall scene completion does not take bery long at all, and can process an individual image and match in about 5 seconds.
The images are compared at different offsets by using a Gaussian Pyramid, and the overall best shift is chosen. The algorithm then uses the Graphcut routine (from project 3) to find the minimum weight seam between the source and match images. Finally, Poisson blending is applied to make a smooth blend.
Scoring each potential match: To score each potential combinations I simply added the max_flow from the Graphcut routine to 200x the best shift SSD score. This was chosen because it allows for both scores to be scaled so that they are on the same order of magnitude. It would be interesting to look at different scoring metrics, however time constraints did not allow for me to do this.
Discussion of Results
The algorithm's performance significantly varied depending on the image. For images with a high amount of semi-random texture (water, forests, etc), the algorithm does a very good job at blending th two images together seamlessly. However, for images with high-contrast edges (ie the last example given below), it is difficult to find an extremely satisfying blend, and so our algorithm does not perform well.
Results
Here we see the algorithm inputs (Source and a weighted mask), and the output composited image
