基于OpenCL的Prewitt算法的并行实现

马歌+肖汉

摘 要： Prewitt算法是数字图像分割中最常用的边缘检测算法。采用传统CPU上的串行方法实现该算法需要较大的计算量、耗时较长，因此，通过GPU对其进行性能加速有着重要的意义。然而由于GPU硬件体系结构的差异性，跨平台移植是一件非常困难的工作。针对上述问题，提出了一种基于OpenCL异构框架的Prewitt图像边缘检测并行算法。实验结果表明，该并行算法比CPU上的串行算法运行速度快，加速比可达30倍，有效地提高了大规模数据处理的效率，可移植性好，具有较高的应用价值。

关键词： OpenCL； 异构框架； 边缘检测； Prewitt算法； 并行实现

中图分类号： TN919?34； TP391 文献标识码： A 文章编号： 1004?373X（2014）20?0103?04

Implementation of Prewitt algorithm parallel based on OpenCL

MA Ge， XIAO Han

（College of Information Science & Technology， Zhengzhou Normal University， Zhengzhou 450044， China）

Abstract： Prewitt algorithm is the most commonly used edge detection algorithm in digital image segmentation， but large amount of calculations and great time consumption are needed to be suffered if traditional CPU serial method is used to implement the algorithm. Therefore， it is important to accelerate its performance by GPU. However， the cross platform transplantation is very difficult because of the difference of GPU hardware system structure. In view of the above questions， a parallel algorithm of Prewitt image edge detection based on OpenCL heterogeneous framework is proposed. The experimental results show that the running speed of the parallel algorithm is faster than that of the serial algorithm in CPU， and its speedup ratio is 30 times as the serial algorithm. It improved the efficiency of large-scale data processing effectively. It has good portability and high application value.

Keywords： OpenCL； heterogeneous framework； edge detecetion； Prewitt algorithm； parallel implementation

0 引 言

边缘检测技术是图像处理和计算机视觉等领域最基本的技术[1]。当前，图像边缘检测技术主要利用以CPU为核心的传统计算资源进行处理，计算量大、能耗高、效率低，不能很好地满足高分辨率图像的快速处理。

随着可编程图形处理器技术的快速发展，当前的GPU已经具有很强的并行计算能力，越来越多的算法被成功移植到GPU平台上，并取得了很好的加速效果。然而由于GPU硬件体系结构的差异性，在不同GPU硬件平台间实现算法移植是一件非常困难的工作。目前国内外已有的研究工作一般只针对单一的硬件平台，没有考虑不同硬件平台间的可移植性。

近几年来，由多核CPU、GPU或其他类型的处理器组成的异构框架作为一种新的计算机体系架构逐渐成为主流。其中，开放式计算语言（Open Computing Language，OpenCL）作为面向异构计算平台的通用编程框架[2]，一方面在实现性能目标的同时降低了能耗，另一方面为实现GPU通用计算程序的跨平台移植提供了解决方案。为此，本文提出了一种基于OpenCL异构框架的Prewitt并行算法。

1 Prewitt算法原理

图像的边缘是图像的重要特征之一。常用边缘检测算法包括Roberts算法、Prewitt算法、Sobel算法、Canny算法和Laplace算法。

Prewitt算法作为一阶微分算子的边缘检测算法[3]，利用像素点上下、左右相邻点的灰度差，在边缘处达到极值检测边缘，去掉部分伪边缘，对噪声具有平滑作用。其原理是在图像空间利用图1所示的水平、垂直两个方向的3×3模板与图2所示的图像像素3×3邻域进行卷积运算来完成。一个模板通常的垂直边缘响应最大，而另一个对水平边缘响应最大。

图1 水平模板和垂直模板

图2 f（i，j）的3×3像素邻域

图1中：水平模板用于检测水平边缘，垂直模板用于检测垂直边缘。在处理时，图像中每个点都用这两个模板进行卷积，两个卷积的最大值作为该点的输出位。运算结果是一幅边缘幅度图像。图内模板的数字是模板系数，中间的点表示中心元素。

对于像素f（i，j），则Prewitt算法定义如下：

水平方向梯度计算：

[Gx=fi-1，j-1+fi-1，j+fi-1，j+1- fi+1，j-1-fi+1，j-fi+1，j+1]

垂直方向梯度计算：

[Gy=fi-1，j-1+fi，j-1+fi+1，j+1- fi-1，j+1-fi，j+1-fi+1，j+1]

梯度：[G（i，j）=Gx2+Gy2]

其中：[Gx]为像素点f（i，j）的3×3领域与水平方向模板的卷积；[Gy]为像素点f（i，j）的3×3领域与垂直方向模板的卷积。求出梯度G后，设定一个常数n（n≤255），当G>n时，标出该点为边界点，其像素值设定为255（白点），否则设定为G。实验表明，CPU上的Prewitt串行算法实现简单，但是，由于需要做大量的卷积运算，当图像分辨率较高时，计算量很大，耗时较长，难以满足大规模数据处理的要求。

2 OpenCL简介

OpenCL提供了统一的面向异构系统的并行编程环境。OpenCL架构包括四部分：

2.1 平台模型

OpenCL平台模型由一个主机（Host）连接一个或多个能执行OpenCL的设备（Device）构成。在AMD的OpenCL平台中，主机一般指x86 CPU[4]。所有由OpenCL编写的应用程序都是从主机启动并在主机上结束的，主机管理着整个平台上的所有计算资源。每个OpenCL设备包括一个或多个计算单元（CU），每个计算单元又包括一个或多个处理单元（PE）。应用程序会从主机端向各个OpenCL设备的处理单元发送计算命令。该模型主要用来编写能够在设备上执行的OpenCL的kernel函数。如图3所示。

图3 OpenCL的平台模型

2.2 执行模型

OpenCL的执行模型包括在主机上执行的主程序（Host Program）和在OpenCL设备上执行的内核程序（kernel）[5]。OpenCL执行模型主要管理kernel在OpenCL设备上的运行。

在主机将内核程序交到设备上执行时，系统便会创建一个N维（可以是一维，二维或者三维）的工作空间（NDRange）。工作空间被划分为多个工作组（work group，也就是块）。每个工作组又包含多个节点（workitem，也就是线程）。所有工作节点都将执行相同的内核程序。用全局ID（global ID）表示每个工作节点在相应维度上的索引，用局部ID（local ID） 表示工作组内部的节点相对该工作组的位置索引。通过一个global ID和一个work group 内的local ID，就能标定一个workitem。

如图4是一个二维工作空间NDRang（Gx，Gy）的例子。工作空间的workitem数量为Gx乘以Gy，一个workgroup内的workitem的数量为Sx乘以Sy。

2.3 内存模型

OpenCL的内存模型定义被kernel用到的抽象内存层次，有四种内存类型，包括全局内存（Global Memory）、常数内存（Constant Memory）、局部内存（Local Memory）、私有内存（Private Memory）。各种内存之间的数据传输必须是显式进行的。

图4 二维索引空间

全局内存：工作空间内所有的工作节点都可以读/写的该内存区域中一个内存对象的任何元素。

常量内存：工作空间内所有的工作节点都可以只读的内存区域。这个内存区域在内核程序的执行过程中保持不变。主机分配并初始化该内存中的存储对象。

局部内存：局部从属于一个工作组的内存区域。这个内存区域可以用来分配由该工作组中所有工作节点共享的变量。

私有内存：是一个工作节点私有的内存区域。一个工作节点在该内存区域中定义的变量对其他工作节点不可见。

2.4 编程模型

OpenCL的编程模型分为：数据并行编程模型、任务并行编程模型和混合编程模型。数据并行编程模型是在编写OpenCL并行程序时采用的首要模型。

数据并行编程模型用一系列操作一个存储对象的多个元素的指令的形式定义了计算。OpenCL实现的是一种松散的数据并行编程模型，它不需要workitem和内存对象元素之间严格的一对一的映射。workgroup可以显示指定，也可以隐式指定。

任务并行编程模型使内核程序的执行独立于线程索引空间。一个计算部件上只有一个workitem执行内核程序。

3 Prewitt算法的并行实现

3.1 主机端程序

Step1：先获得OpenCL的平台信息，在此平台上选定OpenCL设备，如GPU。接着建立上下文环境，并建立命令队列用来执行内核实例。

Step2：创建并编译源程序，建立内核实例。将内核程序代码保存在“Prewitt_Kernel.cl”文件中，读到内存并存储为字符串数组形式。

Step3：首先分配主机内存，将bmp灰度图像数据读入到主机内存中。然后，在显存中申请2块与图像数据相等容量的空间。一块用于存放主机内存中图像数据拷贝，另一外用于存放图像数据的处理的结果，将数据复制到显存上。

Step4：设置内核参数。

Step5：执行内核程序。调用设备端kernel函数，将处理过程交由设备。

Ste：6：验证结果。

Step7：将控制权交回主机端，把计算结果从显存复制到主机内存中。

Step8：释放系统所占资源，并由主机端将经过处理的图像结果显示输出。

Step9：输出状态和运行时间。

3.2 设备端程序

使用设备GPU时，Prewitt并行算法的图像卷积运算需要调用kernel程序实现。设备GPU根据主机端调用kernel函数时指定的参数形成块（Block）数workgroup以及每个块内线程（Threads）数workitem，线程数为256。

4 实验结果与分析

4.1 实验运行平台

硬件平台： CPU采用Intel（R） Xeon（R） CPU E5620@2.40 GHz，4核、8线程。系统内存为12.0 GB DDR3。 显卡采用AMD Radeon HD 6970，GPU为Cayman，显存为2 GB GDDR5。

软件平台：操作系统为64位Windows 7专业版。程序开发环境为Visual Stadio 2010，以及AMD?APP?SDK 2.8。

4.2 实验步骤与记录数据

预先处理好六幅不同分辨率大小的bmp灰度图像，使用它们进行Prewitt边缘检测算法对比实验，分别运行CPU上的串行算法和OpenCL异构框架上的并行算法，并记录处理时间，结果如表1所示。

表1 不同分辨率图像处理时间对比

图5为1 920×1 200分辨率的原始图像，图6和图7分别为对原图进行串行和并行 Prewitt图像边缘检测算法的运行结果。

图5 原图

图6 Prewitt串行算法运行结果图

图7 Prewitt并行算法运行结果图

4.3 性能分析

实验结果表明：随着图像分辨率的不断增大，GPU的加速效果十分明显。例如，在GPU上运行Prewitt并行算法对分辨率为4 800×3 600的图像进行边缘检测，加速比达到了30倍。

5 结 语

提出了一种基于OpenCL的 Prewitt图像边缘检测的算法，借助GPU 高效的运算能力，在显存中对图像进行了并行化的边缘检测，获得了较清晰的处理图像。通过实验可以看出，采用OpenCL异构框架实现Prewitt并行算法，有较好的通用性和可移植性，可以大大提高算法的执行效率，对其他通用并行算法的实现有一定借鉴作用。

参考文献

[1] 杨道普，马秋禾，石磊.边缘检测Prewitt算子的改进算法[J].测绘科学，2008，33（z3）：100?103.

[2] 肖汉，郭运宏，周清雷.面向CPU_GPU异构计算的SIFT特征匹配并行算法[J].同济大学学报：自然科学版，2013，41（11）：1732?1737.

[3] GASTER B R， LEE H， KAELI D R， et al. OpenCL异构计算[M].张云泉，张先轶，龙国平，等译.北京：清华大学出版社，2012.

[4] 刘蕊.数字图像中边缘检测算法的研究[D].镇江：江苏科技大学，2009.

[5] 迈克老狼.AMD 大学教程中文版[EB/OL]. [2013-01-03].http：//www.opengpu.org.

[6] AMD上海研发中心.跨平台的多核与众核编程讲义：OpenCL的方式[M].上海：AMD上海研发中心，2010.

[7] 肖汉，周清雷，张祖勋.基于多GPU的Harris角点检测并行算法[J].武汉大学学报：信息科学版，2012，37（7）：876?880.

Step4：设置内核参数。

Step5：执行内核程序。调用设备端kernel函数，将处理过程交由设备。

Ste：6：验证结果。

Step7：将控制权交回主机端，把计算结果从显存复制到主机内存中。

Step8：释放系统所占资源，并由主机端将经过处理的图像结果显示输出。

Step9：输出状态和运行时间。

3.2 设备端程序

使用设备GPU时，Prewitt并行算法的图像卷积运算需要调用kernel程序实现。设备GPU根据主机端调用kernel函数时指定的参数形成块（Block）数workgroup以及每个块内线程（Threads）数workitem，线程数为256。

4 实验结果与分析

4.1 实验运行平台

硬件平台： CPU采用Intel（R） Xeon（R） CPU E5620@2.40 GHz，4核、8线程。系统内存为12.0 GB DDR3。 显卡采用AMD Radeon HD 6970，GPU为Cayman，显存为2 GB GDDR5。

软件平台：操作系统为64位Windows 7专业版。程序开发环境为Visual Stadio 2010，以及AMD?APP?SDK 2.8。

4.2 实验步骤与记录数据

预先处理好六幅不同分辨率大小的bmp灰度图像，使用它们进行Prewitt边缘检测算法对比实验，分别运行CPU上的串行算法和OpenCL异构框架上的并行算法，并记录处理时间，结果如表1所示。

表1 不同分辨率图像处理时间对比

图5为1 920×1 200分辨率的原始图像，图6和图7分别为对原图进行串行和并行 Prewitt图像边缘检测算法的运行结果。

图5 原图

图6 Prewitt串行算法运行结果图

图7 Prewitt并行算法运行结果图

4.3 性能分析

实验结果表明：随着图像分辨率的不断增大，GPU的加速效果十分明显。例如，在GPU上运行Prewitt并行算法对分辨率为4 800×3 600的图像进行边缘检测，加速比达到了30倍。

5 结 语

提出了一种基于OpenCL的 Prewitt图像边缘检测的算法，借助GPU 高效的运算能力，在显存中对图像进行了并行化的边缘检测，获得了较清晰的处理图像。通过实验可以看出，采用OpenCL异构框架实现Prewitt并行算法，有较好的通用性和可移植性，可以大大提高算法的执行效率，对其他通用并行算法的实现有一定借鉴作用。

参考文献

[1] 杨道普，马秋禾，石磊.边缘检测Prewitt算子的改进算法[J].测绘科学，2008，33（z3）：100?103.

[2] 肖汉，郭运宏，周清雷.面向CPU_GPU异构计算的SIFT特征匹配并行算法[J].同济大学学报：自然科学版，2013，41（11）：1732?1737.

[3] GASTER B R， LEE H， KAELI D R， et al. OpenCL异构计算[M].张云泉，张先轶，龙国平，等译.北京：清华大学出版社，2012.

[4] 刘蕊.数字图像中边缘检测算法的研究[D].镇江：江苏科技大学，2009.

[5] 迈克老狼.AMD 大学教程中文版[EB/OL]. [2013-01-03].http：//www.opengpu.org.

[6] AMD上海研发中心.跨平台的多核与众核编程讲义：OpenCL的方式[M].上海：AMD上海研发中心，2010.

[7] 肖汉，周清雷，张祖勋.基于多GPU的Harris角点检测并行算法[J].武汉大学学报：信息科学版，2012，37（7）：876?880.

Step4：设置内核参数。

Step5：执行内核程序。调用设备端kernel函数，将处理过程交由设备。

Ste：6：验证结果。

Step7：将控制权交回主机端，把计算结果从显存复制到主机内存中。

Step8：释放系统所占资源，并由主机端将经过处理的图像结果显示输出。

Step9：输出状态和运行时间。

3.2 设备端程序

使用设备GPU时，Prewitt并行算法的图像卷积运算需要调用kernel程序实现。设备GPU根据主机端调用kernel函数时指定的参数形成块（Block）数workgroup以及每个块内线程（Threads）数workitem，线程数为256。

4 实验结果与分析

4.1 实验运行平台

硬件平台： CPU采用Intel（R） Xeon（R） CPU E5620@2.40 GHz，4核、8线程。系统内存为12.0 GB DDR3。 显卡采用AMD Radeon HD 6970，GPU为Cayman，显存为2 GB GDDR5。

软件平台：操作系统为64位Windows 7专业版。程序开发环境为Visual Stadio 2010，以及AMD?APP?SDK 2.8。

4.2 实验步骤与记录数据

预先处理好六幅不同分辨率大小的bmp灰度图像，使用它们进行Prewitt边缘检测算法对比实验，分别运行CPU上的串行算法和OpenCL异构框架上的并行算法，并记录处理时间，结果如表1所示。

表1 不同分辨率图像处理时间对比

图5为1 920×1 200分辨率的原始图像，图6和图7分别为对原图进行串行和并行 Prewitt图像边缘检测算法的运行结果。

图5 原图

图6 Prewitt串行算法运行结果图

图7 Prewitt并行算法运行结果图

4.3 性能分析

实验结果表明：随着图像分辨率的不断增大，GPU的加速效果十分明显。例如，在GPU上运行Prewitt并行算法对分辨率为4 800×3 600的图像进行边缘检测，加速比达到了30倍。

5 结 语

提出了一种基于OpenCL的 Prewitt图像边缘检测的算法，借助GPU 高效的运算能力，在显存中对图像进行了并行化的边缘检测，获得了较清晰的处理图像。通过实验可以看出，采用OpenCL异构框架实现Prewitt并行算法，有较好的通用性和可移植性，可以大大提高算法的执行效率，对其他通用并行算法的实现有一定借鉴作用。

参考文献

[1] 杨道普，马秋禾，石磊.边缘检测Prewitt算子的改进算法[J].测绘科学，2008，33（z3）：100?103.

[2] 肖汉，郭运宏，周清雷.面向CPU_GPU异构计算的SIFT特征匹配并行算法[J].同济大学学报：自然科学版，2013，41（11）：1732?1737.

[3] GASTER B R， LEE H， KAELI D R， et al. OpenCL异构计算[M].张云泉，张先轶，龙国平，等译.北京：清华大学出版社，2012.

[4] 刘蕊.数字图像中边缘检测算法的研究[D].镇江：江苏科技大学，2009.

[5] 迈克老狼.AMD 大学教程中文版[EB/OL]. [2013-01-03].http：//www.opengpu.org.

[6] AMD上海研发中心.跨平台的多核与众核编程讲义：OpenCL的方式[M].上海：AMD上海研发中心，2010.

[7] 肖汉，周清雷，张祖勋.基于多GPU的Harris角点检测并行算法[J].武汉大学学报：信息科学版，2012，37（7）：876?880.