燕婭，周曉鋒，湯哲，張立，陳華榮，周建勇

（1.中南大學軟件學院，湖南長沙 410075；2.長沙湘豐智能裝備股份有限公司，湖南長沙 410100）

基于SVM-KNN茶葉圖像紋理分類

燕婭1，周曉鋒1，湯哲2*，張立2，陳華榮2，周建勇2

（1.中南大學軟件學院，湖南長沙 410075；2.長沙湘豐智能裝備股份有限公司，湖南長沙 410100）

機采茶鮮葉的葉和芽混合，利用茶葉圖像紋理特征對茶鮮葉進行分類，分類之后再加工有助于提高茶葉的質(zhì)量和市場價值。支持向量機SVM是一種專門針對小樣本、非線性、高維特征的經(jīng)典分類算法，但對于茶葉這類自然圖片在分界面附近的測試點容易出錯。KNN是一種簡單而經(jīng)典的分類算法，核心在于向量間距離的計算，論文提出歐式距離和余弦相似度結(jié)合的方式作為KNN新的距離計算公式。改進的KNN與SVM結(jié)合起來，形成SVM-KNN算法應用于茶葉圖像的紋理特征分類的研究中，并分析SVM-KNN的時間復雜度。對比實驗表明，SVMKNN算法對茶葉圖像紋理分類正確率有很大程度地提高，最高可達90%以上。

紋理特征；支持向量機；KNN；SVM-KNN；茶葉圖像分類

現(xiàn)代化的機械采茶采用茶園蓬面一次或二次切割收獲方式，收割后茶鮮葉的芽和葉混合在一起，因此機采茶葉的質(zhì)量低于人力采摘的質(zhì)量。盡管傳統(tǒng)鮮葉分級機可以對茶鮮葉進行初級分類[1]，但分類精度均不高。在茶葉自動化生產(chǎn)流水線上，根據(jù)傳送帶上茶鮮葉的分類結(jié)果自動調(diào)整加工參數(shù)，芽被加工成優(yōu)質(zhì)茶葉，葉則被加工成普通茶葉。然而國內(nèi)外目前針對茶鮮葉的分類的研究并不多，這不利于茶葉自動化的發(fā)展及優(yōu)質(zhì)茶葉的市場價值的實現(xiàn)。圖像紋理特征是圖像的重要特征之一。近些年來，邵明等人將計算機視覺用于龍井茶嫩芽的識別[2]，陳孝敬等人將多光譜圖像顏色特征用于茶葉分類[3]，但這些茶葉的分類均非利用茶葉圖像的紋理特征。江才華等將圖像紋理與SVM結(jié)合起來對茶葉進行自動分類能達到90%的效果[4]。相對來說，國內(nèi)對于利用紋理特征對茶葉分類的研究較少。

支持向量機（Support Vector Machine，SVM）是1995年Vapnik和Cortes首次提出的一種專門針對小樣本、非線性及高維模式計算的機器學習算法[1，5]，建立在非傳統(tǒng)的統(tǒng)計學理論（Statistical Learning Theory，SLT）之上，SLT理論保證了在小樣本情況下SVM能得到全局最優(yōu)解，避免了神經(jīng)網(wǎng)絡中的局部極值問題。SVM是分類和預測中最好的有監(jiān)督學習（Supervised Learning）算法[6]，在文本分類、圖像分類、函數(shù)優(yōu)化與回歸方面有著重要應用[7]。KNN是一種懶惰機器學習法（Lazy Learning），是小樣本分類算法中較經(jīng)典的高效算法，其分類速度取決于樣本空間的大小。本文主要研究基于茶葉圖像紋理特征的SVM-KNN算法對茶鮮葉的分類問題，并對實驗結(jié)果做出詳細說明。

1 支持向量機（SVM）算法

SVM的分類思想是將低維空間中線性不可分的樣本映射到高維空間中使其變得線性可分，在高維空間中找到一個最優(yōu)超平面（Optimal Hyperplane）對樣本進行劃分[8]。Optimal Hyperplane是使得兩類距離最大的分類面，w·x+b=0即為最優(yōu)超平面，它使得y=+1類與y=-1類之間的間隔Margin最大。

對于向量xi，yi表示類別，yi∈｛-1，1｝，若，yi（w·x+b=1），則xi稱為支持向量（Support Vector）。SVM決策函數(shù)f（x）表達式為：

其中α1為系數(shù)，b為常數(shù)項，K（x，x1）為核函數(shù)內(nèi)積結(jié)果。f（xi）>=0，xi屬于+1類，f（xi）<0，xi屬于-1類。常用核函數(shù)有 4種：Linear Kernel、Polynomial Kernel、Radial Basis Function （RBF,也稱Gaussian Kernel）及Sigmoid Kernel。

SVM的性能受懲罰因子C和核函數(shù)參數(shù)γ兩者共同影響[9]?？梢允褂眠z傳算法、粒子群算法等優(yōu)化算法獲得（C，γ）最佳參數(shù)，使SVM的訓練模型最優(yōu)，泛化效果最好。

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

KNN核心思想是計算所有訓練樣本與測試樣本的空間距離，選取距離最近的K個訓練樣本為測試點的最近鄰居，K個最近鄰居再進行投票分類[10]。

影響KNN性能有2個重要因素：1、距離或相似度的計算。常見的計算公式有歐式距離、曼哈頓距離、余弦相似度、皮爾遜相關(guān)系數(shù)等等，不同的計算公式會得到不同K最近鄰結(jié)果，從而影響最終分類結(jié)果。2、參數(shù)K的選取，K過大，無關(guān)向量或者無關(guān)點會被考慮進來造成干擾，對分類結(jié)果產(chǎn)生偏差影響；K太小，在統(tǒng)計最近鄰居中出現(xiàn)種類最多的類別時容易區(qū)分不開，得不到最優(yōu)的分類結(jié)果。

歐氏距離強調(diào)的是紋理向量之間的絕對距離和差距，對方向不敏感；余弦相似度使用兩個向量間夾角的余弦值來衡量特征向量之間的相似性，強調(diào)的是方向上的差異，對絕對數(shù)值不敏感。本論文提出使用歐式距離與余弦相似度性線性組合的方式來衡量紋理特征向量之間的相似性，并且分別賦予歐式距離與余弦相似度一定權(quán)值，改進距離公式如下：

其中w1+w2=1。在本論文實驗中，取w1=w2= 0.5。

3 SVM-KNN分類算法

SVM對在分界面附近的茶葉紋理特征向量易出錯，本文利用SVM的支持向量做一些改進，結(jié)合改進的經(jīng)典算法KNN，提出SVM-KNN的結(jié)合算法，提高茶葉圖像的分類精度。

3.1SVM-KNN分類算法理論

SVM-KNN算法描述：當測試樣本離SVM的最優(yōu)超平面距離大于給定閾值時，則認為該分類有效，取SVM分類結(jié)果作為輸出值；當樣本和最優(yōu)超平面的距離小于給定閾值時，則認為此次SVM分類無效，使用改進型KNN對測試樣本重新分類。KNN聚類的集合為對應支持向量集SVs，支持向量集的數(shù)量小于樣本空間，減少計算量同時也保證測試點不會受原樣本空間的非典型樣本的影響。SVM-KNN算法描述如下：

1.使用LIBSVM中的svmtrain函數(shù)訓練SVM分類模型，得到模型model的各項參數(shù)，包括SVs（支持向量）和SVs對應的系數(shù)ceof以及常數(shù)b；

2.設M為測試集，SVs為支持向量集，K為KNN聚類代表點的個數(shù)，

3.當M≠Φ，取測試點x∈M，若M=Φ，分類步驟結(jié)束；

5.將測試集T更新為｛T-｛x｝｝，返回步驟3。

在上述算法描述中，閾值 的選擇根據(jù)SVM的反饋參數(shù)經(jīng)驗值一般在 [0.4，0.8]。K＝w'·min｛nSV1，nSV2｝，其中nSV為支持向量的數(shù)量，w'∈[0.5，1]。

3.2SVM-KNN時間復雜度分析

SVM的時間復雜度需要從訓練階段和分類階段兩方面分析。首先是訓練階段，設樣本空間為N，訓練樣本為T，測試樣本為M，支持向量的個數(shù)為Nsv，特征向量維數(shù)為d。實際求解中的經(jīng)典訓練算法Bunch-Kaufman的時間復雜度在O （Nsv3+ TNsv2+dTNsv）和O（dT2）之間，與訓練過程中支持向量的選擇有關(guān)，若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°四方向的對比度、相關(guān)度、同質(zhì)性和能量。

圖1 茶鮮葉種類示意圖Fig.1 Kinds of tea leaves image

實驗環(huán)境Matlab，采用支持多分類的工具包LIBSVM。在下列對比試驗中分別采用16維紋理特征和隨機選取10維紋理特征（4方向?qū)Ρ榷龋?方向相關(guān)性，0°和45°兩方向同質(zhì)性）。采用PSO優(yōu)化算法搜索的 （C和γ）最佳參數(shù)，分別使用SVM和SVM-KNN做對比實驗，結(jié)果如表1所示。其中多項式的維數(shù)參數(shù)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神經(jīng)網(wǎng)絡分類精度和時間對比Table 2 Accuracy and Time Comparison between SVM-KNN and BP Neural Network

由于BP神經(jīng)網(wǎng)絡是傳統(tǒng)的較經(jīng)典分類算法，因此本文也將BP神經(jīng)網(wǎng)絡實驗結(jié)果加入到對比中，BP神經(jīng)網(wǎng)絡參數(shù)設置是：采用梯度下降法，最大迭代次數(shù)epochs=3000，目標誤差goal= 0.01，學習率lr=0.01。

表2的精度對比圖和時間對比圖如圖3和圖4所示。從兩圖可以看出除Sigmoid（二層神經(jīng)網(wǎng)絡）外，SVM-KNN分類精度明顯高于BP神經(jīng)網(wǎng)絡，運算時間大大縮減，SVM-KNN與BP神經(jīng)網(wǎng)絡的對比實驗進一步說明了SVM-KNN仍保持著SVM相對于神經(jīng)網(wǎng)絡收斂快、無局部極值的優(yōu)點和效率。

圖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 結(jié)論

SVM-KNN分類器對三種類型茶鮮葉進行分類，并采用PSO優(yōu)化算法尋找最佳參數(shù)，克服了SVM對在分界面附近的茶葉紋理特征向量易出錯的缺陷，且沒有增加SVM的時間復雜度，對茶鮮葉分類的效果最理想高達90%以上，對于計算機圖像視覺技術(shù)融入實際應用中有著重要推動作用，并且對于提高茶葉生產(chǎn)質(zhì)量和茶葉自動化連續(xù)生產(chǎn)有著積極作用。

[1] 張?zhí)m蘭.機采名優(yōu)茶鮮葉分級技術(shù)及分級機研究[D].浙江大學，2012.

[2] 邵明.基于計算機視覺的龍井茶葉嫩芽識別方法研究[D].中國計量學院，2013.

[3] 陳孝敬，吳迪，何勇，等.基于多光譜圖像顏色特征的茶葉分類研究[J].光譜學與光譜分析，2008，28（11）:2527-2530.

[4] 湯哲，江才華，張立，等.基于紋理分析的茶青在線分類[J].高技術(shù)通訊，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的圖像分類算法優(yōu)化實現(xiàn)[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）；湖南省戰(zhàn)略性新興產(chǎn)業(yè)科技攻關(guān)項目（2014GK1020）

燕婭（1992-），女，湖南常德人，研究方向為圖像處理、圖像分類。

*通訊作者：tn8@163.com