基于K-means與SVM的雞蛋特征檢測

宋 超 秦永彬 許道云

(貴州大學計算機科學與技術學院 貴陽 550025)

基于K-means與SVM的雞蛋特征檢測

宋 超 秦永彬 許道云

(貴州大學計算機科學與技術學院 貴陽 550025)

機器視覺與機器學習的不斷發展對傳統的視覺特征提取的影響在不斷加強，在實際的使用當中也在逐步替代那些繁雜的人工特征提取的方式，論文從實際應用當中介紹一種基于K-means自動提取特征的方法，其在雞蛋缺陷檢測使用中得到了較好的實際效果。

機器視覺; K-means; 缺陷檢測; SVM

Class Number TP391.9

1 引言

機器視覺作為一種人眼的延伸，用來代替人工的觀察和判斷。近年來，隨著計算機技術、數字圖像處理技術、電子技術等的發展，機器視覺在工業生產當中變得越來越重要，其在實際檢測、測量、控制等方面發揮著重要的作用，在工業生產中的缺陷檢測中應用廣泛。

基于機器視覺的雞蛋缺陷檢測，雞蛋的外部缺陷檢測目前主要是針對雞蛋外部的污點(外殼上附著雞的糞便，羽毛等雜物，主要還是糞便物)、血塊、裂紋進行檢測[1]，由于外部的這些因素很容易在蛋殼上造成病毒的殘留，不利于雞蛋的保存，有時在運輸途中也會對其他干凈的雞蛋產生污染，所以針對上述的問題需要對含有缺陷的雞蛋進行隔離處理。機器視覺檢測技術主要通過分析雞蛋表面的顏色特征來識別雞蛋表面的污點、裂紋等。目前，主要的檢測技術是通過在固定外界光照條件等條件利用缺陷對光照的反射和折射差異性可以通過數字圖像處理的方法進行識別。目前，基于雞蛋外部缺陷識別的方法主要受制于雞蛋圖像采集的完整性，外部光照條件等[1]。如Elster.T[2]和Goodnm.J.W[3]采用直方圖均衡化和sobel算子相結合方法進行特征的提取，Leiqing P[4]采用灰度圖像計算視覺系統，使用灰度直方圖的閾值分割提取特征訓練神經網絡，Patel.V.C[5]采用彩色圖像采集系統，使用顏色直方圖提取特征訓練網絡，熊利榮[6]使用Sobel算子進行邊緣檢測獲取雞蛋的特征。現有的基于機器視覺的方法對雞蛋外部特征提取的方法主要是使用圖像處理技術將獲得雞蛋的彩色圖像，經過背景去除、灰度轉化、中值濾波、閾值分割、區域標記和特征提取從雞蛋的圖像中分割出缺陷區域，并提取出缺陷區域的幾何特征參數，從而實現對雞蛋的判別[7]。基于機器視覺的方法對雞蛋外部特征提取的方法整體流程如圖1所示：(a)→(b)→(c)→(d)→(e)→(f)→(g)。

圖1 雞蛋特征提取的過程

目前，對于雞蛋的缺陷特征(如圖1(g)的污點缺陷)在表示時主要是通過將缺陷部分的值與整個雞蛋的值做比值(如圖1(f)二值圖(f)與(g)中的白色部分的值進行比值，這兩幅圖是二值圖，計算其中的一個數就行了)。但是這種檢測對外部條件要求較高,在使用圖像處理時由于采集圖像的環境對于進行閾值的設置有較大的影響,不利于方法的通用性，而且對雞蛋的顏色差異具有較高的敏感性，會在計算特征時引入很高的偏差，使得在使用過程當中與之前預設置的閾值等產生沖突，會對特征的提取的產生差異，進而出現較高的誤識率。

針對這種特征提取的缺陷性，本文主要采用一種無監督的方法來提取雞蛋的外部特征，利用雞蛋的外部特征,通過聚類的方式將相近的特征進行抽取,在一定的程度上可以對環境的要求可以有所降低。本文通過對新鮮雞蛋的外部品質檢測(主要是污點)，使用基于K-means的聚類方法提取雞蛋外部缺陷特征，并使用線性的支持向量機(SVM)對得到的特征數據進行分類訓練，進而達到對雞蛋進行分類處理。

2 K-means算法和SVM算法

K-means作為一種典型的聚類算法，其基本思想是:在整個數據對象集合中，首先隨機初始化k個中心點，對數據集中的對象找到距離其最近的中心點，將該點放入到中心點所對應的集合中，分配到同一個中心點的數據集合構成一個類，然后更新每個類的中心點，重復上述過程，直到中心點不再發生變化或者達到最大的迭代次數時為止，最終得到整個數據集合的k個中心點。

以下給出K-means的數學描述：假設給定的樣本集{x(1),…,x(m)}，每個x(i)∈Rn，K-means算法是將樣本聚類成K個簇(cluseter)，具體算法如下[8]：

1) 隨機選取K個聚類質心點(cluster centroids)為：μ1,μ2,…,μk∈Rn。

2) 重復下面結構體中的過程直到收斂。

對于每一個樣例i，計算其應該屬于的類:

對于每一個類j，重新計算該類的質心:

K是給定的聚類的數，c(i)代表樣例i與K個類中距離最近的那個類，c(i)的值是1～K中的一個，重復結構體中的過程直到質心不變或者變化很小。

K-means的這種聚集數據的中心點可以看做是數據的特征提取的一種方式。

SVM[9]是建立在統計學習理論中結構風險最小化原理基礎上，在特征空間上的間隔最大的線性分類器，以下給出線性SVM的介紹：輸入給定訓練樣本集：

T= {(x1,y1),(x2,y2),…,(xn,yn)},

yi∈{+1,-1},(i=1,2,3,…,n)

其中，yi為樣本類別。

輸出：分離超平面和分類決策函數。

構造并求解約束最優化問題：

≥1-ξi;ξi≥0,i=1,2,…,n

其中，ξi為松弛變量，表示訓練樣本的錯分程度；C為懲罰常數，控制對錯誤樣本的懲罰程度；w和b分別是判決函數f(x)=(w·x)+b的權向量和閾值。

拉格朗日函數為

在進行提取特征之前，先將所有的雞蛋訓練樣本塊進行亮度和對比度的歸一化[10]，此做法是對每一個樣本減去灰度的均值并除以標準差。另外，在除以標準差的時候，為避免分母為零的情況增加一個很小的偏置常數：

在數據分塊之后為了降低數據塊之間的相關性，在此對數據塊進行一次白化處理。

數據白化(whitening)[11]主要是為了降低數據的相關性所做的操作。其主要是根據PCA的原理進行的,需要先對數據點x進行協方差矩陣的特征值與特征向量的計算

其中，V是數據x的協方差矩陣的特征向量組成的矩陣，D是數據x協方差矩陣的特征值的矩陣，εzca是一個很小的常數，主要是防止分母為0。對于對比度歸一化后的數據。需要注意的是這個常數不能太小，如果太小會加強數據的高頻噪聲，會使特征學習更加的困難。由于數據的旋轉對于K-means沒有影響，所以可以使用其他的白化變換方法。

3 缺陷檢測的算法

本文通過將K-means[1]與SVM結合使用在雞蛋的污點檢測當中,使用K-means數據特征提取及分類器SVM，在此將K-means與SVM結合進行缺陷的檢測。

首先，使用K-means聚類無監督的方式進行圖像的特征提取。使用K-means提取圖像的特征塊之間的相似性進行分類，首先是將所有的圖片進行切塊處理可以獲取大量的圖像塊，根據圖像塊的相似性，可以找出一個相似塊的中心塊(可以通過K-means的方法得到)，使用K-means的方法假設有k個中心塊(隨機初始化)，根據與k個中心塊的距離計算出相近似的圖像塊，進而可以得到近似塊的k個集合，在此可以看做是一幅圖像的統計特征，將得到的統計特征進行分類，只需要存儲這些個中心塊即可，然后利用整張圖像與中心塊的距離來得到一張圖像的塊的分布，由于缺陷的部分與正常的部分的統計塊的數據分布會存在差異，利用這種差異性，使用SVM分類器進行數據分類進而得到一種比較好的分類效果。具體描述如下：

1) 首先將進行切塊，將每一張圖像都進行不重疊的切塊(塊的大小可以設定)，隨機不重樣地抽取其中2/3的數據塊。

2) 將1)中得到數據塊進行規則化，白化處理。

3) 將2)得到數據集進行K-means的訓練得到k個中心塊。

4) 將得到的中心塊進行進行字典化，將每一張圖像都進行切塊并與k中心塊的字典進行初步的分類將一張圖片分成k個特征塊。

5) 將4)中得到的特征塊進行SVM分類器的訓練得到所需要的參數集。

6) 根據得到的k中心字典和SVM的參數即可進行圖片的分類。

經過上述的訓練過程，將得到的中心塊與SVM參數，此分類算法就已經訓練好了。整個過程如下圖2所示。

圖2 K-means+SVM提取特征和分類的過程

在圖2中可以看到將原始圖像輸入進來依次進行分塊處理，K-means訓練得到k類(k個中心塊)，然后再將每一張圖像進行上述操作得到針對一張圖像的k分類特征，將得到的k特征放入到SVM中最后進行訓練得到最終的參數。

在訓練中，防止過擬合在此對數據塊的集合進行了隨機從中選取2/3的數據塊，進行數據的中心塊的學習。

將圖像數據先進行數據分塊，將數據進行預處理和白化處理消除數據相關性，將得到的數據塊進行矢量化。得到樣本集{x(1),…,x(m)}，每個x(i)∈Rn，n=a×b，a是分塊的長度，b是分塊的寬度，可以使用K-means得到k個聚簇的中心塊：μ1,μ2,…,μk∈Rn，將得到的中心塊集合，進行矢量化組合成矩陣k×n的矩陣，然后將每一張圖像進行分塊并與中心塊矩陣進行求距離，將圖像中的每一塊按照距離最小的原則分到相應的中心塊下，進行數據統計，得到此張圖片的特征數據。將m張圖像通過上述的方法得到的特征數據。如圖3所示。

圖3 K-means編碼下采樣的求取特征的過程

在此使用中心塊的組合形成中心塊的字典如圖3中中間的字典矩陣，之后使用單張圖片的分塊形成圖3中左側的矩形，最后利用矩陣的運算可以很好地計算出所需要的特征集如圖3中的右邊的特征矩陣。通過將輸入的圖像按照a×b的塊的大小進行分塊(不重疊)，將所有的圖像塊與中心塊矩陣進行距離計算，將最終得到的特征數據與已知的標簽數據交給SVM分類器去訓練分類參數W矩陣，在此使用的是線性的SVM將上面經過K-means得到的特征值放入SVM中訓練出分類函數的W值的矩陣，至此就完成了訓練集的訓練，最后使用測試進行驗證。

在此使用將數據集的所有圖像進行分塊處理可以得到大量的數據塊，由于數據集中正常的與不正常的塊的比例不是均等的且出現污點的區域的地方一般來講是沒有非污點區域大，在此對數據的選擇上將正常的與缺陷的進行分開處理，將所得到的兩類中心塊進行了距離比較，將距離近的合并求取中值，將距離遠的不作處理，最終形成所需要的k中心塊的字典。

本文通過使用K-means的方法提取特征，使用一種隨機的自學習方式提取到雞蛋的特征值，使用SVM的強分類器可以得到較好的分類效果。

基于K-means的特征提取的方法是一種靈活的可以擴展的無監督的學習方法，可以更好地獲取圖像的局部特征數據(正是由于這種局部特征數據與雞蛋缺陷檢測的特征效果相類似，故產生了較好的效果)，SVM[10]作為一種常用的二值分類器，其在二分類其中的效果較好。這兩者的組合可以使得在實際的應用中得到較好的效果。

4 實驗過程

試驗中所使用的雞蛋樣本，是與某公司合作其公司提供的數據樣本，樣本的采集是在光照一定，背景控制在黑色的情況下，使用CCD攝錄機采集的數據圖像，其中可以正常使用數據圖像856張，其中正常的雞蛋 468張，含有污點的雞蛋388張，實際使用是訓練集與測試集按照3:1的比例進行隨機分配的，具體的額分配如表1。

表1 訓練集與測試集數據分布

試驗中使用的圖像大小統一預處理為100×100的彩色圖像，使用圖像塊的大小是6×6×3的彩色塊，實驗的K取值800，隨機圖像塊的個數設置為5000。

基于上述的數據集進行的使用K-means和SVM實驗結果，如表2所示。

表2 K-means + SVM的實驗結果

在實驗當中，對原始圖像的大小設定為100×100的彩色圖像[12]，對圖像背景的處理是根據邊緣特征將雞蛋的部分保留精剩余的背景統一處理成黑色(像素值為0)，白化處理在試驗中使用的是ZCA白化。從實驗的結果可以得出算法對原始圖的處理下過較好，對于白化在實際的使用中比較耗時，且對實驗結果的影響不是十分的重要。

基于現有的方法對雞蛋進行污點的缺陷檢測的結果[13]。

表3 對比現有的一些算法

注：由于采樣的不同，可能對結果的影響也會存在差異

由于圖像的局部特征根據得到的中心塊矩陣可以根據圖像塊跟中心塊的距離，可以統計出特征的變化，將一張圖像的特征以中心塊的維度進行度量，由于是在訓練期間可以將所有的圖像的數據塊進行中心塊矩陣的學習，可以達到相對精準的判斷。在測試期間可以達到很快的速度提取出特征的數據，根據的SVM的訓練的權重矩陣快速計算出分類的結果。

5 結語

本文建立了一種基于K-means的無監督的特征提取方法用于雞蛋的缺陷檢測中，通過對獲取的雞蛋的圖像，進行簡單地剪切之后，讓算法自動的去學習特征，相較于人工提取的方法有較強的自適應性。

相較于目前的缺陷檢測方法識別仍然存在一定的差距，此算法(K-means+SVM)對缺陷雞蛋的識別率達到94.68%，但隨著算法的不斷優化，差距會縮小，自動提取特征的新的算法將會產生，替代原始的人工特征提取。目前比較流行的深度學習正在自動提取特征和自動訓練分類器的一種端到端的學習正在打破傳統的方式，相信會取得一定的成功。

[1] Lunadei L, Ruiz-Garcia L, Bodria L, et al. Automatic identification of defects on eggshell through a multispectral vision system[J]. Food and Bioprocess Technology,2012,5(8):3042-3050.

[2] Elster R T, Goodrum J W. Detection of cracks in eggs using machine vision[J]. Transactions of the ASAE (USA),1991.

[3] Goodrum J W, Elster R T. Machine vision for crack detection in rotating eggs[J]. Transactions of the ASAE (USA),1992.

[4] Leiqing P, Kang T, Zipeng S, et al. Crack detection in eggs using computer vision and BP neural network[J]. Transactions of the Chinese Society of Agricultural Engineering,2007.

[5] Patel V C, McClendon R W, Goodrum J W. Color computer vision and artificial neural networks for the detection of defects in poultry eggs[M]//Artificial Intelligence for Biology and Agriculture. Springer Netherlands,1998:163-176.

[6] 熊利榮,王樹才,任奕林,等.雞蛋大小等級模型的修正[J].農機化研究,2006(2):104-105. XIONG Lirong, WANG Shucai, REN Yilin, et al. The Revision of Grade Model on Egg’s Weight[J]. Journal of Agricultural Mechanization Research,2006(2):104-105.

[7] 潘磊慶,屠康,蘇子鵬,等.基于計算機視覺和神經網絡檢測雞蛋裂紋的研究[J].農業工程學報,2007,23(5):154-158. PAN Leiqing, TU Kang, SU Zipeng, et al. Crack detection in eggs using computer vision and BP neural network[J]. Transactions of the Chinese Society of Agricultural Engineering, 2007,23(5):154-158.

[8] 李航.統計學習方法〔M〕.北京：清華大學出版社，2012：38-41. LI Hang. Statistical learning methods(M). Beijing: Tsinghua University Press, 2012：38-41.

[9] Coates A, Ng A Y. Learning feature representations with k-means[J]. Lecture Notes in Computer Science,2012,7700:561-580.

[10] Tang Y. Deep learning using linear support vector machines[J]. arXiv preprint arXiv, 2013.

[11] Ng. Andrew, Ngiam, Jiquan, Foo, Chuan Yu, Mai,Yifan, and Suen, Caroline. UFLDL Tutorial,2013. URL http://ufldl.stanford.edu/wiki/index.php/UFLDL Tutorial.

[12] Chandrashekar G, Sahin F. A survey on feature selection methods[J]. Computers & Electrical Engineering, 2014, 40(1): 16-28.

[13] 孫力,蔡健榮,李雅琪,等.禽蛋蛋殼品質無損檢測方法研究進展[J].中國農業科技導報,2015(5):11-17. SUN Li, CAI Jianrong, LI Yaqi, et al. Research Progress on Non-destructive Technology for Quality Detection of Eggshell[J]. Journal of Agricultural Science and Technology,2015(5): 11-17.

Eggs Feature Detection Based on K-means and SVM

SONG Chao QIN Yongbin XU Daoyun

(College of Computer Science and Technology, Guizhou University, Guiyang 550025)

Machine vision and machine learning are used in the feature extraction, and their influences are important. In the actual application they have gradually replace those cumbersome manual feature extraction recentlly. This paper presents a practical application based on K-means the method of automated feature extraction, which gets better practical results in the use of eggs defect detection.

machine vision, K-means, defect detection, SVM

2016年8月11日,

2016年9月27日

宋超,男,碩士研究生,研究方向：算法設計與分析。許道云,男,博士,教授,博士生導師，研究方向:可計算性與計算復雜性、算法設計與分析。秦永彬,男,博士,副教授,碩士生導師,研究方向:智慧計算與智能計算、大數據管理與應用、移動互聯網研究與應用。

TP391.9

10.3969/j.issn.1672-9722.2017.02.034