摘 要：圖像邊緣的檢測可以得到圖像中處于邊緣上的像素點，由于受到噪聲等干擾，一組邊緣像素很少能完整地描繪一條邊緣。利用哈夫(Hough)變換可以將邊緣像素連接成有意義的邊緣?，F(xiàn)有文獻對哈夫變換在極坐標(biāo)中的應(yīng)用，存在不同的形式和論述，容易造成概念混淆。詳細敘述哈夫變換的基本原理，及在直線檢測中的應(yīng)用。尤其是對極坐標(biāo)下直線的標(biāo)準(zhǔn)方程，進行詳細地推導(dǎo)和論述，從而對哈夫變換的應(yīng)用進行有益的補充。

關(guān)鍵詞：圖像邊緣；哈夫變換；直線檢測；極坐標(biāo)

中圖分類號：TP301 文獻標(biāo)識碼：B 文章編號：1004373X(2008)1814902

Image Edge Linking Based on Hough Transform

DONG Liang

(Xi′an Institute of Post Telecommunications，Xi′an，710121，China)

Abstract：The image edge detection should yield pixels lying only on edges.In practice，the resulting pixels seldom characterize an edge completely because of noise and other effects that introduce spurious intensity discontinuities.Using Hough transform can assemble edge pixels into meaningful edges.This paper discusses the principle of Hough transform，and application in line detection in a detail.Especially，the paper introduces line standard form in polar coordinates.

Keywords：image edge;Hough transform;line detection;polar coordinates

1 引 言

哈夫(Hough)變換是一種特殊的在不同空間之間進行的變換。設(shè)在圖像空間有一個目標(biāo)，其輪廓可用代數(shù)方程表示，哈夫變換就是將圖像空間轉(zhuǎn)化為參數(shù)空間的一種變換。基于哈夫變換，可利用圖像的全局特性將目標(biāo)邊緣像素連接起來組成目標(biāo)區(qū)域的封閉邊界，或直接對圖像中已知形狀的目標(biāo)進行邊緣檢測。哈夫變換的主要優(yōu)點是：具有圖像全局特性，受噪聲和邊界間斷的影響比較小，運算量較小，具有較好的魯棒性。

2 哈夫變換的基本原理

在圖像空間xy中，考慮一個定點(xi，yi)和經(jīng)過該點的直線方程：yi=axi+b(1)其中：a為斜率，b為截距。則經(jīng)過點(xi，yi)的直線有無數(shù)條，雖對應(yīng)不同的a 和b值，但均滿足上述直線方程?，F(xiàn)將式(1)改寫為：b=-xia+yi(2)

從式(2)可看作以參數(shù)a，b為變量，在參數(shù)空間ab中的一條直線方程，如圖1所示。其中：-xi為斜率，yi為截距。由于(xi，yi)為定點，因此式(2)可看作參數(shù)空間ab中關(guān)于定點(xi，yi)惟一直線方程。

圖1xy平面和參數(shù)平面同理，在圖像空間xy中，過另一定點(xj，yj)的直線方程：yj=axj+b(3)

則在參數(shù)空間ab中，關(guān)于定點(xj，yj)惟一直線方程為：b=-xja+yj(4)

若在參數(shù)平面內(nèi)，式(2)與式(4)所決定的直線相交，如圖1所示。設(shè)交點為(a′，b′)，此時參數(shù)a′，b′對應(yīng)在圖像空間xy中，一條同時經(jīng)過定點(xi，yi)和定點(xj，yj)的直線方程參數(shù)。即有：y=a′x+b′(5)

則式(5)即為同時經(jīng)過定點(xi，yi)和定點(xj，yj)的直線方程。

哈夫變換就是將圖像空間xy中點是否共線的檢測，轉(zhuǎn)換為參數(shù)空間ab中是否有共同交點的問題。例如：在圖像空間xy中，現(xiàn)有5個定點，需要檢測這5個點中有哪幾個點共線問題。哈夫變換的做法是：對這5個點，在參數(shù)空間ab中，對應(yīng)5條直線參數(shù)方程，若有2條直線參數(shù)方程相交，則交點即為關(guān)于2個定點的直線參數(shù)，即該兩定點共線；若有3條直線參數(shù)方程相交于一點，則交點即為關(guān)于3個定點的直線參數(shù)，即3定點共線；依次類推，若有5條直線參數(shù)方程相交于一點，則全部5點共線。已知直線方程求交點，這在計算量上是可行的。

3 哈夫變換的極坐標(biāo)形式

使用等式y(tǒng)=ax+b表示一條直線帶來的一個問題是：當(dāng)直線接近垂直時，直線的斜率接近無限大。在參數(shù)平面ab中很難將這個參數(shù)點表示出來。解決這一難點的方法是使用直線的極坐標(biāo)方程。

在圖像空間xy中，經(jīng)過定點(x0，y0)的直線方程為：y-y0=k(x-x0)(6)其中：(x0，y0)為原點到該直線的垂足；k為該直線的斜率，a為該直線與x軸正向的夾角，a ∈\\，如圖2所示。則有下式成立：x0=ρ0cos θ0(7)

y0=ρ0sin θ0(8)

k=tg a=-(tg θ0)-1(9)

將式(7)、式(8)、式(9)代入式(6)，經(jīng)整理可得：ρ0=ysin θ0+xcos θ0(10)

則式(10)即為極坐標(biāo)下直線的標(biāo)準(zhǔn)方程。其中ρ0，θ0為直線方程的參數(shù)，其分別表示原點到直線的垂線長度和垂線與x軸正向的夾角，θ0 ∈\\，ρ0可取正負值。正值表示直線與極軸相交于原點的右邊，負值表示直線與極軸相交于原點的左邊。

極坐標(biāo)下的直線標(biāo)準(zhǔn)方程，經(jīng)過哈夫變換可得：

在參數(shù)空間θρ中，經(jīng)過定點(xi，yi)的惟一參數(shù)方程為：ρ=yisin θ+xicos θ(11)

式(11)對應(yīng)參數(shù)空間θρ中的一條正弦曲線。式(11)還可以進一步表示為：ρ=x2i+y2isin(θ+φ)(12)其中，φ=arctgxiyi。

4 哈夫變換的直線檢測步驟

設(shè)已知圖像空間xy中，存在n個定點，利用哈夫變換檢測這n個定點是否共線的具體步驟如下：

(1) 對參數(shù)空間中參數(shù)θ和ρ的取值范圍進行量化，θ通常取值\\，ρ通常取值\\，N為圖像長度。然后根據(jù)量化結(jié)果構(gòu)造一個二維數(shù)組A\\，其中θmin≤θ≤θmax，ρmin≤ρ≤ρmax，該二維數(shù)組初始化值均為零。

(2) 對xy空間中的給定點(xi，yi)其中1≤i≤n，讓θ取遍所有可能的值，根據(jù)式(11)計算出ρ，注意需對θ和ρ的結(jié)果進行取整操作。

(3) 對于計算出相同的(θ，ρ)參數(shù)點，每出現(xiàn)1次，該單元累積器A(θ，ρ)=A(θ，ρ)+1，即累加值等于重復(fù)出現(xiàn)的次數(shù)。

(4) 根據(jù)計算最后所得結(jié)果，二維數(shù)組累積器A(θ，ρ)中的最大值，對應(yīng)n個定點中最多數(shù)的點所確定的直線。

二維累計數(shù)組的最大值對應(yīng)n個定點中最多的點所確定的直線，根據(jù)累加單元坐標(biāo)值θ和ρ值，即可得到該直線的標(biāo)準(zhǔn)方程。

為了能夠調(diào)整精確度，可以對計算的尺度進行不同的設(shè)定，如圖3所示。例如，將參數(shù)空間的θ軸\\劃分為K份，那么對應(yīng)于每個定點(xi，yi)，有K個θ值對應(yīng)K個ρ值。K值越大，則計算出的共線性越粗略；K值越小，則計算出的共線性越精細，甚至可以達到亞像素級。因此在參數(shù)空間θρ的尺度劃分，決定了計算出的共線點的精確度。在計算量上，每個點需進行K次計算，總共n個點，因此需要nK次計算。實際中K小于n，因此計算量小于n2。

圖2 極坐標(biāo)中的直線方程 圖3 參數(shù)空間θρ的劃分

5 結(jié) 語

哈夫變換不僅適用于直線，而且也適用于表達式為f(x，c)=0形式的各類曲線，這里x是一個坐標(biāo)矢量，c是一個參數(shù)矢量。例如圓的一般方程為：(x-a)2+(y-b)2=r2(13)

式(13)中a，b，r 均為參數(shù)，因此需要在參數(shù)空間構(gòu)造一個3維數(shù)組A，記為A(a，b，r)。對圓的檢測方法與直線類似，由于是3個參數(shù)，計算量增大了許多。因此實際中哈夫變換最適合于檢測比較簡單曲線(即表達式中的參數(shù)比較少)上的點。

參 考 文 獻

［1］岡薩雷斯.數(shù)字圖像處理\\.北京:電子工業(yè)出版社，2003.

［2］章毓晉.圖像分析\\.北京:清華大學(xué)出版社，2005.

［3］邱力為，宋子善，沈為群.直線參數(shù)檢測的快速哈夫變換\\.北京航空航天大學(xué)學(xué)報，2003，29(8):741744.

［4］楊四海，陳鍛生，謝維波.Hough變換的特性分析:一種全局觀點\\.計算機輔助設(shè)計與圖形學(xué)學(xué)報，2006，18(8):1 1971 204.

［5］廖劍利.基于小波變換的圖像邊緣檢測方法研究\\.長沙:湖南大學(xué)，2005.

［6］章毓晉.圖像分割\\.北京:科學(xué)出版社，2001.

［7］朱志剛.數(shù)字圖像處理\\.北京:電子工業(yè)出版社，2002.

［8］徐勝男.基于離散小波框架變換的彩色多聚集圖像融合算法\\.計算機應(yīng)用，2005，25(3):580582.

［9］夏明革，何友，蘇峰.基于多小波分析的圖像融合算法\\.電光與控制，2005，12(2):1921，30.

［10］李世雄.小波變換及其應(yīng)用\\.北京:高等教育出版社，1997.

作者簡介 董 梁 男，1977年出生，助教，碩士。主要研究方向為圖像處理與模式識別。

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文