代巍 沈云嘯 謝寧 何道聰 馬亞?wèn)|
【摘 要】為解決現(xiàn)有隨機(jī)Hough變換(RHT)圓檢測(cè)算法存在的無(wú)效積累嚴(yán)重問(wèn)題,提出一種基于k-means聚類(lèi)算法和隨機(jī)Hough變換(RHT)圓檢測(cè)算法的雙階段圓檢測(cè)算法(KRA)。所提出的KRA由k-means聚類(lèi)算法和RHT圓檢測(cè)算法兩部分組成。k-means聚類(lèi)算法負(fù)責(zé)對(duì)邊緣點(diǎn)進(jìn)行聚類(lèi),得到每一類(lèi)邊緣點(diǎn)額范圍。在此基礎(chǔ)上,RHT圓檢測(cè)算法對(duì)區(qū)域內(nèi)的點(diǎn)進(jìn)行檢測(cè),最終得到圓的參數(shù)。實(shí)驗(yàn)表明,提出的KRA能檢測(cè)到所有圓,并且算法的聚類(lèi)和檢測(cè)時(shí)間只占RHT圓檢測(cè)時(shí)間的25.2%~67.8%,即采樣積累減少25.2%~67.8%,從而證明了文章提出的算法在減少無(wú)效采樣方面的有效性。
【關(guān)鍵詞】圓檢測(cè);感興趣區(qū)域(ROI);k均值聚類(lèi);隨機(jī)Hough變換;小范圍隨機(jī)采樣
【中圖分類(lèi)號(hào)】TP391.41 【文獻(xiàn)標(biāo)識(shí)碼】A 【文章編號(hào)】1674-0688(2021)03-0040-03
圓檢測(cè)是計(jì)算機(jī)視覺(jué)領(lǐng)域的常見(jiàn)方向,被廣泛應(yīng)用于工程實(shí)踐項(xiàng)目。Hough變換圓檢測(cè) [1]是最基本的檢測(cè)方法,其原理是把曲線由圖像空間中映射到由圓的3個(gè)參數(shù)構(gòu)成的參數(shù)空間,累加統(tǒng)計(jì)參數(shù)空間的點(diǎn),最大累加值的參數(shù)即為所求圓的參數(shù)。但該算法存在很多不足之處,在參數(shù)量、計(jì)算量和內(nèi)存占用方面有很大的改進(jìn)空間。針對(duì)上述不足,Xu L等人 [2]提出使用隨機(jī)Hough變換做圓檢測(cè),該方法在圖像空間中隨機(jī)選取不共線的3個(gè)特征點(diǎn),映射成參數(shù)空間中的一個(gè)點(diǎn),是多到一的映射,大大減少了計(jì)算量,但是在圖像復(fù)雜的情形下,由于噪聲較多,從而引入大量的無(wú)效采樣,增加迭代次數(shù),降低檢測(cè)效率 [3]。隨后,有很多改進(jìn)的算法被提出,周勇亮等人 [4]提出一種有效繼承的累計(jì)加速算法,每次成功檢測(cè)圓后不清空參數(shù)空間,在隨機(jī)Hough變換圓檢測(cè)算法上測(cè)試取得很好的速度提升,但是對(duì)于單圓和極端情況下加速效果并不明顯。Chen等人 [5]在隨機(jī)Hough變換的基礎(chǔ)上進(jìn)行了改進(jìn),使用第4個(gè)隨機(jī)采樣點(diǎn)判斷是否在候選圓上,隨后再驗(yàn)證圓的真?zhèn)危岣吡藞A的檢測(cè)速度。
除此之外,還有許多學(xué)者從不同的角度改進(jìn)圓檢測(cè)算法,如在Hough變換的基礎(chǔ)上結(jié)合梯度信息 [6],運(yùn)用圓的幾何屬性做圓檢測(cè) [7]及使用圖像的直方圖 [8]作為評(píng)判依據(jù),這些措施都取得了不錯(cuò)的提升。
文中提到的改進(jìn)算法是基于隨機(jī)Hough變換(RHT)圓檢測(cè)算法進(jìn)行,雖然大幅提高了算法檢測(cè)效率,但是仍存在漏檢及無(wú)效積累等嚴(yán)重問(wèn)題。為了改善這一問(wèn)題,本文提出了一種基于k-means聚類(lèi)算法和隨機(jī)Hough變換圓檢測(cè)結(jié)合的新的圓檢測(cè)算法,通過(guò)結(jié)合兩種算法的優(yōu)點(diǎn),對(duì)采樣空間進(jìn)行約束,大大減少了無(wú)效采樣并降低了圓的漏檢率。
1 傳統(tǒng)的隨機(jī)Hough變換圓檢測(cè)
在平面直角坐標(biāo)系中,圓的標(biāo)準(zhǔn)方程如下:
其中,(a,b)為圓心坐標(biāo),r為圓的半徑,(a,b,r)為圓的3個(gè)參數(shù),分別是圓心坐標(biāo)和半徑。隨機(jī)Hough變換(RHT)圓檢測(cè)算法需要在邊緣點(diǎn)集合中隨機(jī)采樣3個(gè)點(diǎn)(x1,y1)、(x2,y2)、(x3,y3),再將隨機(jī)選取的3個(gè)點(diǎn)代入圓的方程中,可以得到如下方程組:
求解以上方程組可求得圓的3個(gè)參數(shù)(a,b,r),即圓心坐標(biāo)和圓半徑。然后計(jì)算邊緣上的其他點(diǎn)到圓心的距離d,并與所得參數(shù)r進(jìn)行比較,若滿(mǎn)足|d-r|≤δ,δ為設(shè)定的誤差閾值,則該圓為候選圓。否則,重新采樣。隨后將其他邊緣點(diǎn)執(zhí)行相同的過(guò)程,并統(tǒng)計(jì)在預(yù)設(shè)誤差范圍內(nèi)的邊緣點(diǎn)的個(gè)數(shù),當(dāng)邊緣點(diǎn)個(gè)數(shù)累積達(dá)到設(shè)定閾值時(shí),確定該圓為真實(shí)圓;否則,重新采樣。重復(fù)上述步驟,直至所有的真實(shí)圓檢測(cè)完成,或者是重復(fù)次數(shù)達(dá)到最大迭代次數(shù)。
2 本文的KR圓檢測(cè)算法
本文的圓檢測(cè)算法主要分為兩個(gè)部分:一是通過(guò)k-means聚類(lèi)算法對(duì)邊緣點(diǎn)進(jìn)行聚類(lèi),得到每個(gè)圓的ROI;二是在每個(gè)圓的ROI基礎(chǔ)上采用隨機(jī)Hough變換算法檢測(cè)圓,從而得到多個(gè)圓的圓心和半徑。
2.1 邊緣點(diǎn)聚類(lèi)
在工程實(shí)踐中,工程背景相對(duì)復(fù)雜,在復(fù)雜環(huán)境拍攝的圖像存在不同程度的噪聲,導(dǎo)致檢測(cè)過(guò)程中的計(jì)算量劇增。為了緩解上述復(fù)雜背景問(wèn)題,首先對(duì)圓所在區(qū)域進(jìn)行提取。通過(guò)對(duì)原始圖像進(jìn)行一系列預(yù)處理,包括灰度化和中值濾波處理,減少了隨機(jī)噪聲對(duì)后期處理的影響;對(duì)濾波后的圖像進(jìn)行Canny邊緣檢測(cè),得到二值圖像,并收集所有邊緣點(diǎn)構(gòu)造邊緣點(diǎn)集;對(duì)邊緣點(diǎn)的數(shù)據(jù)采用k-means聚類(lèi)算法進(jìn)行聚類(lèi),方法描述如下。
(1)在邊緣點(diǎn)集中隨機(jī)選取k個(gè)點(diǎn)作為初始聚類(lèi)的簇心。
(2)分別計(jì)算每個(gè)樣本點(diǎn)到k個(gè)簇心的距離(本文取歐式距離),找到離該點(diǎn)最近的簇核心,將它歸屬到對(duì)應(yīng)的簇。
(3)所有點(diǎn)都?xì)w屬到簇后,邊緣點(diǎn)就被分為k類(lèi)。之后重新計(jì)算每個(gè)簇的中心,將其定義為新的簇核心。
(4)反復(fù)迭代步驟(2)和(3),直到達(dá)到某個(gè)中止條件。
2.2 ROI分區(qū)獨(dú)立采樣
傳統(tǒng)的隨機(jī)Hough變換(RHT)圓檢測(cè)算法是在當(dāng)前所有邊緣點(diǎn)中隨機(jī)采樣3個(gè)點(diǎn),但是在多個(gè)圓的情況下會(huì)有大量無(wú)效采樣。為緩解以上無(wú)效采樣問(wèn)題,本文提出分區(qū)采樣的方法。通過(guò)k-means聚類(lèi)算法對(duì)邊緣點(diǎn)進(jìn)行聚類(lèi),每個(gè)圓的邊緣點(diǎn)都有屬于本身的聚類(lèi)中心,再以此聚類(lèi)中心點(diǎn)為中心,做一個(gè)可以囊括該類(lèi)所有中心點(diǎn)的正方形,作為該圓的ROI。采樣時(shí),只在該類(lèi)邊緣點(diǎn)所在的ROI區(qū)域內(nèi)部采樣,大幅度提高采樣效率,減少無(wú)效采樣。具體步驟如下。
(1)以聚類(lèi)算法得到的k個(gè)點(diǎn)作為中心,分別以該類(lèi)中距離中心點(diǎn)最遠(yuǎn)的點(diǎn)到該中心的距離為半邊長(zhǎng),得到該類(lèi)邊緣的區(qū)域邊框,即該圓的ROI。
(2)在圓對(duì)應(yīng)的ROI區(qū)域內(nèi)分別隨機(jī)采樣3個(gè)邊緣點(diǎn),并確保3點(diǎn)不共線。
(3)將采樣得到的邊緣點(diǎn)代入公式(5)、公式(6)、公式(7)計(jì)算圓的參數(shù)。
其中,(a,b,r)分別為圓的橫縱坐標(biāo)及圓心。
2.3 真圓的判定
通過(guò)統(tǒng)計(jì)位于候選圓上的邊緣點(diǎn)數(shù)目,對(duì)候選圓進(jìn)行判斷,即如果邊緣點(diǎn)位于該候選圓的圓心距離等于半徑,則認(rèn)為邊緣點(diǎn)在候選圓上,否則,邊緣點(diǎn)不在候選圓上。
考慮到數(shù)字化誤差,應(yīng)留有一個(gè)小余量,判斷邊緣點(diǎn)是否在候選圓上應(yīng)滿(mǎn)足公式(8)。
其中,(xe,ye)是邊緣點(diǎn)坐標(biāo),(a,b)為候選圓圓心坐標(biāo)。
將統(tǒng)計(jì)的位于候選圓上的邊緣點(diǎn)數(shù)目與判定為真圓的相關(guān)閾值進(jìn)行對(duì)比,從而確定候選圓的真假性,若候選圓上的邊緣點(diǎn)數(shù)目大于等于判定閾值,則候選圓為真圓,否則,候選圓不是真圓。即
Ne≥NT 候選圓為真圓other? ?候選圓為假圓 (9)
其中,Ne為統(tǒng)計(jì)得到的在候選圓上的邊緣點(diǎn),NT為設(shè)定的數(shù)量閾值。
3 試驗(yàn)驗(yàn)證與結(jié)果分析
為了驗(yàn)證本文算法的檢測(cè)效果,我們采用多幅合成圖像進(jìn)行測(cè)試,并與RHT圓檢測(cè)算法在檢測(cè)時(shí)間和檢測(cè)精確度上進(jìn)行比較。實(shí)驗(yàn)?zāi)康氖峭ㄟ^(guò)圓檢測(cè)算法實(shí)現(xiàn)在對(duì)圖像中圓的精確檢測(cè),實(shí)驗(yàn)所用計(jì)算機(jī)處理器為Intel(R)Core(TM)i5-4210M CPU @2.6 GHz,8 GB RAM,運(yùn)行環(huán)境為Python 3.6。
3.1 圓的ROI區(qū)域獲取
對(duì)原圖像1(a)進(jìn)行灰度化和Canny邊緣檢測(cè),得到如圖1(b)所示的邊緣圖像,采用k-means聚類(lèi)算法對(duì)所有的邊緣點(diǎn)進(jìn)行聚類(lèi)處理,從而得出k個(gè)聚類(lèi)中心,在此基礎(chǔ)上按照ROI分區(qū)獨(dú)立采樣方法獲得圓的ROI(如圖2所示)。
3.2 試驗(yàn)結(jié)果對(duì)比
首先利用圓的ROI區(qū)域獲取方法獲取圓的ROI,在每個(gè)圓的ROI內(nèi)分區(qū)獨(dú)立采樣,然后分別采用隨機(jī)Hough變換圓檢測(cè)算法對(duì)每個(gè)ROI進(jìn)行圓檢測(cè),使用的圖像如圖3所示,本文對(duì)圖像的檢測(cè)效果如圖4所示,算法各環(huán)節(jié)耗時(shí)見(jiàn)表1,與傳統(tǒng)的隨機(jī)Hough變換圓檢測(cè)算法對(duì)比,檢測(cè)時(shí)間見(jiàn)表2,算法運(yùn)行時(shí)間與圓個(gè)數(shù)的關(guān)系如圖5所示。
本文算法與RHT算法在不同個(gè)數(shù)的合成標(biāo)準(zhǔn)圓的圖像上(如圖3所示)進(jìn)行比較,從試驗(yàn)結(jié)果可知,本文提出的KRA在總的檢測(cè)時(shí)間上比RHT略高(如圖5所示),經(jīng)過(guò)實(shí)驗(yàn)對(duì)比分析KRA算法的各個(gè)關(guān)鍵環(huán)節(jié)(見(jiàn)表1),其中前處理耗時(shí)最長(zhǎng),在4張測(cè)試圖像中占比分別為77.69%、69.50%、64.46%和56.27%。縱向比較前處理時(shí)間占比可以發(fā)現(xiàn),隨著圓個(gè)數(shù)的增加,處理時(shí)間增加幅度很小的同時(shí),在整個(gè)算法的占比不斷減小。從圖5可以看出,KRA的主要部分即聚類(lèi)和圓檢測(cè)時(shí)間一直低于直接RHT算法的檢測(cè)時(shí)間,可以得知,KRA縮小了隨機(jī)采樣的像素空間,成功地緩解了RHT圓檢測(cè)無(wú)效積累嚴(yán)重的問(wèn)題。
3.3 算法性能分析
通過(guò)以上實(shí)驗(yàn)結(jié)果和實(shí)驗(yàn)數(shù)據(jù)表明,本文提出的方法在多個(gè)圓同時(shí)存在的情況下具有優(yōu)勢(shì)。通過(guò)對(duì)圓的ROI提取,很好地解決了由于邊緣點(diǎn)數(shù)量大帶來(lái)的無(wú)效采樣劇增的問(wèn)題;ROI分區(qū)采樣是完全隨機(jī)采樣和約束采樣的一種折中方法,既能將所有的邊緣點(diǎn)分區(qū),又能在ROI內(nèi)實(shí)現(xiàn)局部隨機(jī)采樣,大大減少無(wú)效采樣積累,提高圓檢測(cè)速度。
4 結(jié)語(yǔ)
本文提出的多圓檢測(cè)算法結(jié)合了k-means和隨機(jī)Hough變換圓檢測(cè)算法的優(yōu)點(diǎn),既能將所有邊緣點(diǎn)進(jìn)行ROI分區(qū),又能在ROI內(nèi)隨機(jī)采樣,提高了采樣的有效性。試驗(yàn)結(jié)果證明,本文提出的方法在速度上比傳統(tǒng)的隨機(jī)Hough變換圓檢測(cè)算法更有優(yōu)勢(shì),尤其是在圓個(gè)數(shù)較多的情況下優(yōu)勢(shì)非常明顯。但是本文算法仍然存在不足,在使用k-means聚類(lèi)算法對(duì)邊緣點(diǎn)進(jìn)行聚類(lèi)時(shí)需要指定k值的大小,即圓的個(gè)數(shù),從而一定程度上限制了算法的適應(yīng)性。因此,后續(xù)還需要對(duì)算法進(jìn)行改進(jìn)和研究。
參 考 文 獻(xiàn)
[1]Smereka M,Duleba I.Circular object detection us-ing a modified Hough transform[J].International Journal of Applied Mathe matics and Computer Sc-ience,2008,18(1):85.
[2]XU L,OJA E,KULTANEN P.A new curve detec-tion method:randomized Hough transform(RHT)[J].Pattern Recognition Letters,1990,11(5):331-338.
[3]何奎.基于圖像處理技術(shù)的圓環(huán)零件檢測(cè)方法研究 [D].大連:大連理工大學(xué),2017.
[4]周勇亮,金燕,何萍,等.隨機(jī)Hough變換圓檢測(cè)累計(jì)加速算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2014,26(4):574-580.
[5]Chen The-Chuan,Chung Kuo-Lian.An efficient ra-ndomized algorithm for detecting circles[J].Comp-uter Vision and Image Understanding,2001,83(2):172-191.
[6]Kimme C,Ballard D,Sklansky J.Finding circles by an array of accumulator[J].Commun.ACM,1975,18(2):120-122.
[7]Huang YH,Chuang KL,Yang WN,Chiu SH.Effi-cient symmetry-based screening strategy to speed up randomized circle-detection[J].Pattern Recog-nition Letters,2012,33(16):2071-2076.
[8]Yuan B,Liu M.Power histogram for circle detect-ion on images[J].Pattern Recognition,2015,48(10):3268-3280.