級聯Hough變換直線特征提取方法

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

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

0 引言

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

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

1 標準Hough變換

1.1 Hough變換基本原理

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

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

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

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

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

1.2 標準Hough變換

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

圖2 標準Hough變換

2 級聯Hough變換

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

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

由圖4～圖6可見，級聯Hough變換從頂層Hough變換到底層Hough變換時一個逐步縮小搜索域同時提高參數空間分辨率即提高直線參數的解精度的過程。可以預見，當級聯Hough變換達到與標準Hough變換相同的解精度且N為2時，前者的計算效率將比后者提高近50%。

圖3 三層級聯Hough變換結構

圖4 頂層Hough變換

圖5 中層Hough變換

圖6 底層Hough變換

3 實驗結果與分析

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

圖7 原始二值圖像

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

圖8 實驗結果

4 結論

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

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

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

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

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

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

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

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

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