基于梯度的隨機Ｈｏｕｇｈ快速圓檢測方法

(海軍大連艦艇學院， 遼寧 大連 116018)

摘 要： 針對隨機Hough變換(RHT)在復雜圖像中檢測圓時產生隨機采樣的大量無效累積，提出了一種改進的RHT用于圓檢測，方法利用梯度方向信息來判定是否對采樣到的三點進行參數累積，從而較好地解決了無效累積問題。實驗表明改進后的算法比原算法計算速度快，占用的內存小，檢測性能有較大提高。

關鍵詞： 隨機Hough變換； 圓檢測； 梯度方向信息

中圖法分類號： TP391.4文獻標識碼： A

文章編號： 1001 3695(2006)08 0164 02



Fast Circle Detection Using Randomized Hough Transform Based on Gradient 

WANG Jian， WANG Xiao tong， XU Xiao gang， LI Bo

（Dalian Naval Academy， Dalian Liaoning 116018，China）

Abstract: To solve the problem of a large amount of useless accumulations yielded by random sampling when randomized Hough transform (RHT) is used to detect circles in complex images，an improved RHT is proposed. It uses gradient direction information to determine whether the parameter should be accumulated or not. In comparison with the basic RHT， the problem of useless accumulations is well solved and our method has higher speed，smaller storage and better detection performance.

Key words: Randomized Hough Transform (RHT); Circle Detection; Gradient Directioin Formation

檢測圓在計算機視覺領域有著廣泛的應用前景。Hough變換[1]是檢測圓的有效方法，其主要優點為：它對于圖像中的噪聲點不敏感，用其得到的結果可有效地濾除噪聲的影響，以提高結果的可信度；該變換便于并行計算，計算機視覺領域的一些問題相當復雜，需要很大的計算量，并行計算是提高計算速度的有效方法。但傳統的Hough變換有幾個較大的缺陷：①計算量大，每個邊緣點映射成參數空間的一個曲面(有時可簡化成一條曲線)，是一到多的映射；②占用內存大；③提取的參數受參數空間的量化間隔制約。為了克服上述缺陷，Xu等人[2，3]提出了隨機Hough變換 (Randomized Hough Transform， RHT)，在圖像空間隨機選取不共線的三個點映射成參數空間的一個點，是多到一的映射，從而避免了傳統Hough變換一到多映射的龐大計算量。為了降低內存需求，采用動態鏈表結構，只對多到一映射所得到的參數分配單元進行累積，從而與傳統Hough變換相比，降低了內存需求，同時使RHT具有參數空間無限大、參數精度任意高等優點。盡管RHT只對多到一映射所得到的參數分配單元進行累積，但在處理復雜圖像時，由于隨機采樣仍引入大量的無效單元，從而造成了大量無效累積。為此，本文提出一種改進的RHT用于圓檢測。

1 圓檢測的RHT

用于圓檢測的算法描述如下:設 D為圖像空間的邊緣點集，P 為參數空間的參數單元集，它是一個動態鏈表結構。設參數單元的計數值為score，當參數單元 p_c 的score達到指定閾值N t(它是一個很小的數，如2、3)時， p_c(本文用相同的符號表示參數單元和它對應的參數)對應的圓成為候選圓，判斷圖像空間中落到該候選圓上的點數M_pc，若其大于圓所允許的最小點數 M_min，則確認該候選圓為真實圓，記下該圓并繼續進行下一個圓的檢測。當檢測到的圓已達到規定的數目時，結束檢測過程;若事先不知道圓的個數，則可規定檢測一個圓過程中所允許隨機采樣的最大循環次數 K_max，當采樣次數已大于K_max，而參數單元點集P中仍沒有參數單元的score達到指定的閾值N_t 時，則認為Hough變換已不能檢測到更多的圓而結束。算法的具體步驟如下:

2 圓檢測的改進RHT(RHT₊)

盡管只對多到一映射所得到的參數分配單元進行累積，但在處理復雜圖像時，隨機采樣仍然會引入大量的無效單元，造成大量無效累積。例如，某圖像包含 N 個大小(圓的大小是由圓上的點數來衡量的)為 q 的圓，另外還有 n 個非圓上的點，則隨機采樣所得三點落在同一圓上的概率為

由式(2)可知，當圖像中僅有同樣大小的圓時，隨機采樣三點落在同一圓上的概率與圓數目的平方成反比，圓數目越多，三點落在同一圓上的概率就越小，這意味著產生無效累積的概率就越大。對于僅有五個圓的圖像，其無效采樣的概率為24/252。另外，由式(1)知，非圓上的由式(2)可知，當圖像中僅有同樣大小的圓時，隨機采樣三點落在同一圓上的概率將越小，產生無效累積的概率也就越大。

可以利用梯度方向信息來有效地解決無效累積問題(圖1)。圓O₁和圓O₂是待檢測的兩個圓，d₁，d₂，d₃三點顯然不在同一圓上，但由于隨機采樣，RHT可能會選取這三點，導致需要計算經過這三點的圓參數p(其對應的圓為圖中的圓O₃)并搜索參數單元集P(它是一個動態鏈表)，如果在P中沒有p，還需要在P中插入新的參數單元，這就使得鏈表規模變大。鏈表規模變大，一方面意味著占用了更多的內存，另一方面使得后繼映射過程中搜索鏈表的工作量變大。在理想情況下，邊緣圖中圓上各點梯度所在的直線過圓心。考察d₁，d₂，d₃₁，d₂梯度方向所在的直線過圓心O₁，d₃梯度方向所在的直線過圓心O₂，它們均不過圓O₃，且相差甚遠，因此可以確定圓O₃是虛假圓，這三點不在同一真實圓上。這樣就可省去搜索參數單元集P的工作，另外也不會引入新的參數單元，這既減小了占用的內存，又使鏈表保持在一個較小的規模上，使得后繼映射過程中搜索鏈表的工作量較小。這就是本文要改進RHT算法的基本出發點。

3實驗驗證

進行了大量實驗，典型實驗的合成圖像如圖2(a)所示，用Sobel算子提取邊緣并細化后，結果如圖2(b)所示，RHT和RHT+在50次運行中均能較準確地將規定的六個圓檢測出來，如圖2(c)所示。將50次運行后的結果T，CN_av以及CN_max的值進行平均，作為T，CN_av以及CN_max的值，列于表1。由性能指標之比RHT/RHT₊可知:對于圖2(a)所示的合成圖像，RHT+比RHT計算速度約快八倍，占用內存約為RHT的1/70。

4 結論

本文利用梯度方向信息來判定是否對采樣到的三點進行參數累積，從而較好地解決了無效累積問題。由實驗可以看到，RHT+比RHT計算速度快、占用內存小以及檢測性能好，具有較強的實用性。

參考文獻：

[1]Illingworth J，Kittler J.A Survey of the Hough Transform［J］.ComputVision Graphics Image Process， 1988，44(1):87-116.

[2]Xu L， Oja E. A New Curve Detection Method:Randomized Hough Transform (RHT)［J］. Pattern Recognition Letters，1990，11(5):331-338.

[3]Xu L， Oja E， Kultanen P. Randomized Hough Transform (RHT):Basic Mechanisms，Algorithms， and Computational Complexities［J］.Comput Vision Graphics Image Process:Image Understanding，1993，57(2):131154.

作者簡介：王健(1981-)，男，遼寧遼陽人，碩士研究生，主要研究方向為圖像處理和計算機視覺。

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