劉正鈴 黃小海 劉玉學(xué)

摘要：本文介紹了Hough變換的原理，說明了Hough變換的點(diǎn)線對偶性。尤其是在極坐標(biāo)變換下對直線和圓的檢測進(jìn)行了深入的研究。

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

中圖分類號:TP131 文獻(xiàn)標(biāo)識碼:A

Researsh on Hough Transformation in Target Detection

Liu Zheng-lingHuang Xiao-haiLiu Yu-xue

（Institute ofMathematics and Information Engineering, Sanming college,Sanming Fujian ,365004)

Abstract： This paper illustrate the principle of the Hough transformation and studies the point-line duality of the Hough transformation. Especially under the polar coordinate transformation,the problem about straigh line and circle's detection is explained deeply.

Key words: Hough transform; image edge; line detection; polar coordinates

引言

哈夫(Hough)變換是利用圖象全局特性而將邊緣象素連接起來組成區(qū)域封閉邊界的1種方法。在預(yù)先知道區(qū)域形狀的條件下，利用哈夫變換可以方便地得到邊界曲線而將不連續(xù)的邊緣象秦點(diǎn)連接起來。Hough變換在計算機(jī)視覺、軍事防御、辦公自動化等領(lǐng)域都得到了普遍的關(guān)注和廣泛的應(yīng)用。Hough變換1962年由Paul Hough提出，并在美國作為專利[1]。它所實(shí)現(xiàn)的是一種從圖像空間到參數(shù)空間的映射關(guān)系。設(shè)在圖像空間有一個目標(biāo)，其輪廓可用代數(shù)方程表示，哈夫變換就是將圖像空間轉(zhuǎn)化為參數(shù)空間的一種變換[2]?；诠蜃儞Q，可利用圖像的全局特性將目標(biāo)邊緣像素連接起來組成目標(biāo)區(qū)域的封閉邊界，或直接對圖像中已知形狀的目標(biāo)進(jìn)行邊緣檢測。哈夫變換的主要優(yōu)點(diǎn)是：具有圖像全局特性，受噪聲和邊界間斷的影響比較小，運(yùn)算量較小，具有較好的魯棒性[3]。但現(xiàn)有文獻(xiàn)對哈夫變換在極坐標(biāo)中的應(yīng)用，存在不同的形式和論述，容易造成概念混淆。

本文詳細(xì)敘述哈夫變換的基本原理，及在直線檢測中的應(yīng)用。尤其是對極坐標(biāo)下直線的標(biāo)準(zhǔn)方程，進(jìn)行詳細(xì)地推導(dǎo)和論述，對哈夫變換的應(yīng)用進(jìn)行有益的補(bǔ)充。

1 哈夫變換

1.1 基本哈夫變換原理

基本哈夫變換的原理可借助如下的點(diǎn)—線對偶性解釋。在圖像空間xy中，考慮一個定點(diǎn)（xi，yi）和經(jīng)過該點(diǎn)的直線斜截式方程：

yi=axi+b （1）

其中a為斜率， b為截距。則通過點(diǎn)（xi，yi）的直線有無數(shù)條，雖對應(yīng)不同的a和b值，但均滿足上述直線方程。現(xiàn)將式(1)改寫為：

b=-xia+yi （2）

式（2）可認(rèn)為代表參數(shù)空間ab中的一條直線方程，如圖1所示。其中： -xi為斜率，yi 為截距。由于（xi，yi）為定點(diǎn)，因此等式(2)可看作參數(shù)空間ab中關(guān)于定點(diǎn)（xi，yi）唯一直線方程。

同理，在參數(shù)空間中，第2個點(diǎn)（xj，yj）也有與之相關(guān)唯一直線方程：

b=-xja+yj （3）

若在參數(shù)平面內(nèi)，式(2)與式(3)所決定的直線相交，如圖1所示。設(shè)交點(diǎn)為（a'，b'），此時將以參數(shù)a'為斜率，參數(shù)為截距。對應(yīng)在圖像空間xy中，就是一條同時經(jīng)過定點(diǎn)（xi，yi）和定點(diǎn)（xj，yj）的直線方程參數(shù)。即有：

y=a'x+b' (4)

則式(4)即為同時經(jīng)過定點(diǎn)（xi，yi）和定點(diǎn)（xj，yj）的直線斜截式方程。

由此可知在圖像空間中共線的點(diǎn)對應(yīng)在參數(shù)空間里相交的線。反過來，在參數(shù)空間中相交于同1個點(diǎn)的所有直線在圖像空間里都有共線點(diǎn)與之對應(yīng)。這就是點(diǎn)-線的對偶性。哈夫變換就是將圖像空間xy中的點(diǎn)是否共線的問題轉(zhuǎn)換為在參數(shù)空間ab中是否相交于共同交點(diǎn)的問題。例如，圖像空間中有直線y=x，取該直線上的3個點(diǎn)：A(0，0)，B(1，1)，C(2，2)，顯而易見，過A點(diǎn)的直線滿足條件b=0；過B點(diǎn)的直線滿足條件1=a+b；過C點(diǎn)的直線滿足條件2=2a+b，這3個方程就對應(yīng)著參數(shù)平面上的3條直線，而這3條直線相交于一點(diǎn)（a=1，b=0）。同樣，原圖像上直線y=x上的其它點(diǎn)對應(yīng)參數(shù)平面上的直線也會通過點(diǎn)（a=1，b=0），這一性質(zhì)提供了解決問題的方法.這就是Hough變換的基本思想.就是把圖像平面上的點(diǎn)對應(yīng)到參數(shù)平面上的線，最后通過統(tǒng)計特性來解決問題.

1.2基本哈夫變換檢測直線

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

（1）對參數(shù)空間中a和b的可能取值范圍進(jìn)行量化，根據(jù)量化結(jié)果構(gòu)造一個二維累加數(shù)組A(a，b)，其中amin≤a≤amax，bmin≤b≤bmax，該二維數(shù)組的初始化為零；

（2）對每個xy空間中的給定點(diǎn)（xi，yi），讓a取定所有可能的值，用式（2）計算出b，根據(jù)a和b的值累加A，參數(shù)點(diǎn)(a，b)每出現(xiàn)一次，該單元累加器A(a，b)=A(a，b)+1，即累加值等于參數(shù)點(diǎn)(a，b)重復(fù)出現(xiàn)的次數(shù)。

（3）根據(jù)累加后A中最大值所對應(yīng)的a和b，就可求出對應(yīng)n個點(diǎn)中最多數(shù)的點(diǎn)所確定的直線[4 ]。

1.3基本哈夫變換檢測圓

哈夫變換不僅可以用來檢測直線和連接處在同一直線上的點(diǎn)，也可以用來檢測滿足解析式f(x，c)=0形式的各類曲線并把曲線的點(diǎn)連接起來。這里x是1個坐標(biāo)矢量， c是系數(shù)矢量。例如圓的一般方程為：

(x-a)2+(y-b)2=r2 (5)

此時式（5）中有3個參數(shù)a，b，r，所以在檢測圓周時，需要在參數(shù)空間里建立一個3維的累加數(shù)組A，其單元可寫為A(a，b，r)，讓a和b的值依次變化而根據(jù)式（5）計算出r，并對A累加：A(a，b，r)=A(a，b，r)+1?？梢妼A周的檢測與檢測直線上的點(diǎn)原理相同，只是由于是3個參數(shù)，計算量增加了許多。因此實(shí)際中哈夫變換在檢測簡單曲線中更能體現(xiàn)它的優(yōu)越性[5]。

2哈夫變換的改進(jìn)

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

使用等式y(tǒng)=ax+b表示一條直線帶來的一個問題是，當(dāng)直線接近豎直方向時將使a和b都接近于無窮而大大增加計算量.解決這一難點(diǎn)的方法是使用直線的極坐標(biāo)方程：

ρ=xcosθ +ysinθ，-π/2≤θ≤π/2 （6）

如圖2所示ρ表示原點(diǎn)到直線的垂直距離， θ表示該垂線與x軸正向的夾角。

該直線的極坐標(biāo)方程的推導(dǎo)過程如下：

如圖2所示。則有下式成立：

a=tanα＝－（tanθ)-1 (7)

x0=ρcosθ，y0=ρsinθ (8)

將（7），（8）兩式帶入等式y(tǒng)=ax+b，得ρsinθ=－（tanθ)-1ρcosθ+b。從而

b=ρsinθ+（tanθ)-1ρcosθ。 (9)

將式（9）代入直線方程y=ax+b。經(jīng)整理，得原直線方程可轉(zhuǎn)化為 ρ=xcosθ+ysinθ。

圖3是過點(diǎn)（xi，yi）和點(diǎn)（xj，yj）的直線，在參數(shù)空間θρ中，經(jīng)過定點(diǎn)（xi，yi）、（xj，yj）的唯一參數(shù)方程分別為：

ρ=xicosθ+yisinθ (10)

ρ=xjcosθ+yjsinθ （11）

式（10）、（11）分別對應(yīng)參數(shù)空間θρ中的一條正弦曲線。這樣圖像空間xy中的點(diǎn)對應(yīng)于新參數(shù)空間θρ中的一條正弦曲線。則將直線上的所有特征點(diǎn)都進(jìn)行這種映射后，參數(shù)空間中就會出現(xiàn)很多正弦曲線，所有這些正弦曲線都經(jīng)過過參數(shù)空間的定點(diǎn)（θ'，ρ'）。因此檢測在圖像空間中共線的點(diǎn)轉(zhuǎn)化為在參數(shù)空間θρ里檢測正弦曲線的交點(diǎn)。

2.2改進(jìn)的哈夫變換檢測直線

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

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

(2)對xy空間中的給定點(diǎn)（xi，yi）其中1≤i≤n，讓θ取遍所有可能的值，根據(jù)式(5)計算出ρ，注意需對θ和ρ的結(jié)果進(jìn)行取整操作。參數(shù)點(diǎn)（θ，ρ）每出現(xiàn)一次，該單元累加器A[θ，ρ]=A[θ，ρ]+1，即累加值等于參數(shù)點(diǎn)（θ，ρ）重復(fù)出現(xiàn)的次數(shù)。

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

為了能夠調(diào)整精確度，可以對計算的尺度進(jìn)行不同的設(shè)定。例如，將參數(shù)空間的θ軸[θmin，θmax]劃分為K份，那么對應(yīng)于每個定點(diǎn)（xi，yi），有K個 θ值對應(yīng)K個ρ值。K值越大，則計算出的共線性越粗略；K值越小，則計算出的共線性越精細(xì)，甚至可以達(dá)到亞像素級。因此在參數(shù)空間θρ的尺度劃分，決定了計算出的共線點(diǎn)的精確度。在計算量上，每個點(diǎn)需進(jìn)行K次計算，總共n個點(diǎn)，因此需要nK次計算。實(shí)際中K小于n，因此計算量小于n2?？梢姽蜃儞Q有明顯的計算優(yōu)越性。

2.3 改進(jìn)的哈夫變換檢測圓

圓的哈夫變換可用下列參數(shù)方程表示：

(x-ρcosθ)2+(y-ρsinθ)2=r2 （12）

其中r為半徑， ρ為圓心距原點(diǎn)長度， θ為圓心和原點(diǎn)連線與 軸的夾角θ。

此變換有以下性質(zhì)：

(1) （x，y）域中一點(diǎn)對應(yīng)于（ρ，θ，r）變換域中一個面。

(2) （ρ，θ，r）變換域中一點(diǎn)對應(yīng)于（x，y）域中一個圓。

(3) （x，y）域中一圓上的n個點(diǎn)對應(yīng)于（ρ，θ，r）變換域中經(jīng)過一公共點(diǎn)的n個面。一個圓只有一個圓心和半徑，當(dāng)n足夠大時，在（ρ，θ，r）變換域中不存在也不可能有第二個公共點(diǎn)。

(4) （ρ，θ，r）變換域中一面上的n點(diǎn)對應(yīng)于（x，y）域中經(jīng)過一公共點(diǎn)的n個圓。

圓的檢測跟直線的檢測相似，但因?yàn)閳A的Hough變換參數(shù)方程有三個參數(shù)：ρ，θ，r，從而在分小單元時得將三個參數(shù)分段，構(gòu)成一個小單元（□ρ， □θ，□r），在每小單元設(shè)一累加器，然后對圖像中每一有效點(diǎn)進(jìn)行變換。待圖像中全部有效點(diǎn)都變換完成后，對各小單元進(jìn)行檢測。找出公共點(diǎn)，并將其代入方程：

(x-ρcosθi)2+(y-ρsinθi)2=ri2 （13）

從而得出逼近的圓的方程。

4 結(jié)束語

本文研究了Hough變換在直線和圓檢測中的應(yīng)用，并將他推廣應(yīng)用到一般曲線的檢測，事實(shí)上，對于檢測任意已知表達(dá)形式的曲線，累加器的維數(shù)實(shí)關(guān)鍵，因?yàn)殡S著累加器的維數(shù)增加，計算量會大幅增加，如何通過降維的思想設(shè)立累加器以及在極坐標(biāo)下對一般曲線的檢測，還有待近一步研究。

參考文獻(xiàn)

[1]王仁康. 圖象工程 上冊:圖象處理和分析[M].北京：清華大學(xué)出版社，2005.187-182

[2]岡薩雷斯.數(shù)字圖像處理[M].北京:電子工業(yè)出版社,2003.474-479

[3]章毓晉.圖像分析[M].北京:清華大學(xué)出版社,2005.140-150

[4]邱力為,宋子善. 直線參數(shù)檢測的快速哈夫變換[J]. 北京航空航天大學(xué)學(xué)報,2003,(8)

[5]王菁菁,范影樂. 基于Hough變換的圓檢測技術(shù)[J]. 杭州電子科技大學(xué)學(xué)報,2005,(4)

作者簡介：

劉正鈴(Liu Zheng-ling)(1987-)，男，漢族，福建寧德人，單位：三明學(xué)院數(shù)學(xué)與信息工程學(xué)院學(xué)生。

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