Research On Parallel And Efficient Patch Matching Algorithm

The image patch matching technique is used to match patches with translational or rotational transformations in two or more images.It is a technical foundation of many image editing and processing applications.Therefore,it has important practical value and research significance in the field of image processing.This paper proposes a parallel and efficient patch matching algorithm.It can effectively find approximate nearest neighbor correspondences for patches between images.The algorithm is implemented based on the GPU and employs the coarse-to-fine optimization to speed up the convergence.The proposed algorithm improves traditional image patch matching algorithms in three aspects.First,based on the transitivity theory in the mathematical partial order and equivalent relations,two new types of matching enrichment operations are proposed to obtain a richer set of potentially good candidates when updating matching patches.Second,the structure tensor is used to calculate the coherent feature direction of the image and the direction-aware alignment scheme is introduced during the process of patch matching.As a consequence,the calculation of patch similarity can be performed with the angle adjustment,effectively avoiding the huge computation of traversing all possible rotational angles.Third,the proposed algorithm takes advantage of the parallel computational power of the GPU to further accelerate the efficiency.Many applications,including object matching,nonlocal means denoising and texture synthesis,are implemented in order to demonstrate the effectiveness and efficiency of the proposed algorithm.In addition,extensive experimental comparisons are conducted to validate the feasibility of the proposed algorithm.