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.