蘇志祁　尉　宇　王　濤

摘 要:利用Hough變換對直線進(jìn)行檢測,通常參數(shù)空間使用的是極坐標(biāo)系。這種方法存在速度緩慢,結(jié)果不夠精確的問題。這主要是因為極坐標(biāo)所用到的正弦函數(shù)和余弦函數(shù)具有非線性特性,使將來運(yùn)算基本單元的乘法不可避免。為解決這個問題,提出一種通過改換坐標(biāo)系、用加法和移位運(yùn)算代替乘法的新思想,大幅加快了Hough變換的速度。從而使超大型圖像中,直線的實時、精確檢測成為可能。

關(guān)鍵詞:Hough變換;極坐標(biāo);標(biāo)準(zhǔn)直線方程,改進(jìn)的Hough變換

中圖分類號:TP311文獻(xiàn)標(biāo)識碼:A

文章編號:1004-373X(2009)10-042-03

Realization for the Improved Hough Transform

SU Zhiqi,WEI Yu,WANG Tao

(Information Science & Engineering College,Wuhan University of Science and Technology,Wuhan,430081,China)

Abstract:There are some problems occur in Hough transform which generally use polar coordinates,such as low speed or inaccurate results.It is mainly caused by Sine and Cosine functions using in polar coordinates which have non-linear character,accordingly multiply is inevitable.In order to solve this problem,replacing polar coordinates and replacing multiply by addition and shift operator to speed up the process of Hough transform.Therefore,it rises the possibility to obtain in real-time and precise applications for large image.

Keywords:Hough transform;polar coordinates;standard straight line equation;improved Hough transform

0 引 言

Hough變換具有優(yōu)異的魯棒性和極佳的抗干擾能力[1-5],利用Hough變換進(jìn)行直線檢測,是圖像分析和計算機(jī)視覺的一個重要內(nèi)容[6]。但是Hough變換的計算量往往非常大,從而阻礙了其在快速、精確檢測直線方面的應(yīng)用。這里提出的新方法,不僅能大幅度減少Hough變換的總計算量,而且在像素允許的情況下,直線斜率的檢測精度保持最高,這對于超大型圖像中直線的實時、精確檢測,具有重要的實用價值[7]。

1 Hough變換檢測直線的原理

選取圖像空間中一條直線L的某些特征作為參數(shù)空間的一個點M,并且該直線L上的所有點,通過某種算法都能夠?qū)?yīng)這些特征,從而在圖像空間和參數(shù)空間之間,建立起“線-點”的對偶性[8]。Hough變換就是根據(jù)這種對偶性,將圖像空間中直線的檢測問題轉(zhuǎn)化為參數(shù)空間中點的檢測問題,而后者的處理比前者要簡單得多,進(jìn)行累加統(tǒng)計即可。

常用的Hough變換檢測直線的方法,是運(yùn)用下式在圖像空間和參數(shù)空間之間,建立對偶變換。

ρ=xcosα+ysinα(1)

式中:ρ為極徑;α為極角,取0°~180°;x為像素點相對圖像原點的行坐標(biāo);y為像素點相對圖像原點的列坐標(biāo)。為了檢測出直角坐標(biāo)系中,由非零點所構(gòu)成的直線,需要根據(jù)檢測分辨率的要求,將ρ離散化為Nα個參數(shù)區(qū)間,將ρ離散化為Nρ個參數(shù)區(qū)間,也就是說將極坐標(biāo)系量化成許多小格,建立參數(shù)空間。其核心程序代碼如下:

for(int i=0;i

for(int j=0;j

{

if(im.m[j][i]==feature_point)

{

for(angle=0;angle<180;angle++){

r=i*sin_tab[angle]+j*cos_tab[angle];nr=int(r+rmax);

Hough_ima.m[nr][angle]++;

}

}

}

最外層的兩層循環(huán)的目的是對整個圖像進(jìn)行一次遍歷,如果在(i,j)存在有效點,即if(im.m[j][i]==feature_point),則利用參數(shù)(i,j)在參數(shù)空間中畫一條正弦曲線。這條正弦曲線的方程就是ρ=xcosθ+ysinθ。由于程序中數(shù)組的下標(biāo)不能為負(fù)數(shù),所以必須進(jìn)行一次平移,也就是加上可能的負(fù)數(shù)的最大值rmax,之后就是使用一個for循環(huán),讓角度從0°~180°進(jìn)行掃描,使處于正弦線上的位置全部進(jìn)行累加,即Hough_ima.m[nr][angle]++。

如果需要檢測出原圖中的直線,還需要對Hough_ima.m進(jìn)行一次遍歷,搜索出最大值及它的坐標(biāo)。它的值表示在原空間中一共有幾個點落在這條直線上,利用它的坐標(biāo)(r,θ)就可以得到ρ=xcosθ+ysinθ,進(jìn)而就可以求出原直線方程y=kx+b,這樣就可達(dá)到最終目的。

當(dāng)然,有時還要知道這條直線的起點和終點,在獲得y=kx+b之后,這個問題變得非常簡單,只需要對x或者y進(jìn)行一次從最小值到最大值的掃描,即可找出第一個有效點和最后一個有效點,這就是這條直線的起點和終點。

2 改進(jìn)Hough變換的算法及實現(xiàn)

標(biāo)準(zhǔn)Hough變換其優(yōu)點是:無論直線怎樣變化,參數(shù)空間中α和ρ的取值范圍是有限的,所以,目前的直線檢測大多數(shù)都是基于這種方法。但是,這種方法在步進(jìn)值較小的情況下,存在很大缺陷。步進(jìn)值越小,計算量就越大。在要求檢測精度很高的場合,步進(jìn)值往往非常小,這樣會使計算量大增。

標(biāo)準(zhǔn)Hough變換的核心原理依靠的是ρ=xcosθ+ysinθ,對比原程序r=i*sin_tab[angle]+j*cos_tab[angle]可以看到,這里用到兩次查表,兩次乘法以及一次加法,并且由于正弦和余弦是非線性的,所以兩次乘法是不可避免的[10,11]。對于絕大多數(shù)處理,它們并不帶有硬件乘法器,而必須使用軟件的方法來模擬,這將耗費(fèi)很多的時鐘周期,使得程序運(yùn)行很慢,效率很低。

在此提出并實現(xiàn)了一種只用加法和移位運(yùn)算來實現(xiàn)的Hough變換,這種方法有利于在沒有硬件乘法器的CPU上實現(xiàn)Hough變換。它使用直線方程原始定義y=kx+b。可以看到,y=kx+b所有參數(shù)都是線性的,所以不需要乘法,只需要累加就可以。但是這個方法會遇到一個問題,這里的k的范圍是從正無窮到負(fù)無窮,解決的辦法是只對原圖進(jìn)行從-45°~+45°之間的直線檢測,然后將圖像的(x,y)互換,再次對圖像進(jìn)行從-45°~+45°之間的直線檢測,這樣就完成了整張圖片的直線檢測。

for(i=0;i

for(j=0;j

if( k4_lpBits[i*k6_pitch+j*3]!=0 )

{

int s1_tmp = (i+j)<< s_Nbit;

k=(1<<(s_Nbit+1))-1;do

{

k5_mat[k][(s1_tmp>>s_Nbit)+700 ]+=1;

s1_tmp-=j;

}

while(--k);

}

上面是核心代碼。變量s_Nbit是一個宏定義,決定處理的點數(shù),從-45°~+45°有2s_Nbit個點,程序中+700的目的是為了防止數(shù)組的下標(biāo)出現(xiàn)負(fù)數(shù)。這里使用的循環(huán)是 do-while循環(huán),并且使用的是遞減循環(huán),而不是通常的遞加循環(huán)。這個結(jié)構(gòu)和匯編語言中的loop語句剛好是同一個結(jié)構(gòu),如果使用通常的for循環(huán),將會在循環(huán)的跳轉(zhuǎn)語句上浪費(fèi)掉一些時間。使用遞減循環(huán)的好處就是省掉一條cmp語句。下面是這段代碼的反匯編。

在VS 2005中,右鍵單擊核心語句,選擇運(yùn)行到光標(biāo)處,再選擇切換到反匯編?？梢钥吹?

{

int s1_tmp = (i+j)<< s_Nbit;

00401977 mov ecx,edi

00401979 mov edx,7C830h

0040197E mov edi,edi

k=(1<<(s_Nbit+1))-1;do

{k5_mat[k][(s1_tmp>>s_Nbit) +700 ]+=1;

00401980 mov eax,ecx

00401982 sareax,7

00401985 add eax,edx

00401987 add dword ptr

[eax*4+404FB4h],1

0040198F lea eax,[eax*4+404FB4h]

s1_tmp-=j;

00401996 subecx,esi

} while(--k);

00401998 sub edx,7D0h

0040199E jne

}

經(jīng)過優(yōu)化,循環(huán)體本身幾乎不消耗語句,循環(huán)變量k也被優(yōu)化掉了,所以這是一段性能還算比較理想的代碼。由于外層循環(huán)多一條語句少一條語句對整體性能幾乎沒有影響,所以本文并沒有在外層循環(huán)使用do-while遞減循環(huán)。

3 測試與驗證

運(yùn)用斜率兩次查找法,能快速地檢測出圖像中的任意直線。這一點已經(jīng)在個人計算機(jī)上經(jīng)過充分的驗證,并與標(biāo)準(zhǔn)Hough變換方法進(jìn)行了比較。所用的軟硬件環(huán)境如下:

硬件平臺:CPU 為Intel,主頻1 596 MHz, 內(nèi)存為512 MB。

軟件平臺:操作系統(tǒng)為中文Windows XP,算法程序語言是C++,編譯器用Visual C++ 2005。

以上數(shù)據(jù)是經(jīng)10次測試取得平均數(shù)測試結(jié)果,它表明對于普通CPU,改進(jìn)版的Hough變換確實在一定程度上提高了程序運(yùn)行的效率,通過觀察以上數(shù)據(jù),改進(jìn)Hough變換比標(biāo)準(zhǔn)Hough變換快8倍左右。

4 結(jié) 語

通過進(jìn)一步優(yōu)化程序,提高計算機(jī)配置,改進(jìn)Hough變換方法,能快速、準(zhǔn)確地檢測出目標(biāo)直線,這種方法使超大型圖像中直線的實時、精確檢測成為可能。

參考文獻(xiàn)

[1]Lingworth J,Kittler J.A Survey of the Hough Transform[J].CVGIP,1988(44):87-116.

[2]郭強(qiáng),陳桂林,童衛(wèi)旗.基于變換域Hough變換的遙感圖像相干干擾分析[J].光學(xué)精密工程,2001,9(2):121-126.

[3]成丹烈.利用Hough變換在序列圖像中檢測多個運(yùn)動點目標(biāo)[J].光學(xué)精密工程,1996,4(5):100-104.

[4]王紹霖,付永生.Hough變換邊緣提取算法[J].同濟(jì)大學(xué)學(xué)報,1996(2):471-474.

[5]袁捷,胡正儀,王延平.用Hough變換的方法提取圖像拐點[J].武漢大學(xué)學(xué)報,1998(2):85-88.

[6]章毓晉.圖像處理和分析[M].北京:清華大學(xué)出版社,1999.

[7]程洪瑋,孫仲康.利用Hough變換實現(xiàn)目標(biāo)檢測與航跡啟動[J].國防科技大學(xué)學(xué)報,1998,20(4):53-58.

[8]Foresti G,Murino V,Regazzoni C S,et al.Gruoping of Rectilinear Segments by the Labeled Hough Transform[J].CVGIP,1996,58(3):22-42.

[9]Cai Y J,Weng W.Position Control and Product DetectingBased onMachineVisionforGravure PrintingPress [J].Journal of Hunan University:Natural Sciences,2003,30(3):57-59.

[10]Yang Y Y,Deng S X.The Online Use of Image Processing Technology in Detecting Printing Registration Deviation [J].Journal of Applied Sciences,2002,20(4):423-425.

[11]Zhang R Y.Possibility and Deficiency of Automatic Pre-adjusting Inking System[J].Journal of Beijing Institute of Graphic Communication,2000,8(1):58-62.

[12]李凱南.基于Hough變換的指針式儀表的自動判讀.現(xiàn)代電子技術(shù),2006,29(14):18-20.

[13]粱惺彥,和衛(wèi)星.改進(jìn)Hough變換在PCB實時初檢中應(yīng)用.現(xiàn)代電子技術(shù),2004,27(13):8-11.