改進(jìn)Ｈｏｕｇｈ變換的算法實(shí)現(xiàn)

蘇志祁　尉　宇　王　濤

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

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

中圖分類(lèi)號(hào):TP311文獻(xiàn)標(biāo)識(shí)碼:A

文章編號(hào):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)行直線檢測(cè),是圖像分析和計(jì)算機(jī)視覺(jué)的一個(gè)重要內(nèi)容[6]。但是Hough變換的計(jì)算量往往非常大,從而阻礙了其在快速、精確檢測(cè)直線方面的應(yīng)用。這里提出的新方法,不僅能大幅度減少Hough變換的總計(jì)算量,而且在像素允許的情況下,直線斜率的檢測(cè)精度保持最高,這對(duì)于超大型圖像中直線的實(shí)時(shí)、精確檢測(cè),具有重要的實(shí)用價(jià)值[7]。

1 Hough變換檢測(cè)直線的原理

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

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

ρ=xcosα+ysinα(1)

式中:ρ為極徑;α為極角,取0°~180°;x為像素點(diǎn)相對(duì)圖像原點(diǎn)的行坐標(biāo);y為像素點(diǎn)相對(duì)圖像原點(diǎn)的列坐標(biāo)。為了檢測(cè)出直角坐標(biāo)系中,由非零點(diǎn)所構(gòu)成的直線,需要根據(jù)檢測(cè)分辨率的要求,將ρ離散化為Nα個(gè)參數(shù)區(qū)間,將ρ離散化為Nρ個(gè)參數(shù)區(qū)間,也就是說(shuō)將極坐標(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)的目的是對(duì)整個(gè)圖像進(jìn)行一次遍歷,如果在(i,j)存在有效點(diǎn),即if(im.m[j][i]==feature_point),則利用參數(shù)(i,j)在參數(shù)空間中畫(huà)一條正弦曲線。這條正弦曲線的方程就是ρ=xcosθ+ysinθ。由于程序中數(shù)組的下標(biāo)不能為負(fù)數(shù),所以必須進(jìn)行一次平移,也就是加上可能的負(fù)數(shù)的最大值rmax,之后就是使用一個(gè)for循環(huán),讓角度從0°~180°進(jìn)行掃描,使處于正弦線上的位置全部進(jìn)行累加,即Hough_ima.m[nr][angle]++。

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

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

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

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

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

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

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

在VS 2005中,右鍵單擊核心語(yǔ)句,選擇運(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)過(guò)優(yōu)化,循環(huán)體本身幾乎不消耗語(yǔ)句,循環(huán)變量k也被優(yōu)化掉了,所以這是一段性能還算比較理想的代碼。由于外層循環(huán)多一條語(yǔ)句少一條語(yǔ)句對(duì)整體性能幾乎沒(méi)有影響,所以本文并沒(méi)有在外層循環(huán)使用do-while遞減循環(huán)。

3 測(cè)試與驗(yàn)證

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

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

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

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

4 結(jié) 語(yǔ)

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

參考文獻(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變換在序列圖像中檢測(cè)多個(gè)運(yùn)動(dòng)點(diǎn)目標(biāo)[J].光學(xué)精密工程,1996,4(5):100-104.

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

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

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

[7]程洪瑋,孫仲康.利用Hough變換實(shí)現(xiàn)目標(biāo)檢測(cè)與航跡啟動(dòng)[J].國(guó)防科技大學(xué)學(xué)報(bào),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變換的指針式儀表的自動(dòng)判讀.現(xiàn)代電子技術(shù),2006,29(14):18-20.

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