羅 晶， 郎文輝， 許建平

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

?

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

羅 晶， 郎文輝， 許建平

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

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

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

0 引 言

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

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

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

1 分選方法和原理

1.1 k-NN算法

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

1.2 特征篩選原理

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

1)對(duì)包含了所有特征的樣本，用k-NN進(jìn)行類別判斷，然后對(duì)判別的分類結(jié)果與原來(lái)的類別進(jìn)行比較，統(tǒng)計(jì)兩者不一樣的個(gè)數(shù)，計(jì)算此時(shí)對(duì)應(yīng)的總錯(cuò)誤率Error_T。

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

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

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

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

2 材料獲取的系統(tǒng)平臺(tái)設(shè)計(jì)

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

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

3 特征選擇和篩選

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

3.1 花生的特征提取

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

圖3 花生樣本Fig 3 Peanut samples

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

3.2 花生的特征提取

選取的兩類開(kāi)心果帶殼和不帶殼，如圖4所示。

圖4 不帶殼和帶殼開(kāi)心果Fig 4 No shell and shelled pistachios

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

(1)

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

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

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

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

2)FPGA實(shí)時(shí)特征的提取。根據(jù)在PC端實(shí)時(shí)提取的特征標(biāo)簽實(shí)時(shí)提取特征。在PC端進(jìn)行最優(yōu)特征集篩選時(shí)，對(duì)于所有特征進(jìn)行標(biāo)記，經(jīng)過(guò)篩選后的特征就能根據(jù)特征標(biāo)簽準(zhǔn)確知道哪種特征被篩選出來(lái)了。

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

(2)

(3)

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

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

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

5 實(shí)驗(yàn)結(jié)果和討論

5.1 花生的實(shí)驗(yàn)結(jié)果和討論

實(shí)驗(yàn)選取三類花生，總共168個(gè)花生樣本，每一類花生各為56個(gè)。每類隨機(jī)抽取15個(gè)作為訓(xùn)練樣本。實(shí)驗(yàn)結(jié)果如表1所示。

表1 花生的實(shí)驗(yàn)結(jié)果

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

5.2 開(kāi)心果的實(shí)驗(yàn)結(jié)果和討論

用112粒開(kāi)心果進(jìn)行了算法準(zhǔn)確率的驗(yàn)證實(shí)驗(yàn)。在112粒中隨機(jī)選擇30粒作為訓(xùn)練樣本，其中帶殼開(kāi)心果和不帶殼開(kāi)心果各15粒，剩余的82粒作為測(cè)試樣本。

表2 開(kāi)心果的實(shí)驗(yàn)結(jié)果

對(duì)開(kāi)心果的實(shí)驗(yàn)結(jié)果可以看出，分選的正確率最高可達(dá)98.78 %;當(dāng)K=3時(shí)，特征個(gè)數(shù)為4或者5時(shí)其分選正確率達(dá)到98.78 %;當(dāng)K=5時(shí)，特征個(gè)數(shù)為3時(shí)分選正確率也能夠達(dá)到98.78 %;當(dāng)K值固定的時(shí)候，隨著特征個(gè)數(shù)的增加正確率都在下降。

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

6 結(jié) 論

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

[1] 李嘯宇,張秋菊.顆粒狀食品視覺(jué)檢測(cè)分選技術(shù)的發(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] 韓仲志,趙友剛.基于計(jì)算機(jī)視覺(jué)的花生品質(zhì)分級(jí)檢測(cè)研究[J].中國(guó)農(nóng)業(yè)科學(xué),2010,43(18):3882-3891.

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

[5] 李 寒.基于機(jī)器視覺(jué)的目標(biāo)檢測(cè)在精細(xì)農(nóng)業(yè)中的關(guān)鍵技術(shù)研究[D].北京：中國(guó)農(nóng)業(yè)大學(xué),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].計(jì)算機(jī)與應(yīng)用化學(xué),2001,18(2):135-138.

[8] 鄭健睿，趙 軍，劉 宇.基于機(jī)器視覺(jué)的小模數(shù)齒條測(cè)量方法研究[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-)，男，安徽六安人，碩士，研究方向?yàn)閿?shù)字圖像分析與處理及FPGA。