Image Completion __ Writeup

Sam Potasznik (spotaszn)
March 12, 2010

The Algorithm

To fill in the missing area in the picture with information from a given match image, I used three basic steps.

  1. Align the match and source image
  2. Select an appropriate region from the match to paste onto the source
  3. Blend the pasted patch and the source
      4. In step one, instead of aligning the whole match to the source, I only aligned the part of the match that surrounded the area to be patched, like this:
      By only aligning the border of the patch, I tried to ensure that the area that is most likely to be cut through would be aligned correctly. I did not care if a pixel that was certainly only going to come from one image or the other was aligned in both images. Only pixels that had a chance of coming from either image were aligned.

      In step two, I used the graph cut algorithm to find the best area to be cut and pasted onto the source image. However, I did limit the area that the algorithm could cut through by constraining certain pixels to come from the source. As with the alignment, I created a border around the patch. Anything past this border was constrained to come from the source, a la:

      To blend the images, I used the Poisson blending algorithm.

      Ranking the Results

      I used a very simple metric to rank the results which was a combination of the graph cut used on the result and the rank of the match itself. Each match's score was equal to its graph cut cost divided by the sum of all graph cut costs plus the match rank divided by the total match ranks.

      This ranking could definitely be improved. As is, it puts too much emphasis on the ranking of the match itself, and not enough on how much work it took to composite the images. This is evident in that often times, there is not much "movement" between the images as only ranked by the match and the images as ranked by my algorithm.

      Results Images

      As with most things, some of these results were good, and some not so good. My personal favorite match set is #35, which produces some really awesome and novel sunsets. On the whole, landscapes seem to work better than other more detailed scenes (i.e. the sunset). Also, scenes with very common textures (like grass in image 38) work well. Very detailed scenes are understandably hard to cut through (image 36). And if the area to fill is extremely large (the iconic image set at the bottom of this page), messy data will necessarily be copied from the match, and that may be hard to find a good seam to connect it to the rest of the image.

      Click the picture to see the full range of unranked and ranked results
      Ranked