基于隨機Hough變換改進的快速圓檢測算法

朱正偉，宋文浩，焦竹青，郭 曉

(常州大學(xué)(武進校區(qū)) 信息科學(xué)與工程學(xué)院，江蘇 常州 213164)

0 引 言

目前，圖像中圓檢測的最常用方法是Hough變換[1,2]，但Hough變換通常需要較大的存儲空間和計算時間，因而很少在實際應(yīng)用中使用。

為了提升Hough變換算法的性能有學(xué)者提出了隨機Hough變換算法，該算法的思想[3]是在邊緣圖像中隨機選取3個點映射成參數(shù)空間的一個點，以此計算圓的參數(shù)，并對結(jié)果進行累積以判斷圓的真假。隨機Hough變換只對有效參數(shù)單元進行累計，大大減輕了內(nèi)存的負(fù)擔(dān)，節(jié)省大量內(nèi)存空間，避免了Hough變換一到多映射的巨大運算量，但是隨機Hough變換對邊緣圖像的要求很高，如果圓形出現(xiàn)變形，就不能準(zhǔn)確檢測出結(jié)果，且由于隨機采樣，隨機取出的三點在同一圓的概率就很小，導(dǎo)致檢測速度較低。為了克服這些缺陷，研究人員提出了一些改進的方法，比如對隨機采樣進行約束[4,5]、利用采樣點的梯度[6-8]或曲率信息[9,10]來判斷是否進行累積、利用隨機采樣共圓的四點來降低無效累積的計算[11,12]、通過在每次成功檢測圓后不清空參數(shù)空間來減少總采樣次數(shù)[13]。為了進一步提高隨機圓檢測速度，本文提出了一種改進的隨機Hough變換快速圓檢測算法。通過實驗對比驗證，本文算法相比于傳統(tǒng)算法可以明顯提高檢測速度。

1 隨機Hough變換圓檢測

由于Hough變換在檢測圓時有較大問題，因而本文僅對隨機Hough變換算法(RHT)做相關(guān)介紹。首先設(shè)定待檢測圖像中圓的期望個數(shù)以及采樣累積循環(huán)次數(shù)上限。在每次循環(huán)中，隨機采樣3個不共線的邊緣點，計算出對應(yīng)的圓的參數(shù)(a,b,r)，即候選圓的圓心為(a,b)，半徑為r；如果圖像中的邊緣點到圓心的距離近似等于半徑，則認(rèn)為該邊緣點為候選圓上的點，統(tǒng)計邊緣點在候選圓上的個數(shù)；如果候選圓上被驗證的邊緣點個數(shù)超過一定閾值，則認(rèn)定該候選圓為真圓，并將該圓對應(yīng)的所有邊緣點去除，循環(huán)結(jié)束。直到檢測完所有的圓為止。

設(shè)D為圖像邊緣點集，P為圓參數(shù)單元集，k為隨機采樣循環(huán)次數(shù)，Kmax為循環(huán)采樣次數(shù)閾值，N為累計驗證閾值，Mmin為共圓驗證閾值，則RHT算法具體實現(xiàn)步驟如下：

步驟1 構(gòu)造邊緣點集D，初始化圓參數(shù)集合P=NULL，初始化循環(huán)次數(shù)k=0。

步驟2 從集合D中隨機選取3個點。

步驟3 由這3點可得到圓參數(shù)p，若有解，轉(zhuǎn)步驟4；否則轉(zhuǎn)步驟7。

步驟5 將p插入P，令其對應(yīng)value值為1，轉(zhuǎn)步驟7。

步驟6 將pc的value值加1，若value

步驟7 令k=k+1， 若k>Kmax，則結(jié)束；否則轉(zhuǎn)步驟2。

步驟8pc為候選圓參數(shù)，若該圓上統(tǒng)計的點數(shù)M>Mmin，轉(zhuǎn)步驟9；否則轉(zhuǎn)步驟10。

步驟9pc為真圓參數(shù)，轉(zhuǎn)步驟11。

步驟10pc為假圓參數(shù)，從P中去除pc，轉(zhuǎn)步驟2。

步驟11 判斷期望圓是否已經(jīng)檢測完，若是則結(jié)束；否則，從D中去掉pc上的點，同時令P=NULL，k=0，轉(zhuǎn)步驟2。

算法流程如圖1所示。

圖1 隨機Hough變換算法流程

2 改進的快速隨機Hough變換圓檢測

改進算法主要分為以下3個部分：①原始圖像預(yù)處理，即通過對圖像灰度化、平滑濾波和邊緣細(xì)化等處理，消除光照、背景等噪聲點，為后期圖像處理減少數(shù)據(jù)量；②候選圓的檢測，即通過檢測算法計算出候選圓，但不確定真假，需要對其進行驗證；③候選圓的驗證，即通過證據(jù)積累驗證候選圓的真假，同時去除被錯誤擬合的圓，余下的圓就是所找的真圓。

2.1 對原始圖像進行預(yù)處理

由于實際圖像往往比較復(fù)雜，可能存在如光照不均勻、目標(biāo)物體分布不規(guī)則、相互之間有遮擋和物體邊界模糊等問題。為了避免上述問題對圓檢測的影響，先對原圖像進行預(yù)處理，減少圖像中的噪聲點，從而有效減少無效累積和計算量，從而提高檢測效率。

對原圖像進行預(yù)處理的步驟：①對原始圖像進行灰度化和平滑濾波操作，圖像的濾波處理可以去除一些噪聲同時又可以保留圖像的邊緣信息，有利于圖像的進一步處理；②對圖像進行二值化，二值化處理可以大幅減少圖像中數(shù)據(jù)量，同時能凸顯出感興趣的物體輪廓；③對二值圖像進行邊緣檢測，邊緣檢測算子選擇Canny算子,Canny算子相比于其它算子能更好地保留物體邊緣；④對邊緣圖像進行細(xì)化處理，將邊緣細(xì)化到最低限度且相連沒有斷點的線，該步同樣可以減少數(shù)據(jù)量，提高檢測效率。

2.2 候選圓的檢測

盡管傳統(tǒng)RHT是只對多到一映射所得的參數(shù)分配單元進行判斷和累積，但在處理復(fù)雜圖像時，大量噪聲點會干擾隨機采樣操作，使圓上的點被成功采樣到的概率變小，引入大量無效采樣，易導(dǎo)致無效判斷和無效累積從而影響算法效率。

本文獲取候選圓的方式為首先在邊緣圖像上隨機采樣一點p1(x1,y1)(如圖2所示)，再在以p1為中心N×N的方形窗口內(nèi)，找到p1所在的連通域，并對連通域內(nèi)的點進行最小二乘法圓擬合以得到候選圓。

圖2 以p1為中心的N×N的窗口

最小二乘法(least squares analysis)通常用于曲線擬合，它是一種經(jīng)典的優(yōu)化手段。最小二乘法原理是采用最簡的方法求得一些絕對不可知的真值，且令誤差平方之和為最小。

對于從p1點連通域得到的點集 {(xi,yi)，i=1,2,…,m， 其中m為點集中點的數(shù)量}，設(shè)理想圓pc的圓心為(a,b)，半徑為r，則點距候選圓圓心的代數(shù)距離方程為

d=(x-a)2+(y-b)2-r

(1)

式中： (x,y)∈{(xi,yi),i=1,2,…,m}。

令候選圓半徑的取值范圍為[Rmin,Rmax]，如果理想圓的半徑r滿足Rmin

2.3 候選圓的驗證

通過2.2節(jié)的方法可以得到圖像中的候選圓，但候選圓的真假不能確定，可能存在一些被錯誤擬合的圓，因此需要對其進行驗證，去除假圓。

驗證候選圓的真假，需要統(tǒng)計候選圓上的點數(shù)。本文算法規(guī)定如果邊緣點位于該圓內(nèi)切正方形和外接正方形之間的部分區(qū)域，則判斷該點為候選圓上的點。這樣通過簡單的數(shù)值比較即可篩選出符合的像素點，相對通過計算兩點間距離的驗證方式可以明顯減少計算量從而大幅縮減驗證耗時。具體采樣區(qū)域如圖3中陰影部分所示。

圖3 候選圓內(nèi)切外接正方形

由圖3知，候選圓的圓心坐標(biāo)為(a,b)，半徑為r，要驗證的邊緣點坐標(biāo)(x,y)若滿足式(2)

(2)

則視點(x,y)為候選圓上的點，統(tǒng)計該候選圓上的邊緣點的數(shù)量M。令驗證候選圓為真圓的閾值Mmin=λ*2πr(其中λ為比例系數(shù)，r為候選圓半徑)，若M>Mmin，則確認(rèn)當(dāng)前候選圓為真圓，否則為假圓。

2.4 算法的總體流程實現(xiàn)

本文算法描述如下：

步驟1 將邊緣圖像中的所有邊緣點存儲至集合D，初始循環(huán)次數(shù)k=0，令最大循環(huán)次數(shù)為Kmax；

步驟2 從D中隨機選取一個點d1；

步驟3 在以點d1為中心的N×N的窗口內(nèi)，找到d1所在的連通域，并對此連通域內(nèi)點進行圓擬合，得到理想圓pc(a,b,r)，若半徑r滿足Rmin

步驟4 對候選圓pc進行證據(jù)積累，若pc的有效計數(shù)大于閾值Mmin，則轉(zhuǎn)步驟6；否則，轉(zhuǎn)步驟5；

步驟5k=k+1，若k>Kmax，則結(jié)束；否則，轉(zhuǎn)步驟2；

步驟6pc為真圓，判斷理想圓是否已經(jīng)檢測完。若是，則結(jié)束；否則，轉(zhuǎn)步驟2。

算法流程如圖4所示。

圖4 改進算法的流程實現(xiàn)

3 實驗驗證及分析

為驗證算法的有效性，用MATLAB程序完成了大量的圖片圓檢測實驗。限于篇幅，只選取當(dāng)中的幾幅圖片做說明。本文運行軟件版本為MATLAB R2014a，微機硬件配置為Intel(R) Pentium(R) CPU P6200 @2.13 GHz，4 G RAM，比例系數(shù)λ取[0.6,0.9]。下面就多個算法的預(yù)處理、耗時、準(zhǔn)確性3個方面做比較分析。

3.1 預(yù)處理方法比較

對原始圖像進行預(yù)處理，可以顯著減少圖像中無關(guān)噪聲的影響。傳統(tǒng)預(yù)處理方法一般是對原始圖像直接進行邊緣檢測，本文改進方法是按照2.1節(jié)描述的方法對圖像進行預(yù)處理得到邊緣圖像。預(yù)處理結(jié)果如圖5所示，其中(a)、(d)為原圖像，(b)、(e)為對應(yīng)原圖采用傳統(tǒng)預(yù)處理方法得到的邊緣圖像，(c)、(f)為對應(yīng)原圖采用本文改進后的預(yù)處理方法得到的邊緣圖像。

圖5 預(yù)處理方法對比

采用傳統(tǒng)預(yù)處理方法和本文提出的改進方法分別對圖5中的(a)和(d)圖像進行處理，表1為采用兩種方法處理后圖像中剩余邊緣點數(shù)的統(tǒng)計結(jié)果。從表中數(shù)據(jù)可以看出傳統(tǒng)邊緣方法和本文邊緣方法得到的結(jié)果有較大差異。前者得到的結(jié)果中含有大量的噪聲點，而本文改進的方法明顯減少了噪聲點數(shù)量，有利于下一步的圖像處理。

表1 兩種預(yù)處理方法結(jié)果

3.2 算法耗時分析

為驗證本文算法的加速效果，對RHT算法、文獻[13]的RHT_A算法和本文算法進行2組實驗比較。在實驗中，由于3種算法都是基于隨機采樣機制的，因而算法每次運行時間不固定，對此本文對每種算法均分別測試50次，取其耗時的平均值作為檢測時間。

實驗1為合成圖像對比實驗。為測試算法的性能，在圖6(a)的合成圖上增加不同程度的隨機噪聲點，噪聲比分別為50%和100%。圖6中，(a)為一幅大小為256×256的合成圖像，(b)為噪聲比為50%的圖像，(c)為噪聲比為100%的圖像。

圖6 合成圖像實驗

表2所示為3種算法對不同噪聲比圖像進行圓檢測所耗費時間的平均值，從中可以看出，當(dāng)噪聲比相同時，本文算法比RHT算法和RHT_A算法耗時少，說明了本文算法的加速效果。

實驗2為實際圖像對比實驗，圖7中的(a)和(b)兩幅圖片來自文獻[5]和文獻[13]，表3為對(a)、(b)兩幅實際圖像分別使用3種算法所耗費的時間。從中可以看出，本文算法針對不同噪聲比圖像的檢測耗費時間均明顯比RHT算法和RHT_A算法耗費時間少。由此可見本文算法具有較快的圓檢測速度，具有較好的檢測效率。

表2 3種算法對不同噪聲比圖像圓檢測的耗時

圖7 實際圖像

算法圖7(a)圖7(b)RHT算法/s3.1673.437RHT_A算法/s1.4161.252本文算法/s0.4160.547

3.3 算法準(zhǔn)確性分析

為了驗證本文算法的準(zhǔn)確性，分別使用RHT算法、RHT_A算法和本文算法對圖7中的實際圖像(b)進行檢測。其檢測結(jié)果如圖8所示(其中白色圓為檢測出的圓)。

圖8 3種算法檢測結(jié)果

仔細(xì)觀察圖8，可以發(fā)現(xiàn)在檢測精度上，3種算法檢測效果相當(dāng)。對于圖7(b)，考慮到原圖像中部分圓形物體不能完整顯示，故設(shè)定圖像中可識別的完整圓數(shù)目為25個。下面分別對3種算法就圓總數(shù)、正確檢測數(shù)目、錯誤檢測數(shù)目、漏檢數(shù)目4個方面進行統(tǒng)計，詳見表4。

表4 實際圖片實驗數(shù)據(jù)

從表4中數(shù)據(jù)可以看出，3種算法均可以檢測出25個圓中的22個，而本文算法和RHT_A算法沒有錯檢和漏檢，因此在檢測準(zhǔn)確性上，本文算法和RHT_A算法相當(dāng)并且優(yōu)于RHT算法。

4 結(jié)束語

文本就隨機Hough變換算法進行了改進，算法的優(yōu)點在于在預(yù)處理環(huán)節(jié)增加降噪和邊緣化的處理，顯著減少了數(shù)據(jù)量；同時采用圓擬合的方式確定候選圓，提高了擬合候選圓的正確性；最后在驗證真圓環(huán)節(jié)通過縮小限定累積取值區(qū)域，大大降低了計算量。通過對模擬圖像和實際圖像的實驗結(jié)果對比，本文算法運行時間明顯小于隨機Hough變換算法且具有較好的準(zhǔn)確性。另外，本文算法還具有抗噪聲能力強等優(yōu)點，在實際圖像檢測中性能表現(xiàn)良好，對各個領(lǐng)域的圓識別具有較好的應(yīng)用價值。