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

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

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

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

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

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

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

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

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

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

1 支持向量機(jī)（SVM）算法

SVM的分類思想是將低維空間中線性不可分的樣本映射到高維空間中使其變得線性可分，在高維空間中找到一個最優(yōu)超平面（Optimal Hyperplane）對樣本進(jìn)行劃分[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）表達(dá)式為：

其中α1為系數(shù)，b為常數(shù)項(xiàng)，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的訓(xùn)練模型最優(yōu)，泛化效果最好。

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

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

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

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

其中w1+w2=1。在本論文實(shí)驗(yàn)中，取w1=w2= 0.5。

3 SVM-KNN分類算法

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

3.1SVM-KNN分類算法理論

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

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

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

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

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

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

3.2SVM-KNN時間復(fù)雜度分析

SVM的時間復(fù)雜度需要從訓(xùn)練階段和分類階段兩方面分析。首先是訓(xùn)練階段，設(shè)樣本空間為N，訓(xùn)練樣本為T，測試樣本為M，支持向量的個數(shù)為Nsv，特征向量維數(shù)為d。實(shí)際求解中的經(jīng)典訓(xùn)練算法Bunch-Kaufman的時間復(fù)雜度在O （Nsv3+ TNsv2+dTNsv）和O（dT2）之間，與訓(xùn)練過程中支持向量的選擇有關(guān)，若Nsv＜＜T，則訓(xùn)練復(fù)雜度接近O（dT）；若Nsv→T，復(fù)雜度接近O（dT2）。其次是分類階段的時間復(fù)雜度為O（MNsv）。SVM分類器的總復(fù)雜度為：

SVM-KNN的復(fù)雜度也分為訓(xùn)練階段和分類階段：訓(xùn)練階段的復(fù)雜度與SVM的訓(xùn)練復(fù)雜度一樣，分類階段復(fù)雜度為SVM和改進(jìn)型KNN之和，改進(jìn)型KNN算法分類時間復(fù)雜度O（TNsv），因此SVM-KNN的總復(fù)雜度為：

由此可以看出SVM-KNN并沒有增加SVM的復(fù)雜度。

4 茶鮮葉圖像紋理分類實(shí)驗(yàn)及分析

本文對一芽一葉（A類）、一芽二葉（B類）和一芽多葉（C類）做分類實(shí)驗(yàn)，圖片大小為640×640像素，每種類型茶葉100張，共計(jì)300張，訓(xùn)練集3×70=210，測試集3×30=90。茶鮮葉圖像紋理特征16維：0°、45°、90°、135°四方向的對比度、相關(guān)度、同質(zhì)性和能量。

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

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

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

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

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

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

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

[3] 陳孝敬，吳迪，何勇，等.基于多光譜圖像顏色特征的茶葉分類研究[J].光譜學(xué)與光譜分析，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ī)理論與算法研究綜述[J].電子科技大學(xué)學(xué)報(bào)，2011，40（1）:2-10.

[8] 王曉云.基于SVM的圖像分類算法優(yōu)化實(shí)現(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

國家自然科學(xué)基金（31470028）；湖南省戰(zhàn)略性新興產(chǎn)業(yè)科技攻關(guān)項(xiàng)目（2014GK1020）

燕婭（1992-），女，湖南常德人，研究方向?yàn)閳D像處理、圖像分類。

*通訊作者：tn8@163.com