[ECCV2012] Offset based image completion

This is a short post about an ECCV 2012 paper I just discovered.
The paper is Statistics of Patch Off sets for Image Completion by Kaiming He and Jian Sun from Microsoft Asia.
There was a recent talk at MSRC about PatchMatch by Dan Goldman. PatchMatch is a simple but very efficient image completion algorithm that is used in Photoshop. The page linked above contains a beautiful illustration of what is possible using this very efficient, still very powerful, algorithm.
For each patch that has parts that are missing, PatchMatch finds the best fit in the known image.
The trick to do this fast is to use a randomized search and exploit the fact that neighboring patches have probably neighboring matches.
But enough about PatchMatch - that just got me interested in this topic.

So this new ECCV paper has a similar idea, but is a bit more radical.
First, it looks for matching patches in the known parts of the image. It requires that these are not too close. The key observation is: the offsets of these patches cluster. These clusters correspond to repeating patterns in the image, to dominant lines and texture.
Once we found the dominant offsets (done by using 2d histograms in the paper), we can just take some translated versions of the picture (in the paper, 60 offsets=translations are used) and try to stitch these together - using a standard MRF with alpha-expansion approach.
BAM! State of the art. I think this is less than 50 lines of Python. I love it.

Here is an illustration from the paper:

You can find the project website with many images here. In particular, an interesting application is filling in the missing bits in stitched panoramas.


  1. Hi Andreas,
    This is pretty awesome! Would you be willing to share your ~50 lines of python code so I can play around? I'm guessing the MRF with alpha-expansion is part of the scikit-learn library?

  2. Sorry, I didn't write it yet ;) I just meant it should be easy to create a prototype. The MRF is not part of scikit-learn, I have wrappers for gco alpha-expansion on github, though:

    There is a blog-post here:


Post a Comment

Popular posts from this blog

Machine Learning Cheat Sheet (for scikit-learn)

A Wordcloud in Python

MNIST for ever....

Python things you never need: Empty lambda functions