中科院《模式识别》——第七章

1、第七章 句法模式识别第七章 句法模式识别 统计模式识别是基于模式特征的一组测量值来组成特征向量，用决策理论划分特征空间的方法进行分类。 基于描述模式的结构信息，用形式语言中的规则进行分类，可以更典型地应用于景物图片的分析。 因为在这类问题中，所研究的模式通常十分复杂，需要的特征也很多，仅用数值上的特征不足以反映它们的类别。第七章 句法模式识别 句法模式识别系统的组成 图像预处理 图像分割 基元及其关系识别 句法分析第七章 句法模式识别 句法模式识别系统框图第七章 句法模式识别 对图像的结构信息描述第七章 句法模式识别 句法模式识别系统处理过程 待识别的输入图像，经过增强、去噪声等处理后，按识别

2、的具体对象分割成子图； 三角体D和长方体E 然后将子图分割成更简单的模式基元； 组成三角体和长方体的各个面L,T和X,Y,Z 判别基元之间的关系。 三角体D是由相互邻接的四边形L和三角形T组成 长方体E是有三个相互邻接的四边形X,Y和Z组成第七章 句法模式识别 句法模式识别系统处理过程 基元本身包含的结构信息已不多，仅需少量特征即可识别。 如果用有限个字符代表不同的基元，则由基元按一定结构关系组成的子图或图形可以用一个有序的字符串来代表。 假如事先用形式语言的规则从字符串中推断出能生成它的文法，则可以通过句法分析，按给定的句法（文法）来辨识由基元字符组成的句子，从而判别它是否属于由该给定文法所

3、能描述的模式类，达到分类的目的。第七章 句法模式识别 句法模式识别学习过程 为了要事先确定一个文法来描述所要研究模式的结构信息，同样需要采用模式的训练样本集把文法推断出来。 有了推断出来的文法，才可以对未知类别的字符串进行句法分析，达到分类的目的。 这一过程类似于统计模式识别中的学习过程，但文法推断过程远不及统计学习来的成熟。7.1 集合论中的关系运算 要进行句法识别中基元之间关系的判别，首先要明确关系运算。 “关系”在客观世界中广泛存在 社会生活：父子关系，母子关系，兄弟关系，等等； 数学运算：大于、等于和小于关系，函数关系，等等。 二元关系 凡是一对对象之间的关系，都是二元关系。7.1 集

4、合论中的关系运算 二元关系的相关概念 有序偶 设用表示一有序偶，它可以代表迪卡儿坐标，例如，等，它们表示平面坐标上的不同点。 两个有序偶和相等，定义为 迪卡儿积 设A和B是任意两个集合，由A中的一个元素和B中的一个元素组成有序偶，那么由A和B中所有元素组成的有序偶集合，称为A和B的迪卡儿积，写成A x B。 公式表达： 例子)By()Ax( | )y, x(BA7.1 集合论中的关系运算 二元关系的相关概念 二元关系的定义及表示 任意有序对的集合定义一种二元关系，简称为关系 表示 设一有序对 ，其中R是一种关系，则记为xRy 例子7.1 集合论中的关系运算 二元关系的性质 定义：自反 集合X中

5、的关系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是传递的 例：若abc，则ac，表明”“关系是传递的 定义：非自反 集合

6、X中的关系R是非自反的，只要对X中的每个x，有不属于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是自反的、对称的和传递的，则称它是一个等价关系。 实数集合中的数值相等 三角形集合中的三角形相似 一个班内同学之间的同班

7、关系 等价类定义 等价类性质 集合X上的等价关系R所构成的类两两不相交，且覆盖了整个集合X。7.1 集合论中的关系运算 等价关系 可以用图形方法分析研究等价划分：由于等价关系是自反的、对称的、传递的，因此由这些性质的图形特点可知： 一个集合X上的等价关系R的关系图，其每个结点必有环； 若两个结点间有边相连，则必有方向彼此相反的两条有向边； 若图中任何两个结点是可达的，则必有边直接相连。 例子7.1 集合论中的关系运算 兼容关系 如果X中的关系R是自反的而且是对称的，则称R是一个兼容关系。 所有的等价关系是兼容关系； 兼容关系不一定是传递的。 偏序关系 集合P上的二元关系R称为P上的一个偏序关系

8、，当且仅当R是自反的、反对称的和传递的。 偏序关系通常用“=”表示，但注意“ A”叔侄”C7.1 集合论中的关系运算 二元关系的复合 关系图7.1 集合论中的关系运算 二元关系的复合 关系的复合运算可以施加于自身 表示为：RR =R2，RRR =R3 ， 传递闭包 例子7.2 形式语言理论和句法模式识别 形式语言的起源可以追溯到二十世纪五十年代； 乔姆斯基(Chomsky)等科学家在研究语言的工作中发展了文法的数学模型； 其基本目的是发展一种应用于计算机的文法，使它有描述自然语言的能力，例如英文。 如果能做到这一点，则有希望“教”计算机理解自然语言，以达到翻译的目的。7.2 形式语言理论和句法

9、模式识别 形式语言的基本目的迄今为止尚未完全实现，但在这个领域的研究成果却大大冲击了其它一些领域 计算机编译系统的设计 计算机语言 自动机理论 模式识别7.2 形式语言理论和句法模式识别 在模式识别中，如果大量复杂的模式的集合，能用一组为数不多的简单的模式基元和文法规则来描述，则对每一个模式的识别，就可以按给定的一组文法结构规则来剖析； 如果解析的结果表明，模式基元能为给定的文法规则所接受，则可判别它属于该模式类，否则就不属于该模式类。7.2 形式语言理论和句法模式识别7.2.1 形式语言理论中的某些定义 形式语言是一种抽象语言，它可以包括人类使用的自然语言、计算机使用的各种语言、数学中的公式

10、语言等。 自然语言（英文）：它的基本组成是有限个字母，将字母（组成的单词）按一定的文法规则排列，可以构成句子，而一种语言则是所有句子的集合。 人类的自然语言是一个不可数的有穷集 英文：26个字母按一定的文法规则组合，可以表达无数的思想内容。7.2 形式语言理论和句法模式识别7.2.1 形式语言理论中的某些定义 字母表和符号串 字母表：以某些符号作为元素的非空有穷集，以V或表示。 符号串：由字母表中符号组成的任何有穷序列。 例子 空符号串：不包含任何符号的串，用表示。 符号串的长度：符号串x所包含的符号个数，用|x|表示。 例子 符号串的联接：若x和y都是符号串，则把y符号串写在x符号串之后，就

11、得到联接的符号串xy。 例子7.2 形式语言理论和句法模式识别7.2.1 形式语言理论中的某些定义 字母表和符号串 符号串集合的乘积 例子 如果A和B只是代表一个符号串，而不是符号串的集合，则乘积AB与符号串的联接结果相同。 符号串和符号串集合A的幂 集合A的正闭包、闭包 字母表V的幂 集合V的正闭包、闭包 例子7.2 形式语言理论和句法模式识别7.2.1 形式语言理论中的某些定义 文法 一种语言中构成句子所必须遵守的规则； 由某种语言的字母表中的字母所组成的串不一定都是该语言的句子； 只有当一个串符合该语言的文法规则时，才能算是该语言的句子，否则就不是该语言的句子。7.2 形式语言理论和句法

12、模式识别7.2.1 形式语言理论中的某些定义 文法定义 文法举例 在生成规则P中，带的符号称为语法元，不带的符号称为单词； 一个简单句的生成由语法元()开始，反复把生成规则中箭头左边的部分用其右边的部分替换，直到所得的形式中不再出现语法元而只有单词为止。 简单句“The boy runs.”符合给定的文法规则，因为它可以由上述的文法规则产生。 生成过程7.2 形式语言理论和句法模式识别7.2.1 形式语言理论中的某些定义 文法举例 文法树7.2 形式语言理论和句法模式识别7.2.1 形式语言理论中的某些定义 利用文法树可以阐明文法的形式化定义： 文法树的根一定是文法G的起始符S； 树的叶一定是

13、终止符； 树的每一个分支（子树）在沿着根到叶的方向上可以表示成一个直接推导的生成式； 如果利用文法树的逆过程，则可将生成过程重新构造出来。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由以下

14、形式的表达式组成：-，其中是V+中的字符串， 是V*中的字符串，“- ”表示字符串被所取代。 =表示根据文法G，由一字符串直接推导出另一字符串。 例子7.2 形式语言理论和句法模式识别7.2.2 语言的生成过程 句型和句子 定义 句型是由起始符开始进行推导而得到的由字母表中的符号（包括VN 、VT和）组成的任意字符串； 句型和句子关系 句子一定是由字母表中终止符组成的字符串。7.2 形式语言理论和句法模式识别7.2.2 语言的生成过程 语言 定义 短语 定义 从起始符推导一个句子的过程，实际上就是将推导过程中句型的一部分不断用短语来取代的过程，这种文法称为短语结构文法。7.2 形式语言理论和句

15、法模式识别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开始所推导出的所有终止符的集合，它满足两个条件 每一

16、个字符串只能由终止符组成，即每一个字符串都是终止符句子； 每一个字符串都能从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 文法

17、的分类 1型文法（上下文有关文法） 生成式形式 说明 在1和2之间的非终止符可以重写为，这里1和2称为句型1A2对于A的上下文； 不是在1和2之间的A不能使用此规则。 例子 从表面上看似乎上下文并不完整； 但根据1型文法的定义， 1、2属于V*，可以有1=2 =； 因此生成规则P可以改写成例中生成式右侧所示形式。7.2 形式语言理论和句法模式识别7.2.2 文法的分类 2型文法（上下文无关文法） 生成式形式 说明 该文法表明生成式左侧为单变量，可由右侧的字符串来取代，因此是上下文无关的。7.2 形式语言理论和句法模式识别7.2.2 文法的分类 3型文法（正则文法） 生成式形式 说明 该文法表明

18、规则右侧一定要首先含有非终止符。7.2 形式语言理论和句法模式识别7.2.2 文法的分类 四种文法比较 正则文法（3型文法）生成规则的右侧若不强调终止符的首先出现，就变成上下文无关文法（2型文法）； 上下文无关文法（2型文法）生成规则的左侧若不强调单变量，而加以上下文限制，就变成上下文有关文法（1型文法）； 上下文有关文法（1型文法）去掉上下文的限制，就变成无约束文法（0型文法）。7.2 形式语言理论和句法模式识别7.2.2 文法的分类 四种文法比较 包含关系： 正则文法 上下文无关文法 上下文有关文法 无约束文法 所有正则文法都是上下文无关的； 所有上下文无关文法都是上下文有关的； 所有上下

19、文有关文法都是无约束的。 在句法模式识别中，多采用上下文无关文法和正则文法。7.2 形式语言理论和句法模式识别7.2.2 文法的分类 例1：无约束文法 例2：上下文有关文法 例3：上下文无关文法 例4：正则文法作业 写出上下文无关文法，其终止符集VT=a,b能生成语言L(G)=ab,ba,aba,bab,abab,baba,7.3 句法结构的自动机识别 一种类别的模式，可以用一个文法来描述。 要识别一个未知的模式，可以先用其基元表征成一个字符串或句子，然后再用该文法进行判断。 若能被接受，则说明它是属于该文法所生成的语言，亦即它是属于该类模式，否则就不属于该类模式。 自动机就是一种句法识别器，

20、它可以判断一个句子是否属于某种语言，并且自动机的类型与文法的类型有着某种对应关系。7.3 句法结构的自动机识别7.3.1 有限态自动机 有限态自动机是研究自动系统的一种数学模型，它能模拟多种离散的自动系统。 结构概念实例：八进制计数器和有限态自动机模型 一个八进制计数器，要求每逢计数到6输出一脉冲。 将该装置看成是一个离散系统。7.3 句法结构的自动机识别7.3.1 有限态自动机 结构概念实例：八进制计数器和有限态自动机组成 输入信息：接受顺序输入的计数脉冲作为输入信息，有脉冲时为1，无脉冲时为0，以0,1组成的字符串作为输入。 输出信息：当计数器的状态到达6时，输出一脉冲，其余情况均输出为0

21、 ，以0,1组成的字符串作为输出。 内部状态：触发器q1、q2和q3所处的0或1的状态。 该计数装置是否有脉冲输出，不仅依赖于当前的输入信息，而且还依赖于前一时刻触发器所处的状态亦即该触发器的内部状态。这里三个触发器所处的状态的集合q1, q2, q3属于有限个状态的集合。7.3 句法结构的自动机识别7.3.1 有限态自动机 结构概念实例：八进制计数器和有限态自动机组成 状态转换：设以表示输入0,1的集合，以Q表示内部状态的集合q1, q2 , q3，则状态转换函数可以表示成Q和到Q的映射，写成迪卡儿乘积的形式为：Q x - Q， 称为状态转移函数。 内部状态的转换既依赖于输入，也依赖于前一时

22、刻的内部状态。 输出函数：在某时刻的输出信息，一般由同一时刻的输入信息和内部状态所决定。 它也是内部状态与输入的映射 从上述组成可以看出，一个离散的有限状态的自动系统由五部分组成。一个有限态自动机A是模拟多种离散自动系统的一种数学模型。7.3 句法结构的自动机识别7.3.1 有限态自动机 有限态自动机定义 映射的状态图表示： 并不是全部可能的输出函数都一定是需要的输出终止状态，只有其中部分输出状态才是感兴趣的输出终止状态。 有限态自动机抽象结构示意图7.3 句法结构的自动机识别7.3.1 有限态自动机 结构示意图描述 控制器上记录了各种状态，并且各种状态之间按一定的规则在控制器中变化，而变化的

23、改变是受输入支配的。 具体来说，控制器相对于输入磁带自左向右移动，每接受一个输入符号便右移一个单位，并改变一次状态，直至一个句子的全部符号输入结束。 同时，每输入一个符号，控制器要根据状态规则来判断能否接受该符号，若所有的符号都能被接受，就说明该句子属于该自动机所能接受的那种语言。 此时，状态变换(q,a)=q表示“处于状态q并正在扫描输入符号a”的自动机A，将读入磁头右移一个单元，并转到状态q。 自动机输入句子后，若(q,x)=q且q在F中，则称句子x被有限态自动机A所接受。7.3 句法结构的自动机识别7.3.1 有限态自动机 正规集 由有限态自动机A接受的所有句子x的集合表示为： T(A)

24、=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 非确定有限态自动机 形

25、式化定义 例子7.3 句法结构的自动机识别7.3.2 非确定有限态自动机 非确定有限态自动机与确定有限态自动机的关系 非确定有限态自动机是确定有限态自动机的推广 形式化描述7.3 句法结构的自动机识别7.3.2 非确定有限态自动机 非确定有限态自动机与确定有限态自动机的关系 例子 非确定的有限态自动机和确定的有限态自动机统称为有限态自动机7.3 句法结构的自动机识别7.3.3 按正则文法构造有限态自动机 形式化描述 例子7.3 句法结构的自动机识别7.3.4 按有限态自动机确定正则文法 形式化描述 例子作业 求一有限态自动机，它只能接受由“偶数个a”与/或“偶数个b”组成的任意字符串，例如：a

26、a, 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。

27、对于A-a的一般情况，生成式右侧可以是任意数目的非终止符，如写成A-aA1A2An。 在这种情况下，如果仍旧用有限态自动机来识别，当自动机接受了a后，状态A只能转换到A1，下一步仅能考虑从A1开始， A2An都被忽略了。 结论：用有限态自动机不能识别上下文无关文法。7.3 句法结构的自动机识别7.3.5 下推自动机和上下文无关文法 下推自动机的概念 下推自动机针对上述情况，另行配置一个堆栈来压入任意数目的非终止符。这些非终止符都应包括在上下文无关文法之中。 堆栈：后进先出，就是最后一个被压入的非终止符始终处于栈的顶部。 在没有压入任何符号串之前，栈顶内容为起始符。 在处理过程中，栈顶的非终止符

28、Ai与输入字符串中的终止符a共同决定了自动机状态的转移，而在输入终止符使自动机状态转移的同时，栈顶内容亦改变。 带有这种堆栈结构成为下推自动机的特点。7.3 句法结构的自动机识别7.3.5 下推自动机和上下文无关文法 下推自动机的概念 根据下推自动机的特点，下推自动机不能只用一个状态参数qi来描述，而必须加上栈顶内容ri 。 若将栈顶内容也看作是一个状态，则两个参数联合的格局(qi, ri)才能准确地描述自动机的当前状态。 输入终止符a，将引起自动机的格局转移，每个输入终止符所引起的新格局，都和原格局有关，即与以前的输入内容有关。所以，每个新格局都能反映当时及以前的输入符号串。 按此推理，自动

29、机的最后格局也就反映了输入句子的全部符号，可用它来进行句子的识别。7.3 句法结构的自动机识别7.3.5 下推自动机和上下文无关文法 下推自动机的模型和定义 下推自动机构造模型7.3 句法结构的自动机识别7.3.5 下推自动机和上下文无关文法 下推自动机的模型和定义 下推自动机实质上是在有限态自动机上再加上一个后进先出的堆栈，堆栈的一段固定，只能在另一端上存或取。 通常用代表转换过程中处于栈顶的有限字母集。 =Zi|i=1,2,n7.3 句法结构的自动机识别7.3.5 下推自动机和上下文无关文法 下推自动机的模型和定义 下推自动机定义 映射的含义：在自动机q状态下和堆栈顶为Z时，输入符号a，这

30、时造成的映射使自动机进入下一个格局(qi, ri)，即原来处于栈顶的符号Z被压入栈内，而栈顶变成ri串中的首位符号，自动机进入状态qi 。7.3 句法结构的自动机识别7.3.5 下推自动机和上下文无关文法 下推自动机的模型和定义 格局变幻的表达式： 变换式的含义： 对应于映射规则，输入一个符号a，可使下推自动机M从格局(q, Zr)转向(qi, rir)，这里Z为转换前的栈顶符号，ri为转换后的栈顶符号串。 ri代表一个符号串，这时栈顶符号应为ri串中的首位符号。 一个连串导出关系 若存在 ，则对1n之间的所有i，有7.3 句法结构的自动机识别7.3.5 下推自动机和上下文无关文法 下推自动机

31、接受语言的方式 终止状态方式 定义：下推自动机用终止状态方式所接受的语言T(M)定义为： 含义：当下推自动机M从起始状态q0开始到达终止状态q，同时其堆栈栈顶符号从起始符号Z0开始变成r，则接受一个句子x，这是利用状态参数q是否到达终止状态集F来识别语言的方式。 所有识别的句子x的集合就是下推自动机所接受的语言T(M)。rF,qr),(q,| )Z,(q:x|xT(M)*007.3 句法结构的自动机识别7.3.5 下推自动机和上下文无关文法 下推自动机接受语言的方式 空堆栈方式 定义：下推自动机用空堆栈方式所接受的语言N(M)定义为： 含义：不管q是否到达终止状态，只要堆栈变空，输入句子x就被

32、接受，这是利用输入x的过程中堆栈符号r的变换来识别语言的方式。7.3 句法结构的自动机识别7.3.5 下推自动机和上下文无关文法 下推自动机接受语言的方式 例子 在接受xcxR, x=0,1*的句型时： 在状态q1时可反复使用(q1,a,A)接受x，其中a=0或1，A=R,B或G，并使下推自动机存有符号串=(RUB,G*)R 接受符号c后，状态变为q2 在状态q2时，每接受一个符号（0或1），堆栈中的符号被上推，被取出时的次序与存入时的次序恰好相反，故在q2状态下接受xR 因此，L(G)为xcxR7.3 句法结构的自动机识别7.3.5 下推自动机和上下文无关文法 下推自动机与上下文无关语言的联

33、系 描述 例子7.4 基元的提取 模式识别的主要任务之一就是图形的识别。描述一个待识别的图形模式可以借助于一组基元，用语言结构法进行识别。 基元对应于文法中的终止符，它是构成句子的最基本单位。 选择好的基元对有效地进行句法模式识别是十分重要的，可惜的是目前基元选择还没有一个通用的方法，只能根据具体因素而定。 模式的数据性质 待识别对象的具体应用 识别系统所用的技术7.4 基元的提取 基元选择应注意的两点 基元应是模式的基本单元，且易于利用它们之间的结构关系来紧凑方便地描述模式。 例如：图形识别中各子图形之间的连接关系就可以用基元的结构关系来表达 基元是最简单的子模式，它本身的结构信息已不重要，

34、可用非语言方法（如统计方法、几何尺寸度量等）来提取。 例如：识别手写文字用笔画作为基元比较有效，语音识别采用音素作为基元比较方便，心电图识别采用收缩波和扩张波的波形变化特征作为基元比较直接，等等。7.4 基元的提取 在图形识别中，对平面图形可以采用两种类型的基元。 从图形的边界、轮廓或骨架提取基元； 以图形的基本组成区域作为基元。7.4 基元的提取7.4.1 图形边界或骨架的基元选择 Freeman链码可以用来描述图形的边界和骨架。7.4 基元的提取7.4.1 图形边界或骨架的基元选择 Freeman链码可以用来描述图形的边界和骨架。 将待描述的曲线量化，曲线落在每一个方格中的各个分段可用8个

35、方向之一来近似。 例如，图中的曲线可表示为字符串：4444570767077 可以通过句法分析来判别待识别的曲线。7.4 基元的提取7.4.1 图形边界或骨架的基元选择 Freeman链码可以用来描述图形的边界和骨架。 在实际应用中，直接采用Freeman链码中的元素作为基元，会将曲线图形分割的太细，造成句法分析的复杂化。 若选用若干种有共性特点的弧形曲线段作为基元，亦能描述图形，但比直接用Freeman链码简单。 可用一种变换把原来的8种基本方向变换成一组弧形曲线基元，使描述模式的句子短一些。7.4 基元的提取7.4.1 图形边界或骨架的基元选择 可将模式的描述用字符串的形式表示为：V=V1

36、 V2 Vn，其中Vi是串中的一个基元，它可以是一段不变曲率的弧，多边形的一条边，或一段二次曲线的弧等等。 若Vi取自有穷字母表，则可直接采用句法分析。 进行句法分析之前要消除噪声，对边界曲线进行预处理。7.4 基元的提取7.4.1 图形边界或骨架的基元选择 例子：亚中央着丝点染色体的多级结构描述7.4 基元的提取7.4.1 图形边界或骨架的基元选择 例子：亚中央着丝点染色体的多级结构描述 基元采用曲线段a,b,c,d 从左到右把树的叶子汇集起来，就构成了一个字符串，恰好表达了染色体的边界形状。 用符号编码表示为：babcbabdbabcbabd，表达了这类染色体的一个句子。7.4 基元的提取

37、7.4.1 图形边界或骨架的基元选择 讨论 描述一种图形采用哪种基元最合适没有统一的标准和方法，因图形曲线的不同而异。 一般可兼顾两点 基元的提取方法尽可能简单 描述曲线的句子尽量短一些7.4 基元的提取7.4.2 按区域划分成多边形近似的基元 这种基元着眼于待识别图形的区域。 将待识别的图形理想化为一个多边形，再以若干个凸多边形的“并”来表示该多边形，而凸多边形又用若干半平面的“交”来组成。 用形式语言表示 半平面是字母 凸多边形是由这些字母组成的字 由这些字组成的句子就相当于代表图形的多边形 可采用凸多边形作为基元7.4 基元的提取7.4.2 按区域划分成多边形近似的基元 例子：采用凸多边

38、形作为基元的五边形 用穷举试探法求取基元的试探步骤 例子7.5 形式语言在图形识别中的应用7.5.1 各种文法用于模式识别的功能比较 前面讨论了基元的提取问题，下面要根据各种提取的基元来构造适当的文法，以产生出描述所要识别的图形的一种语言。 从理论上讲，最好是能有一个推断文法的机器，它能根据给定的一些符号串的集合，推断出一个合适的文法。 但遗憾的是，在实际中除了某些非常特殊的情况外，至今还没有这样一种有效的机器。 一般上仍是由设计者凭自己的经验和所谓的先验知识来构造文法。7.5 形式语言在图形识别中的应用7.5.1 各种文法用于模式识别的功能比较 构造图形识别的文法仍以前面介绍的形式语言为基础

39、。 一般来说，希望采用有很强描述图形能力的文法，但这样做反过来又增加识别器的复杂性。7.5 形式语言在图形识别中的应用7.5.1 各种文法用于模式识别的功能比较 正则文法的生成式最为简单，它所受的限制也最多，描述图形模式的能力最差，但在句法分析中是最容易实现的，因为一定存在一个确定的有限态自动机与之对应。 上下文无关文法所受的限制要少一些，描述能力要强一些，但为了接受这种文法产生的语言，通常要求非有限、非确定性的句法分析步骤，与之对应的是一个不确定的下推自动机，因而实现起来比确定的有限态自动机复杂。 上下文有关文法所产生的语言的分析，就更困难了。7.5 形式语言在图形识别中的应用7.5.1 各

40、种文法用于模式识别的功能比较 例子 采用上下文有关文法 采用上下文无关文法 采用正则文法 结果分析 n为有限整数时可构造上下文无关文法，n限于3以内可构造正则文法。 但显然，正则文法由于其规则数增多，造成其复杂性增加，而且随着n的增大，规则数更是倍增，相比而言，上下文无关文法就简洁得多。7.5 形式语言在图形识别中的应用7.5.1 各种文法用于模式识别的功能比较 讨论 在具体应用时，只能根据问题，在增加文法描述能力和简化句法分析之间权衡，采取一些办法来进行折衷，针对具体问题来构造文法。 一般可通过对正则文法进行某些修改而使问题简化。 例如文法的形式可能是上下文无关的，但设计语言则可以用有限态语

41、言来近似。7.5 形式语言在图形识别中的应用7.5.1 各种文法用于模式识别的功能比较 讨论 此外，还要注意不要使构造的文法所产生的符号串过剩。 图形符号串的数目总是有限的，但多数情况下所构造的文法，可能产生数目很大或无限多的符号串。 虽然希望过剩的符号串与代表图形的符号串相似，但遗憾的是实际情况往往不是这样，过剩的符号串常常是由文法自行构造出来的。 当过剩的符号串包含了属于其它类别的图形符号串时，问题就会变得非常严重，这是必须进行校正，把过剩的符号串从该文法所产生的语句中排除掉。7.5 形式语言在图形识别中的应用7.5.1 各种文法用于模式识别的功能比较 讨论 综上所述，建立一个文法，要同时

42、考虑图形基元的选择和文法的构成，要兼顾文法的描述能力和句法分析系统的简洁性，所以文法一般由设计者根据具体情况来构造。 可以先由设计者提出基本性的文法和各种折衷方案，然后利用人机交互系统在计算机上进行修改和实验，最终获得一种高效文法及其推断。7.5 形式语言在图形识别中的应用7.5.2 程序文法 为了使字符串文法的结构更为紧凑，可在乔姆斯基文法上加上生成式去向的标号，以规定某几条生成式使用之后，下一次只能用规定的另外哪几条生成式。 这样可以使原来的字符串文法使用起来更为方便，易于检查。7.5 形式语言在图形识别中的应用7.5.2 程序文法 定义和例子 例1 这里，生成式(1)采用成功后可继续执行

43、(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 可以证明，该上下文无关文法可以生成an bn cn |n=1 这个程序文法的

44、简洁程度和刚才介绍的生成同样语言的上下文有关文法相类似。7.5 形式语言在图形识别中的应用7.5.3 图形描述语言PDL(Picture Description Language) 字符串文法中的基元与子模式的连接，按语法规则只能是左右连接，不能同时从四面八方连接，这种一维的连接方式不能满足描述复杂图形的要求。 PDL中的基元是由两个点（称为“头”和“尾”）构成的矢量，它可以组成任一复杂结构的图形。 对于二维图形，该基元就是平面上的一个有向线段，它只需有两个定义点，即头和尾。 PDL用于描述图形模式识别是比较成功的。7.5 形式语言在图形识别中的应用7.5.3 图形描述语言PDL PDL基元的

45、连接规则7.5 形式语言在图形识别中的应用7.5.3 图形描述语言PDL PDL基元的连接规则 一个基元只能在头和尾两点上与其它基元连接，因此它是具有有向支路的图形结构，可用字符串文法来处理。 空白基元：用来产生不连接的结构 零点基元：表示头和尾处于相同的位置 b：表示基元的头尾反转7.5 形式语言在图形识别中的应用7.5.3 图形描述语言PDL 例子 生成式中无循环性 生成式中有循环性7.5 形式语言在图形识别中的应用7.5.3 图形描述语言PDL 讨论 采用句法模式识别，可以提供两种或多种文法，并用每一种文法对不同模式样本进行句法分析。 如果一个样本能成功地被某一种文法所分析，便可归为这一

46、类。 如果一个样本对各种文法都得不到被成功分析的结果，则该文法被拒绝。7.5 形式语言在图形识别中的应用7.5.3 图形描述语言PDL 例子作业 自己定义基元，用PDL文法生成0到5的字符，字符笔划用七划样式。 提示：可参照例题中的基元定义7.5 形式语言在图形识别中的应用7.5.4 树文法 如果一个图形模式易于用树的结构来描述，则可采用树文法。 它可将一维连接的符号串文法向多维推广，是一种应用较广泛的高维文法。7.5 形式语言在图形识别中的应用7.5.4 树文法 例子 对一个边长为a, b和c的立方体，如果用一维字符串描述，有的边会重复，用树表示可直接分成三个叉，每条边仅出现一次。7.5 形

47、式语言在图形识别中的应用7.5.4 树文法 树的定义：树是具有一个或一个以上结点的有限集T，它具有以下性质：(i)具有唯一的被指定为根的结点。(ii)其余的结点被分到m个不相交的集合T1,T2,Tm中，且这些子集的每一个又都是树，称为T的子树。 从定义可以看出，树的每个结点都是这个树中所包含的某个子树的根。 一个结点具有子树的个数称为该结点的秩。秩的相关定义 秩：一个结点的直接分支数定义为该结点的秩。 叶结点：秩为零的结点称为叶结点（终端结点）。 分支结点：秩不为零的结点称为分支结点（非终端结点）。7.5 形式语言在图形识别中的应用7.5.4 树文法 讨论 在计算机中数据的表示是有序的，所以子

48、树的排列也是有一定的相对次序。 同一层上各子树间相互交换位置就构成不同的树。 因此，树是有序的。 比如前面的立方体，叶结点就是有序的。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 例子 树的另一种表示法 圆括

49、号法 与左括号紧挨着的字母表示根。 其子树是紧挨着根字母的一串左右成对的括号中的内容。 例子7.5 形式语言在图形识别中的应用7.5.4 树文法 树文法的定义 上下文无关文法和树文法的对应关系 如果将树用圆括号法表示，则上下文无关语言中的字符串和由树文法生成的树之间存在对应关系。 描述 GT中的每一次推导，就用圆括号表示出了推导过程中生成式的使用次序，根据它可确定生成式的构造。 例子作业 试用树文法生成单位边长的立方体，定义三个基元为立方体的三种方向的边。7.6 句法分析 若对两类模式进行分类，应判别描述模式的字符串x是否可由文法G产生。 假若G能生成x，则x属于1，否则x属于2。 推广到M类

50、模式，应先确定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 通过生成树的句法分析 生成树

51、构造原则 已知一个句子x和文法G，若x是用上下文无关文法生成的，则其生成树可用如下原则构造： 把推导中出现的属于VT的元素作为树的叶，属于VN的元素作为树的结点，每一片叶和每一个结点都设置一个标号。 将S作为树根的标号。 如果一个结点的后代子句中，至少有一个字符与它本身不同，则该结点的标号必属于VN 。 如果结点A有k个直接后代A1, A2, ,Ak，且它们是从左到右排列。则一定存在这样一条生成式：A- A1A2Ak 。7.6 句法分析7.7.1 通过生成树的句法分析 分析的两种方法：“自上而下”和“自下而上” “自上而下”分析法是从G中的起始符S着手，应用P中的生成式从左至右逐个代换非终止符

52、，以得到x。 “自下而上”分析法是从x本身着手，反方向使用生成式，寻找其中与某个生成式右侧部分相同的字符子串，将它用生成式左边的字符代换，直至最后达到起始符S。7.6 句法分析7.7.1 通过生成树的句法分析 例子 分析a2b2c2 分析a2bc 自下而上 自上而下7.6 句法分析7.7.2 CKY(Cocke-Kasami-Younger)分析算法 采用树结构的分析算法实质上是穷举试探，它对任意上下文无关文法所需的分析时间，可能按字符串长度呈指数增长。 为此，采用CKY的分析算法，其时间为输入串长度的三次方。7.6 句法分析7.7.2 CKY(Cocke-Kasami-Younger)分析算

53、法 问题描述 设描述某类模式的文法是上下文无关的，G=(VN,VT,P,S)，其生成式是乔姆斯基范式。 设输入字符串x=a1a2an, |x|=n，要求设计CKY算法来判断x是否属于L(G)。 CKY算法的关键 构表原则 构表步骤7.6 句法分析7.7.2 CKY(Cocke-Kasami-Younger)分析算法 CKY算法实例7.6 句法分析7.7.3 最小距离误差的句法校正分析 上面的识别过程并未考虑图形模式的随机干扰。 实际上，在获取模式的基元描述时，由于随机噪声的干扰，可能发生部分的基元描述错误。 例：模式的正确描述字符串为abcbbc，受干扰后成为一有误差的字符串abbbbac。

54、为了识别这种存在某些误差的串，在比较简单的场合，可以采用通过计算最小距离误差的校正句法分析。7.6 句法分析7.7.3 最小距离误差的句法校正分析 字符串的相似性度量 字符串中的误差通常归纳为三类：代换误差、抹去误差和插入误差，可将它们用相应的转换式来表示。 代换误差的转换 抹去误差的转换 插入误差的转换 转换距离 例子7.6 句法分析7.7.3 最小距离误差的句法校正分析 误差覆盖文法的构成 最小距离误差的句法校正分析 设L(G)是一给定文法，y是一个给定的带有误差的句子，则最小距离误差的句法校正分析实质上就是在L(G)中找出x，使其满足最小距离准则。 d(x,y)的计算： 构成一个误差校正

55、程序的过程时，修改给定文法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)d(x,L(G2)，则x属

56、于L(G1) ，否则x属于L(G2)。 c类模式 对于c类模式情况，可对相应的c个文法G1,G2,GL分别进行最小距离误差校正句法分析，计算出待分类的输入模式x和各类语言间的距离d(x,L(Gk)，k=1,2,c。若对于所有的ji，有d(x, L(Gi)d(x, L(Gj)，则x属于L(Gi) 。ji 7.7 句法模式识别的随机文法 在模式识别中，由于测量噪声的影响以及对模式识别的特征可能缺乏全面的知识，使得被研究的过程存在着某种程度的不确定性，造成描述这类模式的语言的歧异性。 对于一个特定模式类产生的字符串，本来是由某一种文法说明的，但实际上除了该文法外还有其它文法也能产生该类中的字符串。

57、例子 由文法G1产生的语言L(G1)中有句子aaab，由文法G2产生的语言L(G2)中有句子baab。由于测量上的误差，可能使aaab变成abab，也可能使baab变成abab。如果以此为训练样本来推断G1和G2，两种语言L(G1)和L(G2)就变成相交的了。7.7 句法模式识别的随机文法 为了解决这类问题，提出了用随机语言的处理方法 对于一种语言L中的每一条字符串x，分配一个概率p(x)，它用来表征L的不确定性。 如果一个模式文法可能产生某些“不想要”的句子，就可分配以很小的概率。 “不想要”的句子是由噪声产生的，并不真正代表该类中的模式。 把形式语言的概念推广到随机语言有两种途径 把文法的生成式随机化 把识别装置的状态转移条件随机化7.7 句法模式识别的随机文法7.7.1 随机文法 定义 例子 由随机文法GS生成随机语言L