一种水稻指纹图谱计算机检索方法.doc

一种水稻指纹图谱计算机检索方法
摘　要　水稻的DNA指纹图谱可作为水稻品种指纹，应用于品种真实性、品种纯度检验和新品种登记。本文提出一种基于机器学习的水稻指纹图谱检索方法，由计算机自动提取指纹图谱特征，并利用支持向量机作为学习机器，构造水稻品种指纹图谱的分类器，实现对未知样品的品种分类。实验表明该方法是可行的，可以辅助提高水稻品种鉴别效率。
关键词　图像检索　指纹图谱　支持向量机
A METHOD OF PADDY FINGERPRINT IMAGES RETRIEVE
Abstract DNA image is regarded as fingerprint of paddy. It is applies in variety identification, varietal purity examination, and new variety registration. This article proposed a search method based on SVM (Support Vector Machine). By extracting the fingerprint feature automatically, we make use of SVM to create a classifer. Experiments shows that our method is useful and can help to improve the efficieny of variety identification.
Keywords Image Retrieve DNA Fingerprint Indentification SVM
0 引　言
农作物优良品种在农业生产中发挥了重要作用，也深受农民的欢迎。然而近年来不断发生种子质量问题，如假冒伪劣、纯度严重超标等，有的还造成重大损失乃至产生社会问题。解决这类问题的关键在于建立准确、快速的种子鉴定方法，杜绝假冒伪劣种子进入市场。生物指纹图谱（fingerprint）是能够鉴别生物个体之间差异的电泳图谱，所构建的品种指纹图谱象人的指纹一样具有个体特异性，能较快速、准确鉴定品种或品系，为作物育种和种子管理提供极大的便利。
然而，人工鉴别指纹图谱的难度较大，主要由于：（一）品种数量多，同一品种，又由于品种纯度差异，图谱差异不大，人工比对的工作量大；（二）不同电泳凝胶上的品种的比较几乎无法实现。因此人工鉴别的的效率不够高。近年来，农作物种子的指纹图谱与计算机技术相结合应用于农作物种子品种的分析、鉴别研究工作已逐步开展起来。涉及到的关键技术有：图谱特征提取、特征匹配算法。文献[1]提出了一种以指纹图谱的图像文件为输入，经过图像分析、迁移率标准化、样品库管理、样品匹配与识别，确定未知样品品种的方法。以谱带迁移率为特征，以品种间的谱带匹配率评价品种间的相似度。文献[2]提出采用数字图像处理技术，得到指纹图谱的条带数目以及各条带的相对迁移率和染色强度，构成各品种的指纹图谱模式。通过比较各品种的指纹图谱模式来鉴定待比较的品种是否为新品种。现有的方法，都是首先对已知样品的图谱做预处理；抽取图谱特征建立标准特征数据库；然后抽取未知样品的图谱特征，并与标准特征数据库进行比较。这些方法对图像预处理要求较高，要对谱带做严格的拉平、对齐等人工校正工作，有些谱带归一化后差别极其细微，它们在特征空间中的距离变小，使得相似度分析能力变弱。因此如何补偿这些不足，减低图谱预处理要求，提高检索和识别的效率和准确率，形成可以在实际运用中推广的检索方法，成为关键。
我们认为，可以将品种图谱检索问题作为分类问题来研究，方法是：提取品种指纹图谱中的关键特征，采用支持向量机[3]（support vector machine, or SVM）作为学习机器，选取已知品种的图谱进行学习，为图谱分类建立分类器，然后利用分类器对未知品种的图谱进行分类检索，从而鉴别出未知品种。这种方法的特点是：利用支持向量机较强的泛化能力对候选特征进行细分类，对获取的特征进行训练与识别，解决特征提取后不同类别样本之间细微差别所带来的识别困难。
本文首先介绍SVM相关概念和水稻指纹图谱及其特点，然后说明图谱特征向量的获取过程，图谱分类器的构造方法，以及我们的实验结果。
1 相关概念
1.1 支持向量机
支持向量机[4]是Vapnik等人提出的一种新型机器学习方法，已经在模式识别、回归分析和特征选择等方面得到了较好应用。它根据结构风险最小化准则，在使训练样本分类误差极小化的前提下，尽可能提高分类器的泛化推广能力。同时，也能够较好解决小样本学习问题，得到现有信息下的最优解。遇到样本是线性不可分的情况，支持向量机通过事先确定的非线性映射将输入向量映射到一个高维特征空间，在此高维空间中构建最优超平面，从而解决线性不可分的问题。从实施的角度，算法最终将转化成为一个二次型寻优问题，得到的将是全局最优点，克服了在神经网络方法中无法避免的局部极值问题。
SVM依据结构风险最小化原则，将其学习过程转化为优化问题。对一组训练样本（xi，yi）(i=1，2，3，…，l，xi ∈Rn，yi∈{1，-1}l)，为获得最少错分样本和最大分类间隔，即获得最优分类面，SVM需要解决的问题是在满足式（2）约束条件下最小化式（2）给出的目标函数Φ（ω，ξ）。

(1)

(2)

其中训练样本xi被函数zi=Φ(xi)映射到高维空间中，ω∈Rn是超平面的系数向量，b∈R为阈值，ξ为松驰变量，C≥0是对错分样本的惩罚因子。
利用Lagrange多项式把上述最优分类面问题转化为其对偶问题，即寻找最大化目标函数：

(3)
满足约束条件：

(4)

ai为与每个约束条件(3)对应的Lagrange乘子。这是一个不等式约束下二次函数寻优的问题，存在唯一解。在寻优过程中，解中只有一部分（通常是少部分） （i不为零，对应的样本就是支持向量或边界支持向量。只有支持向量影响最终的划分结果。训练支持向量的过程也是寻找支持向量的过程。
于是相应的分类决策函数为：

(5)

其中，ai*为对应a≠0的向量，称为支持向量；m为支持向量的数目，b*为与ai*对应的阈值；K(xi,xj)= Φ(xi)·Φ(xj)为核函数。

1.2 指纹图谱
典型的水稻种子SSR[7]指纹图谱呈带状，如图1所示。

图1 水稻种子SSR指纹图谱

上图左右两边是参照物的图谱。中间是四个不同品种的图谱。RM227、RM72、RM152、RM55是SSR分析所采用的引物名称，引物名称旁标注的数字，2、13、14、15等，是等位基因序号。图谱上的明显深棕色区域为条带。各条带的中心位置相对于参照引物的第一条带的中心位置称为该条带的相对迁移率。
归一化后的条带迁移率的计算：
(6)
公式(6)中xi为第i条条带相对迁移率（距参照物第一条谱带的距离），A为该参照物图谱的起始距离，B为参照物图谱的结束距离。计算得到的样品的归一化后的谱带集为（Rm1,Rm2,…,Rmn），Rmi为归一化后的条带迁移率，即标准迁移率。
2 支持向量机应用于指纹图谱检索的方法
2.1 方法过程
建立和运用分类器的方法过程如下：
Step1：数据采集，得到已知品种的样品图谱。通过特定的制备指纹图谱的设备，可能得到成图像件，或者先将制备好的指纹图谱拍照，再扫描成图像文件。
Step2：提取已知品种的样品特征，形成特征向量组。
Step3：使用特征向量组，构造SVM多分类分类器。
Step4：提取未知品种的样品图谱，用分类器识别。

2.2 特征向量提取
图像特征的选取是设计图像检索系统的关键。好的特征应该能够排除噪音，抓住图像类的本质。特征的这种性质可以用不变性来刻画。直观地说，所谓不变性，就是特征在描述图像的内容时不受图像某类形变，如平移、旋转、缩放等的影响的性质。从图2可以看到，不同水稻品种图谱中的条带数目和条带迁移率有差别，与颜色和纹理没有直接关系。因此，我们选取样品的条带数目和条带迁移率作为样品的关键特征。主要步骤为：1、图谱预处理；2、提取条带边缘；3、跟踪条带轮廓；4、计算条带迁移率，形成特征向量。
2.2.1 图谱预处理
由于图谱制作的环境条件不同，即使是同属一个品种，它们的指纹图谱在图像亮度、对比度、分辨率、噪音等方面表现也存在差异。因此，首先对已制作完成的水稻指纹图谱进行预处理，基本过程为：①彩色RGB图像转换为灰度图像；②去噪；③二值化处理； ④提取边缘；⑤细化。也就是，首先用SSR方法采集水稻的指纹图谱，然后对采集到的彩色图谱RGB图像做灰度图像转换，去除噪声，转为黑白二值图，提取边缘后再细化，得到只有黑白两个灰度的图像，其中一个灰度代表边缘，另一个代表背景。
2.2.2 条带边缘提取
为了得到图谱的条带数目和各条带的迁移率，首先提取各条带的轮廓边缘。
图像上区域的边缘反映为相邻像素间灰度值的跃变。边缘检测可借助空域微分算法通过卷积或类似卷积的运算来实现。对数字图像而言，求导数实际上求的是差分。有两种主要类型的微分边缘检测，即一阶微分、二阶微分。用于提取图像边缘的算子有拉普拉兹算子、索贝尔算子、罗伯特算子等。拉普拉兹算子是2阶微分算子，相当于求取2次微分，它的精度还算比较高，但对噪声过于敏感，有噪声的情况下效果很差是它的重大缺点，所以这种算子并不是特别常用。索贝尔算子是最常用的算子之一，它是一种一阶算子，方法简单效果也不错，但提取出的边缘比较粗，要进行细化处理。我们采用了索贝尔算子来进行边缘提取，得到条带的轮廓。
2.2.3 条带轮廓跟踪
对提取了边缘的各个条带，进行轮廓跟踪，生成每一个条带的链码表。由于一幅图像有多个封闭的条带区域，我们采用多区域跟踪方法，根据边界的连通性，逐点跟踪得到区域的边界，从而将不同的区域分割开来。方法是：1、寻找跟踪起点；2、单区域跟踪；3、对象区域填色（一个区域跟踪完，即用背景色将此区域填充，以避免重复跟踪）；4、重复第1至3步至没有发现新的区域。
条带的轮廓边界用8方向链码Freeman链码[5]描述。一个条带的边界用一个起始点的坐标和一个方向编码的序列来表示。
2.2.4 形成特征向量
利用得到的条带链码表，可以计算出各条带的中心点Y坐标，即条带相对迁移率，再对各个相对迁移率利用公式（5）做归一化处理后，得到样品的特征向量为v={n,Rm1,Rm2,…,Rmn}，n是样品图谱的条带数目，Rmi表示第i个条带的标准迁移率。
经过上述方法，得到每个已知样品的图谱特征向量，形成训练集V={v1,v2,…,vm},i=1，2，…，m。m为样品图谱数。对于水稻种子指纹图谱，我们取最大条带数为30。
2.3 使用SVM构造分类器
选取已知品种的样本，构造学习机器。每经过一次学习，我们便修改对应的SVM模型。训练学习完成后，便得到了可用于分类的分类器。在识别阶段，我们对未知品种的样本用刚得到的分类器进行分类，就可以得到未知品种可能对应的品种类别。
考虑到品种分类是一个多类别的模式分类问题，需要采用多分类SVM分类器进行分类。对于多类SVM分类器的构建，目前主要有两种方法[6]：“一对一”模式和“一对多”模式。在本文中，我们采有“一对一”模式，构造N个品种的M（M=Nx（N-1）/2）个分类器。对每一待鉴别的样品，分别求其在这M个分类器中的分类情况。对N个品种分类其实是对M个分类器进行投票，如果属于哪一类就对那个类别统计加1。最后采用投票方式决定其归属。
分类算法如下：
//遍历所有的分类器
FOR I = 1 to M
//对每个分类器进行判断
{
if x ∈ j ClassifyResult[j]+ = 1; // j∈1……N
//看哪一类得票最多，便属于哪一类
For J = 1 to N {
If (ClassifyResult[j] > MaxCount)
{ MaxClassID=j;
MaxCount = ClassifyResult[j];
}
}
}
3 实验
我们选取10个水稻品种，每个品种取5个样品图谱，共50个样本的特征向量组成训练集，用SVM建立分类器，取30个未知品种样品做测试集。另外，采用欧几里得距离方法进行对比，即先用训练集对已知品种的样品，建立特征向量库，然后，通过将未知品种样品的特征向量与特征向量库中的特征向量比较欧几里得距离来分类。样品i和样品j的特征向量距离，用如下方法计算：
xjk, 是样品j的第k个特征值。对所有样品xj，xj∈已知品种的样品特征, 计算d(i，j)，找出与未知样品特征具有最小欧几里得距离的样品。

我们用两种方法对比实验，表1是实验结果。
表1用支持向量机与欧几里得距离分类品种图谱的实验比较

SVM
欧几里得距离
识别速度
较慢
较快
识别率
95%
91%

从实验结果看，用欧几里得距离方法分类，将待识别样品的特征向量与样品库的样品特征向量计算欧几里得距离后做比较的方法，识别率不如支持向量机高。而用支持向量机方法虽然训练较慢，但识别率总体来说比欧几里得距离分类方法要高，特别是能克服不同类别样本之间细微差别所带来的识别困难。

表2 四种不同核函数的支持向量机对图谱识别率的比较

C=5
C=10
C=20
C=50
C=100
C=200
K(x,y)=x * y
90%
91%
91%
93%
94%
94%
K(x,y)= (xT*y+1)d
80%
89%
92%
93%
93%
95%
K(x,y)=tanh((ax*y+b)
89%
91%
92%
95%
94%
95%
K(x,y)=exp(-r|x-y||2)
90%
90%
92%
92%
93%
96%

表2是用本文的支持向量机学习方法的实验所得到的结果。从表中可以看出，四种核函数取不同的惩罚因子（本文公式（1）中的C）实验的识别率是不同的。当惩罚因子C取值200，核函数中选用RBF函数（K (x,y)=||x-y||2/e2），取得最高识别率96%。而传统的欧几里得距离是模式识别的基本方法，它通过简单的距离向量来比较，识别特别快，但识别率不高，特别对于一些线性不可分的数据效果不是很好。而支持向量模型虽然训练识别的速度要慢，但遇到样本是线性不可分的情况，支持向量机通过事先确定的非线性映射将输入量映射到一个高维特征空间，在此高维空间中构建最优超平面。从而解决线性不可分的问题，识别率总体来说要比欧几里得距离分类要高。
4 结论
为了采用计算机辅助快速鉴别农作物品种，研究人员从图谱预处理、特征提取、特征匹配方法等不同的角度提出了各自的方法。但是，依据品种图谱快速鉴别品种离实用阶段仍然有一定的距离。本文从分类器的角度，提出一种基于机器学习的品种图谱鉴别方法，尝试利用支持向量机较强的泛化能力以及在线性不可分间题上的优势，解决特征提取后不同类别样本之间细微差别所带来的识别困难。实验表明，本方法对图谱的预处理要求不高，分辨速度较快，识别率较高。

参　考　文　献
[1] 王宇生 孔繁胜. 基于图像处理的蛋白质指纹图谱分析系统. 计算机工程, 1998(06)：56-59.
[2] 黄湘华 冯秀兰等. 数字图像处理在植物新品种鉴定中的应用. 林业资源管理, 2004(8): 60-64.
[3] Vapnik V N. The Nature of Statistical Learning Theory[M]．New York: Springer-Verlag, 1995.
[4] Freeman H. On the encoding of arbitrary geometric configurations[J]. IEEE Trans Electron ComputEC-10，1961, 260-268.
[5] 陆宗骐 金登男. Visual C++.NET 图像处理编程. 北京：清华大学出版社, 2006.
[6] Hsu C W, Lin C J. A Comparison of Methods for Multicalss Support Vector Machines. IEEE Trans, On Neural Networks, 2002, Vol. 13, No. 2. 415-425.
[7] 李进波 方宣钧 杨国才 费震江 戚华雄.两系杂交稻亲本SSR指纹图谱的建立及其在种子纯度鉴定中的应用[J].杂交水稻,2005,20(2):50-53.

附 修改说明：
（1）对图2中的“RM”的做了说明。
（2） 在“3 实验”中，将距离向量法修改为“欧几里得距离方法”，并补充说明，与本文的方法在识别效果上进行了比较。
（3）对“3 实验”中的“核函数取不同的惩罚因子”，在1.1节，修改了文中内容，补充了“惩罚因子C”的含义。
（4）将 “正确辨认率”改为了“识别率”。