3.3识别与解释.ppt

《3.3识别与解释.ppt》由会员分享，可在线阅读，更多相关《3.3识别与解释.ppt（69页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、3 3.3 3 识识别别与与解解释释图像分析技术分类的三种基本范畴知识库知识库分割分割表示与描述表示与描述识别识别与与解释解释预处理预处理图像获取图像获取低级处理高级处理中级处理结果问题3.图像处理与分析3 3.3 3 识识别别与与解解释释3.3 识别与解释3.3.1 3.3.1 模式与模式类模式与模式类3.3.2 3.3.2 统计模式识别统计模式识别3.3.3 3.3.3 神经网络与支持向量机神经网络与支持向量机3.3.4 3.3.4 结构模式识别结构模式识别3 3.3 3 识识别别与与解解释释图像识别与解释的基本方法图像识别与解释的基本方法统计模式识别统计模式识别：用向量形式表达模式；分派

2、模：用向量形式表达模式；分派模式向量到不同的模式类式向量到不同的模式类结构模式识别结构模式识别：用符号匹配，模式被表示为符：用符号匹配，模式被表示为符号形式（如形状数、串和树）号形式（如形状数、串和树）图像解释的方法：图像解释技术是基于谓词逻图像解释的方法：图像解释技术是基于谓词逻辑、语义网络和特定产品的系统辑、语义网络和特定产品的系统3.3 识别与解释3 3.3 3 识识别别与与解解释释3.3.1 模式与模式类1.1.模式模式的定义的定义2.2.模式类模式类的定义的定义3.3.模式识别模式识别的定义的定义4.4.常用的模式序列常用的模式序列模式特征向量模式特征向量模式串模式串模式树模式树3

3、3.3 3 识识别别与与解解释释3.3.1 模式与模式类1.1.模式模式的定义的定义模式模式是：图像中的一个是：图像中的一个对象对象或某些或某些感兴趣本感兴趣本质质的的数量或结构的描述数量或结构的描述模式模式是：由一个或多个描述子来组成，换句是：由一个或多个描述子来组成，换句话说，模式是一个话说，模式是一个描述子的序列描述子的序列（名词（名词“特特征征”经常被用来代指描述子）经常被用来代指描述子）模式模式是：是：一组特征或一组描述子一组特征或一组描述子3 3.3 3 识识别别与与解解释释2.2.模式类模式类的定义的定义模式类模式类是具有某些公共特征的模式的系列是具有某些公共特征的模式的系列模式

4、类用模式类用w w1 1,w,w2 2,w wM M表示，表示，M M是类的个数是类的个数3.3.模式识别模式识别的定义的定义根根据据图图像像中中对对象象的的特特征征组组成成的的模模式式，确确定定对对象是属于那一个模式类，即为模式识别象是属于那一个模式类，即为模式识别3.3.1 模式与模式类3 3.3 3 识识别别与与解解释释模式与模式类举例模式与模式类举例1 1）汽车的长、宽、高（）汽车的长、宽、高（L,W,HL,W,H）模式模式2 2）大客车：）大客车：（L,W,HL,W,H）大大小轿车：小轿车：（L,W,HL,W,H）小小卡卡 车：车：（L,W,HL,W,H）卡卡 从而有模式类（从而有模

5、式类（w w大大,w,w小小,w,w卡卡）3 3）从图像中发现一个对象）从图像中发现一个对象模式实例。模式实例。希希望望识识别别出出该该对对象象（L L1 1,W,W1 1,H,H1 1），是是大大客客车车、小小轿轿车车、还是卡车还是卡车模式识别模式识别3.3.1 模式与模式类3 3.3 3 识识别别与与解解释释4.4.常用的模式序列常用的模式序列三种模式序列三种模式序列:1)1)模式特征向量模式特征向量2)2)模式串模式串3)3)模式树模式树1)1)模式特征向量模式特征向量定义定义举例举例特征的选择特征的选择3.3.1 模式与模式类3 3.3 3 识识别别与与解解释释常用的模式序列常用的模式

6、序列1)1)模式特征向量的定义模式特征向量的定义描述子构成的向量描述子构成的向量模式特征向量用粗体小写字母表示，如模式特征向量用粗体小写字母表示，如x,yx,y形形式如下：式如下：其中每一个其中每一个x xi i代表第代表第i i个描述子，个描述子，n n是这种描述子的是这种描述子的数量。模式特征向量被表示为一列或表示成数量。模式特征向量被表示为一列或表示成 x=(xx=(x1 1,x,x2 2,x xn n)T T，其中其中T T指出是转秩指出是转秩x=x1x2.xn3.3.1 模式与模式类3 3.3 3 识识别别与与解解释释模式特征向量举例模式特征向量举例 假假设设我我们们想想描描述述三三

7、种种蝴蝴蝶蝶花花（多多毛毛的的、维维吉吉尼尼亚亚、多多色色的的）通通过过测测量量它它们们花花瓣瓣的的宽宽度度和和长长度度。这这里里涉涉及及一个两维的模式特征向量：一个两维的模式特征向量：其中其中x x1 1、x x2 2分别对应花瓣的长和宽分别对应花瓣的长和宽 三种模式类用三种模式类用w w1 1、w w2 2、w w3 3表示表示x=x1x23.3.1 模式与模式类3 3.3 3 识识别别与与解解释释 由于所有的花瓣在宽和长上都有某种程度由于所有的花瓣在宽和长上都有某种程度的变化，所以描述这些花瓣的模式特征向量也的变化，所以描述这些花瓣的模式特征向量也将有变化，不仅在不同的类之间，而且也在类

8、将有变化，不仅在不同的类之间，而且也在类的内部的内部在这种情况下每一种花变成二维欧几里德在这种情况下每一种花变成二维欧几里德空间的一个点空间的一个点3.3.1 3.3.1 模式与模式类模式与模式类3 3.3 3 识识别别与与解解释释3.3.1 3.3.1 模式与模式类模式与模式类1234567x x1 1 花瓣长花瓣长0.51.01.52.02.53.0 x x2 2 花瓣宽花瓣宽多毛的多毛的维吉尼亚维吉尼亚多色的多色的3 3.3 3 识识别别与与解解释释模式特征向量举例：分析模式特征向量举例：分析 对对花花瓣瓣长长宽宽的的测测量量，成成功功地地将将多多毛毛的的蝴蝴蝶蝶花花与与其其它它两两种种

9、分分离离，但但对对于于分分离离维维吉吉尼尼亚亚和和多多色色的的是是失败的。失败的。这这个个结结论论说说明明了了分分类类的的特特征征选选择择问问题题，在在这这个个问问题题中中，类类的的可可区区别别性性的的程程度度，完完全全依依赖赖于于对对模模式尺寸测量的选择式尺寸测量的选择3.3.1 模式与模式类3 3.3 3 识识别别与与解解释释模式特征的选择模式特征的选择良好的特征应具备四个特点良好的特征应具备四个特点1.1.可区别性：对不同类别对象特征值差异明显可区别性：对不同类别对象特征值差异明显2.2.可靠性可靠性 ：对同类对象特征值比较接近：对同类对象特征值比较接近3.3.独立性独立性 ：所用的各特

10、征之间彼此统计独立：所用的各特征之间彼此统计独立4.4.数数量量少少 ：过过多多的的特特征征数数，会会使使系系统统复复杂杂度度提提高高一般特征向量的选择方法一般特征向量的选择方法尽量不选择带噪声和相关度高的特征尽量不选择带噪声和相关度高的特征先选择一组直觉上合理的特征，然后逐渐减少到最佳先选择一组直觉上合理的特征，然后逐渐减少到最佳3.3.1 模式与模式类3 3.3 3 识识别别与与解解释释2)2)模式串模式串 用于以对象特征的结构或空间关系作为用于以对象特征的结构或空间关系作为模式的识别模式的识别模式串举例：梯状的模式模式串举例：梯状的模式3.3.1 模式与模式类abaaabbb(1)S-(

11、1)S-aAaA(2)A-(2)A-bSbS (3)A-b (3)A-b3 3.3 3 识识别别与与解解释释3)3)模式树模式树 以分层目录结构排序的模式类，一般多采用树结构以分层目录结构排序的模式类，一般多采用树结构模式树举例模式树举例3.3.1 模式与模式类图像城市田园草地森林娱乐区 商业区 娱乐区 商业区城区内城市郊公路3 3.3 3 识识别别与与解解释释3.3.2 3.3.2 统计模式识别统计模式识别1.1.分类器的设计和训练分类器的设计和训练2.2.决策论法的基本概念决策论法的基本概念3.3.分类器分类器最小距离分类器最小距离分类器相关匹配分类器相关匹配分类器3 3.3 3 识识别别

12、与与解解释释3.3.2统计模式识别统计模式识别1.1.分类器的设计与训练分类器的设计与训练分类器一般设计方法分类器一般设计方法分类器对每一模式类，给出一个典型模板分类器对每一模式类，给出一个典型模板对每一个遇到的待分类对象对每一个遇到的待分类对象,计算该对象与计算该对象与个典型模板之间的相似程度个典型模板之间的相似程度相似值是对象的函数相似值是对象的函数函数取值的不同，决定对象属于那一模式类函数取值的不同，决定对象属于那一模式类3 3.3 3 识识别别与与解解释释3.3.2统计模式识别统计模式识别-分类器一般设计规则分类器一般设计规则分类器规则都转换为阈值规则分类器规则都转换为阈值规则将测量空

13、间划分成互不重叠的区域将测量空间划分成互不重叠的区域每一个模式类对应一个区域（或多个）每一个模式类对应一个区域（或多个）对象的分类函数值落在哪个区域，对象就属那类对象的分类函数值落在哪个区域，对象就属那类某些情况，某些区域为某些情况，某些区域为“无法确定无法确定”类类3 3.3 3 识识别别与与解解释释3.3.2统计模式识别统计模式识别-分类器的训练分类器的训练决策规则决定后，需要确定分类器的阈值决策规则决定后，需要确定分类器的阈值实现的方法是用一组已知对象训练分类器实现的方法是用一组已知对象训练分类器训练对象集由每类已被正确识别的部分对象组成训练对象集由每类已被正确识别的部分对象组成通过对这

14、些对象的度量，定出能够将决策面划分通过对这些对象的度量，定出能够将决策面划分成不同区域的合理阈值成不同区域的合理阈值使分类器对训练对象样本集分类准确性最高使分类器对训练对象样本集分类准确性最高3 3.3 3 识识别别与与解解释释3.3.2统计模式识别统计模式识别2.2.统计模式识别统计模式识别的基本概念的基本概念统计模式识别统计模式识别的定义的定义设：模式特征向量：设：模式特征向量：x=(xx=(x1 1,x,x2 2,x xn n)T T，对于：对于：M M个模式类个模式类 w w1 1,w,w2 2,w wM M，寻找寻找M M个个决策函数决策函数d d1 1(x),d(x),d2 2(x

15、),(x),d dM M(x(x)，具有这具有这样的特性：如果模式实例样的特性：如果模式实例x x属于模式类属于模式类w wi i,那么：那么：d di i(x(x)d dj j(x(x)j=1,2,M;j j=1,2,M;j i i换句话说，如果一个未知模式对象换句话说，如果一个未知模式对象x x属于第属于第i i个个模式类，模式类，把把x x代入所有的决策函数，代入所有的决策函数，d di i(x(x)的取值最大。的取值最大。3 3.3 3 识识别别与与解解释释3.3.2统计模式识别统计模式识别-决策边界决策边界的定义的定义对于模式特征向量对于模式特征向量x x，如果决策函数值有：如果决策

16、函数值有：d di i(x(x)-)-d dj j(x(x)=0)=0 此此x x向量，被称为向量，被称为w wi i与与w wj j的决策边界。的决策边界。通常用一个单一的函数标识两个类之间的通常用一个单一的函数标识两个类之间的决策决策边界边界，定义为：，定义为：d dijij(x(x)=)=d di i(x(x)-)-d dj j(x(x)=0)=0 如果如果 d dijij(x(x)0)0 x x 属于类属于类w wi i 如果如果 d dijij(x(x)0)0 x x 属于类属于类w wj j3 3.3 3 识识别别与与解解释释3.3.2统计模式识别统计模式识别3.3.分类器分类器最

17、小距离分类器最小距离分类器 以蝴蝶花的例子为例：以蝴蝶花的例子为例：（1 1）为为多多色色（w w1 1）和和多多毛毛（w w2 2）的的两两种种蝴蝴蝶蝶花花，确定两个确定两个原形原形（或称模板）（或称模板）m m1 1和和m m2 2（2 2）对对于于一一个个未未知知模模式式向向量量x x，判判断断x x与与m m1 1和和m m2 2的的距距离离，如如果果与与m m1 1的的距距离离小小于于与与m m2 2的的距距离离，则则x x属属于于w w1 1，否则属于否则属于w w2 2。3 3.3 3 识识别别与与解解释释3.3.2统计模式识别统计模式识别1234567x1 花瓣长0.51.01

18、.52.02.53.0 x2 花瓣宽多毛的多毛的多色的多色的m1m2x3 3.3 3 识识别别与与解解释释3.3.2统计模式识别统计模式识别-最小距离分类器最小距离分类器（1 1）算法思想：）算法思想：对于对于M M个模式类个模式类 w wi i i=1,2,.,M i=1,2,.,M 为每一个模式类确定一个原形模式特征向量为每一个模式类确定一个原形模式特征向量m mi i对对于于一一个个未未知知模模式式特特征征向向量量x x，如如果果x x与与m mi i的的距距离离最小，就称，最小，就称，x x属于属于w wi i3 3.3 3 识识别别与与解解释释3.3.2统计模式识别统计模式识别-最小

19、距离分类器最小距离分类器（2 2）最小距离分类器定义（训练）：最小距离分类器定义（训练）：1 1计算模式类计算模式类w wj j的原形向量：的原形向量：m mj j=1/N=1/Nj j x j=1,2,M x j=1,2,M x x wjwj 其中其中N Nj j是属于模式类是属于模式类w wj j的模式向量的个数。的模式向量的个数。通过计算已知属于通过计算已知属于w wj j的模式特征向量的各分量的的模式特征向量的各分量的均值均值得到原形模式特征向量得到原形模式特征向量m mj j3 3.3 3 识识别别与与解解释释3.3.2统计模式识别统计模式识别 22计算计算x x 与与 m mi i

20、的距离的距离d dj j(x(x)=|x )=|x m mj j|j=1,2,M|j=1,2,M其其中中|a a|=(a(aT Ta)a)1/21/2是是欧欧几几里里德德范范式式（平平方方和和开开方）方）d dj j(x(x)=(x(x m mj j )T T (x(x m mj j )1/2 1/2 j j=1,1,2,2,M,M3 3 决策决策如如果果，d di i(x(x)=min(dmin(dj j(x(x)j j=1,1,2,2,M M就说：就说：x x 属于属于w wi i3 3.3 3 识识别别与与解解释释3.3.2统计模式识别统计模式识别为便于计算，改写成求最大的标准形式，决策

21、函数为：为便于计算，改写成求最大的标准形式，决策函数为：d dj j(x(x)=)=x xT Tm mj j 1/2m 1/2mj jT Tm mj j j=1,2,M j=1,2,M如果，如果，d di i(x(x)=)=max(dmax(dj j(x(x)j=1,2,)j=1,2,就说：就说：x x 属于属于w wi i4 4用上式得到的类用上式得到的类w wi i和和w wj j之间的之间的决策边界决策边界是：是：d dijij(x(x)=)=d di i(x(x)-)-d dj j(x(x)=x xT T（m mi i m mj j）1/2(m 1/2(mi i m mj j)T T(

22、m(mi i m mj j)=0)=03 3.3 3 识识别别与与解解释释3.3.2统计模式识别统计模式识别（3 3）举例：）举例：多色的和多毛的蝴蝶花，用多色的和多毛的蝴蝶花，用w1w1和和w2w2分别表示，分别表示，有简单的原形向量有简单的原形向量m m1 1=(4.4,1.3)=(4.4,1.3)T T m m2 2=(1.5,0.3)=(1.5,0.3)T T决策函数是：决策函数是：d d1 1(x)=x(x)=xT Tm m1 1 1/2m 1/2m1 1T Tm m1 1=4.3x4.3x1 1+1.3x+1.3x2 2 10.1 10.1d d2 2(x)=x(x)=xT Tm

23、m2 2 1/2m 1/2m2 2T Tm m2 2=1.5x1.5x1 1+0.3x+0.3x2 2 1.17 1.17决策边界的等式：决策边界的等式：d d1212(x)(x)=d d1 1(x)(x)d d2 2(x)(x)=2.8x2.8x1 1 1.0 x1.0 x2 2 8.98.9 =0 03 3.3 3 识识别别与与解解释释3.3.2统计模式识别统计模式识别1234567x1 花瓣长花瓣长0.51.01.52.02.53.0 x2 花瓣宽花瓣宽多毛的多毛的多色的多色的3 3.3 3 识识别别与与解解释释3.3.2统计模式识别统计模式识别分类器分类器相关匹配分类器相关匹配分类器(

24、1)(1)相关匹配的基本思想相关匹配的基本思想:a.a.用样板子图像直接作为模式特征（不是用描述子）用样板子图像直接作为模式特征（不是用描述子）b.b.通通过过子子图图像像与与原原图图像像直直接接进进行行相相关关计计算算，把把相相关关计算作为决策函数计算作为决策函数c.c.相关计算获得最大值的位置，就被认为匹配成功相关计算获得最大值的位置，就被认为匹配成功3 3.3 3 识识别别与与解解释释3.3.2统计模式识别统计模式识别相关匹配分类器相关匹配分类器(1)(1)相关匹配基本思想相关匹配基本思想3 3.3 3 识识别别与与解解释释3.3.2统计模式识别统计模式识别分类器分类器相关匹配分类器相关

25、匹配分类器Mx原点原点Nyf(x,y)(s,t)Jsw(x+s,y+t)Kt3 3.3 3 识识别别与与解解释释3.3.2统计模式识别统计模式识别分类器分类器相关匹配分类器相关匹配分类器(2)(2)算法描述算法描述决策函数是相关函数决策函数是相关函数c(s,t)=c(s,t)=f(x,y)w(x+s,y+tf(x,y)w(x+s,y+t)x y x y 对图像的每一个点进行相关计算，只计算重叠部分对图像的每一个点进行相关计算，只计算重叠部分问问题题：在在边边界界处处将将失失去去准准确确性性，其其误误差差与与子子图图像像的的尺寸成正比尺寸成正比3 3.3 3 识识别别与与解解释释3.3.2统计模

26、式识别统计模式识别相关匹配分类器相关匹配分类器(3)(3)改进改进相相关关函函数数对对振振幅幅的的变变化化太太敏敏感感，f(x,y)f(x,y)加加倍倍，c(s,t)c(s,t)也加倍。用也加倍。用相关系数函数相关系数函数代替代替相关函数相关函数 f(x,y)f(x,y)w(x-s,y-t)wf(x,y)f(x,y)w(x-s,y-t)w(s,t)(s,t)=f(x,y)f(x,y)f(x,y)f(x,y)2 2w(x-s,y-t)w(x-s,y-t)ww2 2 1/21/2 x yx y x yx y(s,t)(s,t)的值域为（的值域为（-1-1，1 1）3 3.3 3 识识别别与与解解释

27、释3.3.2统计模式识别统计模式识别相关匹配分类器相关匹配分类器(4)(4)对旋转和比例变化的分析对旋转和比例变化的分析问题：问题：当当被被匹匹配配图图像像中中，对对象象的的尺尺寸寸和和角角度度与与模模式式不不一一致致，此此方方法将失效。法将失效。改进：改进：尺寸的正则化，解决空间比例的问题。正则化模板与原图。尺寸的正则化，解决空间比例的问题。正则化模板与原图。如如果果知知道道原原图图像像的的旋旋转转角角度度，我我们们可可以以通通过过旋旋转转原原图图像像，对对齐模式解决。齐模式解决。结论结论:如果被匹配的对象的角度任意，此方法不能用于这种问题。如果被匹配的对象的角度任意，此方法不能用于这种问题

28、。3 3.3 3 识识别别与与解解释释3.3.2统计模式识别统计模式识别分类器分类器相关性匹配分类器相关性匹配分类器(5)(5)关于空域计算关于空域计算相关函数，可以在频域计算。相关函数，可以在频域计算。f(x,y)f(x,y)w(x,y)w(x,y)f(s,t)w(s,t)f(s,t)w(s,t)但但无无论论在在何何种种情情况况下下，都都没没有有更更有有优优势势的的理理论论根根据。相关系数方式只能在空域进行。据。相关系数方式只能在空域进行。3 3.3 3 识识别别与与解解释释3.3.33.3.3神经网络和支持向量机神经网络和支持向量机 （1）感知机（2）支持向量机3 3.3 3 识识别别与与

29、解解释释（1）感知机 最基本的感知机建立能将两个线性可分训练集分开的线性决策函数3 3.3 3 识识别别与与解解释释对模式矢量增加第n+1个元素构建一个扩充模式矢量y，让yi=xi，i=1,2,n，且后面加一个元素yn+1=1其中y=y1 y2 yn 1T是个扩充模式矢量，w=w1 w2 wn wn+1T是个权矢量关键问题：用模式矢量的给定训练集确定w （1）感知机 3 3.3 3 识识别别与与解解释释1）.线性可分类线性可分类由两个线性可分训练集获取权矢量令w(1)代表一个任意选定的初始权矢量如果 y(k)s1，wT(k)y(k)0 如果 y(k)s2，wT(k)y(k)0否则：（1）感知机

30、 3 3.3 3 识识别别与与解解释释1）.线性可分类线性可分类两个训练集，每个包括两个模式 先将模式扩充，对类s1得到训练集0 0 1T,0 1 1T，对类s2得到训练集1 0 1T,1 1 1T（1）感知机 3 3.3 3 识识别别与与解解释释（1）感知机 训练算法示例训练算法示例3 3.3 3 识识别别与与解解释释（1）感知机 训练算法示例训练算法示例3 3.3 3 识识别别与与解解释释2）.线性不可分类线性不可分类最小化实际响应和希望响应间的误差 沿J(w)负梯度的方向逐步增加w以寻找上述函数的最小值。最小值应在r=wTy时出现通用的梯度下降算法可写成：（1）感知机 3 3.3 3 识

31、识别别与与解解释释2）.线性不可分类线性不可分类写成德尔塔（Delta）校正算法的形式权矢量的误差误差的变化量改变权重能将误差减少a|y(k)|2，下一轮继续（1）感知机 3 3.3 3 识识别别与与解解释释（1）感知机 3 3.3 3 识识别别与与解解释释（2）支持向量机 1.线性可分类线性可分类线性分类器的设计目的：要设计一个超平面 满足条件的超平面一般不惟一 离开两个类都比较远的超平面分类的结果会更好些，可能的错误率也会更小一些3 3.3 3 识识别别与与解解释释1.线性可分类线性可分类对每个朝向，与两个类距离相等的超平面应该是与两个类都有最大距离的超平面确定能给出类距离最大的朝向的超平

32、面从一个点到一个超平面的距离 （2）支持向量机 3 3.3 3 识识别别与与解解释释1.线性可分类线性可分类对每个类si，记其标号为ti，其中t1=1，t2=1。现在问题变为：计算超平面的w和w0，在满足下列条件的情况下最小化用拉格朗日乘数法来解（2）支持向量机 3 3.3 3 识识别别与与解解释释1.线性可分类线性可分类结果为最优解的向量参数w是Ns个（Ns N）与li 0相关的特征向量的线性组合（支持向量）支持向量机：最优的超平面分类器 （2）支持向量机 3 3.3 3 识识别别与与解解释释2.线性不可分类线性不可分类训练特征向量可以分成以下三类：(1)向量落在分类带之外且被正确地分了类(

33、2)向量落在分类带之内且被正确地分了类(3)向量被错误地分了类 （2）支持向量机 3 3.3 3 识识别别与与解解释释3.3.4 结构模式识别1.匹配形状数2.匹配串3 3.3 3 识识别别与与解解释释3.3.4结构模式识别 统计模式识别统计模式识别，通过量化的方法处理，通过量化的方法处理模式，最大限度地忽略了模式形状的内在模式，最大限度地忽略了模式形状的内在结构关系。结构关系。结构模式识别结构模式识别，则力求通过准确地抓，则力求通过准确地抓住这些不同模式类的内在结构关系来进行住这些不同模式类的内在结构关系来进行模式识别。模式识别。3 3.3 3 识识别别与与解解释释3.3.4结构模式识别1.

34、1.匹配形状数匹配形状数(1)(1)匹配形状数的基本思想匹配形状数的基本思想 通通过过比比较较两两个个对对象象边边界界的的形形状状数数的的相相似似程程度，来匹配对象。例如：度，来匹配对象。例如：未知模式未知模式原形模式类原形模式类3 3.3 3 识识别别与与解解释释3.3.4结构模式识别匹配形状数匹配形状数(2)(2)基本概念基本概念-相似级别相似级别 a.a.两个区域边界的两个区域边界的相似级别相似级别k k的定义：的定义：用相同形状数的用相同形状数的最大序号最大序号表示：即：表示：即：当当考考虑虑用用4 4向向链链码码表表示示的的封封闭闭区区域域边边界界的的形形状状数数时，时，A A和和B

35、 B具有相似级别具有相似级别k k，当且仅当满足：当且仅当满足：s s4 4(A)=s(A)=s4 4(B),s(B),s6 6(A)=s(A)=s6 6(B),(B),s s8 8(A)=s(A)=s8 8(B),(B),s sk k(A(A)=)=s sk k(B(B),),s sk+2k+2(A)(A)s sk+2k+2(B),s(B),sk+4k+4(A)(A)s sk+4k+4(B),(B),，这里这里s s表示形状数表示形状数,下标表示序号。下标表示序号。3 3.3 3 识识别别与与解解释释3.3.4结构模式识别匹配形状数匹配形状数(2)(2)基本概念基本概念-形状数的距离形状数的

36、距离b.b.两个区域边界两个区域边界A A和和B B形状数的距离形状数的距离D(A,B)D(A,B)相似级别的倒数相似级别的倒数 ：D(A,B)=1/kD(A,B)=1/k 距离满足如下性质距离满足如下性质：D(A,B)D(A,B)0 0D(A,B)=0 D(A,B)=0 iffiff A=B A=BD(A,C)D(A,C)maxD(A,B),D(B,C)maxD(A,B),D(B,C)3 3.3 3 识识别别与与解解释释3.3.4结构模式识别匹配形状数匹配形状数(3)(3)算法思想算法思想a.a.用用不不同同密密度度的的网网格格划划分分边边界界区区域域，获获得得不不同序数的形状数。同序数的形

37、状数。b.b.如果使用相似级别如果使用相似级别k k，k k越大说明越相似。越大说明越相似。c.c.如果使用相似距离如果使用相似距离D D，D D越小说明越相似越小说明越相似d.d.可以利用相似树来进行判别可以利用相似树来进行判别3 3.3 3 识识别别与与解解释释3.3.4结构模式识别匹配形状数匹配形状数（4 4）举例举例假假设设我我们们有有一一个个形形状状F F，想想在在另另5 5个个形形状状（A A，B B，C C，D D，E E）中找到与其最相似的形状中找到与其最相似的形状ABCDEF3 3.3 3 识识别别与与解解释释3.3.4结构模式识别 这个问题类似于有五个原型形状，想找出一个给

38、定的尚这个问题类似于有五个原型形状，想找出一个给定的尚不确定的形状的最佳匹配的问题。这个问题可以利用相似树不确定的形状的最佳匹配的问题。这个问题可以利用相似树和矩阵来可视化和矩阵来可视化468101214ABCDEFABCDEFBCDEFAAAABECFBEDDDCFCF BEA B C D E FABEDCF 6 6 6 6 6 8 8 10 8 8 8 12 8 8 8 3 3.3 3 识识别别与与解解释释3.3.4结构模式识别2.2.串匹配串匹配（1 1）串匹配的基本思想）串匹配的基本思想 比较两个边界串编码的相似程度，来进行匹配比较两个边界串编码的相似程度，来进行匹配（2 2）三个基本

39、概念）三个基本概念设设:两个区域边界两个区域边界A A和和B B已分别被编码已分别被编码 为串为串a a1 1a a2 2aan n和和b b1 1b b2 2b bm m。a3a3a3a3a3a3a3a3a2a2a3a33 3.3 3 识识别别与与解解释释3.3.4结构模式识别串匹配串匹配a.a.两个串的两个串的匹配数匹配数M:M:当当 a ak k=b bk k 时时我我们们说说发发生生了了一一个个匹匹配配。令令M M代表代表A A、B B中匹配的总数。中匹配的总数。b.b.不匹配的符号数量不匹配的符号数量Q Q：Q=maxQ=max（|A|A|，|B|B|）-M-M 这里这里|argar

40、g|是字符串的长度。当且仅当是字符串的长度。当且仅当A A和和B B完全相同时，完全相同时，Q=0Q=0。3 3.3 3 识识别别与与解解释释3.3.4结构模式识别串匹配串匹配 c.Ac.A和和B B相似度的简便衡量相似度的简便衡量R:R:R=M/Q=M/max(|A|,|B|)-MR=M/Q=M/max(|A|,|B|)-M 因此，因此，当当A A和和B B完全匹配时，完全匹配时，R=R=；当当A A和和B B中任何字符都不匹配时，中任何字符都不匹配时，M=0M=0，R=0R=0。3 3.3 3 识识别别与与解解释释3.3.4结构模式识别串匹配串匹配（3 3）算法思想）算法思想a.a.由于匹

41、配是逐字符进行的，由于匹配是逐字符进行的，b.b.选选择择一一个个好好的的开开始始点点，可可以以大大大大减减少少计计算算量量。任任何何将将两两个个串串规规则则化化为为相相同同字字符符开开头头的的方方法法都都是是有有效效的的，只只要这种方法不是穷举起点。要这种方法不是穷举起点。c.c.最大的最大的R R给出了最好的匹配。给出了最好的匹配。3 3.3 3 识识别别与与解解释释3.3.4结构模式识别串匹配（4）举例对象1.a对象2.a3 3.3 3 识识别别与与解解释释3.3.4结构模式识别串匹配串匹配现有两个模式类：现有两个模式类：模式类模式类1 1：有：有1.b1.b、1.c1.c、1.d1.d

42、、1.e1.e、1.f1.f 5 5个个模板模板模式类模式类2 2：有：有2.b2.b、2.c2.c、2.d2.d、2.e2.e、2.f2.f 5 5个模板个模板3 3.3 3 识识别别与与解解释释3.3.4结构模式识别串匹配串匹配现现将将对对象象1.a1.a与与模模式式类类1 1的的5 5个个样样例例做做串串匹匹配配，有相似度有相似度R R值的结果表：值的结果表：1.b 1.c 1.d 1.e 1.f1.b 1.c 1.d 1.e 1.f1.a1.a 16.0 9.6 5.07 4.67 4.6716.0 9.6 5.07 4.67 4.673 3.3 3 识识别别与与解解释释3.3.4结构

43、模式识别串匹配串匹配现现将将对对象象2.a2.a与与模模式式类类2 2的的5 5个个样样例例做做串串匹匹配配，有相似度有相似度R R值的结果表：值的结果表：2.b 2.c 2.d 2.e 2.f2.b 2.c 2.d 2.e 2.f2.a2.a 33.5 4.75 3.6 2.83 2.6333.5 4.75 3.6 2.83 2.633 3.3 3 识识别别与与解解释释3.3.4结构模式识别 将对象将对象1.a1.a与与模式类模式类2 2的的5 5个样例做串匹配，有个样例做串匹配，有R R值的结果表值的结果表：2.a 2.b 2.c 2.d 2.e 2.f2.a 2.b 2.c 2.d 2.e 2.f1.a1.a 1.241.24 1.18 1.02 1.02 0.93 .891.18 1.02 1.02 0.93 .89 将将对对象象2.a2.a与与模模式式类类1 1的的5 5个个样样例例做做串串匹匹配配有有R R值的结果表：值的结果表：1.a 1.b 1.c 1.d 1.e 1.f1.a 1.b 1.c 1.d 1.e 1.f2.a2.a 1.241.24 1.50 1.32 1.47 1.55 1.481.50 1.32 1.47 1.55 1.48