Research On GPU Parallelization Of Patch Match Algorithm In Image Processing

As a fundamental problem of classification and clustering, the k-nearestneighbor (kNN) search is widely employed in many research domains. Patchmatch is a specific occasion of kNN search problem in the area of imageprocessing. The simplest approach dealing patch match is exhaustive search,or called brute-force search. Since such approach of patch match isintrinsically time-consuming, it usually becomes the bottleneck of high-levelalgorithms. In order to accelerate image processing, approximate patch matchis usually applied to reduce the computation. At the same time, generouspurpose GPU (GPGPU) has provided a parallel approach to acceleratealgorithm. Based on Compute Unified Device Architecture (CUDA), weproposed a parallel-friendly approximate patch match algorithm andinvestigated its implementation and optimization.At first, this paper proposed an approximate patch match algorithm withpropagation approach. Based on the phenomenon that matched patches ofadjacent query patches have similar information, the proposed algorithm usesinitialization and iteration of propagation to fast complete the match process.In propagation, the information of most possible matching patch is passed toneighbor query patches, thus to reduce the computation of neighbor patchwhile receiving the information. Compared with Barnes approximate kNNalgorithm, one state-of-the art algorithm, our proposed algorithm has acomparable matching error. Under certain occasions, our proposed algorithm even has a better matching error. The proposed algorithm has a significantlybetter parallelism than Barnes algorithm, which makes it suit the GPUplatform and can get substantial speedup. Our proposed algorithm achieves upto5times faster than the Barnes algorithm under GPU platform with the sameoptimization strategies.Secondly, we implemented the proposed algorithm, which is based onJump Flooding, on both GPU and CPU. On GPU platform, we used CUDA toimplement the algorithm and applied many optimization methods aboutmemory access to improve performance. On CPU platform, we implementedit using OpenMP multi-thread method. We compared the parallel computationcapability and advantages of GPU and CPU. GPU has significant advantageon massively parallel algorithm when compared to CPU platform.At the last part, we applied our patch match algorithm to denosing andtexture synthesis to verify the validity of our algorithm. By replacing thepatch descriptor with coefficient in transform domain, we applied ouralgorithm to BM3D (block-matching and3D filtering). We achievedimprovements in PSNR compared with BM3D algorithm implemented withsimple2D Harr transform,3D DCT transform and local search. By changingthe distance metric, we applied the proposed algorithm to texture synthesis,and achieved significant speedup with excellent visual effect and fewartifacts.