# CS195G Project 4: Scene Completion

## Rudy Sandoval (rudy) January 29, 2010

This project is an implementation of Scene Completion using Millions of Photographs. Sometimes, we have a photograph that has some unwanted area we would like to erase. Many algorithms attempt to use information from that one photo to fill in any masked out area in hopes of creating a believable image. This project focuses on using other images, searched for and matched to our image, with the belief that within a vast database of photos taken by people, there are bound to be more than a few images close enough to ours to provide a reasonable replacement.
Using the gist descriptor, 120 matches were found for each image. From here, the neighborhood of the mask was scanned across each matching image, looking for the area with the smallest SSD between mask and match. Once this was found, the area was then graphcut and poisson blended into the source image. SSD was calculated in the fourier domain. Looking at the SSD equation, we can distribute the terms to go from sum(A - B)^2 to sum(A^2 - 2AB + B^2). Since B, our source image, will not be changing, it has no effect on choosing the minimum ssd value and will be removed from the equation. By adding in our mask, we now get sum(M*A^2 - 2M*A*B). Assuming our search window is precalculated as M*B, we now have sum(M*A^2 - 2A*B), which can be split into two sums and treated as convolutions, sum(M*A^2) - sum(2A*B) to conv(M, A^2) - conv(2A, B). When taken into the fourier domain, these convolutions are now just multiplications, increasing the speed at which we calculate the ssd. I split the matching images into two groups to handle memory capacity, then picked the best match from each group. Increasing the radius of my neighborhood lead to worse results, but the amount of time it took to run the algorithm prevented further testing.
• The more advanced heuristic for finding seams in graph cut was implemented. The comparisons are shown below.
• Comparing the ssd's of the images after applying a sobel filter, to focus on edge difference more than color difference.
• Poisson image fill was calculated for all images. The comparison is shown below.