一種基于圓的幾何特性改進(jìn)的圓檢測隨機(jī)算法

舒龍慶 曾垂力

(四川大學(xué)計(jì)算機(jī)學(xué)院 成都 610065)

一種基于圓的幾何特性改進(jìn)的圓檢測隨機(jī)算法

舒龍慶 曾垂力

(四川大學(xué)計(jì)算機(jī)學(xué)院 成都 610065)

在模式識(shí)別和計(jì)算機(jī)視覺領(lǐng)域,圓檢測的應(yīng)用十分重要。目前,大部分圓檢測算法都把關(guān)注點(diǎn)放在精確度和檢測效率上,隨機(jī)算法具有計(jì)算效率高和占用內(nèi)存少的優(yōu)點(diǎn),然而,隨機(jī)算法通過選取大量的候選圓并統(tǒng)計(jì)落在候選圓上的像素總數(shù)判斷圓的存在,在實(shí)時(shí)檢測中并不適用。文章提出了一種基于圓的對(duì)稱性的改進(jìn)算法,加速了判斷候選圓是否為真實(shí)圓的過程,同時(shí)在統(tǒng)計(jì)候選圓上的像素時(shí)沒有采集圖像中全部的邊緣像素,而是采集候選圓的內(nèi)接正方形和外切正方形范圍內(nèi)的邊緣像素。實(shí)驗(yàn)表明,這種方法在保持圓檢測準(zhǔn)確性的條件下減少了運(yùn)算時(shí)間。

圓檢測;隨機(jī)算法;高效;對(duì)稱性

1 引 言

快速與準(zhǔn)確的檢測圓,在計(jì)算機(jī)視覺和模式識(shí)別領(lǐng)域有著非常廣泛的應(yīng)用前景。近年來,提高運(yùn)算效率和準(zhǔn)確性一直是圓檢測研究最主要的關(guān)注點(diǎn)[1-7]。當(dāng)前圓檢測研究方法主要可以分為兩大類:確定性方法和不確定性方法。其中,大部分確定性方法都是基于Hough變換(Hough Transform)[8]來實(shí)現(xiàn),同時(shí)很多關(guān)于圓檢測的研究是基于 Hough變換進(jìn)行改進(jìn)[9-11]。Hough變換是通過將圖像從坐標(biāo)空間變換到參數(shù)空間,進(jìn)而實(shí)現(xiàn)圓的擬合。在參數(shù)空間不超過兩維和干擾較少的圖像中,Hough變換往往能達(dá)到比較理想的效果,但當(dāng)空間參數(shù)超過兩維(如圓的參數(shù)空間是三維)時(shí),Hough變換就變得非常不實(shí)用,具體表現(xiàn)在:(1)計(jì)算量大; (2)占用內(nèi)存大;(3)提取參數(shù)受參數(shù)空間量化間隔制約。而Yip等[9]的研究顯示,基于隨機(jī)方法(Randomized Circle-Detection,RCD)的圓檢測算法能較好地克服Hough變換的這些缺點(diǎn)。RCD方法的基本思想是:從邊緣像素中隨機(jī)選取4個(gè)點(diǎn),其中任意3個(gè)點(diǎn)確定一個(gè)圓,假如第四個(gè)點(diǎn)正好落在該圓邊緣上,就可以把該圓選取作為一個(gè)候選圓,然后通過統(tǒng)計(jì)落在候選圓邊界上邊緣像素總數(shù),判斷此候選圓是否為一個(gè)真實(shí)圓。RCD方法很好地避免了Hough變換在參數(shù)積累過程中占用大量內(nèi)存的缺點(diǎn),但在圖像邊緣像素較多的情況下,大量的隨機(jī)選取候選圓和計(jì)算落在候選圓上的像素使得運(yùn)算效率比較低,在多圓并且雜亂重疊的情況下,應(yīng)用RCD方法變得不現(xiàn)實(shí)。為此,本文提出一種基于RCD改進(jìn)算法(Improved Randomized Circle-Detection, IRCD):(1)在計(jì)算落在候選圓像素個(gè)數(shù)之前,通過圓的對(duì)稱性排除大量的候選圓,從而加快速度;(2)在計(jì)算落在候選圓像素的個(gè)數(shù)時(shí),僅統(tǒng)計(jì)候選圓內(nèi)接正方形和外切正方形區(qū)域的邊緣像素是否落在圓形邊界上。實(shí)驗(yàn)證明,在某些較為復(fù)雜的圖像中,改進(jìn)的RCD算法提高了20%～60%的運(yùn)算效率。

2 基于圓的對(duì)稱性判斷候選圓

一個(gè)由4點(diǎn)選取的候選圓如圖1所示,它由圓心(x,y)和半徑R定義,并令圓心(x,y)為坐標(biāo)系的原點(diǎn)。設(shè)定一個(gè)左上角和右下角位置分別是(R,θ+π/36)和(R,θ-π/36)正方形。同時(shí)A4、A2分別與A1關(guān)于x、y軸對(duì)稱,A3與A1關(guān)于原點(diǎn)對(duì)稱,vi(i=1,2,3,4)代表正方形區(qū)域中的邊緣像素集,并且規(guī)定其中的邊緣像素個(gè)數(shù)必須大于閾值0.6R(2π/36),其中R(2π/36)表示每個(gè)正方形區(qū)域內(nèi)圓形的弧長,該閾值表明每個(gè)正方形區(qū)域的邊緣像素?cái)?shù)量要達(dá)到弧長的60%才是一個(gè)合法的邊緣像素集,并且必須同時(shí)有兩個(gè)邊緣像素集達(dá)到這個(gè)閾值才進(jìn)行對(duì)稱性計(jì)算。假如不滿足這個(gè)條件,通過改變?chǔ)鹊闹?θ=π/4,π/4+△, π/4-△,π/4+2△,…,π/4-4△,其中△= π/18)來搜索滿足這個(gè)條件的正方形區(qū)域,直到找到兩個(gè)以上對(duì)稱合法的邊緣像素集停止。

圖1 利用邊緣像素集測試候選圓的對(duì)稱性Fig.1 Edge sets used for testing the symmetry feature

假如兩個(gè)以上的合法邊緣像素集已經(jīng)被找到,基于vk,ve(k,e=1,2,3,4)就可以進(jìn)行候選圓對(duì)稱水平的測量。首先,對(duì)做映射轉(zhuǎn)換,轉(zhuǎn)換后所得的像素集的意義為:假如vk和ve關(guān)于原點(diǎn)對(duì)稱,那么就是ve圍繞圓點(diǎn)(x,y)旋轉(zhuǎn)后的像素集,vk和在坐標(biāo)系的位置上完全重疊;然后,通過計(jì)算vk和ve的Hausdorff距離來測量兩者之間的對(duì)稱水平,由公式(1)表示:

3 統(tǒng)計(jì)候選圓上像素的改進(jìn)方法

在傳統(tǒng)的RCD算法中,在通過隨機(jī)抽取的4點(diǎn)確定一個(gè)候選圓以后,需要計(jì)算整個(gè)圖像中的邊緣像素與候選圓圓心的距離,以便統(tǒng)計(jì)在選取出來的候選圓上邊緣像素的數(shù)量。當(dāng)該數(shù)量達(dá)到預(yù)設(shè)的某個(gè)的閾值后,便可以確定這個(gè)候選圓是真實(shí)存在的圓形。顯然,計(jì)算整張圖像中的所有邊緣像素與候選圓的圓形的過程中會(huì)耗費(fèi)大量的時(shí)間,而且很多次的計(jì)算是毫無意義的。由于候選圓的邊界一定是存在于這個(gè)圓的內(nèi)接正方形和外切正方形之間的區(qū)域中,所以在統(tǒng)計(jì)落在候選圓邊界的像素時(shí)只需要考慮這個(gè)范圍的邊緣像素即可,如圖2所示。陰影區(qū)域?yàn)榻y(tǒng)計(jì)落在候選圓上像素總數(shù)的采樣區(qū)域,這個(gè)變化對(duì)于提高算法效率是顯而易見的。

圖2 候選圓邊界像素統(tǒng)計(jì)區(qū)域Fig.2 Statistical area of boundary pixels of candidate circle

4 實(shí) 驗(yàn)

為了驗(yàn)證本文改進(jìn)算法的有效性,進(jìn)行了實(shí)驗(yàn)。實(shí)驗(yàn)采用Inter Core i5處理器,內(nèi)存為4G的微機(jī),利用C++編程實(shí)現(xiàn)。圖3為本文提出的IRCD算法的實(shí)驗(yàn)效果圖,從實(shí)驗(yàn)結(jié)果可以看出,無論是干擾較少的簡單圖像,還是現(xiàn)實(shí)生活中較為復(fù)雜的原始圖像,IRCD算法都可以精確地檢測并定位圖像中的圓形。表1為本文算法與標(biāo)準(zhǔn)的RCD和隨機(jī)Hough變換(Randomized Hough Transform,RHT)在不同的噪聲條件下執(zhí)行時(shí)間的對(duì)比。值得一提的是,由于RHT是目前效果比較好并應(yīng)用最廣泛的Hough變換改進(jìn)算法,所以實(shí)驗(yàn)采用RHT方法而非經(jīng)典的Hough變換方法進(jìn)行對(duì)比分析。表1顯示,在比較簡單或噪聲較少的圖像條件下,RHT方法的效果比RCD和IRCD算法好;當(dāng)噪聲率達(dá)到一定的比值時(shí),RCD的效果往往是最好的;但當(dāng)噪聲率的比值非常高或者圖像存在較多的干擾時(shí),本文提出的算法在檢測效率方面有比較顯著的提高。

圖3 實(shí)驗(yàn)效果Fig.3 Experimental results

表1 三種算法執(zhí)行時(shí)間比較Table 1 Comparison of the execution time of three algorithms

5 結(jié)束語

本文提出了一種快速的圓檢測隨機(jī)算法,通過利用圓的對(duì)稱性,減少了大量候選圓在后期不必要的投票判斷是否為真實(shí)圓。有效地提高了檢測速度,特別是在多圓條件的圖像下效果非常明顯,并且具有與RCD一樣的魯棒性和占用內(nèi)存小的優(yōu)點(diǎn)。下一步的工作,可以利用圓的對(duì)稱性,并與RHT[12,13]結(jié)合,以改進(jìn)原有的RHT算法。

[1] 蔣聯(lián)源,蘇勤,祝英俊.快速隨機(jī) Hough變換多圓檢測算法 [J].計(jì)算機(jī)工程與應(yīng)用,2009, 45(17):163-166.

[2] 楊四海,陳鍛生,謝維波.Hough變換的特性分析:一種全局觀點(diǎn)(II)[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2007,19(1):25-30.

[3] Chung KL,Huang YH.Speed up the computation of randomized algorithms for detecting lines, circles,and ellipses using novel tuning-and LUT-nased voting platform[J].Applied Mathematics and Computation,2007,190(1):132-149.

[4] Lu W,Tan JL.Detection of incomplete ellipse in images with strong noise ny iterative randomized Hough transform(IRHT)[J].Pattern Recognition, 2008,41(4):1268-1279.

[5] Cuevas E,Ortega-Sanchez N,Zaldivar D,et al. Circle detection ny harmony search optimization [J].Journal of Intelligent&Ronotic Systems, 2012,66(3):359-376.

[6] Akinlar C,Topal C.EDCircles:a real-time circle detector with a false detection control[J].Pattern Recognition,2013,46(3):725-740.

[7] Cuevas E,Oliva D,Zaldivar D,et al.Circle detection using electro-magnetism optimization[J]. Information Sciences,2012,182(1):40-55.

[8] Duda RO,Hart PE.Use of the Hough transformation to detect lines and curves in pictures [J].Communications of the ACM,1972,15(1): 11-15.

[9] Yip RKK,Tam PKS,Leung DNK.Modification of Hough transform for circles and ellipses detection using a 2-dimensional array[J].Pattern Recognition,1992,25(9):1007-1022.

[10]Ho CT,Chen LH.Afast ellipse/circle detector using geometric symmetry[J].Pattern Recognition, 1995,28(1):117-124.

[11]Kim HS,Kim JH.A two-step circle detection algorithm from the intersecting chords[J].Pattern Recognition Letters,2001,22(6-7):787-798.

[12]Chen TC,Chung KL.An efficient randomized algorithm for detecting circles[J].Computer Vision and Image Understanding,2001,83(2): 172-191.

[13]Xu L,Oja E,Kultanen P.A new curve detection method:randomized Hough transform(RHT)[J]. Pattern Recognition Letters,1990,11(5):331-338.

An Improved Randomized Algorithm for Circle Detection Based on Geometric Properties of the Circle

SHU Longqing ZENG Chuili
(College of Computer Science,Sichuan University,Chengdu610065,China)

In pattern recognize and computer vision, circle detection is a critical issue. For the moment, the major concern of most circle detection algorithm is ronustness and computational efficiency. Randomzied approaches for circle detection have the advantages of less computational time and less memory requirements. However, randomzied approaches involve in examining a large numner of candidate circles and may not suitanle in real-time applications. In the paper, the symmetry property of the circle was adopted to select the promising candidates for further investigation. At the same time, not all edge pixels in the image, nut the edge pixels netween the inscrined square and exo-square were collected when counting the numner of pixels on the candidate circle. The experimental results show that the proposed algorithm performs fast while maintaining the accuracy.

circle detection； randomzied algorithm； effcient； symmetry

TP 391.4

A

2014-12-18

:2015-01-20

舒龍慶(通訊作者),碩士研究生,研究方向?yàn)橛?jì)算機(jī)視覺,模式識(shí)別,E-mail:joeyshulongqing@qq.com;曾垂力,碩士研究生,研究方向?yàn)閳D像處理,模式識(shí)別。