第39卷  计  算  机  学  报  Vol.39 2016 论文在线出版号  No.183  CHINESE JOURNAL OF COMPUTERS  Online Publishing No.183 ——————————————— 本课题得到国家自然科学基金(No. 61372158)、江苏省自然科学基金(No. BK20141487)、江苏省“333工程”高层次人才资助项目  (No.BRA2015351)资助、江苏省政策引导类计划（产学研合作）-前瞻性联合研究项目(BY2016009-03)、江苏省高校优势学科建设工程资助项目（PAPD）.  王斌(通讯作者)，男，1969年生，博士，教授，硕士生导师，中国计算机学会(CCF)高级会员（16022S），主要研究领域为模式识别、计算机视觉、图像处理.E-mail: wangbin@njue.edu.cn.  陈良宵，女，1992年生，硕士研究生，主要研究领域为计算机视觉、图像处理. 叶梦婕，女，1989年生，硕士研究生，主要研究领域为计算机视觉、图像处理.   弦特征矩阵：一种有效的用于植物叶片图像分类和检索的形状描述子   王斌1) ,2)    陈良宵1)  叶梦婕1)   1)(  南京财经大学  信息工程学院,  南京市  210023)   2)(  南京财经大学  电子商务省级重点实验室,  南京市210023)  摘  要  植物叶片形状一般具有小的类间差异和大的类内变化，再加之叶片的自遮挡和噪声的干扰，给叶片形状的识别带来了很大的挑战。本文提出了一种新的形状描述子—弦特征矩阵(Chord-features matrices, CFM)，以精确而又鲁棒的应用于植物叶片图像的分类和检索问题。该方法将目标轮廓线的弦，依据轮廓线所围成的区域，分成内和外两个部分。因其与轮廓线凸凹特性的相关性，该方法用多个尺度级的内部弦长和外部弦长生成两个矩阵，旨在隐式的描述轮廓线的多尺度的凸凹特性。该方法还定义了多个尺度级的弧到弦的平均投影长度，并构成矩阵，以反应轮廓线在各个尺度级下的弯曲程度。组合这三个矩阵所形成的CFM描述子，全面的刻画了轮廓线的几何特性，具有强的形状表征能力。用Swedish、Flavia和ImageCLEF三个具有挑战性的叶片图像测试集，对本文提出的CFM方法分别进行分类和检索性能评估，实验结果表明，本文提出的方法在精确度和对噪声的鲁棒性方面均优于其他植物叶片图像分类和检索方法。而本文提出的方法在MPEG-7 测试集上的实验结果则验证了其具有应用于一般的形状识别任务的潜力。 关键词  形状描述；内外弦长；叶片图像分类；叶片图像检索 中图法分类号  TP391     论文引用格式 王斌，陈良宵，叶梦婕，弦特征矩阵：一种有效的用于植物叶片图像分类和检索的形状描述子，2016，Vol.39：在线出版号  No.183 Wang Bin，Chen Liang-Xiao，Ye Meng-Jie，Chord-features matrices: an effective shape descriptor for plant leaf classification and retrieval,2016, Vol.39: Online Publishing No.183 Chord-features matrices: an effective shape descriptor for plant leaf classification and retrieval Wang Bin1) ,2)    Chen Liang-Xiao1)    Ye Meng-Jie1)   1) ( School of Information Engineering, Nanjing University of Finance and Economics, Nanjing 210023) 2) ( Provincial Key Laboratory of Electronic Business, Nanjing University of Finance and Economics, Nanjing 210023) Abstract    Identifying  leaf shapes  is  a  challenging  task  due to  the  small  inter-class differences  and large intra-class  variations appeared  in  the  leaf  shapes.  The  self-occlusion  and  noise  disturbing  also  make  this  task become  very  difficult. In  this  paper,  a  novel  shape  descriptor,  termed  Chord-features  matrices  (CFM),  is proposed for plant leaf image classification and retrieval. In the proposed CFM, the chord of the object contour is partitioned into two parts, the inner one and the outer one, according to the region enclosed by the contour. Due to  their  high  correlations  to  the  convex  and  concave  properties  of  the  contour,  their  lengths  are  utilized  to 网络出版时间：2016-12-14 17:52:31网络出版地址：http://www.cnki.net/kcms/detail/11.1826.TP.20161214.1752.002.html2  计  算  机  学  报  2016年  generate  two  matrices  for  characterizing  the  convex  and  concave  properties  of  the  contour  in  multiscale.  In additional,  the  projection lengths from  the  arc  to  the  chord  are  also  used  to  build  a  matrix  for  reflecting  the bending degree of the contour. The combination of these three matrices characterizes the contour from coarse to fine  which results a  shape  descriptor with powerful  discriminative  ability  for  accurate  plant  leaf  classification and retrieval. The proposed CFM has been tested on three Challenging plant leaf image databases, including the well-known the Swedish,  Flavia  and  ImageCLEF  databases.  All  the  experimental  results  demonstrate  that the proposed  CFM  approach  outperforms  the  state-of-the-art methods  for shape  based leaf recognition. An  extra experiment  conducted  on  the  MPEG-7  dataset further indicates  its  potential  application  to  the  task  of  general shape recognition.   Key words  shape description, inner length and outer length, leaf image classification, leaf image retrieval  1  引言 目标形状是描述图像内容的一个非常重要的视觉特征[1,2]，在目标检测、图像检索、目标识别中有着广泛的应用[3]。形状的描述与匹配是基于形状特征的目标识别的两个关键步骤。形状描述旨在抽取目标的有效的形状特征，并存储于特定的数据结构，形状匹配的主要任务是对抽取的形状特征进行比较，并采用某种度量，来计算两个形状的相似性值。在许多应用中，如植物叶片图像的识别，目标形状通常存在类内差异大，而类间差异小的问题，因此在形状描述阶段，如何抽取具有强的鉴别能力的形状特征，即最能反映形状类间差异的特征，是一个挑战性的问题。由于目标的平移、旋转和缩放（也称相似性变换）并不改变其形状，因此抽取的形状特征还必须进行归一化处理，以使其满足对相似性变换的不变性。噪声的干扰，植物叶片的遮挡等都会影响算法的稳定性，对识别算法造成挑战。另外，许多实际应用，如移动计算环境的目标识别，在线目标识别，大规模图像数据检索等，都对计算的效率有较高的要求，因此在保证高的形状识别精度的同时，还要尽可能的降低形状识别的计算复杂度。 目标的轮廓线对目标形状具有重要的表征特性，而人的视觉也主要通过目标轮廓线特征来识别目标的形状[2,4,5]。因此，抽取目标轮廓线的不变特征，以用于目标识别，构成了一大类方法—基于轮廓线的形状识别方法[1,2,4-14]。该类方法已产生了大量的实际应用，如遥感图像分析中的湖泊的变化检测[7]，医学肿瘤形状的检索[15]，海生鱼类图像的检索[16]，植物叶片图像的检索[17]等。本文着眼于从轮廓线上抽取有效的形状特征，并实际应用于植物叶片图像的分类和检索问题。 人的视觉感知对目标轮廓线的凸凹特性非常敏感[14],将其作为目标识别的一个重要依据。在计算机视觉的形状分析研究中，一类研究工作就是着眼于轮廓线的凸凹特征的抽取，以有效的用于目标的识别、分类和检索[14, 18-20]，如，曲率尺度空间方法(curvature  scale-space  representation)[18]  被MPEG-7推荐为标准的轮廓线形状描述子，并产生了大量的实际应用，该方法直接用曲率来度量轮廓线的凸凹特性。对于一个全凸的形状，其轮廓线上的所有的弦（连接轮廓线两点的直线段）都会落在轮廓线所围成区域的内部（示例见图1的左图），而对于一个有着凹弧段的轮廓线，总有一部分弦的全部或部分落在该区域的外部（示例见图1的右图）。因此，轮廓线的弦落在形状内部区域的部分和落在外部区域的部分与轮廓线的凸凹性有着相关性（前者相关于轮廓线的凸性，后者则相关于其凹性）。那么，抽取形状的凸凹特征，可以利用这种相关性，通过计算轮廓线的弦落在内部区域和外部区域的长度来间接的获取。本文的动机正是产生于这一基本认识，其主要贡献在于提出了一种新的形状描述子–弦特征矩阵，该描述子通过构造三个矩阵，有效的反应了轮廓线的凸凹特性和弯曲程度—这类对形状识别非常有价值的信息，并实际应用于植物叶片图像的分类和检索问题。  图 1 全凸的形状（左图）和有着凹凸弧段的形状（右图）论文在线出版号  No.183        王斌等：弦特征矩阵:  一种有效的用于植物叶片图像分类和检索的形状描述子    3  的弦的示例(白色标识的是弦落在形状区域内部的部分，灰色标识的是弦落在形状区域外的部分)  2  相关工作 迄今为止，基于目标轮廓线的弯曲特性，包括凸性、凹性、弯曲程度等几何特征，来进行目标识别，已提出了许多方法。其中，代表性的方法是各种基于曲率的描述子[18-20]。曲率是直接反应轮廓线弯曲特性的几何特征。但由于获得曲率需要计算轮廓线上的点的坐标函数的一阶和二阶导数，使得这类方法缺乏对噪声干扰的稳定性。文献[14]提出用不同宽度的高斯核平滑轮廓线，用轮廓线上的点在平滑过程中移动的距离来测量轮廓线在该点的凸凹特性，若点向内移动代表凸特性，向外移动则代表凹特性，由此构成一个多尺度的形状描述子，这里尺度是高斯核的宽度。文献[21]用归一化的面积积分代替曲率来测量轮廓线的凸凹性，这里面积积分是以轮廓线上的点为圆心，指定半径的圆与轮廓线包围区域相交的面积。若让圆的半径取不同的值，则可以构成一个多尺度的描述子。文献[5]提出用带符号的三角形面积来描述轮廓线的凸凹特征，正号表征轮廓线的凸特性，负号表征轮廓线的凹特性，这里三角形是由轮廓线上的点和它的左右邻点构成。但不同的三角形可能有相同的面积，为进一步提高描述子的形状表征能力，文献[22]提出用三角形的边长和内角来构造形状描述子。近来，文献[23]用带符号的多尺度的拱高来描述轮廓线的凸凹特性。这些方法在Flavia  leaf  dataset[24]、ImageCLEF[25]等公认的具有挑战性的植物叶片图像测试集上都取得了较高的检索精确率。除上述特征之外，由轮廓线上的点构成的角度特征也被用来描述轮廓线的凸凹特性[26,27,28]。最近文献[26]提出用不同尺度下的角度特征描述形状，以解决前述的三角形区域描述方法在进行形状匹配时，对微小形变的敏感问题和对剧烈变化的不相似形状的误匹配问题。 上述方法的共同点都是通过直接度量轮廓线的凸凹特性，用曲率或曲率的替代几何量来构造形状描述子，我们称这类方法为显示的凸凹特征描述子。另有一类方法，它们并不直接度量轮廓线凸凹特性，而是抽取与凸凹特性有着间接关联的几何特征来构造形状描述子，我们称这类方法为隐式的凸凹特征描述子。在该类方法中，文献[29]提出了一种最远点距离描述子。该方法对轮廓线的每一个点都找到其在轮廓线上的最远点，用该点和其最远点分别到轮廓线中心点的距离的和作为抽取的形状特征，该方法旨在描述轮廓线的角点信息。一段弧越弯曲，其弦长一般会变得越短。基于该认识，文献[12]提出用弦长特征来描述轮廓线的几何特性。该方法以轮廓线的每一个点作为始点等弧长的分割轮廓线，用连接分割起始点和各割点的弦的长度作为抽取的轮廓线的几何特征，当起始点沿轮廓线移动一周，所产生的各级弦长函数构成了形状描述子。近来，文献[4]提出了距离矩阵描述子。该方法首先将轮廓线均匀的采样成一个点的有序集，第k个采样点依次到其他各点的欧式距离构成了矩阵的k行。通过对矩阵的循环移位和尺度的归一化操作后的距离矩阵构成了对形状的描述子。文献[4]同时也提出了距离矩阵的另外一个版本：将欧式距离替换成文献[10] 提出的内部距离。这里轮廓线上两点的内部距离定义为：从其中一个点出发只经过轮廓线所围区域的路径到达另外一点的最短路径的长度。文献[12]和文献[4]在应用于植物叶片图像的识别中都取得了比较高的精确率。 除了抽取轮廓线的弯曲特性来描述形状，近些年来，一些方法致力于抽取轮廓线上点的空间分布特征来进行形状识别。经典的方法是形状上下文方法[13]。该方法在轮廓线上的每一个点放置对数极坐标栅格，以生成统计其他个点相对于该点的空间分布的直方图，该直方图被称为形状上下文描述子（Shape Contexts）。文献[10]对该方法用内部距离替代欧式距离，产生内部距离形状上下文(Inner-distance  shape  contexts)描述子，以应用于非刚体的目标识别。文献[30]提出在对数极坐标中引入模糊隶属度函数，将轮廓线上的点模糊划分到对数极坐标栅格，生成模糊形状上下文描述子。近来，文献[31]直接用轮廓线上的点，通过对数极坐标变换，构造对称奇数阶对称循环矩阵。基于生成元循环时，所得循环矩阵的特征值不变的理论，用生成的对称循环矩阵的特征值来描述形状。该描述子具有缩放、旋转和平移不变，对运动目标和非刚性形变的形状检索，具有良好的鲁棒性和高效性。 近来，用学习的方法产生形状描述子引起广大学者的关注。前述方法，是将单个图像作为输入，产生该图像的描述子，而基于学习的方法，则输入的除待描述的图像之外，还有通过训练集生成的词包或词典。比较有趣的算法是近来提出的轮廓线片4  计  算  机  学  报  2016年  段包（bag of contour fragments，BCF）算法[32]。该算法首先将图像库中的每一个目标的轮廓线拆分成若干个有意义的片段，并为每一个片段构造形状上下文（Shape Context[13]）描述。然后利用训练集中的样本图像，选取其中部分图像的轮廓线片段集作为训练特征，通过k均值聚类算法，用得到的类中心集合生成轮廓线片段的码本(codebook)，再用该码本为每一个形状进行编码，从而得到形状描述子，最后利用简单的线性SVM分类器完成形状图像的分类任务。该算法得到的描述子鲁棒、紧致而又精确的保留了包括轮廓线片段的空间布局信息在内的有价值的形状特征，且具有高的形状匹配效率。最近，文献[33]提出一种基于学习机制的模式计数（pattern  counting）形状描述子。该方法首先通过对轮廓线的点的坐标进行不同尺度的高斯卷积，构造多尺度的形状上下文描述子，再通过词典学习方法[34]，利用训练集中的样本，生成形状模式词典。基于该词典和形状的多尺度上下文描述子生成一个稀疏矩阵表示，矩阵的每一行对应于模式词典的一个模式，矩阵的每一列对应于轮廓线的一个点，矩阵元素的值为0表示相应的模式在该轮廓点没有被使用，非0值则表示被使用。对矩阵的每一行进行非零元素的计数，得到一个直方图，经归一化后，表征了一个给定形状的多尺度形状特征在模式词典中的所有模式上的分布。该方法用得到的直方图（称为模式计数  pattern counting）的2x距离度量形状差异度。该方法能有效的应用于植物叶片图像的分类问题，也具有拓展到应用于一般形状识别任务的潜力。 此外，文献[24-25,35-39]也提出了一些基于形状特征的植物叶片图像分类或检索算法。最近的工作有：文献[38]将叶片图像表示为一个2D的二值函数，用基于该函数的2D傅里叶功率谱生成不变的形状描述子，该方法在植物叶片图像的分类中报告了较好的结果。文献[37]则抽取叶片图像的矩特征、其轮廓线的1D傅里叶变换系数特征和叶片的相对大小(定义为叶片轮廓的最远点距离与叶片图像库中所有叶片轮廓的最远点距离的最大值的比值)特征，作为叶片形状描述子。该方法在植物叶片图像的分类中取得了较好的效果。文献[39]提出用快速Curvelet变换得到三个变换系数，再对每一个系数，用其第一个不变矩表征形状，由此得到一个三维的形状特征向量。但其对叶片图像的表征能力较弱，从报告的叶片图像分类结果来看，用该形状描述子的分类精确率仅为50%左右。该文献又提出抽取叶片图像的纹理特征，再与该形状描述子组合使用，取得了97.6%的分类精确率。在本文的实验部分，我们引用了这些方法报告的实验结果，以进行性能比较。最近的有关植物叶片图像识别的综述可见文献[40]，而有关形状描述和匹配的综述论文可见文献[41]。 本文提出的方法属于隐式的描述轮廓线的凸凹特性的方法，其创新性在于：前述的显示的凸凹特征描述子都是在给定的尺度级，从轮廓线截取一弧段进行凸凹特性的测量，通过某种几何量，如曲率，拱高，三角形面积的正负等，来确定其整体的凸性或凹性。但存在的事实是，一个曲线段一般既有凸成分，又有凹成分。这些方法并不能细致的描述曲线段的这一特性。而对于隐式的描述方法，用弦长、最远点距离等特征，只能在一定程度上间接反应轮廓线的弯曲程度，但并不能刻画轮廓线的凸性和凹性，这一对形状识别非常有价值的信息。本文提出的方法克服了上述方法的局限性，该方法通过抽取多个尺度的弦的内弦长（与凸性关联）和外弦长（与凹性关联）来构造描述子，从而更为细致的描述了弧段的凸和凹这两个方面特性。同时，本文提出的描述方法，还加入了弧到弦的平均投影长度特征，以反应弧段的整体弯曲程度，从而更为全面的反应了轮廓线的几何特性。另外，本文提出的方法也不同于基于学习机制的形状描述子，其描述子是独立产生的，并不依赖于训练集，使得其在没有训练集的情况下仍然能使用，如应用于网络图像数据的检索等。 3  弦特征矩阵描述(CFM) 3.1   弦特征矩阵 一个目标形状图像是一个二值化图像，可以一般的表示为一个二值函数 ( )( ) 1, ,,0,if x y Df x yotherwiseìÎ =íî                          (1) 这里x和y分别是形状图像像素点的横纵坐标，D是目标形状在图像中的分布区域。抽取形状f的外轮廓线，并对其进行均匀采样，构成一个长度为N的有序的像素点集( ) { } , , 1, ,i i i C P x y i N ==L，这里2TN=，且T取正整数。因为目标轮廓线是闭合的，论文在线出版号  No.183        王斌等：弦特征矩阵:  一种有效的用于植物叶片图像分类和检索的形状描述子    5  所以有N i iPP+=。 令, sil表示从轮廓线上的点( ) ,i i iP x y出发，沿轮廓线按逆时针方向到达另一点( ) ,i s i s i sP x y+ + +所经过的弧段的弦的长度，其值可以用下式计算： ( ) ( )22 , s i i i s i i sl x x y y++ = - + -                      (2) 该弦落在形状区域D内的部分的长度用( ), siIl表示，称为内弦长；落在形状区域D的外部的长度用( ), siOl表示，称其为外弦长。令1x和2x分别为ix和isx+的最小值和最大值，1y和2y分别为iy和isy+的最小值和最大值，则(),Isil和(),Osil的形式化定义如下： ( ) ( )2211(),,xyIsixyl f x y Ax By C dxdy d = + -òò      (3) 和 ( ) ( ), , ,OI s i s i s il l l =-                                                (4) 这里( ) ( ),, s i i s i s i i s iA y y l B x x l++ = - = - ，， ( ), i s i i s i s iC x y y x l++ =-，( ) d g表示Dirac函数。需要指出的是，这里0 Ax By C + + =是点iP和点isP+所决定的直线的法线式方程。从公式3可以看出，内弦长(),Isil是形状函数( ) , f x y在弦i i sPP+上的投影长度。图2的左图给出了轮廓线内外弦长的一个示例。 除了弦的内外弦长，本文还定义与弦有关的另外一种几何特征—弧到弦的平均投影长度(简称平均投影长度，这里用(),Psil表示），其数学定义如下： ( )1(),11,1sPs i i t i i stl d P PPs-++ ==-å                      (5) 这里( ),i t i i sd P P P++表示弦i i sPP+所对应的弧(s个单位长度)上的点itP+到该弦的投影距离。图2的右图给出了轮廓线上的一段弧到其弦的投影的一个示例。  图 2 轮廓线的弦特征示例。左图：轮廓线的内弦长（白色标出的部分）和外弦长(灰色标出的部分)；右图：轮廓线的一段弧(轮廓线上灰色标出的点)到其弦的投影  首先固定变量s，让变量i从1变化到N，我们得到了N段同为s个单位长度的弧所对应的弦（轮廓线上的每一个点作为弧的始点）。通过计算每一段弦的内弦长、外弦长和平均投影长度，可以生成三个序列：外弦长序列( ) ( ) ( ),1 ,2 ,, , ,O O Os s s Nl l l K，内外弦长绝对差序列( ) ( ) ( ) ( ) ( ) ( ),1 ,1 ,2 ,2 , ,, , ,I O I O I Os s s s s N s Nl l l l l l - - - L和平均投影长度序列( ) ( ) ( ),1 ,2 ,, , ,P P Ps s s Nl l l L  。再让变量s分别取值1 2 12 , 2 , , 2T-L（注意，这里2TN =），由此产生如下三个( ) 1N T-´的矩阵： （1）外弦长矩阵  (见公式6) ( ) ( ) ( )( ) ( ) ( )( ) ( ) ( )1 1 12 2 21 1 12 ,1 2 ,2 2 ,2 ,1 2 ,2 2 ,2 ,1 2 ,2 2 ,T T TO O ONO O ONO O ONl l ll l lOMl l l- - -æö ç÷ ç÷ ç÷ =ç÷ ç÷ èøLLM M L ML            (6) （2）内外弦长绝对差矩阵(见公式7) （3）平均投影长度矩阵(见公式8) 6  计  算  机  学  报  2016年   ( ) ( ) ( ) ( ) ( ) ( )( ) ( ) ( ) ( ) ( ) ( )( ) ( ) ( ) ( ) ( ) ( )1 1 1 1 1 12 2 2 2 2 21 1 1 1 1 12 ,1 2 ,1 2 ,2 2 ,2 2 , 2 ,2 ,1 2 ,1 2 ,2 2 ,2 2 , 2 ,2 ,1 2 ,1 2 ,2 2 ,2 2 , 2 ,T T T T T TI O I O I ONNI O I O I ONNI O I O I ONNl l l l l ll l l l l lIODMl l l l l l- - - - - -æö- - -ç÷ ç÷- - -ç÷ =ç÷ ç÷ ç÷- - -èøLLM M L ML        （7） ( ) ( ) ( )( ) ( ) ( )( ) ( ) ( )1 1 12 2 21 1 1P P P2 1 2 ,2 2 ,P P P2 ,1 2 ,2 2 ,P P P2 ,1 2 ,2 2 ,PT T TNNNl l ll l lMl l l- - -æö ç÷ ç÷ ç÷ =ç÷ ç÷ èøLLM M L ML，                    (8) 将这三个矩阵组合在一起，就构成了一个形状描述子，我们称之为弦特征矩阵描述子(chord-features matrixes, CFM)。 弦特征矩阵描述子CFM中的PM矩阵用来描述轮廓线的弯曲程度。一段开曲线可以看成是一条同长度的直线段经过弯曲而成，因此，本文定义的弧到弦的平均投影长度，在一定程度上反应了曲线的弯曲程度这一几何特性。但仅用该特征并不能描述曲线段的凸凹特性。一段曲线一般既有凸的成分，又有凹的成分。描述子CFM的外弦长矩阵OM 和内外弦长绝对差矩阵IODM旨在描述曲线的这一特性，以提高描述子的形状辨识能力。如果轮廓线是全凸的，那么连接轮廓线上的任意两点所构成的弦都落在轮廓线所围成的区域内部。而当轮廓线不是全凸的，即存在凹的曲线段，则必有弦的全部或部分落在形状区域的外部。因此，弦的外部弦长特征与轮廓线的凹的特性密切相关。描述子CFM的外弦长矩阵OM正是用来描述轮廓线的凹的特性。一条轮廓线又不可能是全凹的，即所有的弦都落在轮廓线区域的外部的情形是不可能出现的，因此在CFM 中，与轮廓线的凸特性密切相关的内部弦长也被用来产生描述子，以描述轮廓线的凸的特性。一个轮廓线有凹的成分，那么该轮廓线必有凸的部分存在。 需要说明的是，这里没有单独构造内部弦长矩阵，以直接反应轮廓线的凸的特性，而是构造了内外弦长差矩阵IODM，以隐式的反应轮廓线的凸的特性同时，还能描述曲线段的凸凹部分之间的关系。当轮廓线是全凸的时候，则外弦长矩阵为0矩阵，即所有弦的外弦长都变为0，此时的IODM 矩阵也就变成了内弦长矩阵。值得指出的是，虽然用弦特征描述形状的想法并不是新的，如文献[12]和文献[4]都用到了弦长，但单一的弦长特征并不能描述形状的凸凹特性，而本文提出的弦特征描述子组合了内弦长、外弦长和弧到弦的平均投影长度这三类特征，能更为精确的描述形状的几何特性，这是本文提出的方法跟其他采用弦特征描述方法的主要不同的地方。 弦特征矩阵描述子CFM具有多尺度的形状描述能力，这里弧长s对应尺度。CFM的三个矩阵的每一行的特征都属于相同的尺度级。矩阵共有T-1行，因此共有T-1个尺度级，矩阵的第一行对应最小尺度级，矩阵的最末行对应最大尺度级，这里log N T=。图3给出了多尺度的内外弦长的一个示例。小尺度特征主要描述形状的细节信息，而大尺度特征则主要描述粗的形状特征，由此构成了一个由粗到细的形状描述。需要指出的是，本文提出的CFM描述子的尺度级的选择不同于文献[4]和文献[12]给出的方法。虽然CFM与它们一样都是基于多尺度的方法，但是在尺度级的选择上与它们有明显的不同。文献[4]和文献[12]提出的方法采用的尺度级是均匀分布的，即大尺度级和小尺度级的个数是相等的。而本文提出的CFM 描述子采用的尺度级的分布是不均匀的，对于一个有N个点的轮廓线，CFM选择的尺度级为1 2 12 , 2 , , 2Ts-= L，可看出其小尺度级的分布是密集的，而大尺度级的分布是稀疏的。这种选择的理由是，对于轮廓线上的一点，其在轮廓线上的邻近点要比那些轮廓线上的远点联系更为紧密。因此让小尺度级分布密集，大尺度级分布稀疏的尺度选择方法有其合理性。另外，本文提出CFM方法的重要应用是植物叶片图像的识别，而很多种树叶图像的轮廓线往往在整体特征非常相似，需要依靠大量的细节信息（小尺度特征）才能进行区分，如一些树叶图像的轮廓线包含很多细小的锯齿状边缘，需要依靠小尺度的特征才能揭示其凹凸特性。而小尺度级和大尺度级均匀分布的尺度级选择方法，会造成小尺度特征在描述子中得不论文在线出版号  No.183        王斌等：弦特征矩阵:  一种有效的用于植物叶片图像分类和检索的形状描述子    7  到凸显，使得整个描述子的形状辨识能力不高。   图 3 轮廓线（128个采样点）的3个尺度级的内弦长（白色显示）和外弦长（灰色显示）的一个示例（从左图到右图，尺度s=4、16、64 3.2   特征的归一化 因为目标的平移、旋转、缩放并不会改变其形状，所以在进行识别前，要对抽取的形状描述子进行归一化操作，以使其满足对这些几何变换的不变性。当目标发生平移时，连接轮廓线上的两点的弦也发生相同的移动，由公式3、4、5可以证明弦的内弦长、外弦长和平均投影长度长保持不变。因此，目标形状的外弦长矩阵OM和内外弦长绝对差矩阵IODM和平均投影长度矩阵PM都具有内在的平移不变性。 当目标发生缩放，假设目标函数由( ) , f x y变为( ) , f x y aa，这里0 a>是缩放系数，由公式3和4可以证明内弦长(),Isil、(),Osil和(),Psil将分别变为(),Isil a×、(),Osil a×和(),Psil a×。  这里对描述子CFM的OM矩阵、IODM矩阵和PM矩阵采用相同的归一方法。具体做法是，对矩阵的每一行的每一个元素，用该行的最大值进行归一。因为相同尺度的特征位于矩阵的同一行，这里按行分别进行归一，保证了各个尺度级的特征在目标识别中具有相同的贡献，不会产生因为某个尺度级的特征数据值过大，而使得其他尺度级的特征在目标识别中失效的问题。 当目标发生旋转，轮廓线上的弦也发生相同的旋转，由公式3、4、5也可以证明弦的内弦长、外弦长、平均投影长度保持不变。但需要指出的是目标的旋转会使轮廓线的采样起始点发生改变，从而使三个矩阵OM、IODM 和PM的每一行发生环形移位，即矩阵中第i行，第j列的元素将被移位到第i行，第jt+列，这里1 tN ££是平移量。这里，我们采用傅里叶变换进行归一化操作。具体作法是：将每一行看成一个一维的离散信号，对其作一维离散傅里叶变换，用傅里叶变换系数的模的序列替换原来的行。根据傅里叶变换的原理，当一维信号发生平移，其傅里叶变换系数的模不发生改变，因此，经过傅里叶变换的三个矩阵对轮廓线的起始点都保持不变。对矩阵的每一行进行傅里叶变换所得到的向量的长度为N，为尽量消除噪声的影响和使得描述子更加紧致，我们取前M个低频系数，这里M是远小于N的正整数。通过该操作，CFM描述子的三个矩阵OM、IODM、PM都分别由原来的大小为( ) 1N T-´的矩阵变为大小为( ) 1M T-´的矩阵。 3.3   形状的差异性度量 通过前述的特征归一操作，CFM描述子的三个矩阵都已满足平移、旋转和缩放不变，可以通过直接比较两个形状的CFM描述子中的三个矩阵，来度量两个形状的差异度。设形状A的CFM描述子的三个矩阵OM、IODM 、PM 分别为：( )( ) 1MAijTa-´,( )( ) 1MAijTb-´和( )( ) 1MAijTg-´，而形状B为( )( )B1MijTa-´,( )( ) 1MAijTb-´和( )( ) 1MAijTg-´。则形状A和形状B的差异度定义为： ( )( )111,3TMA B A B A Bij ij ij ij ij ijijdiff A Ba a b b g g-=== - + - + - åå    (9) 这里N是轮廓线采样点的个数，log N T=，而MNg是在对描述子CFM进行归一化操作中所引入的参数。 至此，本文提出的CFM描述子仅涉及到两个参数为：（1）对图像的目标轮廓线进行均匀采样的点的个数N；（2）在归一化阶段，对CFM中矩阵的每一行进行傅里叶变换，所保留的低频系数的个数M。   3.4 鲁棒性分析 在本节，我们首先分析CFM方法对噪声干扰的鲁棒性。从计算弦特征的公式3、4、5可以看出，内外弦长和平均投影长度是通过积分运算和求和运算获得的，而这种运算本身对噪声干扰就具有压制作用[21]。另外，在特征归一阶段，我们对矩阵的8  计  算  机  学  报  2016年  每一行都进行了傅里叶变换，去掉了其高频系数，通过这一操作，又进一步的增加了CFM描述子对噪声干扰的鲁棒性。图4给出了叶片图像和加入了噪声干扰的图像的CFM描述子的比较。从该图可以看出，原图像和其噪声图像的CFM描述子的对应的数据点大多是重叠的，少数不重叠的数据点也非常靠近，显示了CFM描述子对噪声干扰的稳定性。在本文的后面的实验部分，我们将专门用一组实验来验证算法对噪声干扰的鲁棒性。 下面讨论叶片图像的遮挡问题，主要是叶片的自遮挡问题。如图5的左图（未发生自遮挡）和中图（发生了自遮挡）所示。叶片的自遮挡将会使得抽取的外轮廓线发生局部的改变。如图5的中图，部分轮廓片段围城了两个空洞。因为轮廓线描述方法抽取的是外轮廓，因此这部分信息将被扔掉。因此，现有的基于轮廓线的描述子，在识别中将会产生很大的类内距离。一般来说，叶片自遮挡虽然对其轮廓线的抽取影响很大，但对叶片在图像的分布区域的影响却相对较小，从图5给出的示例图像也可以看出这一点。因此，在处理叶片的自遮挡问题上，让形状区域的像素点参与形状特征的抽取，会比仅使用轮廓线上的像素点更具鲁棒性。   图 4叶片图像原图(左上图)和加入强度为10%的椒盐噪声的叶片图像（左下图）的CFM描述子的比较（右图）。右边从下图到上图依次为它们的三个矩阵OM、PM、IODM 的第一行、第四行和第七行的数据。这里横轴的1-10、11-20、21-30分别表示矩阵OM的1-10列、PM的1-10列、IODM的1-10列,纵轴是矩阵元素的取值,“+”表示原图像的CFM的数据点，“o”表示噪声图像的CFM的数据点，这里CFM的参数设定为：N=256,M=10 用CFM的内外弦长，相当于是用一条直线段透射了形状的区域，对形状区域的内外几何特性进行了描述。如图5的中图，因为自遮挡所形成的两个空洞，在遮挡前属于外部区域，在遮挡后，仍然会被CFM的内外弦长看成外部区域，而不会看成形状的内部区域。因此，CFM在处理叶片自遮挡问题上，比现有的基于轮廓线的描述子更具鲁棒性。图5的右图是与左图和中图不同类的植物叶片，在图5中，我们给出了本文提出的方法CFM和另外两种基于轮廓线的方法MDM[4]和MARCH[23]对它们的比较结果。可以看到，采用本文提出的CFM描述子，遮挡的叶片（中图）与其同类叶片（左图）具有更小的形状差异度，而其他两种方法MDM[4]和MARCH[23]都认为遮挡的叶片与其异类叶片（右图）具有更小的形状差异度。 图 5 发生遮挡的叶片图像与同类叶片图像和异类叶片图像的基于不同描述子的形状差异度比较，横线上的数值是用相应的方法得到形状差异度 植物叶片往往有多个子叶片，如图6的第二行的最右边的叶片，它有13 个子叶片。这类叶片一般会发生子叶片姿态的变化，也会因子叶片姿态的变化，产生叶片的自遮挡现象。这些都会使得抽取的轮廓线发生较大的变化，但相对来说，对形状区域的影响较小。因此，对CFM的内外弦长特征的影响，相对于其他的轮廓线特征会小一些。后面的实验部分也验证了有着多个子叶片的叶片图像的识别结果比较理想。 叶片的空洞有两种情况，第一种情况是由叶片的自遮挡而形成的空洞，这种情况在前面已经讨论过，这部分信息是有用的信息，需要加以利用。第二种情况是非叶片原有的空洞，如被昆虫吃掉部分叶片而形成的空洞，这部分信息如果被抽取，会影响识别效果。因为抽取的是叶片的外轮廓，所以对CFM描述子的PM矩阵没有影响，但是因为弦会穿过空洞，所以会对CFM的OM矩阵和IODM 矩阵产生影响。由图3可以看出，弦穿过空洞的概率与尺度s有关系，当尺度值s越大时，弦穿过空洞的概率越大，但由于大尺度级的分布是稀疏的，因此其对OM矩阵和IODM 矩阵的影响较小。另外，同论文在线出版号  No.183        王斌等：弦特征矩阵:  一种有效的用于植物叶片图像分类和检索的形状描述子    9  类植物叶片有着很多自然的形变，对它们是无法建立一个统一的数学模型的。但是CFM方法的多尺度的描述框架不会使得局部的小的形变，造成类内距离的急剧增大，因为局部的小的形变，只会改变CFM矩阵中的少部分特征。 3.5 时间复杂度分析   本文提出的算法的时间复杂度包括两个部分，一个是形状特征抽取阶段的计算时间复杂度，即计算OM、IODM、PM三个矩阵的时间复杂度，一个是形状匹配阶段的时间复杂度，即计算公式9的时间复杂度。 我们先分析形状描述阶段的时间复杂度。假设图像的大小为WW´,轮廓线上的采样点个数为N=2T。因为轮廓线上任意一条弦的弦长小于或等于2W，因此计算弦的内外弦长的在最坏时间复杂度为( ) ( ) 2 O W O W =。则计算矩阵OM和矩阵IODM 的最坏时 间 复 杂 度 为( ) ( ) ( ) 1 log O W T N O WN N -=  。而计算公式5的时间复杂度为( ) Os，这里是s是弧段的采样点的个数。又因为产生矩阵PM时，1 2 12 , 2 , , 2Ts-= L，所以 计 算 矩 阵 PM 的 时 间 复 杂 度 为 ：( ) ( ) ( ) ( )1 2 1 22 2 2 2TT O N O N O N-+ + + = = L.由3.2节，在对这三个矩阵进行归一操作中，主要涉及的计算是尺度归一和轮廓线的起始点归一。对每个矩阵进行尺度归一的时间复杂度为( ) ( ) ( ) ( ) 1 log O T N O TN O N N - = =。而在进行起始点归一的过程中，因为要对矩阵的每一行进行快速傅里叶变换，而对每一行进行快速傅里叶变换的时间复杂度为( ) log O N N，所以对每个矩阵进行起始点 归 一 的 时 间 复 杂 度 为( ) ( ) ( ) ( )21 log log log O T N N O TN N O N N - = =。则计算CFM 描 述 子 的最 坏 时 间复 杂度 为( )22 2 log 3 log 3 log O WN N N N N N N + + +，该式化简后为( )22 log log O WN N N N N ++。这里变量W跟图像的大小有关，( ) OW是精确计算内外弦长的最坏情况下的时间复杂度，即通过检查弦上分布的每一个像素点是目标形状区域内的像素点，还是区域外的像素点，来计算内外弦长。 若近似计算内外弦长，可以将轮廓线的N个采样点用线段连成一个N条边的多边形（每条边连接相邻采样点），通过检查弦与多边形每条边的交点，计算内外弦长。该算法计算内外弦长的时间复杂度为( ) ON。此时，计算描述子CFM的算法复杂度为：( ) ( )( ) ( ) ( )2 2 2 2 22log log = log log= log + log = logO N N N N N O N N N NO N N N N O N N+ + +          我们以流行的内部距离上下文方法[10]作为基准方法来比较特征抽取阶段的算法时间复杂度。因该算法已实际应用于美国史密斯国家自然历史博物馆的计算机视觉辅助植物分类系统[42]。因要计算内部距离，该算法在特征抽取阶段的时间复杂度为( )3ON，这里N是轮廓线采样点的个数。显然，该算法的时间复杂度要高于本文提出的算法。   在形状匹配阶段，计算公式9的时间复杂度为( ) ( ) ( ) 3 1 log O M T O M N -=。因为M是在归一化操作中，保留的傅里叶变换系数的个数，且MNg。从以上分析可以看出，在形状匹配阶段，本文提出的方法有着非常低的计算时间复杂度。而内部距离上下文方法[10]由于要采用动态规划进行形状匹配，因此其时间复杂度为( )3ON。该复杂度要远高于本文提出的算法。 4  实验结果和讨论 为评估本文提出的弦特征矩阵描述方法（CFM）的性能，我们将其应用于植物叶片图像的分类和检索问题，这也是计算机视觉在植物分类学中的一个重要应用。植物叶片形状一般具有类内差异大，类间差异小的问题，使得其分类和识别具有一定的挑战性。三个被广泛用来评估植物叶片图像识别算法的图像库：Swedish 树叶图像库[11]、Flavia10  计  算  机  学  报  2016年  植物叶片图像库[24]、ImageCLEF 植物叶片图像库[25]，以及在这三个测试集上的通用的性能评估方法被用来检验CFM 的有效性。其中，Swedish一般被用来评估算法的分类性能，而Flavia 和ImageCLEF则一般被用来评估算法的检索性能，因此在这三个测试集上的评估方法不一样。在实验中，我们选取了那些在这三个测试集上报告了较高的分类精确率和检索结果的形状描述子作为比较对象。 本文提出的CFM方法的有关参数设定为：256 N=,10 M=。这两个参数是依据经验给定，叶片图像有很多细节信息，而且这些细节往往是区分不同类叶片的主要依据，因此采样点太少，将会丢掉这些信息，而采样点过多，又增加了计算的工作量，因此我们经验的取256 N=，可以使这两个方面达到较好的平衡。而对于参数M的取定，因为信号的能量主要集中在傅里叶变换的低频系数，保留太多的系数，在增加计算量的同时，对识别率的提高并没有显著的贡献，因此我们经验的取10 M=。 算法采用Matlab 编程实现，运行在一台CPU为Intel  i7-4770/3.4GHz，内存为12GB，操作系统为Windows 7 的个人计算机上。值得指出的是，本文的贡献主要是提出新的形状描述方法，所以在图像预处理方面，我们采用已有的技术手段。先将彩色图像变为灰度图像（用Matlab的rgb2gray函数完成），利用灰度图像的全局阈值将其变成二值图像（用Matlab的graythresh函数和im2bw函数完成）, 跟文献[10]一样，我们抽取的是二值图像中最长的轮廓线。在实验中我们用到的抽取叶片图像轮廓线的程序源代码，下载于文献[10]作者的网站。 4.1    Swedish树叶图像库  图6  Swedish树叶图像库中的15种树叶的样本  Swedish树叶图像库[11]是一个用来评估算法分类性能的著名测试集。该测试集有15 类Swedish树叶图像(见图6)，每一类有75个样本，共1125幅叶片图像。我们采用与文献[10, 11, 22, 32, 33，35，38]相同的性能评估方法：对每一类中的75个样本，随机的选取25个作为训练样本，其余的50个作为测试样本，采用最简单的1-NN分类器，算法运行10次，取其平均值作为算法的最终识别率。 表格1列出了本文提出的CFM方法，以及近些年来在该测试集上报告了较高识别率的其他几种形状描述方法的测试结果。对于方法MDM[4]，因其有20种推广形式（MDM、MDM-CD、MDM-ID和MDM-ID-CD共4类，每类各5种），在实验中我们对这20种推广形式都进行了运行，在表1中列出的是其结果最好的两种形式。图7则给出了本文提出的CMF方法的识别结果的示例。 表1  在Swedish树叶图像库的识别率(%)(*标记的数据引自对应的文献报告的结果) 算法  识别率 MARCH[23]  96.2 BCF[32]  96.6* Pattern Counting[33]  97.1* HATSI&RS[38]  96.5* IDSC[10]  94.1* MDM-RM[4]  92.3 MDM-RA [4]  94.0 MCLFD[12]  93.0 LPCM[41]  90.2 TSLA[22]  96.5* 本文提出的CFM方法  96.9  论文在线出版号  No.183        王斌等：弦特征矩阵:  一种有效的用于植物叶片图像分类和检索的形状描述子    11   图 7本文提出的CFM方法在Swedish测试集上的识别结果的示例，图中每一个大方格中的上方的左图为测试图像，右图为在库中找到的最佳匹配图像，下方的数值为它们的差异度（用公式9计算）  从表1列出的实验结果可以看出，本文提出的CFM方法取得了96.9%的识别率，仅比最近提出的Pattern  Counting[33]方法低0.2个百分点，而比其他方法高出0.3 到4.6 个百分点，跟MCLFD[12]、MDM[4]这两种同样采用与弦有关的特征的方法相比，则高出了超过2.9个百分点，显示了其更强的形状识别能力。值得指出的是，Pattern Counting[33]方法和BCF[32]方法一样都需要用专门的训练集学习生成码本(codebook)或词典(dictionary)，再用它们来生成形状描述子，如果训练集不存在，则形状描述子无法产生。而本文提出的CFM描述子是独立产生的，不依赖于任何训练集样本。 本文提出的CFM描述子是三个矩阵OM、IODM和PM的组合。为测试这三类特征在叶片图像识别中的作用效果，我们对这三个矩阵进行单独和两两组合使用的实验。单独使用的识别率为：OM=91.2,  IODM=91.3,  PM=94.1；两两组合使用的识别率为：OM+PM=95.8,  IODM+PM=94.7，OM+IODM=94.6；全部组合使用的识别率为OM+IODM+PM=96.9。从该组实验结果可以看出：OM、IODM 和PM都是具有鉴别力的形状特征（从单独使用的实验结果可以看出），而它们的两两或三个的组合都提升了形状识别率。反过来说，如果从CFM中去掉一个矩阵，若去掉的是OM，则识别率降低了2.2个百分点；若去掉的是IODM，则降低了1.1个百分点；而若去掉的是PM，则降低了2.3个百分点。因此，可以看出，CFM是由三个矩阵构成的一个有机的整体，其中的任一矩阵都在识别中扮演着重要的角色，它们的组合构成了一个具有强的识别能力的形状描述子。 在3.1节，我们指出了本文提出的CFM方法在尺度选择方面不同于文献[4]和文献[12]。前者采用的非均匀的尺度选择，而后者采用的是均匀的尺度选择。为了比较CFM在不同尺度选择方法上的性能差异，我们在Swedish测试集上，执行了另外两组实验。第一组实验是让CFM采用文献[4]的尺度选择方法，即让尺度取s=[1,2,3,…,128]，共128个尺度，另一组实验是让CFM采用文献[12]的尺度选择方法，即让尺度取s=[16,32,48,…,128]，共8个尺度。值得指出的是，它们都多于CFM的非均匀尺度选择方法所采用的7个尺度级。在第一组实验中，CFM取得了96.0%的识别率，要低于CFM采用非均匀尺度选择0.9个百分点。在第二组实验中，CFM取得了95.3%的识别率，低于非均匀尺度选择1.6个百分点。该实验结果说明，CFM方法采用非均匀尺度选择，用较少的尺度级，就取得了比均匀尺度选择方法更好的识别效果，从而在实验上验证了该尺度选择方法的有效性。 4.2    Flavia植物叶片图像库 Flavia植物叶片图像库[24]是另一个具有挑战性的测试集。该图像库常被用作测试算法的检索性能。它有32种植物叶片图像，共1907个样本。其中，每类样本数从50到70不等。图8为每类样本给出了一个示例。有许多方法[22,23,36]在该图像库进行了图像检索实验，并报告了检索结果。在性能评估方面，我们同这些方法一样，采用两种经典的检索性能评估指标：查准率/查全率曲线和平均精度均值(Mean Average Precision)，以便进行性能对比。这里查准率定义为：对于一个查询图像，返回的结果中与其相关的样本所占的比例；而查全率则是返回的结果中与之相关的图像占图像库中所有与之相关的图像的比例。若把查准率当成查全率的函数，即让查全率由0%变换到100%时，求出相应的准确率，由此生成一条查准率/查全率曲线，作为算法的性能评估指标。在实验中，1907个样本的每一个都用作检索图像，在图像库中进行检索实验，检12  计  算  机  学  报  2016年  索结果为1907次检索的平均。  图8  Flavia测试集中的32种植物的叶片图像样本  虽然查准率/查全率曲线是一种常用的图像检索性能评估指标，但查准率只考虑了返回结果中相关图像的个数，没有考虑图像之间的序关系。而对一个检索系统，返回的结果必然是有序的，且相关度越高的图像排名越靠前，表明算法的性能越好。因此，在实验中，我们同文献[22,23,36]一样，同时采用了另一种常用的检索性能评估指标—平均精度均值[43] (Mean Average Precision)，以弥补查准率/查全率曲线评估指标的局限性。给定一个检索图像Q，其平均精度AP定义为 ( )( ) ( ) ( )1Mkp k f kAP QN=´=å                      (10) 这里( ) pk是把返回的图像按跟检索图像Q的差异度由小到大排序形成的列表，截取前k个图像后，所计算得到的准确率。例如，假设截取的前k个图像中有r个图像与Q相关，则( ) p k r k =。而( ) fk的取值规则定义为：在返回列表中，排在第k个位置的图像如果与Q相关，则( ) 1 fk=，否则( ) 0 fk=。N是图像库中与Q相关的图像的个数。M是满足如下两个条件的正整数：  (1)在返回列表的前M个图像中，有N个与Q相关；(2)返回列表的第M个图像与Q相关。平均精度均值(Mean Average  Precision)则是所有检索图像的AP值的平均。 表2给出了各方法在Flavia 测试集上的检索结果。从该表可以看出，本文提出的CFM方法取得的76.2%的平均精度均值，跟参与比较的各方法的实验结果高出了4.0到24.3个百分点，也是目前在该测试集上报告的最好结果。图9则给出了表2列出的各方法在Flavia 测试集上的查准率/查全率曲线。从该图可以看出，本文提出的CFM方法，在各个召回率上的准确率都高于参与比较的各方法，表明了CFM方法的有效性。 表2  在Flavia植物叶片图像库的平均精度均值(%)(*标记的数据引自对应文献报告的结果) 算法  平均精度均值 TSLA[22]  69.9* MARCH[23]  72.2 IDSC[10]  59.9 MDM-RM[4]  59.1 MDM-RA [4]  58.5 MCLFD[12]  58.6 Riemannian metric[36]  57.2* LPCM[31]  51.9 本文提出的CFM方法  76.2  除了上述实验之外，我们还进行了另外一组实验，以将本文提出的方法与最近的一篇文献[39]提出的方法进行性能比较。该方法在Flavia 测试集的一个子集上进行了分类实验。该子集选取了Flavia图像库中的31类样本，每类选取了30个样本，构成了一个930幅图像的测试集。在每类样本中，取10幅图像作为训练样本，20幅图像作为测试样本。为便于比较，我们也在该测试集上进行了相同的实验。文献[39]报告的结果为：采用形状特征的识别率为50.16%，采用纹理特征的识别率为87.10%，采用形状特征和纹理特征的组合的识别率为97.60%。而本文提出的方法仅用形状特征就取得了93.27%的识别率。该结果显示了本文提出的形状描述子要远优于文献[39]所采用的形状特征。  图9  在Flavia植物叶片图像库上的查准率/查全率曲线 论文在线出版号  No.183        王斌等：弦特征矩阵:  一种有效的用于植物叶片图像分类和检索的形状描述子    13     为了比较CFM在不同尺度选择方法上的性能差异，同在Swedish测试集一样，我们在Flavia测试集上也执行了两组相同的实验。第一组实验是让CFM采用文献[4]的尺度选择方法，另一组实验是让CFM采用文献[12]的尺度选择方法。在第一组实验中，CFM取得了67.70%的识别率，要低于CFM采用非均匀尺度选择8.5个百分点。在第二组实验中，CFM取得了66.03%的识别率，低于非均匀尺度选择10.17个百分点。该实验结果进一步验证了，CFM方法采用非均匀尺度选择机制要好于均匀尺度选择方法。 4.3    ImageCLEF植物叶片图像库 实验中用到的第三个具有挑战性的测试集是著名的ImageCLEF 植物叶片图像库1。ImageCLEF有三个测试集，我们采用的是其中的“Scanned”测试集，该测试集中的叶片图像通过扫描生成。该测试集主要用作图像检索性能的评估。它由来自于115种植物的6630幅叶片图像组成。每类植物叶片的样本数从2到249不等。图10为每类样本给出了一个示例图像。该测试集中，1760幅图像被用作检索样本，其余的作为库存样本。  图10  ImageCLEF测试集中的115种植物的叶片图像样本 该测试集的设计者提出了一种不同于前述Precesion/Recall曲线和平均精度均值(MAP)的检索性能评估方法，这里我们称之为“S-Score”  指标。                                                                 1   ImageCLEF.  2012.  Plant  Identification  2012, http://imageclef.org/2012/plant. 它不是简单的对所有检索样本的检索精确率进行平均，而是分别对叶片图像的作者和叶片被采集的植物个体进行平均，以消除评估值对某位作者或某个植物个体的偏向性。“S-Score”  评估指标的定义如下： ,,,1 1 1,1 1 1up uN p Uu p nu p nu u pSSU p N = = == å å å                        (11) 这里U是用户数，即叶片图像作者人数，每位作者在图像库中至少有一幅作品。up是第u个用户所采集的植物个体数，, upN是第u个用户从第p个植物个体上采集的叶片样本数，,, u p nS的计算过程为：将第u个用户从第p个植物个体上采集的第n个样本作为检索样本与所有的库存样本进行比较，并按差异度由小到大排序，再由该排序列表得到类排序列表，其具体操作是按每类样本在排序列表中首次出现的序号进行类排序，每类在得到的类排序列表中占据一个位置）。设该检索样本所属的类在所得的类排序列表中的序号为T，则有,,1u p nST=。  从该公式可以看出，在计算过程中，分别按图像作者和植物个体进行了平均，防止某位作者的制作的样本多，或者从某个植物个体采集的样本多，而产生评估值的偏向性。 表3  在ImageCLEF植物叶片图像库的检索结果（S-Score测试）(*标记的数据引自对应文献报告的结果) Algothims  S-Score (%) TSLA[22]  53.0* MARCH[23]  56.7 IDSC[10]  47.9 MDM-RM[4]  54.5 MDM-RA [4]  55.8 MCLFD[12]  49.3 LPCM[31]  43.4 SABANCI OKAN RUN 1 [25]  58.0* 本文提出的CFM方法  61.2  表3列出了本文提出的CFM方法和其他参与比较的各方法在该测试集上的“S-Score”值。从该表可以看出，本文提出的CFM方法，比目前报告14  计  算  机  学  报  2016年  的最好结果58.0%（由方法SABANCI OKAN RUN 1[25]获得）高出了3.2个百分点。值得指出的是，该方法采用了叶片图像的纹理特征和形状特征，而本文提出的方法的获得的61.2%的检索精确率是在仅采用了形状特征的情况获得的。在与其它基于形状特征的植物叶片图像检索方法[4,10,12,22,23,31]的性能比较中，本文提出的方法则高出了超过4.5个百分点。该组实验进一步证明了CFM 方法在植物叶片图像检索应用中的优越性能。 4.4 噪声干扰测试  图11 从左至右:原图像、加入了噪声强度D分别为10%，15%，20%的三幅叶片图像 本组实验用来评估本文提出的算法对噪声干扰的稳定性。实验方案类似于文献[44]所采用的方案。对于Swedish测试集中的每一幅黑白图像，分别加入强度D分别为10%、15%和20%的椒盐噪声。这里百分比表示像素点变反(0变为1，或1变为0)的比例。图11 给出了原图像和加入了不同强度椒盐噪声的样本图像的示例。由此得到三个加入了不同强度噪声的测试集。在这三个测试集上，按4.1中的实验方案，进行叶片的分类测试。 表4给出了本文提出的方法CFM和其他两种方法IDSC[10]和MARCH[22]在这三个噪声测试集和在原测试集上的识别率的对比。从该表可以看出，对于10%的噪声强度，CFM的识别率降低了2.5个百分点，MARCH方法降低了3.4个百分点，而IDSC则下降了21.7个百分点。而当噪声强度增加到20%时，CFM的识别率下降了6.7个百分点，但识别率仍然超过了90%，MARCH方法则下降了8.1个百分点，识别率已降到90%一下，而IDSC 的识别率仅41.6%，已不能正常工作。该组实验的结果验证了本文提出CFM方法对噪声干扰的鲁棒性。 表4在Swedish树叶图像库中，加入了不同强度噪声干扰下的识别率 Algothims  D=0%  D=10%  D=15%  D=20% IDSC[10]  94.1  72.4  53.3  41.6 MARCH[23]  96.2  92.8  90.9  88.1 本文提出的  CFM方法  96.9  94.4  92.5  90.2 4.5   一般的应用测试 为测试本文提出的CFM方法应用于一般形状的识别能力，我们采用与文献[33]相同的实验方法，用MPEG-7形状测试集评估算法的通用性。该测试集有70类形状图像，每一类有20个样本，共1400副黑白图像，图12给出了70类形状的样本示例。  图12 MPEG-7图像库的70类形状样本示例 为便于与文献[33]提出的方法(Pattern Counting)比较，实验中采用了与之相同的性能评估指标。将每一个形状图像作为测试样本与图像库中所有其他的样本进行比较，在前K个最佳匹配（形状差异最小）样本中，若至少存在一个样本与测试样本同类，则视为一次成功识别，统计1400次测试的识别成功率作为对应于参数Ｋ的识别率P，让Ｋ从1取到10,将得到的识别率P绘成曲线，显然，识别率随着K递增，且当K=1时，对应的值即为1-NN识别率。图13 给出了CFM和其他三种方法IDSC[10]、MARCH[23]和Pattern Counting[33]的识别率曲线。这里，Pattern Counting方法的实验结果直接取自文献[33]，IDSC 的实验结果为运行文献[10]的作者网站提供的程序源代码所获得。从该图可以看出，在各个K的取值，本文提出的方法CFM的识别率P都要好于参与比较的其他三种方法。该结果验证了CFM方法能有效的应用于一般形状的识别。  图13 在MEPG-7形状测试集上的识别率，横轴K是返回的论文在线出版号  No.183        王斌等：弦特征矩阵:  一种有效的用于植物叶片图像分类和检索的形状描述子    15  最佳匹配的样本数，纵轴P是识别率 5  结论 本文提出了一种新的形状描述子–弦特征矩阵（CFM），并有效的应用于植物叶片图像的分类和检索问题。该方法通过抽取轮廓线的多个尺度下的弦的内弦长(与轮廓线的凸性关联)和外弦长(与轮廓线的凹性关联)来构造两个矩阵，以反应轮廓线形状的凸凹特性，而用弧到弦的平均投影长度，构造矩阵以描述轮廓线的弯曲程度。由这三个矩阵构成的形状描述子具有强的形状辨识能力。在应用于三个具有挑战性的植物叶片图像测试集中，CFM的识别率高出参与比较的各同类方法0.4到24.5个百分点。将其跟两种基于学习机制的描述子产生方法BCF[32]和Pattern Counting[33]相比，在Swedish测试集上，识别率高于前者0.3个百分点，而低于后者也仅0.2个百分点。这些实验结果证明了本文提出的CFM方法的有效性。CFM方法不仅具有强的形状识别能力，还对噪声的干扰具有一定的鲁棒性，专门的噪声干扰测试的实验结果验证了这一特性。CFM方法不仅能有效的应用于植物叶片图像的识别问题，而且还能应用于一般的形状识别任务，在MPEG-7形状测试上的实验结果验证了其一般应用能力。CFM方法计算简单，算法涉及的参数少（仅两个参数），使得算法容易使用。 另外，对于本文提出的CFM方法，有几个问题值得一步研究：(1)为对轮廓线的起始点进行归一，采用傅里叶变换去掉变换系数的相位信息的办法，会造成一些有价值的形状信息的损失。研究采用其他的起始点归一方法，是有待进一步研究的问题；（2）CFM方法将三个矩阵通过傅里叶变换从空间域变换到频率域，用L1距离的形状匹配方法，是一种全局匹配方法，虽然在形状匹配阶段有非常快的匹配速度，但在处理形状发生严重的遮挡时，有着较大的局限性。但CFM是一种分层的描述框架，其小尺度特征有着良好的局部特性，可以考虑在空间域，采用点到点的局部匹配方法，来解决形状的严重的遮挡问题，因此研究基于CFM的局部匹配方法将是下一步拟开展的研究工作；（3）本文研究的是基于形状特征的叶片图像识别，但存在有一些不同类的植物叶片，在形状特征上具有高度的相似性（见图10），考虑到它们的纹理特征具有很大的不同，我们将研究在基于CFM的描述框架下，抽取叶片图像的灰度特征和形状特征组合在一起完成更为精确的分类和检索任务。 参 考 文 献 [1] Loncaric S. A survey of shape analysis techniques. Pattern Recognition, 1998, 31(8): 983-1001 [2]  Zhang  D. Review  of  shape  representation  and  description  techniques. Pattern Recognition, 2004, 37(1): 1-19  [3] Chen Y W, Chen Y Q. Invariant descriptor and retrieval of planar shapes using  radon  composite  features.  IEEE  Transactions  on  Signal Processing, 2008, 56(10): 4762-4771  [4] Hu  R  X, Jia  W,  Ling  H,  Huang  D. Multiscale  Distance  Matrix  for  fast plant  leaf  recognition.  IEEE  Transactions  on Image  Processing,  2012, 21(11): 4667-4672  [5]  Alajlan  N,  Rube  I  E,  Kamel  M  S,  Freeman  G.  Shape  retrieval  using triangle-area  representation  and  dynamic  space  warping.  Pattern Recognition, 2007, 40(7): 1911-1920. [6]  Xu  C,  Liu  J,  Tang  X.  2D  shape  matching  by  contour  flexibility.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009, 31(1): 180-186.  [7]  Li  J,  Narayanan  R  M.  A  shape-based  approach  to  change  detection  of lakes  using  time  series  remote  sensing  images.  IEEE  Transactions  on Geoscience and Remote Sensing, 2003, 41(11): 2466-2477.  [8]  Wang  J,  Bai  X,  You  X,  Liu  W,  Latecki  L  J.  Shape  matching  and classification using height functions. Pattern Recognition Letters, 2012, 33(2): 134-143.  [9]  Liu  H, Latecki  L  J,  Liu  W.  A  unified  curvature  definition  for  regular, polygonal, and digital planar curves. International Journal of Computer Vision, 2008, 80(1): 104-124. [10]  Ling  H,  Jacobs  D  W.  Shape  classification  using  the  inner-distance. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007, 29(2): 286-299.   [11]  Söderkvist  O.  Computer  vision  classification  of  leaves  from  swedish trees. Master's thesis, Linköpint University, 2001  [12] Wang B. A Fourier shape descriptor based on multi-level chord length function. Chinese Journal of Computers, 2010, 33(12): 2387-2396.   (王斌.  一种基于多级弦长函数的傅里叶形状描述子.  计算机学报, 2010, 33: 2387-2396)    [13] Belongie S, Malik J, Puzicha J. Shape matching and object recognition using shape  contexts.  IEEE  Transactions  on Pattern  Analysis  and Machine Intelligence, 2002, 24(4): 509-522.  [14]  Adamek  T,  O'Connor  N  E.  A  Multiscale  representation  mehtod  for nonrigid  shapes  with  a  single  closed  contour.  IEEE  Transactions  on Circuits and Systems for Video Technology, 2004, 14(5): 742-753.  [15] Korn P, Sidiropoulos N, Faloutsos C, Siegel E, Protopapas Z. Fast and effective retrieval  of  medical  tumor  shapes.  IEEE  Transactions  on Knowledge and Data Engineering, 1998, 10(6): 889-904.  [16]  Milios  E,  Petrakis  E.G.M.  Shape  retrieval  based  on  dynamic 16  计  算  机  学  报  2016年  programming.  IEEE  Transactions on  Image  Processing,  2000,  9(1): 141-147.  [17]  Wang  Z,  Chi  Z,  Feng  D.  Shape  based  leaf  image  retrieval.  IEE Proceedings-Vision, Image and Signal Processing, 2003, 150(1): 34-43.  [18]  Mokhtarian  F,  Mackworth  A.  A  theory  of  multi-scale  curvature-based shape representation  for  planar  curves. IEEE  Transactions  on Pattern Analysis and Machine Intelligence, 1992, 14(8): 789-805.  [19]  Mokhtarian  F,  Bober M.  Curvature  scale space  representation:  theory, applications, and MPEG-7 standardization. Norwell, MA, USA: Kluwer Academic Publishers, 2003. [20]  EI-ghazal  A,  Basir  O,  Belkasim  S.  Invariant  curvature-based  Fourier shape  descriptors.  Journal  of  Visual  Communication  and  Image Representation, 2012, 23(4): 622-633. [21]  Manay  S,  Cremers  D,  Hong  BW,  Yezzi  AJ  Jr,  Soatto  S.  Integral invariants  for  shape  matching. IEEE  Transactions  on Pattern  Analysis and Machine Intelligence, 2006, 28(10): 1602-1618.  [22] Mouine S, Yahiaoui I, Verroust-Blondet A. A shape-based approach for leaf  classification  using  multiscale  triangular  representation// Proceedings  of  the  3rd  ACM  International  Conference  on  Multimedia Retrieval. Dallas, Texas, US, 2013: 127-134. [23] Wang B, Brown D, Gao Y, Salle J L. MARCH: Multiscale-arch-height description  for  mobile  retrieval  of  leaf  images.  Information  Sciences, 2015, 302(5): 132-148. [24]  Wu  S,  Bao  F,  Xu  E,  Wang  Y,  Chang  Y,  Xiang  Q,  A  Leaf  recognition algorithm  for  plant  classification  using  probabilistic  neural  network. Proceedings of the IEEE International Symposium on Signal Processing and Information Technology. Cairo, Egypt, 2007: 11-16. [25]  Yanikoglu  B  A,  Aptoula  E,  Tirkaz  C.  Sabanci-Okan  System  at ImageClef  2012:  Combining  Features  and  Classifiers  for  Plant Identification.  Proceedings  of  the  CLEF  (Online  Working Notes/Labs/Workshop). Rome, Italy, 2012: 1-13. [26] Yang Y.-F, Zhang D.-C, Han M. A shape matching method using spatial features  of  multi-scaled  contours.  ACTA  Automatica  Sinica,  2015, 41(8): 1405-1411.         (杨亚飞，郑丹晨，韩敏.  一种基于多尺度轮廓点空间关系特征的形状匹配方法.  自动化学报, 2012, 41(8): 1405-1411) [27] Arica N, Vural F. Bas: a perceptual shape descriptor based on the beam angle statistics. Pattern Recognition Letters, 2003, 24(9-10): 1627-1639.  [28]  Hu  R  X,  Jia  W,  Ling  H,  Zhao  Y,  Cui  J.  Angular  pattern  and  binary angular  pattern  for  shape  retrieval.  IEEE  Transactions  on  Image Processing, 2014, 23(3): 1118-1127. [29] EI-ghazal A, Basir O, Belkasim S. Fathest point distance: a new shape signature  for  Fourier  descriptors.  Signal  Processing:  Image Communication, 2009, 24(7): 572-586. [30] Han M, Zheng D.-C. Shape recognition based on fuzzy shape context. ACTA Automatica Sinica, 2012, 38(1): 68-75.         (韩敏，郑丹晨.  基于模糊形状上下文特征的形状识别算法.  自动化学报, 2012, 38: 68-75) [31]  Song  R.-X,  Li  C.-H,  Wang  Y.-N,  Xu  Y.-Q,  Qi  D.X.  Shape  feature description based  on  log-polar  coordinates  and  symmetric  circulant matrix. Science China Mathematics, 2014, 44(7): 815-822.     (宋瑞霞，李成华，王也娜，徐燕青，齐东旭.  基于对数极坐标及对称循环矩阵的形状特征描述.  中国科学：数学, 2014, 44(7): 815-822)    [32] Wang X, Feng B, Bai X, Liu W, Latecki L J. Bag of contour fragments for  robust  shape  classification.  Pattern  Recognition,  2014,  47(6): 2116-2125. [33] Zhao C, Chan S.S.F., Cham W.-K, Chu L.M. Plant identification using leaf shapes-A  pattern  counting  approach.  Pattern  Recognition,  2015, 48(10): 3203-3215. [34]  Wright  J,  Ma  Y,  Mairal  J,  Sapiro  G,  Huang  T  S,  Yan  S.  Sparse representation for computer vision and pattern recognition. Proceedings of the IEEE, 2010, 98(6): 1031-1044. [35] Felzenszwalb P F, Schwartz J D. Hierarchical matching of deformable shapes. Proceedings  of the IEEE  Conference  on  Computer  Vision  and Pattern Recognition. Minneapolis, Minnesota, USA, 2007: 1-8. [36]  Laga  H,  Kurtek  S,  Srivastava  A,  Golzarian  M,  Miklavcic  S.  A Riemannian  Elastic  Metric  for  Shape-based  Plant  Leaf  Classification. Proceedings  of  the  International  Conference  on  Digital  Image Computing:  Techniques  and  Applications  (DICTA).  Fremantel, Australia, 2012: 1-7. [37]  Novotný  P,  Suk  T.  Leaf  recognition  of  woody  species  in  Central Europe. Biosystems Engineering, 2013, 115(4): 444-452. [38] Horaisová  K,  Kukral  J.  Leaf  classification  from  binary  image  via artificial intelligence. Biosystems Engineering, 2016, 142(2): 83-100. [39] Chaki  J,  Parekh  R,  Bhattacharya  S.  Plant  leaf  identification  using texture  and  shape  features  with  neural  classifiers.  Pattern  Recognition Letters, 2015, 58(1): 61-68. [40] Cope J.S, Corney D, Clark J.Y., Remagnino P, Wilkin P. Plant species identification  using  digital  morphometrics:  A  review.  Expert  Systems with Applications, 2012, 39(8): 7562-7573. [41] Zhou Y, Liu J.-T, Bai X. Research and perspective on shape matching. ACTA Automatica Sinica, 2012, 38(6): 889-910       (周瑜，刘俊涛，白翔.  形状匹配方法研究与展望.  自动化学报, 2012, 38: 889--910) [42] Belhumeur P, Chen D, Feiner S, Jacobs D, Kress W, Ling H, Lopez I, Ramamoorthi R,  Sheorey S,  White S,  Zhang  L. Searching the world’s herbaria:  A  system  for  visual  identification  of  plant  species.   Proceedings of the European Conference on Computer Vision (ECCV). Marseille, France, 2008: 116–129. [43] Manning  Ch  D,  Raghavan  P, Schütze  H.  Introduction  to  information retrieval. Cambridge: Cambridge University Press, 2008. [44]  Kadyrov  A, Petrou M.  The trace transform  and its applications. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2001, 23(8): 811-828.      论文在线出版号  No.183        王斌等：弦特征矩阵:  一种有效的用于植物叶片图像分类和检索的形状描述子    17   Wang Bin, born in 1969, Ph.D., Professor，Master Supervisor, Senior  Member  of  China  Computer Federation. His  research  interests  include pattern  recognition,  computer  vision  and image  processing. Chen  Liang-Xiao,  born  in  1992,  Master  candidate.  Her research  interests  include  computer  vision  and  image processing. Ye  Meng-Jie,  born  in  1989,  Master  candidate.  Her  research interests include computer vision and image processing.    Background Object  recognition  is  the  ultimate  goal  for  many image  analysis  and  computer  vision  applications. Among  many cues  such  as  color,  texture,  motion, context  and  function  provided  by  the  object,  shape  is known to be perhaps the most common and dominant. However, how to extract the useful shape features for effective  and  efficient  object  classification  and retrieval  is  a  challenging  problem.  As  a  significant application of computer vision, leaf image based plant identification  has  attracted  more  and  more  attentions of the researchers due to its following challenge: there are  about  400,000  species  plants  all  over  the  world and  the  leaf  images  usually  have  large  intra-class variants  and  small  inter-class  differences  which  make the leaf identification become a difficult task.           The features of the leaf contour provides important cues for effective leaf image identification. Motivated by the correlations of the chords of the leaf contour to its convex and concave properties, we propose a novel shape  description  method  termed  Chord-Features Matrices  for  leaf  image  classification  and  retrieval  in this  paper.  Different  from  those  methods  which present explicit description of the convex and concave properties,  our  method  implicitly  characterize  these properties  using  the  inner  parts  and  outer  parts  of  the chord  relative  to  the  region  enclosed  by  the  contour. In  addition  to  these  features,  the  projections  length from  the  arc  to  the  chord  is  incorporated  into  the descriptors  for  reflecting  the  bending  degree  of  the contour.  The  proposed  Chord-features  matrices provide powerful discriminative ability for leaf image identification and  its  effectiveness  has  been  validated on three well-known plant leaf image databases.        This  work  is  supported  by  National  Natural Science  Foundation  of  China  (Grant  No.  61372158). Our  research  group  has  been  studying  on  pattern recognition,  image  analysis,  shape  based  object classification  and  retrieval  for  a  long  time.  In  these fields, our works has been published many conference papers  and  Journals.  In  recent  years,  we  proposed  a particle  swarm  optimization  algorithm  for  solving polygonal approximation of digital curve, an invariant shape  description  termed  hierarchical  string  cuts  for fast  shape  retrieval,  a  novel  shape  descriptors  termed multiscale arch height (MARCH) for mobile retrieval of  leaf  images,  and  novel  Fourier  descriptors  based multilevel  chord  function.  These  works  have  been published in IEEE Transactions on Image Processing, Information  Sciences,  and  Chinese  Journal  of Computers, respectively.