級聯(lián)Hough變換直線特征提取方法

滿增光，邵 燁，武 星，劉軍軍

（1.常熟理工學(xué)院 機(jī)械工程學(xué)院，常熟 215500；2.南京航空航天大學(xué) 機(jī)電學(xué)院，南京 210016）

0 引言

Hough變換是Paul Hough在1962年為了在二值圖像中檢測直線而引入的一種有效方法，其將在圖像空間中檢測直線問題轉(zhuǎn)換為在參數(shù)空間中搜索局部極值問題，從而使直線檢測得到極大簡化。Hough變換在機(jī)器視覺領(lǐng)域有著極為廣泛和重要的應(yīng)用，如用于車道線、車位線檢測[1,2]、車牌校正定位[3,4]、電路板線路檢測[5,6]等。Hough變換具有較強(qiáng)的抗干擾能力，不僅可以檢測直線，還可以檢測圓、橢圓[7,8]等圖形。

Hough變換的優(yōu)點在于，它是一種全局檢測算法，不需要給定直線參數(shù)的初值，對構(gòu)成直線的點集沒任何要求，可以是致密的，也可以是稀疏的，每一個構(gòu)成點都同等對待，具有很強(qiáng)的抗干擾能力。然而，也正因為標(biāo)準(zhǔn)Hough變換所具有的全局算法特性，搜索的參數(shù)空間過于全面，導(dǎo)致其為了獲得精確的直線參數(shù)，必須提高參數(shù)空間的分辨率，從而降低了標(biāo)準(zhǔn)Hough變換的計算效率。因此，為了有效提高標(biāo)準(zhǔn)Hough變換的計算效率，本文提出一種級聯(lián)Hough變換直線檢測方法。

1 標(biāo)準(zhǔn)Hough變換

1.1 Hough變換基本原理

如圖1所示，圖像空間中的一條直線l可以表示為：

其中，ρ為原點到直線l的距離；θ為通過坐標(biāo)原點做直線l的垂線，該垂線與x軸正方向的夾角。

圖1 圖像空間中的直線表示

對于屬于直線l上的點Pi(xi,yi)，i∈(0,N)，N為直線l上點的個數(shù)，都滿足式，即：

在參數(shù)空間中，xi和yi為常數(shù)，θ和ρ為變量，上式便表示為一條曲線。因此，圖像空間中直線l的參數(shù)便對應(yīng)于參數(shù)空間中多條曲線的交點。

1.2 標(biāo)準(zhǔn)Hough變換

標(biāo)準(zhǔn)Hough變換利用上述原理，將連續(xù)的θ和ρ分別以進(jìn)行離散化，如圖2所示。在離散的參數(shù)空間即空間中，將求取多條曲線的交點問題轉(zhuǎn)換為采用投票方式，搜索局部極大值的問題，即在定義域所確定的范圍內(nèi)搜索問題的解，其中為圖像空間中可能存在的直線參數(shù)ρ的最大值。因此，解的精度與參數(shù)空間的離散化程度有關(guān)，越小，獲得的解的精度越高，同時計算量也越大，計算效率越低。

圖2 標(biāo)準(zhǔn)Hough變換

2 級聯(lián)Hough變換

希望獲得高精度的解是標(biāo)準(zhǔn)Hough變換計算量大的原因之一。事實上，標(biāo)準(zhǔn)Hough變換將更多的計算浪費在不存在解的空間中。鑒于此，本文提出一種級聯(lián)Hough變換，采用多級Hough變換串聯(lián)的策略。多級Hough變換構(gòu)成一個由頂層Hough變換到底層Hough變換的結(jié)構(gòu)，頂層Hough變換搜索參數(shù)空間范圍大，分辨率低，而底層Hough變換搜索參數(shù)空間范圍小，分辨率高，從而解決標(biāo)準(zhǔn)Hough變換計算效率低的問題。

如圖3所示是一個由頂層、中層和底層三層Hough變換構(gòu)成的級聯(lián)Hough變換。在頂層Hough變換中，參數(shù)空間搜索域為全部搜索域，參數(shù)空間分辨率為和如圖4所示。假設(shè)在頂層Hough變換中，得到的直線參數(shù)解為以此為中間值，確定中層Hough變換的參數(shù)空間搜索域為如圖5所示，在中層Hough變換中，以分辨率執(zhí)行Hough變換，其中N為一自定義正整數(shù)，得到直線參數(shù)解為最后，如圖6所示，在底層Hough變換中，以為中間值，確定底層Hough變換的參數(shù)空間搜索域為再以分辨率執(zhí)行Hough變換，得到直線參數(shù)的最終精確解為

由圖4～圖6可見，級聯(lián)Hough變換從頂層Hough變換到底層Hough變換時一個逐步縮小搜索域同時提高參數(shù)空間分辨率即提高直線參數(shù)的解精度的過程?？梢灶A(yù)見，當(dāng)級聯(lián)Hough變換達(dá)到與標(biāo)準(zhǔn)Hough變換相同的解精度且N為2時，前者的計算效率將比后者提高近50%。

圖3 三層級聯(lián)Hough變換結(jié)構(gòu)

圖4 頂層Hough變換

圖5 中層Hough變換

圖6 底層Hough變換

3 實驗結(jié)果與分析

為了驗證本文方法的性能，在配置為Win732位，CPU2.3GHz，內(nèi)存3G的電腦上，用C++和OpenCV實現(xiàn)了本文所提方法，并與OpenCV中自帶的標(biāo)準(zhǔn)Hough變換方法進(jìn)行對比。標(biāo)準(zhǔn)Hough變換方法中個像素；本文方法中即N=2，采用二級Hough變換，個像素。圖7所示為原始二值圖像，其像素大小為500×500，圖中共計11條直線，若不重復(fù)計算點值為1的像素共5500個。

圖7 原始二值圖像

如圖8(a)和(b)所示，分別為標(biāo)準(zhǔn)Hough變換和本文方法處理后得到的直線特征提取結(jié)果。從圖中可以看出標(biāo)準(zhǔn)Hough變換與本文方法所提取的直線幾乎沒有差別，但是計算所需時間卻相差很大，前者所需時間為29ms，而后者所需時間為17ms。通過與標(biāo)準(zhǔn)Hough變換方法對比可知，本文方法在得到相同結(jié)果的前提下，計算效率提高近50%。如果采用三級級聯(lián)Hough變換，進(jìn)一步降低頂層Hough變換的角度分辨率，可預(yù)知計算效率會也會進(jìn)一步提高。

圖8 實驗結(jié)果

4 結(jié)論

針對標(biāo)準(zhǔn)Hough變換在提取直線特征時效率低的問題，提出一種級聯(lián)Hough變換，其由多層Hough變換級聯(lián)構(gòu)成。由頂層至底層Hough變換搜索域逐漸縮小，參數(shù)空間分辨率逐漸提高。實驗結(jié)果表明，本文方法計算效率比標(biāo)準(zhǔn)Hough變換提高至少近50%。

[1]陳功醇,賈志絢.基于視覺傳感器的車道檢測算法[J].傳感器與微系統(tǒng),2014,(11)：125-128.

[2]白中浩,周培義,王飛虎.基于視覺的車位線識別算法[J].中國機(jī)械工程,2014,(20)：2825-2829.

[3]王少偉,尚媛園,丁輝,等.一種改進(jìn)的RGB Hough車牌校正定位算法[J].光學(xué)技術(shù),2014,(1)：35-39.

[4]于明,李延果,于洋,等.融合Hough與Radon變換的車牌傾斜校正算法[J].控制工程,2013,(6)：1014-1017.

[5]喬鬧生,孫萍.印制電路板線路檢測研究[J].光子學(xué)報,2013,(11)：1355-1359.

[6]魏鋒,王小林,婁元靜.基于圖像處理技術(shù)的印刷電路板圓孔檢測方法[J].河南理工大學(xué)學(xué)報(自然科學(xué)版),2013,(1)：69-72.

[7]李保章,崔彥平.視覺測量中橢圓特征亞像素提取方法的研究[J].機(jī)械設(shè)計與制造,2011,(8)：142-144.

[8]于海濱,劉濟(jì)林.基于中心提取的RHT在橢圓檢測中的應(yīng)用[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報,2007,(9)：1107-1113.