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

1、GPU 通用计算在三维距离变换中的应用田绪红 陈茂资 司徒志远华南农业大学信息学院计算机科学与工程系,广州 510642摘要:距离变换是图象处理的一个经典问题,在图象处理中有广泛的应用。本文结合 GPU 的特殊的体系结构,根 据三维距离变换的特点设计了相应的数据存储结构,充分利用 GPU 的并行处理能力,在 GPU 上实现三维距离变 换的算法。实验证明了基于 GPU 的并行算法可以得到很好的加速比,同时也提出了其中的局限性。关键词:GPU ; GPU 通用计算 (GPGPU;距离变换1. 引言近些年来图形处理器 (GPU的硬件技术飞速发展, 其更新速度非常快, 平均每年就有新的一代 GPU 推

2、 出市场。与之相随的是其可编程能力在不断的提高,出现了像 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 价格低廉,十分

3、有利 于推广。距离变换是图象处理的一个经典问题,在图象处理中有广泛的应用。由于三维距离变换的数据量非常 巨大,传统使用 CPU 计算的效率不高。本文尝试在 GPU 上实现三维距离变换算法,利用 GPU 的并行处 理能力提高变换的效率。2. GPU 通用计算 (GPGPU2.1. GPU 的体系架构GPU 是专门为图形图象处理而设计的硬件芯片,其设计初衷是为了减轻 CPU 的负担,将大部分的图 形图象运算如光照处理, 顶点运算, 纹理映射等功能转移到一块专门的芯片上。 这就是图象处理单元 (GPU的由来。从系统架构上看, GPU 是针对向量计算进行了优化的高度并行的数据流处理器,其中包括两种 流

4、处理单元:顶点着色器 (Vertex Shader, 是多指令多数据流的处理单元 (MIMD, 像素着色器 ( Pixel Shader是单指令多数据流的处理单元 (SIMD7,8。这种以数据流作为处理单元的处理器,在对数据流的处理上可 以获取较高的效率。由于 GPU 特殊的系统架构、整数运算逻辑运算支持的贫乏,以及其不同于传统 CPU 的数据存取方式,使得其并不能轻易的运用在非图形图象运算。 GPU 对于通用计算不是一服万能药 8,它 只能完成一些特定的计算。一般说来 GPU 通用计算有如下的特点 9,10:1 算法程序必须能被分解成为不相关的程序片段 (section,这些程序片段作为 G

5、PU 的计算内核,每个流 处理器执行相同的程序片段来并行求解最终的计算结果;2 由于 GPU 的特殊架构,使之更适合运算程序的循环结构而不适合运算程序的分支结构;3 每个程序片段的控制结构不能复杂,语句不能太多,实际应用中可以将复杂算法程序分解成几个规模 较小的代码模块;4 由于 GPU 是针对图形处理进行加速的,因此其中最主要的计算元素,或者说数据结构就是纹理 ;2.2. GPU 的编程接口现在比较流行和通用的图形接口有两个:DirectX 和 OpenGL 。二者都是为了方便人们对 GPU 进行编 程而产生的, 是一套底层 (low-level图形 API 。 利用其强大功能程序员可以十分

6、方便地与驱动程序沟通, 从 而运用 GPU 强大的三维图形处理能力,大幅度地提高三维程序的开发效率。 图 1 GPU工作示意图图 1所示的图形 API 是一套已定义好的, 提供给应用程序的接口和函数。 由于市面上的图形卡品种繁 多,每种卡的性能和结构都有所差异, HAL(Hardware Abstraction Layer,硬件抽象层 就应运而生。它由设 备厂商提供,向下指示特定设备完成具体操作,向上对 API 提供相同的调用接口。为了对 GPU 更好的控 制,人们又开发了着色语言 (Shading Language,当今比较流行的有 3种:Cg: C for Graphics,由 NVIDI

7、A 公司开发的一种针对 GPU 的程序设计语言 ;HLSL: High-Level Shading Language ,微软公司为 Direct3D 开发的着色语言,当今大部分的游戏 厂商都使用该种语言;GLSL :与 OPENGL 绑定的一种着色语言,由于 OPENGL 的开放性,其应用也相当广泛。 利用上面这样的高级着色语言的好处是显而易见的 1011:1 提高了生产力,用高级语言编写程序更简便更快捷,编译器可以自动优化代码并执行底层任务,例如 注册地址分配等,编译器所生成的汇编代码往往都比手工编写的汇编代码更高效;2 增强了可读性,上面的 3种语言都是高级语言,可读性很好,易于调试和维护

8、;3 用高级语言编写的渲染程序要比用汇编代码书写的更能够适用于广泛的平台;4 高级着色语言语法与 C 很相似,大大缩短了学习曲线。2.3. GPU 的程序设计流程由于 GPU 具有适应于图形处理的特殊架构,使得它的程序设计流程与 CPU 的程序设计流程有较大的 差异。图 2可以简要的表示 GPU 的通用计算流程。原始的数据(通常是数组被存放到纹理中,纹理被 读入显存,作为数据流传入象素着色器中。每个着色器流水线对输入的数据流进行运算并将结果通过渲染 纹理的方式写回显存或者直接写入帧缓存 (Frame Buffer后显示在屏幕上。 图 2 GPU通用计算流程3. 三维距离变换距离变换 (Dist

9、ance Transform, DT 是一种基于二值图像的全局操作,在骨架抽取、形状匹配、目标重 建、机器人避障等图象分析与模式识别算法中有着广泛的应用。距离变换的结果不是另一幅二值图像,而 是一幅灰度图像,每个象素的灰度级代表了该象素与距离最近的特征象素间距离大小的测度 12。在实际计算中,往往采用两种距离测度:非欧氏距离和欧氏距离 (Euclidean Distance 。前者常用的是 城市街区距离 (City-block Distance、棋盘距离 (Chess-board Distance和切削距离 (Chamfer Distance。下面给 出在三维情况下这几种距离变换的公式:三维欧

10、式距离:(2.1三维切削距离: +=p F p q p D q d p d p Nm q , 0, ( (min ( (2.2 其中, p q , 表示图象中两个像素点, (p N m 为 p 的 m 邻域。 在三维中 26=m , , (q p D 为相邻两点 q p , 的近似欧氏距离: =-=-=-=3|2|1| , (2, 32, 22, 1q p n q p n q p n q p D 5, 4, 3321=n n n(2.3本文采用的是切削距离的公式进行三维距离变换,体算法如下图 3所示。虽然近年来有很多学者提出 了很优秀的距离变换方法,但由于在 GPU 中进行程序设计有很大的局限

11、性,故本文采取一种相对比较简 单的算法进行计算。本算法的复杂度为 O (n 4 。 图 3 CPU三维距离变换流程图4. 三维距离变换在 GPU 上的实现4.1. 纹理的组织本文的目的是要充分的利用 GPU 的并行计算能力,实现对三维距离变换算法的并行化并提高其 计算速度。 其中一个关键点就在于底层数据的表示, 具体来说就是如何把数据更有效的组织到纹理中。 虽然 GPU 本身提供三维纹理的操作,但是由于其对三维纹理的支持尚不成熟,效率也不高,而相对 来说由于对二维纹理的渲染本身就是 GPU 的一个设计目标,故其对二维纹理提供了高效的处理能力。 对于一个 N ×N ×N 的三

12、维二值图象,我们可以将其分解为 N 个 N ×N 的二维二值图象。三维距 离变换算法中,对每个前景点寻找其 26邻域点只需要相邻的 3张二维图象。从理论上说,虽然可以 将三维体数据存放到内存的三维数组中,每次 GPU 用的时候再把需要的数据写入纹理,最后把计算 得到的纹理写回内存,但是这样将导致内存和显存频繁的数据交换,严重影响算法的执行效率。故本 文使用一个大小为 N 的二维纹理数组将上面的的 N 个 N ×N 的二维二值图象全部读入显存。 一个标准 的纹理单元有 (ARGB4个通道,占用 4×16=64Bit 的空间,考虑当今主流的显存容量为 256MB ,可

13、 以存放 256MB/64Bit=4194304个纹理单元, 约只能存放 161×161×161大小的三维数据。 由于距离变 换是对二值的图象进行操作,得到的结果是一个灰度图象,只需要 1个通道就可以了。故我们可以考 虑将 4个数据元压缩进 1个纹理单元中,这样 256M 的显存就能存放下 256×256×256大小的三维数 据集。当然主流显卡都能够设置一部分内存作为显存的补充,这样就能放下更大的三维图象了,尽管 性能上有所损失。4.2. 算法的流程我们用微软公司的 Direct3D 作为应用程序的接口, 用其自带的高级着色语言 HLSL 编写了三维距

14、离变换的着色器程序,即流处理器程序片段“ 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 的并

15、行处 理能力,提高算法的效率。下面以一趟距离变换为例,详细说明 GPU 的实现过程:1 对于 N 层纹理,顺序将第 i 层以及其相邻的第 (i-1、 (i+1层纹理用 Effect->SetTexture(方法设置为着 色器程序可以使用的纹理;2 用 Effect->SetVectorArray(方法将 vSampleOffset 数组(存放单层纹理中 8-邻域的纹理坐标偏移量传 进着色器;3 用 Device->GetRenderTarget(方法将一个临时的纹理 TempTexture 设置为渲染目标,用于保存计算结 果(纹理不能同时读写,故需要一个临时纹理用于写入;4

16、利用公式 2.3,在 GPU 中更新第 i 层纹理的每个象素点的距离值,结果保存在 2中设置的临时纹理, 保存的方法是象素着色器返回值,这一步骤使用的 HLSL 代码如下:PS_OUTPUT psDT(VS_INOUTPUT InPS_OUTPUT Output; /* 声明一个存储返回值的结构体变量 */float v1, v2, v3;本文采用的实验数据如图 5 所示，其中实验数据(a为由 N 副图 5(a所重叠起来的一个 N×N×N 的立方体数据，该数据的特点是形状规则，并且前景点的数据量占整个数据集的比重很大；实验数据 (b为如图 7 所示的由三维扫描仪扫描得到的体

17、数据。该数据的特点是形状不规则，前景点比较稀疏。 图 5 GPU 实验数据 （a） 实验结果如表 1 和图 6 所示 ： 64×64×64 GPU初始化时间(ms GPU距离变换时间(ms CPU初始化时间(ms CPU距离变换时间(ms 距离变换迭代次数 距离变换加速比 0 296 109 3,703 31 12.51 128×128×128 256×256×256 16 16 1,344 18,672 859 6,703 62,891 1,006,594 63 127 46.79 53.90 表 1 实验数据（a）的时间比较 图

18、6 实验数据（a）的结果 图 7GPU 实验数据 （a） ：分别为 1，2，3 号根 实验结果如表 2 和图 8 所示，图 8 是 1 号根沿 Y 轴方向的相邻的 16 个切片，从中可以很明显的 看到距离变换的效果。 1号根：173×205×145 2号根：209×119×298 3号根：171×162×146 前景点个数 GPU初始化时间(ms GPU距离变换时间(ms CPU初始化时间(ms CPU距离变换时间(ms 距离变换迭代次数 距离变换加速比 242,323 16 1,992 2,109 9,641 22 5.04 表 2 实验数据（b）的时间比较 137,896 16 1,648 3,062 4,531 15 2.75 23,899 0 447 1,656 438 5 0.97 图 8 实验数据（b）1 号根结果 从表 1 可以看出来，对于实验数据(a来说，GPU 的算法