图像识别简介.ppt

形式语言的基本概念 形式语言最初的设想是实现计算机的自然语言(如英语)理解，这一设想虽然至今尚未全部完成，但是，在形式语言的基础上，成功地建立起学科分支：编译器设计、自动机理论、计算机语言以及我们现在讨论的句法模式识别。这里仅就与句法模式识别有关的基本概念作一介绍。 一、????????????? 基本定义 字符集是一任意的有限符号集合。在某一字符集上的句子是任一有限长度字符串，该字符串由取自于这一字符集上的字符组成。如，给定一字符集{0,1}，它上面的有效句子集合为：{0,1,00,01,10,….}。 语言定义为某一字符集上的任一句子集合，该集合不一定是有限的。 给定了字符集、句子、语言的基本定义之后，仅仅明确了下述问题：字符组成句子，句子组成语言。字符究竟是按照什么规则组成句子，进而组成语言？这有待于对语法的研究。与任何一种自然语言一样，语法在形式语言中起中心作用。句法模式识别中的各个环节，都是围绕着语法进行研究的。 高维语法 经典形式语言中定义的语法，原是为自然语言理解设计的，因此，它只处理字符串组成的语言。字符串是一维级联的，难以表达结构信息，为了更好地描述物体的各部分空间联接关系，提出了不少高维语法。这里简单介绍图像描述语言(PDL)和树语法。 一、??? 图像描述语言(PDL) 图像描述语言主要用于图形形状结构，其基元是有向线段，该线段有头和尾，线段之间的连接方式与矢量运算相仿。表示成图中的加、“x”乘和“*”乘。 例子： 其中“ ”表示有向线段d的反向。显然，该语法产生的语言是： 它描述的图形结构为 P： 模糊模式识别简介 在现实世界中，模糊性和随机性是两大不确定性。尽管两者有本质的区别，但是，二者之间却可以相互交叉。同一研究对象往往不仅含有模糊性而且含有随机性。例如，人们说常“明天是好天气的可能性有多大”，“他交好运的概率很小”，“他很少能较早来上班”，这里“好天气”，“好运”，“较早”都是模糊概念，而“可能性有多大”，“很小”，“很少”都是指事件发生的“概率”。对这类问题已经超出了经典概率论的范围。为此，引入模糊集合的概念。 在定义模糊子集的基础上，可以得到一系列的模糊运算、模糊等价关系、模糊相似关系、模糊数、模糊测试等，为模糊模式识别提供了基础。 从本质上来说，模式识别所要讨论的核心问题，便是如何使机器能模拟人脑的思维方法，来对客观事物进行更为有效的识别和分类。一方面现有的广为运用的统计模式识别方法与人脑进行模式识别的方法相比，其判别还很大，另一方面有待识别的客观事物又往往具有不同程度的模糊性。因此，许多学者运用模糊子集理论来解决模式识别的问题，并已经获得了可喜的应用成果。 目前，模糊模式识别的基本方法主要有： (1)???基于最大隶属原则的识别 (2)???基于择近原则的识别 (3)?? 基于模糊等价关系的模式分类 (4)?? 基于模糊相似关系的模式分类 数学上，统计模式识别问题可以归结为：对一组给定的样本集合，找出其最佳的分类判决函数 ，并作判决： 若对所有的 均有： 则作判决： 　　　因为处理的是分类问题，因此最佳的意义是分类误差最小。 由于求解最佳判决函数的出发点和途径不同，因此产生了各种不同的分类方法： 　?判别函数方法 　贝叶斯分类器：判别函数表示为似然比，也称为　 　最大似然率分类器或最小损失分类器 　集群分类方法：它几乎不需要有关待分样本的先验知识。 分类器是某种由硬件或软件组成的“机器”： 计算c个判别函数gi(x) 最大值选择 ARGMAX g1 . . . g2 gc . . . x1 x2 xn a(x) 判别函数方法 　　在很多分类问题中，往往必须知道待分样本的先验知识。这里假设我们已经知道判别函数的形式，剩下的问题是如何求判别函数的待定参量以及进行分类判决。诚然，由分类者随心所欲地选择判别函数的形式，是件快事。但是，类别函数选择不合适，会导致分类误差的增加。 一、??????? 线性判别函数 线性判别函数的一般形式为： 其中， ， 分别称为扩充了的特征矢量和权矢量。 使用线性判别函数的分类判决有下述两种情况： l???????? 第一种情况： 每一类可以用一个判决平面与其它所有类隔开，在这种情况下，有M个判决函数： l???????? 第二种情况： 每一类与其它所有各类可以由不同的判决平面一一隔开，也就是说，各类是可分段可分的，共有 个判决面。 判决函数可以写成 若对于所有的