基于SVM-KNN茶叶图像纹理分类

燕娅，周晓锋，汤哲，张立，陈华荣，周建勇

（1.中南大学软件学院，湖南长沙 410075；2.长沙湘丰智能装备股份有限公司，湖南长沙 410100）

基于SVM-KNN茶叶图像纹理分类

燕娅1，周晓锋1，汤哲2*，张立2，陈华荣2，周建勇2

（1.中南大学软件学院，湖南长沙 410075；2.长沙湘丰智能装备股份有限公司，湖南长沙 410100）

机采茶鲜叶的叶和芽混合，利用茶叶图像纹理特征对茶鲜叶进行分类，分类之后再加工有助于提高茶叶的质量和市场价值。支持向量机SVM是一种专门针对小样本、非线性、高维特征的经典分类算法，但对于茶叶这类自然图片在分界面附近的测试点容易出错。KNN是一种简单而经典的分类算法，核心在于向量间距离的计算，论文提出欧式距离和余弦相似度结合的方式作为KNN新的距离计算公式。改进的KNN与SVM结合起来，形成SVM-KNN算法应用于茶叶图像的纹理特征分类的研究中，并分析SVM-KNN的时间复杂度。对比实验表明，SVMKNN算法对茶叶图像纹理分类正确率有很大程度地提高，最高可达90%以上。

纹理特征；支持向量机；KNN；SVM-KNN；茶叶图像分类

现代化的机械采茶采用茶园蓬面一次或二次切割收获方式，收割后茶鲜叶的芽和叶混合在一起，因此机采茶叶的质量低于人力采摘的质量。尽管传统鲜叶分级机可以对茶鲜叶进行初级分类[1]，但分类精度均不高。在茶叶自动化生产流水线上，根据传送带上茶鲜叶的分类结果自动调整加工参数，芽被加工成优质茶叶，叶则被加工成普通茶叶。然而国内外目前针对茶鲜叶的分类的研究并不多，这不利于茶叶自动化的发展及优质茶叶的市场价值的实现。图像纹理特征是图像的重要特征之一。近些年来，邵明等人将计算机视觉用于龙井茶嫩芽的识别[2]，陈孝敬等人将多光谱图像颜色特征用于茶叶分类[3]，但这些茶叶的分类均非利用茶叶图像的纹理特征。江才华等将图像纹理与SVM结合起来对茶叶进行自动分类能达到90%的效果[4]。相对来说，国内对于利用纹理特征对茶叶分类的研究较少。

支持向量机（Support Vector Machine，SVM）是1995年Vapnik和Cortes首次提出的一种专门针对小样本、非线性及高维模式计算的机器学习算法[1，5]，建立在非传统的统计学理论（Statistical Learning Theory，SLT）之上，SLT理论保证了在小样本情况下SVM能得到全局最优解，避免了神经网络中的局部极值问题。SVM是分类和预测中最好的有监督学习（Supervised Learning）算法[6]，在文本分类、图像分类、函数优化与回归方面有着重要应用[7]。KNN是一种懒惰机器学习法（Lazy Learning），是小样本分类算法中较经典的高效算法，其分类速度取决于样本空间的大小。本文主要研究基于茶叶图像纹理特征的SVM-KNN算法对茶鲜叶的分类问题，并对实验结果做出详细说明。

1 支持向量机（SVM）算法

SVM的分类思想是将低维空间中线性不可分的样本映射到高维空间中使其变得线性可分，在高维空间中找到一个最优超平面（Optimal Hyperplane）对样本进行划分[8]。Optimal Hyperplane是使得两类距离最大的分类面，w·x+b=0即为最优超平面，它使得y=+1类与y=-1类之间的间隔Margin最大。

对于向量xi，yi表示类别，yi∈｛-1，1｝，若，yi（w·x+b=1），则xi称为支持向量（Support Vector）。SVM决策函数f（x）表达式为：

其中α1为系数，b为常数项，K（x，x1）为核函数内积结果。f（xi）>=0，xi属于+1类，f（xi）<0，xi属于-1类。常用核函数有 4种：Linear Kernel、Polynomial Kernel、Radial Basis Function （RBF,也称Gaussian Kernel）及Sigmoid Kernel。

SVM的性能受惩罚因子C和核函数参数γ两者共同影响[9]。可以使用遗传算法、粒子群算法等优化算法获得（C，γ）最佳参数，使SVM的训练模型最优，泛化效果最好。

2 K-最近邻居算法（KNN）

KNN核心思想是计算所有训练样本与测试样本的空间距离，选取距离最近的K个训练样本为测试点的最近邻居，K个最近邻居再进行投票分类[10]。

影响KNN性能有2个重要因素：1、距离或相似度的计算。常见的计算公式有欧式距离、曼哈顿距离、余弦相似度、皮尔逊相关系数等等，不同的计算公式会得到不同K最近邻结果，从而影响最终分类结果。2、参数K的选取，K过大，无关向量或者无关点会被考虑进来造成干扰，对分类结果产生偏差影响；K太小，在统计最近邻居中出现种类最多的类别时容易区分不开，得不到最优的分类结果。

欧氏距离强调的是纹理向量之间的绝对距离和差距，对方向不敏感；余弦相似度使用两个向量间夹角的余弦值来衡量特征向量之间的相似性，强调的是方向上的差异，对绝对数值不敏感。本论文提出使用欧式距离与余弦相似度性线性组合的方式来衡量纹理特征向量之间的相似性，并且分别赋予欧式距离与余弦相似度一定权值，改进距离公式如下：

其中w1+w2=1。在本论文实验中，取w1=w2= 0.5。

3 SVM-KNN分类算法

SVM对在分界面附近的茶叶纹理特征向量易出错，本文利用SVM的支持向量做一些改进，结合改进的经典算法KNN，提出SVM-KNN的结合算法，提高茶叶图像的分类精度。

3.1SVM-KNN分类算法理论

SVM-KNN算法描述：当测试样本离SVM的最优超平面距离大于给定阈值时，则认为该分类有效，取SVM分类结果作为输出值；当样本和最优超平面的距离小于给定阈值时，则认为此次SVM分类无效，使用改进型KNN对测试样本重新分类。KNN聚类的集合为对应支持向量集SVs，支持向量集的数量小于样本空间，减少计算量同时也保证测试点不会受原样本空间的非典型样本的影响。SVM-KNN算法描述如下：

1.使用LIBSVM中的svmtrain函数训练SVM分类模型，得到模型model的各项参数，包括SVs（支持向量）和SVs对应的系数ceof以及常数b；

2.设M为测试集，SVs为支持向量集，K为KNN聚类代表点的个数，

3.当M≠Φ，取测试点x∈M，若M=Φ，分类步骤结束；

5.将测试集T更新为｛T-｛x｝｝，返回步骤3。

在上述算法描述中，阈值 的选择根据SVM的反馈参数经验值一般在 [0.4，0.8]。K＝w'·min｛nSV1，nSV2｝，其中nSV为支持向量的数量，w'∈[0.5，1]。

3.2SVM-KNN时间复杂度分析

SVM的时间复杂度需要从训练阶段和分类阶段两方面分析。首先是训练阶段，设样本空间为N，训练样本为T，测试样本为M，支持向量的个数为Nsv，特征向量维数为d。实际求解中的经典训练算法Bunch-Kaufman的时间复杂度在O （Nsv3+ TNsv2+dTNsv）和O（dT2）之间，与训练过程中支持向量的选择有关，若Nsv＜＜T，则训练复杂度接近O（dT）；若Nsv→T，复杂度接近O（dT2）。其次是分类阶段的时间复杂度为O（MNsv）。SVM分类器的总复杂度为：

SVM-KNN的复杂度也分为训练阶段和分类阶段：训练阶段的复杂度与SVM的训练复杂度一样，分类阶段复杂度为SVM和改进型KNN之和，改进型KNN算法分类时间复杂度O（TNsv），因此SVM-KNN的总复杂度为：

由此可以看出SVM-KNN并没有增加SVM的复杂度。

4 茶鲜叶图像纹理分类实验及分析

本文对一芽一叶（A类）、一芽二叶（B类）和一芽多叶（C类）做分类实验，图片大小为640×640像素，每种类型茶叶100张，共计300张，训练集3×70=210，测试集3×30=90。茶鲜叶图像纹理特征16维：0°、45°、90°、135°四方向的对比度、相关度、同质性和能量。

图1 茶鲜叶种类示意图Fig.1 Kinds of tea leaves image

实验环境Matlab，采用支持多分类的工具包LIBSVM。在下列对比试验中分别采用16维纹理特征和随机选取10维纹理特征（4方向对比度，4方向相关性，0°和45°两方向同质性）。采用PSO优化算法搜索的 （C和γ）最佳参数，分别使用SVM和SVM-KNN做对比实验，结果如表1所示。其中多项式的维数参数d=1。图2为表1的两种算法的茶鲜叶分类精度对比图。

表1 基于SVM-KNN和SVM的茶鲜叶分类精度对比Table 1 Accuracy Comparison of tea classification based on SVM-KNN and SVM

图2 基于SVM-KNN与SVM的茶鲜叶分类精度对比Fig.2 Accuracy Comparison of tea classification based on SVM-KNN and SVM

表2 SVM-KNN和BP神经网络分类精度和时间对比Table 2 Accuracy and Time Comparison between SVM-KNN and BP Neural Network

由于BP神经网络是传统的较经典分类算法，因此本文也将BP神经网络实验结果加入到对比中，BP神经网络参数设置是：采用梯度下降法，最大迭代次数epochs=3000，目标误差goal= 0.01，学习率lr=0.01。

表2的精度对比图和时间对比图如图3和图4所示。从两图可以看出除Sigmoid（二层神经网络）外，SVM-KNN分类精度明显高于BP神经网络，运算时间大大缩减，SVM-KNN与BP神经网络的对比实验进一步说明了SVM-KNN仍保持着SVM相对于神经网络收敛快、无局部极值的优点和效率。

图3 SVM-KNN与BP分类精度对比图Fig.3 Accuracy Comparison between SVM-KNN and BP Neural Network

图4 SVM-KNN与BP分类时间对比图Fig.4 Time Comparison between SVM-KNN and BP Neural Network

5 结论

SVM-KNN分类器对三种类型茶鲜叶进行分类，并采用PSO优化算法寻找最佳参数，克服了SVM对在分界面附近的茶叶纹理特征向量易出错的缺陷，且没有增加SVM的时间复杂度，对茶鲜叶分类的效果最理想高达90%以上，对于计算机图像视觉技术融入实际应用中有着重要推动作用，并且对于提高茶叶生产质量和茶叶自动化连续生产有着积极作用。

[1] 张兰兰.机采名优茶鲜叶分级技术及分级机研究[D].浙江大学，2012.

[2] 邵明.基于计算机视觉的龙井茶叶嫩芽识别方法研究[D].中国计量学院，2013.

[3] 陈孝敬，吴迪，何勇，等.基于多光谱图像颜色特征的茶叶分类研究[J].光谱学与光谱分析，2008，28（11）:2527-2530.

[4] 汤哲，江才华，张立，等.基于纹理分析的茶青在线分类[J].高技术通讯，2014，24（6）:651-656.

[5] Cortes C，Vapnik V.Support-Vector Networks[J].Machine Learning，1995，20:273-297.DOI:10.1007/BF00994018.

[6] Burges C J C.A tutorial on support vector machines forpattern recognition.Data Mining and Knowledge Discovery[J].IEEE International Workshop on Visual Surveillance，1998，2（2）: 121-167.

[7] 丁世飞，齐丙娟，谭红艳.支持向量机理论与算法研究综述[J].电子科技大学学报，2011，40（1）:2-10.

[8] 王晓云.基于SVM的图像分类算法优化实现[J].信息安全与通信保密，2013（2）:59-62.

[9] Olivier C，Vladimir V，Olivier B，et al.ChoosingMultiple Parameters for Support Vector Machines[J].Machine Learning，2002，46（1-3）:131-159.

[10]Homaeinezhad M R，Atyabi S A，Tavakkoli E，et al.ECG arrhythmia recognition via a neuro-SVM-KNN hybrid classifier with virtual QRS image-based geometrical features[J].Expert Systems with Application，2012，39（2）:2047-2058.

Texture Classification of Tea Images Based on SVM-KNN

YAN Ya1，ZHOU Xiao-feng1，TANG Zhe2*，ZHANG Li2，CHEN Hua-rong2，ZHOU Jian-yong2
（1.School of Software，Central South University，Changsha 410075，China；2.Changsha Xiangfeng Intelligent Equipment Co.Ltd.，Changsha 410100，China）

The mechanical plucking tea are mixture of leaves and buds，thus if tea leaves can be classified by the texture feature of tea images before processing，it will contribute to improving the quality and market value of tea leaves. Support Vector Machine is a specific assort algorithm for small samples，nonlinear and high dimensional，but it easily makes mistakes near the hyperplane for nature image such as tea images.K-Nearest-Neighbor is a classic classification algorithm whose key point is to calculate the absolute space distance between different vectors.This paper proposed a new distance formula that linearly combined Euclidean with Cosine Similarity，and then，used the improved KNN and SVM to form a new algorithm called SVM-KNN which would be applied to the research of texture classification of tea images.Besides，it analyzed the time complexity of SVM.The comparison experiments showed that SVM-KNN obviously increased the accuracy of tea images assortment up to 90%and above.

Texture feature；Support Vector Machine；KNN；SVM-KNN；Tea images classification

S571.1；TP391.41

A

2095-0306（2016）06-0005-05

中国茶叶加工 2016（6）:5-9

2016-07-13

国家自然科学基金（31470028）；湖南省战略性新兴产业科技攻关项目（2014GK1020）

燕娅（1992-），女，湖南常德人，研究方向为图像处理、图像分类。

*通讯作者：tn8@163.com