基于哈夫變換的圖像邊緣連接

2008-04-12 00:00:00董梁

現代電子技術 2008年18期

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

關鍵詞：圖像邊緣；哈夫變換；直線檢測；極坐標

中圖分類號：TP301 文獻標識碼：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)變換是一種特殊的在不同空間之間進行的變換。設在圖像空間有一個目標，其輪廓可用代數方程表示，哈夫變換就是將圖像空間轉化為參數空間的一種變換。基于哈夫變換，可利用圖像的全局特性將目標邊緣像素連接起來組成目標區域的封閉邊界，或直接對圖像中已知形狀的目標進行邊緣檢測。哈夫變換的主要優點是：具有圖像全局特性，受噪聲和邊界間斷的影響比較小，運算量較小，具有較好的魯棒性。

2 哈夫變換的基本原理

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

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

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

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

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

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

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

3 哈夫變換的極坐標形式

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

在圖像空間xy中，經過定點(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)，經整理可得：ρ0=ysin θ0+xcos θ0(10)

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

極坐標下的直線標準方程，經過哈夫變換可得：

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

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

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

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

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

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

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

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

二維累計數組的最大值對應n個定點中最多的點所確定的直線，根據累加單元坐標值θ和ρ值，即可得到該直線的標準方程。

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

圖2 極坐標中的直線方程圖3 參數空間θρ的劃分

5 結語

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

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

參考文獻

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

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

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

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

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

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

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