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

《中科院《模式识别》——第七章》由会员分享，可在线阅读，更多相关《中科院《模式识别》——第七章（143页珍藏版）》请在金锄头文库上搜索。

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

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

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

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

5、，只要对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 集合论中的关系运算,二元关系的性质 定义：反

6、对称 集合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 集合论

7、中的关系运算,等价关系 可以用图形方法分析研究等价划分：由于等价关系是自反的、对称的、传递的，因此由这些性质的图形特点可知： 一个集合X上的等价关系R的关系图，其每个结点必有环； 若两个结点间有边相连，则必有方向彼此相反的两条有向边； 若图中任何两个结点是可达的，则必有边直接相连。 例子,7.1 集合论中的关系运算,兼容关系 如果X中的关系R是自反的而且是对称的，则称R是一个兼容关系。 所有的等价关系是兼容关系； 兼容关系不一定是传递的。 偏序关系 集合P上的二元关系R称为P上的一个偏序关系，当且仅当R是自反的、反对称的和传递的。 偏序关系通常用“=”表示，但注意“=”不一定是实数中的“小于或

8、等于”，表示的是更普遍意义上的偏序关系。 例子 半序集 全序或线性序,7.1 集合论中的关系运算,二元关系的复合 定义 人类的亲属关系是最容易理解的复合关系 叔侄关系是兄弟关系和父子关系的复合，可表示为：A”兄弟”B且B”父子”C - A”叔侄”C,7.1 集合论中的关系运算,二元关系的复合 关系图,7.1 集合论中的关系运算,二元关系的复合 关系的复合运算可以施加于自身 表示为：RR =R2，RRR =R3 ， 传递闭包 例子,7.2 形式语言理论和句法模式识别,形式语言的起源可以追溯到二十世纪五十年代； 乔姆斯基(Chomsky)等科学家在研究语言的工作中发展了文法的数学模型； 其基本目的

9、是发展一种应用于计算机的文法，使它有描述自然语言的能力，例如英文。 如果能做到这一点，则有希望“教”计算机理解自然语言，以达到翻译的目的。,7.2 形式语言理论和句法模式识别,形式语言的基本目的迄今为止尚未完全实现，但在这个领域的研究成果却大大冲击了其它一些领域 计算机编译系统的设计 计算机语言 自动机理论 模式识别,7.2 形式语言理论和句法模式识别,在模式识别中，如果大量复杂的模式的集合，能用一组为数不多的简单的模式基元和文法规则来描述，则对每一个模式的识别，就可以按给定的一组文法结构规则来剖析； 如果解析的结果表明，模式基元能为给定的文法规则所接受，则可判别它属于该模式类，否则就不属于该

10、模式类。,7.2 形式语言理论和句法模式识别,7.2.1 形式语言理论中的某些定义 形式语言是一种抽象语言，它可以包括人类使用的自然语言、计算机使用的各种语言、数学中的公式语言等。 自然语言（英文）：它的基本组成是有限个字母，将字母（组成的单词）按一定的文法规则排列，可以构成句子，而一种语言则是所有句子的集合。 人类的自然语言是一个不可数的有穷集 英文：26个字母按一定的文法规则组合，可以表达无数的思想内容。,7.2 形式语言理论和句法模式识别,7.2.1 形式语言理论中的某些定义 字母表和符号串 字母表：以某些符号作为元素的非空有穷集，以V或表示。 符号串：由字母表中符号组成的任何有穷序列。

11、 例子 空符号串：不包含任何符号的串，用表示。 符号串的长度：符号串x所包含的符号个数，用|x|表示。 例子 符号串的联接：若x和y都是符号串，则把y符号串写在x符号串之后，就得到联接的符号串xy。 例子,7.2 形式语言理论和句法模式识别,7.2.1 形式语言理论中的某些定义 字母表和符号串 符号串集合的乘积 例子 如果A和B只是代表一个符号串，而不是符号串的集合，则乘积AB与符号串的联接结果相同。 符号串和符号串集合A的幂 集合A的正闭包、闭包 字母表V的幂 集合V的正闭包、闭包 例子,7.2 形式语言理论和句法模式识别,7.2.1 形式语言理论中的某些定义 文法 一种语言中构成句子所必须

12、遵守的规则； 由某种语言的字母表中的字母所组成的串不一定都是该语言的句子； 只有当一个串符合该语言的文法规则时，才能算是该语言的句子，否则就不是该语言的句子。,7.2 形式语言理论和句法模式识别,7.2.1 形式语言理论中的某些定义 文法定义 文法举例 在生成规则P中，带的符号称为语法元，不带的符号称为单词； 一个简单句的生成由语法元()开始，反复把生成规则中箭头左边的部分用其右边的部分替换，直到所得的形式中不再出现语法元而只有单词为止。 简单句“The boy runs.”符合给定的文法规则，因为它可以由上述的文法规则产生。 生成过程,7.2 形式语言理论和句法模式识别,7.2.1 形式语言

13、理论中的某些定义 文法举例 文法树,7.2 形式语言理论和句法模式识别,7.2.1 形式语言理论中的某些定义 利用文法树可以阐明文法的形式化定义： 文法树的根一定是文法G的起始符S； 树的叶一定是终止符； 树的每一个分支（子树）在沿着根到叶的方向上可以表示成一个直接推导的生成式； 如果利用文法树的逆过程，则可将生成过程重新构造出来。,7.2 形式语言理论和句法模式识别,7.2.2 语言的生成过程 利用文法G来生成语言的过程中的一些规定 非终止符VN用大写英文字母：S, A, B, C, 终止符VT用英文字母表起始部分的小写字母：a, b, c, 终止符组成的字符串用英文字母表中尾部的小写字母：

14、u, v, w, x, 终止符和非终止符混合组成的字符串用希腊字母：, , , , ,7.2 形式语言理论和句法模式识别,7.2.2 语言的生成过程 利用文法G来生成语言的过程中的一些规定 生成式P由以下形式的表达式组成： -，其中是V+中的字符串， 是V*中的字符串，“- ”表示字符串被所取代。 =表示根据文法G，由一字符串直接推导出另一字符串。 例子,7.2 形式语言理论和句法模式识别,7.2.2 语言的生成过程 句型和句子 定义 句型是由起始符开始进行推导而得到的由字母表中的符号（包括VN 、VT和）组成的任意字符串； 句型和句子关系 句子一定是由字母表中终止符组成的字符串。,7.2 形

15、式语言理论和句法模式识别,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

16、|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