Dear Fellow Scholars, this is Two Minute Papers with Károly Zsolnai-Fehér. We're currently more than 130 episodes into the series, and we still haven't talked about this algorithm.
How could we go on for so long without PatchMatch? So, let's do this right now!
You'll love this one. This technique helps us to make absolutely crazy modifications to previously existing photographs and it is one of the landmark papers for all kinds of photo manipulation which is still widely used to this day.
Consider the following workflow: we have this image as an input. Let's mark the roofline for hole filling, or image inpainting as the literature refers to it.
And the hole is now filled with quite sensible information. Now we mark some of the pillars to reshape the object.
And then, we pull the roof upward. The output is a completely redesigned version of the input photograph.
Wow, absolutely incredible. And the whole thing happens interactively, almost in real time, but if we consider the hardware improvement since this paper was published, it is safe to say that today it runs in real time even on a mediocre computer.
And in this piece of work, the image completion part works by adding additional hints to the algorithm, for instance, marking the expected shape of an object that we wish to cut out and have it filled in with new data. Or, showing the shape of the building that we wish to edit also helps the technique considerably.
These results are so stunning, I remember that when I had first seen them, I had to recheck over and over again because I could hardly believe my eyes. This technique offers not only these high quality results, but it is considerably quicker than its competitors.
To accomplish image inpainting, most algorithms look for regions in the image that are similar to the one that is being removed, and borrow some information from there for the filling process. Here, one of the key ideas that speed up the process is that when good correspondances are found, if we are doing another lookup, we shouldn't restart the patch matching process, but we should try to search nearby, because that's where we are most likely to find useful information.
