PatchMatch is an algorithm that fills holes and reshapes objects in images by reusing nearby patch matches instead of searching from scratch each time. It's fast, accepts user hints for shapes, and works without machine learning, though combining it with deep learning could make it even better.
Dear fellow scholars, this is two minute papers with we are 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. It's consider the following workflow. We have this image as an input. Let's mark the roof line 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 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 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 correspondences 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. You know what the best part is? What you see here is just the start. This technique does not use any of the modern machine learning techniques. So in the era of these incredibly powerful deep neural networks, I can only imagine the quality of solutions we'll be able to obtain in the near future. We are living amazing times indeed. Thanks for watching and for your generous support and I'll see you next time.
