最邻近模板匹配法.doc

报告提交日期2013年6月27报告批改日期2013年月最邻近模板匹配法一 实验内容：在模式识别中一个最基本的方法，就是模板匹配法(template matching)，它基本上是一种统计识别方法。 为了在图像中检测出已知形状的目标物，我们使用这个目标物的形状模板（或窗口）与图像匹配，在约定的某种准则下检测出目标物图像，通常称其为模板匹配法。它能检测出图像中上线条、曲线、图案等等。它的应用包括：目标模板与侦察图像相匹配；文字识别和语音识别等。二. 实验条件pc机一台，vs2008软件三.实验原理我们采用以下的算式来衡量模板T（m,n)与所覆盖的子图Sij（i,j)的关系，已知原始图像S(W,H)，如图所示：利用以下公式衡量它们的相似性：上述公式中第一项为子图的能量，第三项为模板的能量，都和模板匹配无关。第二项是模板和子图的互为相关，随（i,j）而改变。当模板和子图匹配时，该项由最大值。在将其归一化后，得到模板匹配的相关系数：当模板和子图完全一样时，相关系数R(i,j) = 1。在被搜索图S中完成全部搜索后，找出R的最大值Rmax(im,jm)，其对应的子图Simjm即位匹配目标。显然，用这种公式做图像匹配计算量大、速度慢。我们可以使用另外一种算法来衡量T和Sij的误差，其公式为：计算两个图像的向量误差，可以增加计算速度，根据不同的匹配方向选取一个误差阀值E0，当E(i,j)E0时就停止该点的计算，继续下一点的计算。最终的实验证明，被搜索的图像越大，匹配的速度越慢；模板越小，匹配的速度越快；阀值的大小对匹配速度影响大；3、改进的模板匹配算法 将一次的模板匹配过程更改为两次匹配； 第一次匹配为粗略匹配。取模板的隔行隔列数据，即1/4的模板数据，在被搜索土上进行隔行隔列匹配，即在原图的1/4范围内匹配。由于数据量大幅减少，匹配速度显著提高。同时需要设计一个合理的误差阀值E0：E0 = e0 * (m + 1) / 2 * (n + 1) / 2式中：e0为各点平均的最大误差，一般取4050即可； m,n为模板的长宽；第二次匹配是精确匹配。在第一次误差最小点（imin, jmin)的邻域内，即在对角点为（imin -1, jmin -1), (Imin + 1, jmin + 1)的矩形内，进行搜索匹配，得到最后结果。四实验内容1. 流程图2.程序number_no Classification:LeastDistance()double min=10000000000; 定义一个变量存放最小值number_no number_no;for(int n=0;n10;n+) 三个for循环逐一地和每个样品 进行距离计算，并把最小距离值for(int i=0;ipatternn.number;i+) 赋给minif(pipei(patternn.featurei,testsample)min)/匹配的最小值min=pipei(patternn.featurei,testsample); number_no.number=n;/样品类别number_no.no=i;/样品序号return number_no;/返回手写数字的类别和序号 将最小距离对应的类别号返 回五，实验结果分析识别数字： 算法实现的关键问题是进行匹配，求最小距离，其解决方法是和训练集的样品逐一进行距离的计算，最后找出最相邻的样品得到类别号。六.实验心得针对每一种模式识别技术。老师讲解了理论基础，实现步骤，编程代码三部分，了解了基本理论之后，按照实现步骤的指导，可以了解算法的实现思路和方法，再进一步体会核心代码。但由于对C+掌握不是太好，所有算法都是用VC+编程实现的，所以对模式识别技术的掌握还是不够好。研究程序代码是枯燥无味的，但只要用心去学，研究，还是能收获自己想要的结果，也会拥有不一样的快乐。别人的思想要做到学以致用，同时自己也要学会绝一反三。希望以后低年级的教学安排中，能早一点多学点相关的软件基础，平时老师能给我们学生一部分相关的作业作为练习。之后能细致的讲解和辅导。当然，我们自己也应该更加努力课下阅读学习相关的书籍知识。七. 参考文献杨淑莹，图像模式识别，清华大学出版社，2005年第一版Bayes分类器最小错误概率的Bayes方法一. 实验目的：1. 对模式识别有一个初步的理解，能够根据自己的设计对贝叶斯决策理论算法有一个深刻地认识；2. 理解二类分类器的设计原理。二. 实验条件pc机一台，vs2008软件三实验原理 1. 目标：计算。分析：由于数据t是一个新的数据，无法在训练数据集中统计出来。因此需要转换。根据概率论中的贝叶斯定理将的计算转换为：（1）其中，表示类Cj在整个数据空间中的出现概率，可以在训练集中统计出来（即用Cj在训练数据集中出现的频率来作为概率。但和仍然不能统计出来。首先，对于，它表示在类中出现数据t的概率。根据“属性独立性假设”，即对于属于类的所有数据，它们个各属性出现某个值的概率是相互独立的。如，判断一个干部是否是“好干部”（分类）时，其属性“生活作风好”的概率（P(生活作风好|好干部)）与“工作态度好”的概率（P(工作态度好|好干部)）是独立的，没有潜在的相互关联。换句话说，一个好干部，其生活作风的好坏与其工作态度的好坏完全无关。我们知道这并不能反映真实的情况，因而说是一种“假设”。使用该假设来分类的方法称为“朴素贝叶斯分类”。根据上述假设，类中出现数据t的概率等于其中出现t的各属性值的概率的乘积。即：（2）其中，是数据t的第k个属性值。其次，对于公式（1）中的，即数据t在整个数据空间中出现的概率，等于它在各分类中出现概率的总和，即：（3）其中，各的计算就采用公式（2）。这样，将（2）代入（1），并综合公式（3）后，我们得到：（4）公式（4）就是我们最终用于判断数据t分类的方法。其依赖的条件是：从训练数据中统计出和。当我们用这种方法判断一个数据的分类时，用公式（4）计算它属于各分类的概率，再取其中概率最大的作为分类的结果。2.文本分类的具体方法文本分类中，数据是指代表一篇文本的一个向量。向量的各维代表一个关键字的权重。训练文本中，每个数据还附带一个文本的分类编码。对此我们有两个方面的工作：（1） 分类器学习：即从训练数据集中统计和，并保存起来。（保存到一个数据文件中，可以再次加载）。在分类器的程序中，需要有表达和保存这些概率数据的变量或对象。（2） 分类识别：从一个测试文档中读取其中的测试数据项，识别他们的分类，并输出到一个文件中。但文本分类有一个特殊情况：各属性的值不是标准值，不像“性别”这样的属性。因此在查找时会遇到麻烦：新数据的值可能在训练数据中从未出现过。这个问题的另一方面是：训练数据中各属性（分别对应一个关键词）的值太分散，几乎不可能出现某个关键词在多篇文章中的权重相同的情况。这样，太多、太分散，没有统计上的意义。这一问题的处理方法是：将各关键词的权重分段：即将权重的值域分成几个段，每段取其中数值的平均值作为其标准值。第一种方法是，直接对所有训练数据的属性值进行分段，如对第k个属性，将其值域分为(00.1), (0.10.2), , (0.91)，各段分别编号为0,1,9。一个数据的该属性值为0.19，则重设该属性值为它所处的分段编号，即1。另一种方法同样进行分段，但分段后计算各段的平均值作为各段的标准值。根据具体数据相应属性的值与各分段标准值的接近程度，重新设置数据该属性的值。如对第k个属性，将其值域分为(00.1), (0.10.2), , (0.91)，假设(0.10.2)的平均值为0.15，(0.20.3)的平均值为0.22，而一个数据的该属性值为0.19，则该数据的该属性值与0.22更接近，应该重设为0.22。这就是我们要采用的方法。下一个问题是，以什么作为分段标准？如果按平分值域的方法，则可能数据在值域各段中的分别非常不均匀，会造成在数据稀少的值域中失去统计意义。因此一个方法是，按照分布数据均匀为标准进行分段划分。假设有N个数据，将属性值域分为M段。对属性k，将数据按k属性的值排序，然后按N/M个进行等分，计算各值域分段中的标准值。（5）其中，m表示一个分段，表示第k个属性值在该段内的数据的总数。每段内的数据的相应属性重设为该段的平均值。分段的工作在在训练阶段进行。必须保留分段的结果：即各属性的各分段值域的标准值。在训练阶段，将所有训练数据的属性值替换为标准值后，再进行统计。而在识别阶段，将待识别数据的属性值同样替换为标准值后，再进行识别。3. 对象模型 根据我们要进行工作，其中包含：数据（项），数据集，属性，属性值，属性标准值，分类概率，分类属性概率等名词。从实现上考虑：（1）训练中的数据分段：根据数据的k属性值，对所有数据进行排序。按数据个数均分的原则进行分段，并计算k属性在各段的标准值，该值需要保留。假设我们有数据项对象（CDataItem）和数据集对象(CDataSet)，显然数据集对象负责该项工作。即，CDataSet中应该包含一个方法：Segment(k, m)。其中k表示对第k个属性，m表示总共分为m个段。该方法产生的各段标准值也需要保留。由于这些标准值是针对各个属性的，因此应该定义一个属性对象来存储这些值。即需要一个CAttribute对象。此外，分段时需要的排序可以使用C+标准库中的sort模板函数来实现。（2）根据属性值域分段的标准值，更新数据项的属性值：对一个数据的第k个属性，使用其属性值在K属性对象（CAttribute的一个对象）中查找它最接近的标准值，并用以替换原值。查找标准值的方法可以分配给CAttribute对象：即需要一个Search方法，返回找到的标准值（如果分段多，需要使用二分法查找以提高效率。可以利用C+标准库中的相应模板函数实现）。（3）分类器本身应该作为一个类，即CBayesClassifier。其中应该包含Train（dataset）和Recognize(data)两个方法。前者用以根据dataset进行训练，后者用以识别一个数据data的分类。识别中需要各种概率：和。可以用CBayesClassifier的一个动态数值成员实现其存储，可以用C+的vector类模板实现。显然是一个二维表：行列分别是类和属性。可以用一个二维数组的成员表示，也可以用两层的vector实现。四. 实验内容假定某个局部区域细胞识别中正常（）和非正常（）两类先验概率分别为：正常状态：=0.9；异常状态：=0.1。现有一系列待观察的细胞，其观察值为：-3.9847 -3.5549 -1.2401 -0.9780 -0.7932 -2.8531-2.7605 -3.7287 -3.5414 -2.2692 -3.4549 -3.0752 -3.9934 2.8792 -0.9780 0.7932 1.1882 3.0682-1.5799 -1.4885 -0.7431 -0.4221 -1.1186 4.2532 类条件概率分布正态分布分别为（-2，0.25）（2,4）。决策表为(表示的简写)，=6, =1，=0。试对观察的结果进行分类。五. 程序和实验结果1.实验程序/* 函数名称：BayesLeasterror()* 函数类型：int * 函数功能：最小错误概率的Bayes分类器,返回手写数字的类别*/int Classification:BayesLeasterror()double X25;/待测样品double Xmeans25;/样品的均值double S2525;/协方差矩阵double S_2525;/S的逆矩阵double Pw;/先验概率double hx10;/判别函数int i,j,k,n;for(n=0;n10;n+)/循环类别int num=patternn.number;/样品个数/求样品平均值for(i=0;i25;i+)Xmeansi=0.0;for(k=0;knum;k+)for(i=0;i0.10?1.0:0.0;for(i=0;i25;i+)Xmeansi/=(double)num;/求协方差矩阵double mode20025;for(i=0;inum;i+)for(j=0;j0.10?1.0:0.0;for(i=0;i25;i+)for(j=0;j25;j+)double s=0.0;for(k=0;knum;k+)s=s+(modeki-Xmeansi)*(modekj-Xmeansj);s=s/(double)(num-1);Sij=s;/求先验概率int total=0;for(i=0;i10;i+)total+=patterni.number;Pw=(double)num/(double)total;/求S的逆矩阵for(i=0;i25;i+)for(j=0;j25;j+)S_ij=Sij;double(*p)25=S_;brinv(*p,25);/S的逆矩阵/求S的行列式double (*pp)25=S;double DetS;DetS=bsdet(*pp,25);/S的行列式/求判别函数for(i=0;i0.10?1.0:0.0;for(i=0;i25;i+)Xi-=Xmeansi;double t25;for(i=0;i25;i+)ti=0;brmul(X,S_,25,t);double t1=brmul(t,X,25);double t2=log(Pw);double t3=log(DetS+1);hxn=-t1/2+t2-t3/2;double maxval=hx0;int number=0;/判别函数的最大值for(n=1;nmaxval)maxval=hxn;number=n;return number;2.实验结果六. 实验心得 在熟悉bayes最小错误概率的决策之后，深知要学会bayes分类器的原理，基本概念，bayes公式是一个巨大的工程。于此，明白学习此门课程需要比较高的阅读程序的能力，需要有较强的数学知识。因此，学习是个无底洞的玩意儿，要想学好它，必须对此门课程有着较强的兴趣。只是可惜，我对此门课程还未进入门道。七. 参考文献杨淑莹，图像模式识别，清华大学出版社，2005年第一版层次聚类中间距离法一实验目的在聚类算法的大环境下，和分类不同的是，聚类问题它在做出聚类判断前，是不知道一批样品中的每一个样品的所属类别的。即它是不凭借任何的先验知识来进行推测的，所以聚类问题又被称之为“无监督学习”； 其次，聚类算法的重点在于依靠寻找特征相似的聚合类，它实现的步骤可以归纳为三步：A找到目标样品，并对目标样品进行标号。B对已经分割出来的目标样品进行特征提取。C采用不同的聚类算法对样品进行聚类.综合上述，我们需要掌握图像的阈值分割和图像的标识，聚类前所有样品的右下角的数值均为0；当采用一种聚类方法进行聚类后，具有相同特征属性的样品右下角的数值是相同的，等等基础知识二. 实验条件pc机一台，vs2008软件三实验原理 流程图四实验内容程序：/*函数名称Zhongjianjulifa()*参数void*返回值 void*函数功能按照中间距离法对全体样品进行分类*/void CCluster:Zhongjianjulifa()GetFeature();double*centerdistance;/记录类间距离double T;/阈值intdistype;/距离的形式（欧氏、余弦。）int i,j;double minous,maxous,mincos,maxcos,minbcos,maxbcos,mintan,maxtan;minous=MAX; mincos=MAX; minbcos=MAX; mintan=MAX;maxous=0; maxcos=0; maxbcos=0; maxtan=0;/计算四种距离模式的参考值for ( i=0;ipatternnum-1;i+)for ( j=i+1;jGetDistance(m_patterni,m_patternj,1)minous=GetDistance(m_patterni,m_patternj,1);if (maxousGetDistance(m_patterni,m_patternj,2)mincos=GetDistance(m_patterni,m_patternj,2);if (maxcosGetDistance(m_patterni,m_patternj,3)minbcos=GetDistance(m_patterni,m_patternj,3);if (maxbcosGetDistance(m_patterni,m_patternj,4)mintan=GetDistance(m_patterni,m_patternj,4);if (maxtanGetDistance(m_patterni,m_patternj,4)maxtan=GetDistance(m_patterni,m_patternj,4);DlgInfor mDlgInfor;mDlgInfor.ShowInfor(minous,maxous,mincos,maxcos,minbcos,maxbcos,mintan,maxtan);if (mDlgInfor.DoModal()=IDOK)T=mDlgInfor.m_T;distype=mDlgInfor.m_DisType;else return; /初始化for ( i=0;ipatternnum;i+)/每个样品自成一类m_patterni.category=i+1;centerdistance=new double *patternnum;/建立类间距离数组，centerdistanceij表示i类和j类距离for ( i=1;ipatternnum;i+)centerdistancei=new double patternnum+1;for ( i=1;ipatternnum;i+)for (int j=i+1;j=patternnum;j+)centerdistanceij=GetDistance(m_patterni-1,m_patternj-1,distype);centernum=patternnum;while(1)double td,*tempdistance;int ti,tj;td=MAX;ti=0;tj=0;tempdistance= new double *patternnum;/临时记录类间距离for (i=1;ipatternnum;i+)tempdistancei=new doublepatternnum+1;for( i=1;icenternum;i+)/找到距离最近的两类:ti,tj,记录最小距离td;for ( j=i+1;jcenterdistanceij)td=centerdistanceij;ti=i;tj=j;if(tdT)/合并类i,jfor ( i=0;itj)m_patterni.category-;centernum-;for (i=1;icenternum;i+)/重新计算合并后的类到其他各类的新距离for ( j=i+1;j=centernum;j+)if (i=tj)tempdistanceij=centerdistanceij+1;elsetempdistanceij=centerdistanceij;else if (i=ti)if (jti)&(itj)if(j=tjtempdistanceij=centerdistancei+1j+1;for (i=1;icenternum;i+)for ( j=i+1;j=centernum;j+)centerdistanceij=tempdistanceij;else break;delete tempdistance;delete centerdistance;五结果分析结果分析：存在问题及改