Hough變換檢測圓算法的并行化研究

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

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

中圖分類號：TP391

1 Hough變換簡介

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

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

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

（1）對圖像進行邊緣檢測并二值化；

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

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

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

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

3 利用TBB并行檢測圓

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

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

4 實驗結(jié)果分析

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

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

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

圖片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的圖片大小和像素數(shù)雖然比圖片3要大，但由于其所選的圖片比較簡單，其中存在的圓數(shù)比圖片3要少的多，故其執(zhí)行時間要比圖片3短很多；

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

5 結(jié)束語

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

參考文獻：

[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é)報，2004（05）：759-762

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

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

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

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