改進Ｈｏｕｇｈ變換的算法實現

蘇志祁　尉　宇　王　濤

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

關鍵詞:Hough變換;極坐標;標準直線方程,改進的Hough變換

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

1 Hough變換檢測直線的原理

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

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

ρ=xcosα+ysinα(1)

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

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]++;

}

}

}

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

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

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

2 改進Hough變換的算法及實現

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

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

在此提出并實現了一種只用加法和移位運算來實現的Hough變換,這種方法有利于在沒有硬件乘法器的CPU上實現Hough變換。它使用直線方程原始定義y=kx+b。可以看到,y=kx+b所有參數都是線性的,所以不需要乘法,只需要累加就可以。但是這個方法會遇到一個問題,這里的k的范圍是從正無窮到負無窮,解決的辦法是只對原圖進行從-45°~+45°之間的直線檢測,然后將圖像的(x,y)互換,再次對圖像進行從-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是一個宏定義,決定處理的點數,從-45°~+45°有2s_Nbit個點,程序中+700的目的是為了防止數組的下標出現負數。這里使用的循環是 do-while循環,并且使用的是遞減循環,而不是通常的遞加循環。這個結構和匯編語言中的loop語句剛好是同一個結構,如果使用通常的for循環,將會在循環的跳轉語句上浪費掉一些時間。使用遞減循環的好處就是省掉一條cmp語句。下面是這段代碼的反匯編。

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

{

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

}

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

3 測試與驗證

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

硬件平臺:CPU 為Intel,主頻1 596 MHz, 內存為512 MB。

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

以上數據是經10次測試取得平均數測試結果,它表明對于普通CPU,改進版的Hough變換確實在一定程度上提高了程序運行的效率,通過觀察以上數據,改進Hough變換比標準Hough變換快8倍左右。

4 結 語

通過進一步優化程序,提高計算機配置,改進Hough變換方法,能快速、準確地檢測出目標直線,這種方法使超大型圖像中直線的實時、精確檢測成為可能。

參考文獻

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

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

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

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

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

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

[7]程洪瑋,孫仲康.利用Hough變換實現目標檢測與航跡啟動[J].國防科技大學學報,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變換的指針式儀表的自動判讀.現代電子技術,2006,29(14):18-20.

[13]粱惺彥,和衛星.改進Hough變換在PCB實時初檢中應用.現代電子技術,2004,27(13):8-11.