基于改進K-Means算法的蠶繭自動計數方法的研究

黃 靜，張 琦，江文斌

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

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

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

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

1 蠶繭自動計數算法研究

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

1.1 腐蝕膨脹法

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

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

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

1.2 K-M eans聚類算法

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

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

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

2 蠶繭粘連分割的實現

2.1 改進K-Means算法的思想

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

2.2 改進的K-Means算法的步驟

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

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

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

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

3 改進算法的實驗驗證

3.1 環境搭建

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

圖3 蠶繭自動計數系統人機交互界面Fig.3 Man-computer interaction interface of automatic cocoon countingsystem

3.2 實驗驗證

為了驗證改進K-Means算法對粘連對象的分離效果，對使用canny邊緣檢測算法、傳統的K-Means算法、改進的K-Means算法等進行了對比實驗。實驗的平臺是 Windows XP、2.60GHz CPU、2.91GB 內存，500GB硬盤。開發工具是采用VS 2008 C++。整個實驗過程中，對多幅蠶繭圖像的統計數目和處理時間進行了記錄和比較。實驗方法:分別多次利用不同的算法對同一蠶繭圖像進行處理，計數并記錄計數時間。選取其中的兩幅原始蠶繭圖像的處理效果和計數結果來說明，其中處理效果如圖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 結果分析

經過canny邊緣檢測算法、傳統的K-Means算法、改進的K-Means算法分別對原始圖像進行處理后，再分別使用cvFind Contours對處理后的蠶繭圖像進行計數，計數結果如表1所示，處理時間如表2所示。

表1 不同算法的計數結果Tab.1 Counting result of different algorithms number

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

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

4 結論

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

[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]駱志堅，張宏建，漆隨平，等.基于計算機視覺檢測技術自動計數系統的研究與應用[J].儀表技術與傳感器，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]余曉流，馬欣藝，儲劉火，等.一種新型棒材自動計數與控制裝置的研究[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].漁業現代化，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]劉世晶，陳軍，劉興國.基于圖像處理技術的小球藻熒光圖像自動計數方法研究[J].漁業現代化，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]蔣東升.基于數學形態學的邊緣檢測算法的研究[D].成都:電子科技大學，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聚類算法優化方法的研究[J].小型微型計算機系統，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算法在網路入侵檢測中的應用研究[J].軟件導刊，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.