Project 4 Writeup: Scene Completion
Basia Korel (bkorel)
March 12, 2010

This project entailed implementing an image completion algorithm that seamlessly composites an image containing a missing region with other semantically similar images. This is based on the Hayes, et al. paper, "Scene Completion Using Millions of Photographs"), however in this implementation we used hundreds, instead of millions, of photographs. The first part of the algorithm in this paper is to find semantically similar scenes to the query image; we were already provided a set of photos to match our query, so this step was not implemented. The second part of scene completion is local context matching which finds the best matching region in the match images to the local context around the query image hole. I defined the local context in the query image to be any pixels within an 80 pixel radius of the hole's boundary, as in the paper.
I utilized my Project 1 implementation, Image alignment with pyramids, to align the matching scene to the local context. Each image in the matching set is resized to the query image and an image pyramid was built for the query image, the local context mask image and the matching image. An (x,y) translation was applied to the matching scene with a certain window size, which varies based on the resolution of the image and are values I found most appropriate in Project 1. This implementation uses SSD as a metric to determine how similar two regions are, and I only considered pixels under the local context mask in both the query and match images into the alignment score. Once the best alignment has been computed, I utilized my Project 3 implementation to find the seam along which to composite the matching image into the hole of the query image. To ensure that graph cut finds the best seam close to the hole to try and preserve as much of the query image as possible, graph cut can find a seam only within the local context. Finally Project 2, Poisson blending, is used to actually composite the matching image and the query image along the best seam.
As extra credit, I computed Poisson Image fill for all query images. To implement Poisson Image fill, I used the same Poisson blending code except the the b column vector contains the value 0 for all unknown pixels instead of calculated values from mixed gradients of the target and source image. Poisson image fill my be a sufficient image completion method if the missing region in the query image is small or if the content in the missing region is all the same color and texture. However Scene completion using additional photographs has proven to be a superior image completion method for the holes in our query images; even if the composited image is not seamless, it may still be a believable photograph in many cases.

Source Image
Composite 1

Composite 2


Poisson Image Fill


Source Image