 Computer Science and Application 计算机科学与应用, 2013, 3, 153-158 http://dx.doi.org/10.12677/csa.2013.33027 Published Online June 2013 (http://www.hanspub.org/journal/csa.html) GPU-Based Parallel Prewitt Algorithm Implementation and Its Application on GPR* Tuyou Peng1, Qinghua Dong2 1Department of Electronics & Information Technology, Jiangmen Polytechnic, Jiangmen 2Department of Civil Engineering and Architecture, Wuyi University, Jiangmen Email: typeng2001@yahoo.com, dqh0359@126.com Received: Mar. 27th, 2013; revised: Apr. 12th, 2013; accepted: Apr. 21st, 2013 Copyright © 2013 Tuyou Peng, Qinghua Dong. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Abstract: The edge of image is one of the important features of the image. Edge detection is an important means to extract image features. GPU-CUDA parallel technology, as the most popular high-performance processing technology, is the best choice for parallel Prewitt algorithm implementation. Since conventional Prewitt algorithm based on CPU is computationally intensive and time-consuming, its application is very restricted. In order to improve the efficiency of Prewitt algorithm, GPU-based parallel Prewitt algorithm and fast imaging algorithm are applied to get higher speedup. Finally, the method is proposed by turning the GPR field data into gray-scale image data, then implementation of GPR field data processing with the Prewitt algorithm based on GPU. It is proved that the algorithm is not only of high effi- ciency, but also effective to improve target identification capability. Keywords: Edge Detection; Prewitt Algorithm; GPU-CUDA; Ground Penetrating Radar; Imaging 基于 GPU 的Prewitt 算法实现及其在探地雷达中的应用* 彭土有1，董清华 2 1江门职业技术学院电子与信息技术系，江门 2五邑大学土木建筑系，江门 Email: typeng2001@yahoo.com, dqh0359@126.com 收稿日期：2013 年3月27 日；修回日期：2013年4月12日；录用日期：2013 年4月21 日 摘 要：图像的边缘是图像的重要特征之一，边缘检测是提取图像特征的重要手段。GPU-CUDA 并行技术作为 当前最热门的高性能处理技术，是并行Prewitt 边缘检测算法实现的首选。由于常规的基于 CPU 的Prewitt 算法 计算量大、耗时，其应用受到很大限制。为了提高算法的效率，文中应用 GPU-CUDA 技术实现 Prewitt 算法及 快速成像，获得了较高的加速比。最后，通过将实测探地雷达数据转换成灰度图像数据，并实施基于 GPU 的 Prewitt 算法处理的方法思路，对实测探地雷达数据进行处理。试验结果表明该算法不仅运行效率高，而且在突 出有效异常，提高目标体的识别能力方面取得实效。 关键词：边缘检测；Prewitt 算法；GPU-CUDA；探地雷达；成像 1. 引言 边缘检测是图像处理和计算机视觉中的基本方 法，构成了图像特征提取的重要研究领域。边缘检测 的目的是标识数字图像中亮度变化明显的点。图像属 性中的显著变化通常反映了属性的重要事件和变化。 例如：深度上的不连续、表面方向上的不连续、物质 *基金项目：基于 Linux 地质雷达一体化处理解释技术及应用基金 项目：2011 年省部产学研结合项目(2011B090400120)。 Copyright © 2013 Hanspub 153  基于 GPU 的Prewitt 算法实现及其在探地雷达中的应用 属性的变化和场景照明的变化等。因此，物质属性的 变化必然在探地雷达GPR (Ground Penetrating Radar) 成像中有所反映[1]。本文探讨应用近年来新发展起来 的GPU-CUDA[2]技术实现 Prewitt 边缘检测算法，提 出将实测探地雷达数据转换成灰度图像数据后，再实 施基于 GPU 的Prewitt 算法处理的方法思路，对实测 探地雷达数据进行处理[3]和基于 GPU 的快速成像，以 求取得好的应用效果。试验结果表明该算法不仅运行 效率高，较好的解决了探地雷达一体化处理解释中的 图形冻结问题，而且在突出有效异常，提高目标体的 识别能力方面取得实效。 2. Prewitt算法原理 多年以来，人们提出了许多以微分法[4]为基础的 边缘检测算法，并以数据块与模板卷积的手段提取图 像边缘。常用边缘检测算法包括Roberts Cross 算法、 Prewitt 算法、Sobel 算法、Canny算法和 Laplace 算法。 Prewitt 算法作为一阶微分算子的边缘检测算法[5]，它 利用像素点左右、上下相邻点的灰度差在边缘处达到 极值的重要特征来检测边缘和去掉部分伪边缘，对噪 声具有平滑作用。其原理是在图像空间中，将左右、 上下相邻点构成的3 × 3 数据块(图1)与水平、垂直两 个方向模板进行卷积运算来完成。其中：水平模板(图 2)用于检测水平边缘，垂直模板(图3)用于检测垂直边 缘。 对于像素点p(i,j)，Prewitt 算法定义如下： 水平方向梯度： 1, 11,1, 1 1, 11,1,1 xpij pijpij pi jpi jpi j P(i − 1, j − 1) P(i − 1, j)P(i − 1, j + 1) P(i, j + 1) P(i + 1, j + 1) P(i + 1, j) P(i, j − 1) P(i + 1, j − 1) P(i, j) Figure 1. P(i,j) pixel and its 3 × 3 pixel neighborhood 图1. P(i,j)像素点及其 3 × 3像素邻域 1 1 1 0 0 0 −1 −1 −1 Figure 2. Horizontal template 1 1 1 图2. 水平模板 0 −1 −10 0 −1 Figure 3. Vertical template 垂直方向梯度： 图3. 垂直模板 1, 1, 11, 1 1, 1,11, 1 ypij pij pij pij pij pij 12 22 ,gijx y 梯度： 其中素点 p(i,j)邻域的 3数据块与水平模 算法的 实现 通过 Prewitt 算法分析可知：计算过程中不需要利 用已 ； 间，其中 拷贝回至设备端； 端。 以及 idth*sizeof(float);//计算图 ：x为像 3 × 板的卷积；y为像素点p(i,j)邻域的3 × 3数据块与垂 直模板的卷积；计算出梯度g(i,j)后，把 g(i,j)值大于 255 的点标记为边界点，其像素值设定为 255(即白点)， 否则设定像素值为g(i,j)的值。Prewitt 算法的串行实现 简单，但是，由于需要做大量的卷积运算，当图像分 辨率较高时，计算量很大，需要较长的运算时间，难 以满足实际工作要求。 3. PrewittGPU-CUDA 经完成的像素处理结果参与，符合 GPU-CUDA (Compute Unified Device Architecture)数据并行处理要 求。因此，可以将Prewitt 算法中的所有单线程循环改 为GPU-CUDA 多线程并行处理，从而提高算法的效 率。根据 CUDA程序设计思想(即CPU进行数据准备、 初始化 GPU 设备以及执行串行代码，GPU 进行并行 计算并向 CPU 返回计算结果)，按如下算法过程完成 Prewitt 算法在 GPU-CUDA 的实现： 1) 由主机端程序完成数据的初始化 2) 申请两块与图像数据相等容量的设备内存空 一块用于存放由主机传送过来的图像数据， 另一块用于存放设备中内核并行程序进行 Prewitt 算 法处理后的结果； 3) 将主机端图像数据 4) 调用设备内核并行程序； 5) 将处理后的图像数据拷贝回主机 Prewitt 并行算法的关键是并行处理网格的构造 内核并行程序实现，构造并行处理网格源代码如 下[6]： int lineByte = screenW Copyright © 2013 Hanspub 154  基于 GPU 的Prewitt 算法实现及其在探地雷达中的应用 像数 loc((void **)&d_DataIn,lineByte*screen High d_DataOut,lineByte*screen High h_DataIn, lineByte*screen High im3 dimBlock1(256,1);//构造并行处理网格 2) + 255) imBlock1>>>(d_Data In,d_ emcpy(h_DataOut,d_DataOut,lineByte*screen High 核并行程序实现源代码如下： oat *d_DataIn, float dx.x;// 计算 nHigh-2))// 控制图像 处理 w=id/(screenWidth-2) + 1;//图像矩阵行编号 row int col=id%(screenWidth-2) + 1; //图像矩阵列编号 col int x,y,result; ow-1)*screenWidth+(col-1))+*(d_ Data ataIn+(row-1)*screenWidth+(col-1))+*(d_ Data 计算梯度值 g(i,j)的平方值 Prew 4736G(含GEFORCE G105M CUD 应用 Prewitt 边缘检测技术处理探地雷达数据的 前提 有实测雷达 数据 idth;j++) idth+j)) min=* (h_D nWidth+j)) max=* (h_D +)// 每点数据进行行列 变换 ((255**(h_DataIn+ i*scr - 处理 640 × 480 1024 × 768 1280 × 768 据大小 cudaMal );//申请设备内存空间 cudaMalloc((void **)& );//申请设备内存空间 cudaMemcpy(d_DataIn, ,cudaMemcpyHostToDevice);// 图像数据拷贝至设 备端 d dim3 dimGrid1(((screenWidth-2)*(screenHigh- /256,1);//构造并行处理网格 prewittProcess<<<dimGrid1,d DataOut,screenWidth,screenHigh);//调用内核并行 处理函数 cudaM ,cudaMemcpyDeviceToHost);// 处理结果拷贝回主 机端 内 __global__ void prewittProcess(fl *d_DataOut,int screenWidth,int screenHigh) {unsigned int id = 256*gridDim.x + threadI 并行处理网格的索引号id if(id<(screenWidth-2)*(scree 范围 {int ro x=*(d_DataIn+(r In+(row-1)*screenWidth+(col))+*(d_DataIn+(row- 1)*screenWidth + (col+1))-*(d_DataIn+(row+1)*screen Width+(col-1))-*(d_DataIn+(row+1)*screenWidth+(col) )-*(d_DataIn+(row+1)*screenWidth+(col+1));// 计算水 平方向梯度 y=*(d_D In+row*screenWidth+(col-1))+*(d_DataIn + (row + 1)*screenWidth + (col-1))-*(d_DataIn + (row-1)*screen Width+(col+1))-*(d_DataIn+row*screenWidth+(col+1)) -*(d_DataIn + (row + 1)*screenWidth+(col+1));//计算 垂直方向梯度 result=x*x+y*y;// *(d_DataOut+row*screenWidth+col)=result;// 保存 itt 并行处理结果}} 实验在 Acer ASPIRE A 512M 图形卡)手提电脑上完成，试验计算结果 如表 1所示，获得了较好的加速比，满足了对探地雷 达数据进行实时交互处理解释的实际需要，圆满地解 决了操作界面冻结问题。 4. Prewitt算法在探地雷达中的成功应用 4.1. 实测雷达数据转化为灰度图像数据 是需要把实测雷达数据转化为灰度图像数据。实 测雷达数据是按道存储，必须在转化为灰度图像数据 的同时进行行列变换。具体实现方法为[7]：遍历所有 实测雷达数据求取最大、最小值，将实测雷达按数据 最大值对应 255，最小值对应 0的准则进行线性变换 求取灰度图像数据。与此同时，完成行列变换后成为 真正的灰度图像数据。主要代码如下： for(int i=0;i<screenHigh;i++)//遍历所 求取最大、最小值 for(int j=0;j<screenW {if(min>*(h_DataIn+i*screenW ataIn+i*screenWidth+j); if(max<*(h_DataIn+i*scree ataIn+i*screenWidth+j);} for(int i=0;i<screenHigh;i+ ，同时转换为灰度图像数据。 for(int j=0;j<screenWidth;j++) {*(h_DataIn+i*screenWidth+j)= eenWidth+j)/(max-min)-255*min/(max-min)));} Table 1. Time comparison of CUP and GPU on different resolu tions 表1. 不同分辨率图像 CUP 与GPU 处理时间对比 时间 单位：秒 CPU 2.245 4.018 5.323 GPU 0.458 0.461 0.551 加速比 4.90 8.72 9.66 Copyright © 2013 Hanspub 155  基于 GPU 的Prewitt 算法实现及其在探地雷达中的应用 以上预处理工 成后，调 于GP DA 实现 处理结果的 GPU快速彩色成像 标数 算法内 核并 Map(float4 *positions,float *seis {unsigned int i=blockIdx.x*blockDim.x + thread 作完用基 U-CU 的Prewitt 算法对灰度图像数据进行边缘检测。边 缘检测结果再按如下实现的GPU 快速彩色成像方法 成像。 4.2. Prewitt 探地雷达 GPU 快速彩色成像算法的关键是在色 据基础上，如何实现色标数据的转换及彩色成像 的GPU 多线程处理[8]？文中通过GPU 多线程并行并 读写 OpenGL 成图缓冲区方法直接成像，极大地提高 了探地雷达成像速度，解决了当前探地雷达彩色成像 速度慢造成程序操作界面冻结等问题。探地雷达GPU 快速彩色成像算法流程图如图4所示[9]。 根据图 4所示流程图，设计快速彩色成像 行程序源代码如下： __global__void prepare mic, float *tmp_color, int screenWidth, int screen- High, float min, float max, int colorTableLength, float TranspSliderValue)//每个线程负责生成一个像素点数 据 选取支持CUDA并行的GPU设备 并初始化设备 在GPU设备上分配存放成图地质雷达数据和色 标颜色数据的内存空间 将主机内存中成图地质雷达数据和色标颜色 数据拷贝至GPU设备内存空间 构造与成图宽度、高度范围一致的并行线程 网格 调用GPU多线程并行程序，每个线程负责生成 一个像素点数据 绘图结束 多线程同步 像素数据直接写入OpenGL成图缓冲区成图 Figure 4. Flow chart of GPU fast imaging algorithm 图4. GPU快速彩色成像算法流程图 Idx.x; signed int j=blockIdx.y*blockDim.y+threadIdx.y; 1)**(seismic +i*scree 数据采用 GPU 快速彩色成 像算法的直接成像，并包括探地雷达系统的总控 界面；图是实测探地雷达数据经过GPU-CUDA 的Prewitt 边缘检测处理后再采用GPU 快速彩色 速比，克服了常规 单进程处理速度过慢引起 窗口界面冻结问题。 6看出，目标体周围的电磁 波绕射干扰 受到，目标体的边界更加清 藏深度只有25塑料管 C处是人工砖砌排水管， 埋藏深度 1.1 M(为 便于观察目标异常，已对上 述成像在垂直了 1 M的向下平移)。由此可 高探地雷 效方法。 Prewitt 边缘检测算法的基础上，首先设计 并实现了基于 CUDA 的Prewitt 快速算法。为了 能够应 中提出了先将实测探地雷达数据转化为灰度图像数 据，然后再调用 快速算法处理，最后应用GPU 快速彩色成像算法成像的工作流程。实验结果表明： //计算并行处理网格的索引号i un //计算并行处理网格的索引号j if(i<screenWidth && j<screenHigh)//成像数据范 围：screenWidth*screenHigh {int index=(int)(((colorTableLength- nHigh+j)/(max-min)-(colorTableLength-1)*min/ (max-min)));//根据定义的色标数据，计算成像数据 if(index<0)index=0; if(index>colorTableLength-1) index=colorTableLength-1; *(positions+i*screenHigh+j) =make_float4(*(tmp_color+index*3 + 0),*(tmp_color + index*3 + 1), *(tmp_color + index*3 + 2),TranspSlider Value);//生成彩色成像数据}} 4.3. 实验结果与分析 图5是实测探地雷达 软件 6基于 成像 算法的成像；由于Prewitt 算法和彩色成像均采用 GPU 多线程并行处理，两者组合处理能达到近 10倍的加 CPU 的 从图 [10] 明显压制 晰。位于 A、B、C三处的地下管线埋设情况及管线 边界更加准确，其中，A、B两处地下管是距地面埋 CM的 ， 注： 了 方向进行 见，应用 Prewitt 算法处理实测探地雷达数据对突出有 效异常，提高目标体的识别能力效果明显，是一种提 达分辨率的有 5. 结语 在分析 GPU- 用Prewitt 快速算法于探地雷达的数据处理，文 Prewitt Copyright © 2013 Hanspub 156  基于 GPU 的Prewitt 算法实现及其在探地雷达中的应用 Copyright © 2013 Hanspub 157 Figure 5. Imaging of GPR field data 图5. 野外实测探地雷达成像 Figure 6. GPR data imaging after applying Prewitt algorithm 图6. Prewitt算法处理后的探地雷达成像  基于 GPU 的Prewitt 算法实现及其在探地雷达中的应用 该工作流程及实现方法既有效解决了常规 CPU 算法 的界面冻结问题，又在突出有效异常，提高目标体的 识别能力方面取得了良好的应用效果。 参考文献 (References) [1] 粟毅. 探地雷达理论与应用[M]. 北京: 科学出版社, 2006. [2] NVIDIA. CUDA programming guide, 2012. http://www.nvidia.com/object/cuda_home.html [3] 杨峰, 彭苏萍. 地质雷达探测原理与方法研究[M]. 北京: 科 学出版社, 2010. [4] 李荣华, 刘播. 微分方程数值解法(第四版)[M]. 北京: 高等 教育出版社, 2010. [5] 曾胜田, 刘羽等. 基于 CUDA的Prewitt 算子并行实现[J]. 微 计算机应用, 2011, 11: 71-75. [6] 蒋长锦. 科学计算与 C程序集[M]. 北京: 中国水利水电出版 社, 2010. [7] J. E. Lucius, M. H. Powers. GPR data processing computer soft- ware for the PC. Reston: United States Geological Survey (USGS), 2002: 151-158. [8] T. Y. Peng, J. X. Cao. The implementation and fast visualization application of Linux-based QT-GPU parallel architecture. Ameri- can Journal of Engineering and Technology Research, 2011, 11 (12): 2063-2068. [9] 彭土有, 叶亚平等. 意大利 RIS-2K 探地雷达数据解密及其快 速可视化方法[J]. 计算机时代, 2012, 7: 17-20. [10] 孟陆波, 李天斌等. 地质雷达超 前预测不良地质体图像的智 能识别[J]. 煤田地质与勘探, 2009, 2: 86-89. Copyright © 2013 Hanspub 158 |