第7章-结构模式识别---西安电子科技大学

第７章结构模式识别第7章结构模式识别7.1结构模式识别概述7.2形式语言与自动机7.3高维文法和随机文法7.4句法分析7.5文法推断习题第７章结构模式识别7.1统计模式识别是从模式中提取一组特性的度量,构成特征向量来表示模式,然后通过划分特征空间的方式进行分类。对于较复杂的模式,要对其充分描述需要很多特征,以至过于复杂。第７章结构模式识别结构模式识别又称句法模式识别,它采用一些比较简单的子模式组成多级结构来描述一个复杂模式,先将模式分为子模式,子模式又分为更简单的子模式,依次分解,直至在某个研究水平上不再需要细分。最后一级最简单的子模式称为模式基元,识别模式基元比识别原模式要简单得多。结构模式识别主要突出模式的结构信息,常用于以结构特征为主的目标识别中,例如指纹、染色体和汉字识别等。图7-1所示是一个模式多级分解的例子。第７章结构模式识别图7-1模式分解示意图第７章结构模式识别结构模式识别法将观察对象表达为一个由基元组成的句子,将模式类表达为由有限或无限个具有相似结构特性的模式组成的集合。基元构成模式所遵循的规则即为文法,或称句法。与统计模式识别类似,用已知类别的训练样本进行学习,产生该类或至少是这些样本的文法,这个学习和训练过程称为文法推断。第７章结构模式识别结构模式识别的系统框图如图7-2所示,包括预处理、模式表达、句法分析和文法推断四个部分。其中,模式表达包括两部分:模式分割和基元及关系的识别。对于一个模式,经过预处理并对模式分解提取基元后,得到表征模式的句子,然后进行句法分析,判断它是否能被代表某个模式类的文法所接受,最终给出识别结果和模式的结构描述。第７章结构模式识别图7-2结构模式识别系统框图第７章结构模式识别7.2形式语言的渊源可以追溯到20世纪50年代中期,乔姆斯基(Chomsky)等在研究自然语言的过程中发展了文法的数学模型。他将语言形式地定义为由一个字母表中的字母组成的串的集合,在字母表上按照一定的规则定义一个文法,该文法产生的所有句子组成的集合就是该文法产生的语言。若一个句子能由某种语言对应的文法产生,则判断这个句子属于该语言。第７章结构模式识别克林(Kleene)在研究神经细胞时提出了自动机,用它来识别语言。按照一定规则构造任意一个自动机,该自动机所能识别的所有句子组成的集合就是一个语言,即一个自动机定义了一个语言。文法和自动机是表示语言的两种不同方法。1959年,乔姆斯基通过深入研究,证明文法和自动机具有等价性。第７章结构模式识别7.2.1短语结构文法1.字符的有限集合称为字母表,记为V。由字母表V中的字符构成的有限序列称为字母表V上的字符串(链)。例如字母表V={a,b,c,…,z,0,1,…,9},即表由26个英文字母和10个阿拉伯数字构成,则字符串可以是a,b,012,ce78等。一个字符串所包含字符的个数称为该字符串的长度,字符串x的长度记为|x|。允许有不含任何符号的空串,记为ε,第７章结构模式识别假设X和Y都是字母表V上的字符串,则XY称为字符串X和Y的连接。字母表上的任意一个字符串W与空串ε的连接还是W,即εW=Wε=W。V+是字母表V上所有字符串构成的集合,V*是字母表V上所有字符串和空串构成的集合,有V*=V+∪{ε}。第７章结构模式识别2.定义7.1短语结构文法是一个四元组:G=(VN,VT,P,S)其中:VN为非终止符集,通常用大写字母表示;VT为终止符集,通常用小写字母表示,VN∪VT=V,且VN∩VT=,即VN与VT不相交;P是形如α→β的产生式有限集,且α∈V+,β∈V*,符号“→”的含义是“能够再写为”;S∈VN为起始符。第７章结构模式识别如果A→β是P中的产生式,α和γ是V*中的字符串,则有GA称αβγ是αAγ的直接推导。设α,α0,α1,…,αn,α′都是V*中的字符串,且有α=α0,α′=αn,其中αi直接推出αi+1(0≤i≤n－1),则称序列是长度为n的直接推导序列,可记为n10'G即'*G包含了'G和'。第７章结构模式识别有一文法G=(VN,VT,P,S),若，且α是终止符和非*GS终止符组成的字符串,则α是文法G的句型;若α∈V*T,则α是文法G的句子,即句子是由终止符组成的符号串。定义7.2文法G=(VN,VT,P,S)产生的语言L(G)是由S开始根据G推出的所有终止符串组成的集合,},|{)(**xSVxxGLGT第７章结构模式识别【例7.1】给定文法G=(VN,VT,P,S),其中:},{ASVN}{aVT},,{aSAaASaSP，由文法产生的语言L(G)如下:,()SaaLG,()SaAaaSaaaaaaLG,()SaAaaSaaaAaaaaSaaaaaaaaaaLG第７章结构模式识别以此类推,}0|{)(12naGLn3.乔姆斯基(Chomsky)分类体系将短语结构文法分为四种类型,即0型、1型、2型和3型文法。1)00型文法是对P中产生式的形式不加任何限制的文法,又称为无约束文法。由此可知,任何一个文法必然是0型文法。只有0型文法才允许有产生空句的产生式。第７章结构模式识别2)11型文法也称上下文有关文法,它对每一产生式的形式限制为α1Aα2→α1βα2,其中α1、α2∈V*,A∈VN,β∈V+。文法的含义是在α1和α2之间的非终止符A可被重写为β,α1和α2被视为A的上下文。第７章结构模式识别理论上讲,每步推导时,可以对句型中的任何一个非终止符进行表达式替换。在形式语言理论中,为了简单,常采取每次对最左边的或最右边的非终止符进行表达式替换,即采用最左推导或最右推导。最左推导即每次对最左边的非终止符进行推导,最右推导即每次对最右边的非终止符进行推导。不论是采用最左推导还是最右推导,其目的均在于简化推导过程。1型文法的一种等价定义是:产生式集P的形式为α→β,α、β∈V+,且|α|≤|β|。第７章结构模式识别【例7.2】给定文法),,,(SPVVGTN，},,{BASVN，},{baVT：PaSABS改写为aSABSaABS改写为aSABSabaA改写为abaAbbbA改写为bbbA第７章结构模式识别该文法为上下文有关文法。虽然表面上看上下文不完整,但根据α1、α2∈V*,可以有α1=α2=ε,经过改写就可以明显看出给定文法是上下文有关的。或者根据1型文法的另一种定义,本例中每个产生式左部字符串长度小于或等于右部字符串长度,表明给定文法是上下文有关的。第７章结构模式识别3)22型文法也称上下文无关文法,它要求每一产生式的形式为A→β,其中A∈VN,β∈V+。产生式的左端是单个非终止符A,可被重写为右端的字符串β,而与A的上下文无关。4)33型文法也称正则文法,或称正规文法、有穷文法、有限状态文法。对每一产生式的形式限制为A→aB或A→b,其中A、B∈VN,a、b∈VT。第７章结构模式识别由定义可以看出,从0型文法到3型文法,对产生式的限制越来越严格,四种文法的类别包含关系是:3型2型10型。对应四类文法,产生的语言也分为四类。0型文法产生的语言称为无限制性语言,1型文法产生的语言称为上下文有关语言,2型文法产生的语言称为上下文无关语言,3型文法产生的语言称为正则语言。第７章结构模式识别每一种类型的语言对应一种识别器,即每个语言的句子都能被某种识别器所接受。句法识别器可以被视为一个离散控制系统,一个离散控制系统可以模型化为一个自动机。短语结构文法和自动机之间的对应关系如下:文法类型自动机类型0型文法——图灵机1型文法——线性有界自动机2型文法——下推自动机3型文法——有限自动机第７章结构模式识别7.2.2定义7.3一个确定的有限状态自动机Af是一个五元组:),,,,(0FqQAf其中:Q为有限状态集;Σ是有限输入字母表;δ是Q×Σ→Q的映射;q0为起始状态;为终止状态集。QF第７章结构模式识别图7-3给出了有限状态自动机的一般表示。有限状态自动机由一个带有读头的有限控制器和一条写有字符的输入带组成。有限控制器包含有限个状态,读头从左到右依次从输入带上读入字符,每当读头从输入带上读入一个字符时,控制器的状态发生改变,即出现状态转换。第７章结构模式识别图7-3有限状态自动机第７章结构模式识别假设映射δ(q,a)=q′,其中,q、q′∈Q,a∈Σ,表示的意思是有限状态自动机当前处于状态q,读头从输入带上读入字符a,自动机的状态转换为q′,读头从左到右移动一个方格。可以用状态转移图方便地描述映射δ,相应于映射δ(q,a)=q′的状态转移图如图7-4所示。每个状态标以一个节点,终止状态集F中的状态用双圈标示,状态集Q中F以外的节点用单圆圈表示。第７章结构模式识别图7-4δ(q,a)=q′的状态转移图第７章结构模式识别对确定的有限状态自动机而言,由当前状态及读入字符决定的下一步状态是确定的。确定的有限状态自动机Af接受的全部字符串的集合为}),(,|{)(0FxqxxALf上式表明,若一个串x被自动机接受,要求自动机Af从起始态q0出发,经输入串x后,状态最后转换到终止态上。第７章结构模式识别【例7.3】设确定的有限状态自动机Af=(Q,Σ,δ,q0,F),其中:},,{210qqqQ},{ba，，}{0qFδ:10),(qaq，21),(qaq，12),(qaq20),(qbq，，01),(qbq02),(qbq自动机的状态转移图如图7-5所示。第７章结构模式识别图7-5例7.3的有限状态自动机的状态转移图第７章结构模式识别自动机Af从起始态q0出发,输入串x=aabbab,在逐个读入x的各字符时,自动机的状态变化过程为0120210qqqqqqqbabbaa整个输入串读完后,自动机处于状态q0∈F,所以输入串x被自动机接受。定义7.4一个非确定的有限状态自动机Af是一个五元组:),,,,(0FqQAf第７章结构模式识别与确定的有限状态自动机相比,只是映射规则不同,δ是Q×Σ→2Q的映射。对非确定的有限状态自动机而言,在当前状态及输入符号确定的情况下,下一步的状态不唯一,即δ(q,a)是一个状态集合(可能为空)。例如δ(q,a)={q1,q2,…,ql},它的解释是:非确定的有限状态自动机处于状态q,读头从输入带上读入字符a,选择q1,q2,…,ql中的任意一个作为下一步状态,并将读头向右移动一格。第７章结构模式识别非确定的有限状态自动机Af接受的语言也定义为输入串后能停留在终止态上的所有串的集合:}),,(,|{)(0FpxqpxxALf定理7.1设L是一个非确定的有限状态自动机),,,,(0FqQAf所接受的语言,则有一个能接受L的确定的有限状态自动机),,,,(''0''''FqQAf第７章结构模式识别'fA的状态是Af的状态的所有子集,即，，QQ2'''00{}qq，是中包含F的一个状态的所有状态集合。映射为'F'Q1212'({,,,},){,,,}ijqqqappp121(,){,,,}ikjkqappp第７章结构模式识别由于确定的有限状态自动机和非确定的有限状态自动机接受同样的语言,在讨论有限状态自动机时,可以不区分是确定的有限状态自动机还是非确定的有限状态自动机。定理7.2设G=(VN,VT,P,S)是一个正则文法,则存在一个有限状态自动机Af=(Q,Σ,δ,q0,F),满足L(Af)=L(G),其中:(1)Σ=VT,Q=VN∪{T},T为一附加的非终止符,q0=S;(2)如果P包含产生式S→ε,则F={S,T},否则F={T};(3)如果P包含产生式B→a,B∈VN,a∈VT,则T∈δ(B,a);(4)如果P包含产生式B→aC,B、C∈VN,a∈VT,则C∈δ(B,a)。第７章结构模式识别定理7.3给定一个有限状态自动机Af=(Q