最邻近模板匹配法.docx
- 文档编号:9474389
- 上传时间:2023-05-19
- 格式:DOCX
- 页数:26
- 大小:570.02KB
最邻近模板匹配法.docx
《最邻近模板匹配法.docx》由会员分享,可在线阅读,更多相关《最邻近模板匹配法.docx(26页珍藏版)》请在冰点文库上搜索。
最邻近模板匹配法
报告提交日期
2013年6月27
报告批改日期
2013年月
最邻近模板匹配法
一.实验内容:
在模式识别中一个最基本的方法,就是模板匹配法(templatematching),它基本上是一种统计识别方法。
为了在图像中检测出已知形状的目标物,我们使用这个目标物的形状模板(或窗口)与图像匹配,在约定的某种准则下检测出目标物图像,通常称其为模板匹配法。
它能检测出图像中上线条、曲线、图案等等。
它的应用包括:
目标模板与侦察图像相匹配;文字识别和语音识别等。
二.实验条件
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为各点平均的最大误差,一般取40~50即可;
m,n为模板的长宽;
第二次匹配是精确匹配。
在第一次误差最小点(imin,jmin)的邻域内,即在对角点为(imin-1,jmin-1),(Imin+1,jmin+1)的矩形内,进行搜索匹配,得到最后结果。
四.实验内容
1.流程图
2.程序
number_noClassification:
:
LeastDistance()
{
doublemin=;定义一个变量存放最小值
number_nonumber_no;
for(intn=0;n<10;n++)三个for循环逐一地和每个样品
{进行距离计算,并把最小距离值
for(inti=0;i { if(pipei(pattern[n].feature[i],testsample) { //匹配的最小值 min=pipei(pattern[n].feature[i],testsample); number_no.number=n;//样品类别 number_no.no=i;//样品序号 } } } returnnumber_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个属性,将其值域分为(0~0.1),(0.1~0.2),…,(0.9~1),各段分别编号为0,1,…9。 一个数据的该属性值为0.19,则重设该属性值为它所处的分段编号,即1。 另一种方法同样进行分段,但分段后计算各段的平均值作为各段的标准值。 根据具体数据相应属性的值与各分段标准值的接近程度,重新设置数据该属性的值。 如对第k个属性,将其值域分为(0~0.1),(0.1~0.2),…,(0.9~1),假设(0.1~0.2)的平均值为0.15,(0.2~0.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.99342.8792-0.97800.79321.18823.0682 -1.5799-1.4885-0.7431-0.4221-1.11864.2532 类条件概率分布正态分布分别为(-2,0.25)(2,4)。 决策表为 ( 表示 的简写), =6, =1, =0。 试对观察的结果进行分类。 五.程序和实验结果 1.实验程序 /****************************************************************** *函数名称: BayesLeasterror() *函数类型: int *函数功能: 最小错误概率的Bayes分类器,返回手写数字的类别 ******************************************************************/ intClassification: : BayesLeasterror() { doubleX[25];//待测样品 doubleXmeans[25];//样品的均值 doubleS[25][25];//协方差矩阵 doubleS_[25][25];//S的逆矩阵 doublePw;//先验概率 doublehx[10];//判别函数 inti,j,k,n; for(n=0;n<10;n++)//循环类别~ { intnum=pattern[n].number;//样品个数 //求样品平均值 for(i=0;i<25;i++) Xmeans[i]=0.0; for(k=0;k { for(i=0;i<25;i++) Xmeans[i]+=pattern[n].feature[k][i]>0.10? 1.0: 0.0; } for(i=0;i<25;i++) Xmeans[i]/=(double)num; //求协方差矩阵 doublemode[200][25]; for(i=0;i for(j=0;j<25;j++) mode[i][j]=pattern[n].feature[i][j]>0.10? 1.0: 0.0; for(i=0;i<25;i++) for(j=0;j<25;j++) { doubles=0.0; for(k=0;k s=s+(mode[k][i]-Xmeans[i])*(mode[k][j]-Xmeans[j]); s=s/(double)(num-1); S[i][j]=s; } //求先验概率 inttotal=0; for(i=0;i<10;i++) total+=pattern[i].number; Pw=(double)num/(double)total; //求S的逆矩阵 for(i=0;i<25;i++) for(j=0;j<25;j++) S_[i][j]=S[i][j]; double(*p)[25]=S_; brinv(*p,25);//S的逆矩阵 //求S的行列式 double(*pp)[25]=S; doubleDetS; DetS=bsdet(*pp,25);//S的行列式 //求判别函数 for(i=0;i<25;i++) X[i]=testsample[i]>0.10? 1.0: 0.0; for(i=0;i<25;i++) X[i]-=Xmeans[i]; doublet[25]; for(i=0;i<25;i++) t[i]=0; brmul(X,S_,25,t); doublet1=brmul(t,X,25); doublet2=log(Pw); doublet3=log(DetS+1); hx[n]=-t1/2+t2-t3/2; } doublemaxval=hx[0]; intnumber=0; //判别函数的最大值 for(n=1;n<10;n++) { if(hx[n]>maxval) { maxval=hx[n]; number=n; } } returnnumber; } 2.实验结果 六.实验心得 在熟悉bayes最小错误概率的决策之后,深知要学会bayes分类器的原理,基本概念,bayes公式是一个巨大的工程。 于此,明白学习此门课程需要比较高的阅读程序的能力,需要有较强的数学知识。 因此,学习是个无底洞的玩意儿,要想学好它,必须对此门课程有着较强的兴趣。 只是可惜,我对此门课程还未进入门道。 七.参考文献 杨淑莹,《图像模式识别》,清华大学出版社,2005年第一版 层次聚类——中间距离法 一.实验目的 在聚类算法的大环境下,和分类不同的是,聚类问题它在做出聚类判断前,是不知道一批样品中的每一个样品的所属类别的。 即它是不凭借任何的先验知识来进行推测的,所以聚类问题又被称之为“无监督学习”;其次,聚类算法的重点在于依靠寻找特征相似的聚合类,它实现的步骤可以归纳为三步: A.找到目标样品,并对目标样品进行标号。 B.对已经分割出来的目标样品进行特征提取。 C.采用不同的聚类算法对样品进行聚类.综合上述,我们需要掌握图像的阈值分割和图像的标识,聚类前所有样品的右下角的数值均为0;当采用一种聚类方法进行聚类后,具有相同特征属性的样品右下角的数值是相同的,等等基础知识 二.实验条件 pc机一台,vs2008软件 三.实验原理 流程图 四.实验内容 程序: /************************************************************ *函数名称Zhongjianjulifa() *参数void *返回值void *函数功能按照中间距离法对全体样品进行分类 *************************************************************/ voidCCluster: : Zhongjianjulifa() { GetFeature(); double**centerdistance;//记录类间距离 doubleT;//阈值 intdistype;//距离的形式(欧氏、余弦。 。 。 ) inti,j; doubleminous,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;i for(j=i+1;j { if(minous>GetDistance(m_pattern[i],m_pattern[j],1)) minous=GetDistance(m_pattern[i],m_pattern[j],1); if(maxous maxous=GetDistance(m_pattern[i],m_pattern[j],1); if(mincos>GetDistance(m_pattern[i],m_pattern[j],2)) mincos=GetDistance(m_pattern[i],m_pattern[j],2); if(maxcos maxcos=GetDistance(m_pattern[i],m_pattern[j],2); if(minbcos>GetDistance(m_pattern[i],m_pattern[j],3)) minbcos=GetDistance(m_pattern[i],m_pattern[j],3); if(maxbcos maxbcos=GetDistance(m_pattern[i],m_pattern[j],3); if(mintan>GetDistance(m_pattern[i],m_pattern[j],4)) mintan=GetDistance(m_pattern[i],m_pattern[j],4); if(maxtan maxtan=GetDistance(m_pattern[i],m_pattern[j],4); } DlgInformDlgInfor; mDlgInfor.ShowInfor(minous,maxous,mincos,maxcos,minbcos,maxbcos,mintan,maxtan); if(mDlgInfor.DoModal()==IDOK) { T=mDlgInfor.m_T; distype=mDlgInfor.m_DisType; } elsereturn; //初始化 for(i=0;i { m_pattern[i].category=i+1; } centerdistance=newdouble*[patternnum];//建立类间距离数组,centerdistance[i][j]表示i类和j类距离 for(i=1;i { centerdistance[i]=newdouble[patternnum+1]; } for(i=1;i for(intj=i+1;j<=patternnum;j++) { centerdistance[i][j]=GetDistance(m_pattern[i-1],m_pattern[j-1],distype); } centernum=patternnum; while (1) { doubletd,**tempdistance; intti,tj; td=MAX; ti=0; tj=0; tempdistance=newdouble*[patternnum];//临时记录类间距离 for(i=1;i { tempdistance[i]=newdouble[patternnum+1]; } for(i=1;i ti,tj,记录最小距离td; for(j=i+1;j<=centernum;j++) { if(td>centerdistance[i][j]) { td=centerdistance[
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 邻近 模板 匹配