，

(浙江工業(yè)大學(xué) 信息工程學(xué)院，浙江 杭州 310023)

在機器視覺領(lǐng)域中，圓檢測是一種重要的檢測手段.圓檢測的方法有很多種，應(yīng)用最廣泛的圓檢測是Hough變換.Hough變換不僅可以用在檢測直線[1]、PCB板的圓Mark點定位[2]以及焊孔缺陷的檢測[3]上，還可以用在圖像的傾斜矯正[4]上.Hough變換的抗干擾能力強，是圓檢測的常用算法.由于當(dāng)Hough變換的參數(shù)空間大于或等于三維時(比如檢測圓)，Hough變換的計算量和所需內(nèi)存大小將大大提高.針對這些問題，Xu等[5-6]提出了隨機霍夫變換，然而隨機霍夫變換的隨機采樣會帶來大量的無效采樣和累積.舒龍慶等[7]提出了基于圓的對稱性的圓檢測算法.周冬躍等[8]提出了基于粒子群優(yōu)化算法的快速圓檢測算法.作為目前為止OpenCV中的唯一一種圓檢測算法[9]，21HT將檢測圓的過程分成了兩部分，首先利用圖像的梯度信息投票檢測圓心，然后通過圓心計算半徑，減少了霍夫空間的維度.因此，不僅21HT的內(nèi)存占用比標(biāo)準(zhǔn)霍夫變換小，而且檢測速度大大超越了標(biāo)準(zhǔn)霍夫變換.但是21HT的半徑檢測來源于圓心的檢測，而圓心的檢測依賴于穩(wěn)定的局部梯度，如果梯度出現(xiàn)一些噪聲，則不能正確地檢出圓，并且21HT不能檢測同心圓.為了解決這些問題，提出了一種新型的基于圓弧特征的圓檢測方法.

目前，主流的圓檢測算法對每個像素點都進(jìn)行相同的檢測，會產(chǎn)生大量無效的運算處理.文中新型的圓檢測算法主要通過邊緣信息分析來提取圓弧，先通過打斷分叉邊緣得到便于存儲和分析的單向邊緣鏈.從圓弧的特征出發(fā)，利用圓弧固有的特征，只提取具有圓弧特征的邊緣進(jìn)行圓檢測，并通過對每一條圓弧坐標(biāo)數(shù)據(jù)的有序存放從而實現(xiàn)高效并準(zhǔn)確地處理圓弧坐標(biāo)數(shù)據(jù).通過最小二乘法和三點定圓相結(jié)合的方式提取圓弧邊緣并得到每一條圓弧邊緣對應(yīng)的圓心坐標(biāo)和圓半徑.最后利用圓弧的圓心坐標(biāo)和圓半徑將屬于同一個圓的圓弧進(jìn)行聚類，并利用最小二乘法將其圓弧擬合得到所求圓.

1 基于圓弧邊緣特征的圓檢測算法

1.1 圖像預(yù)處理以及邊緣特征提取

在圓檢測的過程中，圖像預(yù)處理是一個非常重要的步驟.在實際中，待處理的圖像是彩色的，首先，需要將彩色圖像轉(zhuǎn)化成灰度圖，然后將灰度圖進(jìn)行高斯濾波，最后通過canny算子提取二值化邊緣圖像.

1.2 打斷分叉邊緣鏈

為了實現(xiàn)對圓弧特征邊緣坐標(biāo)的提取和有序存放，需要提取單方向的邊緣鏈.在二值化邊緣圖像中，存在很多的分叉邊緣，如圖1所示，這些分叉鏈中有一些是圓弧邊緣和其他邊緣的重疊形成的，這些分叉的邊緣不利于邊緣鏈的存儲和后期圓檢測的進(jìn)行.新的圓檢測算法提出一種8鄰域編碼方法判斷分叉點，并將分叉的連接點去除，從而獲得無分叉的單一方向的邊緣鏈.通過遍歷可知，當(dāng)邊緣點的八鄰域中值非零(即值為255)鄰域數(shù)≤2時，該邊緣點是必定不是分叉點，當(dāng)非零鄰域數(shù)≥5時必定是分叉點.當(dāng)邊緣點的非零鄰域數(shù)為3或者4時采用查表法判斷是否為分叉點.

圖1 分叉邊緣鏈Fig.1 Bifurcated edges

首先將8鄰域進(jìn)行編碼，如圖2所示.從左上角開始，從左到右，從上到下分別為1，2，4，8，16，32，64，128.計算值非零鄰域數(shù)為3或者4的所有組合中鄰域中心不是分叉點的非零鄰域編碼和，記錄得到非分叉點編碼表，如表1，2所示.

圖2 8鄰域編碼表Fig.2 Coding table of eight neighborhoods

Table1Anonbifurcationpointcodingtablewith3neighbornumber

序號123456Ⅰ141925283842Ⅱ445256677073Ⅲ8498100112131137Ⅳ145146152193194200

表2八鄰域中灰度值非零鄰域數(shù)為4的非分叉點編碼表

Table2Anonbifurcationpointcodingtablewith4neighbornumber

序號1234Ⅰ4660102116Ⅱ147153195201

然后對二值化圖像圖3(a)進(jìn)行3×3窗口掃描圖3(b)，得到8鄰域中非零鄰域數(shù)N，并將8鄰域中值不是0的鄰域編碼累加得累加數(shù)S見圖3(c)，如果非零鄰域數(shù)N≤2，則認(rèn)為該點不是分叉點，不對其做處理，如果非零鄰域數(shù)為N=3或4，則查看累加數(shù)S是否在編碼表中，如果S在編碼表中則該點不是分叉點，如果不在編碼表中則該點是分叉點并將該點像素點的值置為0.如果非零鄰域數(shù)N≥5，則該點是分叉點并將該點像素點的值置為0見圖3(d).經(jīng)過以上的處理后，就可以將分叉連接點去除，將一條分叉鏈打斷成多條單方向邊緣鏈.

圖3 去除連接點Fig.3 Removal of join points

1.3 類圓弧邊緣鏈提取和有序存放

在1.2節(jié)得到的二值化邊緣圖像中，存在很多邊緣鏈，有的邊緣鏈?zhǔn)菆A弧形成的(以下稱這些邊緣鏈為類圓弧)，有的邊緣鏈?zhǔn)窃肼曇?，還有一些邊緣鏈?zhǔn)菆A弧和其他噪聲邊緣連接形成的，排除掉那些不是圓弧的邊緣鏈對算法的速度和精度的提高有重大意義.因此，提出一種方法提取有效的類圓弧邊緣鏈并且將邊緣鏈按照邊緣鏈生長方向存儲在序列中.傳統(tǒng)的圓檢測算法中，并不是對邊緣鏈進(jìn)行處理的，而是對所有邊緣坐標(biāo)同一進(jìn)行處理，導(dǎo)致增加了大量無效的運算.通過對邊緣鏈的有序采集和存儲從而對邊緣鏈的有針對性的處理提供了基礎(chǔ).

研究圓弧的邊緣鏈可以發(fā)現(xiàn)：將圓弧以水平直徑開始每隔90度分成4部分，當(dāng)按照從上往下的方向開始掃描時，左上部分圓弧的像素點走向只有向左、向左下和向下3種方向；右上部分圓弧的像素點走向只有向右、向右下和向下3種方向；左下部分圓弧的像素點走向只有向右、向右下和向下3種方向；右下部分的圓弧的像素點的走向只有向左、向左下、向下3種方向，如圖4所示.

圖4 圓弧像素的生長方向Fig.4 The growth direction of the pixels of the arc

從上往下掃描的時候，這4部分圓弧總共只有2種走向(向左、向左下和向下；向右、向右下和向下)，符合這2種走向的邊緣鏈稱為類圓弧邊緣鏈.將符合這2種走向的邊緣鏈提取出來可以避免處理大量無效邊緣鏈，從而加快檢測速度.新的圓檢測算法優(yōu)先提取向左、向左下和向下方向的邊緣鏈，如果沒有找到則再嘗試提取向右、向右下和向下方向的邊緣鏈.如果是一個完整的圓，經(jīng)過檢測算法后會被分成4條圓弧鏈分別保存在4個不同序列中.該方法將邊緣鏈按照邊緣生長方向存儲在序列中，這將更加有效且快速地處理邊緣鏈.以往的算法只能隨機地選擇點或者遍歷所有的點來擬合圓就是因為沒有將邊緣鏈按照邊緣生長順序存儲，不僅會引入大量的無效計算，而且精度也不高.新的圓檢測算法將邊緣鏈有序存儲，方便后面處理邊緣鏈的時候可以有選擇地處理一些關(guān)鍵點坐標(biāo).這樣可以提高處理的準(zhǔn)確度和處理效率，減少處理時間.

通過這一步，將得到一個序列的集合，集合中的每一個序列都存著一個類圓弧的有序坐標(biāo)序列.這里的有序是指每一個序列中的坐標(biāo)都是按照類圓弧生長的方向存放的(比如序列的頭和尾分別存放類圓弧的頭坐標(biāo)和尾坐標(biāo)).

1.4 類圓弧初步檢測

類圓弧檢測之后，將這些序列按照序列的長度從大到小排序，將長度過小的序列從集合中除去.在1.3節(jié)得到的類圓弧鏈中，有一些不是真正的圓弧，在這部分中將去除不是圓弧的類圓弧.

如果類圓弧序列的長度為L，取出該序列的第一個坐標(biāo)P1(x1,y1)，第L/4個坐標(biāo)P2(x2,y2)，第L/2個坐標(biāo)P3(x3,y3)，第3L/4個坐標(biāo)P4(x4,y4)，序列的最后一個坐標(biāo)P5(x5,y5).先通過P1，P3，P5三點求得圓心Cmax(cmx,cmy)及半徑Rmax，通過P1，P2，P3求得圓心C1(cx1,cy1)和半徑R1，通過P2，P3，P4求得圓心C2(cx2,cy2)和半徑R2，通過P3，P4，P5求得圓心C3(cx3,cy3)和半徑R3，求3個圓心距離的平方和得

Pdec=(cx1-cx2)(cx1-cx2)+(cy1-cy2)(cy1-cy2)+

(cx1-cx3)(cx1-cx3)+(cy1-cy3)(cy1-cy3)+

(cx2-cx3)(cx2-cx3)+(cy2-cy3)(cy2-cy3)

(1)

半徑距離的平方和得

Rdec=(R1-R2)(R1-R2)+(R1-R3)(R1-R3)+

(R2-R3)(R2-R3)

(2)

Pdec與Rdec的比值為

Xdec=Pdec/Rdec

(3)

如果Pdec和Rdec同時小于一個設(shè)定的閾值TH1(與圓半徑有關(guān))，或者Xdec小于閾值TH2，則保留該類圓弧序列并執(zhí)行第一步，否則將該類圓弧序列從集合中除去.

1.5 類圓弧精確檢測

最小二乘法是一種常用的擬合方法，在工業(yè)中有著廣泛的應(yīng)用[10].最小二乘法也可以用于圓檢測上[11].新的圓檢測算法利用最小二乘法擬合與三點定圓相結(jié)合的方式篩選圓弧鏈.對每一條類圓弧序列分別使用最小二乘法擬合圓和三點共圓求得，擬合半徑Rls，擬合圓心Cls(clsx,clsy)與三點共圓圓心Cmax(cmx,cmy)及半徑Rmax.計算兩種方法的偏差作為閾值對類圓弧進(jìn)行篩選，即

Dp=(clsx-cmx)(clsx-cmx)+(clsy-cmy)(clsy-cmy)

(4)

Dr=(Rls-Rmax)(Rls-Rmax)

(5)

式中：Dp為的圓心坐標(biāo)偏差度量；Dr為圓半徑的偏差度量.如果Dp大于設(shè)定的閾值THdp或者Dr大于設(shè)定的閾值THdr，則將該序列從集合中刪除.

1.6 合并同圓序列

聚類在圓擬合中是比較常見的[12].在圓檢測中，殘缺圓會形成一個或多個圓弧邊緣，在檢測過程中需要將同屬一個圓的圓弧進(jìn)行聚類以便后續(xù)處理.類圓弧序列中，為了找出同一個圓的所有圓弧邊緣，可以利用半徑和圓心坐標(biāo)的偏差將類圓弧進(jìn)行聚類，即

Dlsp=(clsx-cls2x)(clsx-cls2x)+(clsy-cls2y)(clsy-cls2y)

(6)

Dlsr=(Rls-Rls2)(Rls-Rls2)

(7)

式中：Dlsp為圓心左邊偏差度量；Dlsr為圓半徑偏差度量.集合中任意兩條類圓弧序列如果滿足Dlsp小于設(shè)定的閾值THdlsp且Dlsr小于設(shè)定的閾值THlsr，則認(rèn)為這兩條序列同屬一個圓，將這兩條類圓弧序列合并，直到集合中每一條序列中的坐標(biāo)分別屬于不同的圓.

1.7 排除短圓弧

將1.6節(jié)中得到的集合中的每一條序列分別作最小二乘法擬合圓，得到每一條序列中對應(yīng)的擬合半徑Rls以及擬合圓心(clsx,clsy).假設(shè)序列的坐標(biāo)數(shù)為N，設(shè)閾值為THls，如果N<2πRls·THls，就將該序列從集合中刪除.最后在每個序列中按一定間隔取坐標(biāo)點計算其到擬合圓心距離以驗證所得擬合圓的誤差，將誤差過大的序列從集合中刪除.

通過以上步驟后，得到的集合中每一個序列對應(yīng)的半徑和圓心都是所求的圓.

2 算法流程

新的圓檢測算法具體流程如下：

1)對進(jìn)行圖像預(yù)處理，得到二值化的邊緣圖像.

2)首先對邊緣進(jìn)行處理，將有分叉的邊緣鏈打斷成無分叉的單向的邊緣鏈.

3)對邊緣鏈進(jìn)行類圓弧檢測，并將檢測到的類圓弧邊緣鏈按照邊緣生長順序存到序列中.

4)將序列中的類圓弧邊緣按照像素點的數(shù)目進(jìn)行排序并將像素點過少的類圓弧移除.

5)通過最小二乘法擬合與三點定圓檢測相結(jié)合的方式過濾掉一些不符合的類圓弧邊緣.

6)對剩下的每一條類圓弧利用最小二乘法擬合求取半徑和圓心并排除掉與三點定圓檢測結(jié)果偏差過大的類圓弧.

7)將半徑和圓心坐標(biāo)的偏差在一定范圍內(nèi)的類圓弧聚成一類(認(rèn)為是同一個圓上的圓弧)，再次進(jìn)行最小二乘法擬合得到半徑r以及圓心坐標(biāo).在序列中按一定比例選取一定數(shù)量的坐標(biāo)點對得到的圓進(jìn)行驗證，過濾掉誤差過大的圓.

8)如果步驟6)所得的圓中參與擬合的像素點的數(shù)目大于一個動態(tài)閾值(2πrj)，則認(rèn)為是該圓是所求圓.

圖5 圓檢測算法流程圖Fig.5 Flow chart of the new circle detection algorithm

3 實驗結(jié)果及分析

實驗環(huán)境采用硬件配置為Intel酷睿i5 480M，主頻2.67 GHz，內(nèi)存為6 GB；軟件配置為Windows 8 64位操作系統(tǒng)，VS 2013軟件開發(fā)平臺.21HT是OpenCV中目前為止唯一一種圓檢測算法，它是一種非常優(yōu)秀的改進(jìn)的霍夫變換，在現(xiàn)實中有廣泛的應(yīng)用.在本實驗中使用OpenCV中的21HT與提出的圓檢測算法進(jìn)行比較.

3.1 實驗1

為了驗證新型圓檢測算法的準(zhǔn)確性、速度以及抗干擾性，實驗中采用了大小為400像素X550像素的合成圖片以及在原圖中加入10 000個噪聲的合成圖片.原圖如圖6(a)中所示，噪聲圖片如圖6(d)所示，其中共有7個圓，包括同心圓、殘缺圓、相交圓.圖6(b，c)分別為21HT算法和新型圓檢測算法在原圖中圓檢測效果，圖6(e，f)分別為21HT算法和新型圓檢測算法在噪聲圖片中的圓檢測效果，表3為2種算法在加入噪聲前后的檢測準(zhǔn)確度和檢測速度的對比實驗結(jié)果，表4為2種算法的抗干擾性能對比結(jié)果.

圖6 圓檢測算法效果Fig.6 Experiment on the images

圓檢測結(jié)果對比算法原圖圓數(shù)量/個檢測出圓數(shù)量/個正確檢測數(shù)量/個檢測正確率/%運行時間/ms未加入噪點21HT76685.7131.47新型算法77710010.23加入噪點后21HT76685.7140.51新型算法77710010.45

表4 圓檢測誤差Table 4 Error of circle detetion results 像素

3.2 實驗2

為了驗證該算法對實際圖片的檢測能力，使用拍攝的照片進(jìn)行圓檢測.實驗采用778像素×656像素的拍攝照片以及加入10 000個噪聲的照片.原照片如圖6(a)中所示，加入噪聲后的照片如圖7(d)所示，其中一共有4個圓.圖7(b，c)分別為21HT算法和新型圓檢測算法在照片中的圓檢測效果，圖7(e，f)分別為21HT算法和新型圓檢測算法在加入噪聲后的圓檢測效果，表5為2種算法在加入噪聲前后的檢測準(zhǔn)確度和檢測速度的對比實驗結(jié)果.

3.3 實驗分析

實驗表明：新型圓檢測算法對同心圓、殘缺圓以及相交圓都具有良好的檢測性能.新型圓檢測算法不僅正確率高于21HT算法，而且檢測速度較21HT有很大的提升.新型圓檢測算法對加入噪聲后的圖片有較強的檢測穩(wěn)定性，具有較強的抗干擾能力.

圖7 圓檢測算法效果Fig.7 Experiment on the images

圓檢測結(jié)果對比算法原圖圓數(shù)量/個檢測出圓數(shù)量/個正確檢測數(shù)量/個檢測正確率/%運行時間/ms未加入噪點21HT4225089.32新型算法44410022.68加入噪點后21HT4225083.63新型算法44410023.13

4 結(jié) 論

提出的檢測圓的方法從圓弧的特性出發(fā)，只檢測具有圓弧特性的邊緣，因此提升了檢測效率和準(zhǔn)確性.通過打斷分叉邊緣鏈以及根據(jù)圓弧邊緣特性的方法提取邊緣鏈并完成邊緣坐標(biāo)的有序存放，在此基礎(chǔ)上利用最小二乘法擬合與三點定圓相結(jié)合的方式篩選圓弧鏈.然后將半徑和圓心坐標(biāo)的偏差在一定范圍內(nèi)的圓弧聚成一類，對其最小二乘法擬合得到求圓.該方法檢測速度快，穩(wěn)定性高，抗干擾能力強，可以在一張圖像中檢測多個圓、殘缺圓、同心圓以及相交圓.

[1] 張江鑫,沈小蘭,王輝,等.快速隨機Hough變換多直線檢測算法[J].浙江工業(yè)大學(xué)學(xué)報,2013,41(3):346-350.

[2] 陳戈珩,李華杰,房曉偉,等.基于相位一致性和Hough圓的貼片機視覺定位系統(tǒng)的研究[J].科學(xué)技術(shù)與工程,2015,15(27):59-63.

[3] 吳全玉,周署,俞洋,等.Hough算法在印刷電路板焊孔缺陷檢測中的應(yīng)用[J].工業(yè)儀表與自動化裝置,2015(6):56-59.

[4] 高宇鵬,李益明,胡眾義,等.基于Hough變換傾斜文檔校正的改進(jìn)方法[J].浙江工業(yè)大學(xué)學(xué)報,2013,41(1):106-109.

[5] XU L, OJA E, KULTANEN P. A new curve detection method: randomized Hough transform (RHT) [J]. Pattern recognition letters,1990,11(5):331-338.

[6] XU L, OJA E. Randomized Hough Transform (RHT): basic mechanisms, algorithms, and computational complexities [J]. Computer vision & image understanding,1993,57(2):131-154.

[7] 舒龍慶,曾垂力.一種基于圓的幾何特性改進(jìn)的圓檢測隨機算法[J].集成技術(shù),2015(2):46-49.

[8] 周冬躍,陳健明,林福民,等.一種基于粒子群優(yōu)化算法的快速圓檢測方法[J].光電子·激光,2016(9):949-956.

[9] 秦開懷,王海潁,鄭輯濤.一種基于Hough變換的圓和矩形的快速檢測方法[J].中國圖象圖形學(xué)報,2010(1):109-115.

[10] 石希,趙殿鵬,徐婕,等.基于最小二乘法的混凝土相關(guān)性曲線的研究[J].浙江工業(yè)大學(xué)學(xué)報,2014,42(4):388-392.

[11] 陳明晶,方源敏,陳杰,等.最小二乘法和迭代法圓曲線擬合[J].測繪科學(xué),2016,41(1):194-197.

[12] 孫國棟,楊林杰,張楊,等.基于三點迭代的聚類圓擬合算法[J].制造業(yè)自動化,2015(13):76-78.