陳 星（廈門(mén)大學(xué)自動(dòng)化系，福建 廈門(mén) 361005）

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

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

1 改進(jìn)的梯度Hough變換檢測(cè)圓(IGHT)

圓的一般方程為：

在對(duì)圓進(jìn)行檢測(cè)的時(shí)候，往往只需要得到該圓的邊界信息，這就要用到邊緣檢測(cè)，一階導(dǎo)數(shù)可以用于檢測(cè)圖像中的一個(gè)點(diǎn)是否是邊緣點(diǎn)。

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

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

其中 表示向量 在（x，y）處的方向角，角度以x軸為基準(zhǔn)度量，邊緣在（x，y）處的方向與此點(diǎn)的梯度向量的方向垂直[6]。文獻(xiàn)[7]提出了一種梯度Hough變換來(lái)檢測(cè)圓方法，用極坐標(biāo)方程表示圓：

在事先知道半徑情況下，用求圓邊緣上每一點(diǎn)的梯度方向角和根據(jù)邊緣點(diǎn)的坐標(biāo)（x，y）來(lái)求圓心坐標(biāo)（a，b），這樣必須預(yù)先知道所求圓的半徑范圍，有較大局限性，所以在此基礎(chǔ)上對(duì)GHT方法進(jìn)行改進(jìn)。

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

傳統(tǒng)的Hough變換用三維累加器A（a，b，r）累加來(lái)求得圓心和半徑[8]，圖像平面的方程轉(zhuǎn)化為參數(shù)平面上的示意圖如圖2所示，這樣每次檢測(cè)圓都要遍歷整個(gè)三維參數(shù)空間，耗費(fèi)大量?jī)?nèi)存，計(jì)算量巨大。為了降低HT方法累加器維數(shù)，累加過(guò)程分兩個(gè)階段進(jìn)行：第一階段，遍歷圖像，求邊緣梯度，通過(guò)Hough變換在參數(shù)空間的二維累加器A累加，通過(guò)累加的局部峰值確定圓心；第二階段，再遍歷圖像邊緣點(diǎn)，用一個(gè)一維累加器B累加半徑，出現(xiàn)頻率最高的半徑作為此圓心對(duì)應(yīng)半徑。

圖1 圓心位于圓邊緣點(diǎn)法線交點(diǎn)

圖2 圓的Hough參數(shù)空間

2 基于IGHT的二次檢測(cè)的同心圓檢測(cè)算法

改進(jìn)的梯度Hough(IGHT)變換方法的優(yōu)點(diǎn)是圖像中存在圓交叉、圓互相包含等情況時(shí)，仍能檢測(cè)出圓，但是當(dāng)有同心圓時(shí)，只能檢測(cè)出同心圓中最小的一個(gè)。如圖3所示。

圖3 IGHT檢測(cè)到的同心圓中的小圓

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

具體算法步驟如下：

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

步驟2 對(duì)圖像進(jìn)行CANNY邊緣檢測(cè)，并二值化保存為EDGE圖像；

步驟3 預(yù)處理后的原圖進(jìn)行第一次IGHT圓檢測(cè)；

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

步驟5 對(duì)DST圖像預(yù)處理，先灰度化，再高斯平滑濾波；

步驟6 第二次IGHT圓檢測(cè)；

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

設(shè)預(yù)處理后的圓的邊緣有N個(gè)邊緣點(diǎn)，IGHT方法對(duì)圓心需要進(jìn)行（梯度方向直線）2維投票的次數(shù)是N。

設(shè)圖像上邊緣特征點(diǎn)坐標(biāo)為 ，與圓心的距離記為d（p（j），（a，b）），

通過(guò)和函數(shù)S進(jìn)行半徑累積：

其中N為圓邊緣特征點(diǎn)個(gè)數(shù)。則Smax累積半徑rk為關(guān)于（a，b）存在圓的半徑，故對(duì)半徑進(jìn)行1維投票的次數(shù)同樣為N。則每次用IGHT方法檢測(cè)圓的復(fù)雜度為：

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

假設(shè)圖像有k個(gè)同心圓，則整個(gè)算法復(fù)雜度為：

而文獻(xiàn)[2]提出的算法復(fù)雜度為

說(shuō)明本文算法執(zhí)行效率更高。

3 實(shí)驗(yàn)仿真

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

圖5 含兩個(gè)半圓同心圓的檢測(cè)結(jié)果

圖6 含干擾的同心圓檢測(cè)

圖7 含3個(gè)同心圓的檢測(cè)結(jié)果

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

表1 本文樣本圖同心圓檢測(cè)的算法處理時(shí)間（處理時(shí)間為10次運(yùn)算的平均值）

4 應(yīng)用實(shí)例

基于此算法的實(shí)用性，將此算法成功應(yīng)用于茶杯茶壺識(shí)別實(shí)例中（茶具中不添加其它圓形干擾物體），通過(guò)基于IGHT同心圓檢測(cè)方法檢測(cè)出有同心圓處的位置的為茶壺，是圓而非同心圓的位置為茶杯，并成功標(biāo)記茶杯和茶壺位置和個(gè)數(shù)。

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

5 結(jié)語(yǔ)

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

圖8 本文算法處理過(guò)程圖以及識(shí)別結(jié)果

[1] 秦開(kāi)懷, 王海穎, 鄭輯濤. 一種基于Hough變換的圓和矩形的快速檢測(cè)方法[J]. 中國(guó)圖象圖形圖像學(xué)報(bào), 2010, 15(1).

[2] 王磊，陳臨強(qiáng). 基于弦中點(diǎn)Hough變換的同心圓檢測(cè)方法[J]. 計(jì)算機(jī)應(yīng)用, 2009, 24(7).

[3] 牛建軍, 劉上乾, 韓寶君, 任寶文. 同心圓檢測(cè)中的區(qū)域劃分算法[J]. 光子學(xué)報(bào), 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變換檢測(cè)圓的快速算法[J]. 計(jì)算機(jī)應(yīng)用與研究, 2007, 24(10).

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

[7] 瞿鈞, 甘嵐. 梯度Hough變換在圓檢測(cè)中的應(yīng)用[J]. 華東交通大學(xué)學(xué)報(bào),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.