资源描述
.西北大学研究生数学建模竞赛承诺书我们仔细阅读了西北大学数学建模竞赛的竞赛规则与赛场纪律。我们完全明白，在竞赛开场后参赛队员不能以任何方式包括、电子、网上咨询等与队外的任何人研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料包括网上查到的资料，必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛的题目是(从A/B中选择一项填写)：C参赛队为：1069705所属院系请填写完整的全名：数学学院、信息科学与技术学院参赛队员 (打印并签名) : 1.耿妍2.朱锐3.卫柄岐 日期：2015 年5月3日评阅由校组委会评阅前进展：西北大学数学建模竞赛专用页评阅(由校组委会评阅前进展):评阅记录:评阅人评分备注评奖结果:. .世界上没有两片一样的叶子摘要本文通过分析叶子图片，建立了形状、边缘、颜色特征的数学模型，使得任意给出测试的叶子图片，我们能判断出它为*种树叶的概率，对于大量的树叶样本图片我们可以根据特征的相似性大小进展分类。在问题一中，我们给形状、边缘、颜色特征分别建立数学模型并将这些特征数字化。对于形状我们又将其细分为外表积、矩形度、伸长度，但是观察所给的数据叶片有可能发生旋转、平移、伸缩，为了克制这些外在因素造成的误差，我们添加不变特征，这样我们的特征描述就比拟细致。对于边缘这一特征，由于叶子边缘函数没有规性，而且在二维上表示，这样对我们的研究带来很大困难，所以我们通过傅里叶描述子将二维图像通过复坐标的形式降到一维，从而简化了问题。对于颜色这一特征，我们将用颜色矩来表示。与颜色直方图相比，该方法的另一个好处在于无需对特征进展向量化。在问题二中，通过分析有关叶子的形状，边缘，颜色的数据可以得出叶子的形态学数据是服从正态分布的，因此我们可以算出叶子的每个形态学数据样本的均值和方差，即可得到样本每一个形态学数据的高斯分布图，但比拟两种叶子的同一个形态学数据的时候在一个图像中却显示了两个正态分布的图像。所以综合多种特点，我们选择用贝叶斯分类器对给出的测试叶子计算为*种叶片的概率。在问题三中，我们将叶片的相似性转化为数学语言，即距离。把每个样品看做一个点，将它们对应的特征值为点的值，通过欧几里得距离的大小来判断叶片的相似性。在这一问中我们分别考虑了独立形状、边缘、颜色和综合考虑这些特征，得出了特征越多，分化越细。并且在这一问中我们通过谱系图的建立使得分类结果更清晰。关键词 不变矩阵法，贝叶斯算法，聚类分析. .一、问题描述1、通过对所给的二百二十组叶子图片的观察，发现形状，边缘，颜色是区分不同种类叶子的最显著特征，所以我们的目的就是将叶子的形状，边缘，颜色特征通过函数数字化，从而定量的分析了不同种类叶子的特征是不同的。2、同一类植物的两片叶子特征经过同一个函数计算，其值不可能完全一样，所以我们需要根据问题一的模型算出给出的测试叶子有可能是那种植物，它的概率有多大。3、对于任意给出的大量叶片，根据叶子特征的相似性，将这些叶子进展归类。二、问题分析问题一：题目中给出的只有叶子的图片，我们只能通过肉眼看出它的形状、颜色、边缘。要求出数学模型，将图片数字化就需要知道图片在计算机中的存储方式。它是被分成像素，用每个像素的灰度值去存储。这样一来我们就可以将图片用离散的点来表示。从而构建了它们的特征模型。问题二：要想知道所给叶子是什么叶子，就要综合考虑它们的特征，但是叶片的三个特征是相互独立的。如何能综合多个特征求概率就是我们要解决的。问题三：叶子的相似性就是由他们的特征所决定，这在问题一将被解决。根据这些特征将叶子进展分类，所以选取那种分类方法就是本问题的关键。三、根本假设1、叶片没有残损卷曲2、不考虑纹理特征四、符号说明符号意义每个像素点的灰度值灰度化后的二值矩阵叶子高度叶子宽度叶子外表积矩形度伸长度不变特征一阶矩平均值颜色二阶矩标准方差三阶矩三次根非对称性图像第个颜色通道分量中灰度级为的像素出现的概率边缘复坐标五、模型的建立与求解5.1问题一：5.1.1形状模型建立与求解：图像在计算机里被分成像素，每个像素的灰度值被整数化。为了防止图片平移，旋转，缩放带来的误差，我们首先将图片归一化，使之变为具有固定标准形式。不考虑图片颜色我们将在形状方面忽略颜色的影响，即将其灰度化，设灰度化后的图像二值矩阵为。我们将形状分为了十个特征来描述:外表积、矩形度、伸长度以及不变矩阵的七个不变特征。对于不变矩阵的七个不变特征，我们选择用二阶和三阶中心距来构造，因为这样能使它们在连续图像变换下可以保持平移、缩放、旋转不变。形状模型如下:，；归一化的中心距离定义为：，其中七个不变矩为形状模型仿真：首先，我们任意选出一种叶子图片，图(5-1)是附件中135号样品图片的一个代表;图(5-2)是附件中153号样品图片(5-1) (5-2)通过对叶子模型的运行，我们得到了每片叶子的十个特征值，由于空间有限，我们只列出前十个数据。其中行为叶片特征，列为叶片序号。如图，(5-3)是样品135的特征值；(5-4)是样品153的特征值叶片的形状特征图(5-3)(样品135)叶片的形状特征图(5-4)(样品153)5.1.2边缘模型的建立对于这一特征，由于叶子边缘函数没有规性，并且在二维上，这样对我们的研究带来很大困难，所以我们选择用傅里叶描述子把二维图像轮廓简化成一维问题进展处理。傅立叶描述子的根本思想是对图像边界进展傅立叶变换作为形状描述。首先假定物体的边缘表示为一个坐标序列,其中。用复数来表示每一个坐标，即，对于封闭边界，这一序列是周期的，为N，这样二维坐标下的边界就可以在一维空间上表示。尽管对序列进展了重新解释，但边界本身的性质并未改变。当然，这种表示方法的一个优点就是：把二维问题简化为一维问题。的离散傅立叶变换DFT表示为：(1)复系数叫做边界的傅立叶描述符.这些系数的反向傅立叶变换存在于： (2)傅立叶变换的高频分量对应细节而低频分量对应总体形状，在图像检索和图像识别中使用傅立叶描述子时，为了减少使用描述子进展图像相似度判别时的计算量，可以只用一局部对应低频分量的傅立叶系数来近似描述边界形状。边缘模型仿真：同样对样品135和样品153进展分析，表中的横坐标表示边缘的周长、面积、周长面积比、圆形度、方形度、比照度。纵坐标为前十个图片的序号。其中(5-5)是样品135对应的局部边缘特征；(5-6)是样品153对应的局部边缘特征。 叶片的边缘特征图(5-5)(样品135)叶片的边缘特征图(5-6) (样品153)5.1.3颜色模型建立：对于这一特征，我们将用颜色矩来表示。与颜色直方图相比，该方法的另一个好处在于无需对特征进展向量化。因此，图像的颜色矩一共只需要9个分量3个颜色分量，每个分量上3个低阶矩，仅采用颜色的一阶矩，二阶矩，和三阶矩就足以表达图像的颜色分布。一阶中心矩，二阶中心矩和三阶中心矩分别表示图像或子区域图像的平均颜色，标准方差和三次根非对称性。三个颜色矩的数学定义：(1)(2)(3)由于每个像素具有颜色空间的三个颜色通道，因此图像的颜色矩由9个分量来描述：颜色模型仿真：对样品135和样品153通过模型求解得到了其对应的局部图(5-7)、(5-8)。图中的横坐标表示图像颜色矩的九个分量。叶片的颜色特征图(5-7)(样品135)叶片的颜色特征图(5-8)(样品153)5.2问题二5.2.1模型建立与求解通过特征提取得到有关叶子的形状，边缘，颜色的数据。以下我们就以样品135的矩形度为例,通过矩形度生成分布图可以发现叶子的形态学数据是服从正态分布的，因此我们可以计算出叶子的每个形态学数据样本的均值和方差，即可得到样本每一个形态学数据的高斯分布图。叶子矩形度数据生成的分布图(5-9)(样品135)通过上面的图可以看出，叶子形态学的数据成正太分布，正好符合贝叶斯分类的先决条件。因此，我们可以利用贝叶斯来进展叶子的分类。贝叶斯原理： 贝叶斯公式： 代表类别，代表特征，我们做出预测肯定是利用当前的特征，来判断输出的类别。 我们可以看到贝叶斯公式先验与后验概率之间的转换，很明显，在我们的定义里面是后验概率，也是我们想要得到的东西。而我们先验概率,以及条件概率。对于多类的分类来说，都是一样，所以此项可以略去。那最终的结果就是计算这一项，是可以通过观察来解决的,我们有三类种子可以通过观察知道。上面对于此项的解释是在类中，特征出现的概率，其实简单来讲，就是的概率密度。 这样通过先验概率到后验概率的转换即可进展分类。形态学通过贝叶斯分类这里是针对叶子数据中的一个形态学数据进展的分析，当比拟两种叶子的同一个形态学数据的时候通过计算类条件概率曲线，可以分辨出该特征分类是否明显。如下：是颜色矩形成的类条件概率。我们是通过对样品135和样品153进展实验。如图是样品135和样品153的颜色矩特征的分析颜色特征类条件概率密度曲线(5-10)(样品135和样品153)从上图可以看出产生的有关颜色矩特征的概率密度曲线的阈值可以很容易的分开两类叶子。因此，颜色特征是对样品135和样品153分类的重要依据。通过计算形成颜色特征后验概率密度曲线。颜色特征类后验概率曲线(5-11)(样品135和样品153)通过后验概率曲线图也很容易看出两类通过颜色分类很容易。实验结果：选取一类似135类中的叶子，通过计算判定是135类的概率是0.8234。是153类叶子的概率为0.1766。通过比拟可以说明利用颜色特征，并且利用贝叶斯分类器分类效果显著。为了增加实验的可靠性，我们有利用边缘特征和形状特征类进一步分析验证。下列图是图片样品135和样品153边缘特征形成的类条件概率。边缘特征类条件概率密度曲线(5-12) (样品135和样品153)从上图可以看出产生的有关边缘特征的概率密度曲线有重叠局部，不过影响不是很大。因此，边缘特征也是样本135与153类叶子分类的重要依据。后验概率图为：边缘特征后验概率曲线(5-13)(样本135和 样本153)我们通过边缘特征的分类，通过给定图片进展测试，分别为135类叶子的概率为0.8763，为153类叶子的概率为0.1237。再通过形状的特征进展分类实验，获得类条件概率如下列图：形状特征类条件概率密度曲线(5-14)(样本135 样本153)我们通过形状特征的周长进展分类，可以看出分类结果不是很明显，所以必须综合三个特征进展分类。获得后验概率如下列图：形状特征后验概率曲线(5-15)(样本135 样本153)通过上图的分析，形状特征对135类和153类的叶子分类效果不是很好，因此需要综合三个特征进展分类。通过给定测试图片，分别为135类叶子的概率为0.6088，为153类叶子的概率为0.3912。三个特征综合进展分类: 为什么利用贝叶斯公式就可以做到区别类别的效果呢？在这里，先引入一个分布函数高斯分布 公式： 利用一维数据生成三个均值不同，标准差也不一样的高斯函数 利用高斯密度函数的优点：通过我们计算，每一类的均值和方差差距大。三个特征是相互独立的，我们通过高斯函数拟合，利用贝叶斯分类器进展分类。 通过三个特征综合产生如下结果三个特征类条件概率密度曲线(5-16)(样本135 样本153) 从上图可以看出分类界限更加明显，利用三个特征的相互独立，并且通过高斯函数的拟合，更加准确的完成了分类。总特征的后验概率图为：三个特征后验概率曲线(5-17)(样本135 样本153)通过给定测试图片，分别为135类叶子的概率为0.998，为153类叶子的概率为0.002。5.3问题三5.3.1模型建立与求解通过对叶子的特征提取，我们得到了叶子有关形状，边缘，颜色的特性，这些特征值从其所属的角度反映了叶子的特征，对于分析的叶子样本，其对应的叶子的特征与样本之间是存在关系的，我们可以利用谱系分析的方法来对叶子进展聚类分析，即用叶子不同的特征对叶子进展分类，这里使用谱系分析中的欧式距离法对其进展距离的计算，运用最短距离法对叶子进展聚类处理。我们通过构建进化树来对叶子进展谱系分析。叶子的种类是由多个特征共同决定，所以我们将运用欧式距离法进展距离的计算运用最短距离法来构建进化树。谱系分析的过程大致分成四步：由于指标变量相差比拟大，所以要对数据预处理标准化初始数据的矩阵中数值的大小不一，距离法计算的是两两样本之间的欧式距离，其中*一个距离相比拟其他距离如果过大，或者*一个距离相比拟其他距离过小都会影响聚类的结果，即会犯大数吃小数的毛病。所以对矩阵的预处理标准化就显得尤为重要，以下是矩阵标准化的过程：为了使抽样样本改变时它仍能保持相对的稳定，我们使用标准化变化：实行此变换后，数据均值为，标准差为，消去了量纲的影响。我们选取了叶子样本中的135样本和153样本对其进展了数据的归一化处理，我们在样本135中选取了10个样本，依次为1-10，在样本153中选取了10个样本，为11-20，对数据统一的进展了归一化处理处理后的结果如下列图: 归一化处理后的叶子边缘特征矩阵(5-18)(样品135和样品153)构造关系矩阵这一步中我们要测量样本之间的相似程度，即用欧式距离来表示它们之间的亲疏程度，样本之间的特征值越相近他们之间的欧式距离就越小，欧式距离从*些方面反映了两个样本之间的关系，即相似的样本之间的距离较小，而相异的样本之间的距离较大。首先每个样品有个指标从不同方面描述其性质，形成一个维的向量。如果把个样品看成维空间中的个点，则两个样品间的相似程度就可以用维空间的两点距离公式来度量。由于在分类之前我们已经做了标准化处理，所以本文中我们定义的距离公式为：欧几里德距离Euclidean distance(euclidean)Euclidean distance在中使用的是函数，函数实现了样本之间的计算 计算中各行向量的相互距离(是一个行列的矩阵)。这里要特别注意，是一个长为的行向量。可以这样理解矩阵的生成：首先生成一个的距离方阵，由于该方阵是对称的，且对角线上的元素都为，所以取此方阵的下三角元素，按照中矩阵的按列存储的原则，此下三角各元素的引索排列即为、.、。如果使其转化为矩阵形式输出如果使其转化为矩阵形式输出则可以用命令将此行向量转换为原距离方阵.这里选取了样本135和样本153的边缘特征数据进展了处理，样本1-10是样本135的而样本11-20是样本153的数据，它们之间的距离矩阵如下列图所示：叶子边缘特征的距离方阵(5-19)(样品135和样品153)聚类根据系统聚类法进展分类上一步中确定了距离矩阵后就可以对已有的样本进展聚类了，距离相近的样本就先聚合成一类，距离相远的就后聚成一类，过程一直进展下去，每个样品总能聚到适宜的类中，在每次聚类过程中都是以距离远近做为标准。在此过程中我们定义类与之间的距离为两类最近样品的距离：在矩阵中寻找距离最近的样本，使其进展聚类，并且紧接着生成新的类。当类与合并为一个新类记为，则任一类的距离为此时矩阵中的样本数变少了，减少的样本数为参与聚合的样本数减去生成样本数，每次产生聚类的过程中都会使的矩阵维数减小。通俗点说，即距离最小的事物首先消亡了完成聚类，产生新类，但是在他们消亡的过程中还保存了他们与其他外物之间的关系。每次聚类完成后关系矩阵维数都会相应的减小，直至关系矩阵变为的矩阵时即完成了样本的聚类。 在中运用函数对矩阵进展聚类，使用最短距离法“对之前产生的向量进展数据处理叶子边缘特征的生成树(5-20)(样品135和样品153)从上图可以看出产生的有关叶片的边缘聚类效果还是很可观的2个样本大致聚类成了两类，也就是叶子样本135类和叶子样本153类。样本3，4，5，6，7，8，9，10首先聚成了一类而样本11，13，14，15，16，17，18，19，20也优先的聚成了一类。但是样本1和样本12的聚类效果不是很好，原因是样本1和样本12有关于边缘的数据是异常的数据，即样本1和样本12是正态分布中的出现概率较小的数据，而最短距离法聚类本身也存在一些问题，即把样本之间的不同属性都同等对待，这使得其在实际中存在着误差，虽然对初始矩阵也就是样本属性矩阵进展了预处理，但是这样的误差依然不能防止的还有一个重要的原因是因为我们只选取了叶子的边缘特征，这并不能完全描绘叶子的形态当我们参加边缘特征10个，形状特征6个，颜色特征9个三个形态学特征总共25个特征的时候，产生的聚类效果要好于单个特征的聚类结果，因为更多的特征才更加形象的描绘了叶子的属性特征，聚类结果如下列图所示：叶子边缘，形态，颜色特征的生成树(5-21)(样品135和样品153)由此图可以判断样本1是属于异类数据，上图可以明显的看到数据分成了两类，聚类结果相比拟单特征边缘特征有了更好的效果。六、模型的评价模型的优点：1、 模型的稳定性较强，当所给图片发生如平移、旋转甚至缩放对结果正确性都没有影响。2、 谱系图让我们更直观的展现叶片的分类结果。3、 模型的推广型比拟强，对于简单的图片都可以进展特征提取、谱系分析。模型的缺点：1、 由于不变矩阵对于纹理比拟复杂的图像，模型的正确率不高，所以对于复杂图像模型不能适应。2、 不能完全排除噪音的干扰。七、参考文献1 兵旗，Visual C+实用图像处理，：清华大学，2004.3。2 鹏宇，基于容的图像特征提取算法的研究：24-27,55-59,2004.5.1。3,算法贝叶斯，.blogs./skyme/p/3564391.html，2015.5.1。4 爱网校，聚类分析 谱系聚类法，.doc88./p-1.html，2015.5.1。.
展开阅读全文