论文部分内容阅读
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算法相比,采用本文提出的块匹配算法的版本的去噪性能获得了一定的提升。通过改变距离描述公式,将本算法应用在纹理合成算法中。在取得显著的加速的同时,保证了较好的视觉效果。