馬歌+肖漢

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

關鍵詞： 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為核心的傳統計算資源進行處理，計算量大、能耗高、效率低，不能很好地滿足高分辨率圖像的快速處理。

隨著可編程圖形處理器技術的快速發(fā)展，當前的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串行算法實現簡單，但是，由于需要做大量的卷積運算，當圖像分辨率較高時，計算量很大，耗時較長，難以滿足大規(guī)模數據處理的要求。

2 OpenCL簡介

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

2.1 平臺模型

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

圖3 OpenCL的平臺模型

2.2 執(zhí)行模型

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

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

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

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

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

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

2.4 編程模型

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

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

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

3 Prewitt算法的并行實現

3.1 主機端程序

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

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

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

Step4：設置內核參數。

Step5：執(zhí)行內核程序。調用設備端kernel函數，將處理過程交由設備。

Ste：6：驗證結果。

Step7：將控制權交回主機端，把計算結果從顯存復制到主機內存中。

Step8：釋放系統所占資源，并由主機端將經過處理的圖像結果顯示輸出。

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

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專業(yè)版。程序開發(fā)環(huán)境為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并行算法，有較好的通用性和可移植性，可以大大提高算法的執(zhí)行效率，對其他通用并行算法的實現有一定借鑒作用。

參考文獻

[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].鎮(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：設置內核參數。

Step5：執(zhí)行內核程序。調用設備端kernel函數，將處理過程交由設備。

Ste：6：驗證結果。

Step7：將控制權交回主機端，把計算結果從顯存復制到主機內存中。

Step8：釋放系統所占資源，并由主機端將經過處理的圖像結果顯示輸出。

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

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專業(yè)版。程序開發(fā)環(huán)境為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并行算法，有較好的通用性和可移植性，可以大大提高算法的執(zhí)行效率，對其他通用并行算法的實現有一定借鑒作用。

參考文獻

[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].鎮(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：設置內核參數。

Step5：執(zhí)行內核程序。調用設備端kernel函數，將處理過程交由設備。

Ste：6：驗證結果。

Step7：將控制權交回主機端，把計算結果從顯存復制到主機內存中。

Step8：釋放系統所占資源，并由主機端將經過處理的圖像結果顯示輸出。

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

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專業(yè)版。程序開發(fā)環(huán)境為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并行算法，有較好的通用性和可移植性，可以大大提高算法的執(zhí)行效率，對其他通用并行算法的實現有一定借鑒作用。

參考文獻

[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].鎮(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.