【教学课件】第11章图象模式识别.ppt

《【教学课件】第11章图象模式识别.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第11章图象模式识别.ppt（42页珍藏版）》请在三一办公上搜索。

1、第11章图象模式识别,11.1模式和分类11.2统计模式识别 11.3感知机和支持向量机 11.4结构模式识别,11.1模式和分类,1.模式和模式矢量模式是一个广泛的概念，模式由一个或多个模式符（也可叫特征）组成模式类由具有共同特性的模式组成图象模式可定义为对图象中的目标或其它感兴趣部分定量或结构化的描述矢量是一种定量描述模式的表达方式,11.1模式和分类,传统的模式识别一般指对客观事物进行分析，做出判断的过程现在常用模式识别指用计算机就人类对周围世界的客体、过程和现象的识别功能进行自动模拟的学科模式识别主要有三个分支：统计模式识别，结构（句法）模式识别，模糊模式识别,11.1模式和分类,2.

2、模式分类对给定的M个模式类s1,s2,sM，确定M个判别函数d1(x),d2(x),dM(x)。如果一个模式x属于类si，则如果对x的值，有di(x)=dj(x)，则得到将类i与类 j分开的决策边界,11.2统计模式识别,根据模式统计特性确定决策函数选取特征表达模式设计分类器进行分类 最小距离分类器最优统计分类器,最小距离分类器,每个模式类用一个均值矢量表示 利用欧氏距离来确定接近程度如果Dj(x)是最小的距离，则将x赋给类sj等价于计算在dj(x)给出最大值时将x赋给类sj,最小距离分类器,类si和sj之间的决策边界 给出一个连接mi和mj线段的垂直二分界M=2，垂直二分界是一条线M=3，垂

3、直二分界是一个平面M 3，则垂直二分界是一个超平面 仅由d12(x)的符号就可判断模式属于哪个类,例A.2.2,例A.2.3,最优统计分类器,1.最优统计分类原理 在平均意义上产生最小可能分类误差 令p(si|x)代表一个特定的模式x属于类si的概率，如果模式分类器判别x属于sj，但事实上x属于si，则分类器犯了一个误检错误，记为Lij将x赋给sj产生的平均损失是（条件平均风险损失）,最优统计分类器,1.最优统计分类原理 平均风险的表达式 贝叶斯分类器：能最小化总平均损失的分类器ri(x)rj(x),最优统计分类器,1.最优统计分类原理 损失函数贝叶斯分类器：满足下面条件时将x赋给类si 贝叶

4、斯分类器的判决函数,最优统计分类器,2.用于高斯模式类的贝叶斯分类器 贝叶斯决策函数：,最优统计分类器,2.用于高斯模式类的贝叶斯分类器 在n-D情况下：利用均值近似期望值如果xj和xk统计上是独立的，Cjk=0，此时多变量高斯密度函数简化为x的各个元素的单变量高斯密度的乘积,最优统计分类器,2.用于高斯模式类的贝叶斯分类器 采用自然对数形式来表达：对数是单增函数，所以分类效果等价如果所有的协方差矩阵都相等,最优统计分类器,2.用于高斯模式类的贝叶斯分类器 如果C 为单位矩阵，P(sj)=1/M：最小距离分类器在贝叶斯意义上最优：模式类是高斯的所有协方差矩阵都与单位矩阵相等所有类出现的几率相等

5、,最优统计分类器,2.用于高斯模式类的贝叶斯分类器 超球体：高斯模式类是n-D中的球状体超平面：最小距离分类器将两类分开的决策面为 d1(x)d2(x)=8x1 8x2 8x3+4=0,11.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.线性可分类由两个

6、线性可分训练集获取权矢量令w(1)代表一个任意选定的初始权矢量如果 y(k)s1，wT(k)y(k)0 如果 y(k)s2，wT(k)y(k)0否则：,感知机,1.线性可分类两个训练集，每个包括两个模式 先将模式扩充，对类s1得到训练集0 0 1T,0 1 1T，对类s2得到训练集1 0 1T,1 1 1T,感知机,2.线性不可分类最小化实际响应和希望响应间的误差 沿J(w)负梯度的方向逐步增加w以寻找上述函数的最小值。最小值应在r=wTy时出现通用的梯度下降算法可写成：,感知机,2.线性不可分类写成德尔塔（Delta）校正算法的形式权矢量的误差误差的变化量改变权重能将误差减少a|y(k)|2

7、，下一轮继续,支持向量机,1.线性可分类线性分类器的设计目的：要设计一个超平面 满足条件的超平面一般不惟一 离开两个类都比较远的超平面分类的结果会更好些，可能的错误率也会更小一些,支持向量机,1.线性可分类对每个朝向，与两个类距离相等的超平面应该是与两个类都有最大距离的超平面确定能给出类距离最大的朝向的超平面从一个点到一个超平面的距离,支持向量机,1.线性可分类对每个类si，记其标号为ti，其中t1=1，t2=1。现在问题变为：计算超平面的w和w0，在满足下列条件的情况下最小化用拉格朗日乘数法来解,支持向量机,1.线性可分类结果为最优解的向量参数w是Ns个（Ns N）与li 0相关的特征向量的

8、线性组合（支持向量）支持向量机：最优的超平面分类器,支持向量机,2.线性不可分类训练特征向量可以分成以下三类：(1)向量落在分类带之外且被正确地分了类(2)向量落在分类带之内且被正确地分了类(3)向量被错误地分了类,11.4结构模式识别,句法模式识别一组模式基元，一组确定这些基元相互作用的规则和一个识别器（称为自动机）字符串结构识别树结构识别 学习和推理,字符串结构识别,1.字符串文法 文法（语法）：一组句法规则，控制字符集中符号产生句子的过程语言：由一个文法G所产生的一组句子，记为L(G)句子：符号的串，代表模式，语言对应模式类文法G1中的句法规则只允许产生对应类s1中模式的句子，文法G2中

9、的句法规则只允许产生对应类s2中模式的句子 识别：对一个表示未知模式的句子，决定在哪个语言中模式表示了一个可成立的句子,字符串结构识别,1.字符串文法 定义一个四元组：N为一个有限的变量集，称为非终结符号集用大写字母A,B,S,代表非终结符号 T为一个有限的常量集，称为终结符号集用小写字母a,b,c,表示终结符号 P是一组称为产生式的重写规则集S在N中，称为起始符号,字符串结构识别,1.字符串文法 字符串文法的特点由产生式规则的形式决定：规则文法 产生式规则：A aB或A a前后文无关文法它只包含形式为A a的产生式规则，a 在集(N T)*l 中a 可以是除了空集以外的由终结符号和非终结符号

10、组成的任何字符串,字符串结构识别,1.字符串文法 文法G=(N,T,P,S)N=A,B,C，T=a,b,cP=S aA,A bA,A bB,B c S aA abA abbA abbbA abbbbA abbbbbB abbbbbc 语言：L(G)=abnc|n 1，bn代表b的n次重复,字符串结构识别,2.语义应用 句法确定了目标的结构，而语义主要与其正确性有关 通过使用语义信息，可用较少的句法规则以描述较广泛（但是有限）的模式类,字符串结构识别,3.用自动机作为字符串识别器 自动机能识别一个输入模式字符串是否属于与自动机关联的语言有限自动机：由规则语法产生的语言识别器Q是一个有限的非空状态

11、集；T 是一个有限的输入字符集；d 是一个从Q T（即由Q和T的元素组成的排序对集合）到所有Q子集的映射；q0是初始状态；F（Q的一个子集）是一个最终或可接收状态的集合,字符串结构识别,3.用自动机作为字符串识别器 有限自动机状态图 Q=q0,q1,q2T=a,bF=q0映射规则：d(q0,a)=q2，d(q0,b)=q1，d(q1,a)=q2，d(q1,b)=q0，d(q2,a)=q0，d(q2,b)=q1 能识别字符串abbabb，但不能识别字符串aabab,字符串结构识别,3.用自动机作为字符串识别器 规则文法和有限自动机之间一一对应 用G=(N,T,P,X0)代表文法，其中X0 S，设

12、N由X0和n个非终结符号X1,X2,Xn组成。对自动机，Q由n+2个状态 q0,q1,qn,qn+1 组成，其中当0 i n时，qi对应Xi，且qn+1是终结状态。输入符号集与G中的终结集相同，d 中的映射规则是用两个基于G中的产生式得到的(1)如果Xi aXj在P中，那么d(qi,a)包括qj(2)如果Xi a在P中，那么d(qi,a)包括qn+1,字符串结构识别,3.用自动机作为字符串识别器 规则文法和有限自动机之间一一对应给定一个有限自动机，Af=(Q,T,d,q0,F)，令N包含Q的元素，用起始符号X0对应q0，则可如下得到对应的规则文法G=(N,T,P,X0)：(1)如果qj在d(q

13、i,a)中，那么在P中有Xi aXj；(2)如果一个F中的状态在d(qi,a)中，那么在P中有Xi a,树结构识别,1.树文法 N：非终结符号集T：终结符号集S：一个包含在N中的起始符号，它一般是一棵树P：一组产生式规则，其一般形式为Ti Tj，其中Ti和Tj是树r：排序函数，它记录了一个其标号是文法中终结符号结点的直接后裔数目,扩展树文法,树结构识别,1.树文法（扩展）树文法产生的结构骨架N=X1,X2,X3,S，S=a,b,c,d,e,树结构识别,1.树文法 产生式规则 r(a)=0,1，r(b)=r(d)=r(e)=1，r(c)=2限制产生式规则(2)，(4)，(6)使用相同的次数，将会产生一个其中所有三段腿长度都相同的结构,通信地址：北京清华大学电子工程系 邮政编码：100084 办公地址：清华大学东主楼，9区307室 办公电话：传真号码：电子邮件：个人主页：实验室网：,联 系 信 息,