改進(jìn)的RANSAC圓檢測(cè)算法

鄧仕超， 高 陽(yáng)， 韓海媚

(桂林電子科技大學(xué) 機(jī)電工程學(xué)院 廣西 桂林 541004)

0 引言

圖像處理中常用的圓檢測(cè)算法有：基于Hough變換的圓檢測(cè)[1-2]算法;基于隨機(jī)抽樣一致性(random sampling consistency,RANSAC)算法的圓檢測(cè).Hough變換圓檢測(cè)算法要遍歷三維參數(shù)空間，對(duì)內(nèi)存和時(shí)間的消耗特別大，且檢測(cè)結(jié)果精度受參數(shù)離散化程度的影響也大.文獻(xiàn)[3]提出了隨機(jī)Hough變換(RHT)算法，該算法隨機(jī)抽取圖像空間中的3個(gè)點(diǎn)，對(duì)應(yīng)到參數(shù)空間中的1個(gè)點(diǎn)，再?gòu)膮?shù)空間中選取候選圓并進(jìn)一步挑出真實(shí)圓，從而大大減少了內(nèi)存消耗.RANSAC算法[4]與RHT算法相似，但其抽樣的目的在于估計(jì)出一個(gè)能包含盡可能多的邊界點(diǎn)的圓模型，只用圓模型上的點(diǎn)來(lái)擬合真實(shí)圓.這兩種算法的共同缺點(diǎn)在于大量圓外點(diǎn)會(huì)帶來(lái)大量無(wú)效抽樣和累積.文獻(xiàn)[5]用梯度法預(yù)先判斷3點(diǎn)是否在候選圓上，減少了無(wú)效采樣，但計(jì)算梯度本身也要消耗不少時(shí)間.文獻(xiàn)[6]則對(duì)每條連續(xù)邊界3等分，再分別取點(diǎn)進(jìn)行圓擬合，該方法僅對(duì)連續(xù)邊界進(jìn)行取樣，大大減少了對(duì)無(wú)效點(diǎn)的抽樣.但這兩種改進(jìn)算法都只用3個(gè)點(diǎn)得到圓參數(shù)，準(zhǔn)確度有限.文獻(xiàn)[7]用最小二乘法改進(jìn)了RHT算法，先用4點(diǎn)確定初始圓參數(shù)，再對(duì)得到的圓上點(diǎn)迭代使用最小二乘法，直至沒(méi)有新點(diǎn)加入，該方法準(zhǔn)確性較好，但所需迭代次數(shù)受初始參數(shù)影響大.本文設(shè)計(jì)了一種改進(jìn)的RANSAC圓檢測(cè)算法，可以進(jìn)一步減少檢測(cè)圓所需時(shí)間并保證其準(zhǔn)確度.

1 RANSAC算法

傳統(tǒng)RANSAC圓檢測(cè)算法的具體步驟如下：

1) 對(duì)待檢測(cè)的圖像進(jìn)行預(yù)處理及邊緣提取，建立由所有邊緣點(diǎn)坐標(biāo)構(gòu)成的點(diǎn)集D.令當(dāng)前循環(huán)次數(shù)k=0.

2) 初始化局內(nèi)點(diǎn)點(diǎn)集Inpts=NULL.從邊界點(diǎn)點(diǎn)集D中隨機(jī)抽取3個(gè)點(diǎn)，計(jì)算這3個(gè)點(diǎn)所確定的圓的參數(shù)[a,b,r](圓心(a,b). 半徑r)，若圓的半徑r的范圍在預(yù)設(shè)的范圍之內(nèi)，則轉(zhuǎn)3)；否則轉(zhuǎn)6).

3) 計(jì)算各邊界點(diǎn)到2)中所得到的圓的圓心的距離d，若|d-r|≤ε(ε為可接受的局內(nèi)點(diǎn)偏離裕度)，則認(rèn)為該點(diǎn)為局內(nèi)點(diǎn)，將其坐標(biāo)存入局內(nèi)點(diǎn)點(diǎn)集Inpts，否則視為局外點(diǎn).

4) 計(jì)算該圓上的局內(nèi)點(diǎn)點(diǎn)數(shù)M，若M大于閾值Mmin，則認(rèn)為此次估計(jì)出的圓模型足夠合理，這些局內(nèi)點(diǎn)也可視為有效點(diǎn)，轉(zhuǎn)5)；否則轉(zhuǎn)6).

5) 對(duì)點(diǎn)集Inpts中的所有點(diǎn)用最小二乘法重新計(jì)算圓的參數(shù)模型，得到最終結(jié)果.

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

2 改進(jìn)的RANSAC算法

傳統(tǒng)RANSAC算法中抽樣耗時(shí)占算法總耗時(shí)的比重較大，而非圓邊界點(diǎn)(即局外點(diǎn))的數(shù)量又是影響所需抽樣次數(shù)的最主要的因素.所以，減少局外點(diǎn)數(shù)量對(duì)減少算法總耗時(shí)有較大作用.另外，傳統(tǒng)算法通過(guò)三點(diǎn)預(yù)估圓方法選取的局內(nèi)點(diǎn)點(diǎn)集的隨意性較大，這使得最終得到的檢測(cè)結(jié)果的隨意性也較大，為改善這一點(diǎn)，可以考慮綜合使用多組局內(nèi)點(diǎn)點(diǎn)集進(jìn)一步地?cái)M合和篩選.本文根據(jù)以上思路對(duì)原算法進(jìn)行改進(jìn).

2.1 圖像預(yù)處理

為減少邊緣提取中偽邊緣帶來(lái)的非圓邊界點(diǎn)，本文在預(yù)處理環(huán)節(jié)中采用陷波濾波[8]，針對(duì)性地濾去圖像中金屬本身的紋路.常用的邊緣提取方法有：1) 使用Sobel、Canny等算子直接提取.2) 使用模糊分割等分割算法進(jìn)行區(qū)域分割[9]，再用形態(tài)學(xué)算法提取邊緣.綜合考慮算法準(zhǔn)確性和耗時(shí)長(zhǎng)短，本文使用Canny檢測(cè)法進(jìn)行邊緣提取.待處理的圖像如圖1所示.提取出的邊緣如圖2所示.從圖中可以看出，凹痕圓的邊界基本被提取，金屬紋路偽邊緣大大減少.接著，為進(jìn)一步減少凹痕固有的小裂紋帶來(lái)的非圓邊界點(diǎn)，本文對(duì)提取出的邊緣進(jìn)行連通域檢測(cè)，并對(duì)檢測(cè)出的所有8鄰接連通區(qū)域進(jìn)行標(biāo)記.8鄰接的示意圖如圖3所示.然后，將這些連通區(qū)域存儲(chǔ)到一個(gè)元胞數(shù)組中，每1個(gè)元胞代表1個(gè)連通區(qū)域(即一條連續(xù)邊界).最后通過(guò)統(tǒng)計(jì)的方法將小邊界去除，僅對(duì)較長(zhǎng)的連續(xù)邊界進(jìn)行抽樣.

圖1 待檢測(cè)凹痕圖像Fig.1 The picture of dent for detection

圖2 圖1中提取的邊緣Fig.2 The extracted edge of Fig.1

圖3 8鄰接示意圖Fig.3 The sketch of 8-adjacency pixels

2.2 三點(diǎn)估計(jì)圓參數(shù)

通常，由三點(diǎn)確定圓參數(shù)的方法是將三點(diǎn)的坐標(biāo)代入圓的方程，聯(lián)立三元方程求解得到.本文則利用圓的圓心到弦的中點(diǎn)的連線垂直于弦這一特性，聯(lián)立二元方程求出圓心坐標(biāo)，然后求圓心到任意一點(diǎn)的距離即可得出半徑.由于只需求解二元方程，比原算法更為簡(jiǎn)便.

假設(shè)圓心坐標(biāo)為Z(a,b)，三點(diǎn)坐標(biāo)分別為A(x1,y1)，B(x2,y2)，C(x3,y3)，可以得到二元方程：

(1)

從而可以很容易地得到圓心坐標(biāo)(a,b)，而半徑即為[5]

2.3 尋找候選圓

在判定某點(diǎn)是否屬于局內(nèi)點(diǎn)時(shí)，本文由原判定公式|d-r|≤ε，得出(r-ε)2≤d2≤(r+ε)2，若設(shè)某次估計(jì)出的圓的圓心為Z(a,b)，某點(diǎn)坐標(biāo)為I(xi,yi)，則該公式變成(r-ε)2≤(xi-a)2+(yi-b)2≤(r+ε)2，從而避免了原方法中計(jì)算邊界點(diǎn)到圓心的距離d時(shí)的開(kāi)方運(yùn)算，加快了速度.

若抽樣所得圓的局內(nèi)點(diǎn)個(gè)數(shù)大于閾值Mmin，則可判定該圓為候選圓.由于后期還有進(jìn)一步的篩選，閾值可以根據(jù)多次試驗(yàn)的結(jié)果取一個(gè)相對(duì)較小的值以減少抽樣時(shí)間.如果是第一次取到候選圓，我們可以綜合原來(lái)判定候選圓局內(nèi)點(diǎn)時(shí)的閾值ε估計(jì)出一個(gè)閾值ε2(ε2>ε)，并認(rèn)為滿足|d-r|>ε2的點(diǎn)不屬于所求圓的邊界并將其排除，僅對(duì)剩下的點(diǎn)抽樣以進(jìn)一步提高后續(xù)抽樣取到候選圓的概率.實(shí)驗(yàn)證明，在第一次得到候選圓后，可以很容易地連續(xù)得到候選圓.

如果在隨機(jī)抽樣中，已經(jīng)有3～4次能夠得到候選圓，那么真實(shí)圓的邊緣存在于這些候選圓局內(nèi)點(diǎn)中的概率就已經(jīng)很大了.再繼續(xù)抽樣的意義不大.為控制總的檢測(cè)時(shí)間，本文以4次為閾值，只要4次取到候選圓，就可以結(jié)束抽樣循環(huán)

2.4 確定最終圓參數(shù)

得到候選圓后，用最小二乘法對(duì)以上候選圓的局內(nèi)點(diǎn)再進(jìn)行圓擬合，可以得到更為精準(zhǔn)的候選圓[10].然后，設(shè)定一個(gè)很小的距離閾值ε3(ε3<ε)，把原局內(nèi)點(diǎn)中到新圓的邊緣的徑向距離小于閾值ε3的點(diǎn)作為新候選圓的局內(nèi)點(diǎn)，比較各新候選圓局內(nèi)點(diǎn)的個(gè)數(shù)N，選擇N最大的新候選圓作為最終真實(shí)圓.相比原算法只選出一個(gè)候選圓進(jìn)行最小二乘法擬合，本算法對(duì)多個(gè)候選圓進(jìn)行擬合與精選，可以得到更準(zhǔn)確更穩(wěn)定的結(jié)果.

2.5 本文算法的具體步驟

1) 對(duì)待檢測(cè)的圖像進(jìn)行預(yù)處理及邊緣提取，檢測(cè)邊緣點(diǎn)中所有的8鄰接連通區(qū)域，排除長(zhǎng)度較小的連通域，用剩余的較長(zhǎng)的連續(xù)邊界上的點(diǎn)構(gòu)建邊界點(diǎn)集D，初始化候選圓局內(nèi)點(diǎn)單元集Pcir=NULL，候選圓參數(shù)單元集P=NULL，當(dāng)前循環(huán)次數(shù)k=0，候選圓個(gè)數(shù)Nt=0.然后，為最大抽樣次數(shù)Kmax設(shè)定一初始值.

2) 初始化局內(nèi)點(diǎn)點(diǎn)集Inpts=NULL.從邊界點(diǎn)點(diǎn)集D中隨機(jī)抽取3個(gè)點(diǎn)，計(jì)算這3個(gè)點(diǎn)所確定的圓的參數(shù)[a,b,r](圓心(a,b)，半徑r)，若半徑r的范圍在預(yù)設(shè)的圓的半徑范圍之內(nèi)，則轉(zhuǎn)3)；否則轉(zhuǎn)6).

3) 計(jì)算各邊界點(diǎn)到2)中所得到的圓的圓心的距離d，若|d-r|≤ε(ε為可接受的局內(nèi)點(diǎn)偏離圓的邊緣的裕度)，則認(rèn)為該點(diǎn)為局內(nèi)點(diǎn)，將其坐標(biāo)存入局內(nèi)點(diǎn)點(diǎn)集Inpts，否則視為局外點(diǎn).

4) 計(jì)算該圓上的局內(nèi)點(diǎn)點(diǎn)數(shù)M，若M大于閾值Mmin，則認(rèn)為該圓可以作為候選圓，將局內(nèi)點(diǎn)點(diǎn)集Inpts作為一個(gè)單元pcir，存入候選圓局內(nèi)點(diǎn)單元集Pcir，轉(zhuǎn)5)；否則轉(zhuǎn)6).

5)Nt=Nt+1,若Nt≥4，則結(jié)束循環(huán)，轉(zhuǎn)8)；若Nt=1，則計(jì)算邊界點(diǎn)到該候選圓的圓心的距離d，從邊界點(diǎn)點(diǎn)集D中排除滿足|d-r|>ε2的點(diǎn)，再轉(zhuǎn)6)；若1

6)k=k+1，若k>Kmax，則結(jié)束循環(huán)，轉(zhuǎn)7)；否則轉(zhuǎn)2).

7) 若Nt<2，則Kmax自加10，再轉(zhuǎn)2)；否則轉(zhuǎn)8).

8) 對(duì)各候選圓局內(nèi)點(diǎn)單元pciri(i=1, 2,…，Nt)分別進(jìn)行最小二乘法圓擬合，將得到的新的候選圓參數(shù)pi=[ai,bi,ri]作為一個(gè)單元存入候選圓參數(shù)單元集P中，計(jì)算各候選圓的局內(nèi)點(diǎn)到由該候選圓重新擬合出的圓心[ai,bi]的距離di，從這些局內(nèi)點(diǎn)中找出滿足|di-ri|≤ε3的局內(nèi)點(diǎn)，并排除pciri中其他的點(diǎn).初始化候選圓局內(nèi)點(diǎn)數(shù)目集NP=NULL，將新的候選圓局內(nèi)點(diǎn)的個(gè)數(shù)存入NP中.比較各候選圓的局內(nèi)點(diǎn)個(gè)數(shù)，找出局內(nèi)點(diǎn)個(gè)數(shù)最大的候選圓，并將其參數(shù)[ai,bi,ri]作為最終得到的真實(shí)圓的圓參數(shù).

3 實(shí)驗(yàn)結(jié)果

為了檢驗(yàn)本文算法的有效性，用該算法在VS2013平臺(tái)下編寫(xiě)了實(shí)驗(yàn)程序，并將其用于布氏硬度壓痕直徑自動(dòng)化測(cè)量?jī)x器研制中.圖1即為用HB-3000B硬度計(jì)，10 mm直徑淬硬鋼球在用正火處理過(guò)的T10鋼板上壓出的凹痕圖像，實(shí)驗(yàn)載荷為29.42 kN，成像用的CCD像素?cái)?shù)為1 920×1 560.本實(shí)驗(yàn)用該方法在同一塊鋼板上共得到了10個(gè)凹痕(凹痕分布相對(duì)集中).實(shí)驗(yàn)要求測(cè)出凹痕直徑并查表得出布氏硬度值[11].本文分別用上述3種算法對(duì)這10個(gè)凹痕進(jìn)行檢測(cè)，其結(jié)果如表1所示.其中隨機(jī)Hough變換(RHT)圓檢測(cè)算法的具體步驟見(jiàn)文獻(xiàn)[3].

表1中的參考直徑是用讀數(shù)顯微鏡對(duì)這10個(gè)凹痕進(jìn)行測(cè)量所得到的直徑的平均值(括號(hào)內(nèi)為測(cè)量所得直徑的取值范圍).從表中可以看出，本文算法所得直徑相比其他兩種算法更接近參考值，測(cè)量結(jié)果的方差也比其他兩種方法更小.因此，本文算法提高了測(cè)量結(jié)果的準(zhǔn)確性和穩(wěn)定性.從檢測(cè)時(shí)間上看，本文算法的耗時(shí)也明顯比其他兩種算法更短.

表1 3種算法檢測(cè)結(jié)果

用以上3種算法檢測(cè)得到的圓參數(shù)在圖2所示的邊緣圖像上畫(huà)圓，其對(duì)比效果如圖4所示.從圖中可以看出，3種算法檢測(cè)出的圓對(duì)左上角的邊緣的貼合程度有微小差異.為了更清楚地看出這些差異，圖5為圖4左上角的局部放大圖.從圖中可以看出，本文算法所得結(jié)果對(duì)圖像邊緣的貼合效果也優(yōu)于其他兩種算法.

圖4 3種算法擬合的圓的對(duì)比Fig.4 The differences among the fitting circles in three algorithms

圖5 圖4的局部放大圖Fig.5 The partial enlargement of Fig.4

4 結(jié)論

本文對(duì)傳統(tǒng)的RANSAC圓檢測(cè)算法從無(wú)效點(diǎn)的排除、候選圓的選取、真實(shí)圓的確定等方面進(jìn)行了改進(jìn)，實(shí)驗(yàn)結(jié)果表明，該算法結(jié)果在準(zhǔn)確性、穩(wěn)定性、運(yùn)算時(shí)間3個(gè)方面均明顯優(yōu)于傳統(tǒng)RANSAC圓檢測(cè)算法，而且也優(yōu)于目前常用的RHT圓檢測(cè)算法，完全能夠滿足實(shí)時(shí)檢測(cè)需求.

[1] LI G Q，ZHANG L X，YU Z P，et al．Research of edge detection algorithm based on Canny algorithm and Hough transform[J]．Advanced materials research，2014，1039：262-265.

[2] BOUKHAROUBA A．A new algorithm for skew correction and baseline detection based on the randomized Hough transform[J]．Journal of King Saud university-computer and information sciences，2017，29(1)：29-38．

[3] 王新，張?jiān)獤|，王莉．一種隨機(jī)Hough變換檢測(cè)圓的優(yōu)化方法[J]．測(cè)控技術(shù)，2016，35(6)：112-116．

[4] 袁清珂，張振亞，畢慶．改進(jìn)的RANSAC算法在直線擬合中的應(yīng)用[J]．組合機(jī)床與自動(dòng)化加工技術(shù)，2015，1(1)：123-125.

[5] 袁理，曹智睿．改進(jìn)的隨機(jī)Hough變換圓檢測(cè)算法[J]．計(jì)算機(jī)應(yīng)用，2010，30(S1)：174-176．

[6] 陳小艷，王強(qiáng)，李柏林．改進(jìn)的Hough變換檢測(cè)圓方法[J]．計(jì)算機(jī)系統(tǒng)應(yīng)用，2015，24(8)：197-201．

[7] 霍建亮，曾翎，王德勝，等．基于最小二乘法改進(jìn)的隨機(jī)圓檢測(cè)算法[J]．光電工程，2011，38(5)：145-150．

[8] 阮秋琦．?dāng)?shù)字圖像處理學(xué)[M]．北京：電子工業(yè)出版社，2013．

[9] 劉洪普，楊樂(lè)，侯向丹，等．一種改進(jìn)的模糊C均值圖像分割算法[J]．鄭州大學(xué)學(xué)報(bào)(理學(xué)版)，2017，49(2)：66-71．

[10] 牛方君，曹慧慧．利用最小二乘法測(cè)量半徑樣板半徑[J]．電子產(chǎn)品可靠性與環(huán)境試驗(yàn)，2015，33(6)：56-58．

[11] 文九巴．金屬材料學(xué)[M]．北京：機(jī)械工業(yè)出版社，2011．