一種自適應(yīng)Canny邊緣檢測算法的并行設(shè)計(jì)與TBB實(shí)現(xiàn)*

孫陸鵬　肖漢

摘要：為了充分利用多核優(yōu)勢(shì)，提高運(yùn)算圖像處理速度，采用Intel線程構(gòu)建模塊對(duì)自適應(yīng)Canny邊緣檢測算法的并行處理進(jìn)行分析和設(shè)計(jì)，提出在自適應(yīng)尺度計(jì)算、高斯濾波、自適應(yīng)閾值計(jì)算、非最大抑制、邊緣連接各階段的并行解決方案，對(duì)不同分辨率圖像進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，該算法加速效果顯著，對(duì)提高圖像處理系統(tǒng)的運(yùn)行效率具有實(shí)際意義。

關(guān)鍵詞：Intel TBB 自適應(yīng)高斯平滑 Canny邊緣檢測 自適應(yīng)閾值

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2016）06-0000-00

1 引言

圖像的邊緣檢測是進(jìn)行圖像分析和理解的基礎(chǔ)，是目前機(jī)器視覺研究領(lǐng)域的熱點(diǎn)之一。傳統(tǒng)的邊緣檢測方法包括Roberts算子、Soble算子、Prewitt算子等一階微分算子，以及Laplacian算子、LoG算子等二階微分算子等[3]。Canny邊緣檢測算法對(duì)受白噪聲影響的階躍型邊緣進(jìn)行邊緣檢測是最優(yōu)的[4]，因此，Canny算法在邊緣檢測中的應(yīng)用最為廣泛。Canny算法進(jìn)行邊緣檢測，需要人為設(shè)定尺度和雙門限值，近年來，多位學(xué)者提出了自適應(yīng)確定尺度和雙閾值的方法[5-8]，同時(shí)反映自適應(yīng)Canny邊緣檢測方法運(yùn)算速度較慢，無法滿足實(shí)時(shí)性的需要[6-8]。本文嘗試?yán)枚嗪藘?yōu)勢(shì)，提高自適應(yīng)Canny邊緣檢測的速度。

目前，單核CPU的處理能力已達(dá)到極限狀態(tài)，而對(duì)計(jì)算能力的應(yīng)用需求卻越來越高，市場上多核處理器已成為主流，通過多核CPU進(jìn)行并行計(jì)算來提高計(jì)算性能已成為發(fā)展趨勢(shì)[1]。并行編程模型將逐漸取代傳統(tǒng)的串行編程模式。從應(yīng)用程序開發(fā)層面來看，目前流行的并行編程模型主要有兩類[2]：一類是共享存儲(chǔ)模型；例如OpenMP，它是對(duì)一種語言的擴(kuò)展，支持C語言和Fortran語言的并行擴(kuò)展，包括編譯指導(dǎo)語句、函數(shù)庫和環(huán)境變量。另一類是消息傳遞模型；例如MPI，它本身不是編程語言，而是具有并行語義的編程接口。TBB（Threading Building Blocks，線程構(gòu)建模塊）是Intel公司針對(duì)多核平臺(tái)開發(fā)的一組開源的C++的模板庫， 支持可伸縮的并行編程。TBB為多核環(huán)境下采用多線程并行程序設(shè)計(jì)提供了一種解決方案。

2自適應(yīng)Canny邊緣檢測算法簡介

Canny邊緣檢測算法是Canny在1983年提出的，它基于以下三個(gè)標(biāo)準(zhǔn)[9，10]：（1）檢測標(biāo)準(zhǔn)：不丟失重要的邊緣，不應(yīng)有虛假的邊緣；（2）定位標(biāo)準(zhǔn)：實(shí)際邊緣與檢測到的邊緣位置之間的偏差最小；（3）單響應(yīng)標(biāo)準(zhǔn)：將多個(gè)響應(yīng)降低為單個(gè)邊緣響應(yīng)。Canny邊緣檢測的一般過程如下[4]：

2）計(jì)算圖像中的每個(gè)像素的梯度和梯度方向；

3）非最大化抑制（non-maximum suppression），對(duì)每一個(gè)像素點(diǎn)，將其梯度與其梯度方向兩側(cè)的像素的梯度進(jìn)行比較，若其梯度不是最大的，則該像素不可能為邊緣，將其灰度值置為0，否則將其設(shè)置為候選邊緣點(diǎn)，其灰度用128表示。

4）使用雙門限方法對(duì)邊緣圖像作滯后閾值化處理，消除虛假響應(yīng)。設(shè)置高閾值τh和低閾值τl， τh>τl，梯度不小于τh的像素一定是邊緣點(diǎn)，與邊緣點(diǎn)相鄰并且梯度不小于τl的像素也設(shè)置為邊緣（灰度設(shè)置為255），其余像素設(shè)置為非邊緣（灰度置為0）。

傳統(tǒng)Canny邊緣檢測算法中，τh和τl一般由經(jīng)驗(yàn)得來。文獻(xiàn)[6]提出用兩次最大類間方差法的自適應(yīng)設(shè)定雙門限值τh和τl。最大類間方差法（又名大津法，Otsu方法）是一種閾值自動(dòng)選取的方法。其基本思想是選取一個(gè)最佳閾值使得該閾值分割得到的兩類間具有最好的分離性。對(duì)經(jīng)過非極大抑制后得到的所有候選邊緣點(diǎn)，統(tǒng)計(jì)其梯度信息得到邊緣梯度直方圖。在梯度直方圖上，依次將每個(gè)梯度值作為分類依據(jù)，計(jì)算該值左右兩類的類間方差，選取類間方差最大的梯度值作為最佳閾值。首先得到高閾值τh，然后在區(qū)間[0， τh）再次使用該方法，得到低閾值τl。

3 并行性分析與設(shè)計(jì)

多核并行Canny自適應(yīng)邊緣檢測方法的每一步都要用到前一步的計(jì)算結(jié)果，依賴性較強(qiáng)。分六個(gè)階段進(jìn)行，選擇TBB的模板進(jìn)行并行計(jì)算。

3.1計(jì)算各像素高斯濾波平滑系數(shù)

為了提高運(yùn)算速度，高斯濾波的高斯核事先計(jì)算出來，硬編碼在程序中，用一個(gè)二維double型數(shù)組存儲(chǔ)，每行對(duì)應(yīng)一個(gè)平滑系數(shù)σ。此階段本文運(yùn)用公式（1），并進(jìn)行歸一化處理，計(jì)算結(jié)果在區(qū)間[0，0.9]內(nèi)，各像素的σ值乘以10并取整存儲(chǔ)，為該像素濾波參數(shù)在數(shù)組中的索引。

3.3 計(jì)算梯度和方向

針對(duì)高斯濾波結(jié)果圖像，使用prewitt算子分別計(jì)算：x方向的梯度P；y方向的梯度Q；梯度M；梯度方向θ。梯度 ，梯度方向 ，并由弧度轉(zhuǎn)換為角度。

3.4 非最大抑制

非最大抑制階段，逐像素檢測其梯度是否不小于其梯度方向上兩側(cè)像素點(diǎn)的梯度值，插值計(jì)算各像素梯度方向兩側(cè)像素的梯度，進(jìn)行比較，若像素的梯度是三個(gè)點(diǎn)中最大的，將該像素確定為為候選邊緣，像素值設(shè)為128。其中根據(jù)梯度方向，分為四類進(jìn)行插值運(yùn)算，分別是：（1）[0o，45o），[180o，225o）；（2）[45o，90o），[225o，270o）；（3）[90o，135o），[270o，315o）；（4）[135o，180o），[315o，360o）。

3.5自適應(yīng)計(jì)算雙門限值

此階段采用類間最大方差法進(jìn)行兩次運(yùn)算，分別求出高閾值和低閾值。分為四個(gè)步驟：

（1）統(tǒng)計(jì)非最大抑制后的各梯度像素?cái)?shù)，得到梯度直方圖，使用parallel_for模板；

（2）統(tǒng)計(jì)最大梯度值M，串行計(jì)算；

（3）在梯度直方圖數(shù)據(jù)基礎(chǔ)上，對(duì)每一梯度值，用公式（4）求出不大于該梯度的梯度總質(zhì)量矩；此運(yùn)算屬于前綴和運(yùn)算，使用parallel_scan模板。

3.6 邊緣檢測與連接階段

在非最大抑制后的圖像上，檢測各像素的梯度值，梯度大于高閾值的設(shè)為邊緣，梯度在高低閾值之間又與邊緣像素相鄰的像素也設(shè)為邊緣，其它像素為非邊緣像素。分三步進(jìn)行：

（1）邊緣檢測：對(duì)每個(gè)像素，其若高于高閾值，設(shè)置為邊緣像素，并行，parallel_for模板；

（2）邊緣連接：與邊緣像素相鄰的像素，梯度值高于低閾值的，設(shè)置為邊緣像素，遞歸進(jìn)行。串行。

（3）設(shè)置非邊緣像素灰度值為0，并行，parallel_for模板。

此階段，筆者嘗試了以下方法：

使用一階段并行，遞歸進(jìn)行邊緣檢測，實(shí)驗(yàn)中發(fā)生沖突，因?yàn)橄噜徬袼赜泄餐泥徑狱c(diǎn)，如果這兩個(gè)像素均為邊緣，并且該鄰接點(diǎn)梯度高于低閾值，則都要寫入此鄰接點(diǎn)的灰度值，就發(fā)生了并發(fā)沖突。

此階段第二步筆者嘗試使用TBB提供的并發(fā)容器concurrent_hash_map分兩步進(jìn)行：（1）考查已設(shè)置為邊緣的像素，若其梯度高于低閾值，將該像素保存在一個(gè)concurrent_hash_map中；遞歸。（2）將位于concurrent_hash_map中的像素設(shè)置為邊緣，其余像素設(shè)置為非邊緣。實(shí)驗(yàn)結(jié)果表明，這種方法的速度比串行速度慢，因此邊緣連接階段仍采用了串行算法。

4 實(shí)驗(yàn)結(jié)果與分析

本文采用的實(shí)驗(yàn)平臺(tái)是AMD A6-3670四核處理器，2.7GHz，4G內(nèi)存，編程環(huán)境為Visual Studio 2010，語言采用VC10.0，TBB版本為4.1。圖像分辨率從512*512到4096*4096的8bits灰度Lena圖像，進(jìn)行對(duì)比實(shí)驗(yàn)，結(jié)果見表1。其中線程數(shù)是初始化TBB的task_scheduler_init對(duì)象時(shí)指定的線程數(shù)量，在使用parallel_for模板時(shí)，指定粒度為1024，其中的運(yùn)行時(shí)間包括圖像讀取、處理和保存的總時(shí)間。

從實(shí)驗(yàn)結(jié)果可以看出，并行算法在線程數(shù)設(shè)置為1時(shí)，也比串行算法要快，在實(shí)驗(yàn)數(shù)據(jù)范圍內(nèi)，隨著圖像的增大，加速比逐漸提高，但沒有高出計(jì)算機(jī)核數(shù)。

5 結(jié)語

使用Intel TBB并行模板進(jìn)行自適應(yīng)Canny邊緣檢測，提高了邊緣檢測的速度，算法通用性強(qiáng)，對(duì)提高圖像處理的實(shí)時(shí)性有一定的意義。其中邊緣連接階段的并行處理尚需進(jìn)一步研究。

參考文獻(xiàn)

[1]Cameron Hughes，Tracey Hughes著，齊寧譯.C++多核高級(jí)編程[M].北京：清華大學(xué)出版社，2010：1-16.

[2]張思乾，程果，陳犖 等.多核環(huán)境下邊緣提取并行算法研究[J].計(jì)算機(jī)科學(xué)，2012，39（1）：295-298.

[3]杜文亮，劉曉東，呂園園.基于C-Canny 算子與灰度空間的彩色圖像邊緣檢測[J].微電子學(xué)與計(jì)算機(jī)，2010，27（4）：17-20.

[4]Milan Sonka，Vaclav Hlavac，Roger Boyle著，艾海舟，蘇延超，興軍亮 等譯.圖像處理、分析與機(jī)器視覺（第3版）[M].北京：清華大學(xué)出版社，2011：100-102.

[5]趙潔，李瑋，郝志鵬，彭慧卿.基于改進(jìn)Canny算子與圖像形態(tài)學(xué)融合的邊緣檢測方法[J].微型機(jī)與應(yīng)用，2011，30（10）：44-47.

[6]劉超，周激流，何坤.基于Canny算法的自適應(yīng)邊緣檢測方法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2010，31（18）：4036-4039.

[7]李二森，張保明，周曉明，等.自適應(yīng)Canny邊緣檢測算法研究[J]測繪科學(xué)，2008，33（6）：119-120.

[8]王植，賀賽先.一種基于Canny理論的自適應(yīng)邊緣檢測方法[J].中國圖象圖形學(xué)報(bào)，2004，9（8）：957-961.

[9]陳宏希.基于邊緣保持平滑濾波的Canny算子邊緣檢測[J].蘭州交通大學(xué)學(xué)報(bào)（自然科學(xué)版），2006，25（1）：86-90.

[10]王小俊，劉旭敏，關(guān)永.基于改進(jìn)Canny算子的圖像邊緣檢測算法[J].計(jì)算機(jī)工程，2012，38（14）：196-198，202.

[11]陳杰，王振華，竇麗華.一種尺度自適應(yīng)Canny邊緣檢測方法[J].光電工程，2008，35（2）：79-84.

[12]James Reinders（仁達(dá)敬）著，聶雪軍譯.Intel Threading Building Blocks編程指南[M].北京：機(jī)械工業(yè)出版社，2009：46-122.