基于K-means聚类算法分类的水果等级识别与应用

朱 玲

(湖北工业大学 工程技术学院,武汉 430068)

0 引言

高品质的水果和蔬菜是在当今竞争激烈市场成功的首要条件,也是水果加工成果汁、糖浆和葡萄酒的基础,人们对优质和新鲜的水果需求不断增长。传统的水果和蔬菜分类和分级耗时长,需要大量的人力物力。本文采用K-means聚类和BP神经网络相结合的方法,设计了一种水果等级分类识别模型,可以实现对水果质量等级的自动分类,能够大大提高水果等级分类效率。

1 K-means聚类算法

所谓“聚类”,就是将统一类型的成员集中进行管理和分类,是数据挖掘技术的一个重要分支。在数据挖掘算法中,聚类算法主要包括基于层次、密度、划分、网络和模型的5种基本算法,而K-means是聚类算法中一种常用的基于划分的算法。

K-means聚类算法的简要描述如下:假设有1个样本集X={xi|i=1,2,3,…,N},存在K个等级类型Cj(j=1,2,…,K)和K个聚类中心Aj(j=1,2,3,…,K),则N个样本间的欧式距离公式为

(1)

样本集X的聚类中心为

(2)

K-means聚类算法的核心思想是:确定k个中心点,进行最小化聚类误差,而聚类误差定义为所有数据点到其各自聚类中心的距离之和,从而判断该对象是属于哪一类。

(3)

其中,Cj为第j个等级集合的样本数据;cj为第j个等级类型的聚类中心;E为样本聚类误差平方准则和,当E逐渐收敛时,聚类过程结束。

K-means算法采用模糊分组的方法,将n个向量Xi(i=1,2,...,n)分为c组,并求每组的聚类中心,隶属矩阵u允许有取值在0,1间的元素,通过归一化规定,1个数据集的隶属度的和总等于1,其表达式为

(4)

则可以得到FCM的目标函数为

(5)

其中,ci为模糊组I的聚类中心;dij=‖ci-xj‖为第I个聚类中心与第J个数据点间的欧几里德距离,且m∈[1,∞)是一个加权指数。通过构造如下新的目标函数,可求得使式(2)达到最小值的必要条件,即

(6)

其中,λj、j=1～n是式(1)的n个约束式的拉格朗日乘子,对所有输入参量求导,使式(2)达到最小的必要条件为

(7)

(8)

假设采集到的农作物环境分类数据集合为X={x1,x2,...,xN},其中每一个数据集合xk有n个特性指标,设为Xk={x1k,x2k,...,xNk}T。

K-means聚类算法流程如下:

1)随机选择k个模式作为初始k中心,分配剩下N-k模式到中心最近的聚类,并计算所获得聚类的新中心。

2)根据欧式距离公式(1),计算距离聚类中心的距离,并选择最小值的类作为该对象的所属类别,即

(9)

其中,xi=(xi1,xi2,…,xip)和xj=(xj1,xj2,…,xjp)为包含P维的对象。

3)在每个类簇中,计算数据对象均值,从而得到新的聚类中心,即

(10)

4)一直重复进行2)和3),直至结果趋于收敛。

为了更清晰地表达聚类算法的核心思想,本文将用一组数据详细描述K-means算法流程,假设存在10个样本对象{x1,x2,x3,…,x10},而每个样本有两种属性{xi1,xi2},如表1所示。

表1 K-means聚类算法数据集Table 1 The data set of K-means clustering algorithms。

设定聚类数为2,采用K-means聚类算法分别计算各对象到聚类中心的距离,迭代的过程如图1和图2所示(实圆为类簇中心)。当迭代到第4次时,趋于收敛。因此,经过K-means计算得到两类分别为{x1,x8,x9,x10}和{x2,x3,x4,x5,x6,x7},总共迭代了4次。

根据欧式距离公式(1),计算距离聚类中心的距离,并选择最小值的类作为该对象的所属类别。

图1 K-means聚类算法第1次迭代Fig.1 The first iteration of K-means clustering algorithm。

图2 K-means聚类算法第4次迭代Fig.2 The fourth iteration of K-means clustering algorithm。

2 水果图像采集与处理

2.1 水果图像的获取

为了尽量逼近真实识别分类环境,采集到具有代表性的样本。试验采用1200万像素的相机对水果进行拍摄,背景色均为白色,分别在不同光线、角度获取了大量原始数据。本文采集到的水果主要包括苹果、梨子、火龙果、石榴、香蕉、橘子等水果,每种水果分别获取了500张高清的相片,共计3000幅。获取到的水果图像如图3所示。

图3 获取到的水果图像Fig.3 The obtained fruit image。

在水果图像拍摄过程中,充分考虑了角度、光线和遮挡问题,使得拍摄到的图像更加符合要求,如图4所示。

图4 不同角度、光线和遮挡下采集到的水果图像Fig.4 The captured fruit images from different angles, light and occlusion。

为了方便处理,采用Photoshop CS6.0软件对采集到的相片进行归一化处理,得到了640×480的图像。

2.2 水果图像的预处理

水果图像预处理主要包括尺寸裁剪、滤波、图像增强、特征抽取和分割等,是进行水果等级识别分类的基础,且图像增强是非常关键的一个环节。为了实现更好的图像预处理,对图像进行了彩色空间选择和滤波。

1)彩色空间选择。图像预处理中有很多的颜色空间模型,其中RGB颜色模型的亮度和色彩未实现分离,具有较强的关联性,边缘像素无法较好地保存。RGB颜色模型如图5所示。

图5 RGB颜色模型Fig.5 RGB color model。

HSV模型中,H通道可以消除目标物体受到亮度的影响,V通道则可以反应出目标物体的信号强度。颜色模型如图6所示。

图6 HSI颜色模型Fig.6 HIS color model。

在进行图像预处理过程中,先将采集到的图像转为HSV模型,然后对图片进行亮度、均衡化、阈值化等处理,再转换成RGB颜色模型进行最终的图像增强。RGB颜色模型转化成HSV模型的公式为

Max←max(B,G,R)

(11)

Min←min(B,G,R)

(12)

(13)

(14)

V←Max

(15)

其中,H为色调值;S为饱和度值;V为明度值;R为红;G为绿;B为蓝。Max和Min分别为B、G和R中的最大值、最小值。H∈[0,360]为角度的色相角,而S、V∈[0,1]为饱和度和亮度值。

2)滤波器选择。图像处理常用的有均值、高斯、直方图均衡化和中值等滤波算法,在研究过程中,为了提高图像处理的质量,采用了中值和直方图均衡化两种算法。

直方图均衡化处理中的主要滤波函数为

(15)

其中,0≤rj≤1,k=0,1,2,3,…,l-1;l为灰度级所有的数目;Pr(rj)为灰度第j级的的概率;nj和n为灰度出现的次数和总数。

中值滤波的基本思想是使用标准模板在原始图像中滑动,对原始图像内的像素做大小排序,取序列的中值作为图像该像素点处中值滤波的结果。中值滤波器计算公式为

yk=med(xk-n,xk-n+1,xk-n,…,xk,xk+n+1,xk+n)

(16)

3 K-means聚类和BP神经网络结合

为了提高系统分类识别的精准度,在K-means聚类算法的基础上增加了BP神经网络算法。二者结合的构造分类模型,如图7所示。

图7 水果等级识别的分类模型Fig.7 The classification model of fruit grade recognition。

水果等级识别的分类模型描述如下:

输入:待识别分类的水果图像;

输出:已经识别分类的水果图像。

本文研究的K-means聚类和BP神经网络相结合的水果等级识别方法的实现过程如下:

1)提出特征参数。对输入的图像进行图像预处理,然后提取水果图像的特征值。

2)聚类。选取分类类别为特级、一级、二级、三级等4个等级,对等待识别分类的图像利用K-means方法进行聚类,得到准确的聚类中心。

3)BP神经网络。设置神经网络的结构,确定输入、隐藏和输出等网络层数、训练函数、实现神经网络的识别分类器。

4)分类识别。对训练完成的分类模型输入测试数据,计算出识别分类的正确率。

4 水果分类识别结果分析

本文总共采集了3 000张水果图像,其中2 100张用于分类模型的训练集,600张用于测试集,300张用于试验验证。试验中,将水果图像直接作为分类模型的输入图像,分别制作训练集和试验集水果的等级标签,标签用特级、一级、二级和三级表示;将训练集、试验集和水果便签放于K-means聚类和BP神经网络相结合的水果分类模型中训练,验证分类模型的性能。判定标准为:分类识别正确率越高,模型性能越好。

分类识别正确率为

(17)

其中,la和label分别为数据输入、输出的标签;sum表示分类的总和。

训练完成后,对50张石榴图像进行了分类测试试验,分别采用K-means算法、BP神经网络算法和二者结合的分类算法进行了分类识别。通过3种算法的识别正确率,可以判断出哪种算法最优。石榴图像如图8所示,3种算法的等级分类识别正确率如表2所示。

图8 石榴图像Fig.8 The pomegranate image。

表2 3种算法的等级分类识别正确率Table 2 The recognition correct rate of classification of three algorithms。

由表1可以看出:单独采用K-means算法的等级分类正确率为91.52%,BP神经网络算法为89.36%,采用K-means聚类和BP神经网络相结合的水果分类算法的正确率为96.28%。因此,采用K-means聚类和BP神经网络相结合的方法,大大提高了水果分类识别的准确率,并使得识别时间大幅缩短,具有一定的现实意义。

5 结论

针对目前水果质量等级分类难、耗时长的问题,采用K-means聚类和BP神经网络相结合的方法,设计了一种水果等级分类识别算法,可以实现对水果质量等级的自动分类。试验结果表明:采用K-means聚类和BP神经网络相结合的方法,大大提高了水果分类识别的准确率,并使得识别时间大幅降低,具有一定的现实意义。