Abstract: Many image processing or computer graphic applications involve similar patches search in images,which is a very computational-expensive operation．Traditional acceleration methods such as ANN (Approximate Nearest Neighbor) do not support exact search in non-metric space,and the searching time becomes longer for high-dimensional space.In this paper the general GPU-based framework to compute the similar patches was proposed which can be extended to incorporate any distance functions．Specifically,both Euclidean distance and non-metric Chamfer distance are adopted to compute the similarity between two patches．We proposed the GPU-based algorithm for fast search of similar patches in images under these two distances．Besides,the distances computation is optimized to achieve more efficient CUDA implementation．This algorithm supports exact search since exhaustive search strategy is adopted．The distances between patches are computed in parallel on GPU to greatly improve the computational efficiency．Experimental results show that our method has one or two orders of magnitude speedup compared with traditional acceleration methods and the results of applications in texture synthesis show that our method is capable to synthesize high-quality textures with fast speed.

Key words: Metric space,Similar patches,GPU,Chamfer distance,Texture synthesis