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

劉正鈴 黃小海 劉玉學

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

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

1 哈夫變換

1.1 基本哈夫變換原理

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

yi=axi+b （1）

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

b=-xia+yi （2）

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

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

b=-xja+yj （3）

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

y=a'x+b' (4)

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

由此可知在圖像空間中共線的點對應在參數空間里相交的線。反過來，在參數空間中相交于同1個點的所有直線在圖像空間里都有共線點與之對應。這就是點-線的對偶性。哈夫變換就是將圖像空間xy中的點是否共線的問題轉換為在參數空間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個方程就對應著參數平面上的3條直線，而這3條直線相交于一點（a=1，b=0）。同樣，原圖像上直線y=x上的其它點對應參數平面上的直線也會通過點（a=1，b=0），這一性質提供了解決問題的方法.這就是Hough變換的基本思想.就是把圖像平面上的點對應到參數平面上的線，最后通過統計特性來解決問題.

1.2基本哈夫變換檢測直線

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

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

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

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

1.3基本哈夫變換檢測圓

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

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

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

2哈夫變換的改進

2.1哈夫變換的極坐標形式

使用等式y=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=ax+b，得ρsinθ=－（tanθ)-1ρcosθ+b。從而

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

將式（9）代入直線方程y=ax+b。經整理，得原直線方程可轉化為 ρ=xcosθ+ysinθ。

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

ρ=xicosθ+yisinθ (10)

ρ=xjcosθ+yjsinθ （11）

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

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

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

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

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

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

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

2.3 改進的哈夫變換檢測圓

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

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

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

此變換有以下性質：

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

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

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

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

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

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

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

4 結束語

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

參考文獻

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

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

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

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

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

作者簡介：

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

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