K近邻搜索(k-nearest neighbor)作为分类和聚类的一种基本问题被广泛地应用在众多研究领域。块匹配算法是k近邻搜索在图像处理领域中的一种具体应用。最简单的块匹配算法是暴力搜索法，也叫穷举搜索法。但是该算法极为耗时，块匹配也经常成为图像处理算法的性能瓶颈。为了提高图像处理速度，目前常采用近似块匹配方法达到减少运算量的目的。同时，图形处理器(GPU)通用计算也为块匹配算法加速提供了并行化的方法。本文基于CUDA(Compute Unified Device Architecture)通用并行计算架构，提出了一种并行化友好的近似块匹配算法，并研究其并行实现的优化技术。首先，本文提出了一种基于传播的近似块匹配算法。基于相邻的块的匹配块具有相似的信息这一特性，该算法通过初始化和传播迭代来快速完成匹配。传播过程将最有可能的匹配块的信息传递给邻域块，从而在减少邻域的块的运算量的同时，使之获得匹配块信息。在传播过程中引入了Jump Flooding方法使之并行化。与目前性能较好的近似块匹配算法Barnes算法相比，本文算法有着与该算法相近的匹配误差性能。甚至在某些应用环境下，本文算法匹配误差性能更优。但与Barnes算法相比，本文提出的算法有着显著的并行友好性，更易于在GPU平台下实现从而获得更为显著的加速。在CUDA架构下，本文算法相较Barnes算法有5倍以上的加速比。其次，分别在GPU平台和CPU平台上实现并优化了本文提出的基于Jump Flooding的块匹配算法。在GPU平台上，基于CUDA架构实现此算法，并采用了多种了内存访问优化策略来提高算法实现的性能。在CPU平台，采用OpenMP的多线程方法并行地实现该算法。本文比较了GPU和CPU的并行计算能力与优势。与CPU相比，GPU在实现大规模并行算法上有着显著的优势。本文最后将该块匹配算法应用于去噪和纹理合成中，验证其在应用中的有效性。通过改变图像块描述子，使用变换域系数描述块，将该算法应用在BM3D(block-matching and3D filtering)去噪算法。与使用简单2D Harr，3D DCT变换和局部搜索实现的BM3D算法相比，采用本文提出的块匹配算法的版本的去噪性能获得了一定的提升。通过改变距离描述公式，将本算法应用在纹理合成算法中。在取得显著的加速的同时，保证了较好的视觉效果。