The key ingredients of PatchMatch are two insights on natural image statistics, especially from the patch offsets space: 1. There are abundant similar patches inside natural image (Non-local Means also shares this spirit); so large number of random sampling would yield good initialization. 2. Neighboring patches often have similar offset vectors; this observation enables propagation of offset vectors among neighboring patches that leads to an efficient iteration solution.
I have also tried this useful algorithm on one of Jimmy Liao's hand drawings and a Chinese ancient painting. The extrapolation effects are illustrated as follows:
Both results are visually plausible overall. By inspecting some local regions and details, we further find that: 1. This category of methods (like PatchMatch) work well on smooth regions, repetitive patterns and could also maintain local semantic coherence. 2. Global semantic coherence still can't be handled, which leaves room for the interdisciplinary research between low-level image processing and high-level visual reasoning.
