摘 要：針對Hough變換存在的運(yùn)算時(shí)間較長的缺點(diǎn)，本文用了TBB（Threading Building Blocks）這種線程構(gòu)建模塊來并行處理Hough變換檢測圓的問題，以有效的減少其運(yùn)行時(shí)間。并通過實(shí)驗(yàn)表明這種方法對Hough變換有很好的加速效果。

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

中圖分類號：TP391

1 Hough變換簡介

Hough變換是由Paul Hough在1962年提出的，并申請了專利。其基本思想是將圖像空間中的一個(gè)點(diǎn)變換經(jīng)過坐標(biāo)變換變換為參量空間中的一條曲線或者一個(gè)曲面，在坐標(biāo)變換中具有同一參量特征的點(diǎn)經(jīng)變換后在參量空間中相交，我們可以通過判斷交點(diǎn)處的累積程度來檢測特征曲線。這種方法是一種檢測二進(jìn)制圖像中直線、圓、橢圓等圖形的有效方法，后來人們又提出了可以檢測任意形狀圖形的廣義Hough變換的應(yīng)用范圍已經(jīng)不僅僅是識(shí)別圖形的邊界了，它在生物醫(yī)學(xué)、辦公文檔圖像處理、SAR/ISAR圖像處理和自動(dòng)判讀航空圖像等多個(gè)方面也有著廣泛的應(yīng)用[1]。

2 Hough變換檢測圓的串行算法

一般情況下，圖像空間中的圓經(jīng)過Hough變換后映射在參數(shù)空間中是三維的，需要在參數(shù)空間中建立一個(gè)三維的累加數(shù)組A（a，b，r），用于對圖像中每一個(gè)邊緣點(diǎn)進(jìn)行計(jì)算之后的累加[2]。算法的具體步驟如下：

（1）對圖像進(jìn)行邊緣檢測并二值化；

（2）依據(jù)圖像的大小分別計(jì)算參數(shù)a，b，r的最小值和最大值，建立三維離散的參數(shù)空間，參數(shù)空間的大小由a，b，r的最小值和最大值決定；

（3）在參數(shù)空間中建立累加器數(shù)組A（a，b，r），并置其中每一個(gè)元素為0；

（4）對圖像中的邊緣點(diǎn)作Hough變換，即通過公式（3-6）計(jì)算出該點(diǎn)在（a，b，r）三維網(wǎng)格上的對應(yīng)曲線，并在相應(yīng)的累加器上加1，即A（a，b，r）=A（a，b，r）+1；

（5）找出對應(yīng)圖像共圓周點(diǎn)的累加器上的局部最大值，這個(gè)值就提供了圖像平面上共圓周點(diǎn)的半徑以及圓心參數(shù)[3]。

3 利用TBB并行檢測圓

由檢測圓的串行算法，可以得知在整個(gè)檢測過程中最耗時(shí)的也是算法的第四步，而這個(gè)過程中也是一個(gè)循環(huán)迭代，故對該算法的并行主要是針對這一段的。在這段的循環(huán)迭代中，各個(gè)迭代是相互獨(dú)立的，可以通過TBB中的模板類parallel_for或模板類parallel_reduce來將這個(gè)循環(huán)并行化。又因程序中的循環(huán)累加是可重入的，即上一次運(yùn)行與下一次運(yùn)行之間沒有聯(lián)系，或說上一次運(yùn)行不會(huì)改變下一次運(yùn)行的結(jié)果，故能通過模板類parallel_for來并行。

對該循環(huán)進(jìn)行并行化首先是要把循環(huán)體轉(zhuǎn)換成在小空間上進(jìn)行操作的形式，該形式是標(biāo)準(zhǔn)模板庫風(fēng)格的函數(shù)對象，稱為體對象，每一個(gè)小空間將有一個(gè)operator（）來處理。注意方法operator（）的迭代空間參數(shù)，blocked_range是一個(gè)在庫中定義的模板類，它表示類型T上的一維迭代空間。在類parallel_for中也可以使用其他類型的迭代空間，在庫中還定義了blocked_range2d用來表示二維迭代空間。在OpFor中需要包含一些成員變量來保存那些在循環(huán)外部定義，但卻要在循環(huán)內(nèi)部使用的局部變量。通常，在體對象的構(gòu)造器中將這些成員變量初始化，不過parallel_for并不需要關(guān)心體對象是如何創(chuàng)建的。模板函數(shù)parallel_for要求體對象有一個(gè)構(gòu)造器的副本，這個(gè)構(gòu)造器用來為每一個(gè)工作線程創(chuàng)建一個(gè)獨(dú)立的副本，parallel_for還會(huì)調(diào)用析構(gòu)函數(shù)來銷毀這些副本[4]。

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

表1是Hough變換檢測圓的串行程序和TBB并行程序執(zhí)行時(shí)間的對比表：

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

圖片編號圖片大小圖片寬高（像素）串行執(zhí)行時(shí)間（秒）并行執(zhí)行時(shí)間（秒）加速比

圖片11.48M868*6000.4680.1802.600

圖片234.3M4000*30003.7811.4612.588

圖片318.1M2772*228620.2046.6023.060

圖片435.8M2795*448185.42224.5623.478

圖片560.1M5973*4481285.09380.3443.548

圖片6152M11922*4481876.016240.1563.648

圖1 TBB檢測圓的加速比比較圖

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

（1）圖片2的圖片大小和像素?cái)?shù)雖然比圖片3要大，但由于其所選的圖片比較簡單，其中存在的圓數(shù)比圖片3要少的多，故其執(zhí)行時(shí)間要比圖片3短很多；

（2）將程序通過TBB的任務(wù)調(diào)度機(jī)制映射到四個(gè)物理線程上運(yùn)行，相對于單物理線程，理論上速度可以提高四倍。但由于存在線程開銷和通信同步等消耗，以及程序中仍然存在部分串行程序比例，系統(tǒng)其它開銷等因素，最后的速度提高不會(huì)達(dá)到理論值。

5 結(jié)束語

本文在實(shí)現(xiàn)串行Hough變換算法的基礎(chǔ)上，使用TBB工具對其進(jìn)行了并行化改造加速，都取得了較好的效果。

參考文獻(xiàn)：

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

[2]LI ZE-NIAN， TONG F， LAUGHLIN R G.Parallel algorithms for line detection on a 1×N array processor [C].Proceedings of the 1991 IEEE International Conference on Robotics and Automation.Washington， DC： IEEE Press，1991：2312-2318.

[3]陳燏，陳宏建，徐曉華.一種快速高效的Hough變換并行算法[J].電子學(xué)報(bào)，2004（05）：759-762

[4]張彤，劉釗，歐陽寧等.基于圖形處理器的實(shí)時(shí)直線段檢測[J].計(jì)算機(jī)應(yīng)用，2009（05）：1359-1361.

作者簡歷：劉向嬌（1984-），女，河南安陽人，助教，碩士，研究方向：并行處理。

作者單位：南陽師范學(xué)院 軟件學(xué)院，河南南陽 473061

基金項(xiàng)目：1.國家自然科學(xué)基金項(xiàng)目（項(xiàng)目編號：60963004）；2.河南省基礎(chǔ)與前言技術(shù)研究計(jì)劃項(xiàng)目，（項(xiàng)目編號：132300410439）；3.河南省基礎(chǔ)與前沿技術(shù)研究計(jì)劃項(xiàng)目，（項(xiàng)目編號：122300410302）；4.河南省基礎(chǔ)與前沿技術(shù)研究計(jì)劃項(xiàng)目，（項(xiàng)目編號：132300410433）；5.南陽師范學(xué)院校級項(xiàng)目，（項(xiàng)目編號：QN2013040）；6.南陽師范學(xué)院校級科研項(xiàng)目，（項(xiàng)目編號：QN2010010）。