Project 4: Scene Completion Writeup

Scene completion using millions of photographs

Scene completion by searching over a large image database has two basic components

In this assignment we were already provided with the nearest neighbors. For finding the best fitting patch I did template matching. As suggested by Hays and Efors'09, I extracted a patch (80 pixels wide) around the missing region. This patch was then compared to all other possible patches in the nearest neighbor images. Instead of using the SSD difference between the patches, I compute the average RGB value of the patch and use that to find similar patches. The choice of using the average patch value was governed primarily by the fact that designing a convolution filter for computing the average is trivial. My strategy to deal with the massive search over the nearest neighbors was to brute force it. Since the operations are massively parallel I offloaded all the computation to the department cluster which ran a total of 51*120*3 convolution operations. The output of the convolution operation is an image which contains the average patch value at each pixel with the patch mask centered at that pixel. Finding the optimal patch, now boils down to simply finding the location where the difference between the convolution result and the statistics of the reference patch is the least.

patch 80 pixel wide patch corresponding mask
Target Image Patch Convolution Mask

Once the optimal patch is found the corresponding graph cut needs to be computed. To find the optimal seam I minimize the SSD between the source and target images along with a distance penalty (k*distance(p,hole))^3, as suggested in the paper. The distance penalty encourages cuts closer to the hole.

Results

Here are some of the cases where the algorithm works reasonably well. All the results shown are without any blending.

test set test set test set test set
test set test set test set test set
test set test set test set test set
test set test set test set test set
test set test set test set test set
test set test set test set test set

And here are some spectacular failures. A large number of errors are because I compare average patch statistics and not the SSD between patches. Firstly, by comparing just the patch mean I end up throwing away all spatial relationships which is a bad idea. Secondly, whenever the patch contains a variety of colors, the average color of the patch isn't a very relaible statistic of the patch and as a result the matches are not very good. In city scenes, with lots of small objects of various colors this effect is particularly visible.

test set test set test set test set
test set test set test set test set
test set test set test set test set
test set test set test set test set

Multiple completions can be generated by finding many close patches instead of just one. These matches are sorted on the basis of their similarity to the reference patch. Here is an example where 5 completions were generated. The completions are presented in decreasing order of their similarity with the reference patch.

test set test set test set test set test set

Auto Colorization

For extra credit, I tried out the auto colorization scheme suggested by Torralba et al. Here are the results:
test set test set test set test set
test set test set test set test set