鄧仕超， 高 陽， 韓海媚

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

0 引言

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

1 RANSAC算法

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

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

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

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

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

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

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

2 改進的RANSAC算法

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

2.1 圖像預處理

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

圖1 待檢測凹痕圖像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 三點估計圓參數(shù)

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

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

(1)

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

2.3 尋找候選圓

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

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

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

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

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

2.5 本文算法的具體步驟

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

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

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

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

5)Nt=Nt+1,若Nt≥4，則結(jié)束循環(huán)，轉(zhuǎn)8)；若Nt=1，則計算邊界點到該候選圓的圓心的距離d，從邊界點點集D中排除滿足|d-r|>ε2的點，再轉(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) 對各候選圓局內(nèi)點單元pciri(i=1, 2,…，Nt)分別進行最小二乘法圓擬合，將得到的新的候選圓參數(shù)pi=[ai,bi,ri]作為一個單元存入候選圓參數(shù)單元集P中，計算各候選圓的局內(nèi)點到由該候選圓重新擬合出的圓心[ai,bi]的距離di，從這些局內(nèi)點中找出滿足|di-ri|≤ε3的局內(nèi)點，并排除pciri中其他的點.初始化候選圓局內(nèi)點數(shù)目集NP=NULL，將新的候選圓局內(nèi)點的個數(shù)存入NP中.比較各候選圓的局內(nèi)點個數(shù)，找出局內(nèi)點個數(shù)最大的候選圓，并將其參數(shù)[ai,bi,ri]作為最終得到的真實圓的圓參數(shù).

3 實驗結(jié)果

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

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

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

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

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

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

4 結(jié)論

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

[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] 王新，張元東，王莉．一種隨機Hough變換檢測圓的優(yōu)化方法[J]．測控技術(shù)，2016，35(6)：112-116．

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

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

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

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

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

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

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

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