袁 坤,彭和平
(江漢大學(xué)智能制造學(xué)院,湖北武漢 430056)
圓形是自然界中的常見(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)題之一。
為解決傳統(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í)行效率。
邊緣檢測(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è)試圖像
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 概化算法處理后的圖像
相鄰線段之間夾角大小的變化可近似衡量圓弧的曲率變化,曲率變化大于設(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.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)記。
為驗(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í)別能力。
如圖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ò)誤圓。
本文結(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è)能力