Parallel and efficient approximate nearest patch matching for image editing applications

This paper presents a novel GPU-based patch matching method which efficiently finds approximate nearest neighbor correspondences for patches between images. Our approach improves traditional patch matching algorithms in two aspects. First, we propose to improve the convergence of matching with two new types of forward enrichment operations, enabling the fast propagation of a richer set of potentially good candidates on different images. Second, we reduce the search space of patch direction by estimating a coherent feature direction field for each image and computing the similarity between patches with a direction-aware alignment scheme. Furthermore, we develop a number of GPU-based image editing and processing applications by incorporating our new patch matching algorithm, including object matching, nonlocal means denoising, image completion, texture synthesis, and image retargeting. Experimental results and comparisons are shown to demonstrate the effectiveness of the proposed approach.