張 帆，韓樹奎，張立國，王文勝,2

(1.中國科學院 長春光學精密機械與物理研究所，吉林 長春 130033;2.中國科學院大學，北京 100049；3.東北電力設計研究院，吉林 長春 130021)

Canny算法的GPU并行加速

張 帆1,2*，韓樹奎3，張立國1，王文勝1,2

(1.中國科學院 長春光學精密機械與物理研究所，吉林 長春 130033;2.中國科學院大學，北京 100049；3.東北電力設計研究院，吉林 長春 130021)

Canny算法在PC機上的執(zhí)行速度較慢，這極大地限制了其實用性。本文在前人的研究基礎上對算法進行更深的優(yōu)化和改進。首先在VS2012開發(fā)環(huán)境下利用數(shù)字圖像處理技術對原算法進行原理上的改進，再利用GPU流處理器數(shù)量眾多的優(yōu)勢以及強大的多線程并發(fā)執(zhí)行能力對Canny算法進行并行加速。在500 pixel×500 pixel的圖片上，對本文算法和原Canny算法進行了實驗驗證。實驗結果表明，在4 096 pixel×4 096 pixel大小的圖片上采用本文的GPU移植算法處理后，執(zhí)行速度從80 ms降到了6 ms以內(nèi)。在不影響邊緣檢測效果的前提下極大地提高了算法的實用性。

邊緣檢測；GPU；并行處理；連通域提取

1 引 言

邊緣檢測是圖像處理領域的一種很重要算法，其能從原始圖像中分離出目標的邊緣信息，去除冗余信息。邊緣檢測效果比較好的算法為Canny算法。自1986年John Canny提出該算法以來，其高效性得到學者們的廣泛認可[1]。該算法在總結前人算法的基礎上，提出了新的邊緣檢測原則：(1)能正確標識出圖像的邊緣；(2)標出的邊緣要和圖像的真實邊緣盡可能接近；(3)圖像中的邊緣在結果圖中只被標識出一次，因此，可有效去除虛假邊緣信息。為了達到上述效果，Canny算法采取了高斯濾波、非極大值抑制、邊緣連接等方法進行處理。檢測高效性是其重要優(yōu)點，但是由于算法復雜導致其執(zhí)行速度緩慢，從而極大制約了其實用性。已有的C版本，OpenCV庫函數(shù)版本的執(zhí)行效率都比較低，不能用于快速場景檢測以及工程項目開發(fā)中。

近年來，隨著高性能計算設備的發(fā)展，以及MPI、OpenGL等一系列并行加速工具的出現(xiàn)使得算法的執(zhí)行速度有了很大提高。特別是近年來GPU顯卡編程為并行計算提供了新的途徑。GPU編程以高速的執(zhí)行速度、良好的可編程性、較高的功耗比成為了并行編程的一個熱門工具[2]。目前，對于GPU版本的Canny算法，國內(nèi)外許多文獻的關注點不一樣。文獻[3]直接將原算法移植到了GPU上，使其執(zhí)行效率受到很大的制約，有很大的提高空間；文獻[4]利用FPGA系統(tǒng)對算法進行改進，而這種改進僅是將高斯濾波改成了中值濾波進行去噪。這種改進在某些程度上有可能降低算法的執(zhí)行速率。文獻[5]將改進重點放在了最后的邊緣搜索部分，改進了搜索算法策略，但是單一的優(yōu)化搜索策略對于算法性能的整體提升并不明顯。

本文利用GPU加速工具對Canny算法的各個執(zhí)行步驟都進行優(yōu)化。其中，主要優(yōu)化了高斯去噪求邊緣步驟和邊緣搜索鏈接步驟。利用GPU的大流量處理器和多線程并發(fā)執(zhí)行的特點，對一幅4 096×4 096圖像進行邊緣檢測，將邊緣算法的執(zhí)行時間壓縮到6 ms以內(nèi)。

2 算法介紹和分析

John Canny在前人的邊緣檢測標準上又加了一條判別依據(jù)，即圖像中的邊緣在結果圖中應該只被標識一次，以去除虛假邊緣信息。改進后的算法流程如下。

(1)高斯濾波：在檢測之前，采用高斯濾波去噪以去除圖像采集時的隨機噪聲；隨后再分別對x和y方向做差分，求邊緣信息。高斯卷積公式如式(1)所示，*表示卷積。

由公式得出的離散化差分模板如式(2)所示。

利用式(2)的模板對圖像逐像素卷積。

在實際圖像處理中，高斯濾波經(jīng)常采用的離散化卷積模板大小為3×3或5×5，方差根據(jù)實際圖像的噪聲分布選取，由此可計算出模板中每個位置的值。

高斯濾波是一種線性平滑濾波，主要用于消除高斯噪聲。在遙感圖像數(shù)據(jù)采集過程中，空間相機的圖像采集環(huán)境比較穩(wěn)定，圖像噪聲主要是電子元器件造成的高斯噪聲。因此可以采用高斯濾波進行初步的去噪處理。

(2)非極大值抑制：為了使標識的邊緣和圖像的真實邊緣盡可能接近，算法引入了非極大值抑制方法。在粗線條的邊緣信息中只保留梯度最大的邊緣，從而使檢測出的邊緣盡可能地靠近真實邊緣。非極大值抑制原理如圖1所示，在所測像素8鄰域內(nèi)尋找差分值最大的可能點，再通過線性插值尋找梯度方向[8]。

圖1 非極大值抑制示意圖Fig.1 Schematic diagram of non-maximum suppression

(3)雙閾值邊緣假設：Canny在前人的基礎上加入了雙閾值邊緣假設，算法設定了兩個差分閾值A、B(Agt;B)。邊緣差分值大于閾值A的一定是所求的邊緣，由此得出邊緣圖A，閾值介于A和B之間的是可能要的邊緣，由此得出邊緣圖B。最終在B圖結果中尋找連接到A圖的邊緣區(qū)域，從而得到最終的邊緣結果圖。雙閾值假設的原理如圖2(彩色見期刊電子版)所示，其中黃色是圖A中的邊緣區(qū)域，綠色是圖B中的邊緣區(qū)域。算法以3為起點不斷地在B圖中搜索連接區(qū)域，直到搜索完所有點為止。

圖2 雙閾值假設搜索過程Fig.2 Searching process of dual threshold hypothesis

表1是對于一幅大小為4 096×4 096的8位灰度圖執(zhí)行Canny算法的耗時結果?；贠pencv2.4.8計算機視覺庫在I5-2400，3.1 GHz主頻，內(nèi)存為16 GB的PC機上進行算法實現(xiàn)。

從表1可以看出，在CPU的串行模式下，Canny算法耗時主要集中于第一步的高斯濾波求差分和最后一步的邊緣搜索連接。這主要因為高斯模板對圖像卷積計算在CPU單線程串行執(zhí)行模式下的速度非常緩慢。對于在連通域搜索部分，算法的搜索策略是搜索已被標記點8鄰域，判斷是否存在有效點，這種單個點標記的搜索方法也是單線程邏輯搜索，耗時較多。而算法中的非極大值抑制部分耗時較少，優(yōu)化起來相對簡單。

3 算法改進與加速優(yōu)化

依據(jù)以上分析，制約算法執(zhí)行速度的兩個主要原因是算法本身因素和串行執(zhí)行模式[10]。算法自身耗時主要集中在高斯卷積濾波和邊緣搜索和連接上。串行執(zhí)行模式主要是算法在PC機上基于CPU的單線程串行執(zhí)行。因此本文將從這兩個方面對Canny算法進行優(yōu)化加速。

3.1 算法優(yōu)化

3.1.1 優(yōu)化高斯濾波和差分

在圖像求邊緣差分算法中，基于Sobel算子的邊緣檢測方法既可以進行x和y方向的邊緣檢測，又可以對圖像中的噪聲起到一定的抑制作用[12]。因此本文考慮利用Sobel算子代替Canny算法中的高斯濾波和差分求邊緣兩步，以降低計算復雜度。Sobel算子邊緣檢測的離散化模板和其卷積計算公式如下：

由式(3)可以看出，Sobel算子模板為3×3，其中有效計算的非零元素個數(shù)為6，在代碼中單次循環(huán)的計算量為6；在原Canny算法流程中高斯濾波3×3模板的非零元素個數(shù)為9，差分的2×2模板的非零元素個數(shù)為4，因此在單個方向代碼中的單次循環(huán)計算量總量是13。由此可知，Sobel算子的計算復雜度是原Canny算法的1/2。對于x和y兩個方向的圖像求邊緣差分計算，可以通過GPU并行加速。圖像處理的GPU并行加速原理如圖3所示。其中，每個像素點的計算過程可以映射為一個線程再賦予到一個流處理器上進行處理。這樣可以利用GPU數(shù)量眾多的流處理器，實現(xiàn)大規(guī)模線程并行以壓縮時間。

圖3 GPU并行加速原理圖Fig.3 Schematic diagram of parallel acceleration by GPU

3.1.2 GPU加速非極大值抑制和雙閾值圖像分割

非極大值抑制和雙閾值分割都是屬于任務簡單計算密集型的操作。它們可以采用如圖3所示的GPU并行加速方法，將每個像素點的計算映射到一個線程，并賦予一個流處理器SP進行處理。在非極大值抑制中，為了簡化計算，不采用插值求8鄰域最大值，而直接采用8鄰域求最大值的方法。

3.1.3 優(yōu)化搜索和鏈接

本文將中間值邊緣的搜索改成連通域搜索，并且在搜索方式上采用3步進式搜索，這樣可以充分利用3×3卷積模板的信息。

原始Canny算法存在計算能力浪費的現(xiàn)象。每次進行連通區(qū)域掃描時都只是掃描了與邊緣點連接的部分，而對于可能的連通區(qū)域沒有執(zhí)行操作。算法中的邊緣搜索與求連通域的操作步驟相似，因此，可以先將可能存在的連通域求出來，再與真正的邊緣點相連接。這樣能夠充分減少邊緣搜索的時間。如圖4(a)所示，黃色是雙閾值分割后A圖中的連通區(qū)域，綠色是B圖中的連通區(qū)域。以1、2、3為邊緣搜索A圖中的連通域，再以4、5、6和7、8搜索出B圖中連通區(qū)域，因為B圖4點連接到A圖中的連通域，故將整個連通域判定為邊緣。

在搜索策略上依據(jù)改進的3步進式搜索原理，如圖4(b)所示。1點為起始搜索點傳統(tǒng)方法是以1點為中心判斷其8鄰域的有效點，如圖4(b)右圖。改進后以1點8鄰域中的有效點2為中心，判斷其8鄰域中除1點以外的有效點即3點，如圖4(b)左。3步進式的搜索方法，單次搜索可以標記兩個以上的點，效率較原算法中的8鄰域單個點標記有了大大提高。

圖4 搜索方法優(yōu)化示意圖 4(a)(左),4(b)(右)Fig.4 Schematic diagram of optimizing search and connection,4(a)(left)) and 4(b)(right)

3.2 雙GPU優(yōu)化

在Canny算法雙閾值假設的兩個閾值搜索連接過程中，圖像A和圖像B的連通域搜索連接過程是相互獨立的。針對這種相互獨立的分塊任務可以利用雙GPU進行加速，每個GPU分別負責一幅圖像的搜索連接過程，原理如圖5所示，即將兩幅圖像的邊緣搜索連接任務分別放到兩個GPU中進行。最終利用GPU的內(nèi)部等待完成指令synthreads，等兩幅圖像的搜索任務全部完成后，再進行有效區(qū)域邊緣的連接與合并，這樣可以隱藏計算用時較少的圖像的處理時間。

圖5 雙GPU優(yōu)化原理示意圖Fig.5 Schematic diagram of dual-GPU optimization

此外，Canny算法前面的從高斯濾波到非極大值抑制，也都可以利用雙GPU進行優(yōu)化加速。由于采用了兩個相同的GPU，則流處理器數(shù)量也將加倍，對于大規(guī)模的線程并行會帶來線性的加速收益。類似步驟可以利用開發(fā)平臺進行。

4 實驗結果和討論

本文采用PC平臺，Opencv2.4.8計算機視覺庫以及Nvidia 750Ti顯卡對本文算法進行了驗證。對于500 pixel×500 pixel大小的圖片，邊緣檢測結果如圖6所示,左圖為CPU的邊緣檢測結果，右圖為GPU的邊緣檢測結果。

圖6 不同算法的比較結果(左圖CPU,右圖GPU)Fig.6 Comparison of two results by CPU(left) and GPU(right)

可以看出，原始Canny算法和本文算法的差異很小，不影響目標的整體邊緣輪廓[11]。對于港口區(qū)域圖像，能夠看出圖中的海上船只輪廓已經(jīng)能夠很好地與陸地分割開。在GPU的檢測結果中(圖6(b))主要輪廓的邊緣信息雖然有斷點，但是能夠反映出目標物的主要信息。上述實驗說明本文算法的檢測結果是可靠的。

圖7 本文算法、OpenCV庫及GPU庫算法的結果比較Fig.7 Results comparison of proposed method,OpenCV-lib and GPU-lib methods

圖8 本文方法、文獻[7]和文獻[3]算法的結果比較Fig.8 Results comparison of proposed method,and methods from Ref.[7] and Ref.[3]

針對不同版本的Canny檢測算法的實驗結果見圖7。圖7是本文算法、OpenCV庫、GPU庫的實現(xiàn)檢測結果，縱坐標是執(zhí)行時間(單位：ms)，橫坐標是圖像尺寸(單位:pixel2)。圖8是本文算法、文獻[3]算法和文獻[7]用FPGA的執(zhí)行結果。從圖中可以看出，對于不同尺寸的圖像，本文算法的執(zhí)行速度較其他算法有明顯提高[13-14]。其中圖7是本文算法的GPU并行移植與原算法GPU并行化移植的結果對比。圖8為用GPU加速與其他硬件加速后的效果對比。

由圖7和圖8可以看出，在數(shù)據(jù)量較大的圖像中，GPU的加速效果比較明顯。表2是本文使用雙GPU對于Canny算法的執(zhí)行過程進行優(yōu)化后的結果，實驗采取4 096×4 096的大尺寸圖像。實驗數(shù)據(jù)表明，雙GPU加速會帶來線性的加速收益，這主要是因為更多的GPU芯片擁有更多的流處理器，可以同時并行處理更多的像素。因此，在實際工作以及硬件開發(fā)中，可以選擇更多的GPU處理芯片群組進行更高效率的程序開發(fā)。

表2 對于4 096×4 096大小的圖片雙GPU優(yōu)化本文改進算法執(zhí)行時間Tab.2 Execution time by proposed method based on dual-GPU optimization on image with size of 4 096×4 096 (ms)

從上面的實驗結果可以看出，GPU對于模板卷積這種任務簡單，計算密集的操作可實現(xiàn)非常好的加速壓縮，而對于邊緣搜索連接這種任務復雜的操作加速效果不是很好。

前三步操作的速度隨著GPU處理器能力的提高以及流處理器數(shù)量的增多而加速，當顯卡從750Ti換成980以后，前面三步的計算速度有了很大的提高，說明前三步操作受流處理器數(shù)量的影響較大。而后半部分速度提升較小，主要因為其受限于算法本身。處理器換成雙GPU以后，處理4 096×4 096大小的圖像的執(zhí)行時間從19 ms壓縮到5.9 ms，速度提升了3.3倍。

在遵從于原算法的GPU并行化移植后，Canny邊緣檢測算法相對于C語言版本的算法效率提高數(shù)十倍，經(jīng)過本文的算法改進后，算法效率又提高3～5倍。

5 結 論

本文從算法本身和執(zhí)行模式兩方面對Canny算法進行了優(yōu)化和加速。

(1)通過對原算法各個執(zhí)行步驟進行分析和優(yōu)化，在不影響邊緣檢測效果的前提下，減少了Canny算法的計算復雜度，充分提高了算法的執(zhí)行速度。

(2)利用GPU的多線程并行執(zhí)行能力，對圖像處理進行了串行轉(zhuǎn)并行的移植。將4 096×4 096大小的圖像的邊緣檢測時間從80 ms壓縮到了6 ms以內(nèi)。執(zhí)行速度相比C版本以及FPGA和相關參考文獻都有較大提升，大大提高了算法的實用性。

此外，GPU在提供相同計算能力的基礎上，功耗比硬件平臺要小很多。此外，GPU能夠進行嵌入式硬件開發(fā)，有望將算法的執(zhí)行速率進一步提高。

[1] CANNY J.A computational approach to edge detection[J].IEEETransactionsonPatternAnalysisandMachineIntelligence,1986,6:679-698.

[2] 丁鵬,張葉,劉讓,等.結合形態(tài)學和Canny算法的紅外弱小目標檢測[J].液晶與顯示,2016,31(8):793-800.

DING P,ZHANG Y,LIU R,etal..Infrared small target detection based on adaptive Canny algorithm and morphology[J].ChineseJournalofLiquidCrystalsandDisplays,2016,31(8):793-800.(in Chinese)

[3] 朱玉娥,吳曉紅,何小海.基于GPU圖像邊緣檢測的實時性[J].電子測量技術,2009,32(2):140-142.

ZHU Y E,WU X H,HE X H.Real-time edge detection based on GPU[J].ElectronicMeasurementTechnology,2009,32(2):140-142.(in Chinese)

[4] 唐斌,龍文.基于GPU+CPU的CANNY算子快速實現(xiàn)[J].液晶與顯示,2016,31(7):714-720.

TANG B,LONG W.Fast Canny algorithm based on GPU+CPU[J].ChineseJournalofLiquidCrystalsandDisplays,2016,31(7):714-720.(in Chinese)

[5] 李大禹.基于多GPU的液晶自適應光學波前處理器[J].液晶與顯示,2016,31(5):491-496.

LI D Y.Liquid crystal adaptive optics wavefront processor based on multi-GPU[J].ChineseJournalofLiquidCrystalsandDisplays,2016,31(5):491-496.(in Chinese)

[6] 張宏薇,王仕洋,李憲龍,等.基于Hough變換的瞳孔識別方法研究與實現(xiàn)[J].液晶與顯示,2016,31(6):621-625.ZHANG H W,WANG SH Y,LI X L,etal..Research and implementation of pupil recognition based on Hough transform[J].ChineseJournalofLiquidCrystalsandDisplays,2016,31(6):621-625.(in Chinese)

[7] 張素文,陳志星,蘇義鑫.Canny邊緣檢測算法的改進及 FPGA 實現(xiàn)[J].紅外技術,2010,32(2):93-96.

ZHANG S W,CHEN ZH X,SU Y X.Improved Canny edge detection algorithm and implementation in FPGA[J].InfraredTechnology,2010,32(2):93-96.(in Chinese)

[8] Canny edge detection algorithm principle and its VC implement[EB/OL].http://blog.csdn.net/augusdi/article/details/12907151.

[9] 周海芳.遙感圖像并行處理算法的研究與應用[D].長沙:國防科學技術大學,2003.

ZHOU H F.Researchandapplicationofparallelaccelerationinremotesensingimage[D].Changsha:National University of Defense Technology,2003.(in Chinese)

[10] 徐亮,魏銳.基于Canny算子的圖像邊緣檢測優(yōu)化算法[J].科技通報,2013,29(7):127-131.

XU L,WEI R.An optimal algorithm of image edge detection based on Canny[J].BulletinofScienceandTechnology,2013,29(7):127-131.(in Chinese)

[11] 曾文靜,萬磊,張鐵棟,等.復雜?？毡尘跋氯跣∧繕说目焖僮詣訖z測[J].光學 精密工程,2012,20(2):403-412.

ZENG W J,WAN L,ZHANG T D,etal..Fast detection of weak targets in complex sea-sky background[J].Opt.PrecisionEng.,2012,20(2):403-412.(in Chinese)

[12] 陳娟,陳乾輝,師路歡,等.圖像跟蹤中的邊緣檢測技術[J].中國光學,2009,2(1):46-53.

CHEN J,CHEN Q H,SHI L H,etal..Edge detection technology in imaging tracking[J].ChineseOptics,2009,2(1):46-53.(in Chinese)

[13] XU Q,VARADARAJAN S,CHAKRABARTI C,etal.A distributed canny edge detector:algorithm and FPGA implementation[J].IEEETransactionsonImageProcessing,2014,23(7):2944-2960.

[14] 周克良,周利鋒,劉太鋼,等.基于改進的Canny算子實時視頻邊緣檢測系統(tǒng)在FPGA上的設計與實現(xiàn)[J].計算機測量與控制,2016,24(1):219-222.

ZHOU K L,ZHOU L F,LIU T G,etal..Design and implementation of real-time video edge detection system based on improvement of canny algorithm on FPGA[J].ComputerMeasurementamp;Control,2016,24(1):219-222.(in Chinese)

[15] 王希遠,成榮,朱煜,等.基于FPGA的BiSS-C協(xié)議編碼器接口技術研究及解碼實現(xiàn)[J].液晶與顯示,2016,31(4):386-391.

WANG X Y,CHENG R,ZHU Y,etal..Research and realization of BiSS-C protocol encoder interface based on FPGA[J].ChineseJournalofLiquidCrystalsandDisplays,2016,31(4):386-391.(in Chinese)

張 帆(1992—)，男，河南周口人，碩士研究生，主要從事數(shù)字圖像處理、GPU并行加速、機器視覺等方面的研究。E-mail:zhangfan_6284@126.com

張立國(1961—)，男，吉林長春人，研究員，主要從事空間光學方面的研究。E-mail:zhangliguo@ciomp.ac.cn

ParallelaccelerationofCannyalgorithmbasedonGPU

ZHANG Fan1,2,HAN Shu-kui3,ZHANG Li-guo1*,WANG Wen-sheng1,2

(1.ChangchunInstituteofOptics,FineMechanicsandPhysic,ChineseAcademyofSciences,Changchun130033,China; 2.UniversityofChineseAcademyofScience,Beijing100049,China；3.NortheastElectricalPowerDesignInstitute,Changchun130021,China)

*Correspondingauthor，E-mail:zhangliguo@ciomp.ac.cn

Due to the slow execution speed of Canny algorithm in PC,the practicality of this algorithm is greatly restricted.Based on the previous studies,we further optimizes and improves the algorithm.First of all,we use the digital image processing technology to improve the original algorithm under the development environment of VS2012,and then accelerate the Canny algorithm by taking advantage of the large number of GPU stream processors and powerful multithreaded concurrent execution capability.Experiments were made on the improved algorithm and the original Canny algorithm.Experimental results show that in the 4 096×4 096 pixel-size images,the GPU migration algorithm presented in this paper can reduce the execution speed from 80 ms to less than 6 ms.Through this improvement,it can greatly improve the practicability of the algorithm without affecting the edge detection effect.

edge detection;GPU;parallel processing;connected component extraction

2017-09-11；

2017-11-13

國家高技術研究發(fā)展計劃(863計劃)資助項目(No.863-2-5-1-13B)

Supported by National High-tech Ramp;D Program of China(No.863-2-5-1-13B)

2095-1531(2017)06-0737-07

TP751.1

A

10.3788/CO.20171006.0737