袁 坤，彭和平

（江漢大學(xué)智能制造學(xué)院，湖北武漢 430056）

0 引言

圓形是自然界中的常見(jiàn)形狀，如硬幣、籃球和交通標(biāo)識(shí)等。圓檢測(cè)是計(jì)算機(jī)視覺(jué)和模式識(shí)別領(lǐng)域的基本問(wèn)題，在產(chǎn)品檢測(cè)、生物信息提取等方面有廣泛應(yīng)用［1-2］。目前圓檢測(cè)有許多算法，其中最常用的為Hough 變換及其改進(jìn)算法。Hough 變換由Paul Hough［3］于1962 年提出，其原理是將二維圖像空間的像素轉(zhuǎn)化到三維參數(shù)空間，然后在累加器中對(duì)圖像中的像素點(diǎn)進(jìn)行投票累計(jì)。在Hough 變換圓檢測(cè)中，二維空間中圖像的每個(gè)像素點(diǎn)都要遍歷三維空間［4］，導(dǎo)致計(jì)算量巨大、耗費(fèi)大量?jī)?nèi)存，因此在多圓的精確檢測(cè)中，經(jīng)典Hough 變換有一定的應(yīng)用局限性。目前，高效率、高準(zhǔn)確度的圓檢測(cè)算法是計(jì)算機(jī)視覺(jué)和模式識(shí)別領(lǐng)域亟需解決的問(wèn)題之一。

1 相關(guān)研究

為解決傳統(tǒng)Hough 變換圓檢測(cè)算法運(yùn)算量大、檢測(cè)精度低的問(wèn)題，國(guó)內(nèi)外學(xué)者進(jìn)行了相關(guān)研究提出一些改進(jìn)算法。例如，文獻(xiàn)［5］提出基于梯度的Hough 變換（Gradient Hough Transform，GHT）的同心圓檢測(cè)算法，在一定程度上減小了計(jì)算量，提高了檢測(cè)精度，但該算法需要提前設(shè)定被檢測(cè)圓的半徑范圍，當(dāng)圖像背景復(fù)雜，如包含多個(gè)不同半徑的圓時(shí)，算法的執(zhí)行效率和識(shí)別準(zhǔn)確度較低；文獻(xiàn)［6］提出一種基于4 個(gè)點(diǎn)的隨機(jī)圓檢測(cè)算法（Randomized Circle Detection，RCD），依據(jù)迭代思想求取圓的參數(shù)。其從邊緣像素點(diǎn)集中隨機(jī)選取4 個(gè)點(diǎn)作為代理點(diǎn)，當(dāng)4 個(gè)代理點(diǎn)均在同一圓模型邊緣上時(shí)，即可得到該圓模型的參數(shù)。相較于Hough 變換及其改進(jìn)算法，RCD 算法顯著減少了運(yùn)算量，對(duì)單一圓的檢測(cè)效率及精度有很大提高。但當(dāng)圖像背景復(fù)雜或包含多個(gè)被檢測(cè)圓時(shí)，4 個(gè)代理點(diǎn)來(lái)自于同一個(gè)圓的可能性很?。?］。此外，在構(gòu)造圓模型后，該算法會(huì)利用全部邊緣點(diǎn)對(duì)模型進(jìn)行驗(yàn)證［8］，導(dǎo)致算法效率低且可重復(fù)性差。

為此，本文對(duì)基于4 個(gè)點(diǎn)的原始RCD 算法進(jìn)行改進(jìn)，提出一種基于曲線擬合的隨機(jī)圓檢測(cè)算法（Curve Fitting based RCD，CFRCD）。該算法結(jié)合概化算法與曲線擬合對(duì)檢測(cè)邊緣進(jìn)行預(yù)篩選和分類，改進(jìn)了原始RCD 算法因選取代理點(diǎn)不在同一個(gè)圓輪廓上而導(dǎo)致無(wú)效迭代次數(shù)過(guò)多的問(wèn)題，提高了算法的執(zhí)行效率。

2 CFRCD算法

2.1 邊緣檢測(cè)

邊緣檢測(cè)是圖像預(yù)處理的重要環(huán)節(jié)，在一定程度上決定著后續(xù)檢測(cè)的準(zhǔn)確度。傳統(tǒng)邊緣檢測(cè)算法，如Canny 邊緣檢測(cè)算法［9］通過(guò)圖像平滑、梯度計(jì)算、非極大抑制及雙閾值邊緣標(biāo)記等方法，可得到較好的二值邊緣圖像。然而，該算法需要設(shè)定雙閾值，邊緣檢測(cè)結(jié)果易受閾值大小的影響。為避免實(shí)驗(yàn)結(jié)果的不確定性，本文采用無(wú)參數(shù)邊緣繪制的EDPF（Edge Drawing Parameter Free）算法［10］，其是基于ED（Edge Drawing）算法［11］改進(jìn)的一種實(shí)時(shí)、無(wú)參數(shù)的邊緣分割檢測(cè)算法，工作原理為將ED 算法參數(shù)設(shè)置為極值，首先檢測(cè)圖像中被稱為錨點(diǎn)的像素點(diǎn)并對(duì)其進(jìn)行連接，然后根據(jù)Helmholtz 原理對(duì)檢測(cè)到的邊緣段進(jìn)行反向驗(yàn)證，從而消除無(wú)效檢測(cè)邊緣，僅留下有意義的圖像邊緣。相較于Canny 邊緣檢測(cè)算法，EDPF 算法可對(duì)圖像邊緣點(diǎn)進(jìn)行有序標(biāo)記，使檢測(cè)邊緣更為精確。測(cè)試圖像及采用EDPF 算法處理后的邊緣圖像分別如圖1、圖2所示。

Fig.1 Test image圖1 測(cè)試圖像

2.2 曲線擬合

Fig.2 Picture after edge processing圖2 處理后邊緣圖像

得到邊緣檢測(cè)圖像后，對(duì)于互不連接的邊緣，通過(guò)連通域分析以及圖像形態(tài)學(xué)操作提取不同邊緣。當(dāng)圖像邊緣為類似測(cè)試圖像中的遮擋圓時(shí)，則無(wú)法通過(guò)這些傳統(tǒng)方法提取各個(gè)圓的邊緣。采用CFRCD 算法，首先通過(guò)概化算法以一系列線段近似替代提取的邊緣曲線，使用Visvalingam-Whyatt（V-M）概化算法［12］對(duì)提取的邊緣進(jìn)行曲線擬合。該算法原理為計(jì)算圖像邊緣點(diǎn)中的某一中心像素點(diǎn)與前后鄰近像素點(diǎn)所構(gòu)成的三角形面積，并與設(shè)定閾值進(jìn)行比較，若三角形面積大于閾值，則分別對(duì)這3 個(gè)像素點(diǎn)構(gòu)成的兩像素區(qū)域各自取其中間像素點(diǎn)，再與之前中心像素點(diǎn)構(gòu)成三角形并重復(fù)上述步驟，直至三角形面積不大于閾值為止。完成對(duì)邊緣輪廓上的像素點(diǎn)標(biāo)記后，通過(guò)線段連接相鄰像素點(diǎn)完成對(duì)原有邊緣的近似替代。圖3（彩圖掃OSID 碼可見(jiàn)，下同）為采用概化算法處理后的圖像。

Fig.3 Image after generalization algorithm processing圖3 概化算法處理后的圖像

2.3 圓弧提取

相鄰線段之間夾角大小的變化可近似衡量圓弧的曲率變化，曲率變化大于設(shè)定閾值的點(diǎn)稱為拐點(diǎn)。對(duì)于V-M概化算法處理后的邊緣圖像，選取任意兩相鄰線段ei、ei+1構(gòu)造則兩線段之間的夾角θi大小變化可近似表示曲線曲率大小的變化，其中θi的大小表示為：

設(shè)定一角度閾值θt，通過(guò)判斷cosθi≤cosθt篩選出拐點(diǎn)，以拐點(diǎn)為分界進(jìn)行邊緣分割，并將分割后的邊緣作為候選邊緣設(shè)定構(gòu)成邊緣像素點(diǎn)數(shù)量閾值為ns，當(dāng)候選邊緣li構(gòu)成像素點(diǎn)數(shù)量大于ns時(shí)，則標(biāo)記為有效邊緣并置于邊緣集δ={li}中，從而剔除圖像中的小邊緣像素點(diǎn)和噪聲點(diǎn)。測(cè)試圖像設(shè)定角度閾值θt=25°，對(duì)圖像進(jìn)行拐點(diǎn)檢測(cè)并去除拐點(diǎn)以分割邊緣曲線。圖4 圓圈處即為邊緣拐點(diǎn)所在處。

2.4 圓檢測(cè)

2.4.1 候選圓及圓弧篩選

對(duì)于提取的有效邊緣集δ，以及任一有效邊緣ζ=，需判斷ζ是否為封閉邊緣。將構(gòu)成ζ的像素點(diǎn)集首尾元素之間距離di與設(shè)定封閉距離閾值ε進(jìn)行比較，當(dāng)di≤ε時(shí)，標(biāo)記邊緣ζ為封閉邊緣，并置于封閉邊緣集δ c中；否則，標(biāo)記邊緣ζ為非封閉邊緣，并置于非封閉邊緣集δs中。

對(duì)封閉邊緣集δ c與非封閉邊緣集δ s進(jìn)行初步篩選，保留圓和圓弧邊緣作為候選邊緣，剔除非圓及非圓弧邊緣。采取CFRCD 算法一次迭代，依次對(duì)每個(gè)邊緣進(jìn)行計(jì)算并篩選。為避免采樣點(diǎn)距離過(guò)近以及取點(diǎn)偶然性影響算法檢測(cè)結(jié)果，采用分區(qū)采樣方法［14］，按照邊緣將邊緣點(diǎn)集分為等區(qū)間的S1、S2、S33個(gè)部分，具體如圖5所示。

Fig.5 Picture of areal sampling圖5 分區(qū)采樣圖

隨機(jī)從3 個(gè)像素點(diǎn)區(qū)間中各取一點(diǎn)，分別表示為(x1，y1)、(x2，y2)及(x3，y3)，代入圓的方程中進(jìn)行計(jì)算。采用參數(shù)a、b和r表示候選圓的相關(guān)參數(shù)，其中(a，b)表示候選圓圓心，r表示半徑，計(jì)算公式分別為：

采用三點(diǎn)確定圓模型后，在該三點(diǎn)對(duì)應(yīng)的邊緣點(diǎn)集中隨機(jī)選取一異于該三點(diǎn)的像素點(diǎn)(x4，y4)，并計(jì)算該像素點(diǎn)是否靠近模型圓的邊界［15］。計(jì)算該點(diǎn)與模型圓圓心的距離d，并以該距離與模型圓半徑作差求取絕對(duì)值，公式為：

Fig.4 Edge inflection point of the signed image圖4 標(biāo)記圖像中的邊緣拐點(diǎn)

對(duì)于式（5）中的距離d，設(shè)定距離閾值Td。若d≤Td，對(duì)于封閉邊緣，判定為候選圓邊緣并儲(chǔ)存于圓邊緣集Φc中；對(duì)于非封閉邊緣，判定為候選圓弧邊緣，并儲(chǔ)存于圓弧邊緣集Φa中；否則，判定該邊緣為非圓邊緣，并從δ c或δs中剔除。

2.4.2 圓及圓弧的驗(yàn)證

篩選后Φc與Φa中的圓及圓弧邊緣需要進(jìn)一步精確，基于CFRCD 算法通過(guò)代理點(diǎn)進(jìn)行多次迭代。對(duì)于圓邊緣，取邊緣ζcc上等距的m個(gè)點(diǎn)，其中m≥3且m∈Ζ，m的取值應(yīng)確保取點(diǎn)之間的最短距離不能過(guò)小，又不能因m數(shù)值過(guò)大而使運(yùn)算量過(guò)大?？筛鶕?jù)式（2）、式（3）和式（4）計(jì)算a、b與r，單個(gè)圓邊緣迭代次數(shù)，則總迭代次數(shù)Ωc=nΤc。第i次迭代與第j次迭代結(jié)果的差值為：

式中，i，j=1，2，···，m且i≠j。對(duì)于Δa、Δb和Δr，設(shè)定閾值Ta、Tb和Tr。若對(duì)于全部的Δa、Δb和Δr有：

則邊緣ζcc確定為圓邊緣，并根據(jù)次迭代的參數(shù)結(jié)果求取均值得到圓參數(shù)a、b與r，表示為：

根據(jù)參數(shù)對(duì)圓輪廓進(jìn)行標(biāo)記，否則將邊緣ζcc從Φc集中剔除。

對(duì)于圓弧邊緣，采取基于CFRCD 算法的多個(gè)代理點(diǎn)進(jìn)行自身迭代。選取各圓弧的兩端點(diǎn)為既定點(diǎn)，在每條圓弧上隨機(jī)取κ個(gè)點(diǎn)，對(duì)于每條圓弧，利用兩端點(diǎn)及圓弧上的隨機(jī)點(diǎn)進(jìn)行計(jì)算。單條圓弧迭代次數(shù)為κ，總迭代次數(shù)為nκ。迭代完成后，將利用式（6）、式（7）求得的圓心半徑差值小于閾值的圓弧歸為同一類圓弧。

將分類后的圓弧劃分為N 類，其中0 ≤N≤n且N∈Ζ+。若同一類圓弧中僅有一條圓弧，則對(duì)該圓弧進(jìn)行自身代理點(diǎn)迭代；若同一類圓弧中包含多個(gè)圓弧，則將任一圓弧兩端點(diǎn)與同類其他圓弧上的隨機(jī)點(diǎn)組成代理點(diǎn)，直至完成所有圓弧間代理點(diǎn)的相互迭代。假設(shè)第i個(gè)同類圓弧所包含的圓弧段數(shù)目為ρ，則該類圓弧迭代次數(shù)為：

總迭代次數(shù)為：

同類圓弧完成迭代后，通過(guò)式（6）、式（7）、式（8）對(duì)圓弧組的圓心及半徑數(shù)值進(jìn)行精度優(yōu)化，并根據(jù)得到的圓參數(shù)a、b與r對(duì)圓弧組確定的圓進(jìn)行輪廓標(biāo)記。

3 實(shí)驗(yàn)方法與結(jié)果分析

3.1 實(shí)驗(yàn)方法

為驗(yàn)證CFRCD 算法的可行性，利用C++程序語(yǔ)言搭配Opencv 4.1.0 視覺(jué)庫(kù)針對(duì)多幅圖像進(jìn)行圓檢測(cè)比較實(shí)驗(yàn)。程序開(kāi)發(fā)環(huán)境為Visual Studio 2015，硬件環(huán)境為AMD Ryzen7處理器，主頻率為1.8GHz，運(yùn)行內(nèi)存為16GB。

選取4 組圖像進(jìn)行圓檢測(cè)測(cè)試，比較本文算法與GHT算法、RCD 算法對(duì)圖像中圓輪廓的識(shí)別能力。

3.2 結(jié)果分析

如圖6 所示，從左至右分別為原始圖像，以及GHT 算法、RCD 算法和CFRCD 算法的檢測(cè)結(jié)果?？梢钥闯?，GHT算法與RCD 算法對(duì)于圖像中圓輪廓的檢測(cè)存在誤檢與漏檢現(xiàn)象，而CFRCD 算法能準(zhǔn)確檢測(cè)出圖像中的圓輪廓，且多次檢測(cè)結(jié)果一致。

將圖6 中的4 組圖像分別命名為圖像1、圖像2、圖像3和圖像4，采用GHT 算法、RCD 算法及CFRCD 算法分別對(duì)4 組圖像進(jìn)行10 次圓檢測(cè)，并求取算法平均運(yùn)行時(shí)間，結(jié)果如表1 所示。可以看出，對(duì)于同一圖像，CFRCD 算法的運(yùn)行時(shí)間稍大于GHT 算法，但遠(yuǎn)小于RCD 算法。雖然GHT 算法的運(yùn)行速度較快，但其需要預(yù)設(shè)待測(cè)圓半徑的范圍，否則會(huì)大大增加運(yùn)算時(shí)間，故其運(yùn)行效率具有不確定性。當(dāng)圖像中干擾像素點(diǎn)或待測(cè)圓數(shù)量較多時(shí)，RCD 算法最優(yōu)結(jié)果的抽樣概率大大增加，計(jì)算量也隨之大大增加［16］。

Fig.6 Original images，GHT，RCD and CFRCD detection results（from left to right）圖6 原始圖像以及GHT算法、RCD算法、CFRCD算法檢測(cè)結(jié)果（從左到右）

Table 1 Execution times of three kinds of algorithm表1 3種算法的運(yùn)行時(shí)間 （ms)

向真實(shí)場(chǎng)景中分別添加5%、15%、25%和35%的椒鹽噪聲，以驗(yàn)證CFRCD 算法的魯棒性，結(jié)果如圖7 所示?？梢钥闯?，隨著噪聲比例的增加，CFRCD 算法檢測(cè)出的圓數(shù)量逐漸下降。為進(jìn)一步考察CFRCD 算法的抗干擾性能力，分別向測(cè)試圖像中添加8%、18%、27%和36%的椒鹽噪聲，結(jié)果如圖8 所示?？梢钥闯?，隨著噪聲比例的增加，該算法檢測(cè)出的圓數(shù)量亦逐漸減少。無(wú)論是自然場(chǎng)景還是測(cè)試場(chǎng)景，噪聲均會(huì)影響CFRCD 算法的檢測(cè)性能。

Fig.7 Robustness detection of CFRCD in real scenes圖7 真實(shí)場(chǎng)景中CFRCD算法的魯棒性檢測(cè)

Fig.8 Anti-interference detection of CFRCD in test scenes圖8 測(cè)試圖像中CFRCD算法的抗干擾性檢測(cè)

圖9 為3 種算法在不同百分比噪聲下對(duì)測(cè)試圖像中圓的檢測(cè)能力?？梢钥闯?，當(dāng)噪聲百分比大于10%時(shí)，RCD算法無(wú)法檢測(cè)出圓；當(dāng)噪聲百分比大于18%時(shí)，GHT 算法無(wú)法檢測(cè)出圓；當(dāng)噪聲百分比大于36%時(shí)，CFRCD 算法無(wú)法檢測(cè)出圓。這是由于噪聲比例過(guò)高時(shí)，圖像邊緣會(huì)變得很分散，檢測(cè)難度增大。

與GHT 算法和RCD 算法相比，CFRCD 算法在一定噪聲比例下仍具有較好的魯棒性，能夠較為準(zhǔn)確地檢測(cè)出圓輪廓，而其他兩種算法隨著噪聲百分比的增加，檢測(cè)結(jié)果出現(xiàn)較多錯(cuò)誤圓。

4 結(jié)語(yǔ)

本文結(jié)合概化算法與曲線擬合算法對(duì)圖像模型邊緣進(jìn)行分類并結(jié)合RCD 算法對(duì)圓形輪廓進(jìn)行識(shí)別與標(biāo)記。相較于傳統(tǒng)圓檢測(cè)算法，該改進(jìn)算法能準(zhǔn)確識(shí)別各種場(chǎng)景下的圓輪廓，在執(zhí)行效率以及抗干擾性方面均有顯著提升。然而較小的圓用概化算法經(jīng)一系列線段替代后，相鄰線段之間的夾角會(huì)較大而無(wú)法通過(guò)拐點(diǎn)篩選，故該算法可能無(wú)法檢測(cè)較小的圓輪廓。后續(xù)將研究如何對(duì)較小圓輪廓進(jìn)行檢測(cè)，并進(jìn)一步提高算法的抗干擾性能。

Fig.9 Circle detection ability of each algorithm under different percentages of noise圖9 不同百分比噪聲下各算法的圓檢測(cè)能力