葉 明, 吳迪飛

(南京航空航天大學(xué) 機(jī)電學(xué)院,南京 210016)

一種粘連顆粒圖像中心點(diǎn)的識(shí)別方法①

葉 明, 吳迪飛

(南京航空航天大學(xué) 機(jī)電學(xué)院,南京 210016)

針對(duì)粘連顆粒檢測(cè)中的中心點(diǎn)提取問題,提出了一種基于改進(jìn)廣義Hough變換的檢測(cè)算法.該算法首先計(jì)算已知圖形的覆蓋圓環(huán),然后將圓環(huán)模板遍歷待測(cè)圖像前景輪廓點(diǎn)進(jìn)行覆蓋區(qū)域累加,最后得到累加圖的極大值.該算法產(chǎn)生的圓環(huán)具有旋轉(zhuǎn)不變性,能夠大大縮減檢測(cè)時(shí)間.同時(shí)實(shí)驗(yàn)表明,這種圓環(huán)模板累加的算法能夠得到更加準(zhǔn)確的定位中心點(diǎn),并且部分消除了偽中心.

粘連顆粒;廣義Hough變換;前景標(biāo)記

隨著科技的發(fā)展,數(shù)字圖像處理已經(jīng)在醫(yī)療,農(nóng)業(yè)生產(chǎn)自動(dòng)檢測(cè),工業(yè)生產(chǎn)自動(dòng)檢測(cè)等領(lǐng)域得到廣泛應(yīng)用.在實(shí)際應(yīng)用中常常遇到需要對(duì)粘連的顆粒進(jìn)行分離操作的情況,如粘連細(xì)胞圖像的自動(dòng)分割,農(nóng)作物圖像的自動(dòng)分離,粘連纖維圖像的自動(dòng)分割等.

粘連顆粒的分離通常采用的是凹點(diǎn)匹配算法[1-3]和分水嶺算法[4-6].凹點(diǎn)匹配算法的主要研究問題為:(1)凹點(diǎn)和凹區(qū)域的求取;(2)凹點(diǎn)的匹配規(guī)則.然而求得的凹點(diǎn)和凹區(qū)域可能會(huì)受到輪廓噪音的影響,在凹點(diǎn)匹配規(guī)則中常常使用的凹區(qū)域向量[1,2],輪廓切線[3]等同樣會(huì)受到輪廓噪音的影響.這使得凹點(diǎn)匹配算法受到很大的限制.因此較復(fù)雜的粘連顆粒分割通常采用的是分水嶺算法.然而傳統(tǒng)分水嶺算法又會(huì)產(chǎn)生非常嚴(yán)重的過分割問題,因此有學(xué)者提出了區(qū)域標(biāo)注器(也叫前景標(biāo)記)來(lái)解決這個(gè)問題[6].該算法的優(yōu)勢(shì)在于采用前景標(biāo)記對(duì)單個(gè)顆粒進(jìn)行標(biāo)記,然后再做分水嶺變換,所以可以有效地消除原有分水嶺算法結(jié)果中的過分割現(xiàn)象.但是其準(zhǔn)確性主要依賴于標(biāo)記提取的準(zhǔn)確性.現(xiàn)在采用的前景標(biāo)記提取算法主要是形態(tài)學(xué)重構(gòu)算法[4]和極限腐蝕算法[5].然而這兩種算法對(duì)于粘連顆粒的形狀缺陷(如顆粒內(nèi)部出現(xiàn)孔洞的情況)的魯棒性均不理想.雖然一些文獻(xiàn)[7,8]中對(duì)這兩種算法提出修改方案,但依然無(wú)法很好地解決單個(gè)顆粒內(nèi)部存在孔洞的問題.

針對(duì)前景標(biāo)記提取不準(zhǔn)確的問題,本文嘗試使用廣義Hough變換來(lái)予以解決.廣義Hough變換(Generalized Hough transform,GHT)是根據(jù)已知圖形去尋找在待求圖像中和已知圖形相似的圖形的常用算法[9].其主要思想是通過已知圖形構(gòu)造一種變換,稱為GHT坐標(biāo)變換.遍歷待求圖像前景輪廓點(diǎn)作GHT坐標(biāo)變換,得到的坐標(biāo)即是需要在累加空間進(jìn)行累加的點(diǎn)的坐標(biāo).最后累加空間的極值點(diǎn)為目標(biāo)的可能位置.其變換公式為:

GHT的優(yōu)點(diǎn)有:(1)可以檢測(cè)任意復(fù)雜的形狀;(2)對(duì)于有一定遮擋和一定形變的圖形具有較好的魯棒性.因此,GHT對(duì)于單個(gè)顆粒內(nèi)部的孔洞等形狀缺陷的干擾應(yīng)該具有比較好的抗干擾能力.但GHT算法的時(shí)間和空間復(fù)雜度都較高,并且若輪廓噪音比較大時(shí),采用輪廓梯度方向作為索值并不準(zhǔn)確.因此需要對(duì)其進(jìn)行一定的改進(jìn).

有許多對(duì)GHT進(jìn)行改進(jìn)的文獻(xiàn),包括對(duì)于精度的改進(jìn)和對(duì)于速度的改進(jìn).對(duì)于精度的改進(jìn)主要有使用其他索值代替梯度方向的方法[9-12]以及對(duì)大量樣本進(jìn)行訓(xùn)練來(lái)優(yōu)化R表的方法[13,14].對(duì)于速度的改進(jìn)主要有減少待檢測(cè)點(diǎn)的數(shù)量的方法[15],使用旋轉(zhuǎn)不變量作為索值使GHT算法獲得旋轉(zhuǎn)不變性的方法[16,17]和采用GPU并行處理的方法[18].文獻(xiàn)[16]中使用相鄰輪廓點(diǎn)梯度向量的夾角作為索值,使GHT具有旋轉(zhuǎn)不變性,累加空間從四維變成三維,從而大大縮減了運(yùn)行時(shí)間.但由于使用了輪廓點(diǎn)的梯度方向,因此容易受到輪廓噪音的干擾.

針對(duì)GHT及其改進(jìn)算法存在的問題,本文對(duì)GHT做了一些改進(jìn).包括:(1)采用累加模板對(duì)每個(gè)輪廓點(diǎn)進(jìn)行覆蓋累加,回避了輪廓梯度的計(jì)算,從而減弱了輪廓噪音的影響;(2)累加模板為圓環(huán),從而使其具有旋轉(zhuǎn)不變性,減少了運(yùn)行時(shí)間.

由于GHT算法只能搜索相似的圖形,加上本文算法的一些限制,因此研究的粘連顆粒對(duì)象具有如下特點(diǎn):(1)顆粒之間具有相似性,并且可能存在旋轉(zhuǎn)變換;(2)輪廓的內(nèi)切圓和外接圓的比值較小,形狀與圓接近;(3)顆粒之間相互粘連,有一定的遮擋和形變;(4)粘連顆粒大小基本一致,縮放比例可以近似忽略.此類顆粒中比較典型的顆粒是各種類圓形的化學(xué)纖維,本文以化學(xué)纖維為例對(duì)問題進(jìn)行說明如圖1所示.

圖1 化學(xué)纖維橫截面

1 改進(jìn)的廣義Hough變換

1.1 覆蓋圓環(huán)

對(duì)于單個(gè)顆粒圖形的輪廓,可以使用一個(gè)圓環(huán)將其完全覆蓋,如圖2所示.其中圓環(huán)的中心為輪廓的質(zhì)心,并且要求圓環(huán)的面積最小.

圖2 顆粒輪廓及其覆蓋圓環(huán)

將這個(gè)覆蓋圓環(huán)沿著圖2輪廓進(jìn)行覆蓋區(qū)域累加.則圓環(huán)中心經(jīng)過每個(gè)輪廓點(diǎn)時(shí),圓環(huán)均覆蓋到了輪廓的質(zhì)心,所以質(zhì)心將成為累加圖的區(qū)域極大值點(diǎn).并且由于該圓環(huán)的面積最小,因此造成的錯(cuò)誤累加也最少.基于以上兩點(diǎn)考慮,可以采用最小覆蓋圓環(huán)模板累加的方式來(lái)求粘連顆粒的質(zhì)心.

這樣做的好處是即使輪廓上的點(diǎn)發(fā)生了擾動(dòng),只要擾動(dòng)在一定范圍內(nèi),潛在的質(zhì)心點(diǎn)仍然會(huì)被覆蓋到.從而在一定程度上減弱了輪廓噪音的干擾.同時(shí),因?yàn)橹恍柽M(jìn)行N2×M次加法運(yùn)算(N為圓環(huán)的直徑,M為待檢測(cè)圖像前景輪廓點(diǎn)的個(gè)數(shù))而無(wú)需計(jì)算梯度和變換后的坐標(biāo),所以該算法運(yùn)算速度很快.

當(dāng)然,這種方法也存在一些可能的問題.包括比例系數(shù)s,異形度λ等帶來(lái)的影響.這些影響因素會(huì)在算法的實(shí)現(xiàn)和討論中有所討論.異形度λ的定義公式[19]為:

其中rmax和rmin分別是圓環(huán)的大小圓半徑.λ值越小,顆粒的輪廓越接近于圓.

1.2 算法描述

算法分為兩步:(1)圓環(huán)累加模板的制作;(2)進(jìn)行模板累加并求極值點(diǎn).算法流程圖如圖3所示.

圖3 算法流程圖

1.2.1 模板的制作

模板的制作是一個(gè)由已知圖形得到最小覆蓋圓環(huán)的過程.其具體步驟如下:

① 求模板圖像的輪廓圖;

② 求模板圖像輪廓的質(zhì)心(xr,yr),將質(zhì)心作為參考點(diǎn);

③ 求輪廓上每個(gè)點(diǎn)到參考點(diǎn)的距離,記錄在dist中,其中dist為1×N的行向量,N為輪廓點(diǎn)的個(gè)數(shù).令distmax=max(dist);

④ 確定模板Rtable的大小為邊長(zhǎng)等于(2*distmax+1)的正方形矩陣.對(duì)于每個(gè)dist(n),遍歷Rtable中每個(gè)點(diǎn)(xk,yk),判斷是否滿足:

圖4 累加圓環(huán)模板

本文中的模板圖形選取采用人工選取的方式.主要是因?yàn)轭w粒輪廓彼此之間具有相似性,由顆粒輪廓得到的distmax和distmin差距較小.模板圖形會(huì)對(duì)結(jié)果產(chǎn)生些許影響,體現(xiàn)在中心點(diǎn)的位置不是完全重合上.

1.2.2 中心點(diǎn)的識(shí)別

中心點(diǎn)的識(shí)別過程是由求得的覆蓋圓環(huán)模板和待檢測(cè)圖像找出粘連顆粒質(zhì)心的過程.本文以圖1作為樣例進(jìn)行說明,為了證明本文算法的有效性,對(duì)圖1的二值圖做了一些修改,具體為增加了凹陷,空洞和斷裂等缺陷如圖5(b)所示.

圖5 樣例的二值圖

中心點(diǎn)識(shí)別的具體步驟如下:

① 計(jì)算待檢測(cè)圖像的前景輪廓.

② 置Acc為和待識(shí)別圖像相同大小的零矩陣,作為累加空間.遍歷待識(shí)別圖像的每個(gè)輪廓點(diǎn),將其與Rtable的中心點(diǎn)對(duì)齊.設(shè)Rtable覆蓋的區(qū)域?yàn)镾i,則Acc(Si)=Acc(Si)+1,其中下標(biāo)i是輪廓點(diǎn)的編號(hào).最終得到累加圖Acc,如圖6所示.

圖6 樣例的累加圖Acc

③ 對(duì)Acc進(jìn)行歸一化處理,Acc=Acc max(Acc).

④ 令A(yù)cc2為和Acc大小相同的零矩陣.對(duì)Acc作閾值處理,令閾值為threshold.Acc中大于等于threshold的點(diǎn)在Acc2中置1,小于的點(diǎn)置0,如圖7所示.threshold通常取0.4～0.9.

圖7 閾值化后得到的待選點(diǎn)集

⑤ 遍歷Acc2中的前景點(diǎn)(像素值為1的點(diǎn)),判斷在Acc中,以這個(gè)點(diǎn)為中心,半徑為R的圓形區(qū)域內(nèi),其是否為這個(gè)區(qū)域的最大值.若是,則將其坐標(biāo)記錄在(cx,cy)中,結(jié)果如圖8所示.其中R是設(shè)定的閾值.R通常取0.6～0.8個(gè)distmax.

圖8 待選點(diǎn)集中的區(qū)域極大值點(diǎn),R取0.8*distmax

2 算法的實(shí)現(xiàn)和討論

為了進(jìn)一步說明算法的可行性,本文采用兩組形狀為“三角形”和“五角形”的粘連顆粒圖像,應(yīng)用文中算法與基于形態(tài)學(xué)重構(gòu)的標(biāo)記提取算法、經(jīng)典的GHT算法進(jìn)行仿真對(duì)比實(shí)驗(yàn).本文所使用的實(shí)驗(yàn)平臺(tái)為:PC機(jī),主頻2.2 GMHZ,內(nèi)存3 G,Matlab9開發(fā)環(huán)境.由于三角形源圖存在非均勻光照現(xiàn)象,因此使用了文獻(xiàn)[4]中的方法進(jìn)行二值化.五角形源圖的二值化算法采用otsu算法,運(yùn)用canny算子來(lái)獲取兩張圖像的邊緣圖.

由表1可知,GHT算法在搜索與已知圖形之間沒有角度變換的圖形所用時(shí)間比本文方法更長(zhǎng).因此,本文的方法在時(shí)間復(fù)雜度上小于GHT算法.由圖9(e)和圖10(e)可以看出GHT算法得到了一些偽中心點(diǎn).產(chǎn)生偽中心點(diǎn)的主要原因分為兩類:(1)附近其他輪廓的干擾以及輪廓形變的影響使中心點(diǎn)發(fā)生偏移;(2)旋轉(zhuǎn)過程造成了前景區(qū)域外部出現(xiàn)了區(qū)域極值點(diǎn).第一種偽中心點(diǎn)不易消除.第二種偽中心點(diǎn)的累加值較小,若增大threshold的值就能夠在一定程度上消除這些偽中心點(diǎn).但由于部分輪廓的缺失,導(dǎo)致前景中有一些中心點(diǎn)的累加值也比較小,如果增大threshold就會(huì)出現(xiàn)中心點(diǎn)的遺漏.因此GHT算法并不能很好地解決該類問題.本文的算法減弱了梯度方向的影響,加強(qiáng)了算法對(duì)于輪廓形變的魯棒性,因此可以有效減少GHT算法中的第一類偽中心點(diǎn)的數(shù)量,同時(shí)僅在兩個(gè)相鄰顆粒的部分輪廓構(gòu)成了已知圖形的一部分輪廓時(shí)才會(huì)在前景區(qū)域外圍形成區(qū)域極值點(diǎn).

表1 本文方法和GHT算法運(yùn)行時(shí)間對(duì)比(單位:秒)

由圖9(d)和圖10(d)可知,使用形態(tài)學(xué)重構(gòu)計(jì)算纖維中心點(diǎn)的算法,若纖維上出現(xiàn)比較明顯的孔洞和凹陷時(shí),會(huì)將一個(gè)纖維誤檢為多個(gè).該算法中使用到了距離變換來(lái)生成距離圖.距離圖中一個(gè)前景點(diǎn)的像素值是該點(diǎn)到所有輪廓點(diǎn)的最小距離,因此距離圖的生成對(duì)于孔洞和凹陷比較敏感.若能夠修正距離圖,減少孔洞和凹陷,則可以在很大程度上消除誤檢的情況.本文的做法是在中心點(diǎn)識(shí)別準(zhǔn)確的情況下,使用半徑為r的圓來(lái)覆蓋中心點(diǎn)區(qū)域,被覆蓋的區(qū)域全部置1.

圖9 三角形粘連顆粒源圖和中心點(diǎn)識(shí)別圖

圖10 五角形粘連顆粒源圖和中心點(diǎn)識(shí)別圖

以圖5(b)為例進(jìn)行說明,圖11中的r取值為distmin.對(duì)比圖11(a)和(c)可以看出修正后的標(biāo)記結(jié)果得到了非常大的改善.這種距離圖修正的方法是建立在中心點(diǎn)的識(shí)別準(zhǔn)確的基礎(chǔ)上的.若識(shí)別的中心點(diǎn)因?yàn)樾螤钫`差發(fā)生偏移,則需要將r的取值減小.r取值減小后的修正效果將有所下降.

相比于GHT算法和其他相關(guān)算法,本文的方法可能會(huì)存在一些缺陷.如比例系數(shù)和異形度等對(duì)于算法的影響.對(duì)于不同尺度顆粒相互粘連的情況,使用縮放后的圓環(huán)來(lái)進(jìn)行累加.當(dāng)使用較小的圓環(huán)累加時(shí),可能在較大顆粒內(nèi)部形成多個(gè)區(qū)域極值點(diǎn).當(dāng)小顆粒的輪廓存在遮擋,使得其中心累加值較小時(shí)就無(wú)法使用閾值來(lái)過濾大顆粒內(nèi)部形成的偽中心點(diǎn)從而出現(xiàn)錯(cuò)誤的識(shí)別.如圖12(b)所示,若下方兩個(gè)小三角形的輪廓被部分遮擋,則其中心累加值將減小.當(dāng)異形度較大時(shí),顆粒將變成條狀.這類顆粒的最小覆蓋圓環(huán)的小圓半徑很小,覆蓋圓環(huán)與圓接近,使得累加圖中出現(xiàn)大量冗余的累加,導(dǎo)致識(shí)別失敗,如圖12(d)所示.

圖11 二值圖修正的分水嶺分割

圖12 比例系數(shù)和異形度的影響

3 結(jié)語(yǔ)

本文提出了一種針對(duì)一類粘連顆粒的中心點(diǎn)識(shí)別算法.首先根據(jù)已知圖形計(jì)算圓環(huán)覆蓋模板,然后將圓環(huán)模板沿待檢測(cè)圖像輪廓進(jìn)行覆蓋累加.得到的累加圖的極值點(diǎn)即各個(gè)纖維的中心.該算法計(jì)算出的覆蓋圓環(huán)具有旋轉(zhuǎn)不變性,大大降低了算法的時(shí)間復(fù)雜度,并且具有較高的準(zhǔn)確性,是一種可靠的檢測(cè)類圓形粘連顆粒中心的算法.得到的中心點(diǎn)對(duì)于距離變換圖的修正可以起到指導(dǎo)作用,從而使得分水嶺算法分割的準(zhǔn)確度得到提高.

1 Farhan M,Yli-Harja O,Niemist? A.A novel method for splitting clumps of convex objects incorporating image intensity and using rectangular window-based concavity point-pair search.Pattern Recognition,2013,46(3):741–751.[doi:10.1016/j.patcog.2012.09.008]

2 Kumar S,Ong SH,Ranganath S,et al.A rule-based approach for robust clump splitting.Pattern Recognition,2006,39(6):1088–1098.[doi:10.1016/j.patcog.2005.11.014]

3 韋冬冬,趙豫紅.基于凹點(diǎn)匹配的重疊圖像分割算法.計(jì)算機(jī)與應(yīng)用化學(xué),2010,27(1):99–102.

4 倪志強(qiáng),葉明.基于分水嶺變換的粘連顆粒圖像分割方法.計(jì)算機(jī)系統(tǒng)應(yīng)用,2014,23(6):93–97.

5 戴丹.基于改進(jìn)分水嶺算法的粘連顆粒圖像分割.計(jì)算機(jī)技術(shù)與發(fā)展,2013,(3):19–22.

6 Meyer F,Beucher S.Morphological segmentation.Journal of Visual Communication and Image Representation,1990,1(1):21–46.[doi:10.1016/1047-3203(90)90014-M]

7 劉相濱,鄒北驥,孫家廣.菌群細(xì)胞圖像分離算法研究.電子學(xué)報(bào),2005,33(6):1056–1059.

8 李希,王天江,周鵬.一種改進(jìn)的粘連顆粒圖像分割算法.湖南大學(xué)學(xué)報(bào)(自然科學(xué)版),2012,39(12):84–88.[doi:10.3969/j.issn.1674-2974.2012.12.015]

9 李智磊,翟宏琛,王明偉.一種可識(shí)別破碎圖形的特殊廣義Hough變換方法.物理學(xué)報(bào),2007,56(6):3234–3239.[doi:10.7498/aps.56.3234]

10 胡正平,楊蘇.基于關(guān)鍵特征點(diǎn)決策的廣義Hough變換目標(biāo)定位快速算法.信號(hào)處理,2009,25(11):1748–1753.[doi:10.3969/j.issn.1003-0530.2009.11.016]

11 劉宏申,程健.廣義Hough變換算法的分析改進(jìn).中國(guó)科學(xué)技術(shù)大學(xué)學(xué)報(bào),2009,39(11):1202–1206.

12 Kontschieder P,Riemenschneider H,Donoser M,et al.Discriminative learning of contour fragments for object detection.Proc.of the British Machine Vision Conference.Dundee,UK.2011.

13 Gall J,Lempitsky V.Class-specific Hough forests for object detection.2013 IEEE Conference on Computer Vision and Pattern Recognition.Miami,FL,USA.2009.1022–1029.

14 Opelt A,Pinz A,Zisserman A.A boundary-fragment-model for object detection.Computer Vision-ECCV 2006,9th European Conference on Computer Vision.Graz,Austria.2006.575–588.

15 Xu L,Oja E,Kultanen P.A new curve detection method:Randomized Hough transform (RHT).Pattern Recognition Letters,1990,11(5):331–338.[doi:10.1016/0167-8655(90)90042-Z]

16 Tsai DM.An improved generalized Hough transform for the recognition of overlapping objects.Image and Vision Computing,1997,15(12):877–888.[doi:10.1016/S0262-8856(97)00033-4]

17 楊華,尹周平,王瑜輝,等.基于局部不變幾何特征的廣義霍夫變換圖像匹配方法:中國(guó),CN103456005A.[2013-12-18].

18 侯怡婷.基于CUDA的Hough變換并行實(shí)現(xiàn)[碩士學(xué)位論文].大連:大連理工大學(xué),2013.

19 尹平平.噴絲板微孔中熔體流動(dòng)及異形纖維成形過程的研究[碩士學(xué)位論文].上海:東華大學(xué),2006.

Detection Method for the Center of Touching Particle Image

YE Ming,WU Di-Fei
(College of Mechanical Engineering,Nanjing University of Aeronautics and Astronautics,Nanjing 210016,China)

Aiming at the problem of detecting the centers of touching particles images,a detecting method based on the improved Generalized Hough transform is proposed in this paper.The method firstly figures out the ring that overlaps the known particle’s outline,then the overlapping area of the ring template is accumulated along the foreground contour of the image to be detected.Finally,the region maximum value of the accumulated matrix will be the centers of the particles.The ring template has rotation invariance so that the detection time will be shortened greatly.Meanwhile,the result shows that the method in this paper has fine detection effect.

touching particles;the Generalized Hough transform;foreground makers

葉明,吳迪飛.一種粘連顆粒圖像中心點(diǎn)的識(shí)別方法.計(jì)算機(jī)系統(tǒng)應(yīng)用,2017,26(9):181–187.http://www.c-s-a.org.cn/1003-3254/6048.html

① 基金項(xiàng)后:南京航空航天大學(xué)基本科研業(yè)務(wù)費(fèi)專項(xiàng)科研資助項(xiàng)后(NS2014051)

2016-12-29;采用時(shí)間:2017-03-16