滿(mǎn)增光，邵 燁，武 星，劉軍軍

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

0 引言

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

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

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

1.1 Hough變換基本原理

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

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

圖1 圖像空間中的直線(xiàn)表示

對(duì)于屬于直線(xiàn)l上的點(diǎn)Pi(xi,yi)，i∈(0,N)，N為直線(xiàn)l上點(diǎn)的個(gè)數(shù)，都滿(mǎn)足式，即：

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

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

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

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

2 級(jí)聯(lián)Hough變換

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

如圖3所示是一個(gè)由頂層、中層和底層三層Hough變換構(gòu)成的級(jí)聯(lián)Hough變換。在頂層Hough變換中，參數(shù)空間搜索域?yàn)槿克阉饔颍瑓?shù)空間分辨率為和如圖4所示。假設(shè)在頂層Hough變換中，得到的直線(xiàn)參數(shù)解為以此為中間值，確定中層Hough變換的參數(shù)空間搜索域?yàn)槿鐖D5所示，在中層Hough變換中，以分辨率執(zhí)行Hough變換，其中N為一自定義正整數(shù)，得到直線(xiàn)參數(shù)解為最后，如圖6所示，在底層Hough變換中，以為中間值，確定底層Hough變換的參數(shù)空間搜索域?yàn)樵僖苑直媛蕡?zhí)行Hough變換，得到直線(xiàn)參數(shù)的最終精確解為

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

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

圖4 頂層Hough變換

圖5 中層Hough變換

圖6 底層Hough變換

3 實(shí)驗(yàn)結(jié)果與分析

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

圖7 原始二值圖像

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

圖8 實(shí)驗(yàn)結(jié)果

4 結(jié)論

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

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

[2]白中浩,周培義,王飛虎.基于視覺(jué)的車(chē)位線(xiàn)識(shí)別算法[J].中國(guó)機(jī)械工程,2014,(20)：2825-2829.

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

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

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

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

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

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