利用局部算子檢測峰值的改進Ｈｏｕｇｈ變換算法

摘要：提出了一種改進的峰值檢測算法，將累加器空間視為一幅二維圖像，利用局部算子區增強期望的直線和噪聲對應的峰值之間的差別；利用最小二乘法擬合增強后的累加器空間對應的分布直方圖，得到具有更強魯棒性的閾值來確定期望峰值所在的位置。實驗結果表明，該算法同時具有較高的精度和較強的魯棒性，對先驗知識的需求很低，具有較好的通用性，為自主應用方式奠定了基礎。

關鍵詞：圖像線模式分析；峰值檢測器；Hough變換

中圖分類號：TP391文獻標志碼：A

文章編號：1001-3695(2008)05-1569-04

0引言

Hough變換作為數字圖像處理中識別幾何形狀的基本方法，由于其良好的抗噪聲性能以及對部分遮蓋現象的不敏感，在圖像處理和模式識別等領域得到了廣泛應用[1~3]。其原理是將圖像空間的直線檢測問題轉換為參數累加器空間求最大值問題，累加值最大的單元對應的參數即為所求的直線參數。由于在得到的累加器空間中準確地確定各有效峰值存在困難，Hough變換早期多被用于為圖片分析人員提供輔助信息，罕見成功的自主應用。近年來隨著機器視覺軟硬件技術的進步和對自動機器視覺系統要求的提高，Hough空間中的峰值檢測問題成為制約全自主視覺系統的關鍵因素之一。如何有效、準確地在累加器空間中確定與原始圖像中各直線對應的峰值問題吸引了眾多的研究者。最簡單方法是設定全局閾值，提取出每一個大于該閾值的局部最大值點。如果圖片中存在多條長度相差較大的直線，難以自主地確定全局閾值。不合理的全局閾值會導致虛假直線或漏線的情況。為確定該閾值，通常需要一些先驗知識，如期望直線的最短長度等。上述先驗知識往往只針對特定的場景有效，如同樣的直線當攝像機的焦距發生變化或攝像機的相對位置發生變化時，所獲得圖像中直線的長度也會發生變化，原有的先驗知識就有可能失效。

針對傳統Hough變換算法的缺陷，許多研究者進行了改進。早期的工作主要致力于采用概率采樣方法代替對圖像中所有特征點進行處理來降低計算量，如概率Hough變換[4]、隨機Hough變換算法[5]、分級Hough變換[6，7]、遞歸概率Hough變換[8]等。有關共性的問題即如何確定閾值，沒有被涉及到。

為克服傳統Hough變換不能檢測直線的端點和長度的弱點，針對累加器空間中累加值的分布特點，幾何方法也被提出[9，10]。對于單條直線，該方法在全局最大峰值的兩側分別取累加值不為零的范圍確定直線段的端點，進而得到直線段的長度和參數。其優點是不依賴于峰值檢測的精度，而且計算量很小。但對于存在多條直線的圖像，如何確定一個合適的范圍也沒有給出合理的準則，尤其是直線距離較近的情況下，依然要根據先驗知識來確定，否則很容易出現混淆多條直線的現象。同樣為檢測直線段的端點，一個圖像坐標x或y被添加到參數空間將累加器空間擴展到三維[11]。由于該方法只需要分析某一個坐標不為零的頁面，雖然需要更多的存儲空間，但計算時間并沒有明顯上升。筆者采用貝葉斯概率統計方法來降低噪聲的影響。與傳統Hough變換算法相比，新算法在各種噪聲等級下的表現都有提高。但其中的噪聲模型也需要先驗知識，作者并未說明如果先驗知識不充分，即噪聲模型不準確時，算法的效果會受到多大的影響。而且在噪聲較低的情況改善較小，在噪聲很強的情況下雖然識別的成功率大大提高，但仍難以滿足實際要求，這再次提示對于包含很強噪聲的圖像直接運用Hough變換并非一個好的方案。

為改善Hough變換算法對圖像噪聲的魯棒性，利用像素之間的連接性作為權值的加權累加算法被提出[12~14]，其主要針對符合隨機概率分布的噪聲，在圖像中體現為椒鹽噪聲的形式。筆者認為其實際應用價值受到以下兩點限制：a)光學系統的改進使得圖片的質量較以往大大改善；b)即使是在惡劣天氣等條件下采集的圖像，如果噪聲呈椒鹽噪聲的形式，也可以利用空間濾波器，如中值濾波器等有效地消除。對于加權之后的累加值峰值檢測，仍需要根據先驗知識確定閾值。由于需要考慮連接性，所需要的先驗知識反而有所增加。尤其是如果噪聲不具有椒鹽的形式，意味著由此導致的間斷寬度超過1，那么關于連接性的權值也必須重新定義。

由于實際圖像中除了期望的幾何特性之外還包含其他物體，如自然物體的形狀大多不規則，這類特性大多難以利用簡單的空間濾波器消除，分析這類背景圖像的影響比簡單噪聲的影響更有意義。噪聲，背景中自然物體和人造物體的影響分別進行了分析[15]。正如作者指出的，由于幾乎不可能為千差萬別的各種物體建立準確的模型，采用高斯正態分布來描述。由于累加器空間中期望的峰值呈蝴蝶形分布，一種針對蝴蝶形狀和正態分布曲面的Canny算子被用來從背景中提取出期望的峰值。實驗效果表明了算法的有效性，經人工驗證，在復雜背景條件下對直線的識別率得到提高。該方法的主要問題是Canny算子的設計過程比較復雜，需要指定較多的參數，而且文中沒有說明各自的原則。筆者在驗證時采用了未經慎重選擇的參數，發現該算法的效果大大下降。歸根到底，該方法也需要針對某類對象的先驗知識來作為設計Canny算子的依據。

在各種改進的Hough變換算法中，一個重要的方向是利用累加器空間中峰值的分布情況，得到比參數空間坐標軸分辨率精度高的結果，而不是直接得到的局部最大值。采用的算法包括最小二乘擬合[16]、一維濾波器[17]和魯棒累加核[18]。這些算法的主要問題都是基于峰值確實存在的假設，而不是如何檢測出峰值。對于筆者認為最關鍵的如何確定閾值的問題沒有涉及。針對傳統Hough變換算法不能檢測出直線寬度的缺點，將圖像空間與參數累加器空間結合檢測直線，并實際應用于掃描后的大尺寸工程圖紙[19]中。算法針對工程圖紙中大部分線的方向均垂直，水平或沿45°方向分布的特點，進行了相應的簡化，保證了計算時間的可實現性。并針對工程圖紙中線的粗細代表意義不同的特點，利用線的寬度作為權值進行了加權求和。在選取權值時依賴于所掃描圖紙的特點，其通用性較差。盡管文中特地說明，窗口模板的尺寸也對算法的效果有明顯的影響，但并未說明為何選取當前的尺寸，即針對特定的場合有一定的特殊要求。

1問題描述

通常，在Hough變換中ρ，θ參數被采用描述直線方程[11]：

變換后，[x，y]圖像空間一點對應[θ，ρ]累加器空間中的一條正弦曲線，圖像空間中一條直線上所有點在累加器單元中形成的峰值對應的ρ、θ值即為期望的式(1)中的參數。

在應用Hough變換前，需要進行顏色閾值分割和輪廓提取等預處理操作。為減低噪聲改善圖片質量，還經常采用空間域濾波器。如圖1(a)中的原始圖像，為檢測網球場地中的白線，閾值被設定來區分白色和其他顏色。提取到的白色部分的邊緣如圖1(b)所示。運動服和運動鞋的邊緣在使用Hough變換時，相當于噪聲。但這種噪聲不是由圖像質量所導致，也不能利用空間域濾波器有效地消除。算法若獲得實際應用，必須對這類噪聲具有足夠強的魯棒性。

對圖1(b)直接應用Hough變換得到的累加器空間三維曲面如圖2所示。從中可以清晰地發現三個明顯的峰，對應原始圖像中三塊明顯的直線區域（事實上共有六條直線，即每條白線有兩個邊緣，以下將詳細介紹相互靠近的直線之間的區分）。其他部分的累加值由噪聲導致，其最大幅值與理想期望由噪聲引起的峰值比較接近，難以直接地利用幅值進行區分。觀察各峰值的分布特點，可以發現與對應噪聲的累加值相比，對應期望直線的峰值更孤立，其與周圍區域的累加值差距明顯，這啟發筆者利用能反映其孤立特性的指標檢測出期望的峰值。

2利用局部算子的峰值增強方法

由Hough變換的原理可知，期望的峰值由一系列正弦曲線累加形成，導致在累加器空間該處附近沿其正弦曲線的切線方向分布的累加值變化相對較緩；沿其法線方向分布的累加值變化劇烈，考慮利用這個特征將期望的峰值與噪聲導致的累加峰值之間的差別進一步增強。

式(4)相當于一個算子，其基于累加器空間中的累加值的局部信息，得到新的變量。在期望峰值處，沿切線和法線方向的鄰域內的累加值差別明顯，因此平均法線方向具有明確的意義；對于其他點，計算出的平均法線方向的意義不大。利用各夾角的余弦作為加權系數，對于期望峰值，沿法線方向的劇烈變化得到進一步的加強，對于其他的噪聲點，各個方向的差別無明顯差別，從而對非孤立的峰值增強作用很弱。

將其應用到圖2所示的累加器空間得到的矩陣對應的三維曲面如圖4所示，為顯示清晰起見，所有小于零的值被設置為零?？梢钥吹狡谕逯岛驮肼晫逯抵g的幅值差別被明顯增強。由上述計算過程可以容易地發現，由于鄰域內其他元素的影響，使用該方法雖然有可能改變不同峰值之間的相對大小關系，但不會改變各局部最大值的位置。

3全局閾值確定方法

對比圖2和4可以看出，利用上文介紹的局部算子，已經將期望峰值與噪聲部分的差別明顯增強，對于該圖像可以在更大的范圍內選擇一個閾值，達到確定有效峰值的效果。但即使是同一類型的圖片，由于拍攝角度和場景的不同，有用信號和噪聲之間的比例也會有很大的差別。為使提出的算法具有更強的通用性，還需建立一個通用的算法能夠針對不同的情況選擇正確的閾值。

圖5(a)所示為圖2對應的Hough空間內累加值的統計直方圖；(b)對應采用局部增強算子之后的累加值的統計直方圖，從中可以看到直方圖的形狀發生了改變。圖6的子圖是由另一幅圖片得到的相應直方圖。通過對比可以發現，由不同的圖片直接經過Hough變換得到的直方圖的形狀有很大的差異，但采用局部增強算子后的直方圖具有相似的形狀。這說明采用局部增強算子可以提取出不同圖片中包含的共性信息，得到的直方圖包含更抽象的特征信息，因此利用其確定所需的全局閾值。

觀察圖5（b）和圖6(b)發現，它們具有類似負指數曲線的形狀，存在小幅值的毛刺。進一步采用指數函數來擬合統計直方圖數據的方法來消除可能由噪聲導致的毛刺的影響。典型的指數函數形式為

其中:常數a和b確定函數的具體形式，需要在擬合過程中計算出。在此采用最小二乘法來計算。

通過對式（5）的兩端取自然對數得到

4直線參數確定方法

上章中確定出的每一個峰值所在小區域的等高線如圖9所示。

在圖9各子圖上橫軸為θ軸，縱軸為ρ軸。可以觀察到，在每一個子塊中這些累加值帶都近似平行分布，形成若干累加值帶，帶與帶之間存在間隙，在間隙處的累加值比兩側帶上的累加值都要小，分別對帶上的任一點所在的行和列進行分析，總會存在多個峰值的情況。對每一個子塊，首先找出其內部的最大值，在其所在的行或列中會觀察到明顯的多個峰值，這些多峰必定處于不同的峰值帶上，是否為期望的峰值，還需要進行驗證。定義在局部最大值所在同一行或列中得到的另一個峰值的位置為(θi，ρi)，在(θi，ρi)的八鄰域內進行搜索，如果其是八鄰域內的最大值，則確定其是有效的峰值；如果存在比(θi，ρi)處更大的值，則認為該最大值比對應的參數對比(θi，ρi)處接近有效峰值，重復同樣的搜索過程直到得到其本身是八鄰域內的最大值為止，認定這結果為有效峰值。如果在得到的小區域內存在三條或三條以上的累加值帶，上述方法同樣有效。

利用上述算法提取出的參數對應的直線被用紅顏色疊加在原始圖像上，如圖10所示。在事先并未設定最短期望直線長度的情況下，得到了六個有效的峰值，分別對應三條白線的邊緣。從圖10中可以看到，檢測結果與原始直線的差別與圖像采集設備的量化誤差處于同一級別。該算法應用到類似的網球比賽場景也得到了理想的結果，對于明顯的場地中明顯的白線，雖然原始圖像的分辨率相差很大，直線的長度也相差很大，算法未經任何參數調整都取得了理想的效果，沒有出現漏線和檢測出虛假直線的情況。

5結束語

針對傳統及若干改進Hough變換峰值檢測算法對噪聲魯棒性不強，可能出現漏線和虛假直線，需要人為參與，自主性不強的問題，提出了一種改進的峰值檢測方法。針對分別對應直線和噪聲的峰值在累加器空間中的不同分布特性，采用局部算子對期望的峰值進行增強，并利用指數曲線擬合進一步降低噪聲的影響，從而得到魯棒性更強的閾值。利用實際圖像的測試結果表明，該算法具有較好的魯棒性，未出現漏線和虛假直線。計算過程中需要根據先驗知識指定的量很少，自主性較強。該方法以累加器空間為基礎進行操作，同樣適用于隨機Hough變換，概率Hough變換，分層Hough變換等方法。

參考文獻：

［1］HOUGH P.Methods and means for recognizing complex patterns：US，3069654[P].1962.

[2]DUDA R O，HART P E.Use of Hough transformation to detect lines and curves in pictures[J].Commun ACM，1972，18(2):120－122.

[3]LEAVERS V F.Survey which Hough transform[J].Computer vision， Graphics and Image Processing，1993，58(2):250-264.

[4]KIRYATI N，ELDAR Y，BRUCKSTEIN A M.A probabilistic Hough transform[J].Pattern Recognition，1991，24(4):303-316.

[5]XU L，OJA E，KULTANEN P.A new curve detection method: randomized Hough transform (rht)[J].Pattern Recognition Letters，1990，11(5):331-338.

[6]PRINCE J，ILLINGWORTH J，KITTLER J.A hierarchical approach to line extraction based on the Hough transform[J].Computer Vision， Graphics and Image Processing，1990，52(1): 57－77.

[7]PALMER P L，KITTLER J，PETROU M.Using focus of attention with the Hough transform for accurate line parameter estimation[J].Pattern Recognition，1994，27(9): 1127－1134.

[8]MATAS J，GALAMBOS C，KITTLER J.Robust detection of lines using the progressive probabilistic Hough transform[J].Computer Vision and Image Understanding，2000，78(1): 119－137.

[9]ATIQUZZAMAN M，AKHTAR M W.Complete line segment description using the Hough transform[J].Image Vision Computation，1994，12(5): 267-273.

[10]ATIQUZZAMAN M，AKHTAR M W.A robust Hough transform technique for complete line segment description[J].Real－time Imaging，1995，1(6): 419-426.

[11]CHA J，COFER R H，KOZAITIS S P.Extended Hough transform for linear feature detection[J].Pattern Recognition，2006，39(6): 1034－1043.

[12]LI H，PAO D，JAYAKUMAR R.Improvements and systolic implementation of the Hough transformation for the straight line detection[J].Pattern Recognition，1989，22(6): 697－706.

[13]YUEN S，LAM T，LEUNG N.Connective Hough transform[J].Image and Vision Computing，1993，11(5): 295-301.

[14]YANG M，LEE J，LIEN C，et al.Hough transform modified by line connectivity and line thickness[J].IEEE Trans on Pattern Analysis and Machine Inteligence，1997，19(8): 905-910.

[15]FURUKAWA Y，SHINAGAWA Y.Accurate and robust line segment extraction by analyzing distribution around peaks in Hough space[J].Computer Vision and Image Understanding，2003，92(1):1-25.

[16]NIBLACK W，PETKOVIC D.On improving the accuracy of the Hough transform[J].Machine Vision and Application，1990，2(2): 87－106.

[17]PRICDEN J，ILLINGWORTH J，KITTLER J.Hypothesis testing:a framework for analyzing and optimizing Hough transform performance[C]//Proc of IEEE Trans on Pattern Analysis and Machine Intelligence.Washington DC:IEEE Computer Society，1994:329-341.

[18]PALMER P L，KITTER J，PETROU M.An optimizing line finder using a Hough transform algorithm[J].Computer Vision and Image Understanding，1997，67(1): 1-23.

[19]SONG J，LYU M R.A Hough transform based line recognition method utilizing both parameter space and image space[J].Pattern Recognition，2005，38(4): 539-552.

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