面向颗粒状农产品的分选方法

罗 晶， 郎文辉， 许建平

(合肥工业大学 计算机与信息学院，安徽 合肥 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。