Project 3: Scene Completion

Donnie Kendall (dkendall)

Algorithm

Candidate images were resized to match the source image. The resizing was a flat, brute-force resize which occasionally resulted in images with distorted aspect ratios.

In order to determine if a candidate image was a good match for the given source image I compared an area of radius 80 pixels around the missing area between the candidate and source. The comparison was an SSD comparison in L*a*b* color space (as this should have captured perceptual differences better than RGB does). The comparison was linearly weighted, with the pixels immediately adjacent to the hole mattering the most, and those furthest out mattering less. I experimented with trying to match texture (via gradient, or edge detection) in addition to color, but results did not improve enough for the speed loss for me to keep that in.

I also experimented briefly with attempting to search an area of the candidate images via alignment, however, this was found to severely slow down the algorithm with a minimal impact on my end results. The good matches occasionally got slightly better, but bad matches tended to remain bad. In the end I removed this as well because of run time considerations.

The best 3 matches (defined as those with the lowest SSD cost) were then used to generate candidate images. The exact seam to use was determined via a graph cut. The cut was allowed to go anywhere inside the 80 pixel radius mentioned previously. This occassionally resulted in more of the source image getting removed, however, it often resulted in a better overall fit.

Results

The full results can be viewed here. A selection of the best (and worst) is shown below.

Result images are presented in order based on how well the boundry region of the candidate matched the boundry region of the source. The graph cut cost is not taken into consideration here.

Some almost-good results were ruined by perseptive problems, others by scaling distortion. Other results are just completely wrong.

The Good

The results of this set are generally pretty good. Some individual images are poor, but at least one in each set is a fairly convincing replacement.

The Bad

The results of this set are pretty uniformly not good. Urban scenes gave it particular problems.

Grab Bag

A random (not dynamically random, don't refresh the page hoping for new images) smattering of result images. Some are good, some are almost, but not quite good, and some are hilariously bad.