基于曲線擬合的隨機圓檢測算法

袁 坤，彭和平

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

0 引言

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

1 相關研究

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

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

2 CFRCD算法

2.1 邊緣檢測

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

Fig.1 Test image圖1 測試圖像

2.2 曲線擬合

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

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

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

2.3 圓弧提取

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

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

2.4 圓檢測

2.4.1 候選圓及圓弧篩選

對于提取的有效邊緣集δ，以及任一有效邊緣ζ=，需判斷ζ是否為封閉邊緣。將構成ζ的像素點集首尾元素之間距離di與設定封閉距離閾值ε進行比較，當di≤ε時，標記邊緣ζ為封閉邊緣，并置于封閉邊緣集δ c中；否則，標記邊緣ζ為非封閉邊緣，并置于非封閉邊緣集δs中。

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

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

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

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

Fig.4 Edge inflection point of the signed image圖4 標記圖像中的邊緣拐點

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

2.4.2 圓及圓弧的驗證

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

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

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

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

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

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

總迭代次數(shù)為：

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

3 實驗方法與結果分析

3.1 實驗方法

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

選取4 組圖像進行圓檢測測試，比較本文算法與GHT算法、RCD 算法對圖像中圓輪廓的識別能力。

3.2 結果分析

如圖6 所示，從左至右分別為原始圖像，以及GHT 算法、RCD 算法和CFRCD 算法的檢測結果。可以看出，GHT算法與RCD 算法對于圖像中圓輪廓的檢測存在誤檢與漏檢現(xiàn)象，而CFRCD 算法能準確檢測出圖像中的圓輪廓，且多次檢測結果一致。

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

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

Table 1 Execution times of three kinds of algorithm表1 3種算法的運行時間 （ms)

向真實場景中分別添加5%、15%、25%和35%的椒鹽噪聲，以驗證CFRCD 算法的魯棒性，結果如圖7 所示。可以看出，隨著噪聲比例的增加，CFRCD 算法檢測出的圓數(shù)量逐漸下降。為進一步考察CFRCD 算法的抗干擾性能力，分別向測試圖像中添加8%、18%、27%和36%的椒鹽噪聲，結果如圖8 所示。可以看出，隨著噪聲比例的增加，該算法檢測出的圓數(shù)量亦逐漸減少。無論是自然場景還是測試場景，噪聲均會影響CFRCD 算法的檢測性能。

Fig.7 Robustness detection of CFRCD in real scenes圖7 真實場景中CFRCD算法的魯棒性檢測

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

圖9 為3 種算法在不同百分比噪聲下對測試圖像中圓的檢測能力。可以看出，當噪聲百分比大于10%時，RCD算法無法檢測出圓；當噪聲百分比大于18%時，GHT 算法無法檢測出圓；當噪聲百分比大于36%時，CFRCD 算法無法檢測出圓。這是由于噪聲比例過高時，圖像邊緣會變得很分散，檢測難度增大。

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

4 結語

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

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