一種自適應Canny邊緣檢測算法的并行設計與TBB實現(xiàn)*

孫陸鵬　肖漢

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

關鍵詞：Intel TBB 自適應高斯平滑 Canny邊緣檢測 自適應閾值

中圖分類號：TP391 文獻標識碼：A 文章編號：1007-9416（2016）06-0000-00

1 引言

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

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

2自適應Canny邊緣檢測算法簡介

Canny邊緣檢測算法是Canny在1983年提出的，它基于以下三個標準[9，10]：（1）檢測標準：不丟失重要的邊緣，不應有虛假的邊緣；（2）定位標準：實際邊緣與檢測到的邊緣位置之間的偏差最?。唬?）單響應標準：將多個響應降低為單個邊緣響應。Canny邊緣檢測的一般過程如下[4]：

2）計算圖像中的每個像素的梯度和梯度方向；

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

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

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

3 并行性分析與設計

多核并行Canny自適應邊緣檢測方法的每一步都要用到前一步的計算結果，依賴性較強。分六個階段進行，選擇TBB的模板進行并行計算。

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

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

3.3 計算梯度和方向

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

3.4 非最大抑制

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

3.5自適應計算雙門限值

此階段采用類間最大方差法進行兩次運算，分別求出高閾值和低閾值。分為四個步驟：

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

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

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

3.6 邊緣檢測與連接階段

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

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

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

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

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

使用一階段并行，遞歸進行邊緣檢測，實驗中發(fā)生沖突，因為相鄰像素有共同的鄰接點，如果這兩個像素均為邊緣，并且該鄰接點梯度高于低閾值，則都要寫入此鄰接點的灰度值，就發(fā)生了并發(fā)沖突。

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

4 實驗結果與分析

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

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

5 結語

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

參考文獻

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

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

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

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

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

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

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

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

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

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

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

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