最新中科院《模式识别》——第七章课件PPT.ppt 150页

'中科院《模式识别》——第七章 第七章句法模式识别统计模式识别是基于模式特征的一组测量值来组成特征向量，用决策理论划分特征空间的方法进行分类。基于描述模式的结构信息，用形式语言中的规则进行分类，可以更典型地应用于景物图片的分析。因为在这类问题中，所研究的模式通常十分复杂，需要的特征也很多，仅用数值上的特征不足以反映它们的类别。 第七章句法模式识别句法模式识别系统的组成图像预处理图像分割基元及其关系识别句法分析 第七章句法模式识别句法模式识别系统处理过程基元本身包含的结构信息已不多，仅需少量特征即可识别。如果用有限个字符代表不同的基元，则由基元按一定结构关系组成的子图或图形可以用一个有序的字符串来代表。假如事先用形式语言的规则从字符串中推断出能生成它的文法，则可以通过句法分析，按给定的句法（文法）来辨识由基元字符组成的句子，从而判别它是否属于由该给定文法所能描述的模式类，达到分类的目的。 第七章句法模式识别句法模式识别学习过程为了要事先确定一个文法来描述所要研究模式的结构信息，同样需要采用模式的训练样本集把文法推断出来。有了推断出来的文法，才可以对未知类别的字符串进行句法分析，达到分类的目的。这一过程类似于统计模式识别中的学习过程，但文法推断过程远不及统计学习来的成熟。 7.1集合论中的关系运算要进行句法识别中基元之间关系的判别，首先要明确关系运算。“关系”在客观世界中广泛存在社会生活：父子关系，母子关系，兄弟关系，等等；数学运算：大于、等于和小于关系，函数关系，等等。二元关系凡是一对对象之间的关系，都是二元关系。 7.1集合论中的关系运算二元关系的相关概念有序偶设用表示一有序偶，它可以代表迪卡儿坐标，例如<1,3>，<2,4>，<1,2>等，它们表示平面坐标上的不同点。两个有序偶和相等，定义为迪卡儿积设A和B是任意两个集合，由A中的一个元素和B中的一个元素组成有序偶，那么由A和B中所有元素组成的有序偶集合，称为A和B的迪卡儿积，写成AxB。公式表达：[例子] 7.1集合论中的关系运算二元关系的相关概念二元关系的定义及表示任意有序对的集合定义一种二元关系，简称为关系表示设一有序对，其中R是一种关系，则记为xRy[例子] 7.1集合论中的关系运算二元关系的性质定义：自反集合X中的关系R是自反的，只要对X中的每个x，有xRx，则属于R。写法：X中的R是自反的定义：对称集合X中的关系R是对称的，只要对X中的每个x和y，每当xRy时总有yRx。写法：X中的R是对称的例：实数集合中的“<=”不是对称的，但“=”关系是对称的。例：全体人的集合中，师生关系不是对称的，但同学关系是对称的。例：平面上三角形集合中的相似关系是自反的和对称的。 7.1集合论中的关系运算二元关系的性质定义：传递集合X中的关系R是传递的，只要对X中的每个x,y和z，一旦xRy且yRz，则有xRz。写法：X中的R是传递的例：若a不属于R。[例] 7.1集合论中的关系运算二元关系的性质定义：反对称集合X中的关系R是反对称的，只要对X中的每个x和y，一旦xRy且yRx，则有x=y。写法：X中的R是反对称的[例] 7.1集合论中的关系运算关系图关系可以用图形表示设R为集合X={x,y,z}中的一种关系，X中的元素用结点表示，并用相应的元素名称标志。如果xRy，则用带箭头的弧线连接结点x和y。 7.1集合论中的关系运算等价关系如果集合X中的关系R是自反的、对称的和传递的，则称它是一个等价关系。实数集合中的数值相等三角形集合中的三角形相似一个班内同学之间的同班关系等价类定义等价类性质集合X上的等价关系R所构成的类两两不相交，且覆盖了整个集合X。 7.1集合论中的关系运算等价关系可以用图形方法分析研究等价划分：由于等价关系是自反的、对称的、传递的，因此由这些性质的图形特点可知：一个集合X上的等价关系R的关系图，其每个结点必有环；若两个结点间有边相连，则必有方向彼此相反的两条有向边；若图中任何两个结点是可达的，则必有边直接相连。[例子] 7.1集合论中的关系运算兼容关系如果X中的关系R是自反的而且是对称的，则称R是一个兼容关系。所有的等价关系是兼容关系；兼容关系不一定是传递的。偏序关系集合P上的二元关系R称为P上的一个偏序关系，当且仅当R是自反的、反对称的和传递的。偏序关系通常用“<=”表示，但注意“<=”不一定是实数中的“小于或等于”，表示的是更普遍意义上的偏序关系。[例子]半序集全序或线性序 7.1集合论中的关系运算二元关系的复合定义人类的亲属关系是最容易理解的复合关系叔侄关系是兄弟关系和父子关系的复合，可表示为：A”兄弟”B且B”父子”C->A”叔侄”C 7.1集合论中的关系运算二元关系的复合关系图 7.1集合论中的关系运算二元关系的复合关系的复合运算可以施加于自身表示为：RºR=R2，RºRºR=R3，…传递闭包[例子] 7.2形式语言理论和句法模式识别形式语言的起源可以追溯到二十世纪五十年代；乔姆斯基(Chomsky)等科学家在研究语言的工作中发展了文法的数学模型；其基本目的是发展一种应用于计算机的文法，使它有描述自然语言的能力，例如英文。如果能做到这一点，则有希望“教”计算机理解自然语言，以达到翻译的目的。 7.2形式语言理论和句法模式识别形式语言的基本目的迄今为止尚未完全实现，但在这个领域的研究成果却大大冲击了其它一些领域计算机编译系统的设计计算机语言自动机理论模式识别 7.2形式语言理论和句法模式识别在模式识别中，如果大量复杂的模式的集合，能用一组为数不多的简单的模式基元和文法规则来描述，则对每一个模式的识别，就可以按给定的一组文法结构规则来剖析；如果解析的结果表明，模式基元能为给定的文法规则所接受，则可判别它属于该模式类，否则就不属于该模式类。 7.2形式语言理论和句法模式识别7.2.1形式语言理论中的某些定义形式语言是一种抽象语言，它可以包括人类使用的自然语言、计算机使用的各种语言、数学中的公式语言等。自然语言（英文）：它的基本组成是有限个字母，将字母（组成的单词）按一定的文法规则排列，可以构成句子，而一种语言则是所有句子的集合。人类的自然语言是一个不可数的有穷集英文：26个字母按一定的文法规则组合，可以表达无数的思想内容。 7.2形式语言理论和句法模式识别7.2.1形式语言理论中的某些定义字母表和符号串字母表：以某些符号作为元素的非空有穷集，以V或Σ表示。符号串：由字母表中符号组成的任何有穷序列。[例子]空符号串：不包含任何符号的串，用ε表示。符号串的长度：符号串x所包含的符号个数，用|x|表示。[例子]符号串的联接：若x和y都是符号串，则把y符号串写在x符号串之后，就得到联接的符号串xy。[例子] 7.2形式语言理论和句法模式识别7.2.1形式语言理论中的某些定义字母表和符号串符号串集合的乘积[例子]如果A和B只是代表一个符号串，而不是符号串的集合，则乘积AB与符号串的联接结果相同。符号串和符号串集合A的幂集合A的正闭包、闭包字母表V的幂集合V的正闭包、闭包[例子] 7.2形式语言理论和句法模式识别7.2.1形式语言理论中的某些定义文法一种语言中构成句子所必须遵守的规则；由某种语言的字母表中的字母所组成的串不一定都是该语言的句子；只有当一个串符合该语言的文法规则时，才能算是该语言的句子，否则就不是该语言的句子。 7.2形式语言理论和句法模式识别7.2.1形式语言理论中的某些定义文法定义[文法举例]在生成规则P中，带<>的符号称为语法元，不带<>的符号称为单词；一个简单句的生成由语法元()开始，反复把生成规则中箭头左边的部分用其右边的部分替换，直到所得的形式中不再出现语法元而只有单词为止。简单句“Theboyruns.”符合给定的文法规则，因为它可以由上述的文法规则产生。[生成过程] 7.2形式语言理论和句法模式识别7.2.1形式语言理论中的某些定义[文法举例]文法树 7.2形式语言理论和句法模式识别7.2.1形式语言理论中的某些定义利用文法树可以阐明文法的形式化定义：文法树的根一定是文法G的起始符S；树的叶一定是终止符；树的每一个分支（子树）在沿着根到叶的方向上可以表示成一个直接推导的生成式；如果利用文法树的逆过程，则可将生成过程重新构造出来。 7.2形式语言理论和句法模式识别7.2.2语言的生成过程利用文法G来生成语言的过程中的一些规定非终止符VN用大写英文字母：S,A,B,C,…终止符VT用英文字母表起始部分的小写字母：a,b,c,…终止符组成的字符串用英文字母表中尾部的小写字母：u,v,w,x,…终止符和非终止符混合组成的字符串用希腊字母：α,β,γ,δ,… 7.2形式语言理论和句法模式识别7.2.2语言的生成过程利用文法G来生成语言的过程中的一些规定生成式P由以下形式的表达式组成：α->β，其中α是V+中的字符串，β是V*中的字符串，“->”表示字符串α被β所取代。η=>γ表示根据文法G，由一字符串η直接推导出另一字符串γ。[例子] 7.2形式语言理论和句法模式识别7.2.2语言的生成过程句型和句子定义句型是由起始符开始进行推导而得到的由字母表中的符号（包括VN、VT和ε）组成的任意字符串；句型和句子关系句子一定是由字母表中终止符组成的字符串。 7.2形式语言理论和句法模式识别7.2.2语言的生成过程语言定义短语定义从起始符推导一个句子的过程，实际上就是将推导过程中句型的一部分不断用短语来取代的过程，这种文法称为短语结构文法。 7.2形式语言理论和句法模式识别7.2.2语言的生成过程[例子]从生成规则P中可以看出，只有第二生成式A->aAc中出现了a和c，可见由此生成的字符串中a和c的个数是同样多的，且a和c只能分别地连续出现。如果不用第二生成式A->aAc而用第三生成式A->B时，则只能往下用第四生成式B->bB和第五生成式B->b，这样再也不会出现a和c。因此由P生成的字符串只能是anbmcn的形式。L(G)={anbmcn|m,n>=1且仅为整数} 7.2形式语言理论和句法模式识别7.2.2语言的生成过程文法G产生语言的描述一个文法G=(VN,VT,P,S)所产生的语言，是由S开始所推导出的所有终止符的集合，它满足两个条件每一个字符串只能由终止符组成，即每一个字符串都是终止符句子；每一个字符串都能从S开始，适当应用P中的生成式来导出。 7.2形式语言理论和句法模式识别7.2.2文法的分类文法可定义为一个四元组G=(VN,VT,P,S)，乔姆斯基按照文法所允许的生成形式的不同，定义四种文法类型：0型文法：称为无约束文法1型文法：称为上下文有关文法2型文法：称为上下文无关文法3型文法：称为正则文法 7.2形式语言理论和句法模式识别7.2.2文法的分类0型文法（无约束文法）生成式形式说明可以有β=ε，但不能有α=ε；只有0型文法才允许有产生空句ε的生成式。 7.2形式语言理论和句法模式识别7.2.2文法的分类1型文法（上下文有关文法）生成式形式说明在α1和α2之间的非终止符可以重写为β，这里α1和α2称为句型α1Aα2对于A的上下文；不是在α1和α2之间的A不能使用此规则。[例子]从表面上看似乎上下文并不完整；但根据1型文法的定义，α1、α2属于V*，可以有α1=α2=ε；因此生成规则P可以改写成例中生成式右侧所示形式。 7.2形式语言理论和句法模式识别7.2.2文法的分类2型文法（上下文无关文法）生成式形式说明该文法表明生成式左侧为单变量，可由右侧的字符串β来取代，因此是上下文无关的。 7.2形式语言理论和句法模式识别7.2.2文法的分类3型文法（正则文法）生成式形式说明该文法表明规则右侧一定要首先含有非终止符。 7.2形式语言理论和句法模式识别7.2.2文法的分类四种文法比较正则文法（3型文法）生成规则的右侧若不强调终止符的首先出现，就变成上下文无关文法（2型文法）；上下文无关文法（2型文法）生成规则的左侧若不强调单变量，而加以上下文限制，就变成上下文有关文法（1型文法）；上下文有关文法（1型文法）去掉上下文的限制，就变成无约束文法（0型文法）。 7.2形式语言理论和句法模式识别7.2.2文法的分类四种文法比较包含关系：正则文法上下文无关文法上下文有关文法无约束文法所有正则文法都是上下文无关的；所有上下文无关文法都是上下文有关的；所有上下文有关文法都是无约束的。在句法模式识别中，多采用上下文无关文法和正则文法。 7.2形式语言理论和句法模式识别7.2.2文法的分类[例1：无约束文法][例2：上下文有关文法][例3：上下文无关文法][例4：正则文法] 作业写出上下文无关文法，其终止符集VT={a,b}能生成语言L(G)={ab,ba,aba,bab,abab,baba,…} 7.3句法结构的自动机识别一种类别的模式，可以用一个文法来描述。要识别一个未知的模式，可以先用其基元表征成一个字符串或句子，然后再用该文法进行判断。若能被接受，则说明它是属于该文法所生成的语言，亦即它是属于该类模式，否则就不属于该类模式。自动机就是一种句法识别器，它可以判断一个句子是否属于某种语言，并且自动机的类型与文法的类型有着某种对应关系。 7.3句法结构的自动机识别7.3.1有限态自动机有限态自动机是研究自动系统的一种数学模型，它能模拟多种离散的自动系统。结构概念实例：八进制计数器和有限态自动机模型一个八进制计数器，要求每逢计数到6输出一脉冲。将该装置看成是一个离散系统。 7.3句法结构的自动机识别7.3.1有限态自动机结构概念实例：八进制计数器和有限态自动机组成输入信息：接受顺序输入的计数脉冲作为输入信息，有脉冲时为1，无脉冲时为0，以{0,1}组成的字符串作为输入。输出信息：当计数器的状态到达6时，输出一脉冲，其余情况均输出为0，以{0,1}组成的字符串作为输出。内部状态：触发器q1、q2和q3所处的0或1的状态。该计数装置是否有脉冲输出，不仅依赖于当前的输入信息，而且还依赖于前一时刻触发器所处的状态亦即该触发器的内部状态。这里三个触发器所处的状态的集合{q1,q2,q3}属于有限个状态的集合。 7.3句法结构的自动机识别7.3.1有限态自动机结构概念实例：八进制计数器和有限态自动机组成状态转换：设以Σ表示输入{0,1}的集合，以Q表示内部状态的集合{q1,q2,q3}，则状态转换函数可以表示成Q和Σ到Q的映射，写成迪卡儿乘积的形式为：δ：QxΣ->Q，δ称为状态转移函数。内部状态的转换既依赖于输入，也依赖于前一时刻的内部状态。输出函数：在某时刻的输出信息，一般由同一时刻的输入信息和内部状态所决定。它也是内部状态与输入的映射从上述组成可以看出，一个离散的有限状态的自动系统由五部分组成。一个有限态自动机A是模拟多种离散自动系统的一种数学模型。 7.3句法结构的自动机识别7.3.1有限态自动机有限态自动机定义映射的状态图表示：并不是全部可能的输出函数都一定是需要的输出终止状态，只有其中部分输出状态才是感兴趣的输出终止状态。有限态自动机抽象结构示意图 7.3句法结构的自动机识别7.3.1有限态自动机结构示意图描述控制器上记录了各种状态，并且各种状态之间按一定的规则在控制器中变化，而变化的改变是受输入支配的。具体来说，控制器相对于输入磁带自左向右移动，每接受一个输入符号便右移一个单位，并改变一次状态，直至一个句子的全部符号输入结束。同时，每输入一个符号，控制器要根据状态规则来判断能否接受该符号，若所有的符号都能被接受，就说明该句子属于该自动机所能接受的那种语言。此时，状态变换σ(q,a)=q’表示“处于状态q并正在扫描输入符号a”的自动机A，将读入磁头右移一个单元，并转到状态q’。自动机输入句子后，若σ(q,x)=q’且q’在F中，则称句子x被有限态自动机A所接受。 7.3句法结构的自动机识别7.3.1有限态自动机正规集由有限态自动机A接受的所有句子x的集合表示为：T(A)={x|δ(q,x)在F中}，F是终止状态集。由有限态自动机接受的句子的任何集合，称为正规集。 7.3句法结构的自动机识别7.3.1有限态自动机[例子]状态图 7.3句法结构的自动机识别7.3.2非确定有限态自动机确定有限态自动机映射关系唯一非确定的有限态自动机它所确定的状态不是唯一的，可以由若干个状态可供选择，亦即是一个状态集。映射关系：δ(q,x)={p1,p2,…,pk}自动机A在状态q若输入字母为x，则其转换到下一时刻的状态可以从p1,p2,…pk这k个状态中任选一个，这样的一种自动机称为非确定有限态自动机。 7.3句法结构的自动机识别7.3.2非确定有限态自动机形式化定义[例子] 7.3句法结构的自动机识别7.3.2非确定有限态自动机非确定有限态自动机与确定有限态自动机的关系非确定有限态自动机是确定有限态自动机的推广形式化描述 7.3句法结构的自动机识别7.3.2非确定有限态自动机非确定有限态自动机与确定有限态自动机的关系[例子]非确定的有限态自动机和确定的有限态自动机统称为有限态自动机 7.3句法结构的自动机识别7.3.3按正则文法构造有限态自动机形式化描述[例子] 7.3句法结构的自动机识别7.3.4按有限态自动机确定正则文法形式化描述[例子] 作业求一有限态自动机，它只能接受由“偶数个a”与/或“偶数个b”组成的任意字符串，例如：aa,bb,abab,abba,baba等。 7.3句法结构的自动机识别7.3.5下推自动机和上下文无关文法上下文无关语言的范式任何上下文无关文法的生成式A->β都可以写成乔姆斯基范式或格雷巴赫标准式乔姆斯基范式形式：A->BC，A->a，其中[例子]格雷巴赫标准式形式：A->aα，其中[例子] 7.3句法结构的自动机识别7.3.5下推自动机和上下文无关文法构造下推自动机的原因若正则文法的生成规则为A->aB，生成式的左侧和右侧都只有一个非终止符，则用有限态自动机的状态转换来表达就已经足够了。但在上下文无关文法中，生成式左侧只有一个非终止符，但右侧不止一个非终止符，如A->aBC。对于A->aα的一般情况，生成式右侧可以是任意数目的非终止符，如写成A->aA1A2…An。在这种情况下，如果仍旧用有限态自动机来识别，当自动机接受了a后，状态A只能转换到A1，下一步仅能考虑从A1开始，A2…An都被忽略了。结论：用有限态自动机不能识别上下文无关文法。 7.3句法结构的自动机识别7.3.5下推自动机和上下文无关文法下推自动机的概念下推自动机针对上述情况，另行配置一个堆栈来压入任意数目的非终止符。这些非终止符都应包括在上下文无关文法之中。堆栈：后进先出，就是最后一个被压入的非终止符始终处于栈的顶部。在没有压入任何符号串之前，栈顶内容为起始符。在处理过程中，栈顶的非终止符Ai与输入字符串中的终止符a共同决定了自动机状态的转移，而在输入终止符使自动机状态转移的同时，栈顶内容亦改变。带有这种堆栈结构成为下推自动机的特点。 7.3句法结构的自动机识别7.3.5下推自动机和上下文无关文法下推自动机的概念根据下推自动机的特点，下推自动机不能只用一个状态参数qi来描述，而必须加上栈顶内容ri。若将栈顶内容也看作是一个状态，则两个参数联合的格局(qi,ri)才能准确地描述自动机的当前状态。输入终止符a，将引起自动机的格局转移，每个输入终止符所引起的新格局，都和原格局有关，即与以前的输入内容有关。所以，每个新格局都能反映当时及以前的输入符号串。按此推理，自动机的最后格局也就反映了输入句子的全部符号，可用它来进行句子的识别。 7.3句法结构的自动机识别7.3.5下推自动机和上下文无关文法下推自动机的模型和定义下推自动机构造模型 7.3句法结构的自动机识别7.3.5下推自动机和上下文无关文法下推自动机的模型和定义下推自动机实质上是在有限态自动机上再加上一个后进先出的堆栈，堆栈的一段固定，只能在另一端上存或取。通常用Г代表转换过程中处于栈顶的有限字母集。Г={Zi|i=1,2,…,n} 7.3句法结构的自动机识别7.3.5下推自动机和上下文无关文法下推自动机的模型和定义下推自动机定义映射的含义：在自动机q状态下和堆栈顶为Z时，输入符号a，这时造成的映射使自动机进入下一个格局(qi,ri)，即原来处于栈顶的符号Z被压入栈内，而栈顶变成ri串中的首位符号，自动机进入状态qi。 7.3句法结构的自动机识别7.3.5下推自动机和上下文无关文法下推自动机的模型和定义格局变幻的表达式：变换式的含义：对应于映射规则δ，输入一个符号a，可使下推自动机M从格局(q,Zr)转向(qi,rir)，这里Z为转换前的栈顶符号，ri为转换后的栈顶符号串。ri代表一个符号串，这时栈顶符号应为ri串中的首位符号。一个连串导出关系若存在，则对1~n之间的所有i，有 7.3句法结构的自动机识别7.3.5下推自动机和上下文无关文法下推自动机接受语言的方式终止状态方式定义：下推自动机用终止状态方式所接受的语言T(M)定义为：含义：当下推自动机M从起始状态q0开始到达终止状态q，同时其堆栈栈顶符号从起始符号Z0开始变成r，则接受一个句子x，这是利用状态参数q是否到达终止状态集F来识别语言的方式。所有识别的句子x的集合就是下推自动机所接受的语言T(M)。 7.3句法结构的自动机识别7.3.5下推自动机和上下文无关文法下推自动机接受语言的方式空堆栈方式定义：下推自动机用空堆栈方式所接受的语言N(M)定义为：含义：不管q是否到达终止状态，只要堆栈变空，输入句子x就被接受，这是利用输入x的过程中堆栈符号r的变换来识别语言的方式。 7.3句法结构的自动机识别7.3.5下推自动机和上下文无关文法下推自动机接受语言的方式[例子]在接受xcxR,x={0,1}*的句型时：在状态q1时可反复使用δ(q1,a,A)接受x，其中a=0或1，A=R,B或G，并使下推自动机存有符号串γ=(RU{B,G}*)R接受符号c后，状态变为q2在状态q2时，每接受一个符号（0或1），堆栈中的符号被上推，γ被取出时的次序与γ存入时的次序恰好相反，故在q2状态下接受xR因此，L(G)为xcxR 7.3句法结构的自动机识别7.3.5下推自动机和上下文无关文法下推自动机与上下文无关语言的联系描述[例子] 7.4基元的提取模式识别的主要任务之一就是图形的识别。描述一个待识别的图形模式可以借助于一组基元，用语言结构法进行识别。基元对应于文法中的终止符，它是构成句子的最基本单位。选择好的基元对有效地进行句法模式识别是十分重要的，可惜的是目前基元选择还没有一个通用的方法，只能根据具体因素而定。模式的数据性质待识别对象的具体应用识别系统所用的技术 7.4基元的提取基元选择应注意的两点基元应是模式的基本单元，且易于利用它们之间的结构关系来紧凑方便地描述模式。例如：图形识别中各子图形之间的连接关系就可以用基元的结构关系来表达基元是最简单的子模式，它本身的结构信息已不重要，可用非语言方法（如统计方法、几何尺寸度量等）来提取。例如：识别手写文字用笔画作为基元比较有效，语音识别采用音素作为基元比较方便，心电图识别采用收缩波和扩张波的波形变化特征作为基元比较直接，等等。 7.4基元的提取在图形识别中，对平面图形可以采用两种类型的基元。从图形的边界、轮廓或骨架提取基元；以图形的基本组成区域作为基元。 7.4基元的提取7.4.1图形边界或骨架的基元选择Freeman链码可以用来描述图形的边界和骨架。 7.4基元的提取7.4.1图形边界或骨架的基元选择Freeman链码可以用来描述图形的边界和骨架。将待描述的曲线量化，曲线落在每一个方格中的各个分段可用8个方向之一来近似。例如，图中的曲线可表示为字符串：4444570767077可以通过句法分析来判别待识别的曲线。 7.4基元的提取7.4.1图形边界或骨架的基元选择Freeman链码可以用来描述图形的边界和骨架。在实际应用中，直接采用Freeman链码中的元素作为基元，会将曲线图形分割的太细，造成句法分析的复杂化。若选用若干种有共性特点的弧形曲线段作为基元，亦能描述图形，但比直接用Freeman链码简单。可用一种变换把原来的8种基本方向变换成一组弧形曲线基元，使描述模式的句子短一些。 7.4基元的提取7.4.1图形边界或骨架的基元选择可将模式的描述用字符串的形式表示为：V=V1V2…Vn，其中Vi是串中的一个基元，它可以是一段不变曲率的弧，多边形的一条边，或一段二次曲线的弧等等。若Vi取自有穷字母表，则可直接采用句法分析。进行句法分析之前要消除噪声，对边界曲线进行预处理。 7.4基元的提取7.4.1图形边界或骨架的基元选择例子：亚中央着丝点染色体的多级结构描述 7.4基元的提取7.4.1图形边界或骨架的基元选择例子：亚中央着丝点染色体的多级结构描述基元采用曲线段a,b,c,d从左到右把树的叶子汇集起来，就构成了一个字符串，恰好表达了染色体的边界形状。用符号编码表示为：babcbabdbabcbabd，表达了这类染色体的一个句子。 7.4基元的提取7.4.1图形边界或骨架的基元选择讨论描述一种图形采用哪种基元最合适没有统一的标准和方法，因图形曲线的不同而异。一般可兼顾两点基元的提取方法尽可能简单描述曲线的句子尽量短一些 7.4基元的提取7.4.2按区域划分成多边形近似的基元这种基元着眼于待识别图形的区域。将待识别的图形理想化为一个多边形，再以若干个凸多边形的“并”来表示该多边形，而凸多边形又用若干半平面的“交”来组成。用形式语言表示半平面是字母凸多边形是由这些字母组成的字由这些字组成的句子就相当于代表图形的多边形可采用凸多边形作为基元 7.4基元的提取7.4.2按区域划分成多边形近似的基元例子：采用凸多边形作为基元的五边形用穷举试探法求取基元的试探步骤[例子] 7.5形式语言在图形识别中的应用7.5.1各种文法用于模式识别的功能比较前面讨论了基元的提取问题，下面要根据各种提取的基元来构造适当的文法，以产生出描述所要识别的图形的一种语言。从理论上讲，最好是能有一个推断文法的机器，它能根据给定的一些符号串的集合，推断出一个合适的文法。但遗憾的是，在实际中除了某些非常特殊的情况外，至今还没有这样一种有效的机器。一般上仍是由设计者凭自己的经验和所谓的先验知识来构造文法。 7.5形式语言在图形识别中的应用7.5.1各种文法用于模式识别的功能比较构造图形识别的文法仍以前面介绍的形式语言为基础。一般来说，希望采用有很强描述图形能力的文法，但这样做反过来又增加识别器的复杂性。 7.5形式语言在图形识别中的应用7.5.1各种文法用于模式识别的功能比较正则文法的生成式最为简单，它所受的限制也最多，描述图形模式的能力最差，但在句法分析中是最容易实现的，因为一定存在一个确定的有限态自动机与之对应。上下文无关文法所受的限制要少一些，描述能力要强一些，但为了接受这种文法产生的语言，通常要求非有限、非确定性的句法分析步骤，与之对应的是一个不确定的下推自动机，因而实现起来比确定的有限态自动机复杂。上下文有关文法所产生的语言的分析，就更困难了。 7.5形式语言在图形识别中的应用7.5.1各种文法用于模式识别的功能比较[例子][采用上下文有关文法][采用上下文无关文法][采用正则文法]结果分析n为有限整数时可构造上下文无关文法，n限于3以内可构造正则文法。但显然，正则文法由于其规则数增多，造成其复杂性增加，而且随着n的增大，规则数更是倍增，相比而言，上下文无关文法就简洁得多。 7.5形式语言在图形识别中的应用7.5.1各种文法用于模式识别的功能比较讨论在具体应用时，只能根据问题，在增加文法描述能力和简化句法分析之间权衡，采取一些办法来进行折衷，针对具体问题来构造文法。一般可通过对正则文法进行某些修改而使问题简化。例如文法的形式可能是上下文无关的，但设计语言则可以用有限态语言来近似。 7.5形式语言在图形识别中的应用7.5.1各种文法用于模式识别的功能比较讨论此外，还要注意不要使构造的文法所产生的符号串过剩。图形符号串的数目总是有限的，但多数情况下所构造的文法，可能产生数目很大或无限多的符号串。虽然希望过剩的符号串与代表图形的符号串相似，但遗憾的是实际情况往往不是这样，过剩的符号串常常是由文法自行构造出来的。当过剩的符号串包含了属于其它类别的图形符号串时，问题就会变得非常严重，这是必须进行校正，把过剩的符号串从该文法所产生的语句中排除掉。 7.5形式语言在图形识别中的应用7.5.1各种文法用于模式识别的功能比较讨论综上所述，建立一个文法，要同时考虑图形基元的选择和文法的构成，要兼顾文法的描述能力和句法分析系统的简洁性，所以文法一般由设计者根据具体情况来构造。可以先由设计者提出基本性的文法和各种折衷方案，然后利用人机交互系统在计算机上进行修改和实验，最终获得一种高效文法及其推断。 7.5形式语言在图形识别中的应用7.5.2程序文法为了使字符串文法的结构更为紧凑，可在乔姆斯基文法上加上生成式去向的标号，以规定某几条生成式使用之后，下一次只能用规定的另外哪几条生成式。这样可以使原来的字符串文法使用起来更为方便，易于检查。 7.5形式语言在图形识别中的应用7.5.2程序文法定义和例子[例1]这里，生成式(1)采用成功后可继续执行(1),(2)或(3)，而且其本身可反复使用。生成式(2)成功后去向范围是(2),(3)，即使用(2)后不能再使用(1)，但可用(2),(3)，这使P的生成语句中a,b,c只能各自连续地出现。当应用的去向范围遇到空时，则生成停止。 7.5形式语言在图形识别中的应用7.5.2程序文法[例2]程序文法属于乔姆斯基文法的哪一种形式，决定于生成式的核。如果生成式的核为上下文无关形式，则这个文法是上下文无关的。如果程序文法的核是正则形式，则该文法是正则文法。 7.5形式语言在图形识别中的应用7.5.2程序文法[例3]可以证明，该上下文无关文法可以生成{anbncn|n>=1}这个程序文法的简洁程度和刚才介绍的生成同样语言的上下文有关文法相类似。 7.5形式语言在图形识别中的应用7.5.3图形描述语言PDL(PictureDescriptionLanguage)字符串文法中的基元与子模式的连接，按语法规则只能是左右连接，不能同时从四面八方连接，这种一维的连接方式不能满足描述复杂图形的要求。PDL中的基元是由两个点（称为“头”和“尾”）构成的矢量，它可以组成任一复杂结构的图形。对于二维图形，该基元就是平面上的一个有向线段，它只需有两个定义点，即头和尾。PDL用于描述图形模式识别是比较成功的。 7.5形式语言在图形识别中的应用7.5.3图形描述语言PDLPDL基元的连接规则 7.5形式语言在图形识别中的应用7.5.3图形描述语言PDLPDL基元的连接规则一个基元只能在头和尾两点上与其它基元连接，因此它是具有有向支路的图形结构，可用字符串文法来处理。空白基元：用来产生不连接的结构零点基元：表示头和尾处于相同的位置~b：表示基元的头尾反转 7.5形式语言在图形识别中的应用7.5.3图形描述语言PDL[例子][生成式中无循环性][生成式中有循环性] 7.5形式语言在图形识别中的应用7.5.3图形描述语言PDL讨论采用句法模式识别，可以提供两种或多种文法，并用每一种文法对不同模式样本进行句法分析。如果一个样本能成功地被某一种文法所分析，便可归为这一类。如果一个样本对各种文法都得不到被成功分析的结果，则该文法被拒绝。 7.5形式语言在图形识别中的应用7.5.3图形描述语言PDL[例子] 作业自己定义基元，用PDL文法生成0到5的字符，字符笔划用七划样式。提示：可参照例题中的基元定义 7.5形式语言在图形识别中的应用7.5.4树文法如果一个图形模式易于用树的结构来描述，则可采用树文法。它可将一维连接的符号串文法向多维推广，是一种应用较广泛的高维文法。 7.5形式语言在图形识别中的应用7.5.4树文法例子对一个边长为a,b和c的立方体，如果用一维字符串描述，有的边会重复，用树表示可直接分成三个叉，每条边仅出现一次。 7.5形式语言在图形识别中的应用7.5.4树文法树的定义：树是具有一个或一个以上结点的有限集T，它具有以下性质：具有唯一的被指定为根的结点。其余的结点被分到m个不相交的集合T1,T2,…,Tm中，且这些子集的每一个又都是树，称为T的子树。从定义可以看出，树的每个结点都是这个树中所包含的某个子树的根。一个结点具有子树的个数称为该结点的秩。秩的相关定义秩：一个结点的直接分支数定义为该结点的秩。叶结点：秩为零的结点称为叶结点（终端结点）。分支结点：秩不为零的结点称为分支结点（非终端结点）。 7.5形式语言在图形识别中的应用7.5.4树文法讨论在计算机中数据的表示是有序的，所以子树的排列也是有一定的相对次序。同一层上各子树间相互交换位置就构成不同的树。因此，树是有序的。比如前面的立方体，叶结点就是有序的。 7.5形式语言在图形识别中的应用7.5.4树文法结论用树来描述图形时，不但要知道树的结点，还要知道与其相邻结点的关系。这里，相邻结点的关系确定了基元与图形的其它子结构间的物理关系。 7.5形式语言在图形识别中的应用7.5.4树文法秩的集合的表示设X是结点符号的有穷集，a是结点的编号，α(a)是结点a上的一棵树，则α(a)的秩的集合可用r(α(a))表示。若α(a)能够具有的秩为r1,r2,…,rn，可写成r(α(a))={r1,r2,…,rn}[例子]树的另一种表示法—圆括号法与左括号紧挨着的字母表示根。其子树是紧挨着根字母的一串左右成对的括号中的内容。[例子] 7.5形式语言在图形识别中的应用7.5.4树文法树文法的定义上下文无关文法和树文法的对应关系如果将树用圆括号法表示，则上下文无关语言中的字符串和由树文法生成的树之间存在对应关系。描述G’T中的每一次推导，就用圆括号表示出了推导过程中生成式的使用次序，根据它可确定生成式的构造。[例子] 作业试用树文法生成单位边长的立方体，定义三个基元为立方体的三种方向的边。 7.6句法分析若对两类模式进行分类，应判别描述模式的字符串x是否可由文法G产生。假若G能生成x，则x属于ω1，否则x属于ω2。推广到M类模式，应先确定M种文法，它能生成M类语言L(Gi)，i=1,2,…,M。一个未知类别的模式字符串x，当它是属于L(Gi)中的一个句子，则x属于ωi。假如x不属于任何一种语言，则它可被拒识，即x不被接受为M类中的任一类。 7.6句法分析句法识别其原理图 7.6句法分析采用有限态自动机对未知模式进行识别，实质上是对输入字符串从左向右进行推导，判断它是否为机器所接受。这种识别方法计算工作量小，但是没有对语法结构进行分析。在某些情况下，不仅需要判断字符串是否属于L(G)，还要知道它的语法结构，以便改进文法，这就需要采用句法分析（句法剖析）。 7.6句法分析7.7.1通过生成树的句法分析生成树构造原则已知一个句子x和文法G，若x是用上下文无关文法生成的，则其生成树可用如下原则构造：把推导中出现的属于VT的元素作为树的叶，属于VN的元素作为树的结点，每一片叶和每一个结点都设置一个标号。将S作为树根的标号。如果一个结点的后代子句中，至少有一个字符与它本身不同，则该结点的标号必属于VN。如果结点A有k个直接后代A1,A2,…,Ak，且它们是从左到右排列。则一定存在这样一条生成式：A->A1A2…Ak。 7.6句法分析7.7.1通过生成树的句法分析分析的两种方法：“自上而下”和“自下而上”“自上而下”分析法是从G中的起始符S着手，应用P中的生成式从左至右逐个代换非终止符，以得到x。“自下而上”分析法是从x本身着手，反方向使用生成式，寻找其中与某个生成式右侧部分相同的字符子串，将它用生成式左边的字符代换，直至最后达到起始符S。 7.6句法分析7.7.1通过生成树的句法分析[例子][分析a2b2c2][分析a2bc]自下而上自上而下 7.6句法分析7.7.2CKY(Cocke-Kasami-Younger)分析算法采用树结构的分析算法实质上是穷举试探，它对任意上下文无关文法所需的分析时间，可能按字符串长度呈指数增长。为此，采用CKY的分析算法，其时间为输入串长度的三次方。 7.6句法分析7.7.2CKY(Cocke-Kasami-Younger)分析算法问题描述设描述某类模式的文法是上下文无关的，G=(VN,VT,P,S)，其生成式是乔姆斯基范式。设输入字符串x=a1a2…an,|x|=n，要求设计CKY算法来判断x是否属于L(G)。CKY算法的关键构表原则构表步骤 7.6句法分析7.7.2CKY(Cocke-Kasami-Younger)分析算法[CKY算法实例] 7.6句法分析7.7.3最小距离误差的句法校正分析上面的识别过程并未考虑图形模式的随机干扰。实际上，在获取模式的基元描述时，由于随机噪声的干扰，可能发生部分的基元描述错误。例：模式的正确描述字符串为abcbbc，受干扰后成为一有误差的字符串abbbbac。为了识别这种存在某些误差的串，在比较简单的场合，可以采用通过计算最小距离误差的校正句法分析。 7.6句法分析7.7.3最小距离误差的句法校正分析字符串的相似性度量字符串中的误差通常归纳为三类：代换误差、抹去误差和插入误差，可将它们用相应的转换式来表示。代换误差的转换抹去误差的转换插入误差的转换转换距离[例子] 7.6句法分析7.7.3最小距离误差的句法校正分析误差覆盖文法的构成最小距离误差的句法校正分析设L(G)是一给定文法，y是一个给定的带有误差的句子，则最小距离误差的句法校正分析实质上就是在L(G)中找出x，使其满足最小距离准则。d(x,y)的计算：构成一个误差校正程序的过程时，修改给定文法G，把它扩大为G’，使得L(G’)不仅包括L(G)，而且包括能生成具有上述三类误差的所有可能的句子。根据G’对带有误差的句子进行分析，计算能产生三类误差的生成式的最少应用次数，从而求得关于最小距离的度量。构成误差覆盖文法G’的过程 7.6句法分析7.7.3最小距离误差的句法校正分析最近邻分类两类模式若已知两类模式，分别用文法G1和G2来描述，其误差覆盖文法分别为G1’和G2’。对于一个待分类的输入模式x，用最小距离误差分析算法计算出它与L(G1’)和L(G2’)之间的距离分别为d(x,L(G1’))和d(x,L(G2’))。如果有d(x,L(G1’))i，有d(x,L(Gi’))