基于改进K均值聚类的葡萄果穗图像分割

刘智杭， 于 鸣， 任洪娥

(东北林业大学信息与计算机工程学院，黑龙江哈尔滨 150040)

葡萄是一种重要的农作物，全球市场报告显示，2017年我国的葡萄产量达到1 020万t[1]。依靠人工进行大面积葡萄采摘耗时费力，葡萄采摘机器人可以有效改善这一情况[2]，如何提高机器采摘的速度和准确率已成为国内外现代化农业研究的重点问题。

采摘机器人对果实位置定位的准确程度是采摘成功的关键因素。图像分割是图像识别和机器视觉的基础，对于加快机器采摘速度和提高机器采摘准确率的意义重大。图像分割是指根据颜色、纹理等特征将图像分成若干个互不交叠区域并提出感兴趣目标的技术和过程[3]。常用的图像分割方法主要有：基于图像灰度特征的阈值分割、利用图像局部特征不连续性的边缘检测分割、根据图像相似性准则的区域分割及利用聚类分析的图像分割等[4]。其中基于K均值聚类的图像分割方法不受图像形状和边界的限制，分割效果显著，在人脸识别、医学造影、果实识别等方面都有应用[5]。如刘国成用色度值作为特征向量进行K-means聚类，将对图像进行分割的任务转化为对数据集合进行分类的任务，从背景中能有效地识别出叶片上的叶螨害虫，平均识别率达93.95%[6]。由于K-means聚类算法本身存在着过于依赖于初始聚类中心的选择、对于离群点和孤立点过于敏感和容易陷入局部最优等问题，很难保证分割精确度，很多学者将K-means算法与其他算法结合进行改进[7]。徐黎明等在Lab空间下结合同态滤波和K-means算法对彩色杨梅图像进行分割，并进行了3组试验来比较不同形态的杨梅分割情况，一定程度上减少了光照对于分割的影响，但若背景复杂会导致较大的误差[8]；张善文等根据图像直方图的峰值划分区域，并将区域中值作为聚类中心，改善了初始聚类中心选择的不足，但边缘处分割效果不好[9]；赵文昌等提出一种人工蜂群融合K-means聚类的分割算法，提高了4.8%的分割准确率，但算法没有考虑自然环境因素，实用性效果不好[10]。

针对上述问题，本研究提出一种改进K-means聚类算法的图像分割方法。采用局部异常因子算法[11]来优化K-means聚类中心的选择，可以有效地剔除数据集合中的离群点，使分割后的葡萄果穗图像更加完整，能够满足采摘机器人对目标图像在复杂背景下分割精确度高的要求。

1 改进的K均值聚类算法

1.1 基本算法描述

1.1.1 K-means算法 MacQueen在1967年提出了K-means算法[12]。该算法是一种基于距离的聚类算法，基本思想是对于给定的观测值集合P={P1，P2，…，Pn}，根据集合P的某种属性特征将集合分为k个类别S={S1，S2，…，Sk}(k≤n)，然后随机选择k个数据点作为Si(i=1，2，…，k)的初始聚类中心，计算对象到初始聚类中心的距离将其分配给最近的类别，最后计算重新划分的k个集合的聚类中心，算法不断迭代分配然后计算的这一整个过程，直到聚类中心基本不变。最终以群内平方和(即方差)作为聚类准则函数，方差越小聚类效果越好[13]。有关概念：

概念1：分配原则。给定初始聚类中心集合s={s1，s2，…，sk}，比较数据点Pi到sj欧氏距离d(Pi，sj)，将Pi分配给最小欧氏距离时sj所属的类别

(1)

概念2：聚类中心。聚类中心即每个类别Sj的质心，计算公式如下：

(2)

1.1.2 局部异常因子(LOF)算法 Breunig等在2000年提出基于局部密度概念的局部异常因子(LOF)算法[14]，其中局部由集合中k个最近邻居给出，密度由局部中k个邻居的距离得出。有关概念：

概念2：对象空间距离。集合P中的对象之间的可度量距离，记为k-d(Pi，Pk，w)，给定对象Pi，Pk∈{P}两者间的颜色特征加权距离为

(3)

(w∈[0，1])，该距离为数据间基于k维非空间属性的加权距离。

概念3：对象Pi的K-距离邻居。在给定对象Pi的k-d(Pi)时，Pi的K-距离邻居包括所有和对象Pi之间的带权距离小于或等于k-d(Pi)的对象的集合，记为Nk(Pi)。

Nk(Pi)={k-d(Pi,p′,w)≤k-d(Pi)}(p′∈P/{Pi})。

(4)

k-d(Pi)是对象Pi的K-距离，即对象Pi与集合P中某个对象p之间的欧氏距离dist(Pi，p)，它需要满足2个条件：至少有k个对象p′∈P/{Pi}，d(Pi，p′，w)≤d(Pi，p，w)；至多有k-1个对象p′∈P/{Pi}，d(Pi，p′，w)

概念4：Pi的局部偏离率。Pi的局部偏离率反映了对象Pi附近数据点的分布情况，记为LDRk(Pi)。

(5)

p′为Pi的K-距离邻居的质心，LDRk(Pi)的值越大说明对象Pi附近的分布密度越小，该点是离群点的概率越大；LDRk(Pi)的值越小说明对象Pi附近的分布密度越大，该点是离群点的概率越小。

概念5：Pi的局部偏离影响率。Pi的局部偏离影响率反映了属于对象Pi的K-距离邻居集合的数据点对于对象Pi的偏离程度的影响，记为LIRk(Pi)。

(6)

分子为对象Pi的K-距离邻居集合中所有数据点的局部偏离率之和。

概念6：Pi的局部偏离因子。Pi的局部离群因子反映了对象Pi的K-距离邻居集合中相邻数据点的分散程度，记为LOFk(Pi)即

(7)

局部偏离因子的值越大，表明该对象周围的邻居数据点分布密集，不是离群点，局部偏离因子的值越小，表明该对象离其他邻居数据点较远，分布较为稀疏，很可能是离群点。

1.2 基于LOF的改进K-means算法

(1)输入参数计算。参数1：数据集P。初始化数据集合P={P1，P2，…，Pn}，将图片中的每个像素点作为数据点放入集合P，提取每个像素点的R、G、B3个通道分量值，构造三维数组A(i，j，k)，存放像素点的值(图1)。根据CIE国际照明委员会给出的RGB颜色空间色度值在结合专家意见给不同色度值分配权重，W={w1，w2，…，wd}。

参数2：聚类的类别数k。考虑到试验所用的葡萄图片整体上可以分为葡萄果穗和背景2个部分，再综合对运行速度等因素的考虑，将聚类的类别数k设定为2。

(2)根据式(3)计算每个对象与集合中其他数据点之间的加权空间距离，挑选出k个最小距离的点作为对象的 K- 距离邻居，其中距离最大者为对象的K-距离，然后求算对象与其K-距离邻居的质心之间的距离，再根据式(5)计算出对象的局部偏离率，根据式(6)计算局部偏离影响率，根据式(7)计算局部偏离因子。

(3)通过得到的局部偏离因子的值将数据集合重新排序，剔除局部偏离因子值偏大的前n个数据，创建新的数组A′(i，j，k)，用来存放去除离群数据点后的数据集合。

(4)用LOF算法输出的数据集合重新构造R、G、B等3个通道的分量值，然后合并3个通道并转换为HSI颜色空间，最后提取H分量值构成新集合P′。

(5)根据式(1)将集合P′中的每个对象分配给与其欧氏距离最近的第k个类别，根据式(2)计算分配后k个类别的聚类中心。

2 葡萄果穗图像分割

2.1 选取颜色空间

对于一张彩色葡萄图片，人眼可以轻松地观察出背景和葡萄果穗的分界线，识别出自己需要的部分。计算机以像素数据的形式存储彩色图片，要在大量的像素数据中得到需要的目标图像，需要选择合适的颜色空间和算法对图片进行有效分割。

通过CIE(国际照明委员会)提出的CIE1931-RGB标准色度系统演变出的颜色空间有RGB、HSI、LAB等[15]。普遍使用的RGB颜色空间是由三原色R(红)、G(绿)、B(蓝)进行不同程度的叠加形成的。由于缺少人的视觉系统对于颜色感知的亮度等信息，表示出的图片颜色与人眼识别出的颜色色差较大，不适用于自然背景下图像的颜色聚类。为解决RGB颜色空间颜色不均匀的问题，本算法采用了HSI颜色空间，HSI颜色空间使用色调(H)、饱和度(S)、亮度(I)来描述色彩，一方面HSI表示颜色的方式更加符合人眼对颜色的感知和描述；另一方面，HSI空间将亮度I与色调H分离，用饱和度S表示颜色的纯净度，降低颜色空间3个通道的关联性，减小自然光照下试验图片亮度不均匀对试验结果的影响[16]。

2.2 光线补偿和去噪

数字图像在拍摄和传输的过程中会受到成像设备和外部环境的影响，易造成图像色彩偏差、图像中细节不突出或者图像产生噪声点等问题[17]，这些因素会干扰图像分割的精准度，因此在进行图像分割前对图像进行预处理是必要的。本算法首先采用gamma校正来对图像进行光线补偿，以图2所示葡萄果穗原图为例，图3-a为原图的散点图，进行光线补偿后得到的散点图见图3-b，剔除离群点后得到的散点图见图3-c，比较发现，gamma校正[18]后图像中的像素点集中在坐标系对角线上，有效地解决了光照不平衡造成的色彩偏差问题。然后使用中值滤波去除gamma校正过程中产生的噪声，其结果如图4所示。经过上述处理后，降低了噪音和光照的影响，使图像的光照更加均匀，实现了提高试验图像质量的目的，为之后的图像分割做好了准备。

2.3 图像分割过程

对图4的RGB空间图像提取R、G、B等3个通道的分量值进行FOL算法去除离群点[19]，如图3-c所示，分散在整体像素点边缘的稀疏分布像素点被准确剔除。FOL算法输出的像素点数据合并成的图像是RGB模式的，因此需要将图像从RGB空间转换为HSI空间，转换公式如下：

(8)

(9)

(10)

将根据公式(8)、(9)、(10)得到H、S、I等3个通道的分量值绘制成颜色直方图(图5)。观察图5-a可以发现，H分量直方图中背景与目标对象呈明显的双峰，选择H分量对图片进行聚类，然后再根据聚类结果对图像进行分割。

3 试验结果与分析

3.1 试验环境

联想电脑：处理器为Intel® CoreTMi7-6700，主频 3.40 GHz，内存为4 GB；软件运行环境：64位Windows操作系统，算法在MATLAB R2015b下实现。

为了验证本算法的有效性，选取50幅不同环境背景、不同光线、不同生长形态的葡萄果穗图片作为测试图片，分析其中4种具有典型特征的葡萄果穗图片：带有露珠的葡萄果穗如图6-a，2串相叠且有叶片遮挡的葡萄果穗如图6-b，有套袋遮挡的葡萄果穗如图6-c，背景复杂的葡萄果穗如 图6-d。

3.2 试验结果分析

为测试本算法的图像分割效果，分别使用Otsu、传统聚类算法和本算法对图6所示4种具有典型特征的葡萄果穗原图进行图像分割试验，3种算法的试验结果如图7所示。对于葡萄果穗的分割效果，Otsu算法最差，带有露珠和2串相叠有叶子遮挡的葡萄果穗分割后还能够分辨出整体葡萄轮廓，但在有葡萄套袋遮挡和复杂背景的葡萄果穗分割结果中，基本轮廓与背景部分相互交杂难以识别；传统的K-means算法在带有露珠、2串相叠有叶子遮挡和复杂背景的葡萄果穗分割试验中，能够识别出果穗轮廓但有部分缺失，在有葡萄套袋遮挡的葡萄果穗分割试验中，受葡萄套袋影响，果粒像素点丢失严重；本算法的葡萄果穗分割试验结果达到预期目标，实现了葡萄果穗轮廓的识别，其中带有露珠的葡萄果穗分割效果最好，对复杂背景中的葡萄果穗分割时，仅在果粒上有斑点的区域丢失少量像素点。

从图7-a可以看出，在果穗上的单颗果粒识别中，Otsu算法受到露珠影响较大，识别不出带露珠葡萄果粒的部分区域；传统K-means算法受到葡萄果穗上葡萄果粉面积不均匀的影响，导致属于目标对象聚类区域像素点部分被划分为非目标对象区域，且出现小面积的背景区域划分入目标区域内；本算法能够准确分割出果穗轮廓，且果穗上所有果粒的像素点没有缺失；观察图7-b发现，用Otsu算法分割的试验结果中有部分果梗混入目标区域且果粒区域像素点丢失严重；传统K-means算法分割结果中存在部分果粒区域丢失现象；本算法只有小面积果梗混入；图7-c中只有本算法准确将葡萄套袋区域识别并分割出来；图7-d中传统K-means算法和本研究算法都没有准确识别出葡萄果粒上的斑点区域，但本算法损失的葡萄果穗有效像素点数目更少。

4 结论

为解决K-means算法对离群点和孤立点敏感度高，容易陷入局部最优和过分依赖初始聚类中心选择等问题，提出一种融合LOF和K-means聚类算法的图像分割算法，利用LOF算法剔除数据中的离群点，采用局部偏离因子优化初始聚类中心的选择。将本算法分别与Otsu算法、传统聚类算法进行试验对比，结果表明本算法在分割准确度方面优于后2种算法。本算法为果实结构呈穗状且果粒密集相互堆叠的水果图像分割提出了一种新的思路。