基于改進(jìn)K-Means算法的蠶繭自動計數(shù)方法的研究

黃 靜，張 琦，江文斌

(浙江理工大學(xué) a.信息學(xué)院;b.材料與紡織學(xué)院，杭州310018)

目前的繅絲設(shè)備基本采用的是定纖控制系統(tǒng)的自動繅絲機(jī)，根據(jù)生絲規(guī)格要求自動控制生絲纖度，但是在生絲纖度的自動控制過程中由于車間溫濕度變化、煮熟繭的煮熟程度不同，以及生絲纖度控制機(jī)構(gòu)間的差異等因素會引起生絲纖度的粗細(xì)變化。生絲纖度的粗細(xì)在實(shí)際生產(chǎn)過程中無法采用定量標(biāo)示的方法進(jìn)行直觀反映，實(shí)驗(yàn)證實(shí)緒下繭平均粒數(shù)與生絲纖度存在一一對應(yīng)關(guān)系，可以通過檢查緒下繭粒數(shù)多少來了解纖度的變化情況[1]，以便進(jìn)行實(shí)繅工藝參數(shù)的修正。傳統(tǒng)的生絲生產(chǎn)管理是采用人工定期目測、手工記錄、計算的方法，對每組繅絲設(shè)備的緒下繭粒數(shù)進(jìn)行檢測，這種方法存在著效率低、工作量大、實(shí)時效果差，不利于提高生絲品質(zhì)、減少用工等問題。因此，開發(fā)出能夠快速、準(zhǔn)確地自動判別緒下繭粒數(shù)的計數(shù)系統(tǒng)，不僅能提高勞動生產(chǎn)率，而且還可以實(shí)現(xiàn)生絲纖度控制系統(tǒng)的實(shí)時修正，提高生絲質(zhì)量。

近年來，學(xué)者們在自動計數(shù)方面做了大量的研究。駱志堅(jiān)等[2]利用CCD圖像傳感器獲取實(shí)時圖像，并對圖像中的邊界、灰度值及梯度等數(shù)據(jù)信息進(jìn)行融合來實(shí)現(xiàn)自動計數(shù)，但該方法只對大小一致的成捆螺紋鋼圓形截面搜索有效，不適用于形態(tài)變化較大的蠶繭。余曉流等[3]提出了利用光電傳感器獲取的脈沖數(shù)，實(shí)現(xiàn)棒材的計數(shù)和打捆，但該方法成本較高。朱從容[4]提出基于數(shù)據(jù)擬合的方法計算魚苗的數(shù)目，但該方法的灰度閾值選取困難，魚苗的位置和圖像環(huán)境對計數(shù)的影響較大。劉世晶等[5]提出基于藻類熒光激發(fā)效應(yīng)的小球藻類自動計數(shù)方法，解決了藻類和雜質(zhì)難區(qū)分的問題，但依然存在丟失部分圖像特征信息，熒光點(diǎn)與背景顏色相近計數(shù)不準(zhǔn)確等問題。

針對蠶繭圖像識別時存在的圖像粘連問題，本研究提出運(yùn)用C++和OpenCV結(jié)合的方法對圖像進(jìn)行處理，用于對每個蠶繭槽上的蠶繭計數(shù)。針對二值圖像中出現(xiàn)的多個對象相互黏連的情況，應(yīng)用形態(tài)學(xué)方法中的腐蝕膨脹法和K-Means聚類算法，實(shí)現(xiàn)了對蠶繭圖像的分割和計數(shù)，并比較了每種方法的計數(shù)精度，同時結(jié)合界面開發(fā)計數(shù)系統(tǒng)，使其具有良好的人機(jī)交互功能，操作簡單方便。本研究采用攝像機(jī)拍照直接獲得蠶繭的圖像，為了增強(qiáng)對比度，實(shí)驗(yàn)將若干粒蠶繭隨機(jī)地撒在一張黑紙上進(jìn)行拍攝，并不斷改變蠶繭數(shù)量拍攝多幅圖片進(jìn)行處理。

1 蠶繭自動計數(shù)算法研究

本研究分別嘗試使用腐蝕膨脹法、sobel算子、cannay邊緣檢測法、分水嶺分割算法、光流法、camshift算法、K-Means聚類算法等對蠶繭圖像進(jìn)行處理。其中，腐蝕膨脹法能很好地填充圖像孔洞，消除圖像噪聲，并取得合適大小的圖像，但腐蝕膨脹次數(shù)很難確定，且無法分割深度粘連圖像;sobel算子、cannay邊緣檢測算法在沒有粘連的蠶繭圖像中效果非常好，能夠很好地檢測出圖像邊緣，但無法分割粘連圖像;分水嶺算法基本能將蠶繭圖像分割出來，但它對噪聲敏感，且存在過度分割現(xiàn)象;光流法、camshift算法對于運(yùn)動目標(biāo)物的圖像具有很好的識別效果，但對邊緣不敏感;K-Means聚類算法對蠶繭圖像處理效果很好，且對光照要求不高，但對初始聚類中心的選擇要求很高，初始聚類中心選擇不當(dāng)極易陷入局部極小值。

1.1 腐蝕膨脹法

基本形態(tài)學(xué)運(yùn)算中腐蝕算法的作用是收縮圖像，膨脹算法則是腐蝕的對偶運(yùn)算，起到放大圖像的作用，同時它們都具有一定的濾波作用[6]。所謂腐蝕膨脹法，就是同時利用腐蝕和膨脹算法進(jìn)行圖像處理，先對圖像腐蝕一定次數(shù)(本實(shí)驗(yàn)為6次)，再設(shè)定膨脹的次數(shù)(本實(shí)驗(yàn)膨脹6次)。在腐蝕膨脹之前，先對蠶繭圖像進(jìn)行灰度化處理，灰度化后去除噪聲信息，再進(jìn)行二值化處理。圖像的二值化，是指將圖像上的像素點(diǎn)的灰度值設(shè)置為0或255，即將整幅圖像呈現(xiàn)出黑和白兩種視覺效果，其中一種顏色為背景區(qū)域，另一種顏色則為目標(biāo)區(qū)域。在OpenCV中，利用cvAdaptive Threshold對灰度圖像進(jìn)行閾值操作得到二值化圖像。通過對二值化蠶繭圖像的適當(dāng)腐蝕膨脹，得到適當(dāng)大小的蠶繭圖像，再進(jìn)行后續(xù)處理。在OpenCV中，利用cvErode對圖像進(jìn)行腐蝕運(yùn)算，利用cvDilate對圖像進(jìn)行腐蝕運(yùn)算[7]。膨脹和腐蝕效果如圖1所示。

圖1 腐蝕膨脹處理效果Fig.1 Treatment effect of corrosion expansion

由圖1可知，單純的使用腐蝕膨脹法無法將粘連的蠶繭分離，因此需要對蠶繭圖像進(jìn)行進(jìn)一步的處理。

1.2 K-M eans聚類算法

傳統(tǒng)K-Means算法的基本思想是初始隨機(jī)給定K個簇中心，按照最鄰近原則把待分類樣本點(diǎn)分到各個簇。然后按平均法重新計算各個簇的質(zhì)心，從而確定新的簇心。一直迭代，直到簇心的移動距離小于某個給定的值。

K-Means聚類算法主要分為4個步驟:1)為待聚類的點(diǎn)尋找聚類中心;2)計算每個點(diǎn)到聚類中心的距離，將每個點(diǎn)聚類到離該點(diǎn)最近的聚類中去;3)計算每個聚類中所有點(diǎn)的坐標(biāo)平均值，并將這個平均值作為新的聚類中心;4)反復(fù)執(zhí)行2)、3)，直到聚類中心不再進(jìn)行大范圍的移動或者聚類次數(shù)達(dá)到要求為止[8]。

聚類技術(shù)中，K-Means算法是基于劃分的方法，具有可靠、有效、簡單、快速的優(yōu)點(diǎn)。然而該算法對選取初值要求很高，選取不同的初值往往會導(dǎo)致不同的聚類結(jié)果;且它是基于目標(biāo)函數(shù)進(jìn)行聚類的，一般采用梯度法求解極值。由于梯度法的搜索方向一般都是沿著能量遞減的方向進(jìn)行，因此當(dāng)初始聚類的中心選擇不當(dāng)時，極易陷入局部極小值點(diǎn)[9]。

2 蠶繭粘連分割的實(shí)現(xiàn)

2.1 改進(jìn)K-Means算法的思想

在K-Means算法中，初始聚類中心的選擇不同往往會得到不同的聚類結(jié)果，且準(zhǔn)確率也不同。改進(jìn)KMeans算法的研究旨在如何可以在圖像上快速找到各個數(shù)據(jù)的初始聚類中心，盡可能準(zhǔn)確地找到數(shù)據(jù)在空間分布上的分布，從而對圖像上的數(shù)據(jù)進(jìn)行劃分。KMeans算法是用歐氏距離作為相似性度量的，數(shù)據(jù)距離越遠(yuǎn)，它們屬于不同聚類的可能性就越大。如果找到相對距離最遠(yuǎn)的數(shù)據(jù)對象有K個，則表示不同的數(shù)據(jù)集合為K個，然后可以找到與空間分布上的數(shù)據(jù)相一致的初始聚類中心。假設(shè)在一個二維數(shù)據(jù)集U中，為了在圖像上找到空間分布與數(shù)據(jù)相一致的數(shù)據(jù)集合，采取如下方法:1)多次嘗試確定最佳聚類數(shù)目K，分別計算兩兩數(shù)據(jù)對象之間的距離;2)找到相距最遠(yuǎn)的數(shù)據(jù)對象，并將它們定義為兩個獨(dú)立的數(shù)據(jù)對象a1，a2，記錄數(shù)據(jù)對象 a1，a2，然后從 U 中刪除;3)計算數(shù)據(jù)對象a1，a2與集合U中每一個數(shù)據(jù)對象的距離，找出在U中與a1，a2同時相距最遠(yuǎn)的數(shù)據(jù)對象，將它設(shè)為數(shù)據(jù)對象a3，記錄a3并從U中刪除;4)重復(fù)2)、3)過程，直到確定了圖像上的所有數(shù)據(jù)對象為止;5)計算U中的各個樣本到數(shù)據(jù)對象a1，a2，a3，…，ak的距離，將樣本與相距最近的數(shù)據(jù)對象 a1，a2，a3，…，ak合并，形成對應(yīng)的 b1，b2，b3，…，bk數(shù)據(jù)對象集合;6)對b1，b2，b3，…，bk對象集合中的所有數(shù)據(jù)對象分別求算術(shù)平均，得到K個初始聚類中心。

2.2 改進(jìn)的K-Means算法的步驟

假設(shè)在一個二維數(shù)據(jù)集R中，包含有9個蠶繭樣本(A～I(xiàn))，其分布如圖2所示。

圖2 二維蠶繭樣本分布Fig.2 Two-dimensional cocoonsample distribution

根據(jù)2.1中尋找初始聚類中心的思想，將蠶繭樣本圖像劃分為3類。其中一類為背景，一類為蠶繭邊緣信息，一類為蠶繭中心信息。過程如下:1)計算蠶繭圖像中兩兩蠶繭樣本之間的距離，可以得出蠶繭A、蠶繭H之間的相距最遠(yuǎn)，那么將A、H作為數(shù)據(jù)對象粘a1，a2，記錄a1，a2并將它們從總的數(shù)據(jù)集合R中刪除。2)計算R中所有蠶繭樣本到A、H的相對距離，得出B與A、H的相對距離最遠(yuǎn)，將B作為數(shù)據(jù)對象a3，記錄a3并將它從集合 R中刪除。3)集合R中與a1相鄰的對象是C和D，將C和D與a1合并形成集合b1。集合R中與a2相鄰的數(shù)據(jù)對象是 E、I、G，將 E、I、G 與 a2合并成集合 b2。集合 R中與a3相鄰的對象是B。將B與a3合并形成集合b3。4)對集合b1、b2、b3中的樣本數(shù)據(jù)分別求算術(shù)平均值，形成3個初始聚類中心，然后利用K-Means聚類算法生成最終聚類。

經(jīng)過步驟1)～4)后，形成的初始聚類中心更加相符于實(shí)際樣本的分布，從而可以得到更好的聚類效果。

3 改進(jìn)算法的實(shí)驗(yàn)驗(yàn)證

3.1 環(huán)境搭建

為了使整個計數(shù)系統(tǒng)具有更好的人機(jī)交互功能，利用VS 2008 C++中的GUI界面開發(fā)功能，設(shè)計了更為便捷的圖像處理界面，省去了直接運(yùn)行程序的繁瑣步驟，使操作更符合人性化。設(shè)計的人機(jī)交互界面如圖3所示。

圖3 蠶繭自動計數(shù)系統(tǒng)人機(jī)交互界面Fig.3 Man-computer interaction interface of automatic cocoon countingsystem

3.2 實(shí)驗(yàn)驗(yàn)證

為了驗(yàn)證改進(jìn)K-Means算法對粘連對象的分離效果，對使用canny邊緣檢測算法、傳統(tǒng)的K-Means算法、改進(jìn)的K-Means算法等進(jìn)行了對比實(shí)驗(yàn)。實(shí)驗(yàn)的平臺是 Windows XP、2.60GHz CPU、2.91GB 內(nèi)存，500GB硬盤。開發(fā)工具是采用VS 2008 C++。整個實(shí)驗(yàn)過程中，對多幅蠶繭圖像的統(tǒng)計數(shù)目和處理時間進(jìn)行了記錄和比較。實(shí)驗(yàn)方法:分別多次利用不同的算法對同一蠶繭圖像進(jìn)行處理，計數(shù)并記錄計數(shù)時間。選取其中的兩幅原始蠶繭圖像的處理效果和計數(shù)結(jié)果來說明，其中處理效果如圖4、圖5所示。

圖4 各算法對粘連蠶繭圖像1的處理效果Fig.4 Treatment effect of algorithms for adhesive cocoon image 1

圖5 各算法對粘連蠶繭圖像2的處理效果Fig.5 Treatment effect of algorithms for adhesive cocoonsample 2

3.3 結(jié)果分析

經(jīng)過canny邊緣檢測算法、傳統(tǒng)的K-Means算法、改進(jìn)的K-Means算法分別對原始圖像進(jìn)行處理后，再分別使用cvFind Contours對處理后的蠶繭圖像進(jìn)行計數(shù)，計數(shù)結(jié)果如表1所示，處理時間如表2所示。

表1 不同算法的計數(shù)結(jié)果Tab.1 Counting result of different algorithms number

表2 不同算法的處理時間Tab.2 Processing time of different algorithms ms

其中，蠶繭圖像3為沒有粘連的蠶繭圖像，圖像4為有輕微粘連的蠶繭圖像，圖像5和圖像6為粘連程度較深的蠶繭圖像。從圖4、圖5和表1中可以得出結(jié)論:改進(jìn)的K-Means算法能很好地分離粘連的蠶繭圖像，實(shí)現(xiàn)正確的計數(shù);從表2中可以得出結(jié)論:與傳統(tǒng)的K-Means算法比較，改進(jìn)的K-Means算法能在不增加處理時間的情況下提高計數(shù)的準(zhǔn)確率，實(shí)現(xiàn)正確的計數(shù)。

4 結(jié)論

利用VS 2008 C++圖像處理技術(shù)對實(shí)驗(yàn)蠶繭粒數(shù)進(jìn)行計數(shù)，為研究緒下繭粒數(shù)實(shí)時檢測技術(shù)提供了理論依據(jù)。實(shí)驗(yàn)結(jié)果表明，K-Means聚類算法能很好地解決蠶繭粘連的問題，使計數(shù)系統(tǒng)計數(shù)能獲得很高的準(zhǔn)確度，具有一定的理論研究價值和學(xué)術(shù)價值。

[1]胡征宇.影響自動繅生絲均方差的因素分析[J].絲綢，2005(12):31-34.HU Zhengyu.The influence factor analysis of automaticsilk reeling meansquare error[J].Journal of Silk，2005(12):31-34.

[2]駱志堅(jiān)，張宏建，漆隨平，等.基于計算機(jī)視覺檢測技術(shù)自動計數(shù)系統(tǒng)的研究與應(yīng)用[J].儀表技術(shù)與傳感器，2005(3):19-21.LUO Zhijian，ZHANG Hongjian，QI Suiping，etal.Study and application of automatic countsystem based on computer vision detect technology[J].Instrument Technique and Sensor，2005(3):19-21.

[3]余曉流，馬欣藝，儲劉火，等.一種新型棒材自動計數(shù)與控制裝置的研究[J].冶金自動化，2006(4):54-57.YU Xiaoliu，MA Xinyi，CHU Liuhuo，etal.Research on a new kind of automatic counting and control device for bar and rod[J].Metallurgical Industry Automation，2006(4):54-57.

[4]朱從容.一種基于機(jī)器視覺的魚苗自動計數(shù)方法[J].漁業(yè)現(xiàn)代化，2009，36(2):25-28.ZHU Congrong.A fish fry automatic counting method based on machine vision[J].Fishery Modernization，2009，36(2):25-28.

[5]劉世晶，陳軍，劉興國.基于圖像處理技術(shù)的小球藻熒光圖像自動計數(shù)方法研究[J].漁業(yè)現(xiàn)代化，2012，39(5):16-20.LIU Shijing，CHEN Jun，LIU Xingguo，etal.Study on Chlorella automatic counting based on the algae fluorescence excitation effect[J].Fishery Modernization，2012，39(5):16-20.

[6]蔣東升.基于數(shù)學(xué)形態(tài)學(xué)的邊緣檢測算法的研究[D].成都:電子科技大學(xué)，2012:9-12.JIANG Dongsheng.Study of Edge Detection Based on Mathematical Morphology Algorithm[D].Chengdu:University of Electronic Science and Technology，2012:9-12.

[7]GRAY Bradski，ADRIAN Kaebler.Learning OpenCV Computer Vision with the OpenCV Library[M].Beijing:Tsinghua University Press，2009:259-270.

[8]于海濤，李梓，姚念民.K-Means聚類算法優(yōu)化方法的研究[J].小型微型計算機(jī)系統(tǒng)，2012(10):2273-2277.YU Haitao，LIZi，YAO Nianmin.Research on optimization method for K-Means clustering algorithm[J].Journal of Chinese Computer Systems，2012(10):2273-2277.

[9]易云飛，張志平，蔡永樂，等.K-Means算法在網(wǎng)路入侵檢測中的應(yīng)用研究[J].軟件導(dǎo)刊，2013(12):64-66.YIYunfei，ZHANG Zhiping，CAI Yongle，etal.Research on K-Means algorithm and its application for network intrusion detection[J].Software Guide，2013(12):64-66.