最邻近模板匹配法_法律资料_人文社科_专业资料

1、报告提交日期2013 年 6 月 27报告批改日期2013年 月最邻近模板匹配法5实验内容:在模式识别中一个最基本的方法，就是模板匹配法(template matching)，它基本上是一种统计识别方法。为了在图像中检测出已知形状的目标物，我们使用这个目标物的形状模板(或窗口)与图像匹配，在约定的 某种准则下检测出目标物图像，通常称其为模板匹配法。它能检测出图像中上线条、曲线、图案等等。它 的应用包括：目标模板与侦察图像相匹配；文字识别和语音识别等。二. 实验条件pc机一台，vs2008软件实验原理我们采用以下的算式来衡量模板 T(m,n)与所覆盖的子图Sij(i,j)的关系，已知原始图像S(

2、W,H)， 如图所示：-m利用以下公式衡量它们的相似性：Af A'M N工厂(叫 H)z - 2工伽)+£ n八朋昇沂ffjs!I:w!RFT*l 障:上述公式中第一项为子图的能量， 第三项为模板的能量，都和模板匹配无关。第二项是模板和 子图的互为相关，随(i,j)而改变。当模板和子图匹配时，该项由最大值。在将其归一化后， 得到模板匹配的相关系数：w7?/?)x Tlm.n)M x.工厂伽,“)F当模板和子图完全一样时，相关系数R(i,j) = 1。在被搜索图S中完成全部搜索后，找出R的最大值Rmax(imjm)，其对应的子图Simjm即位匹配目标。显然，用这种公式做图像匹配

3、计算 量大、速度慢。我们可以使用另外一种算法来衡量T和Sij的误差，其公式为：= X X計5异)1厂(叫小计算两个图像的向量误差，可以增加计算速度，根据不同的匹配方向选取一个误差阀值E0,当E(i,j)>E0时就停止该点的计算，继续下一点的计算。最终的实验证明，被搜索的图像越大，匹配的速度越慢；模板越小，匹配的速度越快；阀值的 大小对匹配速度影响大；3、改进的模板匹配算法将一次的模板匹配过程更改为两次匹配；第一次匹配为粗略匹配。取模板的隔行隔列数据，即1/4的模板数据，在被搜索土上进行隔行隔列匹配，即在原图的1/4范围内匹配。由于数据量大幅减少，匹配速度显著提高。同时 需要设计一个合理的

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;nu mber_ no nu mber_ no;for定义

5、一个变量存放最小值(intn=0; n<10; n+)for(int i=O;i<patternn.number;i+)三个for循环逐一地和每个样品 进行距离计算，并把最小距离值赋给minif(pipei(patter nn .featurei,testsample)< min)/匹配的最小值min=pipei(patter nn .featurei,testsample); nu mber_ no.nu mber= n; /样品类别 number_no.no=i; / 样品序号 returnnumber_no; /返回手写数字的类别和序号五，实验结果分析将最小距离对应的类

6、别号返 回识别数字: 嚴接近样品算法实现的关键问题是进行匹配，求最小距离，其解决方法是和训练集的样品逐一进行距离的计算，最 后找出最相邻的样品得到类别号。六.实验心得针对每一种模式识别技术。老师讲解了理论基础，实现步骤，编程代码三部分，了解了基本理论之后，按照实现步骤的指导，可以了解算法的实现思路和方法，再进一步体会核心代码。但由于对C+掌握不是太好，所有算法都是用 VC+编程实现的，所以对模式识别技术的掌握还是不够好。研究程序代码是枯燥无味 的，但只要用心去学，研究，还是能收获自己想要的结果，也会拥有不一样的快乐。别人的思想要做到学 以致用，同时自己也要学会绝一反三。希望以后低年级的教学安排

7、中，能早一点多学点相关的软件基础， 平时老师能给我们学生一部分相关的作业作为练习。之后能细致的讲解和辅导。当然，我们自己也应该更 加努力课下阅读学习相关的书籍知识。七.参考文献杨淑莹，图像模式识别，清华大学出版社，2005年第一版Bayes分类器最小错误概率的Bayes方法一.实验目的：1. 对模式识别有一个初步的理解，能够根据自己的设计对贝叶斯决策理论算法有一个深刻地 认识；2. 理解二类分类器的设计原理。二. 实验条件pc机一台，vs2008软件三. 实验原理1.目标:计算分析:由于数据t是一个新的数据，的贝叶斯定理无法在训练数据集中统计出来。因此需要转换。根据概率论中将 10的计算转换为

8、:其中,表示类G在整个数据空间中的出现概率，可以在训练集中统计出来（即用G在训练数据（1）(4)9集中出现的频率W丿来作为概率®）。但和円/）仍然不能统计出来。首先，对于巩啊），它表示在类中出现数据t的概率。根据“属性独立性假设”，即对于属于类的所有数据,它们个各属性出现某个值的概率是相互独立的。如，判断一个干部是否是“好干部”（分类）时，其属性“生活作风=好”的概率（P（生活作风=好 好干部）与“工作态度=好”的概率（ P（工作态度=好I好干部）是独立的，没有潜在的相互关联。换句话说，一个好干部，其生活作风的好坏与其工作 态度的好坏完全无关。我们知道这并不能反映真实的情况，因而说是

9、一种“假设”。使用该假设来分类的 方法称为“朴素贝叶斯分类”。c根据上述假设，类一中出现数据t的概率等于其中出现 t的各属性值的概率的乘积。即:t（2）其中，'t是数据t的第k个属性值。其次，对于公式（1）中的贰°,即数据t在整个数据空间中出现的概率，等于它在各分类中出现概率的总和，即:其中，各的计算就采用公式（这样，将（2）代入（1）,并综合公式（3 ）后，我们得到:其中:公式(4)就是我们最终用于判断数据 t分类的方法。其依赖的条件是:从训练数据中统计出叫I 丿当我们用这种方法判断一个数据的分类时，用公式(4)计算它属于各分类的概率，再取其中概率最大的作为分类的结果。2.

10、 文本分类的具体方法(1)分类器学习：即从训练数据集中统计叫I 和珂®，并保存起来。(保存到一个数据文件文本分类中，数据是指代表一篇文本的一个向量。向量的各维代表一个关键字的权重。训练文本中, 每个数据还附带一个文本的分类编码。对此我们有两个方面的工作：中，可以再次加载)。在分类器的程序中，需要有表达和保存这些概率数据的变量或对象。时会遇到麻烦：新数据的(2)分类识别：从一个测试文档中读取其中的测试数据项，识别他们的分类，并输出到一个文件中。但文本分类有一个特殊情况：各属性的值不是标准值， 不像“性别”这样的属性。因此在查找14值可能在训练数据中从未出现过。这个问题的另一方面是：训练

11、数据中各属性(分别对应一个关键词)的值太分散，几乎不可能出现某个关键词在多篇文章中的权重相同的情况。这样，I )太多、太分散，没有统计上的意义。这一问题的处理方法是：将各关键词的权重分段：即将权重的值域分成几个段，每段取其中数值的平 均值作为其标准值。第一种方法是，直接对所有训练数据的属性值进行分段，如对第k个属性，将其值域分为(00.1), (0.10.2),(0.91)，各段分别编号为 0,1,9。一个数据的该属性值为0.19，则重设该属性值为它所处的分段编号，即1。另一种方法同样进行分段，但分段后计算各段的平均值作为各段的标准值。根据具体数据相应属性的 值与各分段标准值的接近程度，重新设

12、置数据该属性的值。如对第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个进行等分，计算各值域分段中的标准值。其中

13、，m表示一个分段,(5)表示第k个属性值在该段内的数据的总数。每段内的数据的相应属性重设为该段的平均值。分段的工作在在训练阶段进行。必须保留分段的结果：即各属性的各分段值域的标准值。在训练阶段, 将所有训练数据的属性值替换为标准值后，再进行统计。而在识别阶段，将待识别数据的属性值同样替换 为标准值后，再进行识别。3. 对象模型根据我们要进行工作，其中包含：数据（项），数据集，属性，属性值，属性标准值，分类概率，分 类属性概率等名词。从实现上考虑：（1） 训练中的数据分段：根据数据的k属性值，对所有数据进行排序。按数据个数均分的原则进行分 段，并计算k属性在各段的标准值，该值需要保留。假设我们有

14、数据项对象（CDataltem）和数据集对象（CDataSet），显然数据集对象负责该项工作。即， CDataSet中应该包含一个方法：Segment（k, m）。其中k表示对第k个属性，m表示总共分为 m个段。该方法产生的各段标准值也需要保留。由于这些标准值是针对各个属性的，因此应该定义一个属性对象来存储 这些值。即需要一个 CAttribute对象。此外，分段时需要的排序可以使用C+标准库中的sort模板函数来实现。（2） 根据属性值域分段的标准值，更新数据项的属性值：对一个数据的第k个属性，使用其属性值在K属性对象（CAttribute的一个对象）中查找它最接近的标准值，并用以替换原值。

15、查找标准值的方法可以 分配给CAttribute对象：即需要一个 Search方法，返回找到的标准值（如果分段多，需要使用二分法查找 以提高效率。可以利用C+标准库中的相应模板函数实现）。（3） 分类器本身应该作为一个类，即CBayesClassifier。其中应该包含 Train（ dataset）和Recognize（data）两个方法。前者用以根据dataset进行训练，后者用以识别一个数据data的分类。识别中需要各种概率：叫I印和吧）叫可以用CBayesClassifier的一个动态数值成员实现其存储,可以用C+的vector类模板实现。显然是个二维表：行列分别是类和属性。可以用一个

16、二维数组的成员表示，也可21以用两层的vector实现。四. 实验内容假定某个局部区域细胞识别中正常（皿1）和非正常（仙2 ）两类先验概率分别为:正常状态:厲讪=0.9 ；异常状态：他）=0.1。现有一系列待观察的细胞，其观察值为.1 :以屮。加I幼）类条件概率分布正态分布分别为（-2，0.25）（ 2,4）。决策表为的简写），=6,爲 1=1，妇=0。3.9847-3.5549-1.2401-0.9780-0.7932 -2.85312.7605-3.7287-3.5414-2.2692-3.4549-3.07523.99342.8792-0.97800.79321.18823.06821.

17、5799-1.4885-0.7431-0.4221-1.11864.2532试对观察的结果进行分类。五 . 程序和实验结果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，

18、n;for (n=0;n<10;n+) / 循环类别int num=patternn.number; / 样品个数/ 求样品平均值for (i=0;i<25;i+)Xmeansi=0.0;for (k=0;k<num;k+)for (i=0;i<25;i+)Xmeansi+=patternn.featureki>0.10?1.0:0.0; for (i=0;i<25;i+)Xmeansi/=( double )num;/ 求协方差矩阵double mode20025;for (i=0;i<num;i+)for (j=0;j<25;j+)modei

19、j=patternn.featureij>0.10?1.0:0.0;for (i=0;i<25;i+)for (j=0;j<25;j+)double s=0.0;for (k=0;k<num;k+)s=s+(modeki-Xmeansi)*(modekj-Xmeansj);s=s/( double )(num-1);Sij=s;/ 求先验概率int total=0;for (i=0;i<10;i+)total+=patterni.number;Pw=(double )num/( double )total;/求S的逆矩阵for (i=0;i<25;i+)fo

20、r (j=0;j<25;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;i<25;i+)Xi=testsamplei>0.10?1.0:0.0;for (i=0;i<25;i+)Xi-=Xmeansi;double t25;for (i=0;i<25;i+)ti=0;brmul(X,S_,25,t);double t1=brmul(t,X,25);doub

21、le t2=log(Pw);double t3=log(DetS+1);hxn=-t1/2+t2-t3/2;double maxval=hx0;int number=0;/ 判别函数勺最大值for (n=1;n<10;n+)if (hxn>maxval)maxval=hxn;number=n;return number;2.实验结果R(幻| X) 左兀占的| X)=入応仙| X) = 1.092 j-i2R(a3 | X)-若入巧玖3j |X) X21P(ai2 |X) - 0,818由于 R(oc|X)aR(oc2|X)判待钗别的细胞X% 3 2类畀常细胞比较例2d PfwJX)

22、 =0.818, P(w2|X) =0,182 ,正常细胞六.实验心得在熟悉bayes最小错误概率的决策之后，深知要学会bayes分类器的原理，基本概念，bayes公式是一个巨大的工程。于此，明白学习此门课程需要比较高的阅读程序的能力，需要有较强的数学知识。因此，学 习是个无底洞的玩意儿，要想学好它，必须对此门课程有着较强的兴趣。只是可惜，我对此门课程还未进 入门道。七 . 参考文献杨淑莹，图像模式识别 ，清华大学出版社， 2005 年第一版层次聚类中间距离法一实验目的在聚类算法的大环境下，和分类不同的是，聚类问题它在做出聚类判断前，是不知道一批样品中的每一 个样品的所属类别的。即它是不凭借任

23、何的先验知识来进行推测的，所以聚类问题又被称之为“无监督学 习”； 其次，聚类算法的重点在于依靠寻找特征相似的聚合类，它实现的步骤可以归纳为三步： A 找到 目标样品，并对目标样品进行标号。B 对已经分割出来的目标样品进行特征提取。C 采用不同的聚类算法对样品进行聚类 .综合上述，我们需要掌握图像的阈值分割和图像的标识，聚类前所有样品的右下角的数 值均为 0；当采用一种聚类方法进行聚类后，具有相同特征属性的样品右下角的数值是相同的，等等基础知 识二. 实验条件pc 机一台， vs2008 软件三.实验原理流程图将能测到的第一个样黑作为第一个聚类申心四.实验内容程序：/*函数名称Zhongjia

24、njulifa()*参数void*返回值void*函数功能按照中间距离法对全体样品进行分类*Jvoid CCIuster:Zhongjianjulifa()GetFeature();double *centerdistance; / 记录类间距离double T; / 阈值int distype; / 距离的形式(欧氏、余弦。) int i,j;double minous,maxous,mincos,maxcos,minbcos,maxbcos,mintan,maxtan;minous=MAX; mincos=MAX; minbcos=MAX; mintan=MAX; maxous=0; ma

25、xcos=0; maxbcos=0; maxtan=0;/ 计算四种距离模式的参考值for ( i=0;i<patternnum-1;i+)for ( j=i+1;j<patternnum;j+)if (minous>GetDistance(m_patterni,m_patternj,1) minous=GetDistance(m_patterni,m_patternj,1);if (maxous<GetDistance(m_patterni,m_patternj,1) maxous=GetDistance(m_patterni,m_patternj,1);if (mi

26、ncos>GetDistance(m_patterni,m_patternj,2)mincos=GetDistance(m_patterni,m_patternj,2);if (maxcos<GetDistance(m_patterni,m_patternj,2)maxcos=GetDistance(m_patterni,m_patternj,2);if (minbcos>GetDistance(m_patterni,m_patternj,3)minbcos=GetDistance(m_patterni,m_patternj,3);if (maxbcos<GetDist

27、ance(m_patterni,m_patternj,3) maxbcos=GetDistance(m_patterni,m_patternj,3);if (mintan>GetDistance(m_patterni,m_patternj,4) mintan=GetDistance(m_patterni,m_patternj,4);if (maxtan<GetDistance(m_patterni,m_patternj,4)maxtan=GetDistance(m_patterni,m_patternj,4);DlgInfor mDlgInfor;mDlgInfor.ShowInf

28、or(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;i<patternnum;i+)/ 每个样品自成一类m_patterni.category=i+1;表示 i 类和 j 类距离centerdistance= new double *patternnum; / 建立类间距离数组， centerdistanceij f

29、or ( i=1;i<patternnum;i+)centerdistancei= new double patternnum+1;for ( i=1;i<patternnum;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 do

30、uble *patternnum; / 临时记录类间距离 for (i=1;i<patternnum;i+)tempdistancei= new double patternnum+1;for ( i=1;i<centernum;i+) / 找到距离最近的两类 :ti,tj, 记录最小距离 td; for ( j=i+1;j<=centernum;j+)if (td>centerdistanceij)td=centerdistanceij;ti=i;tj=j;if (td<T) / 合并类 i,j for ( i=0;i<patternnum;i+) if

31、(m_patterni.category=tj) m_patterni.category=ti;if (m_patterni.category>tj) m_patterni.category-;centernum-;for (i=1;i<centernum;i+) / 重新计算合并后的类到其他各类的新距离for ( j=i+1;j<=centernum;j+)if (i<ti)if (j=ti)tempdistanceij=sqrt (centerdistanceiti*centerdistanceiti/2+centerdistanceitj*centerdistan

32、ceitj/2-centerdistance titj*centerdistancetitj/4);else if (j>=tj)tempdistanceij=centerdistanceij+1;elsetempdistanceij=centerdistanceij;else if (i=ti)if (j<tj)tempdistanceij=sqrt (centerdistancetij*centerdistancetij/2+centerdistancejtj*centerdistancejtj/2-centerdistance titj*centerdistancetitj/

33、4);elsetempdistanceij=sqrt (centerdistancetij+1*centerdistancetij+1/2+centerdistancetjj+1*centerdistancetjj+1/2-centerd istancetitj*centerdistancetitj/4);else if (i>ti)&&(i<tj)if (j<tj)tempdistanceij=centerdistanceij;elsetempdistanceij=centerdistanceij+1;else /i>=tjtempdistanceij=centerdistancei+1j+1;for (i=1;i<centernum;i+)for ( j=i+1;jv=centernum;j+)centerdistanceij=tempdis