Project 4: Scene Completion
Tristan Hale (thale)

Overview
The goal of this project was to fill in missing information of a source image with a piece of another image, picked from a large database of images. We were given 120 images to use for each source image. I ended up using just 80 matching images per source image due to memory constraints.


Algorithm
I used a combination of the previous three projects. I first cropped and scaled the match to be the same size as the source. Some information was invariably lost here (cut off from the sides), but I liked the ease of SSD implementation that followed from having two identically sized images. Then I aligned the matched image to the best fitting spot on the source image using an image pyramid. I scaled down the images to 1/64 size and went up by factors of 2. At each level I allowed for a 5x5 pixel box of shifting (2 pixels in each direction). I compared only the areas included in my "context mask". This was the area around the mask 80 pixels deep. I used a linear fall-off for the values in this mask. This way, pixels closer to the edge of the mask were more valuable to the SSD than the ones farther away.

After aligning the images, I ran the graph-cut algorithm over them to find the best seam. I used the original mask as the source and a 2-pixel thick line 80 pixels away from the edge of the mask as the sink.

Finally, I blended the two images using the mask generated from the graph-cut.

Each image was given a score of how well the pieces fit together. I calculated the score as: SSD+(dist*10)-flow, where SSD is the sum of squares difference from the alignment, dist is the given match-rating of the matched image, and flow is the flow returned from the graph-cut.

I saved the top 20 best-scoring resulting images.


Results
Some images worked better than others. It really seems to depend a lot on how good the matched image is to begin with. I also noticed that my scoring metric was not as good as it could have been. Most of the very bad results were weeded out, but of the top 20, there was often little real consensus of what made one picture better than the other. As a result, the best-scoring image was often not the best-looking one. I post below the 51 resulting images; first the best-scoring, and then the one I deem to be the best-looking. Note that sometimes I simply pick the best-scoring image as the best-looking.

Results Images

Masked source image:



















































Best scoring pictures:



















































Hand-picked best pictures: