一種粘連顆粒圖像中心點的識別方法①

葉 明, 吳迪飛

(南京航空航天大學 機電學院,南京 210016)

一種粘連顆粒圖像中心點的識別方法①

葉 明, 吳迪飛

(南京航空航天大學 機電學院,南京 210016)

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

粘連顆粒;廣義Hough變換;前景標記

隨著科技的發展,數字圖像處理已經在醫療,農業生產自動檢測,工業生產自動檢測等領域得到廣泛應用.在實際應用中常常遇到需要對粘連的顆粒進行分離操作的情況,如粘連細胞圖像的自動分割,農作物圖像的自動分離,粘連纖維圖像的自動分割等.

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

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

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

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

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

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

圖1 化學纖維橫截面

1 改進的廣義Hough變換

1.1 覆蓋圓環

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

圖2 顆粒輪廓及其覆蓋圓環

將這個覆蓋圓環沿著圖2輪廓進行覆蓋區域累加.則圓環中心經過每個輪廓點時,圓環均覆蓋到了輪廓的質心,所以質心將成為累加圖的區域極大值點.并且由于該圓環的面積最小,因此造成的錯誤累加也最少.基于以上兩點考慮,可以采用最小覆蓋圓環模板累加的方式來求粘連顆粒的質心.

這樣做的好處是即使輪廓上的點發生了擾動,只要擾動在一定范圍內,潛在的質心點仍然會被覆蓋到.從而在一定程度上減弱了輪廓噪音的干擾.同時,因為只需進行N2×M次加法運算(N為圓環的直徑,M為待檢測圖像前景輪廓點的個數)而無需計算梯度和變換后的坐標,所以該算法運算速度很快.

當然,這種方法也存在一些可能的問題.包括比例系數s,異形度λ等帶來的影響.這些影響因素會在算法的實現和討論中有所討論.異形度λ的定義公式[19]為:

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

1.2 算法描述

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

圖3 算法流程圖

1.2.1 模板的制作

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

① 求模板圖像的輪廓圖;

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

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

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

圖4 累加圓環模板

本文中的模板圖形選取采用人工選取的方式.主要是因為顆粒輪廓彼此之間具有相似性,由顆粒輪廓得到的distmax和distmin差距較小.模板圖形會對結果產生些許影響,體現在中心點的位置不是完全重合上.

1.2.2 中心點的識別

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

圖5 樣例的二值圖

中心點識別的具體步驟如下:

① 計算待檢測圖像的前景輪廓.

② 置Acc為和待識別圖像相同大小的零矩陣,作為累加空間.遍歷待識別圖像的每個輪廓點,將其與Rtable的中心點對齊.設Rtable覆蓋的區域為Si,則Acc(Si)=Acc(Si)+1,其中下標i是輪廓點的編號.最終得到累加圖Acc,如圖6所示.

圖6 樣例的累加圖Acc

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

④ 令Acc2為和Acc大小相同的零矩陣.對Acc作閾值處理,令閾值為threshold.Acc中大于等于threshold的點在Acc2中置1,小于的點置0,如圖7所示.threshold通常取0.4～0.9.

圖7 閾值化后得到的待選點集

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

圖8 待選點集中的區域極大值點,R取0.8*distmax

2 算法的實現和討論

為了進一步說明算法的可行性,本文采用兩組形狀為“三角形”和“五角形”的粘連顆粒圖像,應用文中算法與基于形態學重構的標記提取算法、經典的GHT算法進行仿真對比實驗.本文所使用的實驗平臺為:PC機,主頻2.2 GMHZ,內存3 G,Matlab9開發環境.由于三角形源圖存在非均勻光照現象,因此使用了文獻[4]中的方法進行二值化.五角形源圖的二值化算法采用otsu算法,運用canny算子來獲取兩張圖像的邊緣圖.

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

表1 本文方法和GHT算法運行時間對比(單位:秒)

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

圖9 三角形粘連顆粒源圖和中心點識別圖

圖10 五角形粘連顆粒源圖和中心點識別圖

以圖5(b)為例進行說明,圖11中的r取值為distmin.對比圖11(a)和(c)可以看出修正后的標記結果得到了非常大的改善.這種距離圖修正的方法是建立在中心點的識別準確的基礎上的.若識別的中心點因為形狀誤差發生偏移,則需要將r的取值減小.r取值減小后的修正效果將有所下降.

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

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

圖12 比例系數和異形度的影響

3 結語

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

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 韋冬冬,趙豫紅.基于凹點匹配的重疊圖像分割算法.計算機與應用化學,2010,27(1):99–102.

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

5 戴丹.基于改進分水嶺算法的粘連顆粒圖像分割.計算機技術與發展,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 劉相濱,鄒北驥,孫家廣.菌群細胞圖像分離算法研究.電子學報,2005,33(6):1056–1059.

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

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

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

11 劉宏申,程健.廣義Hough變換算法的分析改進.中國科學技術大學學報,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 楊華,尹周平,王瑜輝,等.基于局部不變幾何特征的廣義霍夫變換圖像匹配方法:中國,CN103456005A.[2013-12-18].

18 侯怡婷.基于CUDA的Hough變換并行實現[碩士學位論文].大連:大連理工大學,2013.

19 尹平平.噴絲板微孔中熔體流動及異形纖維成形過程的研究[碩士學位論文].上海:東華大學,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

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

① 基金項后:南京航空航天大學基本科研業務費專項科研資助項后(NS2014051)

2016-12-29;采用時間:2017-03-16