面向顆粒狀農產品的分選方法

羅 晶， 郎文輝， 許建平

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

?

面向顆粒狀農產品的分選方法

羅 晶， 郎文輝， 許建平

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

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

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

0 引 言

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

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

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

1 分選方法和原理

1.1 k-NN算法

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

1.2 特征篩選原理

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

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

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

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

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

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

2 材料獲取的系統平臺設計

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

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

3 特征選擇和篩選

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

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算子利用二階導數零交叉特性檢測邊緣，定位精度較高[8]。發現經3×3離散拉普拉斯算子處理后邊界有較高藍色分量[9]，而不帶殼開心果則沒有這一屬性，所以，選取的特征為顏色直方圖的R,G和B三通道的值，每個通道的顏色直方圖等分成16等分，經過拉普拉斯算子處理的B通道和沒有經過處理的B通道組成二維直方圖，每個維數分成8等分，這樣組成8×8的二維直方圖。3×3拉普拉斯算子如下

(1)

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

4 FPGA實現分類算法

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

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

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

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

(2)

(3)

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

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

圖5 FPGA實現k-NN算法內部框圖Fig 5 FPGA implementation of k-NN algorithminternal block diagram

5 實驗結果和討論

5.1 花生的實驗結果和討論

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

表1 花生的實驗結果

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

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

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

表2 開心果的實驗結果

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

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

6 結 論

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

[1] 李嘯宇,張秋菊.顆粒狀食品視覺檢測分選技術的發展[J].食品工業科技,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] 韓仲志,趙友剛.基于計算機視覺的花生品質分級檢測研究[J].中國農業科學,2010,43(18):3882-3891.

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

[5] 李 寒.基于機器視覺的目標檢測在精細農業中的關鍵技術研究[D].北京：中國農業大學,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] 鄭健睿，趙 軍，劉 宇.基于機器視覺的小模數齒條測量方法研究[J].傳感器與微系統，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-)，男，安徽六安人，碩士，研究方向為數字圖像分析與處理及FPGA。