基于改进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.