Scene Completion Writeup

Linda Fong (lfong)
Thursday, March 11 2010

Algorithm

The overall idea of this project is to use many similar images to offer options for filling a hole in an original image. This involves finding these similar images, and then trying to find the portion of each of these hole-filling images that best fits the hole. The first part has already been done for us. The remaining part of the project breaks down into three parts, only one of which is really interesting. First we have to find the offset of the image that is best for inserting into the hole, and then we have to do the graph cut to insert this image, and poisson blending to make it seemless.

The definition of a good offset is an area in the filling image that is similar to the area surrounding the hole in the source image. Thus a band around the hole was chosen to match against the filling image with. I altered my imalign from color alignment to align two 3 channel images with one image masked out. The mask given was the band around the source image's hole. The distance metric was a simple SSD. There were also bounds constraints put into the alignment so it would never shift the hole area off the edge of the bottom image. The reasoning behind this was that i didn't care what the image looked like far from the hole, and also expected the images to be decently aligned in the first place so i didn't have to search over the whole image, just make some small alignment adjustments, which imalign already does.

Next is blending the aligned fill image into the source. I once again make use of the band around the whole. All areas on the outside of the band are constrained to come from the target, all areas inside are constrained to come from the source. The graph cut is made to operate within the band. This way the hole is definitely filled by the filling image, but it has a little flexibility to go over the border of the hole... but not too much. The mask retrieved from graph cut is passed into poisson. And then we're done.

After all the results are gathered, there is the matter of ranking them. The ranking heuristic i used was the
cost of the graphcut + the error from alignment + how well the image matched.
There were some weights (not shown) to scale the the alignment error because it returned rather small values and i wanted it to matter about as much as the graph cut cost.

Results

I've noticed that this works pretty ok where there are not strong lines. When there are though... usually the results are awful.

On the left is the #1 ranked choice, on the right is my preference.

They all suck.
They all suck so here's another cute one from before