PatchMatch: amazing interactive content-aware image editing (SIGGRAPH 09)
cs.princeton.edu
cs.princeton.edu
However, I have a feeling that that haven't tuned these heuristics perfectly. They've just come up with the basic idea, and got it working. Images that hill-climb well, and user-selected regions that match up well will be very fast with this technique - the cool thing is that that covers most images that humans like to look at, and the kinds of edits that humans want to do. You could construct special cases that this method would perform terribly at: e.g. a user-selected region that only matches exactly one other region like that in the image, and such that these two regions do not "almost match" when they are "almost aligned", but only match when they are perfectly aligned.
But I bet it works great for most actual images and edits in practice. A few times, my eyes didn't register all the changes that have been made, because they look so natural. It also looks like fun.