面向顆粒狀農(nóng)產(chǎn)品的分選方法

羅 晶， 郎文輝， 許建平

(合肥工業(yè)大學 計算機與信息學院，安徽 合肥 230009)

?

面向顆粒狀農(nóng)產(chǎn)品的分選方法

羅 晶， 郎文輝， 許建平

(合肥工業(yè)大學 計算機與信息學院，安徽 合肥 230009)

為提高顆粒狀農(nóng)產(chǎn)品分選精度,提出了一種基于現(xiàn)場可編程門陣列(FPGA)的k最近鄰(k-NN)方法。該方法分兩步：第一步對基于FPGA的彩色線陣CCD成像系統(tǒng)得到的圖像在PC上進行保存，并對得到的圖像進行特征提取，然后用k-NN方法對提取的特征進行特征篩選得到最優(yōu)特征集。第二步將訓練好的最優(yōu)特征集放在FPGA的ROM上，F(xiàn)PGA對線陣CCD得到的圖像數(shù)據(jù)實時提取特征與ROM上最優(yōu)特征集做距離計算實現(xiàn)k-NN分選算法。對花生和開心果兩種顆粒狀農(nóng)產(chǎn)品用該方法進行實驗，以RGB顏色空間為主要特征，結果表明：在選擇合理特征個數(shù)和k值情況下對花生和開心果的分選正確率都達到了95 %以上。

k最近鄰; 現(xiàn)場可編程門陣列; 特征篩選; 分選; 花生; 開心果

0 引 言

對于顆粒狀農(nóng)產(chǎn)品，由于其體積小、品質(zhì)問題不明顯、數(shù)量多等特點，人工分選的工作量巨大，增加了生產(chǎn)成本。隨著計算機圖形處理技術和機器視覺的發(fā)展與成熟，以及市場的需求，顆粒狀農(nóng)產(chǎn)品的分選已經(jīng)由人工逐步發(fā)展到機器視覺分級[1]。

目前，國內(nèi)外學者在顆粒狀農(nóng)產(chǎn)品分選中取得了很多成果。2009年，Pearson T[2]為了檢測和分離帶有不同色彩的谷物，開發(fā)了基于現(xiàn)場可編程門陣列(field programmable gate array,FPGA)的CMOS圖像傳感器的分選設備，以彩色和紋理為特征對紅白小麥分選正確率高達96 %。在FPGA上進行復雜的編程，以實時執(zhí)行圖像處理，難度大。國內(nèi)也有許多對紅棗、花生等顆粒狀谷物進行分選的研究，也有較好的正確率[3,4]。但是研究的最終分類識別環(huán)節(jié)中大多以計算機視覺為基礎的神經(jīng)網(wǎng)絡分類器作為模式識別工具，其具體的神經(jīng)網(wǎng)絡算法在FPGA上的實現(xiàn)難度較大。也有用樸素貝葉斯分類器、監(jiān)督k-means分類器和k最近鄰(k-neatest neighbor,k-NN)分類器對藍莓果實進行分選，結果顯示用k-NN分類器有最好的正確率[5]。

本文結合實際項目，實現(xiàn)了一種基于FPGA的k-NN分選方法。利用FPGA強大的并行處理能力，能夠快速有效的分選農(nóng)產(chǎn)品。

1 分選方法和原理

1.1 k-NN算法

k-NN算法是一種應用廣泛的模式識別中的分類方法，其屬于監(jiān)督分類。k-NN算法有兩個階段：第一階段為訓練階段，訓練樣本為在多維空間中已知類別的向量樣本。第二階段為分類階段，將需要分類的測試樣本與每個訓練樣本做距離運算，然后將所得到的距離進行排序，選出與測試樣本距離最近的K樣本(k-最近鄰)，最后根據(jù)這K樣本的類別來判斷未知樣本的類別[6]。

1.2 特征篩選原理

本文是利用k-NN方法進行最優(yōu)特征集的篩選和分類。特征篩選原理如下：用k-NN方法對樣本中的特征進行測試，對分類結果影響大的留著，否則棄之[7]。k-NN算法進行特征篩選的具體實現(xiàn)步驟如下：

1)對包含了所有特征的樣本，用k-NN進行類別判斷，然后對判別的分類結果與原來的類別進行比較，統(tǒng)計兩者不一樣的個數(shù)，計算此時對應的總錯誤率Error_T。

2)特征最優(yōu)集X從空集開始，每次選擇一個特征x加入到特征最優(yōu)集。用k-NN對含有一個特征的樣本進行未知類別的判別，然后對判別的分類結果與原來的類別進行比較，此時對應的錯誤率Error_1。同理，讓其余的樣本特征依次進入樣本空集，計算出相應的錯誤率Error_N，然后對所有的錯誤率進行排序，找出錯誤率最小的對應的特征值，放在最優(yōu)特征集中。

3)此時最優(yōu)特征集里已經(jīng)有了一個特征，然后從剩下的特征里面依次放進最優(yōu)特征集，組成由兩個特征的最優(yōu)特征集，然后k-NN做判斷，選出錯誤率最小對應的特征放進最優(yōu)特征集中。

4)依次類推選出特征，當特征個數(shù)滿足要求或者所選特征計算的錯誤率比總錯誤率大，就結束特征篩選算法；否則，返回上一級繼續(xù)用k-NN篩選特征，直至滿足要求結束算法。

圖1 k-NN特征篩選算法流程圖Fig 1 Flow chart of k-NN feature selection algorithm

2 材料獲取的系統(tǒng)平臺設計

文中所用的實驗圖片均來自自行設計的成像系統(tǒng)，基于FPGA高幀率彩色線陣CCD實時成像系統(tǒng)，如圖2所示。其中相機機型為東芝線陣傳感器TCD2566，最大分辨率為5 340×1，最大行頻可達6 222 fps。采集到的圖像數(shù)據(jù)經(jīng)過USB 2.0傳輸至上位機實現(xiàn)圖像的拼接、顯示和保存。不同于其他單色線陣CCD，該傳感器既可輸出單色又可輸出R，G，B三路彩色模擬信號。

圖2 彩色線陣CCD采集系統(tǒng)框圖Fig 2 Block diagram of CCD acquisition system forcolor linear array

3 特征選擇和篩選

特征提取是圖像識別的關鍵步驟，其中長短軸軸長、RGB三通道灰度和灰度共生矩陣是一般顆粒的形狀、顏色和紋理的代表特征?？紤]到實時性和易于實現(xiàn)等需求，發(fā)揮FPGA速度快等優(yōu)點， 本文對花生和開心果兩種顆粒狀農(nóng)產(chǎn)品分選，提取的特征主要以顏色特征和邊界特征為主。

3.1 花生的特征提取

選取三類花生如圖3所示。

圖3 花生樣本Fig 3 Peanut samples

實驗選取的特征為花生顏色通道的G,B分量，每個分量等分成16等分，花生 G,B通道顏色分量組成的G-B的二維直方圖，每個維度等分成8等份，所以，總的特征為8×8+16+16=96個特征作為k-NN篩選算法的輸入特征。

3.2 花生的特征提取

選取的兩類開心果帶殼和不帶殼，如圖4所示。

圖4 不帶殼和帶殼開心果Fig 4 No shell and shelled pistachios

分析帶殼開心果和不帶殼的開心果，由于帶殼開心果有邊界特性，Laplacian算子利用二階導數(shù)零交叉特性檢測邊緣，定位精度較高[8]。發(fā)現(xiàn)經(jīng)3×3離散拉普拉斯算子處理后邊界有較高藍色分量[9]，而不帶殼開心果則沒有這一屬性，所以，選取的特征為顏色直方圖的R,G和B三通道的值，每個通道的顏色直方圖等分成16等分，經(jīng)過拉普拉斯算子處理的B通道和沒有經(jīng)過處理的B通道組成二維直方圖，每個維數(shù)分成8等分，這樣組成8×8的二維直方圖。3×3拉普拉斯算子如下

(1)

這樣總的特征為16×3+8×8=112個特征作為k-NN篩選算法的輸入特征。

4 FPGA實現(xiàn)分類算法

本文選用的FPGA型號為Altera的EP4CE15F17C8N，該FPGA顆粒邏輯塊達到15 000，內(nèi)部嵌入式存儲器504 kbits，能夠完成對線陣CCD的圖像采集和預處理，以及k-NN的分類算法。k-NN分類器[10]的設計分為以下4步：

1)將訓練集放置在FPGA的ROM中。如果需要將對象分為n類，就應該開辟n個ROM，然后將在PC上已經(jīng)訓練好的最優(yōu)特征值作為訓練數(shù)據(jù)放入ROM中，這里每種類別放置15個訓練樣本。

2)FPGA實時特征的提取。根據(jù)在PC端實時提取的特征標簽實時提取特征。在PC端進行最優(yōu)特征集篩選時，對于所有特征進行標記，經(jīng)過篩選后的特征就能根據(jù)特征標簽準確知道哪種特征被篩選出來了。

3)k-NN算法中的距離計算。常用的計算距離的公式有歐氏距離(Euclidian distinct)和曼哈頓距離(Manhattan distance)。使用歐氏距離計算測試向量與一個訓練向量的距離如公式(2)所示，使用曼哈頓距離計算測試向量與一個測試向量的距離如公式(3)所示

(2)

(3)

考慮在FPGA上實現(xiàn)歐氏距離的難度，曼哈頓距離相比較歐氏距離其優(yōu)點在于簡單和較少的計算量，所以選擇曼哈頓距離。

4)排序和分類。將測試集和訓練集計算得到的距離進行排序，選出最小的K個距離對應的訓練集標簽，出現(xiàn)次數(shù)最多的標簽就是經(jīng)算法得到的最終分類標簽。FPGA實現(xiàn)k-NN算法的內(nèi)部框圖如圖5。

圖5 FPGA實現(xiàn)k-NN算法內(nèi)部框圖Fig 5 FPGA implementation of k-NN algorithminternal block diagram

5 實驗結果和討論

5.1 花生的實驗結果和討論

實驗選取三類花生，總共168個花生樣本，每一類花生各為56個。每類隨機抽取15個作為訓練樣本。實驗結果如表1所示。

表1 花生的實驗結果

三類花生的分類實驗結果可以看出，當能夠合理選擇特征個數(shù)和K值(最近鄰個數(shù))，分選的正確率接近98 %。從表中可以得出，當K固定時，隨著特征個數(shù)的增加分選正確率反而會下降，最優(yōu)的特征個數(shù)應該在3～5個，當特征個數(shù)固定時，隨著最近鄰個數(shù)的增加分選正確率也是下降的。

5.2 開心果的實驗結果和討論

用112粒開心果進行了算法準確率的驗證實驗。在112粒中隨機選擇30粒作為訓練樣本，其中帶殼開心果和不帶殼開心果各15粒，剩余的82粒作為測試樣本。

表2 開心果的實驗結果

對開心果的實驗結果可以看出，分選的正確率最高可達98.78 %;當K=3時，特征個數(shù)為4或者5時其分選正確率達到98.78 %;當K=5時，特征個數(shù)為3時分選正確率也能夠達到98.78 %;當K值固定的時候，隨著特征個數(shù)的增加正確率都在下降。

對花生和開心果實驗可以得出，特征個數(shù)只需要3～4個就可以達到較高的分選精度，樣本包含3～4個特征值,這個很符合在FPGA上構建k-NN分類器對樣本維數(shù)的要求，從而實現(xiàn)這些算法并以高速分選顆粒。

6 結 論

針對顆粒狀農(nóng)產(chǎn)品的分選，提出一種基于FPGA的k-NN分選方法，該方法在PC上進行特征提取和用k-NN方法進行特征篩選，在FPGA上利用篩選的特征集和特征標簽構建k-NN分類器，最終實現(xiàn)顆粒狀農(nóng)產(chǎn)品的分類。實驗選取了花生和開心果兩種農(nóng)作物，實驗表明:構建的k-NN分類器，在選擇合理的k值和特征個數(shù)情況下，對花生的分選正確率達到97.56 %，對開心果的分選正確率達到98.78 %。

[1] 李嘯宇,張秋菊.顆粒狀食品視覺檢測分選技術的發(fā)展[J].食品工業(yè)科技,2014(13):378-381.

[2] Pearson T.High-speed sorting of grains by color and surface texture[J].Applied Engineering in Agriculture,2010,26(3):499-505.

[3] 韓仲志,趙友剛.基于計算機視覺的花生品質(zhì)分級檢測研究[J].中國農(nóng)業(yè)科學,2010,43(18):3882-3891.

[4] 許 敏,馬 鉞,陳 帥.基于計算機視覺的紅棗形狀識別方法研究[J].傳感器與微系統(tǒng),2013,32(4):23-26.

[5] 李 寒.基于機器視覺的目標檢測在精細農(nóng)業(yè)中的關鍵技術研究[D].北京：中國農(nóng)業(yè)大學,2014.

[6] Hussain H M,Benkrid K,Seker H.An adaptive implementation of a dynamically reconfigurable K-nearest neighbour classifier on FPGA[C]∥2012 NASA/ESA Conference on Adaptive Hardware and Systems(AHS),IEEE,2012:205-212.

[7] 姚莉秀，楊 杰，葉晨洲，等.用于特征篩選的最近鄰(KNN)方法[J].計算機與應用化學,2001,18(2):135-138.

[8] 鄭健睿，趙 軍，劉 宇.基于機器視覺的小模數(shù)齒條測量方法研究[J].傳感器與微系統(tǒng)，2011,30(1):63-65.

[9] Haff R P,Pearson T C,Toyofuku N.Sorting of in-shell pistachio nuts from kernels using color imaging[J].Applied Engineering in Agriculture,2010,26(4):633-638.

[10] Manolakos E S,Stamoulias I.IP-cores design for the kNN classi-fier[C]∥Proceedings of 2010 IEEE International Symposium on Circuits and Systems(ISCAS),IEEE,2010:4133-4136.

Granular agricultural products sorting method

LUO Jing, LANG Wen-hui, XU Jian-ping

(School of Computer and Information,Hefei University of Technology,Hefei 230009,China)

In order to improve sorting precision of granular agricultural products,ak-nearest neighbor(k-NN)method based on FPGA is proposed.The method contains two steps:the first step,image obtained by FPGA-based color linear array CCD imaging system is saved on PC,and the obtained image is feature extracted,and then usingk-NN method extracted features are screened and obtain the optinal feature set.The second step,trained the optimal feature set is put on FPGA-ROM,FPGA real-time extract characteristics of image data obtained by linear CCD on ROM and optimal feature set make distance calculation,achievek-NN sorting algorithms.Two kinds of granular agricultural products,peanuts and pistachios,are tested by this method,RGB color space as main feature,the results show that under reasonable choice in the number and characteristics of the K-value situations, sorting correct rate of peanuts and pistachios reach above 95 %.

k-nearest neighbor(k-NN)； FPGA； feature selection； sort； peanut； pistachio

10.13873/J.1000—9787(2016)12—0066—03

2016—02—26

TP 753

A

1000—9787(2016)12—0066—03

羅 晶(1990-)，男，安徽六安人，碩士，研究方向為數(shù)字圖像分析與處理及FPGA。