基于OpenCL的Prewitt算法的并行實現(xiàn)

馬歌+肖漢

摘 要： Prewitt算法是數(shù)字圖像分割中最常用的邊緣檢測算法。采用傳統(tǒng)CPU上的串行方法實現(xiàn)該算法需要較大的計算量、耗時較長，因此，通過GPU對其進行性能加速有著重要的意義。然而由于GPU硬件體系結(jié)構(gòu)的差異性，跨平臺移植是一件非常困難的工作。針對上述問題，提出了一種基于OpenCL異構(gòu)框架的Prewitt圖像邊緣檢測并行算法。實驗結(jié)果表明，該并行算法比CPU上的串行算法運行速度快，加速比可達30倍，有效地提高了大規(guī)模數(shù)據(jù)處理的效率，可移植性好，具有較高的應用價值。

關(guān)鍵詞： OpenCL； 異構(gòu)框架； 邊緣檢測； Prewitt算法； 并行實現(xiàn)

中圖分類號： 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 引 言

邊緣檢測技術(shù)是圖像處理和計算機視覺等領(lǐng)域最基本的技術(shù)[1]。當前，圖像邊緣檢測技術(shù)主要利用以CPU為核心的傳統(tǒng)計算資源進行處理，計算量大、能耗高、效率低，不能很好地滿足高分辨率圖像的快速處理。

隨著可編程圖形處理器技術(shù)的快速發(fā)展，當前的GPU已經(jīng)具有很強的并行計算能力，越來越多的算法被成功移植到GPU平臺上，并取得了很好的加速效果。然而由于GPU硬件體系結(jié)構(gòu)的差異性，在不同GPU硬件平臺間實現(xiàn)算法移植是一件非常困難的工作。目前國內(nèi)外已有的研究工作一般只針對單一的硬件平臺，沒有考慮不同硬件平臺間的可移植性。

近幾年來，由多核CPU、GPU或其他類型的處理器組成的異構(gòu)框架作為一種新的計算機體系架構(gòu)逐漸成為主流。其中，開放式計算語言（Open Computing Language，OpenCL）作為面向異構(gòu)計算平臺的通用編程框架[2]，一方面在實現(xiàn)性能目標的同時降低了能耗，另一方面為實現(xiàn)GPU通用計算程序的跨平臺移植提供了解決方案。為此，本文提出了一種基于OpenCL異構(gòu)框架的Prewitt并行算法。

1 Prewitt算法原理

圖像的邊緣是圖像的重要特征之一。常用邊緣檢測算法包括Roberts算法、Prewitt算法、Sobel算法、Canny算法和Laplace算法。

Prewitt算法作為一階微分算子的邊緣檢測算法[3]，利用像素點上下、左右相鄰點的灰度差，在邊緣處達到極值檢測邊緣，去掉部分偽邊緣，對噪聲具有平滑作用。其原理是在圖像空間利用圖1所示的水平、垂直兩個方向的3×3模板與圖2所示的圖像像素3×3鄰域進行卷積運算來完成。一個模板通常的垂直邊緣響應最大，而另一個對水平邊緣響應最大。

圖1 水平模板和垂直模板

圖2 f（i，j）的3×3像素鄰域

圖1中：水平模板用于檢測水平邊緣，垂直模板用于檢測垂直邊緣。在處理時，圖像中每個點都用這兩個模板進行卷積，兩個卷積的最大值作為該點的輸出位。運算結(jié)果是一幅邊緣幅度圖像。圖內(nèi)模板的數(shù)字是模板系數(shù)，中間的點表示中心元素。

對于像素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領(lǐng)域與水平方向模板的卷積；[Gy]為像素點f（i，j）的3×3領(lǐng)域與垂直方向模板的卷積。求出梯度G后，設定一個常數(shù)n（n≤255），當G>n時，標出該點為邊界點，其像素值設定為255（白點），否則設定為G。實驗表明，CPU上的Prewitt串行算法實現(xiàn)簡單，但是，由于需要做大量的卷積運算，當圖像分辨率較高時，計算量很大，耗時較長，難以滿足大規(guī)模數(shù)據(jù)處理的要求。

2 OpenCL簡介

OpenCL提供了統(tǒng)一的面向異構(gòu)系統(tǒng)的并行編程環(huán)境。OpenCL架構(gòu)包括四部分：

2.1 平臺模型

OpenCL平臺模型由一個主機（Host）連接一個或多個能執(zhí)行OpenCL的設備（Device）構(gòu)成。在AMD的OpenCL平臺中，主機一般指x86 CPU[4]。所有由OpenCL編寫的應用程序都是從主機啟動并在主機上結(jié)束的，主機管理著整個平臺上的所有計算資源。每個OpenCL設備包括一個或多個計算單元（CU），每個計算單元又包括一個或多個處理單元（PE）。應用程序會從主機端向各個OpenCL設備的處理單元發(fā)送計算命令。該模型主要用來編寫能夠在設備上執(zhí)行的OpenCL的kernel函數(shù)。如圖3所示。

圖3 OpenCL的平臺模型

2.2 執(zhí)行模型

OpenCL的執(zhí)行模型包括在主機上執(zhí)行的主程序（Host Program）和在OpenCL設備上執(zhí)行的內(nèi)核程序（kernel）[5]。OpenCL執(zhí)行模型主要管理kernel在OpenCL設備上的運行。

在主機將內(nèi)核程序交到設備上執(zhí)行時，系統(tǒng)便會創(chuàng)建一個N維（可以是一維，二維或者三維）的工作空間（NDRange）。工作空間被劃分為多個工作組（work group，也就是塊）。每個工作組又包含多個節(jié)點（workitem，也就是線程）。所有工作節(jié)點都將執(zhí)行相同的內(nèi)核程序。用全局ID（global ID）表示每個工作節(jié)點在相應維度上的索引，用局部ID（local ID） 表示工作組內(nèi)部的節(jié)點相對該工作組的位置索引。通過一個global ID和一個work group 內(nèi)的local ID，就能標定一個workitem。

如圖4是一個二維工作空間NDRang（Gx，Gy）的例子。工作空間的workitem數(shù)量為Gx乘以Gy，一個workgroup內(nèi)的workitem的數(shù)量為Sx乘以Sy。

2.3 內(nèi)存模型

OpenCL的內(nèi)存模型定義被kernel用到的抽象內(nèi)存層次，有四種內(nèi)存類型，包括全局內(nèi)存（Global Memory）、常數(shù)內(nèi)存（Constant Memory）、局部內(nèi)存（Local Memory）、私有內(nèi)存（Private Memory）。各種內(nèi)存之間的數(shù)據(jù)傳輸必須是顯式進行的。

圖4 二維索引空間

全局內(nèi)存：工作空間內(nèi)所有的工作節(jié)點都可以讀/寫的該內(nèi)存區(qū)域中一個內(nèi)存對象的任何元素。

常量內(nèi)存：工作空間內(nèi)所有的工作節(jié)點都可以只讀的內(nèi)存區(qū)域。這個內(nèi)存區(qū)域在內(nèi)核程序的執(zhí)行過程中保持不變。主機分配并初始化該內(nèi)存中的存儲對象。

局部內(nèi)存：局部從屬于一個工作組的內(nèi)存區(qū)域。這個內(nèi)存區(qū)域可以用來分配由該工作組中所有工作節(jié)點共享的變量。

私有內(nèi)存：是一個工作節(jié)點私有的內(nèi)存區(qū)域。一個工作節(jié)點在該內(nèi)存區(qū)域中定義的變量對其他工作節(jié)點不可見。

2.4 編程模型

OpenCL的編程模型分為：數(shù)據(jù)并行編程模型、任務并行編程模型和混合編程模型。數(shù)據(jù)并行編程模型是在編寫OpenCL并行程序時采用的首要模型。

數(shù)據(jù)并行編程模型用一系列操作一個存儲對象的多個元素的指令的形式定義了計算。OpenCL實現(xiàn)的是一種松散的數(shù)據(jù)并行編程模型，它不需要workitem和內(nèi)存對象元素之間嚴格的一對一的映射。workgroup可以顯示指定，也可以隱式指定。

任務并行編程模型使內(nèi)核程序的執(zhí)行獨立于線程索引空間。一個計算部件上只有一個workitem執(zhí)行內(nèi)核程序。

3 Prewitt算法的并行實現(xiàn)

3.1 主機端程序

Step1：先獲得OpenCL的平臺信息，在此平臺上選定OpenCL設備，如GPU。接著建立上下文環(huán)境，并建立命令隊列用來執(zhí)行內(nèi)核實例。

Step2：創(chuàng)建并編譯源程序，建立內(nèi)核實例。將內(nèi)核程序代碼保存在“Prewitt_Kernel.cl”文件中，讀到內(nèi)存并存儲為字符串數(shù)組形式。

Step3：首先分配主機內(nèi)存，將bmp灰度圖像數(shù)據(jù)讀入到主機內(nèi)存中。然后，在顯存中申請2塊與圖像數(shù)據(jù)相等容量的空間。一塊用于存放主機內(nèi)存中圖像數(shù)據(jù)拷貝，另一外用于存放圖像數(shù)據(jù)的處理的結(jié)果，將數(shù)據(jù)復制到顯存上。

Step4：設置內(nèi)核參數(shù)。

Step5：執(zhí)行內(nèi)核程序。調(diào)用設備端kernel函數(shù)，將處理過程交由設備。

Ste：6：驗證結(jié)果。

Step7：將控制權(quán)交回主機端，把計算結(jié)果從顯存復制到主機內(nèi)存中。

Step8：釋放系統(tǒng)所占資源，并由主機端將經(jīng)過處理的圖像結(jié)果顯示輸出。

Step9：輸出狀態(tài)和運行時間。

3.2 設備端程序

使用設備GPU時，Prewitt并行算法的圖像卷積運算需要調(diào)用kernel程序?qū)崿F(xiàn)。設備GPU根據(jù)主機端調(diào)用kernel函數(shù)時指定的參數(shù)形成塊（Block）數(shù)workgroup以及每個塊內(nèi)線程（Threads）數(shù)workitem，線程數(shù)為256。

4 實驗結(jié)果與分析

4.1 實驗運行平臺

硬件平臺： CPU采用Intel（R） Xeon（R） CPU E5620@2.40 GHz，4核、8線程。系統(tǒng)內(nèi)存為12.0 GB DDR3。 顯卡采用AMD Radeon HD 6970，GPU為Cayman，顯存為2 GB GDDR5。

軟件平臺：操作系統(tǒng)為64位Windows 7專業(yè)版。程序開發(fā)環(huán)境為Visual Stadio 2010，以及AMD?APP?SDK 2.8。

4.2 實驗步驟與記錄數(shù)據(jù)

預先處理好六幅不同分辨率大小的bmp灰度圖像，使用它們進行Prewitt邊緣檢測算法對比實驗，分別運行CPU上的串行算法和OpenCL異構(gòu)框架上的并行算法，并記錄處理時間，結(jié)果如表1所示。

表1 不同分辨率圖像處理時間對比

圖5為1 920×1 200分辨率的原始圖像，圖6和圖7分別為對原圖進行串行和并行 Prewitt圖像邊緣檢測算法的運行結(jié)果。

圖5 原圖

圖6 Prewitt串行算法運行結(jié)果圖

圖7 Prewitt并行算法運行結(jié)果圖

4.3 性能分析

實驗結(jié)果表明：隨著圖像分辨率的不斷增大，GPU的加速效果十分明顯。例如，在GPU上運行Prewitt并行算法對分辨率為4 800×3 600的圖像進行邊緣檢測，加速比達到了30倍。

5 結(jié) 語

提出了一種基于OpenCL的 Prewitt圖像邊緣檢測的算法，借助GPU 高效的運算能力，在顯存中對圖像進行了并行化的邊緣檢測，獲得了較清晰的處理圖像。通過實驗可以看出，采用OpenCL異構(gòu)框架實現(xiàn)Prewitt并行算法，有較好的通用性和可移植性，可以大大提高算法的執(zhí)行效率，對其他通用并行算法的實現(xiàn)有一定借鑒作用。

參考文獻

[1] 楊道普，馬秋禾，石磊.邊緣檢測Prewitt算子的改進算法[J].測繪科學，2008，33（z3）：100?103.

[2] 肖漢，郭運宏，周清雷.面向CPU_GPU異構(gòu)計算的SIFT特征匹配并行算法[J].同濟大學學報：自然科學版，2013，41（11）：1732?1737.

[3] GASTER B R， LEE H， KAELI D R， et al. OpenCL異構(gòu)計算[M].張云泉，張先軼，龍國平，等譯.北京：清華大學出版社，2012.

[4] 劉蕊.數(shù)字圖像中邊緣檢測算法的研究[D].鎮(zhèn)江：江蘇科技大學，2009.

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

[6] AMD上海研發(fā)中心.跨平臺的多核與眾核編程講義：OpenCL的方式[M].上海：AMD上海研發(fā)中心，2010.

[7] 肖漢，周清雷，張祖勛.基于多GPU的Harris角點檢測并行算法[J].武漢大學學報：信息科學版，2012，37（7）：876?880.

Step4：設置內(nèi)核參數(shù)。

Step5：執(zhí)行內(nèi)核程序。調(diào)用設備端kernel函數(shù)，將處理過程交由設備。

Ste：6：驗證結(jié)果。

Step7：將控制權(quán)交回主機端，把計算結(jié)果從顯存復制到主機內(nèi)存中。

Step8：釋放系統(tǒng)所占資源，并由主機端將經(jīng)過處理的圖像結(jié)果顯示輸出。

Step9：輸出狀態(tài)和運行時間。

3.2 設備端程序

使用設備GPU時，Prewitt并行算法的圖像卷積運算需要調(diào)用kernel程序?qū)崿F(xiàn)。設備GPU根據(jù)主機端調(diào)用kernel函數(shù)時指定的參數(shù)形成塊（Block）數(shù)workgroup以及每個塊內(nèi)線程（Threads）數(shù)workitem，線程數(shù)為256。

4 實驗結(jié)果與分析

4.1 實驗運行平臺

硬件平臺： CPU采用Intel（R） Xeon（R） CPU E5620@2.40 GHz，4核、8線程。系統(tǒng)內(nèi)存為12.0 GB DDR3。 顯卡采用AMD Radeon HD 6970，GPU為Cayman，顯存為2 GB GDDR5。

軟件平臺：操作系統(tǒng)為64位Windows 7專業(yè)版。程序開發(fā)環(huán)境為Visual Stadio 2010，以及AMD?APP?SDK 2.8。

4.2 實驗步驟與記錄數(shù)據(jù)

預先處理好六幅不同分辨率大小的bmp灰度圖像，使用它們進行Prewitt邊緣檢測算法對比實驗，分別運行CPU上的串行算法和OpenCL異構(gòu)框架上的并行算法，并記錄處理時間，結(jié)果如表1所示。

表1 不同分辨率圖像處理時間對比

圖5為1 920×1 200分辨率的原始圖像，圖6和圖7分別為對原圖進行串行和并行 Prewitt圖像邊緣檢測算法的運行結(jié)果。

圖5 原圖

圖6 Prewitt串行算法運行結(jié)果圖

圖7 Prewitt并行算法運行結(jié)果圖

4.3 性能分析

實驗結(jié)果表明：隨著圖像分辨率的不斷增大，GPU的加速效果十分明顯。例如，在GPU上運行Prewitt并行算法對分辨率為4 800×3 600的圖像進行邊緣檢測，加速比達到了30倍。

5 結(jié) 語

提出了一種基于OpenCL的 Prewitt圖像邊緣檢測的算法，借助GPU 高效的運算能力，在顯存中對圖像進行了并行化的邊緣檢測，獲得了較清晰的處理圖像。通過實驗可以看出，采用OpenCL異構(gòu)框架實現(xiàn)Prewitt并行算法，有較好的通用性和可移植性，可以大大提高算法的執(zhí)行效率，對其他通用并行算法的實現(xiàn)有一定借鑒作用。

參考文獻

[1] 楊道普，馬秋禾，石磊.邊緣檢測Prewitt算子的改進算法[J].測繪科學，2008，33（z3）：100?103.

[2] 肖漢，郭運宏，周清雷.面向CPU_GPU異構(gòu)計算的SIFT特征匹配并行算法[J].同濟大學學報：自然科學版，2013，41（11）：1732?1737.

[3] GASTER B R， LEE H， KAELI D R， et al. OpenCL異構(gòu)計算[M].張云泉，張先軼，龍國平，等譯.北京：清華大學出版社，2012.

[4] 劉蕊.數(shù)字圖像中邊緣檢測算法的研究[D].鎮(zhèn)江：江蘇科技大學，2009.

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

[6] AMD上海研發(fā)中心.跨平臺的多核與眾核編程講義：OpenCL的方式[M].上海：AMD上海研發(fā)中心，2010.

[7] 肖漢，周清雷，張祖勛.基于多GPU的Harris角點檢測并行算法[J].武漢大學學報：信息科學版，2012，37（7）：876?880.

Step4：設置內(nèi)核參數(shù)。

Step5：執(zhí)行內(nèi)核程序。調(diào)用設備端kernel函數(shù)，將處理過程交由設備。

Ste：6：驗證結(jié)果。

Step7：將控制權(quán)交回主機端，把計算結(jié)果從顯存復制到主機內(nèi)存中。

Step8：釋放系統(tǒng)所占資源，并由主機端將經(jīng)過處理的圖像結(jié)果顯示輸出。

Step9：輸出狀態(tài)和運行時間。

3.2 設備端程序

使用設備GPU時，Prewitt并行算法的圖像卷積運算需要調(diào)用kernel程序?qū)崿F(xiàn)。設備GPU根據(jù)主機端調(diào)用kernel函數(shù)時指定的參數(shù)形成塊（Block）數(shù)workgroup以及每個塊內(nèi)線程（Threads）數(shù)workitem，線程數(shù)為256。

4 實驗結(jié)果與分析

4.1 實驗運行平臺

硬件平臺： CPU采用Intel（R） Xeon（R） CPU E5620@2.40 GHz，4核、8線程。系統(tǒng)內(nèi)存為12.0 GB DDR3。 顯卡采用AMD Radeon HD 6970，GPU為Cayman，顯存為2 GB GDDR5。

軟件平臺：操作系統(tǒng)為64位Windows 7專業(yè)版。程序開發(fā)環(huán)境為Visual Stadio 2010，以及AMD?APP?SDK 2.8。

4.2 實驗步驟與記錄數(shù)據(jù)

預先處理好六幅不同分辨率大小的bmp灰度圖像，使用它們進行Prewitt邊緣檢測算法對比實驗，分別運行CPU上的串行算法和OpenCL異構(gòu)框架上的并行算法，并記錄處理時間，結(jié)果如表1所示。

表1 不同分辨率圖像處理時間對比

圖5為1 920×1 200分辨率的原始圖像，圖6和圖7分別為對原圖進行串行和并行 Prewitt圖像邊緣檢測算法的運行結(jié)果。

圖5 原圖

圖6 Prewitt串行算法運行結(jié)果圖

圖7 Prewitt并行算法運行結(jié)果圖

4.3 性能分析

實驗結(jié)果表明：隨著圖像分辨率的不斷增大，GPU的加速效果十分明顯。例如，在GPU上運行Prewitt并行算法對分辨率為4 800×3 600的圖像進行邊緣檢測，加速比達到了30倍。

5 結(jié) 語

提出了一種基于OpenCL的 Prewitt圖像邊緣檢測的算法，借助GPU 高效的運算能力，在顯存中對圖像進行了并行化的邊緣檢測，獲得了較清晰的處理圖像。通過實驗可以看出，采用OpenCL異構(gòu)框架實現(xiàn)Prewitt并行算法，有較好的通用性和可移植性，可以大大提高算法的執(zhí)行效率，對其他通用并行算法的實現(xiàn)有一定借鑒作用。

參考文獻

[1] 楊道普，馬秋禾，石磊.邊緣檢測Prewitt算子的改進算法[J].測繪科學，2008，33（z3）：100?103.

[2] 肖漢，郭運宏，周清雷.面向CPU_GPU異構(gòu)計算的SIFT特征匹配并行算法[J].同濟大學學報：自然科學版，2013，41（11）：1732?1737.

[3] GASTER B R， LEE H， KAELI D R， et al. OpenCL異構(gòu)計算[M].張云泉，張先軼，龍國平，等譯.北京：清華大學出版社，2012.

[4] 劉蕊.數(shù)字圖像中邊緣檢測算法的研究[D].鎮(zhèn)江：江蘇科技大學，2009.

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

[6] AMD上海研發(fā)中心.跨平臺的多核與眾核編程講義：OpenCL的方式[M].上海：AMD上海研發(fā)中心，2010.

[7] 肖漢，周清雷，張祖勛.基于多GPU的Harris角點檢測并行算法[J].武漢大學學報：信息科學版，2012，37（7）：876?880.