[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.

Comments

  1. gchuMay 23, 2013 at 7:46 PM

    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?
    Thanks!

    ReplyDelete
  2. Andreas MuellerMay 27, 2013 at 2:15 PM

    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:
    https://github.com/amueller/gco_python

    There is a blog-post here:
    http://peekaboo-vision.blogspot.it/2012/05/graphcuts-for-python-pygco.html

    ReplyDelete

Post a Comment

Popular posts from this blog

Machine Learning Cheat Sheet (for scikit-learn)

Image
As you hopefully have heard, we at scikit-learn are doing a user survey (which is still open by the way). One of the requests there was to provide some sort of flow chart on how to do machine learning. As this is clearly impossible, I went to work straight away. This is the result: [edit2] clarification: With ensemble classifiers and ensemble regressors I mean random forests , extremely randomized trees, gradient boosted trees , and the soon-to-be-come weight boosted trees (adaboost). [/edit2] Needless to say, this sheet is completely authoritative.
Read more

A Wordcloud in Python

Image
Last week I was at Pycon DE , the German Python conference. After hacking on scikit-learn a lot last week, I decided to to something different on my way back, that I had planned for quite a while: doing a wordl -like word cloud . I know, word clouds are a bit out of style but I kind of like them any way. My motivation to think about word clouds was that I thought these could be combined with topic-models to give somewhat more interesting visualizations. So I looked around to find a nice open-source implementation of word-clouds ... only to find none. (This has been a while, maybe it has changed since). While I was bored in the train last week, I came up with this code . A little today-themed taste:
Read more

MNIST for ever....

Image
[update] This post is a bit old, but many people still seem interested. So just a short update: Nowadays I would use Python and scikit-learn to do this. Here is an example of how to do cross-validation for SVMs in scikit-learn. Scikit-learn even downloads MNIST for you. [/update] MNIST is, for better or worse, one of the standard benchmarks for machine learning and is also widely used in then neural networks community as a toy vision problem. Just for the unlikely case that anyone is not familiar with it: It is a dataset of handwritten digits, 0-9, in black on white background. It looks something like this: There are 60000 training and 10000 test images, each 28x28 gray scale. There are roughly the same number of examples of each category in the test and training datasets. I used it in some papers myself even though there are some reasons why it is a little weird. Some not-so-obvious (or maybe they are) facts are: - The images actually contain a 20x20 patch of digi...
Read more

Python things you never need: Empty lambda functions

Ever wanted to create an empty Python function in-line? No? Me neither. But my coworker does... We found the answer: <pre> x = lambda : None </pre> If you ever needed this, please tell me ;) [Edit] Apparently some people do need it :) Btw, most people seem to try Most people try lambda: pass first. But you have to remember, the thing at the right side of the colon is the return value of the function, not the body! So an expression is needed, not a statement. [\Edit]
Read more