哈夫變換在目標檢測中的應用

劉正鈴 黃小海 劉玉學

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

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

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

本文詳細敘述哈夫變換的基本原理，及在直線檢測中的應用。尤其是對極坐標下直線的標準方程，進行詳細地推導和論述，對哈夫變換的應用進行有益的補充。

1 哈夫變換

1.1 基本哈夫變換原理

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

yi=axi+b （1）

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

b=-xia+yi （2）

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

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

b=-xja+yj （3）

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

y=a'x+b' (4)

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

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

1.2基本哈夫變換檢測直線

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

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

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

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

1.3基本哈夫變換檢測圓

哈夫變換不僅可以用來檢測直線和連接處在同一直線上的點，也可以用來檢測滿足解析式f(x，c)=0形式的各類曲線并把曲線的點連接起來。這里x是1個坐標矢量， 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。可見對圓周的檢測與檢測直線上的點原理相同，只是由于是3個參數(shù)，計算量增加了許多。因此實際中哈夫變換在檢測簡單曲線中更能體現(xiàn)它的優(yōu)越性[5]。

2哈夫變換的改進

2.1哈夫變換的極坐標形式

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

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

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

該直線的極坐標方程的推導過程如下：

如圖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)整理，得原直線方程可轉化為 ρ=xcosθ+ysinθ。

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

ρ=xicosθ+yisinθ (10)

ρ=xjcosθ+yjsinθ （11）

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

2.2改進的哈夫變換檢測直線

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

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

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

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

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

2.3 改進的哈夫變換檢測圓

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

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

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

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

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

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

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

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

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

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

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

4 結束語

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

參考文獻

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

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

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

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

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

作者簡介：

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

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