基于TBB的Hough變換并行檢測直線

劉向嬌　趙學(xué)武　賈超超

摘要：Hough變換存在著運(yùn)算時(shí)間長的缺點(diǎn)，用了并行處理這種解決海量數(shù)據(jù)計(jì)算的有效方法來減少其運(yùn)行時(shí)間。該文主要研究了：利用TBB（Threading Building Blocks）這種線程構(gòu)建模塊在多核機(jī)上對Hough變換中可并行的部分進(jìn)行并行化；實(shí)驗(yàn)表明這種方法對Hough變換的并行化都有很好的加速效果。

關(guān)鍵詞：Hough變換；TBB

中圖分類號：TP391 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2014）13-3162-03

Hough Transform Based on TBB Parallel Detection Straight Line

LIU Xiang-jiao1， ZHAO Xue-wu1， JIA Chao-chao2

（1.Department of Soft， Nanyang Normal College， Nanyang 473061， China； 2.ChuMuJu， Jiyuan 454450， China）

Abstract： Hough transform operation time long shortcomings， using the parallel processing that solution is a effective method to compute the huge amounts of data to reduce the running time. This paper mainly studied the： using the TBB （Threading Building Blocks） this thread Building Blocks on a multi-core machine was carried out on the part of the Hough transform can be parallel parallelization； Parallel experiments show that this method of Hough transform has a good speedup.

Key word： Hough transform；TBB

TBB的概念在2004年產(chǎn)生于Intel的內(nèi)部，到了目前已經(jīng)有了4.2的版本。TBB在編程的時(shí)候使用模板作為通常的并行迭代模型。它提供了豐富的C++模板類，這使得程序員不需要專業(yè)地去學(xué)習(xí)同步、緩存優(yōu)化、負(fù)載平衡等問題，就能很容易地自動(dòng)調(diào)度并行程序，并能使CPU的多個(gè)核心都高效的運(yùn)轉(zhuǎn)起來。TTB是一種能使程序的伸縮性得以提升，且對嵌套完全支持的并行編程模型，可以在 Windows、MacX和Linux的系統(tǒng)上運(yùn)行，支持 Intel C++、VC7/和gcc編譯器。并且為了構(gòu)建大型的并行程序，允許程序員創(chuàng)建自己的并行組件[1]。

1 TBB的任務(wù)調(diào)度器

線程構(gòu)建模塊的核心組件就是TBB的任務(wù)調(diào)度器（Task Schedule），任務(wù)調(diào)度器使用之前，每個(gè)線程都會通過tbb：： task_scheduler_int來初始化線程構(gòu)建模塊庫，并且在同時(shí)還會隱含地初始化一個(gè)全局線程池，通過調(diào)度與任務(wù)機(jī)制自動(dòng)地來管理線程池。任務(wù)的管理由任務(wù)調(diào)度器通過線程池來進(jìn)行，通過使用讓每一個(gè)邏輯線程都對應(yīng)一個(gè)物理線程的方法來解決負(fù)荷問題。使用TBB的任務(wù)調(diào)度機(jī)制task與task_schedule可以將線程與任務(wù)結(jié)合，任務(wù)就是計(jì)算的邏輯單元，用戶可以不必關(guān)注線程，而只關(guān)心任務(wù)本身，通過使用把這些任務(wù)映射到物理線程的方法以減少系統(tǒng)的開銷。任務(wù)調(diào)度器不需要用戶考慮負(fù)載平衡問題，只需要把程序分成若干個(gè)小任務(wù)，調(diào)度器就會將任務(wù)自動(dòng)分配給線程，做到在多核處理器上的負(fù)載均衡。

任務(wù)調(diào)度器將任務(wù)映射到物理線程，這個(gè)映射是非搶占式的。每個(gè)線程都有一個(gè)execute（）方法，當(dāng)線程開始執(zhí)行execute（）方法之后，這個(gè)任務(wù)將被綁定到線程上，直到execute（）方法返回。在這期間，線程只有在子任務(wù)上等待時(shí)，才會執(zhí)行其他任務(wù)，這時(shí)它可以執(zhí)行同一線程中的其他子任務(wù)或 （如果沒有正在等待的子任務(wù)）執(zhí)行在其他線程中創(chuàng)建的任務(wù)。

任務(wù)調(diào)度器主要是將計(jì)算高度密集的工作進(jìn)行并行化。由于任務(wù)對象不會被搶先調(diào)度，故在執(zhí)行時(shí)不可以有長時(shí)間的阻塞，因阻塞的線程（及其相應(yīng)的處理器）將無法為其他任務(wù)服務(wù)了。

調(diào)度器是對任務(wù)圖進(jìn)行計(jì)算的。任務(wù)圖就是一張有向圖，圖中的一個(gè)節(jié)點(diǎn)表示一個(gè)任務(wù)，每個(gè)節(jié)點(diǎn)都指向其各自的父節(jié)點(diǎn)，根節(jié)點(diǎn)的父節(jié)點(diǎn)是NULL，或是正在等待根節(jié)點(diǎn)完成的其他任務(wù)。通過task：：parent（）方法能訪問父指針。

2 Hough變換檢測直線的原理

Hough變換的基本思想是：利用點(diǎn)—線的對偶性，即圖像空間中共線的點(diǎn)與參數(shù)空間中相交的線相對應(yīng)；而反過來，相交于參數(shù)空間里同一個(gè)點(diǎn)上的所有直線（曲線）與在圖像空間中共線的點(diǎn)相對應(yīng)[2-3]。

在圖像空間X-Y中，所有共線的點(diǎn)（x，y）均能用公式（1）所示的直線方程來描述：

y=mx+c （1）

其中截距是c，斜率是m，公式（1）又可以改寫成公式（2）：

c=-xm+y （2）

該方程是參數(shù)空間M-C中的一條直線方程，其中y是截距，x是斜率。

比較公式（1）與公式（2）可以知道，在圖像空間中的一點(diǎn)（x，y）至少要與參數(shù)空間中的一條直線相對應(yīng)，而圖像空間中的一條直線又是由參數(shù)空間中的一個(gè)點(diǎn)（m，c）來決定的。Hough變換的基本思想就是將公式（1）和公式（2）這兩個(gè)式子看作是對圖像空間里的點(diǎn)與參數(shù)空間里的線的約束條件，并定義了一個(gè)一對多的從圖像空間到參數(shù)空間的映射關(guān)系。endprint

假若被檢測直線的斜率為無限大（例直線x=a），公式（2）將無法完成該直線的檢測工作，要想使任意方向或位置的直線都能夠被正確的識別和檢測[4]，我們可以利用Hart與Duda提出的直線極坐標(biāo)方程公式來替代公式（1）：

[ρ]=ycos[θ]+xsin[θ] （3）

3 利用TBB并行檢測直線

由檢測直線的串行算法可以得到在整個(gè)檢測過程中最耗時(shí)的是：對任意一個(gè)給定的[θ]值，對X-Y平面上的每一個(gè)邊緣像素點(diǎn)應(yīng)用Hough變換，利用公式[ρn=icosθm+jsinθm]，計(jì)算相應(yīng)的[ρ]值，并在相應(yīng)的累加器上加l，[A（ρ，θ）=A（ρ，θ）+1][5]。又因這一步是一個(gè)循環(huán)迭代過程（其中所有的迭代都可以同時(shí)運(yùn)行，不互相影響），而循環(huán)迭代又是可擴(kuò)展并行的簡單形式，故對此算法的并行化改造應(yīng)主要針對這個(gè)最耗時(shí)的循環(huán)進(jìn)行[6]。

在這個(gè)循環(huán)迭代中，由于各個(gè)迭代是相互獨(dú)立的，故可以通過TBB中的模板類parallel_for或模板類parallel_reduce將這個(gè)循環(huán)并行化。又因程序中的累加是不可重入的，即下一次循環(huán)依賴上一次循環(huán)的結(jié)果，故只能通過模板類parallel_reduce來并行。在應(yīng)用模板類parallel_reduce時(shí)，線程私有的函數(shù)副本在最后要被合并起來，故operator（）不能被聲明為const。OpSum擁有一個(gè)join方法和一個(gè)劃分構(gòu)造函數(shù)。

在劃分構(gòu)造函數(shù)中有一個(gè)split類型的啞參數(shù)和一個(gè)指向初始對象的引用參數(shù)。這個(gè)啞參數(shù)的作用是將劃分構(gòu)造函數(shù)與構(gòu)造函數(shù)副本（在構(gòu)造副本中沒有這個(gè)參數(shù)）區(qū)分開來[7]。當(dāng)任務(wù)完成了它的工作且開始將結(jié)果匯合到整體工作中去時(shí)，就需要調(diào)用join方法。傳遞給這個(gè)方法的參數(shù)是已經(jīng)完成工作的結(jié)果，故這個(gè)方法只需要重復(fù)在每個(gè)元素上執(zhí)行相同的運(yùn)算（在這里是求和運(yùn)算）即可。當(dāng)任務(wù)調(diào)度器發(fā)現(xiàn)有一個(gè)工作線程可用時(shí)，parallel_reduce將首先調(diào)用劃分構(gòu)造函數(shù)來創(chuàng)建子任務(wù)，然后把子任務(wù)傳遞給這個(gè)線程來執(zhí)行。當(dāng)任務(wù)完成時(shí)，parallel_reduce將使用join方法來匯合各個(gè)子任務(wù)的結(jié)果[8]。注意，劃分構(gòu)造函數(shù)可能會并發(fā)地進(jìn)行，故當(dāng)在劃分構(gòu)造函數(shù)中需要增加其他共享對象的引用計(jì)數(shù)時(shí)，應(yīng)該使用原子遞增操作。

以下是用TBB檢測直線程序的核心代碼：

struct OpSum{

int r；

void operator（）（const tbb：：blocked_range &t）

{ for（int i=t.begin（）； i！=t.end（）； ++i）

for（ int j = 0； j < width； j++ ）

{if（ image[i * step + j] ！= 0 ）

for（int n = 0； n < numangle； n++ ）

{

r = cvRound（ j * tabCos[n] + i * tabSin[n] ）；

r += （numrho - 1） / 2；

accum[（n+1） * （numrho+2） + r+1]++；

}}}

void join（OpSum& x）{r += x.r；}

OpSum（ OpSum& x， tbb：：split）

： r（0） {；}

OpSum（）

：r（0） {；}

}；

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

在Hough變換檢測直線的串行程序和TBB并行程序執(zhí)行時(shí)間的對比中，應(yīng)用的硬件環(huán)境：CPU 為Intel Core2 Quad Q9400 2.66GHz，內(nèi)存為 DDR3 4G；軟件環(huán)境：Windows XP；編程環(huán)境：Microsoft Visual Studio 2008，tbb30_20100915oss。線檢測串并行程序執(zhí)行時(shí)間比較表：

表1 直線檢測串并行程序執(zhí)行時(shí)間比較表

[圖片編號＼&圖片大?。?amp;圖片寬高（像素）＼&串行執(zhí)行時(shí)間（秒）＼&并行執(zhí)行時(shí)間（秒）＼&加速比＼&圖片1＼&1.48M＼&868*600＼&0.578＼&0.257＼&2.249＼&圖片2＼&34.3M＼&4000*3000＼&1.468＼&0.518＼&2.834＼&圖片3＼&18.1M＼&2772*2286＼&8.156＼&2.477＼&3.292＼&圖片4＼&35.8M＼&2795*4481＼&19.046＼&5.625＼&3.386＼&圖片5＼&60.1M＼&5973*4481＼&42.781＼&12.438＼&3.440＼&圖片6＼&152M＼&11922*4481＼&122.109＼&34.601＼&3.529＼&]

圖1 TBB檢測直線的加速比比較圖

有上表1和圖1可得出如下結(jié)論：

1）實(shí)驗(yàn)中所用的圖片2的圖片大小和像素?cái)?shù)雖然比圖片3要大，但由于其所選的圖片比較簡單，其中存在的直線條數(shù)比圖片3要少的多，故其執(zhí)行時(shí)間要比圖片3短很多。

2）在啟動(dòng)了多個(gè)線程的時(shí)候，剛開始由于問題的規(guī)模較小，線程間的切換也比較頻繁并且初始化多個(gè)線程也要占用較多的時(shí)間，故加速比不是很大。隨著問題規(guī)模的擴(kuò)大，CPU的使用率也越來越高，多核優(yōu)勢逐漸體現(xiàn)出來，而啟動(dòng)多個(gè)線程所用的時(shí)間在程序總的執(zhí)行時(shí)間中所占的比例也越來越小，故加速比越來越大。

5 結(jié)束語

本文在實(shí)現(xiàn)串行Hough變換算法的基礎(chǔ)上，使用TBB工具對其進(jìn)行了并行化改造加速，都取得了較好的效果。但論文還有一些不足需要進(jìn)一步改進(jìn)和提高：

由于時(shí)間的關(guān)系，該文只做了Hough變換對直線檢測的并行化研究工作，而對圓、橢圓及拋物線之類的其他曲線檢測的并行化有待進(jìn)一步研究。

參考文獻(xiàn)：

[1] Bennett N，ButridgeR，Saito N.A Method to Detect and Characterize ElliPses Using the Hough Transform[J].IEEE Transactions on Patten Analysis and Machine Intelligence，1999，21（7）.

[2] Ballard D H.Generalizing the Hough Transform to detect arbitrary shapes[J].PatternReeoguition，1981，13（2）：111-122.

[3] 趙書安，馮少彤，聶守平.Hough變換在幾何特征檢測中的應(yīng)用[J].南京師范大學(xué)學(xué)報(bào)：工程技術(shù)版，2006，16（4）.

[4] IbrahimHAH，Kender J R，Shaw D E.The analysis and performanceof two middle-level vision tasks on a fine-grained SIMD tree machine [A].Binford T O.Proceedings IEEE Computer Society Conference onComputer Vision and Pattern Recognition[C].Los Alamitos： IEEE Computer Society Press，1985：387-393.

[5] Fisher A L，Highnam P T.Computing the hough transform on a scan line array processor[J].IEEETransactions on PAMI，1989，11（3）：262-265.

[6] Jolion J，Rosenfeld A.AnO（logn） pyramid Hough transform[J].Pat-tern Recognition Letters，1989，9（5）：343-349.

[7] Pan Y，Chung H Y H.Faster line detection algorithms on enhanced mesh connected arrays[J].IEEE Proceeding-E，1993，2（140）：95-100.

[8] Chung KL，Lin H Y.Hough transform on reconfigurable meshes[J].Computer Vision and Image Understanding，1995，61（2）：278-284.endprint

由于時(shí)間的關(guān)系，該文只做了Hough變換對直線檢測的并行化研究工作，而對圓、橢圓及拋物線之類的其他曲線檢測的并行化有待進(jìn)一步研究。

參考文獻(xiàn)：

[1] Bennett N，ButridgeR，Saito N.A Method to Detect and Characterize ElliPses Using the Hough Transform[J].IEEE Transactions on Patten Analysis and Machine Intelligence，1999，21（7）.

[2] Ballard D H.Generalizing the Hough Transform to detect arbitrary shapes[J].PatternReeoguition，1981，13（2）：111-122.

[3] 趙書安，馮少彤，聶守平.Hough變換在幾何特征檢測中的應(yīng)用[J].南京師范大學(xué)學(xué)報(bào)：工程技術(shù)版，2006，16（4）.

[4] IbrahimHAH，Kender J R，Shaw D E.The analysis and performanceof two middle-level vision tasks on a fine-grained SIMD tree machine [A].Binford T O.Proceedings IEEE Computer Society Conference onComputer Vision and Pattern Recognition[C].Los Alamitos： IEEE Computer Society Press，1985：387-393.

[5] Fisher A L，Highnam P T.Computing the hough transform on a scan line array processor[J].IEEETransactions on PAMI，1989，11（3）：262-265.

[6] Jolion J，Rosenfeld A.AnO（logn） pyramid Hough transform[J].Pat-tern Recognition Letters，1989，9（5）：343-349.

[7] Pan Y，Chung H Y H.Faster line detection algorithms on enhanced mesh connected arrays[J].IEEE Proceeding-E，1993，2（140）：95-100.

[8] Chung KL，Lin H Y.Hough transform on reconfigurable meshes[J].Computer Vision and Image Understanding，1995，61（2）：278-284.endprint

由于時(shí)間的關(guān)系，該文只做了Hough變換對直線檢測的并行化研究工作，而對圓、橢圓及拋物線之類的其他曲線檢測的并行化有待進(jìn)一步研究。

參考文獻(xiàn)：

[1] Bennett N，ButridgeR，Saito N.A Method to Detect and Characterize ElliPses Using the Hough Transform[J].IEEE Transactions on Patten Analysis and Machine Intelligence，1999，21（7）.

[2] Ballard D H.Generalizing the Hough Transform to detect arbitrary shapes[J].PatternReeoguition，1981，13（2）：111-122.

[3] 趙書安，馮少彤，聶守平.Hough變換在幾何特征檢測中的應(yīng)用[J].南京師范大學(xué)學(xué)報(bào)：工程技術(shù)版，2006，16（4）.

[4] IbrahimHAH，Kender J R，Shaw D E.The analysis and performanceof two middle-level vision tasks on a fine-grained SIMD tree machine [A].Binford T O.Proceedings IEEE Computer Society Conference onComputer Vision and Pattern Recognition[C].Los Alamitos： IEEE Computer Society Press，1985：387-393.

[5] Fisher A L，Highnam P T.Computing the hough transform on a scan line array processor[J].IEEETransactions on PAMI，1989，11（3）：262-265.

[6] Jolion J，Rosenfeld A.AnO（logn） pyramid Hough transform[J].Pat-tern Recognition Letters，1989，9（5）：343-349.

[7] Pan Y，Chung H Y H.Faster line detection algorithms on enhanced mesh connected arrays[J].IEEE Proceeding-E，1993，2（140）：95-100.

[8] Chung KL，Lin H Y.Hough transform on reconfigurable meshes[J].Computer Vision and Image Understanding，1995，61（2）：278-284.endprint