GPU通用计算在三维距离变换中的应用.doc

GPU通用计算在三维距离变换中的应用田绪红 陈茂资 司徒志远华南农业大学信息学院计算机科学与工程系，广州 510642摘要：距离变换是图象处理的一个经典问题，在图象处理中有广泛的应用。本文结合GPU的特殊的体系结构，根据三维距离变换的特点设计了相应的数据存储结构，充分利用GPU的并行处理能力，在GPU上实现三维距离变换的算法。实验证明了基于GPU的并行算法可以得到很好的加速比，同时也提出了其中的局限性。关键词：GPU；GPU通用计算(GPGPU)；距离变换1. 引言近些年来图形处理器(GPU)的硬件技术飞速发展，其更新速度非常快，平均每年就有新的一代GPU推出市场。与之相随的是其可编程能力在不断的提高，出现了像C for Graphics (Cg)，High Level Shading Language(HLSL)，OpenGL Shading Language(GLSL)等类似C的高级语言。GPU的应用领域不断扩大，学者们提出GPU通用计算(GPGPU)的概念，将GPU应用于非图象绘制方面的计算。这些计算相当广泛，如碰撞检测1，数值计算2，流体模拟3，图象处理4，偏微分方程计算2,5,6等。由于GPU的高效的并行处理能力，使之在以上的运算中有很好的性能，达到许多大型计算机的水平，并且GPU价格低廉，十分有利于推广。距离变换是图象处理的一个经典问题，在图象处理中有广泛的应用。由于三维距离变换的数据量非常巨大，传统使用CPU计算的效率不高。本文尝试在GPU上实现三维距离变换算法，利用GPU的并行处理能力提高变换的效率。2. GPU通用计算(GPGPU)2.1. GPU的体系架构GPU是专门为图形图象处理而设计的硬件芯片，其设计初衷是为了减轻CPU的负担，将大部分的图形图象运算如光照处理，顶点运算，纹理映射等功能转移到一块专门的芯片上。这就是图象处理单元(GPU)的由来。从系统架构上看，GPU 是针对向量计算进行了优化的高度并行的数据流处理器，其中包括两种流处理单元：顶点着色器(Vertex Shader)，是多指令多数据流的处理单元(MIMD)，像素着色器 ( Pixel Shader)是单指令多数据流的处理单元(SIMD) 7,8。这种以数据流作为处理单元的处理器，在对数据流的处理上可以获取较高的效率。由于GPU特殊的系统架构、整数运算逻辑运算支持的贫乏，以及其不同于传统CPU的数据存取方式，使得其并不能轻易的运用在非图形图象运算。GPU对于通用计算不是一服万能药8，它只能完成一些特定的计算。一般说来GPU通用计算有如下的特点9,10：1) 算法程序必须能被分解成为不相关的程序片段(section)，这些程序片段作为GPU的计算内核，每个流处理器执行相同的程序片段来并行求解最终的计算结果；2) 由于GPU的特殊架构，使之更适合运算程序的循环结构而不适合运算程序的分支结构；3) 每个程序片段的控制结构不能复杂，语句不能太多，实际应用中可以将复杂算法程序分解成几个规模较小的代码模块；4) 由于GPU是针对图形处理进行加速的，因此其中最主要的计算元素，或者说数据结构就是纹理;2.2. GPU的编程接口现在比较流行和通用的图形接口有两个：DirectX和OpenGL。二者都是为了方便人们对GPU进行编程而产生的，是一套底层(low-level)图形API。利用其强大功能程序员可以十分方便地与驱动程序沟通，从而运用GPU强大的三维图形处理能力，大幅度地提高三维程序的开发效率。图1 GPU工作示意图图1所示的图形API是一套已定义好的，提供给应用程序的接口和函数。由于市面上的图形卡品种繁多，每种卡的性能和结构都有所差异，HAL(Hardware Abstraction Layer，硬件抽象层)就应运而生。它由设备厂商提供，向下指示特定设备完成具体操作，向上对API提供相同的调用接口。为了对GPU更好的控制，人们又开发了着色语言(Shading Language)，当今比较流行的有3种：l Cg: C for Graphics，由NVIDIA公司开发的一种针对GPU的程序设计语言;l HLSL: High-Level Shading Language，微软公司为Direct3D开发的着色语言，当今大部分的游戏厂商都使用该种语言；l GLSL：与OPENGL绑定的一种着色语言，由于OPENGL的开放性，其应用也相当广泛。利用上面这样的高级着色语言的好处是显而易见的1011：1) 提高了生产力，用高级语言编写程序更简便更快捷，编译器可以自动优化代码并执行底层任务，例如注册地址分配等，编译器所生成的汇编代码往往都比手工编写的汇编代码更高效；2) 增强了可读性，上面的3种语言都是高级语言，可读性很好，易于调试和维护；3) 用高级语言编写的渲染程序要比用汇编代码书写的更能够适用于广泛的平台；4) 高级着色语言语法与C很相似，大大缩短了学习曲线。2.3. GPU的程序设计流程由于GPU具有适应于图形处理的特殊架构，使得它的程序设计流程与CPU的程序设计流程有较大的差异。图2可以简要的表示GPU的通用计算流程。原始的数据（通常是数组）被存放到纹理中，纹理被读入显存，作为数据流传入象素着色器中。每个着色器流水线对输入的数据流进行运算并将结果通过渲染纹理的方式写回显存或者直接写入帧缓存(Frame Buffer)后显示在屏幕上。图2 GPU通用计算流程3. 三维距离变换距离变换(Distance Transform, DT)是一种基于二值图像的全局操作，在骨架抽取、形状匹配、目标重建、机器人避障等图象分析与模式识别算法中有着广泛的应用。距离变换的结果不是另一幅二值图像，而是一幅灰度图像，每个象素的灰度级代表了该象素与距离最近的特征象素间距离大小的测度12。在实际计算中，往往采用两种距离测度：非欧氏距离和欧氏距离(Euclidean Distance)。前者常用的是城市街区距离(City-block Distance)、棋盘距离(Chess-board Distance)和切削距离(Chamfer Distance)。下面给出在三维情况下这几种距离变换的公式：三维欧式距离： （2.1）三维切削距离： (2.2)其中，表示图象中两个像素点，为的邻域。在三维中 ， 为相邻两点的近似欧氏距离： (2.3)本文采用的是切削距离的公式进行三维距离变换，体算法如下图3所示。虽然近年来有很多学者提出了很优秀的距离变换方法，但由于在GPU中进行程序设计有很大的局限性，故本文采取一种相对比较简单的算法进行计算。本算法的复杂度为O（n4）。图3 CPU三维距离变换流程图 4. 三维距离变换在GPU上的实现4.1. 纹理的组织本文的目的是要充分的利用GPU的并行计算能力，实现对三维距离变换算法的并行化并提高其计算速度。其中一个关键点就在于底层数据的表示，具体来说就是如何把数据更有效的组织到纹理中。虽然GPU本身提供三维纹理的操作，但是由于其对三维纹理的支持尚不成熟，效率也不高，而相对来说由于对二维纹理的渲染本身就是GPU的一个设计目标，故其对二维纹理提供了高效的处理能力。对于一个NNN的三维二值图象，我们可以将其分解为N个NN的二维二值图象。三维距离变换算法中，对每个前景点寻找其26邻域点只需要相邻的3张二维图象。从理论上说，虽然可以将三维体数据存放到内存的三维数组中，每次GPU用的时候再把需要的数据写入纹理，最后把计算得到的纹理写回内存，但是这样将导致内存和显存频繁的数据交换，严重影响算法的执行效率。故本文使用一个大小为N的二维纹理数组将上面的的N个NN的二维二值图象全部读入显存。一个标准的纹理单元有(ARGB)4个通道，占用41664Bit的空间，考虑当今主流的显存容量为256MB，可以存放256MB/64Bit=4194304个纹理单元，约只能存放161161161大小的三维数据。由于距离变换是对二值的图象进行操作，得到的结果是一个灰度图象，只需要1个通道就可以了。故我们可以考虑将4个数据元压缩进1个纹理单元中，这样256M的显存就能存放下256256256大小的三维数据集。当然主流显卡都能够设置一部分内存作为显存的补充，这样就能放下更大的三维图象了，尽管性能上有所损失。4.2. 算法的流程我们用微软公司的Direct3D作为应用程序的接口，用其自带的高级着色语言HLSL编写了三维距离变换的着色器程序，即流处理器程序片段“DT.fx”。该程序片段在Direct3D中又称为效果(Effect)，在该效果中实现2个手法(Technique)，一个用于实现距离变换的初始化，即将背景距离值设为0，前景点距离值设为无穷大；另外一个是距离变换的核心算法，它根据公式2.2，2.3，在传入的第i-1，i，i+1三层纹理中寻找第i层每一纹素的26邻域点的距离值，并以纹理渲染的方式更新其距离值。GPU三维距离变换流程如图4所示。图4 GPU三维距离变换流程图 由图4可以看出，算法将运算量最大的部分都交给GPU运行，这样就能充分利用GPU的并行处理能力，提高算法的效率。下面以一趟距离变换为例，详细说明GPU的实现过程：1) 对于N层纹理，顺序将第i层以及其相邻的第(i-1)、(i+1)层纹理用Effect-SetTexture()方法设置为着色器程序可以使用的纹理；2) 用Effect-SetVectorArray()方法将vSampleOffset数组（存放单层纹理中8-邻域的纹理坐标偏移量）传进着色器；3) 用Device-GetRenderTarget()方法将一个临时的纹理TempTexture设置为渲染目标，用于保存计算结果（纹理不能同时读写，故需要一个临时纹理用于写入）；4) 利用公式2.3，在GPU中更新第i层纹理的每个象素点的距离值，结果保存在2）中设置的临时纹理，保存的方法是象素着色器返回值，这一步骤使用的HLSL代码如下：PS_OUTPUT psDT(VS_INOUTPUT In)PS_OUTPUT Output; /* 声明一个存储返回值的结构体变量 */float v1, v2, v3;vSampleOffset0.xy += In.vTexCoord.xy;vSampleOffset8.xy += In.vTexCoord.xy; /* 从CPU传入的8-邻域纹理坐标的偏移量 */v1 = min3(tex2D(sImage0, vSampleOffset0.xy).r + (PACE*3),tex2D(sImage1, vSampleOffset0.xy).r + (PACE*2),tex2D(sImage2, vSampleOffset0.xy).r + (PACE*3);v2 = min3(tex2D(sImage0, vSampleOffset1.xy).r + (PACE*2),tex2D(sImage1, vSampleOffset1.xy).r + (PACE*1), tex2D(sImage2, vSampleOffset1.xy).r + (PACE*2);v3 = min3(tex2D(sImage0, vSampleOffset2.xy).r + (PACE*3), tex2D(sImage1, vSampleOffset2.xy).r + (PACE*2),tex2D(sImage2, vSampleOffset2.xy).r + (PACE*3);v1 = min3(v1, v2, v3);/* 根据该象素点的26邻域的距离值，更新该点的距离值 */Output.vColor = float4(v1, 0, 0, 0);return Output; /* 象素着色器返回值，用于渲染到场景 */5) 将渲染结果TempTexture写回传入的第i层纹理，对第i+1层纹理重复以上的步骤。4.3. 本算法的缺陷与改进办法本算法能比较好的将传统的距离变换算法并行化，能利用GPU的强大并行能力提高算法的效率。但其中有一个比较严重的缺陷。在CPU算法中，由于其串行性，我们可以很容易的设置一个观测变量来判断距离值是否有改变，根据这个变量的值来判断算法是否结束。但在GPU算法中，由于有多个点并行的进行距离变换，不能同时对一个变量或者说寄存器的同一实例执行写操作，故我们不能像CPU算法那样设置一个观测变量来终止程序。这意味着GPU算法不能直接累计该趟变换中距离值的改变次数来判断是否算法结束。由实验结果表明，对于一个NNN的三维数据集，算法的外层迭代次数总是小于N/2。故算法的结束条件可以改为外层循环N/2次。当然这样的改进方法并不完善，希望将来能找到更好的改进办法。5. 实验结果与结论实验平台为：2.0GHz的AMD双核速龙3600+处理器，1GB 双通道DDR2-667内存，Windows XP SP2操作系统。GPU为NVIDIA公司的GeForce 7600GT，其核心工作频率为575MHz,显存频率为1400MHz，显存位宽为128Bit，显存大小为256M。它提供了8个顶点处理器及12个象素处理器，每次能并行处理含4位通道的1个顶点或象素。应用程序使用C语言进行编写。使用了Direct3D 9c API以及HLSL来进行GPU方面的程序设计。在Visual Studio 2005的开发环境下进行了程序的编译及执行。本文采用的实验数据如图5所示，其中实验数据(a)为由N副图5(a)所重叠起来的一个NNN的立方体数据，该数据的特点是形状规则，并且前景点的数据量占整个数据集的比重很大；实验数据(b)为如图7所示的由三维扫描仪扫描得到的体数据。该数据的特点是形状不规则，前景点比较稀疏。 图5 GPU实验数据 （a）实验结果如表1和图6所示 ：表1 实验数据（a）的时间比较图6 实验数据（a）的结果图7GPU实验数据 （a）：分别为1，2，3号根实验结果如表2和图8所示，图8是1号根沿Y轴方向的相邻的16个切片，从中可以很明显的看到距离变换的效果。表2 实验数据（b）的时间比较图8 实验数据（b）1号根结果从表1可以看出来，对于实验数据(a)来说，GPU的算法有非常好的加速比。在初始化过程中，使用GPU实现几乎不花费多少时间，而在CPU上花费的时间则与N的规模成正比；在距离变换过程中，第一组数据（646464）GPU的并行优势并不明显，但是当数据量达到一定规模后，其加速比很快提高到了27倍左右。这是由于在GPU实现时，纹理是作为整体加载到流处理单元中执行，充分利用了GPU的并行计算能力；而在CPU实现时，必须使用一个三重循环对一个三维数组中的每一个象素顺次进行操作，其遍历一次256256256的数组进行初始化就需要6.7秒的时间。由表2数据3看不出来GPU的优势，这是因为规模小，迭代次数过少，使用CPU已经能达到很好的性能，GPU上因为数据载入及载出显存有一定时间耗费，所以实际性能可能稍弱于CPU实现。由上面的数据可以看到，GPU在所做计算相同的情况下，数据量越大，其处理效率越高，这是由于GPU是为了加速图形图像处理而出现的，它适用于计算密集型及数据密集型的运算。实验的效果图如图6，7所示。图6为实验数据(a)的立方体切掉1/4的大小后的效果图。图7为实验数据(b)的沿Y轴的连续16个切面图。参考文献：1 Govindaraju N. K., Redon S., Lin M., et al. Interactive collision detection between complex models in large environments using graphics hardwareA. In.Proc.of the Eurographics/SIGGRAPH Workshop on Graphics Hardware, 2003, 25-32.2 Krger J., Westermann R. Linear Algebra Operators for GPU Implementation of Numerical Algorithms J. ACM Transactions on Graphics, 2003, 22(3). 908-916.3 Harris M. Fast Fluid Dynamics Simulation on the GPU M. GPU Gems Chapter 38, Addison-Wesley ,2004.4 Moreland K., Angel A. The FFT on a GPU C/ In. Proc. of the Graphics Hardware, 2003.5 Bolz J., Farmer I., Grinspun