结构模式识别-OK.pdf

《结构模式识别-OK.pdf》由会员分享，可在线阅读，更多相关《结构模式识别-OK.pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1结构模式识别结构模式识别1997 20031997 2003年年6 6月月目录目录?一、模式基元一、模式基元?二、结构化描述二、结构化描述?三、句法分析三、句法分析?四、结构匹配四、结构匹配一、模式基元（一、模式基元（Pattern primitivesPattern primitives）?基本概念基本概念?信号基元信号基元?图像基元图像基元1.0 1.0 基本概念基本概念?1 1、不同于以往的相似性度量、不同于以往的相似性度量?2 2、所关心的事对一个模式从结构上进行描述，解、所关心的事对一个模式从结构上进行描述，解释一个模式如何有一个简单的子模式（释一个模式如何有一个简单的子模式（Su

2、bSub-patternspatterns，Pattern primitivesPattern primitives，模式基元）组织起来，模式基元）组织起来?3 3、两类方法、两类方法?句法分析句法分析?结构匹配结构匹配?4 4、错误率的讨论、错误率的讨论-ProblemProblem-dependent(dependent(样本集测样本集测试）试）?5 5、与统计模式识别和神经网络联合使用（、与统计模式识别和神经网络联合使用（2D,3D)2D,3D)1.1 1.1 信号基元信号基元UUUUUUDDDDDDD1.1 1.1 信号基元信号基元?SigParseSigParse算法：算法：对以每一

3、个直线段，确定一个最大的误差对以每一个直线段，确定一个最大的误差EmaxEmax从第一个样本信号从第一个样本信号X(iX(i)开始进行逼近搜索，它开始进行逼近搜索，它对第一个直线段进行了初始化对第一个直线段进行了初始化i=1i=1设定需要回归的样本信号的个数设定需要回归的样本信号的个数k=1k=1产生一条直线去回归产生一条直线去回归k k个样本信号个样本信号,从从X(iX(i)到到X(i+kX(i+k-1)1)对于回归直线评价值，如果它比小，增大对于回归直线评价值，如果它比小，增大k k值回值回到第四部否则，否则选择一个新的直线段，增到第四部否则，否则选择一个新的直线段，增大大i i值，回到第

4、三步。值，回到第三步。21.1 1.1 信号基元信号基元?误差的定义误差的定义=dihxjjijxhxsE1)()(为直线段为信号)()(xhxS1.1 1.1 信号基元信号基元1221.2 1.2 图像基元图像基元?链码和模板链码和模板X=60076564543242210021.2 1.2 图像基元图像基元?曲线段曲线段Shape primitives-Image silhouette primitivesMethod:Hough Transformation1.2 1.2 图像基元图像基元?区域区域?Divide the image into different regions,and

5、Divide the image into different regions,and compute their pute their features.二、结构化描述二、结构化描述?2.1 2.1 字符串字符串?2.2 2.2 图形图形?2.3 2.3 树树32.1 2.1 字符串字符串?定义：是符号的一个有序序列，每个符号表示一定义：是符号的一个有序序列，每个符号表示一个基元。个基元。?EgEg.X=a0,a1,a2,.X=a0,a1,a2,am am ai ai belongs to Tbelongs to T?T:T:charsetcharset?DefinationDefinati

6、on operation:+,operation:+,-,etc.,etc.?To describe the 2D and 3D structure To describe the 2D and 3D structure?Some shortcomings:Some shortcomings:?To describe a wave according to the above description,To describe a wave according to the above description,?No duration,length,angleNo duration,length,

7、angle?Attributed vector:Attributed vector:?Ax=a1,a2,Ax=a1,a2,am,every charam,every char-element denote a perelement denote a per-determined determined featuresfeatures2.2 2.2 图形图形?定义：一个图形定义：一个图形G G的一个有序对的一个有序对G=N,RG=N,R，分析集合分析集合N N，边集合，边集合R R。2.3 2.3 树树?定义：定义：树是一树是一个无向个无向图图外?内：o?I上?下：t?b左?右：l?r三、句法分

8、析三、句法分析?3.0 3.0 概述概述?3.1 3.1 字符串语法字符串语法?3.2 3.2 画面描述语言画面描述语言?3.3 3.3 语法种类语法种类?3.4 3.4 有限状态自动机有限状态自动机?3.5 3.5 属性语法属性语法?3.6 3.6 随机语法随机语法?3.7 3.7 语法推理语法推理3.0 3.0 概述概述?句法分析是一种解决结构模式识别的方法，句法分析是一种解决结构模式识别的方法，理论基础是形式语言的有关原理。理论基础是形式语言的有关原理。?句法模式识别（句法模式识别（Syntactic Pattern Recognition)Syntactic Pattern Recog

9、nition)?优缺点：优缺点：?优点：某种描述形成一种应用的标准方法优点：某种描述形成一种应用的标准方法?缺点：缺少对于复杂模式足够的描述能力，以及缺点：缺少对于复杂模式足够的描述能力，以及自动推论与学习的进程上存在的困难，对于现有自动推论与学习的进程上存在的困难，对于现有问题，通常需要首先规定一系列合适的语法规问题，通常需要首先规定一系列合适的语法规则。则。3.1 3.1 字符串语法字符串语法?定义：形式字符串语法为一个定义：形式字符串语法为一个4 4元组元组G=T,N,P,SG=T,N,P,S?T(terminal symbols)T(terminal symbols)：?终端符号集，对

10、应于基元集中的模式，也称为字母表终端符号集，对应于基元集中的模式，也称为字母表(pattern(pattern alphabet)alphabet)，字母表中所有可能的符号组成符号串及空字符串，字母表中所有可能的符号组成符号串及空字符串，共同构成集合被称为形式语言共同构成集合被称为形式语言L L。?N(nonN(non-terminal symbols)terminal symbols)：?非终端符号集，对应于模式类别，标记非终端符号集，对应于模式类别，标记T T中元素类别的符号。中元素类别的符号。?P(production rules)P(production rules)：?用来产生字符串

11、，形如用来产生字符串，形如A A?B B，表示在字符串中，任何出现，表示在字符串中，任何出现A A的的地方可以用地方可以用B B代替；代替；?S(parent class symbol)S(parent class symbol)：?起始符号，用来作为产生基于规则起始符号，用来作为产生基于规则P P的字符串的字符串43.1 3.1 字符串语法字符串语法(波形识别示例)?定义语法：?T：三种基元：?水平段h，朝上段u，朝下段d，构成字母表T=h，u，d?N：考虑T中下面这些类别的字符串：?P+：朝上的尖峰；P-：朝下的尖峰；H：水平状态；N=P+，P-，H?P：产生式规则?朝上尖峰P+?u d

12、P+?u(P+)d?朝下尖峰：P-?d u P-?d(P-)u?水平状态：H?h H?hH?起始符号：S?P+S S?P-S S?HS S?P+S?P-S?H S?O UUUUUUDDDDDDD3.1 3.1 字符串语法字符串语法(波形识别示例)?EgEg.X=.X=hhuuddhhhuuddh?考虑：考虑：x=x=hhuuuddhhhuuuddh是否是该产生式语法规则的字符串？是否是该产生式语法规则的字符串？hhuuddhdhhHuPHHPSHPHSS+3.2 3.2 画面描述语言画面描述语言?PDLPDL（Picture description languagePicture descri

13、ption language）?对对2D2D空间样本提供了很好的描述空间样本提供了很好的描述?每个基元有两个连接点每个基元有两个连接点-尾尾(tail)(tail)和头和头(head)(head)?定义定义4 4各二元操作和各二元操作和1 1个一元操作个一元操作?任何一个有类别标号边长的有向图都可以用一任何一个有类别标号边长的有向图都可以用一个个PLDPLD表达式描述。表达式描述。3.2 3.2 画面描述语言画面描述语言?示例：示例：?R=(R=(v+(b)+(dv+(b)+(d)R=R=d+(b+(vd+(b+(v)?E=(E=(vxh)+(vxh)+hvxh)+(vxh)+h)E=(E=(

14、h)+(vh)+(v-(h)+(v(h)+(v-(h(h)3.2 3.2 画面描述语言画面描述语言?字符串语法推广到字符串语法推广到PDLPDL描述描述?例：以对于字母例：以对于字母”P P”、“R R”、“F F”、“E E”的字符串描述的字符串描述?G=T,N,P,S G=T,N,P,S?T=v,h,d,b,T=v,h,d,b,-,+,(,),+,(,)?N=S,P,R,F,E,LEFTCORNER N=S,P,R,F,E,LEFTCORNER?P=SP=S?(P|R|F|E),(P|R|F|E),R R?d+Pd+P,P P?b+(vb+(v),),LEFTCONERLEFTCONER?

15、v v-(h(h),),F F?LEFTCORNER+LEFTCORNERLEFTCORNER+LEFTCORNER，E E?(h)+F(h)+F 53.3 3.3 语法种类语法种类G0,G1语法建立一个对应的分析器较难，G2,G3语法较常用，有商业或免费的分析器。Ref:Schalkoff,19923.3 3.3 语法种类语法种类利用语法识别字符串：建立语法；分析器识别；3.4 3.4 有限状态自动机有限状态自动机?有限状态自动机定义：有限状态自动机定义：?M=T,Q,q0,FM=T,Q,q0,F?T T是一个符号集合是一个符号集合?Q Q机器的状态集合机器的状态集合?映射映射Q*TQ*T?

16、q0q0初始状态初始状态?F F最终状态最终状态3.4 3.4 有限状态自动机有限状态自动机举例：3.4 3.4 有限状态自动机有限状态自动机3.4 3.4 有限状态自动机有限状态自动机?常规语法转换到有限状态自动机常规语法转换到有限状态自动机:,;),(;),(;0AFASFSPFaaaaSqANQ=，否则则有包含产生规则如果对对应着产生规则对应着产生规则63.4 3.4 有限状态自动机有限状态自动机;dBuABhBAuAAdAuAACEL检测加速情况（ACEL)，使用规则及自动机3.5 3.5 属性语法属性语法?问题提出：使用字符串不能完全表示模式基元问题提出：使用字符串不能完全表示模式基

17、元的属性；的属性；?语法规则语法规则+语义规则语义规则?a(aa(a)属性向量对应于终端属性向量对应于终端b b的属性向量的计算结果的属性向量的计算结果?举例举例（对上图）（对上图）?L(ACEL)=L(ACEL)=L(u)+L(AL(u)+L(A););?T(ACEL)=T(ACEL)=T(u)+T(AT(u)+T(A););)()(,bfaba=3.6 3.6 随机语法随机语法?产生规则的定义：产生规则的定义：?语言语言x x出现的概率：出现的概率：=iiiikjijGxPGxPGxPlGLxPP(x|G)PGLx11)|()|()|()(k)(那么有：个衍生，每个概率是不确定的，是如果那

18、么有：有概率个规则的衍生，每个具是确定的，是如果jiijP:3.6 3.6 随机语法随机语法输入字符串dU3.6 3.6 随机语法随机语法,1),|()(max)|()()(ciGxPGPxGPGPGLxiikkk=，如果判定决策规则：贝叶斯决策032.0)|()(336.0)|()(=QxPQPPxPPP3.7 3.7 语法推理语法推理?从训练样本集提取语法规则从训练样本集提取语法规则?Ref:Ref:MicletMiclet,1990(Survey),1990(Survey)?继承者方法继承者方法(Successor method)(Successor method)：?EgEg.T=.T

19、=udud,uhduhd,uuduud,uuhuuduuhuud,uhuduhud?列出列出T T中每一个符号的所有继承者中每一个符号的所有继承者?状态状态S S-T T中空串继承者中空串继承者uu?状态状态q qu u-T T中中u u的继承者的继承者 u,h,du,h,d?状态状态q qh h-T T中中h h的继承者的继承者 u,du,d?状态状态qd-T T中中d d的继承者的继承者 空集空集?建立自动机状态图建立自动机状态图73.7 3.7 语法推理语法推理?EgEg.当当 T=T=ud,uhd,uud,uuhuud,uhudud,uhd,uud,uuhuud,uhud,uhhudu

20、hhud 四、结构模式识别四、结构模式识别?4.0 4.0 概述概述?4.1 4.1 字符串匹配字符串匹配?4.2 4.2 随机松驰匹配随机松驰匹配?4.3 4.3 离散松弛匹配离散松弛匹配?4.4 4.4 利用利用HopfiedHopfied网络的松弛算法网络的松弛算法?4.5 4.5 图和树匹配图和树匹配4.0 4.0 概述概述?结构匹配的关键思想：结构匹配的关键思想：?利用一些相似性度量准则确定出未知样本和一利用一些相似性度量准则确定出未知样本和一些典型的模式之间的相似程度，这些度量准则些典型的模式之间的相似程度，这些度量准则必须足以用来表示样本的结构。必须足以用来表示样本的结构。4.1

21、 4.1 字符串匹配字符串匹配?基本思想：对两个分别具有基本思想：对两个分别具有n n和和m m个符号的个符号的字符串字符串x x和和y y计算相似度；计算相似度；?相似度：相似度：?定义：将字符串定义：将字符串x x转换到转换到y y时需要的字母编辑次时需要的字母编辑次数；数；?可以为每一此转换定义代价，总代价为最小的可以为每一此转换定义代价，总代价为最小的转换代价。转换代价。4.1 4.1 字符串匹配字符串匹配?EgEg.x=x=duuhduuhy=y=hdhuhhdhuh?LevenshteinLevenshtein算法：算法：?核心建立代价矩阵，求解最小代价路径核心建立代价矩阵，求解最

22、小代价路径?D(i,jD(i,j-1)1)?D(i,j)D(i,j)：?将对应的顶部将对应的顶部y y的符号插入到的符号插入到x x中去，代价为中去，代价为D1=D(I,jD1=D(I,j-1)+c(1)+c(?a);a);?D(iD(i-1,j)1,j)?D(i,j)D(i,j)：?将左边的将左边的x x的符号删除，代价为的符号删除，代价为D2=D(iD2=D(i-1,j)+c(a1,j)+c(a?););?D(iD(i-1,j1,j-1)1)?D(i,j)D(i,j)：?将将x x中的符号用中的符号用y y中的符号代替，代价为中的符号代替，代价为D3=D(iD3=D(i-1,j1,j-1)

23、+c(b1)+c(b?)+c()+c(?a),a),如果两个符号相同，代价为零如果两个符号相同，代价为零4.1 4.1 字符串匹配字符串匹配84.2 4.2 随机松弛匹配随机松弛匹配?问题的提出：问题的提出：未调整编辑代价时，未调整编辑代价时，d d的匹配比的匹配比b b得好，上图是调整后的代价；得好，上图是调整后的代价；调整局部最优的发生，即利用局部限制条件，反复调整匹配，调整局部最优的发生，即利用局部限制条件，反复调整匹配，得到较好的结果；（串行工作得到较好的结果；（串行工作?并行工作）并行工作）4.2 4.2 随机松弛匹配随机松弛匹配?原理：假设现在有原理：假设现在有n n个需要标记的物

24、体个需要标记的物体A(iA(i)，和和m m个标号个标号l(jl(j););?同时假设标记规划同时假设标记规划A(i)A(i)?l(jl(j)与与A(h)A(h)?l(kl(k)之间有某种联系，联之间有某种联系，联系使用兼容程度系使用兼容程度C(i:j,h:kC(i:j,h:k)来测量，取值为来测量，取值为-1,1;1,1;?目的是在给物体设定标号时得到一个兼容的结果，它是由一目的是在给物体设定标号时得到一个兼容的结果，它是由一个概率度量，假定将标记为个概率度量，假定将标记为p0(ij)p0(ij)，表示把，表示把A(iA(i)标记标记l(jl(j););?从初始概率出发从初始概率出发p0p0

25、，讨论该标号规划对其它规划影响（兼容，讨论该标号规划对其它规划影响（兼容性），通过计算兼容性来修正该规划的匹配概率，如果该标性），通过计算兼容性来修正该规划的匹配概率，如果该标号规划对其它规划有一个较好的兼容性（支持），调整该标号规划对其它规划有一个较好的兼容性（支持），调整该标号规划为具有较高的匹配概率，反之亦然。迭代后，最后较号规划为具有较高的匹配概率，反之亦然。迭代后，最后较好的标号规划具有较高的匹配概率，好的标号规划具有较高的匹配概率，?该方法的最主要是兼容性度量方法及匹配概率修正和计算方该方法的最主要是兼容性度量方法及匹配概率修正和计算方法；法；4.2 4.2 随机松弛匹配随机松弛匹

26、配=+=+=mjrijrijrijrijrijijnihhmkrhkrijhimkrhkijijijhkkhijqPqPPPPkhjicnqAAcPkhjicPbPPPPkhjiclAarP1)()()()()1(11)()(1)()0()1()1(3):,:(11 ):,:():,:(,21、更新计算增长平均值：、对所有的影响（联合增长）：带来的对、计算所有可能的规划；，反之减小兼容性好增加的值；来调整希望通过后、给定每一个规划方式划计算兼容性：次迭代对所有可能的规、第、初始标记规划概率4.2 4.2 随机松弛匹配随机松弛匹配?例：图像注册问题例：图像注册问题?建立两个点集合（控制点）建立两

27、个点集合（控制点）A A，B B之间的对应关之间的对应关系，系，A A上上n n个点，个点，B B上上m m个点，它们具有个点，它们具有k k个相同的个相同的点，这些控制点是各个区域的质心，区域的类型和点，这些控制点是各个区域的质心，区域的类型和大小都对应了该区域的属性值。大小都对应了该区域的属性值。?建立建立n*mn*m概率值矩阵，反映了各对点之间的匹配概概率值矩阵，反映了各对点之间的匹配概率率=其它是相同的类型如果0,)()(,)()(min)0(ABAsizeBsizeBsizeAsizePijjiij4.2 4.2 随机松弛匹配随机松弛匹配?建立建立n*mn*m概率值矩阵，反映了各对点

28、之间的匹配概率概率值矩阵，反映了各对点之间的匹配概率?兼容性因子计算：兼容性因子计算：?第第r r次迭代中，其它点对的支持度：次迭代中，其它点对的支持度：?概率更新，期望对于一个匹配得到概率值接近概率更新，期望对于一个匹配得到概率值接近1 1=ihjkjkihrhkrddddPkhjic,min):,:()()(=nihhrjkmkrijkhjicmq1)(1)():,:(max11)()()1(rijrijrijPqP=+=其它是相同的类型如果0,)()(,)()(min)0(ABAsizeBsizeBsizeAsizePijjiij4.2 4.2 随机松弛匹配随机松弛匹配94.2 4.2 随机松弛匹配随机松弛匹配4.3 4.3 离散松弛匹配离散松弛匹配