国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

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

2014-07-18 00:42:50劉向嬌趙學(xué)武賈超超
電腦知識與技術(shù) 2014年13期
關(guān)鍵詞:任務(wù)調(diào)度線程直線

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

摘要:Hough變換存在著運(yùn)算時間長的缺點(diǎn),用了并行處理這種解決海量數(shù)據(jù)計算的有效方法來減少其運(yùn)行時間。該文主要研究了:利用TBB(Threading Building Blocks)這種線程構(gòu)建模塊在多核機(jī)上對Hough變換中可并行的部分進(jì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在編程的時候使用模板作為通常的并行迭代模型。它提供了豐富的C++模板類,這使得程序員不需要專業(yè)地去學(xué)習(xí)同步、緩存優(yōu)化、負(fù)載平衡等問題,就能很容易地自動調(diào)度并行程序,并能使CPU的多個核心都高效的運(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)度器使用之前,每個線程都會通過tbb:: task_scheduler_int來初始化線程構(gòu)建模塊庫,并且在同時還會隱含地初始化一個全局線程池,通過調(diào)度與任務(wù)機(jī)制自動地來管理線程池。任務(wù)的管理由任務(wù)調(diào)度器通過線程池來進(jìn)行,通過使用讓每一個邏輯線程都對應(yīng)一個物理線程的方法來解決負(fù)荷問題。使用TBB的任務(wù)調(diào)度機(jī)制task與task_schedule可以將線程與任務(wù)結(jié)合,任務(wù)就是計算的邏輯單元,用戶可以不必關(guān)注線程,而只關(guān)心任務(wù)本身,通過使用把這些任務(wù)映射到物理線程的方法以減少系統(tǒng)的開銷。任務(wù)調(diào)度器不需要用戶考慮負(fù)載平衡問題,只需要把程序分成若干個小任務(wù),調(diào)度器就會將任務(wù)自動分配給線程,做到在多核處理器上的負(fù)載均衡。

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

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

調(diào)度器是對任務(wù)圖進(jìn)行計算的。任務(wù)圖就是一張有向圖,圖中的一個節(jié)點(diǎn)表示一個任務(wù),每個節(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ù)空間里同一個點(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ù)空間中的一個點(diǎn)(m,c)來決定的。Hough變換的基本思想就是將公式(1)和公式(2)這兩個式子看作是對圖像空間里的點(diǎn)與參數(shù)空間里的線的約束條件,并定義了一個一對多的從圖像空間到參數(shù)空間的映射關(guān)系。endprint

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

[ρ]=ycos[θ]+xsin[θ] (3)

3 利用TBB并行檢測直線

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

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

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

在Hough變換檢測直線的串行程序和TBB并行程序執(zhí)行時間的對比中,應(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í)行時間比較表:

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

[圖片編號\&圖片大?。?amp;圖片寬高(像素)\&串行執(zhí)行時間(秒)\&并行執(zhí)行時間(秒)\&加速比\&圖片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)實驗中所用的圖片2的圖片大小和像素數(shù)雖然比圖片3要大,但由于其所選的圖片比較簡單,其中存在的直線條數(shù)比圖片3要少的多,故其執(zhí)行時間要比圖片3短很多。

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

5 結(jié)束語

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

由于時間的關(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é)報:工程技術(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

由于時間的關(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é)報:工程技術(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

由于時間的關(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é)報:工程技術(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

猜你喜歡
任務(wù)調(diào)度線程直線
基于改進(jìn)NSGA-Ⅱ算法的協(xié)同制造任務(wù)調(diào)度研究
基于時間負(fù)載均衡蟻群算法的云任務(wù)調(diào)度優(yōu)化
畫直線
兩條直線 變變變
畫直線
淺談linux多線程協(xié)作
云計算環(huán)境中任務(wù)調(diào)度策略
云計算中基于進(jìn)化算法的任務(wù)調(diào)度策略
Linux線程實現(xiàn)技術(shù)研究
么移動中間件線程池并發(fā)機(jī)制優(yōu)化改進(jìn)
马公市| 陕西省| 葫芦岛市| 枝江市| 婺源县| 乌什县| 洛川县| 新邵县| 苏尼特左旗| 井研县| 庆城县| 延吉市| 博爱县| 青神县| 普格县| 华亭县| 城步| 巴林左旗| 锡林郭勒盟| 阿尔山市| 溧水县| 临安市| 崇明县| 庆阳市| 乳山市| 木兰县| 徐闻县| 永嘉县| 峨山| 连城县| 景谷| 天长市| 天全县| 通化县| 柳江县| 巴楚县| 西贡区| 亳州市| 信丰县| 嘉峪关市| 康定县|