最邻近模板匹配法

报告提交日期 2013年6 月27

报告批改日期

2013年 月

最邻近模板匹配法

一． 实验内容：

在模式识别中一个最基本的方法，就是模板匹配法(template matching)，它基本上是一种统计识别方法。 为了在图像中检测出已知形状的目标物，我们使用这个目标物的形状模板（或窗口）与图像匹配，在约定的某种准则下检测出目标物图像，通常称其为模板匹配法。它能检测出图像中上线条、曲线、图案等等。它的应用包括：目标模板与侦察图像相匹配；文字识别和语音识别等。

二. 实验条件 pc机一台，vs2008软件

三.实验原理

我们采用以下的算式来衡量模板T（m,n)与所覆盖的子图Sij（i,j)的关系，已知原始图像S(W,H)，如图所示：

利用以下公式衡量它们的相似性：

上述公式中第一项为子图的能量，第三项为模板的能量，都和模板匹配无关。第二项是模板和子图的互为相关，随（i,j）而改变。当模板和子图匹配时，该项由最大值。在将其归一化后，得到模板匹配的相关系数：

1

当模板和子图完全一样时，相关系数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

2.程序

number_no Classification::LeastDistance() {

double min=10000000000; 定义一个变量存放最小值 number_no number_no;

for(int n=0;n<10;n++) 三个for循环逐一地和每个样品 { 进行距离计算，并把最小距离值 for(int i=0;i

if(pipei(pattern[n].feature[i],testsample)

//匹配的最小值

min=pipei(pattern[n].feature[i],testsample); number_no.number=n;//样品类别 number_no.no=i;//样品序号 } } }

return number_no;//返回手写数字的类别和序号 将最小距离对应的类别号返

} 回

五，实验结果分析

识别数字：

3

算法实现的关键问题是进行匹配，求最小距离，其解决方法是和训练集的样品逐一进行距离的计算，最后找出最相邻的样品得到类别号。

六.实验心得

针对每一种模式识别技术。老师讲解了理论基础，实现步骤，编程代码三部分，了解了基本理论之后，按照实现步骤的指导，可以了解算法的实现思路和方法，再进一步体会核心代码。但由于对C++掌握不是太好，所有算法都是用VC++编程实现的，所以对模式识别技术的掌握还是不够好。研究程序代码是枯燥无味的，但只要用心去学，研究，还是能收获自己想要的结果，也会拥有不一样的快乐。别人的思想要做到学以致用，同时自己也要学会绝一反三。希望以后低年级的教学安排中，能早一点多学点相关的软件基础，平时老师能给我们学生一部分相关的作业作为练习。之后能细致的讲解和辅导。当然，我们自己也应该更加努力课下阅读学习相关的书籍知识。

七. 参考文献

杨淑莹，《图像模式识别》，清华大学出版社，2005年第一版

Bayes分类器——最小错误概率的Bayes方法

一. 实验目的：

1. 对模式识别有一个初步的理解，能够根据自己的设计对贝叶斯决策理论算法有一个深刻地

认识；

2. 理解二类分类器的设计原理。

二. 实验条件 pc机一台，vs2008软件

三．实验原理

1. 目标： 计算分析：

。

4

由于数据t是一个新的数据，的贝叶斯定理

无法在训练数据集中统计出来。因此需要转换。根据概率论中

将

的计算转换为：

其中，集中出现的频率

首先，对于

（1）

表示类Cj在整个数据空间中的出现概率，可以在训练集中统计出来（即用Cj在训练数据

来作为概率，它表示在类

。但

和

仍然不能统计出来。

中出现数据t的概率。根据“属性独立性假设”，即对于属于类

的所有数据，它们个各属性出现某个值的概率是相互独立的。如，判断一个干部是否是“好干部”（分类）时，其属性“生活作风＝好”的概率（P(生活作风＝好|好干部)）与“工作态度＝好”的概率（P(工作态度＝好|好干部)）是独立的，没有潜在的相互关联。换句话说，一个好干部，其生活作风的好坏与其工作态度的好坏完全无关。我们知道这并不能反映真实的情况，因而说是一种“假设”。使用该假设来分类的方法称为“朴素贝叶斯分类”。

根据上述假设，类

中出现数据t的概率等于其中出现t的各属性值的概率的乘积。即：

其中，

是数据t的第k个属性值。

，即数据t在整个数据空间中出现的概率，等于它在各分类中出现概率

（2）

其次，对于公式（1）中的的总和，即：

其中，各

的计算就采用公式（2）。

（3）

这样，将（2）代入（1），并综合公式（3）后，我们得到：

（4）

5

公式（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个进行等分，计算各值域分段中的标准值。

其中，m表示一个分段，

（5）

表示第k个属性值在该段内的数据的总数。

每段内的数据的相应属性重设为该段的平均值。

分段的工作在在训练阶段进行。必须保留分段的结果：即各属性的各分段值域的标准值。在训练阶段，将所有训练数据的属性值替换为标准值后，再进行统计。而在识别阶段，将待识别数据的属性值同样替换为标准值后，再进行识别。

6

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。

(

表示

试对观察的结果进行分类。

7

五. 程序和实验结果

1.实验程序

/****************************************************************** * 函数名称：BayesLeasterror() * 函数类型：int

* 函数功能：最小错误概率的Bayes分类器,返回手写数字的类别

******************************************************************/ int Classification::BayesLeasterror() { double X[25];//待测样品 double Xmeans[25];//样品的均值 double S[25][25];//协方差矩阵 double S_[25][25];//S的逆矩阵 double Pw;//先验概率 double hx[10];//判别函数

int i,j,k,n;

for(n=0;n<10;n++)//循环类别～ { int num=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; //求协方差矩阵 double mode[200][25]; for(i=0;i

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++) { double s=0.0;

for(k=0;k

8

s=s+(mode[k][i]-Xmeans[i])*(mode[k][j]-Xmeans[j]);

s=s/(double)(num-1); S[i][j]=s;

}

//求先验概率 int total=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; double DetS;

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]; double t[25]; for(i=0;i<25;i++)

t[i]=0; brmul(X,S_,25,t); double t1=brmul(t,X,25); double t2=log(Pw); double t3=log(DetS+1); hx[n]=-t1/2+t2-t3/2;

}

double maxval=hx[0]; int number=0; //判别函数的最大值 for(n=1;n<10;n++) { if(hx[n]>maxval) {

maxval=hx[n];

9

}

}

}

number=n;

return number;

2.实验结果

六. 实验心得

在熟悉bayes最小错误概率的决策之后，深知要学会bayes分类器的原理，基本概念，bayes公式是一个

10

巨大的工程。于此，明白学习此门课程需要比较高的阅读程序的能力，需要有较强的数学知识。因此，学习是个无底洞的玩意儿，要想学好它，必须对此门课程有着较强的兴趣。只是可惜，我对此门课程还未进入门道。

七. 参考文献

杨淑莹，《图像模式识别》，清华大学出版社，2005年第一版

层次聚类——中间距离法

一．实验目的

在聚类算法的大环境下，和分类不同的是，聚类问题它在做出聚类判断前，是不知道一批样品中的每一个样品的所属类别的。即它是不凭借任何的先验知识来进行推测的，所以聚类问题又被称之为“无监督学习”； 其次，聚类算法的重点在于依靠寻找特征相似的聚合类，它实现的步骤可以归纳为三步：A．找到目标样品，并对目标样品进行标号。B．对已经分割出来的目标样品进行特征提取。C．采用不同的聚类算法对样品进行聚类.综合上述，我们需要掌握图像的阈值分割和图像的标识，聚类前所有样品的右下角的数值均为0；当采用一种聚类方法进行聚类后，具有相同特征属性的样品右下角的数值是相同的，等等基础知识

二. 实验条件 pc机一台，vs2008软件

三．实验原理

流程图

11

四．实验内容

程序：

/************************************************************ *函数名称 Zhongjianjulifa() *参数

void *返回值 void

*函数功能

按照中间距离法对全体样品进行分类

*************************************************************/ void CCluster::Zhongjianjulifa() { GetFeature();

double

**centerdistance;//记录类间距离

12

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; maxcos=0; maxbcos=0; maxtan=0; //计算四种距离模式的参考值 for ( i=0;iGetDistance(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);

}

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;i

13

{ m_pattern[i].category=i+1;

}

centerdistance=new double *[patternnum];//建立类间距离数组，centerdistance[i][j]表示i类和j类距离 for ( i=1;i

for ( i=1;i

}

centernum=patternnum; while(1) { double td,**tempdistance; int ti,tj; td=MAX; ti=0; tj=0;

tempdistance= new double *[patternnum];//临时记录类间距离 for (i=1;i

}

for( i=1;icenterdistance[i][j])

{ td=centerdistance[i][j]; ti=i;tj=j;

}

}

if(td

{

14

for ( i=0;i

centernum--;

for (i=1;i

for ( j=i+1;j<=centernum;j++) {

if (i

if(j==ti)

tempdistance[i][j]=sqrt

if (m_pattern[i].category==tj)

m_pattern[i].category=ti; m_pattern[i].category--; if (m_pattern[i].category>tj)

(centerdistance[i][ti]*centerdistance[i][ti]/2+centerdistance[i][tj]*centerdistance[i][tj]/2-centerdistance[ti][tj]*centerdistance[ti][tj]/4);

}

else if (i==ti) {

if (j

tempdistance[i][j]=sqrt else if (j>=tj)

tempdistance[i][j]=centerdistance[i][j+1]; tempdistance[i][j]=centerdistance[i][j]; else

(centerdistance[ti][j]*centerdistance[ti][j]/2+centerdistance[j][tj]*centerdistance[j][tj]/2-centerdistance[ti][tj]*centerdistance[ti][tj]/4); else

tempdistance[i][j]=sqrt

(centerdistance[ti][j+1]*centerdistance[ti][j+1]/2+centerdistance[tj][j+1]*centerdistance[tj][j+1]/2-centerdistance[ti][tj]*centerdistance[ti][tj]/4);

}

else if((i>ti)&&(i

else //i>=tj {

if(j

tempdistance[i][j]=centerdistance[i][j]; tempdistance[i][j]=centerdistance[i][j+1]; else

15

tempdistance[i][j]=centerdistance[i+1][j+1];

}

}

for (i=1;i

for ( j=i+1;j<=centernum;j++) { centerdistance[i][j]=tempdistance[i][j];

}

}

else break;

delete []tempdistance;

}

delete []centerdistance;

}

五．结果分析

16

结果分析：

存在问题及改进设想

每个物体的左上角标号是物体的标号，右下角是该物体的所属号。最大最小距离法不需要用户输入聚类阈值，只需要输入距离计算类型即可，选择距离公式，并输入阈值，程序会根据所有样品数据自动确定阈值。若样品集中没有突出的噪声，程序一般会正确聚类，然而，当样品中含有离中心较远的孤立点时，聚类阈值会受到干扰。

通过比较可以看出的是，在最大最小距离算法中，“Tanimoto距离”聚类的结果是最不准确的，造成这种不准确性的原因在最邻近规则试探法中得以体现：样品间最小距离是1，最大距离也是1，阈值大小影响结果为0.因为Tanimoto表示的是两类物体的交集除以它们的并集。故当Tanimoto系数值为1时，说明两类样品的特征是一样的，所以最后显示的聚类结果就如上图所示（全部都是同类样品）。

六．实验心得

通过本学期的模式识别实验，了解了模式识别属于当代高科技研究的重要领域，是一门独立的新学科。了解了各种相关的算法，和模式识别现在重要的理论和方法

在本次开发学习中，让我熟悉了C++语言中类的功能，深入学习了模板匹配算法及实现过程，该算法是一种最简单的识别方法，可是存在一个缺点就是待测目标需要与训练集的每一个样品进行匹配运算，运算量极大。

七. 参考文献

杨淑莹，《图像模式识别》，清华大学出版社，2005年第一版

17

对课程的建议；

感谢老师一直以来费心为教学课程改革想办法动脑筋，作为学生，感到很感激，同时，也是非常的内疚。我并没有花太对的心思在这个课程之上。

我觉得，这是一个蛮有难度的课程，包括数学功底，程序理解能力等等。因此，我觉得非常建议从大一开始学习c语言，并且能够多方面的锻炼学生在程序理解能力，这是对于刚开始学习计算机必须要的基础。

要做好一件事情，最好的办法就是兴趣，怎么把学生的兴趣提上来，这才是老师应该做的，这不单单只是换个课本那么容易，这需要老师们能够深入的改革教学方式，把学生变被动为主动。就如，大学教育就是一项服务，为学生提供让他们感兴趣的平台，同时，老师能够在这个平台上引导学生走下去。

因此，引导他们对这门课程的认识，对这门课程的发展前景，和引导他们加入实验或者是老师的各项项目反而比上课叫他们的知识更重要也更有意思。

再次谢谢老师。

学生：谢瑜

18

本文来源：https://www.bwwdw.com/article/1row.html