论文部分内容阅读
[摘 要]纹理合成在计算机动画制作中具有重要地位。为克服传统串行点匹配纹理合成算法效率低下的缺陷，提出一种基于计算统一设备架构（CUDA）的并行合成算法。通过合理安排CPU和GPU之间的数据传输，用GPU进行繁琐耗时的计算，明显地提高了算法效率。
[关键词]纹理合成 点匹配 CUDA GPU并行计算
中图分类号：TP393.08 文献标识码：A 文章编号：1009-914X（2014）25-0323-02
纹理合成是当前计算机的研 究热点之一。该技术在图像编辑、计算机动画、数据高倍压缩、大规模场景的生成等方面具有广泛的应用前景。纹理合成方法可分为基于过程的纹理合成和基于样图的纹理合成两类。而基于样图的纹理合成技术不仅可以克服传统纹理映射存在走样的缺点，而且避免了纹理合成过程中调整参数的繁琐。
Wei和Levoy提出的纹理合成算法（简称WL算法）是典型的基于样图的纹理合成算法之一，WL算法中L邻域的尺寸对合成质量和合成效果影响很大，一般说来，L邻域越大，效果越好，但是随之带来的计算量会很大，因此，合成时间也会成倍增加。传统的算法都是在CPU中串行执行，效率非常低下，特别是在计算量特别庞大而不需要过多的逻辑控制时，使用CPU串行计算，很难有效利用处理器的全部资源。本文使用一种基于CUDA的纹理合成算法，通过将繁琐的L邻域计算和最匹配像素的搜索转入GPU中并行计算，优化了算法。
1.基于点匹配的纹理合成算法介绍
WL纹理合成算法是基于点纹理合成算法的代表，是一种确定性搜索的纹理合成算法。该算法使用像素L邻域的[1]相似度作为合成依据，L邻域只取像素邻域的上半部分，因其形状像字母L，故称为L邻域。在输入纹理中按照扫描线顺序搜索与当前合成像素的L邻域具有最大相似度的像素点来合成纹理。WL算法的具体步骤如下：
（1）用随机噪声初始化输出图像。
（2）对于输出图像的每个像素p，按照扫描线顺序计算：
a.构造输出图像当前像素p的L邻域（如图1中b，c，d）；
b.在输入纹理中同样按照扫描线顺序搜索与像素p的L邻域具有最大相似度L邻域的像素q（如图1，a）；
c.将像素q拷贝到像素p。
（3）重复步骤（2），直到图像合成完毕。
图1 L邻域查找示意图
算法中采用Euclid距离来度量邻域之间的相似度。
（1）
式中，R，G，B分别为像素p，q的红，绿，蓝三原色通道。N1，N0分别是输入纹理和输出纹理中某一点的L邻域。
从上面步骤可以看出，WL算法主要耗时在L邻域相似度的计算和L邻域最大相似度像素的搜索上，每合成输出图像的一个像素，都要在输入图像中逐个像素地计算，虽然合成效果较好，但是其计算和搜索过程相当费时。如果能将以上耗时的计算搜索转为并行，相信会对算法效率有很大提高。
2.CUDA介绍
2006年NVIDIA推出的G80系列显卡引入了CUDA架构，使得GPU可以解决商业、工业以及科学方面的复杂计算问题。下面对CUDA进行简要介绍：
2.1 CPU与GPU结构的区别
传统的CPU由于摩尔定律失效，其计算速度目前已经基本达到顶峰，而GPU则是专为计算密集型、高度并行化的计算而设计的。两者的架构如图2所示：
CPU GPU
图2 cpu（左）和gpu（右）的结构
GPU的设计增强了数据处理能力，而数据缓存和流控制方面则不及CPU。这使得GPU适用于解决不需要过多精密流控制的大规模并行计算问题。
2.2 CUDA的线程层次模型和存储器分配
CUDA采用线程->线程块->线程块网格的线程层次模型。一个线程块网格可以划分为多个线程块，每个线程块包含了一定数量的线程。CUDA通过这种结构来管理线程的执行以及存储器的分配。每个线程有一个私有的本地存储器。每个线程块有一个共享存储器，该存储器对于块内的所有线程都是可见的，并且与块具有相同的生命周期。最后，所有线程都可访问全局存储器。
2.3 CUDA运行模式
CUDA定了一种称为内核（kernel）的C语言函数，并且扩展了C语言。在调用此类函数时，它将由N个不同的CUDA线程并行执行N次，这与普通的C语言函数只执行一次方式不同。另外CUDA把CPU称作主机，GPU称作设备，在运行CUDA程序时，串行代码在主机上执行，并行代码即”kernel”在设备上执行。另外，可以通过主机和设备同步函数，使CPU和GPU同时计算，提高程序效率。
3.基于CUDA的纹理合成
本部分介绍在CUDA平台上用GPU来计算像素L邻域相似度并寻找最大相似度像素的算法。
3.1 GPU存储器的分配
把数据传入GPU，需要合理分配存储器。输入与输出图像存入对于所有线程都是可读写的Global Memory。在计算L邻域相似度时为各线程分配高速的Local Memory；而在规约计算查找具有最大L邻域相似度的像素时，则使用对线程块可见的shared memory。
3.2 并行计算输入纹理L邻域的相似度值
在计算L邻域相似度时，输入图像存储在GPU的Global Memory中，其每个像素在计算时不发生变化，即只需对Global Memory进行读操作，多个线程并行读Global Memory不会发生冲突。基于以上原因，通过GPU对此过程进行并行优化。以64×64大小的输入样图为例，可使用64×64个线程来并行计算，由一个线程计算一个像素的L邻域相似度。定义一个含有64个线程块的网格，每个线程块包含64个线程。这样便完成了像素到CUDA线程的映射。 3.3 并行查找具有最大L邻域相似度的像素
在并行计算输入纹理的L邻域相似度后，需要找出具有L邻域最大相似度的像素。所有数据在GPU中计算得出，如果将数据传回CPU计算后再传入GPU，会浪费大量的数据拷贝时间。
为提高整个程序的效率，在GPU中使用改进的并行规约算法来进行查找。并行规约算法的思想类似归并排序，把规约中的加运算改为比较运算，并且设置一个监视哨，用来存储由公式（1）计算得到的Euclid距离最小值（即L邻域最大相似度值）的位置。线程块里的每个线程分别处理一个数据，线程块前半部分的数据分别与后半部分数据比较，得出相对较小的结果，并存入前半部分线程所分配的空间，以此循环，直到只剩下最后一个数据。此时监视哨里也保存了最小值的位置，它对应输入纹理的像素位置。
4.实验结果及分析
实验平台为INTEL CORE I3 cpu，显卡是常用的NVIDIA GEFORCE 9800MGS与GTX560显卡。在LINUX下文本模式下实验（图形模式会消耗显卡资源）。程序使用C语言编写。为了便于比较，输入纹理像素均等于输出纹理。
4.1 不同邻域尺寸的加速比
分别对L3，7，9，13邻域进行实验，输入纹理为64×64像素，显卡采用GEFORCE 9800GTX使用基本WL算法和经过CUDA加速的算法，并且对照TSVQ，SPSO加速的WL算法，它们的运行时间如下表所示。
表1 CPU与GUP运行时间比较（单位：秒）
下图直观显示了CUDA并行算法的加速效果：
图3 加速比对比
CUDA的平均加速效果可达100倍以上。由于合成算法的计算量随L邻域的增大而增加，图表中也可以看出计算量越大，GPU的加速越高，这也体现了CUDA平台下GPU的大规模并行处理能力。且加速比要高于SPSO和TSVQ加速的WL算法。
5.小结
为了加速计算L邻域的相似度值并寻找最匹配的像素，利用CUDA平台下GPU强大的计算能力，并行计算输入纹理的L邻域相似度值，并使用改进并行规约算法寻找具有最大相似度的像素，提高了算法效率。然而加速比并没有达到并行线程的数量，这主要是局限于GPU流处理器的数目，以及算法本身的优化质量。另外，对不同大小的输入样图，或者非正方形样图，需要手工指定线程数目与线程块数目，也是需要改进的地方。
参考文献
[1] Wei LiYi，Marc Levoy.Fast texture synthesis using tree-stuctured vector quantization[A].In：proceedings of SIGGRAPH[C]，New Orleans，2010：479-488.
[2] Kennedy J，Eberhart R C.Particle swarm optimization [C]//IEEE Service Center.Proc IEEE Int’1 Conf on Neural Networks Vol IV.2009.
[3] Zhang Yan，Meng Yu L Wen-hui，et al.A fast algorithm for image analogy using particle swarm optimization[C]//Proc of the 3rdInternational Conference on Machine Leaning and Cybernetics， shanghai：2011.26-29.
[4] Daniel Bratton，James Kennedy，et al.Defining a Standard for Particle Swarm Optimization [C]// Proceedings of the 2011 IEEE Swarm Intelligence Symposium.2011.120-127.
[5] NVIDIA CUDA programming guide 2.0[z].NVIDIA，2012.
[6] 薛峰，张佑生.基于样图的纹理合成技术研究[D].合肥：合肥工业大学.2011.
[关键词]纹理合成 点匹配 CUDA GPU并行计算
中图分类号：TP393.08 文献标识码：A 文章编号：1009-914X（2014）25-0323-02
纹理合成是当前计算机的研 究热点之一。该技术在图像编辑、计算机动画、数据高倍压缩、大规模场景的生成等方面具有广泛的应用前景。纹理合成方法可分为基于过程的纹理合成和基于样图的纹理合成两类。而基于样图的纹理合成技术不仅可以克服传统纹理映射存在走样的缺点，而且避免了纹理合成过程中调整参数的繁琐。
Wei和Levoy提出的纹理合成算法（简称WL算法）是典型的基于样图的纹理合成算法之一，WL算法中L邻域的尺寸对合成质量和合成效果影响很大，一般说来，L邻域越大，效果越好，但是随之带来的计算量会很大，因此，合成时间也会成倍增加。传统的算法都是在CPU中串行执行，效率非常低下，特别是在计算量特别庞大而不需要过多的逻辑控制时，使用CPU串行计算，很难有效利用处理器的全部资源。本文使用一种基于CUDA的纹理合成算法，通过将繁琐的L邻域计算和最匹配像素的搜索转入GPU中并行计算，优化了算法。
1.基于点匹配的纹理合成算法介绍
WL纹理合成算法是基于点纹理合成算法的代表，是一种确定性搜索的纹理合成算法。该算法使用像素L邻域的[1]相似度作为合成依据，L邻域只取像素邻域的上半部分，因其形状像字母L，故称为L邻域。在输入纹理中按照扫描线顺序搜索与当前合成像素的L邻域具有最大相似度的像素点来合成纹理。WL算法的具体步骤如下：
（1）用随机噪声初始化输出图像。
（2）对于输出图像的每个像素p，按照扫描线顺序计算：
a.构造输出图像当前像素p的L邻域（如图1中b，c，d）；
b.在输入纹理中同样按照扫描线顺序搜索与像素p的L邻域具有最大相似度L邻域的像素q（如图1，a）；
c.将像素q拷贝到像素p。
（3）重复步骤（2），直到图像合成完毕。
图1 L邻域查找示意图
算法中采用Euclid距离来度量邻域之间的相似度。
（1）
式中，R，G，B分别为像素p，q的红，绿，蓝三原色通道。N1，N0分别是输入纹理和输出纹理中某一点的L邻域。
从上面步骤可以看出，WL算法主要耗时在L邻域相似度的计算和L邻域最大相似度像素的搜索上，每合成输出图像的一个像素，都要在输入图像中逐个像素地计算，虽然合成效果较好，但是其计算和搜索过程相当费时。如果能将以上耗时的计算搜索转为并行，相信会对算法效率有很大提高。
2.CUDA介绍
2006年NVIDIA推出的G80系列显卡引入了CUDA架构，使得GPU可以解决商业、工业以及科学方面的复杂计算问题。下面对CUDA进行简要介绍：
2.1 CPU与GPU结构的区别
传统的CPU由于摩尔定律失效，其计算速度目前已经基本达到顶峰，而GPU则是专为计算密集型、高度并行化的计算而设计的。两者的架构如图2所示：
CPU GPU
图2 cpu（左）和gpu（右）的结构
GPU的设计增强了数据处理能力，而数据缓存和流控制方面则不及CPU。这使得GPU适用于解决不需要过多精密流控制的大规模并行计算问题。
2.2 CUDA的线程层次模型和存储器分配
CUDA采用线程->线程块->线程块网格的线程层次模型。一个线程块网格可以划分为多个线程块，每个线程块包含了一定数量的线程。CUDA通过这种结构来管理线程的执行以及存储器的分配。每个线程有一个私有的本地存储器。每个线程块有一个共享存储器，该存储器对于块内的所有线程都是可见的，并且与块具有相同的生命周期。最后，所有线程都可访问全局存储器。
2.3 CUDA运行模式
CUDA定了一种称为内核（kernel）的C语言函数，并且扩展了C语言。在调用此类函数时，它将由N个不同的CUDA线程并行执行N次，这与普通的C语言函数只执行一次方式不同。另外CUDA把CPU称作主机，GPU称作设备，在运行CUDA程序时，串行代码在主机上执行，并行代码即”kernel”在设备上执行。另外，可以通过主机和设备同步函数，使CPU和GPU同时计算，提高程序效率。
3.基于CUDA的纹理合成
本部分介绍在CUDA平台上用GPU来计算像素L邻域相似度并寻找最大相似度像素的算法。
3.1 GPU存储器的分配
把数据传入GPU，需要合理分配存储器。输入与输出图像存入对于所有线程都是可读写的Global Memory。在计算L邻域相似度时为各线程分配高速的Local Memory；而在规约计算查找具有最大L邻域相似度的像素时，则使用对线程块可见的shared memory。
3.2 并行计算输入纹理L邻域的相似度值
在计算L邻域相似度时，输入图像存储在GPU的Global Memory中，其每个像素在计算时不发生变化，即只需对Global Memory进行读操作，多个线程并行读Global Memory不会发生冲突。基于以上原因，通过GPU对此过程进行并行优化。以64×64大小的输入样图为例，可使用64×64个线程来并行计算，由一个线程计算一个像素的L邻域相似度。定义一个含有64个线程块的网格，每个线程块包含64个线程。这样便完成了像素到CUDA线程的映射。 3.3 并行查找具有最大L邻域相似度的像素
在并行计算输入纹理的L邻域相似度后，需要找出具有L邻域最大相似度的像素。所有数据在GPU中计算得出，如果将数据传回CPU计算后再传入GPU，会浪费大量的数据拷贝时间。
为提高整个程序的效率，在GPU中使用改进的并行规约算法来进行查找。并行规约算法的思想类似归并排序，把规约中的加运算改为比较运算，并且设置一个监视哨，用来存储由公式（1）计算得到的Euclid距离最小值（即L邻域最大相似度值）的位置。线程块里的每个线程分别处理一个数据，线程块前半部分的数据分别与后半部分数据比较，得出相对较小的结果，并存入前半部分线程所分配的空间，以此循环，直到只剩下最后一个数据。此时监视哨里也保存了最小值的位置，它对应输入纹理的像素位置。
4.实验结果及分析
实验平台为INTEL CORE I3 cpu，显卡是常用的NVIDIA GEFORCE 9800MGS与GTX560显卡。在LINUX下文本模式下实验（图形模式会消耗显卡资源）。程序使用C语言编写。为了便于比较，输入纹理像素均等于输出纹理。
4.1 不同邻域尺寸的加速比
分别对L3，7，9，13邻域进行实验，输入纹理为64×64像素，显卡采用GEFORCE 9800GTX使用基本WL算法和经过CUDA加速的算法，并且对照TSVQ，SPSO加速的WL算法，它们的运行时间如下表所示。
表1 CPU与GUP运行时间比较（单位：秒）
下图直观显示了CUDA并行算法的加速效果：
图3 加速比对比
CUDA的平均加速效果可达100倍以上。由于合成算法的计算量随L邻域的增大而增加，图表中也可以看出计算量越大，GPU的加速越高，这也体现了CUDA平台下GPU的大规模并行处理能力。且加速比要高于SPSO和TSVQ加速的WL算法。
5.小结
为了加速计算L邻域的相似度值并寻找最匹配的像素，利用CUDA平台下GPU强大的计算能力，并行计算输入纹理的L邻域相似度值，并使用改进并行规约算法寻找具有最大相似度的像素，提高了算法效率。然而加速比并没有达到并行线程的数量，这主要是局限于GPU流处理器的数目，以及算法本身的优化质量。另外，对不同大小的输入样图，或者非正方形样图，需要手工指定线程数目与线程块数目，也是需要改进的地方。
参考文献
[1] Wei LiYi，Marc Levoy.Fast texture synthesis using tree-stuctured vector quantization[A].In：proceedings of SIGGRAPH[C]，New Orleans，2010：479-488.
[2] Kennedy J，Eberhart R C.Particle swarm optimization [C]//IEEE Service Center.Proc IEEE Int’1 Conf on Neural Networks Vol IV.2009.
[3] Zhang Yan，Meng Yu L Wen-hui，et al.A fast algorithm for image analogy using particle swarm optimization[C]//Proc of the 3rdInternational Conference on Machine Leaning and Cybernetics， shanghai：2011.26-29.
[4] Daniel Bratton，James Kennedy，et al.Defining a Standard for Particle Swarm Optimization [C]// Proceedings of the 2011 IEEE Swarm Intelligence Symposium.2011.120-127.
[5] NVIDIA CUDA programming guide 2.0[z].NVIDIA，2012.
[6] 薛峰，张佑生.基于样图的纹理合成技术研究[D].合肥：合肥工业大学.2011.