一種基于梯度Hough變換的同心圓檢測新方法

陳 星（廈門大學自動化系，福建 廈門 361005）

一些常見的平面規則圖形，如直線、圓形、橢圓形、三角形、正方形等在工業產品檢測、生物信息提取、集成電路板在線質量檢測、交通標志識別等領域等有著廣泛的應用[1]。對于直線、圓形等檢測問題，已經提出了大量實用的檢測方法，但對于同心圓檢測問題，目前沒有專門的檢測算法，部分學者在這一方面做了一定的研究，如文獻[2]提出的基于弦中點Hough變換的同心圓檢測方法，這種方法雖然能比較好地檢測出同心圓，但每次都要重復遍歷邊緣特征點找到弦中點，當圖中同心圓每增加一個，算法復雜度會劇烈增大，這樣就不利于對存在很多同心圓的圖像進行檢測。文獻[3]給出了一種同心圓檢測中的區域劃分算法，在圓心已知情況下用最小二乘法擬合圓，但沒有給出具體的圓心計算方法，且僅適合于固定區域劃分層次。

目前，有許多檢測圓的算法，Hough變換是檢測圓的一種常用方法，由Paul Hough在1962年提出[4]，它的突出優點是可以將圖像中較為困難的全局檢測問題轉換為參數空間中相對容易解決的局部峰值檢測問題[5]。本文將提出一種基于改進的Hough變換的二次檢測同心圓的算法，先用一種改進的Hough變換算法檢測圓，再將檢測到的圓進行破壞后，進行第二次圓檢測，最后判斷前后檢測到的圓的圓心和半徑的關系來判斷其是否為同心圓。這種算法克服了以前同心圓檢測算法缺點，一方面縮小了檢測同心圓的局限性，另一方面提高了檢測效率，并用仿真和應用實例證明了算法的高效和準確性。

1 改進的梯度Hough變換檢測圓(IGHT)

圓的一般方程為：

在對圓進行檢測的時候，往往只需要得到該圓的邊界信息，這就要用到邊緣檢測，一階導數可以用于檢測圖像中的一個點是否是邊緣點。

圖像f（x，y）在（x，y）的梯度定為如下方向：

梯度向量指向在坐標（x，y）的f的最大變化率方向。由向量分析得：

其中 表示向量 在（x，y）處的方向角，角度以x軸為基準度量，邊緣在（x，y）處的方向與此點的梯度向量的方向垂直[6]。文獻[7]提出了一種梯度Hough變換來檢測圓方法，用極坐標方程表示圓：

在事先知道半徑情況下，用求圓邊緣上每一點的梯度方向角和根據邊緣點的坐標（x，y）來求圓心坐標（a，b），這樣必須預先知道所求圓的半徑范圍，有較大局限性，所以在此基礎上對GHT方法進行改進。

如圖1所示，圓上所有點的梯度方向都是指向圓心的，圓邊緣上所有的法線必相交于圓心。

傳統的Hough變換用三維累加器A（a，b，r）累加來求得圓心和半徑[8]，圖像平面的方程轉化為參數平面上的示意圖如圖2所示，這樣每次檢測圓都要遍歷整個三維參數空間，耗費大量內存，計算量巨大。為了降低HT方法累加器維數，累加過程分兩個階段進行：第一階段，遍歷圖像，求邊緣梯度，通過Hough變換在參數空間的二維累加器A累加，通過累加的局部峰值確定圓心；第二階段，再遍歷圖像邊緣點，用一個一維累加器B累加半徑，出現頻率最高的半徑作為此圓心對應半徑。

圖1 圓心位于圓邊緣點法線交點

圖2 圓的Hough參數空間

2 基于IGHT的二次檢測的同心圓檢測算法

改進的梯度Hough(IGHT)變換方法的優點是圖像中存在圓交叉、圓互相包含等情況時，仍能檢測出圓，但是當有同心圓時，只能檢測出同心圓中最小的一個。如圖3所示。

圖3 IGHT檢測到的同心圓中的小圓

基于此，本文提出先用IGHT方法進行第一次圓檢測檢測到小圓，記錄圓心（x1，y1），和半徑r1。對此圓進行破壞，分割出外圓，再使用IGHT進行第二次Hough圓檢測，再次記錄圓心（x2，y2）和半徑r2。定義距離：

具體算法步驟如下：

步驟1 原圖像預處理（圖像灰度化，高斯平滑濾波）；

步驟2 對圖像進行CANNY邊緣檢測，并二值化保存為EDGE圖像；

步驟3 預處理后的原圖進行第一次IGHT圓檢測；

步驟4 破壞第一次檢測到的圓，即將EDGE圖像中檢測到的圓的 的圓環內的像素值全部設為0，將這些圓去除，得到圖像DST；

步驟5 對DST圖像預處理，先灰度化，再高斯平滑濾波；

步驟6 第二次IGHT圓檢測；

步驟7 兩次檢測到的圓比較，判斷是否為同心圓，并在原圖中畫出同心圓位置。

設預處理后的圓的邊緣有N個邊緣點，IGHT方法對圓心需要進行（梯度方向直線）2維投票的次數是N。

設圖像上邊緣特征點坐標為 ，與圓心的距離記為d（p（j），（a，b）），

通過和函數S進行半徑累積：

其中N為圓邊緣特征點個數。則Smax累積半徑rk為關于（a，b）存在圓的半徑，故對半徑進行1維投票的次數同樣為N。則每次用IGHT方法檢測圓的復雜度為：

每次用賦值法去掉小圓的復雜度為：

假設圖像有k個同心圓，則整個算法復雜度為：

而文獻[2]提出的算法復雜度為

說明本文算法執行效率更高。

3 實驗仿真

仿真實驗在2.6GHz PC機上應用VS 2008 軟件開發平臺完成，編程語言為C++，并采用OpenCV-2.1庫進行圖像相關處理，下面分別對468×473的三幅圖片先進行CANNY邊緣檢測再進行同心圓檢測。圖5為成功檢測兩個不完整的圓的同心圓的圖片，圖6為存在干擾曲線仍成功檢測到同心圓的圖像，圖7為成功檢測到3個同心圓的圖像，其中圓心的位置都有標注。對于有多個同心圓的情況此算法仍然適用。通過仿真結果和數據，可以看到此算法準確度高，計算速度快，而且有較好地抗干擾性。

圖5 含兩個半圓同心圓的檢測結果

圖6 含干擾的同心圓檢測

圖7 含3個同心圓的檢測結果

圖5 ~圖7的算法處理時間如表1所示。

表1 本文樣本圖同心圓檢測的算法處理時間（處理時間為10次運算的平均值）

4 應用實例

基于此算法的實用性，將此算法成功應用于茶杯茶壺識別實例中（茶具中不添加其它圓形干擾物體），通過基于IGHT同心圓檢測方法檢測出有同心圓處的位置的為茶壺，是圓而非同心圓的位置為茶杯，并成功標記茶杯和茶壺位置和個數。

從茶具正上方拍攝一幅圖片，圖片分辨率為320 240。如圖8，(a)為基于VS 2008 軟件開發平臺和OpenCV庫的茶杯茶壺識別軟件用戶界面，(b)，(c)，(d)，(e)，(f)為算法過程圖以及識別結果圖。第一次檢測到的圓A，B，C，D圓心分別為(144,130)，(244,116)，(32,168)，(204,44)，半徑分別為42，34，26，31。第二次檢測到的圓E圓心為（144,136），半徑為60。這里定義 為0.15，根據公式(5)說明圓A與圓E為同心圓，同心圓所在位置為茶壺，圓B，C，D為茶杯所在位置，時間為69.34ms。

5 結語

日常生活包含同心圓的物體大量存在，如果能方便檢測出同心圓，那么將容易檢測出包含同心圓的物體，因此研究同心圓檢測算法在實際應用中有著十分重要的意義。本文結合IGHT檢測圓的方法和二次檢測法，高效并準確地檢測出圖像中的同心圓，并將此算法成功應用到茶杯茶壺識別中去，證明了此算法的實用性。通過仿真可以看出此算法對半圓弧仍然能準確檢測，抗干擾性較強，而且檢測速度較快，不需要事先確定圓心，半徑，在檢測圓的局限性上有所改善，說明了此算法的優越性。

圖8 本文算法處理過程圖以及識別結果

[1] 秦開懷, 王海穎, 鄭輯濤. 一種基于Hough變換的圓和矩形的快速檢測方法[J]. 中國圖象圖形圖像學報, 2010, 15(1).

[2] 王磊，陳臨強. 基于弦中點Hough變換的同心圓檢測方法[J]. 計算機應用, 2009, 24(7).

[3] 牛建軍, 劉上乾, 韓寶君, 任寶文. 同心圓檢測中的區域劃分算法[J]. 光子學報, 2006, 35(12).

[4] P.V.C.Hough. Method and means for recognizing complex patterns[P].U.S.Pattern, 3069654, 1962, 12: 18.

[5] 夏磊, 蔡超, 周成平, 丁明躍. 一種用Hough變換檢測圓的快速算法[J]. 計算機應用與研究, 2007, 24(10).

[6] RAFAEL C.GONZALEZ，RICHARD E.WOODS. 數字圖像處理（第二版）. 電子工業出版社, 2007. 8. 467-474.

[7] 瞿鈞, 甘嵐. 梯度Hough變換在圓檢測中的應用[J]. 華東交通大學學報,2007, 24(1).

[8] C.KIMME, D.H.BALLARD, J.SKLANSKY, “Finding circles by an array of accumulators”, Communications of the Association for Computing Machinery 18(1975):120-122.